Asynchronous encoding of digital content

A server generates a combination of symbols requested by a set of users in response to the symbols requested by each user in the set being cached by the other users in the set. A transmitter in the server multicasts the combination of symbols to the set of users based on a transmission deadline associated with the set of users.

BACKGROUND

1. Field of the Disclosure

The present disclosure relates generally to communication systems and, more particularly, to asynchronous encoding of digital content conveyed by communication systems.

2. Description of the Related Art

Content providers such as Netflix, Amazon, Hulu, YouTube, and Verizon provide digital content to end-users over wired or wireless communication networks. For example, end-users may watch television shows or movies using video-on-demand or streaming services supported by the content providers. These services are very popular and may consume a significant portion of the bandwidth of the communication network during peak usage. For example, Netflix alone has been estimated to use as much as a third of the bandwidth available in the U.S. between 9 PM and midnight. Caching portions of the digital content before it is requested by end-users may reduce the strain on the network. For example, randomly selected portions of different programs may be prefetched into caches associated with different users before the users choose one or more of the different programs for viewing. If the user then selects one of the programs for viewing, only the un-cached portion needs to be transmitted over the network.

DETAILED DESCRIPTION

The effectiveness of caching can be increased by prefetching different portions of programs (or other digital content) into caches associated with different users that share the same network connection to the content provider. The portions of the programs can be prefetched into the different caches so that the caches hold complementary portions of the programs. For example, if the content provider is providing two programs (A, B) that are each divided into two portions (A1, A2, B1, B2), the cache associated with a first user may hold the portions (A1, B1) and the cache associated with a second user may hold the complementary portions (A2, B2). Then, if the users request different programs, the content provider can transmit linear combinations of the complementary portions cached in different caches over the shared network connection to the users. The users can use their cached portion to invert the linear combination and retrieve the un-cached portion of their requested programs. For example, if the first user requests program A and the second user requests program B, the content provider can transmit a linear combination such as A2⊕B1(where ⊕ represents the exclusive-OR (XOR) operation) over the shared network connection. The first user can retrieve the portion A2using the cached portion B1to invert the linear combination (A2⊕B1⊕B1=A2) and the second user can retrieve the portion B1using the cached portion A2to invert the linear combination (A2⊕ B1⊕A2=B1). The bandwidth needed to transmit the linear combination is half the bandwidth required to transmit the two portions A2and B1separately.

Time-sensitive or delay-sensitive services such as video-on-demand or other streaming services must satisfy two basic constraints. First, the service must be able to respond to asynchronous user requests because users can request content (such as a movie or television program) at any time and at any point within the content, as well as being able to rewind or fast-forward through the content. Second, the service must be able to provide the requested content within a time interval set by the delay sensitivity of the user. For example, when a program begins and a user is buffering the beginning of the program, the user may abandon the program if the user does not receive responses with a latency of less than about 0.5-2 seconds. Once the buffer is full, the required latency may be increased to approximately 30 seconds. However, if the user fast-forwards or rewinds, the program may be re-buffered from its new starting point and the latency may be reduced to a smaller value such as 0.5-2 seconds until the re-buffering is complete. Some embodiments of the techniques described above for generating linear combinations of cached portions of data for different users do not account for the delay sensitivity of the different users and consequently are not well-suited for supporting delay sensitive applications.

The bandwidth consumed by delay-sensitive applications, such as video-on-demand and streaming services, can be reduced by generating linear combinations of symbols requested by a set of users when the symbols requested by each user in the set are cached by all of the other users in the set and each user has cached all the symbols requested by the other users. The linear combinations may then be transmitted prior to a minimum deadline requested by the users. In some embodiments, a service provider can maintain a queue to store symbols or linear combinations of symbols requested by users. For example, the queue may store a first symbol that represents a portion of a program requested by a first user. A linear combination of the first symbol and a second symbol that represents a portion of a program requested by a second user may be formed and stored in the queue if the first user has cached the second symbol and the second user has cached the first symbol. This process can be repeated to incorporate symbols requested by subsequent users into the linear combination as long as the symbol requested by the subsequent user is cached by all the previously-incorporated users and all the symbols requested by the previously-incorporated users are cached by the subsequent user. The linear combination can then be transmitted to the first user, the second user, and any subsequently-incorporated users prior to a deadline requested by the first user, the second user, or the subsequently-incorporated users. Some embodiments may use a sequential rule to decide whether to form a linear combination of a requested symbol and a symbol or linear combination of symbols in a queue entry by comparing the requested symbol and cached symbols for a requesting user to the requested symbols and cached symbols for users associated with the queue entries.

