Patent Description:
This application relates generally to multi-source content delivery and, in particular, to excess data traffic reduction during multi-source content delivery.

Redundancy code partitions a data file into K equal-length original symbols and generates N > K coded symbols, each being a mixture (e.g., a linear combination) of the original symbols. Redundancy code allows the decoding of the K original symbols (and thus the recovery of a data file) using any K + δ coded symbols, where δ ≥ <NUM> is a small integer. Some example redundancy codes include Reed-Solomon code, low-density parity check code, fountain code, and network code.

<NPL>, discloses improved dynamic media partitioning algorithm for load balancing on multiple servers to distribute video contents. Each server has a nominal bandwidth and a round trip bandwidth computed as a function of the window size and the round trip time. The total required bandwidth during a given time period is computed and each server takes charge of a part of this total required bandwidth according to the minimum of its nominal bandwidth and its round trip bandwidth.

<NPL>, discloses a transmission control protocol for multi providers environment called multi path TCP where different chunks of the same file are provided by multiple servers. Especially, the ratio of the requests sent to a specific server, i.e. the portion of the requests that the sender takes from the total request, is computed based on the ratio of the window size of this server to the round trip time, RTT, of this server, divided by the sum of all theses ratios for all the servers.

<NPL>, discloses dynamic rate control mechanism adapting to the change of network condition for multi-server content distribution using Erasure codes. A client estimates the rate from each server when the server joins the system according to an initial proportional allocation of the overall rate of the client and later updates this rate based on the measured rate of the server. After each rate estimation, the client sends a request to the server to update the rate of the server.

Independent claim <NUM> defines a method according to the invention. Claims <NUM> and <NUM> define a corresponding non-transitory computer-readable medium and apparatus according to the invention respectively.

Various aspects of the present disclosure relate to circuits, systems, and methods for managing excess data traffic in a multi-source content delivery system.

The present disclosure provides an apparatus that includes, in one implementation, a downloader and a controller. The downloader is coupled to a plurality of servers via a plurality of communication links. The controller is configured to determine initial download requests for the plurality of servers based on predetermined information about a quality of the plurality of communication links. The controller is also configured to send the initial download requests to the plurality of servers with the downloader. The controller is further configured to update the information about the quality of the plurality of communication links after the downloader receives data associated with a data file from the plurality of servers via the plurality of communication links. The controller is also configured to determine subsequent download requests for the plurality of servers based on the updated information about the quality of the plurality of communication links. The controller is further configured to send the subsequent download requests to the plurality of servers via the downloader.

The present disclosure also provides a method that includes, in one implementation, determining initial download requests for a plurality of servers based on predetermined information about a quality of a plurality of communication links coupling the plurality of servers to a downloader. The method also includes sending the initial download requests to the plurality of servers with the downloader. The method further includes receiving data associated with a data file at the downloader from the plurality of servers via the plurality of communication links. The method also includes updating the information about the quality of the plurality of communication links after the downloader receives the data from the plurality of servers via the plurality of communication links. The method further includes determining subsequent download requests for the plurality of servers based on the updated information about the quality of the plurality of communication links. The method also includes sending the subsequent download requests to the plurality of servers with the downloader.

The present disclosure also provides a non-transitory computer-readable medium storing instructions that, when executed by a processor of a computer, cause the computer to perform operations including, in one implementation, determining initial download requests for a plurality of servers based on predetermined information about a quality of a plurality of communication links coupling the plurality of servers to a downloader. The operations also include sending the initial download requests to the plurality of servers with the downloader. The operations further including receiving data associated with a data file at the downloader from the plurality of servers via the plurality of communication links. The operations also include updating the information about the quality of the plurality of communication links after the downloader receives the data from the plurality of servers via the plurality of communication link. The operations further include determining subsequent download requests for the plurality of servers based on the updated information about the quality of the plurality of communication links. The operations also include sending the subsequent download requests to the plurality of servers with the downloader.

In this manner, various aspects of the present disclosure provide for the reduction of excess data traffic, and effect improvements in at least the technical fields of multi-source content delivery.

The present disclosure is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which reference numerals refer to similar element and in which:.

