Data retrieval based on bandwidth cost and delay

• US 9,948,708 B2
• Filed: 06/01/2010
• Issued: 04/17/2018
• Est. Priority Date: 06/01/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Wormley, Nicholas A.
• Primary Examiner(s): Vu, Viet D
• Application Number:
  US12/791,555
• Publication Number:
  US 20100306373A1
• Time in Patent Office: 2,877 Days
• Field of Search: 709224
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer

Abstract

The invention provides for a download agent executing on a computing device. The download agent determines the status of each of the source servers, and downloads from source servers that are in the available state. Additionally the download agent tracks characteristics of the source servers. The download agent determines the required bandwidth of portions of the media content stored on the source servers. Based on the characteristics of the source servers and the required bandwidth of the portions of the media content, the download agent determines how much media content should be downloaded from which source servers and at what time.

Claims

1. A method comprising:

determining, by one or more processors of a client device, states of a plurality of servers associated with a media content provider, wherein the states of the plurality of the servers indicate availability of the plurality of servers to deliver a media asset to the client device;

determining, by the one or more processors of the client device, a subset of the plurality of servers available to deliver the media asset to the client device in view of the determined states;

determining, by the one or more processors of the client device, characteristics associated with the subset of the plurality of servers, wherein the characteristics comprise a cost to transmit the media asset to the client device from the subset of the plurality of servers through a plurality of service providers (SP) to the client device and throughput rates of the subset of the plurality of servers, wherein the cost is indicative of a fee charged to the media content provider by different SPs of the plurality of SPs based on bandwidth utilization by the subset of the plurality of servers, wherein the subset of the plurality of servers use the different SPs of the plurality of SPs to transmit the media asset;

estimating, by the one or more processors of the client device, a first bit rate at which the client device is to receive a first portion of the media asset, wherein the first bit rate is to provide for uninterrupted playback of the media asset, and wherein the first portion corresponds to data for a first playback time period of the media asset, wherein estimating the first bit rate comprises;

receiving metadata associated with the media asset, wherein the metadata comprises a starting timestamp, an ending timestamp, a starting byte offset, and an ending byte offset associated with the first portion of the media asset, and

computing the first bit rate of the first portion based on the metadata; and

selecting, by the client device and based on the determined characteristics and the first bit rate, one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device.

2. The method of claim 1, further comprising:

estimating a second bit rate associated at which the client is to receive a second portion of the media asset, wherein the second portion corresponds to data for a second playback time period of the media asset that temporally follows the first playback time period of the first portion of the media asset; and

selecting, based on the determined characteristics and the second bit rate, one or more servers from the subset of the plurality of servers to deliver the second portion of the media asset to the client device.

3. The method of claim 1, further comprising:

receiving the first portion of the media asset;

serializing the first portion of the media asset into a stream; and

verifying the stream to determine bytes in the stream are uncorrupted.

4. The method of claim 1, further comprising:

monitoring the states of the plurality of servers; and

maintaining state data indicative of the states of the plurality of servers, wherein the states comprise an untested state, a test pending state, an untested retry state, an available state, an unavailable retry state, an available busy state, or an unavailable state.

5. The method of claim 4, wherein determining the subset of the plurality of servers available to deliver the media asset the client device in view of the determined states comprises selecting the subset of the plurality of servers having the available state.

6. The method of claim 1, wherein the characteristics comprise one or more of the throughput rates of the subset of the plurality of servers, peak download times of the subset of the plurality servers, geographic locations of the subset of the plurality of servers, a privilege level of the client device, a client-side autonomous system (AS) number, or the cost to transmit the media asset to the client device from the subset of the plurality of servers.

7. The method of claim 1, further comprising

receiving the characteristics from the plurality of servers in response to a query.

8. The method of claim 1, wherein the first playback time period is determined based on one or more key frames of the media asset.

9. The method of claim 1, wherein estimating the first bit rate at which the client device is to receive the first portion of the media asset is based on previously downloaded frames of the media asset and comprises:

determining an average bit rate for the previously downloaded frames; and