FIG. 1is a block diagram of a communication system100according to some embodiments. The communication system100includes a network105that supports a network connection110between a content provider115and a plurality of users120,121,122(collectively referred to as the “users120-122”). The term “user” may refer to a device that transmits or receives information over the network connection110, such as a desktop computer, laptop computer, tablet computer, a smart phone, or smart television, as well as the person that is using the device. Furthermore, each of the users120-122shown inFIG. 1may represent a single user or a plurality of users. In the interest of clarity,FIG. 1depicts one content provider115, one connection110and three users120-122. However, some embodiments of the communication system100may include different numbers of these elements. For example, the communication system100may include hundreds, thousands, or millions of users120-122. For another example, the communication system100may include multiple content providers115and the content providers115may be implemented using a plurality of servers that may be geographically dispersed. Embodiments of the network105or the network connection110may be implemented using wired connections, wireless connections, or any combination thereof.

The users120-122are associated with corresponding caches125,126,127(collectively referred to as “the caches125-127”) that are used to store information received from the content provider115. Caching of the information received from the content provider may be performed before, after, or concurrently with providing this information to the users120-122. Some embodiments of the caches125-127include cache entries or cache lines and each cache entry or line may store a segment of a block of digital content received from the content provider. For example, as discussed in detail herein, the caches125-127may be able to store segments of blocks of digital content selected from the blocks of digital content that are transmitted over the network connection110.

Blocks, segments of blocks, or combinations of segments of blocks of digital content may be transmitted over the network connection110in response to requests for the blocks from one or more of the users120-122. As used herein, the term “symbol” is used to refer to a portion of information that is requested by one of the users120-122for transmission by the content provider115. Thus, a requested symbol may include blocks, a segment or portion of a block, a combination of segments of blocks, or other parts of the digital content provided by the content provider115.

Symbols may be pre-provisioned to the caches125-127or the caches125-127may cache symbols that were previously transmitted to the corresponding user120-122. For example, the caches125-127may select and store transmitted symbols based on criteria including fullness of the caches125-127, a number of symbols cached in the caches125-127, and ages of symbols that are cached in the caches125-127. The cache selection process may therefore be referred to as a dynamic process or an “online” process because the caches125-127select symbols concurrently with provision of the digital content to the users120-122. For example, the caches125-127may select and cache symbols that represent a television show that is currently being watched by the user122. The cache selection process may also be referred to as a “decentralized” process because the caches125-127may not communicate with each other and each cache125-127can independently select and cache symbols that are being conveyed over the network connection110. Consequently, the sets of symbols stored in the caches125-127may evolve and change as different programs are requested by the users120-122. Furthermore, the caches125-127may store different and complementary sets of symbols that have been requested by the users120-122, which may provide opportunities to reduce the volume of data transmitted over the network connection110by transmitting linear combinations of the symbols stored by the different caches125-127, as discussed herein.

Some embodiments of the content provider115may reduce the network resources consumed by symbol transmissions by forming linear combinations of the requested symbols. For example, the content provider115may generate linear combinations of symbols requested by the set of users120-122when each symbol requested by one of the users120-122in the set is cached by all of the other users120-122in the set and each user120-122has cached all the symbols requested by the other users120-122in its associated cache125-127. Some embodiments of the content provider115may form the linear combination by performing an exclusive-OR of symbols requested by the users120-122. This process may be referred to as “coding” or “encoding” the symbols for transmission over the network105. Symbols and linear combinations of symbols may be stored in entries of a queue130and the symbols or the linear combinations may then be transmitted prior to a minimum deadline requested by the users120-122or prior to some other time indicated by transmission deadlines requested by the users120-122. Upon reception of the linear combination, the users120-122may reconstruct (or “decode”) their requested symbols using their cached symbols.