Redundancy-coded multi-source content delivery systems include multiple servers and one receiver. Each server stores a different set of coded symbols of the same data file. The system enables the receiver to enjoy the aggregated bandwidth of all the server-receiver links because all the servers stream coded symbols to the receiver, and the receiver terminates all the streams once it has downloaded sufficient coded symbols from all servers for decoding. Using this approach, every link is fully utilized throughout the course of the download, which maximizes the throughput. However, this download strategy may generate excess traffic across the servers that is significantly more than the K + δ coded symbols requested by the receiver. One exemplary cause is network latency. Once the servers have transmitted K + δ coded symbols, the receiver will finish the reception of these coded symbols after a delay of one single trip time and then send a termination request. This termination request will be received by the servers after another delay of single trip time. This results in a total of one round trip time delay between when enough data has been transmitted for the receiver to decode and the reception of the termination request. During this period, each server will continue to stream coded symbols that are redundant and can be labelled as excess data or overhead. These redundant coded symbols exist in every link and may also exist in the servers' and receiver's lower layer communication buffers under certain implementations. These redundant coded symbols may increase server egress (and thus cost), reduce the network bandwidth available for other network flows, and may cause head-of-line blockages for delivery of subsequent data files.

<FIG> is a block diagram of an example of a system <NUM> for multi-source content delivery according to an implementation of the present disclosure. The system <NUM> illustrated in <FIG> includes a plurality of servers <NUM> that each store coded symbols <NUM> of the same data file. In some implementations, each of the plurality of server <NUM> stores a different set of coded symbols <NUM> of the same data file. In some implementations, each of the plurality of servers <NUM> store a complete identical set of coded symbols <NUM> of the same data file. The plurality of servers <NUM>, which will be described in more detail below, each include an output buffer <NUM> and are configured to, among other things, send or stream coded symbols <NUM> to other components of the system <NUM>, as well as components external to the system <NUM>. In practice, the plurality of servers <NUM> may include additional components such as one or more electronic processors, memories, interfaces, displays, speakers, power supplies, and the like. For ease of explanation, these additional components are not illustrated here. The system <NUM> illustrated in <FIG> includes three servers. In practice, the system <NUM> may include fewer than three servers or more than three servers.

The system <NUM> illustrated in <FIG> also includes a receiver <NUM> (for example, an audio/video receiver). The receiver <NUM>, which will be described in more detail below, includes a downloader <NUM> and a controller <NUM>. In practice, the receiver <NUM> may include additional components such one or more displays, speakers, power supplies, memories, and the like. For ease of explanation, these additional components are not illustrated here.

The downloader <NUM> illustrated in <FIG> includes an input buffer <NUM> and is communicably coupled to the plurality of servers <NUM> via a plurality of communication links <NUM>. The plurality of communication links <NUM> include wired links, wireless links, or a combination thereof. As described above, each of the plurality of servers <NUM> store a different set of coded symbols <NUM> of a data file. To decode the data file, the downloader <NUM> is configured to send download requests to the plurality of servers <NUM>, and subsequently receive the coded symbols <NUM> stored in each of the plurality of servers <NUM>. The downloader <NUM> receives the coded symbols <NUM> from the plurality of servers <NUM> with the input buffer <NUM> via the plurality of communication links <NUM>. After receiving a sufficient quantity of coded symbols <NUM> to decode the data file, the downloader <NUM> is configured to send download termination requests to the plurality of servers <NUM> to terminate the data transfer therefrom.

The controller <NUM> is communicably coupled to the downloader <NUM> and is configured to, among other things, determine which data the downloader <NUM> should request from each of the plurality of servers <NUM>, as will be described in more detail below. <FIG> is a block diagram of one example of the controller <NUM> according to an implementation of the present disclosure. The controller <NUM> illustrated in <FIG> includes an electronic processor <NUM> (for example, one or more microprocessors, application-specific integrated circuits (ASICs), systems-on-a-chip (SoCs), or other electronic controllers), memory <NUM>, an input/output interface <NUM>, a user interface <NUM>, and a bus <NUM>. In practice, the controller <NUM> may include additional components such as communication circuitry, one or more sensors, one or more power supplies, and the like. For ease of explanation, these additional components are not illustrated here.

The bus <NUM> connects various components of the controller <NUM> including, for example, the memory <NUM> to the electronic processor <NUM>. The memory <NUM>, for example, includes read only memory (ROM), random access memory (RAM), an electrically erasable programmable read-only memory (EEPROM), other non-transitory computer-readable media, or a combination thereof. The electronic processor <NUM> is configured to retrieve program instructions and data from the memory <NUM> and execute, among other things, instructions to perform the methods described herein. In some implementations, the memory <NUM> is included in the electronic processor <NUM>.

The input/output interface <NUM> includes routines for transferring information between components within the controller <NUM> and other components of the system <NUM>, as well as components external to the system <NUM>. The input/output interface <NUM> is configured to transmit and receive signals via one or more wired couplings (e.g., wires, optical fiber, and the like), wirelessly, or a combination thereof. Signals may include, for example, download requests, termination requests, coded symbols, or a combination thereof.