increasing or decreasing the average bit rate based on whether bandwidth for the previously downloaded frames respectively increased or decreased over subsequent frames of the previously downloaded frames.

10. The method of claim 1, wherein selecting the one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device further comprises:

selecting a first server from the subset of the plurality of servers to deliver a first sub-portion of the first portion of the media asset to the client device; and

selecting a second server from the subset of the plurality of servers to deliver a second sub-potion of the first portion of the media asset to the client device, wherein selecting the first server and the second server is based on the determined characteristics and the first bit rate.

11. The method of claim 1, wherein estimating the first bit rate at which the client device is to receive the first portion of the media asset further comprises:

downloading header information for one or more encoded frames prior to the one or more encoded frames being received by the client device, wherein the one or more encode frames represent the first portion of the media asset, and wherein the header information indicates one or more timestamps and one or more corresponding byte offsets for the one or more encoded frames; and

computing the first bit rate of the first portion of the media asset based on starting and ending byte offsets of the one or more encoded frames and starting and ending timestamps of the one or more encoded frames.

12. The method of claim 2, wherein the first portion of the media asset and the second portion of the media asset are encoded at different bit rates.

13. A device comprising:

a memory; and

one or more processors of a client device, coupled to the memory, to;

determine states of a plurality of servers, wherein the states of the plurality of the servers associated with a media content provider indicate availability of the plurality of servers to deliver a media asset to the client device;

determine a subset of the plurality of servers available to deliver the media asset the client device in view of the determined states;

determine characteristics associated with the subset of the plurality of servers, wherein the characteristics comprise a cost to transmit the media asset to the client device from the subset of the plurality of servers through a plurality of service providers (SP) to the client device and a throughput rate of the subset of the plurality of servers, wherein the cost is indicative of a fee charged to the media content provider by different SPs of the plurality of SPs based on bandwidth utilization by the subset of the plurality of servers, wherein the subset of the plurality of servers use the different SPs of the plurality of SPs to transmit the media asset;

estimate a first bit rate at which the client device is to receive a first portion of the media asset, wherein the first bit rate is to provide for uninterrupted playback of the media asset, and wherein the first portion corresponds to data for a first playback time period of the media asset, wherein to estimate the first bit rate, the one or more processors to;

receive metadata associated with the media asset, wherein the metadata comprises a starting timestamp, an ending timestamp, a starting byte offset, and an ending byte offset associated with the first portion of the media asset, and

compute the first bit rate of the first portion based on the metadata; and

select based on the determined characteristics and the first bit rate, one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device.

14. The device of claim 13, wherein the one or more processors further to:

estimate a second bit rate associated at which the client is to receive a second portion of the media asset, wherein the second portion corresponds to data for a second playback time period of the media asset that temporally follows the first playback time period of the first portion of the media asset; and

select, based on the determined characteristics and the second bit rate, one or more servers from the subset of the plurality of servers to deliver the second portion of the media asset to the client device.

15. The device of claim 13, wherein to select the one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device, the one or more processors further to:

selecting a first server from the subset of the plurality of servers to deliver a first sub-portion of the first portion of the media asset to the client device; and

selecting a second server from the subset of the plurality of servers to deliver a second sub-potion of the first portion of the media asset to the client device, wherein selecting the first server and the second server is based on the determined characteristics and the first bit rate.

16. The device of claim 13, the one or more processors further to:

receive the first portion of the media asset;

serialize the first portion of the media asset into a stream; and

verify the stream to determine bytes in the stream are uncorrupted.

17. The device of claim 13, wherein the one or more processors is further to:

monitor the states of the plurality of servers; and

maintain state data indicative of the states of the plurality of servers, wherein the states comprise an untested state, a test pending state, an untested retry state, an available state, an unavailable retry state, an available busy state, or an unavailable state.

18. The device of claim 17, wherein to determine the subset of the plurality of servers available to deliver the media asset the client device in view of the determined states, the one or more processors further to select the subset of the plurality of servers having the available state.