FIG. 2is a diagram of an example of a data packet200that can be used to transmit linear combinations of symbols according to some embodiments. Some embodiments of the data packet200include information identifying the symbols that contribute portions of the linear combinations transmitted by the data packet200. The identifying information may be transmitted in a header that includes symbol identifiers205that identify the different symbols represented in the linear combinations. For example, a header including symbol identifiers205may include information identifying programs A and B if the invertible combination includes symbols from programs A and B such as A2and B1. The data packet200may also include linear combinations210of symbols. For example, the data packet200may include a linear combination210such as A2⊕B1.

FIG. 3is a block diagram of a server300for providing coded symbols in response to user requests according to some embodiments. Content providers such as the content provider115shown inFIG. 1may implement one or more servers300to provide coded symbols to users such as the users120-122shown inFIG. 1. In the illustrated embodiment, files including digital content that represent requested programming, such as multimedia programming, television programming, films, live broadcast, and the like, may be stored by the server300or at an external location. The files may be split into a sequence of symbols of a fixed size (e.g., a size that may range from 1 kB to 10 kB). User requests may then be translated into symbol requests, which may allow the users to skip over content, ask for content at locations within the program, fast-forward, rewind, or perform other operations.

Requests305from different users arrive asynchronously at a request handler310. Some embodiments of the request handler310may read requests305from a plurality of open network connections or sockets. The request handler310may then add the arriving requests305to entries of a request queue315. The request queue315includes entries to hold pending requests305and may be implemented as a first-in-first-out (FIFO) queue. New requests305may therefore be added to the tail of the request queue315and previously queued requests305may be removed from the head of the request queue315. For example, the request handler310may add the most recent request305to an entry at the tail of the request queue315.

The server300includes an encoder320that may form linear combinations of requested symbols and symbols or linear combinations of symbols stored in a coded symbol queue325. Some embodiments of the queue130shownFIG. 1may be implemented using the coded symbol queue315. The encoder320may be able to remove requests from the entry at the head of the request queue315or, if the request queue315is empty, the encoder320may block further processing until a new request305is added to the request queue315. The encoder320can read the symbol requested by the request305, e.g., from a memory location in the server300or from an external memory device. The encoder320may then iterate over the entries of the coded symbol queue325to determine whether the requested symbol can be coded with a symbol or linear combination of symbols stored in one of the entries of the coded symbol queue325, as discussed herein. Some embodiments of the encoder320iterate over the entries of the coded symbol queue325according to a sequential rule. For example, the encoder320may iterate over the entries in a sequence based on the transmission deadlines associated with the entries so that entries corresponding to an earliest minimum deadline for transmitting a symbol or linear combination of symbols in the entry are accessed first and entries corresponding to the latest minimum deadline are accessed last. However, other sequences that are a function of the transmission deadlines may also be used. If the requested symbol did not satisfy the criteria for coding with information in any existing entry of the coded symbol queue325, the encoder320may create a new coded content symbol containing only the requested symbol and add it to an entry at the tail of the coded symbol queue325.

The coded symbol queue325includes entries to hold a list of coded symbols, which may include a single symbol or a linear combination of symbols. Some embodiments of the coded symbol queue325may be implemented as a FIFO queue325and therefore coded symbols may be added to an entry at the tail of the coded symbol queue325and removed from the entry at the head of the coded symbol queue325. Each entry is associated with a transmission deadline for the coded symbol and entries in the coded symbol queue325may be ordered according to the transmission deadline. The coded symbols may only be removed from the coded symbol queue325after remaining in the coded symbol queue325for an amount of time determined by the transmission deadline. For example, an entry at the head of the coded symbol queue325may be removed when the current time is equal to the transmission deadline.

The server300includes a transmitter330that can remove coded symbols from entries at the head of the coded symbol queue325. If the coded symbol queue325is empty or the entry at the head of the coded symbol queue325does not satisfy the condition for removal indicated by its transmission deadline, the transmitter330may block further processing until a coded symbol at the head of the coded symbol queue325is eligible for transmission. The transmitter330may also determine the members of a multicast group that includes the set of users that requested symbols that were coded together in the entry that is ready for transmission. The transmitter330may then multicast or broadcast the coded symbol over the network to the set of users in the multicast group. In some embodiments, in response to expiration of the transmission deadline of a request in the entry at the head of the coded symbol queue325, the coded symbol queue325may be searched to determine the largest set of requests in the coded symbol queue325that can be coded together with the expiring request. If any such requests are found, the transmitter330may remove the requests from the coded symbol queue325. The removed requests may be merged with the expiring request and the transmitter330may multicast the resulting merged request to the set of users corresponding to the merged request.