The user interface <NUM> includes, for example, a computer having a display and input devices, a touch-screen display, a plurality of knobs, dials, switches, buttons, faders, and the like. In some implementations, the user interface <NUM> includes a touch-sensitive interface (e.g., a touch-screen display) that displays visual output generated by software applications executed by the electronic processor <NUM>. Visual output includes, for example, graphical indicators, lights, colors, text, images, graphical user interfaces (GUIs), combinations of the foregoing, and the like. The touch-sensitive interface also receives user input using detected physical contact (e.g., detected capacitance or resistance). In some implementations, the user interface <NUM> is separated from the controller <NUM>, the receiver <NUM>, or from the system <NUM>.

In some implementations, the downloader <NUM> downloads a data file progressively by sequentially sending one or more partial download requests to each of the plurality of servers <NUM>. The controller <NUM> determines when and how much data to request from each of the plurality of servers <NUM>. Once the file becomes decodable, the controller <NUM> instructs the downloader <NUM> to transmit download termination requests to each of the plurality of servers <NUM>. In some implementations, the partial download requests fall into two phases: an initial phase and a refill phase.

During the initial phase, one initial download request is made to each of the plurality of servers <NUM>. The total number of coded symbols K' requested across all of the plurality of servers <NUM> is less than K(<NUM> + p), where K is the quantity of useful coded symbols being requested to decode the file, and p ≥ <NUM> is the allowance on excess data. In some implantations, the value of K' may depend on the variation of each communication link's bandwidth, latency, or both. In general, the more stable the plurality of communication links <NUM>, the closer K' is to K(<NUM> + p).

During the refill phase, additional download requests (for example, subsequent download requests) are sent to some or all of the plurality of servers <NUM> to: (i) keep the respective communication link <NUM> between each server <NUM> and the downloader <NUM> fully utilized; and (ii) adjust the total quantity of data requested from the server <NUM> to minimize excess data.

<FIG> and <FIG> illustrate a flow diagram of an example of a method <NUM> for data traffic management in multi-source content delivery with progressive partial download requests according to the claimed invention. The steps of method <NUM> illustrated in <FIG> are one example of the initial phase described above. At block <NUM>, an initial load request K' is determined (e.g., by the controller <NUM>). According to the claimed invention, the initial load request K' is the total quantity of coded symbols <NUM> to be requested in the initial download requests. In some implementations, the initial request load K' is determined based on the stability of the communication links <NUM>. For example, the initial load request K' may be determined based on the normalized standard deviation of the bandwidths of the communication links <NUM>. The normalized bandwidth standard deviation is the ratio between the standard deviation and the mean of the bandwidth of a communication link according to prior information (e.g., observations). The normalized bandwidth standard deviations of all the communication links <NUM> are averaged to yield a variance factor v which is bounded by a non-negative fractional number c, such as <NUM>. The variance factor v is given by the following: <MAT> where N is the total quantity of communication links <NUM>, σi is an observed standard deviation of communication link i, and wi is the average bandwidth of communication link i. In some implementations, the bandwidth wi of communication link i is determined based on previously-observed performances of communication link i (e.g., by averaging previously-observed performances of communication link i).

The initial load request K' is given by the following: <MAT> where v is the variance factor described above, K is the number of useful symbols requested to decode the data file, and p is an allowance of excess data. In some implementations, the allowance of excess data p is determined based on system-level requirements for the system <NUM>. In some implementations, the allowance of excess data p is determined based at least in part on the specific components of the system <NUM>.

At block <NUM>, an initial download completion time T is determined (e.g., by the controller <NUM>). In some implementations, the controller <NUM> is configured to determine the initial download completion time T based the total quantity of data provided by each of the plurality of servers <NUM> when a total of K' coded symbols <NUM> are received and each of the plurality of communication links <NUM> are fully utilized. For example, the initial download completion time T may be determined by solving the following equation for T: <MAT> where N is the total quantity of communication links <NUM>, di is the round trip time of communication link i, wi is the average bandwidth of communication link i, s is the size of a coded symbol, and K' is the quantity of coded symbols <NUM> still being requested to decode the data file (i.e., the initial load request).

At block <NUM>, initial server loads Li for each of the plurality of servers <NUM> are determined (e.g., by the controller <NUM>). According to the claimed invention, the controller <NUM> is configured to determine the initial server load Li of server i based in part on the initial download completion time T. For example, when the initial download completion time T is greater than the round trip time di of communication link i, the initial server load Li of server i may be given by the following: <MAT> where di is the round trip time of communication link i, wi is the average bandwidth of communication link i, and p is an allowance of excess data.

In situations in which server i is allocated with zero load (e.g., due to a high round trip time, small bandwidth, or both), the controller <NUM> is configured to allocate an initial server load Li to server i that is smaller than the initial load request K'. For example, when the initial download completion time T is less than or equal to the round trip time di of communication link i, the initial server load Li of server i may be given by the following: <MAT> where c is a non-negative fractional number (e.g., <NUM>), K is the number of useful symbols being requested to decode the data file, p is an allowance of excess data, and N is the total quantity of communication links <NUM>.