19. The device of claim 13, wherein the characteristics comprise one or more of the throughput rates of the subset of the plurality of servers, peak download times of the subset of the plurality of servers, geographic locations of the subset of the plurality of servers, a privilege level of the client device, a client-side autonomous system (AS) number, or the cost to transmit the media asset to the client device.

20. The device of claim 13, the one or more processors further to:

receive the characteristics from the plurality of servers in response to a query.

21. The device of claim 13, wherein the first playback time period is determined based on one or more key frames of the media asset.

22. The device of claim 13, wherein to estimate the first bit rate at which the client device is to receive the first portion of the media asset is based on previously downloaded frames of the media asset, the one or more processors to:

determine an average bit rate for the previously downloaded frames; and

increase or decrease the average bit rate based on whether bandwidth for the previously downloaded frames respectively increased or decreased over subsequent frames of the previously downloaded frames.

23. The device of claim 13, wherein to estimate the first bit rate at which the client device is to receive the first portion of the media asset is based on previously downloaded frames of the media asset, the one or more processors to:

downloading header information from one or more encoded frames prior to the one or more encoded frames being received by the client device, wherein the one or more encoded frames represent the first portion, and wherein the header information indicates one or more timestamps and one or more corresponding byte offsets of the one or more encoded frames; and

computing the first bit rate based on starting and ending byte offsets of the one or more encoded frames and starting and ending time stamps of the one or more encoded frames.

24. The device of claim 14, wherein first portion and the second portion of the media asset are encoded at variable bit rates.

25. The device of claim 13, wherein the client device comprises at least one of a personal computer, a laptop computer, a mobile telephone, a personal media player, a device integrated into a vehicle, a network telephone, a network television, a television set-top box, or a network appliance.

26. A non-transitory computer readable storage medium having instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

determining, by the one or more processors of a client device, states of a plurality of servers associated with a media content provider, wherein the states of the plurality of the servers indicate availability of the plurality of servers to deliver a media asset to the client device;

determining, by the one or more processors of the client device, a subset of the plurality of servers available to deliver the media asset the client device in view of the determined states;

determining, by the one or more processors of the client device, characteristics associated with the subset of the plurality of servers, wherein the characteristics comprise a cost to transmit the media asset to the client device from the subset of the plurality of servers through a plurality of service providers (SP) to the client device and a throughput rate of the subset of the plurality of servers, wherein the cost is indicative of a fee charged to the media content provider by different SPs of the plurality of SPs based on bandwidth utilization by the subset of the plurality of servers, wherein the subset of the plurality of servers use the different SPs of the plurality of SPs to transmit the media asset;

estimating, by the one or more processors of the client device, a first bit rate at which the client device is to receive a first portion of the media asset, wherein the first bit rate is to provide for uninterrupted playback of the media asset, and wherein the first portion corresponds to data for a first playback time period of the media asset, wherein estimating the first bit rate comprises;

receiving metadata associated with the media asset, wherein the metadata comprises a starting timestamp, an ending timestamp, a starting byte offset, and an ending byte offset associated with the first portion of the media asset, and

computing the first bit rate of the first portion based on the metadata; and

selecting, by the client device and based on the determined characteristics and the first bit rate, one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device.

27. The non-transitory computer readable storage medium of claim 26, the operations further comprising:

estimating a second bit rate associated at which the client is to receive a second portion of the media asset, wherein the second portion corresponds to data for a second playback time period of the media asset that temporally follows the first playback time period of the first portion of the media asset; and

selecting, based on the determined characteristics and the second bit rate, one or more servers from the subset of the plurality of servers to deliver the second portion of the media asset to the client device.

28. The non-transitory computer readable storage medium of claim 26, wherein estimating the first bit rate at which the client device is to receive the first portion of the media asset is based on previously downloaded frames of the media asset, the operations further comprising:

determining an average bit rate for the previously downloaded frames; and

increasing or decreasing the average bit rate based on whether bandwidth for the previously downloaded frames respectively increased or decreased over subsequent frames of the previously downloaded frames.

29. The non-transitory computer readable storage medium of claim 26, wherein selecting the one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device, the operations further comprising:

selecting a first server from the subset of the plurality of servers to deliver a first sub-portion of the first portion of the media asset to the client device; and

selecting a second server from the subset of the plurality of servers to deliver a second sub-potion of the first portion of the media asset to the client device, wherein selecting the first server and the second server is based on the determined characteristics and the first bit rate.

30. A method comprising:

determining, by one or more processors of a client device, states of a plurality of servers associated with a media content provider, wherein the states of the plurality of the servers indicate availability of the plurality of servers to deliver a media asset to the client device;

determining, by the one or more processors of the client device, a subset of the plurality of servers available to deliver the media asset to the client device in view of the determined states;

determining, by the one or more processors of the client device, characteristics associated with the subset of the plurality of servers, wherein the characteristics comprise a cost to transmit the media asset to the client device from the subset of the plurality of servers through a plurality of service providers (SP) to the client device and throughput rates of the subset of the plurality of servers, wherein the cost is indicative of a fee charged to the media content provider by different SPs of the plurality of SPs based on bandwidth utilization by the subset of the plurality of servers, wherein the subset of the plurality of servers use the different SPs of the plurality of SPs to transmit the media asset;

estimating, by the one or more processors of the client device, a first bit rate at which the client device is to receive a first portion of the media asset, wherein the first bit rate is to provide for uninterrupted playback of the media asset, and wherein the first portion corresponds to data for a first playback time period of the media asset, wherein estimating the first bit rate comprises;

downloading header information for encoded frames of the first portion of the media asset prior to the encoded frames being received by the client device, wherein the header information indicates a starting timestamp, an ending timestamp, a starting byte offset, and an ending byte offset associated with the encoded frames, and

computing the first bit rate of the first portion of the media asset based on the header information; and

selecting, by the client device and based on the determined characteristics and the first bit rate, one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device.

31. The method of claim 30, further comprising:

estimating a second bit rate associated at which the client is to receive a second portion of the media asset, wherein the second portion corresponds to data for a second playback time period of the media asset that temporally follows the first playback time period of the first portion of the media asset; and

selecting, based on the determined characteristics and the second bit rate, one or more servers from the subset of the plurality of servers to deliver the second portion of the media asset to the client device.

32. A device comprising:

a memory; and

one or more processors of a client device, coupled to the memory, to;

determine—

states of a plurality of servers, wherein the states of the plurality of the servers associated with a media content provider indicate availability of the plurality of servers to deliver a media asset to the client device;

determine a subset of the plurality of servers available to deliver the media asset the client device in view of the determined states;

determine—

characteristics associated with the subset of the plurality of servers, wherein the characteristics comprise a cost to transmit the media asset to the client device from the subset of the plurality of servers through a plurality of service providers (SP) to the client device and a throughput rate of the subset of the plurality of servers, wherein the cost is indicative of a fee charged to the media content provider by different SPs of the plurality of SPs based on bandwidth utilization by the subset of the plurality of servers, wherein the subset of the plurality of servers use the different SPs of the plurality of SPs to transmit the media asset;

estimate a first bit rate at which the client device is to receive a first portion of the media asset, wherein the first bit rate is to provide for uninterrupted playback of the media asset, and wherein the first portion corresponds to data for a first playback time period of the media asset, wherein to estimate the first bit rate, the one or more processors to;

download header information for encoded frames of the first portion of the media asset prior to the encoded frames being received by the client device, wherein the header information indicates a starting timestamp, an ending timestamp, a starting byte offset, and an ending byte offset associated with the encoded frames, and

compute the first bit rate of the first portion of the media asset based on the header information; and

select based on the determined characteristics and the first bit rate, one or more servers from the subset of the plurality of servers to deliver the first portion of the media asset to the client device.

33. The device of claim 32, wherein the one or more processors further to:

estimate a second bit rate associated at which the client is to receive a second portion of the media asset, wherein the second portion corresponds to data for a second playback time period of the media asset that temporally follows the first playback time period of the first portion of the media asset; and

select, based on the determined characteristics and the second bit rate, one or more servers from the subset of the plurality of servers to deliver the second portion of the media asset to the client device.