FIG. 4is a diagram of a sequence400of user requests and a corresponding coded symbol queue405of a server according to some embodiments. The coded symbol queue405may be used as the coded symbol queue325shown inFIG. 3. Time is measured in arbitrary units increasing from left to right as indicated by the numerals 1-9, which may refer to cycles, timeslots, or other time intervals. The sequence400depicts user requests from three users (User1, User2, and User3) in each of the time intervals. The coded symbol queue325has at least three entries (Entry1, Entry2, and Entry3) that can store symbols or linear combinations of symbols prior to transmission. The entries are associated with a corresponding transmission deadline, which is set to three time intervals for each of the entries. Thus, a symbol or a linear combination of symbols may remain in an entry of the coded symbol queue405for a maximum of three time intervals, after which the symbol or linear combination of symbols in the entry is to be transmitted. Some embodiments may use other definitions of the transmission deadline, such as a transmission deadline that indicates that the entry is to be transmitted when the transmission deadline is equal to a current time, and different transmission deadlines may be associated with different entries, as discussed herein.

At time interval1, User1requests transmission of symbol A1. The server determines that the coded symbol queue405is empty and thus there are no opportunities for coding the requested symbol A1with a previously requested symbol. The requested symbol A1is therefore added to Entry1of the coded symbol queue405.

At time interval2, User2requests transmission of symbol B1. The server determines (using embodiments of the techniques described herein) that the symbol B1may be coded with the previously requested symbol A1. For example, the server may determine that User1has cached the symbol B1and User2has cached the symbol A1. The server may therefore code the symbols A1and B1, e.g., by forming a linear combination A1⊕B1. In the illustrated embodiment, the symbol “⊕” indicates that the linear combination is an exclusive-OR operation, although linear combinations over fields larger than the binary field or functions other than linear combinations may also be used. The linear combination is then stored in Entry1of the coded symbol queue405.

At time interval3, User1requests transmission of symbol A2. The server determines that the symbol A2is not eligible for combination with the linear combination A1⊕B1because the symbols A1and A2were both requested by User1, which does not have a cached copy of either symbol. The symbol A2may therefore be stored in Entry2of the coded symbol queue405. The symbol A1will have been in the coded symbol queue405for three time intervals at the expiration of time interval3. The linear combination A1⊕B1may therefore be removed from the coded symbol queue405and transmitted at the end of time interval3, as indicated by the dashed box around the linear combination A1⊕B1.

At time interval4, User3requests transmission of symbol C1. The server determines (using embodiments of the techniques described herein) that the symbol C1may be coded with the previously requested symbol A2. For example, the server may determine that User1has cached the symbol C1and User3has cached the symbol A2. The server may therefore code the symbols A2and C1by forming a linear combination A2⊕C1. The linear combination is then stored in Entry1of the coded symbol queue405.

At time interval5, User2requests transmission of symbol B2. InFIG. 4, the box representing the time interval5is larger than the boxes for other time intervals to accommodate the notation. This does not necessarily indicate that the time interval5is different than any other time intervals. The server determines (using embodiments of the techniques described herein) that the symbol B2may be coded with the linear combination A2⊕C1. For example, the server may determine that User1has cached the symbols B2and C1, User2has cached the symbols A2and C1, and User3has cached the symbols A2and B2. The server may therefore code the symbol B2by forming a linear combination A2⊕C1⊕B2. The symbol A2will have been in the coded symbol queue405for three time intervals at the expiration of time interval5. The linear combination A2⊕C1⊕B2may therefore be removed from the coded symbol queue405and transmitted at the end of time interval5, as indicated by the dashed box around the linear combination A2⊕C1⊕B2.

At time interval6, User3requests transmission of symbol C2. The server determines that the coded symbol queue405is empty and thus there are no opportunities for coding the requested symbol C2with a previously requested symbol. The requested symbol C2is therefore added to Entry1of the coded symbol queue405.