At block <NUM>, quantities ni of coded symbols <NUM> to initially request from each of the plurality of servers <NUM> are determined (e.g., by the controller <NUM>). In some implementations, the controller <NUM> is configured to determine the quantities ni of coded symbols <NUM> by rounding the initial server load Li of each of the plurality of servers <NUM> by the size s of a coded symbol <NUM>. For example, the quantity ni of coded symbols <NUM> to request from server i may be given by the following: <MAT> where Li is initial server load of server i, and s is the size of a symbol. As used herein, ceil(x) is a ceiling function which returns the smallest integer that is greater than x. At block <NUM>, initial download requests are sent to each of the plurality of servers <NUM> (e.g., by the downloader <NUM>). For example, the downloader <NUM> sends signals including the initial download requests over each of the plurality of communication links <NUM> to each of the plurality of servers <NUM>. In some implementations, each of the initial downloads requests includes, among other things, an identifier of the data file to download and a quantity ni of coded symbols <NUM> to request from a server <NUM>. For example, the downloader <NUM> sends an initial download request to server i, via communication link i, that includes an identifier of the data file to download and a quantity ni of coded symbols <NUM> to request from server i.

In some implementations, the initial load request K' is unevenly allocated to the plurality of servers <NUM>. For example, servers <NUM> with higher performance are allocated more of the initial load request K' than servers <NUM> with lower performance. As described above in block <NUM> of method <NUM>, the initial load request K' is allocated based on the round trip times and the bandwidths of each of the plurality of communication links <NUM>. In some implementations, the initial load request K' is evenly allocated across all of the plurality of servers <NUM>.

Turning to <FIG>, the steps of method <NUM> illustrated in <FIG> are one example of the refill phase described above. At block <NUM>, a coded symbol <NUM> is received from one of the plurality of servers <NUM> over one of the plurality of communication links <NUM> (e.g., by the downloader <NUM>). For example, the downloader <NUM> receives a coded data packet containing one or more coded symbols <NUM> from one of the plurality of servers <NUM>. At block <NUM>, updated information about the quality of the plurality of communication links <NUM> is determined (e.g., by the controller <NUM>). In some implementations, the controller <NUM> determines updated bandwidths and instantaneous latencies τi for each of the plurality of communication links <NUM>. For example, the controller <NUM> determines an updated bandwidth wi of communication link i based on download speeds measured during receipt of the most recently downloaded coded data packet. Further, the controller <NUM> determines an instantaneous latency τi of communication link i based on whether or not the downloader <NUM> has received any data over communication link i. For example, the controller <NUM> determines an instantaneous latency τi of zero for communication link i when the downloader <NUM> has received any data over communication link i. If the downloader <NUM> has not received any data over communication link i, the round trip time di of communication link i is higher than the time t that has elapsed since the initial download requests were sent and the controller <NUM> determines the instantaneous latency τi of communication link i as the difference between di and t.

At block <NUM>, an updated download completion time T' is determined (e.g., by the controller <NUM>). In some implementations, the controller <NUM> is configured to determine the updated download completion time T' based on the updated information about the quality of the plurality of communication links <NUM> and the total quantity K" of coded symbols <NUM> still being requested to decode the data file. For example, the updated download completion time T' may be determined by solving the following equation for T': <MAT> where N is the total quantity of communication links <NUM>, τi is the instantaneous latency of communication link i, wi is the updated bandwidth of communication link i, s is the size of a symbol, and K" is the quantity of coded symbols <NUM> still being requested to decode the data file.

At block <NUM>, updated server loads Li of each of the plurality of servers <NUM> are determined (e.g., by the controller <NUM>). In some implementations, the controller <NUM> is configured to determine an updated server load Li of server i based on the updated download completion time T' and the updated bandwidth wi of communication link i. For example, the updated server load Li of server i is given by the following: <MAT> where T' is the updated download completion time and wi is the updated bandwidth of communication link i.

In some implementations, a subsequent download request (also known as a refill request) is sent to a server <NUM> only when the updated server load of the server <NUM> is higher than its current load that has not been received. Thus, at block <NUM>, load differences δi of each of the plurality of servers <NUM> are determined (e.g., by the controller <NUM>). For example, the load difference δi of server i is the difference between the updated server load Li of server i and the current undelivered load Li' of server i.