At time interval7, User3requests transmission of symbol C3. The server determines that the symbol C3is not eligible for combination with C2because both symbols were requested by User3, which does not have cached copies of either symbol. The symbol C3may therefore be stored in Entry2of the coded symbol queue405.

At time interval8, User1requests transmission of symbol A3. The server determines (using embodiments of the techniques described herein) that the symbol A3may be coded with the symbol C2. For example, the server may determine that User1has cached the symbol C2and User3has cached the symbol A3. The server may therefore code the symbols by forming a linear combination C2⊕A3. The symbol C2will have been in the coded symbol queue405for three time intervals at the expiration of time interval8. The linear combination C2⊕A3may therefore be removed from the coded symbol queue405and transmitted at the end of time interval8, as indicated by the dashed box around the linear combination C2⊕A3.

At time interval9, User2requests transmission of symbol B3. The server determines that the symbol B3is not eligible for combination with C3. For example, User2may not have a cached copy of the symbol C3or User3may not have a cached copy of the symbol B3. The symbol B3may therefore be stored in Entry2of the coded symbol queue405. The symbol C3will have been in the coded symbol queue405for three time intervals at the expiration of time interval9. The symbol C3may therefore be removed from the coded symbol queue405and transmitted at the end of time interval9, as indicated by the dashed box around the symbol C3.

In some embodiments, a server such as one or more servers implemented by the content provider115shown inFIG. 1or the server300shown inFIG. 3may utilize various criteria or thresholds to determine whether symbols requested by one set of users may be coded and transmitted together with symbols requested by another set of users.

The user requests may be represented by a triple (k, S, t), where k∈{1, 2, . . . , K} is the user requesting the symbol, S⊂{1, 2, . . . , K} is the subset of users that have already cached the requested symbol in their cache, and t is the transmission deadline that indicates when the request is to be served. The transmission deadline t is assumed to be an integer that represents an arbitrary time interval such as milliseconds, but other embodiments may use other deadlines. The triple (k, S, t) may be written (k, S) if the value of the deadline is not material. In this notation, the identifier of the actual symbol requested by the user is suppressed. Furthermore, each request (k, S) satisfies the property k∉S because otherwise the request could be satisfied by a symbol cached by the requesting user.

The video server may create coded multicasting opportunities for different users requesting symbols for a streaming application. For example, three users may issue a sequence of requests:(1; 2, 3) (2; 1) (2; 1, 3) (3; 1, 2) (1; 2)
The first request is from user1and indicates that users2,3have cached the requested symbol, the second request is from user2and indicates that user1has cached the requested symbol, etc.

The video server can satisfy requests (k1, S1, t1), (k2, S2, t2), . . . , (kL, SL, tL) using a single coded multicast transmission if the symbols requested by each user in the set of requesting users are cached by all of the other users in the set and each user has cached all the symbols requested by the other users. This condition may be represented as:

kℓ∈⋂j≠ℓ⁢Sj
for all 1∈{1, 2, . . . , L}. The coded transmission can be interpreted as a request by users
K={k1,k2, . . . ,kL}
with shared cache content

S=⋂Lℓ=1⁢Sℓ
and a request deadline of:

t=minℓ∈{1,2,…,L}⁢⁢tℓ.
The shared request can therefore be indicated as (K, S, t). In some embodiments, other functions (besides a minimum function) of the transmission deadlines may be used to determine the request deadline.

Two shared requests (K1, S1, t1) and (K2, S2, t2) can be merged so that they can be satisfied by a single coded multicast transmission from the video server if K1⊂S2and K2⊂S1. The merged request may then be represented as:
(K1∪K2;S1∩S2;min{t1,t2}).
The video server may transmit the coded multicast packet including the linear combination of symbols when the current time is equal to the transmission deadline of the merged request. As discussed herein, linear combinations of symbols associated with the merged requests may be stored in a queue that is maintained by the video server. In some embodiments, other functions (besides a minimum function) of the transmission deadlines may be used to determine the request deadline for the merged requests.