At block <NUM>, the controller <NUM> determines whether any of the plurality of servers <NUM> are under-loaded. For example, the controller <NUM> determines that server i is under-loaded when the load difference δi of server i is greater than zero. Further, the controller <NUM> determines that server i has enough load when the load difference δi of server i is less than or equal to zero. When none of the plurality of servers <NUM> are under-loaded, no subsequent download requests are sent to the plurality of server <NUM> and the method <NUM> returns to block <NUM> to receive additional coded symbols <NUM> from the plurality of servers <NUM>. Alternatively, when any of the plurality of servers <NUM> are under-loaded, updated quantities ni of coded symbols <NUM> to request from each of the under-loaded servers are determined at block <NUM> (e.g., by the controller <NUM>). For example, the updated quantity ni of coded symbols <NUM> to request from server i may be given by the following: <MAT> where δi is load difference of server i, wi is the updated bandwidth of communication link i, di is the round trip time of communication link i, and s is the size of a symbol.

At block <NUM>, subsequent download requests are sent to the under-loaded servers <NUM> (e.g., by the downloader <NUM>). In some implementations, each of the subsequent downloads requests includes, among other things, an updated quantity ni of coded symbols <NUM> to request from an under-loaded server <NUM>. For example, the downloader <NUM> sends a subsequent download request to server i, via communication link i, that includes an updated quantity ni of coded symbols <NUM> to request from server i. In some implementations, after sending the subsequent download requests, the method <NUM> returns to block <NUM> to receive additional coded symbols <NUM> from the plurality of servers <NUM>.

In some implementations, the downloader <NUM> is configured to send download termination requests to each of the plurality of servers <NUM> at specific times so that each of the plurality of servers <NUM> receive a download termination request immediately after that server <NUM> loads the last useful symbol to its output buffer <NUM>. Each of the plurality of servers <NUM> receives and executes the download termination request immediately after the server <NUM> has loaded the last useful symbol to its output buffer <NUM>. In this manner, the quantity of excess data sent by each of the plurality of servers <NUM> is minimized because each of the plurality of servers <NUM> sends few or no excess symbols to the downloader <NUM>.

<FIG> illustrates a flow diagram of an example of a method <NUM> for data traffic management in multi-source content delivery with soft download termination requests according to an implementation of the present disclosure. At block <NUM>, coded symbols are requested from each of the plurality of servers <NUM> (e.g., by the downloader <NUM>). In some implementations, the coded symbols are requested from the plurality of servers <NUM> using any portion (or any combination of portions) of the method <NUM> described above. At block <NUM>, a coded symbol <NUM> is received (e.g., by the downloader <NUM>) from one of the plurality of servers <NUM> over one of the plurality of communication links <NUM>. For example, the downloader <NUM> receives a coded data packet containing one or more coded symbols <NUM> from one of the plurality of servers <NUM>. At block <NUM>, the controller <NUM> determines whether the download is almost complete. In some implementations, the controller <NUM> determines that the download is almost complete when the downloader <NUM> has received a majority of the coded symbols <NUM> from the plurality of servers <NUM>. For example, the controller <NUM> determines that the download is almost complete when the downloader <NUM> has received a quantity of coded symbols <NUM> that is greater than a final phase threshold Th'. The final phase threshold Th' may be given by the following: <MAT> where s is the size of a coded symbol, K is the quantity of useful coded symbols being requested to decode the data file, N is the total quantity of communication links <NUM>, wi is the average bandwidth of communication link i, and di is the round trip time of communication link i. When the download is not almost complete, the method <NUM> returns to block <NUM> to receive additional coded symbols <NUM> from the plurality of servers <NUM>.

Alternatively, when download is almost complete, a download completion time T is determined at block <NUM> (e.g., by the controller <NUM>). For example, the download completion time T may be determined by solving the following equation for T: <MAT> where N is the total quantity of communication links <NUM>, di is the round trip time of communication link i, wi is the average bandwidth of communication link i, s is the size of a coded symbol, and K is the quantity of useful symbols being requested to decode the data file.

At block <NUM>, server completion times Ui when each of the plurality of servers <NUM> load the last useful coded symbol <NUM> to their output buffer <NUM> are determined (e.g., by the controller <NUM>). In some implementations, the controller <NUM> determines the server completion times Ui based on information about the quality of the plurality of communication links <NUM> and the sizes of the servers' output buffers <NUM>. For example, the server completion time Ui of server i is given by the following: <MAT> where di is the round trip time of communication link i, T is the download completion time, bi is the size of the output buffer <NUM> of server i, and wi is the bandwidth of communication link i.

At block <NUM>, download termination requests are sent to the plurality of servers <NUM> (e.g., by the downloader <NUM>). Each of the download termination requests is sent to a specific server at a set period of time prior to the specific server's server completion time. For example, a download termination request is sent to server i at time Ui - (di/<NUM>). In some implementations, a specific subset of the plurality of servers <NUM> are not sent download termination requests until after the data file is downloadable.