The size of the queue is a matter of design choice but may be quite large. For example, the server queue may have approximately 103 (unmerged) requests at any time for an HTTP adaptive streaming application with 100 users, a video rate of 100 kb per second, a delay tolerance of two seconds, and the a size of 10 kB. For another example, the server queue may have approximately 106 (unmerged) requests at any time for a progressive download video-on-demand application with 600 users, a video rate of 1800 kb per second, a delay tolerance of 30 seconds, and a symbol size of 4 kB. For yet another example, the server queue may have approximately 109 (unmerged) requests at any time for a complete download video-on-demand application with 1000 users, a video rate of 2400 kb per second, a delay tolerance of 3600 seconds, and a symbol size of 1 kB.

Some embodiments of the video server implement different request merging rules to determine when a newly received request should be merged with an existing request in one of the entries of the queue maintained by the video server. Examples of request merging rules include a first-fit rule, a perfect-fit rule and a τ-fit threshold rule. However, some embodiments of the video server may implement other request merging rules.

The first-fit rule compares the new request to an ordered sequence of requests such as the requests stored in entries of a queue maintained by the video server. The sequence of comparisons follows the ordered sequence of requests. For example, the ordered sequence may include requests (K1, S1, t1), (K2, S2, t2), . . . , (KL-1, SL-1, tL-1), that are ordered based on their transmission deadlines such that t1≦t2≦ . . . ≦tL-1. The video server receives a new request for a single symbol (kL, SL, tL), and, in response, the video server traverses its queue starting from l=1 to find the first request (Kl, Sl, tl), (i.e., the request with the tightest deadline) that can be merged with the new request so that the following conditions hold:
kL∈Sl,
Kl⊂SL.
The newly merged request may be represented as:
(Kl∪{kL};Sl∩SL;min{tl,tL}).
If the video server is not able to find a request that satisfies the conditions, the new request (kL, SL, tL) may be added to the server queue, e.g., to the tail of the server queue.

The perfect-fit rule incorporates additional criteria for merging requests relative to the first-fit rule. In response to receiving a new request for a single symbol (kL, SL, tL), the video server traverses its queue starting from l=1 to find the first request (Kl, Sl, tl), (i.e., the request with the tightest deadline) that can be merged with the new request so that the following conditions hold:kL∈Sl,Kl⊂SL,SL∪Kl=Sl∪kL.
The first two conditions ensure that the two requests under consideration can be merged, as discussed herein. The third condition stipulates that the merging should be optimal in terms of the size of the intersection of cache availability S1∩S2of the merged request.

The perfect-fit rule may be nearly optimal in a large queue regime (L→∞) because the probability that there is a queued request that satisfies all three merging conditions increases as the queue length increases and the third condition ensures that the server bandwidth is minimized. The first-fit rule may be nearly optimal in the small queue regime (L→0).

The τ-fit threshold rule is used to merge requests by comparing measures of a size (or cardinality) of a set of symbols that would be cached by the users associated with the merged request. Mergers that produce a larger set of commonly cached symbols have a higher probability of subsequently being merged with additional requests, whereas mergers that produce a smaller set of commonly cached symbols have a lower probability of subsequent merger with new requests. For example, if the users associated with a merger request do not have any cached symbols in common, no new requests can be merged with the previously merged request. Some embodiments may therefore define a misfit function for the potential merger of two requests (K1, S1, t1) and (K2, S2, t2):

Lower values of the misfit function indicate better fits and a misfit of zero indicates that the fit is optimal. The τ-fit threshold rule may therefore merge two requests (KL, SL, tL) and (K1, S1, t1) when the value of the misfit function is below a threshold value, τ:
ρ((kL;SL),(Kl;Sl))≦τ.

Sequential rules such as the first-fit rule, the perfect-fit rule, and the τ-fit threshold rule have a number of advantages. First, each queued request is considered only once and each merger determination is based only on information in the request and therefore takes O(1) time to evaluate. Thus, the computational complexity to insert one new request into the server queue is O(L), where L is the queue length. Second, for the same reasons, sequential rules can be easily parallelized. For example, several threads may sequentially traverse the queue in parallel, each handling the merging operation of one new request.