In some implementations, while downloading a data file, the controller <NUM> adapts the streaming rate of each of the plurality of servers <NUM> to: (i) maintain a maximum streaming rate until the data file is almost decodable, and (ii) use a reduced streaming rate to download the last few coded symbols. For example, as illustrated in <FIG>, the server streaming rate is set to its maximum rate r<NUM> until K - ε coded symbols are downloaded in total, where K is the quantity of useful coded symbols being requested to decode the data file and ε is a small positive integer. The server streaming rate illustrated in <FIG> is reduced to a small rate r<NUM> until the data file is decodable. After this, the download is terminated.

In some implementations, the controller <NUM> adapts the streaming rates of the plurality of servers <NUM> by adapting the sizes of the output buffers <NUM> of the plurality of servers <NUM>. For example, the controller <NUM> adapts the sizes of the output buffers <NUM> of the plurality of servers <NUM> through HTTP/<NUM> session window size adaption. In general, increasing the size of the output buffer <NUM> of a server <NUM> increases the streaming rate and the bandwidth of the corresponding communication link <NUM>.

<FIG> illustrates a flow diagram of an example of a method <NUM> for data traffic management in multi-source content delivery with download rate adaption according to an implementation of the present disclosure. At block <NUM>, coded symbols are requested from each of the plurality of servers <NUM> (e.g., by the downloader <NUM>). In some implementations, the coded symbols are requested from the plurality of servers <NUM> using any portion (or any combination of portions) of the method <NUM> described above.

At block <NUM>, the output buffers <NUM> of the plurality of servers <NUM> are set to large values (an example of a "first value"). For example, a large size value L_Bufi for the output buffer <NUM> of server i is given by the following: <MAT> where wi is the bandwidth of communication link i, and di is the round trip time of communication link i, and pi is the smallest positive number that: (i) allows a streaming rate of server i to reach the bandwidth wi and (ii) is a multiple of the size s of the coded symbols <NUM>.

At block <NUM>, coded symbols <NUM> are received (e.g., by the downloader <NUM>) from the plurality of servers <NUM> over the plurality of communication links <NUM>. For example, the downloader <NUM> receives coded data packets containing coded symbols <NUM> from the plurality of servers <NUM>. At block <NUM>, the controller <NUM> determines whether the download is almost complete. In some implementations, the controller <NUM> determines that the download is almost complete when the downloader <NUM> has received a majority of the coded symbols <NUM> from the plurality of servers <NUM>. For example, the controller <NUM> determines that the download is almost complete when the downloader <NUM> has received a total of K - ε coded symbols <NUM> from the plurality of servers <NUM> (an example of a "majority threshold"), where K is the quantity of useful coded symbols being requested to decode the data file and ε is a small positive integer. When the download is not almost complete, the method <NUM> returns to block <NUM> to receive additional coded symbols from the plurality of servers <NUM>.

Alternatively, when download is almost complete, the output buffers <NUM> of the plurality of servers <NUM> are set to small values (an example of a "second value"), at block <NUM>. For example, a small size value S_Bufi for the output buffer <NUM> of server i is given by the following: <MAT> where wi is the bandwidth of communication link i, di is the round trip time of communication link i, and qi is positive number that: (i) is smaller than pi, and (ii) is a multiple of the size s of the coded symbols <NUM>.

At block <NUM>, additional coded symbols <NUM> are received (e.g., by the downloader <NUM>) from the plurality of servers <NUM> over the plurality of communication links <NUM>. At block <NUM>, the controller <NUM> determines whether the data file is decodable. In some implementations, the data file is decodable when the downloader <NUM> has received a sufficient quantity of the coded symbols <NUM> being requested to decode the data file. For example, the controller <NUM> determines that the data file is decodable when the downloader <NUM> has received a total of K + δ coded symbols <NUM> from the plurality of servers <NUM>, where K is the quantity of useful coded symbols being requested to decode the data file and δ is a small positive integer. When the data file is not decodable, the method <NUM> returns to block <NUM> to receive additional coded symbols from the plurality of servers <NUM>. Alternatively, when the data file is decodable, download termination requests are sent to the plurality of servers <NUM> at block <NUM> (e.g., by the downloader <NUM>).

<FIG> illustrates a flow diagram of an example of a method <NUM> for data traffic management in multi-source content delivery according to an implementation of the present disclosure. At block <NUM>, initial download requests for the plurality of servers <NUM> are determined (e.g., by the controller <NUM>). In some implementations, each of the initial download requests includes a request for a specific server to send a specific quantity (an example of a "first quantity") of data to the downloader <NUM>. For example, as described above in relation to block <NUM> in <FIG>, each of the initial download requests may include a request for a specific server to send a specific quantity of the coded symbols <NUM> to the downloader <NUM>. In some implementations, each of the initial download requests includes a request for a specific server to set the size of its output buffer <NUM> to a large value, for example, as described above in relation to block <NUM> in <FIG>.