FIG. 5is a plot500illustrating scaling of a global coding gain as a function of queue length for a τ-fit threshold rule according to some embodiments. As used herein, the term “global coding gain” is defined as a ratio of the bandwidth for uncoded transmission of a set of symbols and the bandwidth for coded transmission of the set of symbols. The horizontal axis indicates the queue length and the vertical axis indicates the global coding gain. The number of users in the illustrated embodiment is K=10 and a caching probability p, which indicates the fraction of the total content database that is stored in each cache, is set to 0.5. Different curves indicate different values of the threshold.FIG. 5indicates that the optimal value of the threshold decreases as the length of the queue increases. In the limit that the queue length L→∞, the sequential perfect-fit rule (τ=0) asymptotically achieves a global coding gain of:

Kp1-(1-p)K
where p is the caching probability for K users. For example, for K=10, p=0.5, and L=50,000, the global coding gain achieved by the perfect-fit rule is more than 4.5, corresponding to a server bandwidth reduction of more than 75%. This value is quite close to the limiting value of about 5.0 indicated by the above analytical expression.

FIG. 6is a plot600illustrating scaling of the global coding gain as a function of the number of users for a system that implements a first-fit merging rule according to some embodiments. The queue length L is set equal to the number of users K, which may correspond to each user having a constant delay requirement for a single outstanding symbol request. The global coding gain illustrated inFIG. 6can approach a factor of 5.3 for K=1000 users under a first-fit merging rule.

FIG. 7is a flow diagram of a method700for merging new symbol requests with queued symbol requests according to some embodiments. The method700may be implemented in a server such as one or more servers implemented in some embodiments of the content provider115shown inFIG. 1or the server300shown inFIG. 3. At block705, the server receives a request for a symbol from a requesting user. At block710, the server compares the new request with a previous request associated with an entry at the head of a queue (such as a coded symbol queue) associated with the server. For example, the server may compare the symbol requested by the requesting user to symbols cached by one or more previous requesting users associated with the previous request. The server may also compare the symbols requested by the previous requesting users associated to symbols cached by the requesting user. At decision block715, the server determines whether the new request is eligible for linear combination with the request associated with the current entry. For example, the server may apply the first-fit rule, the perfect-fit rule, or the τ-fit threshold rule to determine whether the new request is eligible for merging with the previous request. If not, the server determines whether there are more entries in the queue at decision block720. As long as there are more entries, the server continues to compare the new request with the next sequential entry in the queue at block725. If there are no more entries, the symbol requested in the new request may be stored in a tail entry of the queue at block730.

If the new request is eligible for merger with the previous request associated with of the entries of the queue, the server may form a linear combination of the newly requested symbol and a symbol or linear combination of symbols stored in the queue entry at block735. At block740, the server stores the new linear combination in the current entry of the queue. At block745, the server updates the transmission deadline based on a function of the transmission deadlines associated with the new request and the previous request. For example, the transmission deadline for the merged request may be set equal to the shortest (or nearest or earliest) transmission deadline for the new request and the previous request. In the event that modifying the transmission deadline for the merged request results in an entry with a shorter/nearer/earlier deadline being closer to the tail of the queue than an entry with a longer/further/later deadline, some embodiments of the server may also reorder the queue so that the queue is sequentially ordered from shortest (or nearest or earliest) transmission deadline to longest (or furthest or latest) transmission deadline.

FIG. 8is a flow diagram of a method800for determining whether to transmit a symbol or linear combination of symbols from an entry in a coded symbol queue according to some embodiments. The method800may be implemented in server such as one or more servers implemented in some embodiments of the content provider115shown inFIG. 1or the server300shown inFIG. 3. At block805, the server accesses the transmission deadline associated with an entry at the head of the coded symbol queue. In the illustrated embodiment, the transmission deadline indicates a deadline for responding to the request by transmitting the coded symbols. However, other embodiments may use other formats for the transmission deadline. For example, the transmission deadline may indicate a duration of a time interval that a request is to spend in the coded symbol queue before transmission. At decision block810, the server determines whether the transmission deadline is equal to the current time. If not, the server may wait and perform the comparison again at a later time. If the current time is equal to the transmission deadline, the server removes the coded symbol from the entry at the head of the queue and transmits the symbol at block815. For example, the server may multicast the coded symbol to a set of users that requested information represented in the coded symbol, as discussed herein.