The initial download requests are determined based on predetermined information about the quality of the plurality of communication links <NUM> (e.g., bandwidth, latency, and packet loss rate). In some implementations, the initial download requests are determined based on server information (e.g., server location, cache status, and output buffer size). In some implementations, the initial download requests are determined based on information about the data file being downloaded (e.g., data file size and data file type). In some implementations, the initial download requests are determined based on the download performance of previously-downloaded data files. In some implementations, the initial download requests are determined based on the system budget (e.g., maximum acceptable amount of excess data).

At block <NUM>, the initial download requests are sent to the plurality of servers <NUM> (e.g., by the downloader <NUM>). For example, the downloader <NUM> sends signals including the initial download requests over each of the plurality of communication links <NUM> to each of the plurality of servers <NUM>. At block <NUM>, the receiver <NUM> receives data from the plurality of servers <NUM> (e.g., with the downloader <NUM>). For example, the downloader <NUM> may receive coded symbols <NUM> from the plurality of servers <NUM>.

At block <NUM>, updated information about the quality of the plurality of communication links <NUM> is determined (e.g., by the controller <NUM>). In some implementations, the controller <NUM> determines updated bandwidths and instantaneous latencies for each of the plurality of communication links <NUM>, for example, as described above in relation to block <NUM> in <FIG>.

At block <NUM>, subsequent download requests are determined (e.g., by the controller <NUM>). In some implementations, each of the subsequent download requests includes a request for a specific server to send a specific quantity (an example of a "second quantity") of the data to the downloader <NUM>. For example, as described above in relation to block <NUM> in <FIG>, each of the subsequent download requests may include a request for a specific server to send a specific quantity of the coded symbols <NUM> to the downloader <NUM>. In some implementations, each of the subsequent download requests includes a download termination request for a specific server to stop sending data to the downloader <NUM>. For example, as described above in relation to block <NUM> in <FIG>, each of the subsequent download requests may include a request for a specific server to stop sending coded symbols <NUM> to the downloader <NUM>. In some implementations, each of the subsequent download requests includes a request for a specific server to set the size of its output buffer <NUM> to a small value, for example, as described above in relation to block <NUM> in <FIG>.

The subsequent download requests are determined based on updated information about the quality of the plurality of communication links <NUM> (e.g., bandwidth, latency, and packet loss rate). In some implementations, the subsequent download requests are determined based on server information (e.g., server location, cache status, and output buffer size). In some implementations, the subsequent download requests are determined based on information about the data file being downloaded (e.g., data file size and data file type). In some implementations, the subsequent download requests are determined based on the download performance of previously-downloaded data files and the current data file being downloaded. In some implementations, the subsequent download requests are determined based on the system budget (e.g., maximum acceptable amount of excess data).

At block <NUM>, the subsequent download requests are sent to the plurality of servers <NUM> (e.g., by the downloader <NUM>). For example, the downloader <NUM> sends signals including the subsequent download requests over each of the plurality of communication links <NUM> to each of the plurality of servers <NUM>.

In some implementations, machine-learning techniques are used to train and deploy the download process used by the controller <NUM> to make control decisions. Examples of control decisions include, but are not limited to: (i) which one of the aforementioned data traffic management processes should be used; (ii) what are the parameters for the chosen process; and (iii) a decision beyond the scope of the aforementioned processes. In some implementations, the training initialization defines the following four settings: (i) an input space; (ii) a learning process and model; (iii) an output space; and (iv) a reward/penalty function. With input space, each input is a set of system information, including (but not limited to) server information, network information, device information, download progress, and the like. The information is collected globally, regionally, locally, and/or on a per-user basis, and then the training data set and testing data set are created accordingly. One example of a learning algorithm and model is batched stochastic gradient descent using a convolutional neural network. The output space includes, for example, which servers <NUM> make download requests, how much data to request, when to make download requests, and when to terminate downloads. The reward/penalty function generates a higher reward for a higher ratio between throughput and excess data. The training process is iterative and each iteration may, for example, include: (i) a batch of training inputs being given to the model; (ii) for each sample input, the model determining an output (i.e., a control decision) based on a learning process; (iii) determining excess data and throughput performance of each output; (iv) determining a total reward/penalty; and (v) adjusting the model based on feedback from the reward/penalty. In some implementations, the performance of the model is tracked using a test data set, so that the training will stop when the model's performance become stable (i.e., the model is converged).

The training output is the model, which determines control decisions when provided with system information. The model can be either pre-trained using universal data samples and then distributed to the controller <NUM>, be trained at the controller <NUM> using real-time data of the receiver <NUM>, or be pre-trained and then evolved at the controller <NUM>. <FIG> illustrates a flow diagram of an example of a training process <NUM> according to an implementation of the present disclosure. At block <NUM>, data is collected globally, regionally, locally, and on a per-user basis. At block <NUM>, a training data set and testing data set are determined based on the collected data. At block <NUM>, a random subset of training inputs is selected. At block <NUM>, control decisions are determined using a current neural network. At block <NUM>, excess data and system performance of control decisions are determined. At block <NUM>, rewards and penalties are determined. At block <NUM>, the neural network is updated using gradient descent according the rewards and penalties. At block <NUM> the neural network's performance is tested using the test data set. At block <NUM>, it is determined if the neural network has converged. When the neural network has not converged, the training process <NUM> returns to block <NUM> to select a new random subset of training input. Alternatively, when the neural network has converged, the neural network is sent to the controller <NUM>, at block <NUM>.

In some implementations, a reinforcement learning model is utilized. <FIG> illustrates an example of training process <NUM> with reinforcement learning. The training process <NUM> illustrated in <FIG> includes a broker <NUM>, an environment <NUM>, and a reward calculator <NUM>. The broker <NUM> may be defined as the download process used by the controller <NUM>. The environment <NUM> may be defined as one or more uniquely identified servers <NUM>, output buffers <NUM>, input buffers <NUM>, and communication links <NUM>. The reward calculator <NUM> determines rewards based on throughput, excess data, and the like. The reinforcement learning model defines the use of the broker <NUM> interacting with the environment <NUM>. At each time step during training, the broker <NUM> observes an updated state of the environment <NUM> (e.g., a download completion time) then determines an action to perform (e.g., send download termination request to a specific server at a specific time). Upon the action being applied, the environment <NUM> transitions to another updated state and the broker <NUM> receives a reward. The broker <NUM> uses the reward information to improve its decisions with a goal of maximizing the expected cumulative discounted reward.

The training and processes of the controller <NUM> may also use global, regional, local, per-user, and per-device environment data. Environment data can be sourced from third party platforms and from the system's own data collection processes in real-time or non-real-time. This capability information that a single implementation of an optimized controller utilized globally, may be different at a regional, a local, a per-user, or a per-device basis because both server characteristics and network characteristics can vary widely within and across geographic locations. For example, the controller <NUM> may be configured to different solutions for clients running in San Francisco vs. clients running in Mumbai. Moreover, the model and the controller <NUM> can additionally factor temporal variances and access network heterogeneity during training and operation.

According to one implementation, the techniques described herein are implemented by one or more special-purpose computing devices. The techniques are not limited to any specific combination of hardware circuitry and software, nor to any particular source for the instructions executed by a computing device or data processing system.

The term "storage media" as used herein refers to any media that store data and/or instructions that cause a machine to operation in a specific fashion. It is non-transitory. Non-volatile media includes, for example, optical or magnetic disks. Volatile media includes dynamic memory.

For example, transmission media includes coaxial cables, copper wire and fiber optics. Transmission media can also take the form of acoustic or light waves, such as those generated during radiowave and infra-red data communications.

In the foregoing specification, possible implementations of the present disclosure have been described with reference to numerous specific details that may vary from implementation to implementation. Any definitions expressly set forth herein for terms contained in the claims shall govern the meaning of such terms as used in the claims. Hence, no limitation, element, property, feature, advantage or attribute that is not expressly recited in a claim should limit the scope of such claim in any way. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. It should be further understood, for clarity, that exempli gratia (e.g.) means "for the sake of example" (not exhaustive), which differs from id est (i.e.) or "that is.

Claim 1:
A method (<NUM>) for downloading by a downloader a data file from a plurality of servers coupled to the downloader via a plurality of communication links (<NUM>), comprising:
determining an initial load request (<NUM>), wherein the initial load request includes a total quantity of coded symbols (<NUM>) corresponding to the data file to be requested in an initial download request;
determining an initial download completion time (<NUM>), wherein the initial download completion time is estimated based on the initial load request and predetermined information about a quality of the plurality of communication links (<NUM>);
determining initial server loads for respective servers of the plurality of servers (<NUM>), wherein the initial server loads are a function of the product of an average bandwidth of the respective communication link (<NUM>) and the difference between the initial download completion time and a round trip time of the communication link;
determining quantities of coded symbols (<NUM>) to request from respective servers of the plurality of servers based on the initial server loads (<NUM>); and
sending initial download requests for the quantities of coded symbols (<NUM>) to the respective servers of the plurality of servers (<NUM>).