Method for caching of media files to reduce delivery cost

• US 6,868,452 B1
• Filed: 08/07/2000
• Issued: 03/15/2005
• Est. Priority Date: 08/06/1999
• Status: Expired due to Term

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Ferris, Michael C., Eager, Derek L., Vernon, Mary K.
• Primary Examiner(s): Cuchlinski, Jr., William
• Assistant Examiner(s): MESFIN, YEMANE
• Application Number:
  US09/633,722
• Time in Patent Office: 1,681 Days
• Field of Search: 709/203, 709/217, 709/226, 709/231, 709/235, 725/87, 725/90, 725/91, 725/92, 725/93, 725/97, 725/101, 725/103
• US Class Current: 709/231
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568

Abstract

Improvement on delivery of continuous media programs, such as video, divides the programs into prefixes and suffixes of data. One of these groups, or other groups associated with alternate on-demand data streaming, may be stored at a remote location, while the other of the groups may be stored at a plurality of regional locations. Accordingly, when the media program is ordered by a plurality of clients, a portion of the program will be broadcast from the regional server, while the other portion of the program will be transmitted from the remote server. The prefixes and suffixes are chosen so as to maximize the efficiency of data transfer taking into account the cost of storing the data as well as bandwidth costs.

Claims

1. A method of improving an efficiency of transmitting a continuous media program on-demand to multiple consumers, wherein the media program is transmitted from at least one regional storage location serving a corresponding plurality of consumers and a remote storage location in communication with the at least one regional storage location, in response to a plurality of consumer requests, the method comprising:

(a) splitting the program into a prefix and a suffix as a function of at least

     1) costs associated with storing the prefix at the at least one regional storage location and

     2) costs of transmitting the suffix from the remote storage location;

(b) storing the prefix in the at least one regional storage location;

(c) storing the suffix in the remote storage location;

(d) transmitting the prefix to the plurality of consumers from the corresponding at least one regional storage location; and

(e) transmitting the suffix to the plurality of consumers from the remote storage location.

2. The method as recited in claim 1, further comprising transmitting the prefix and suffix continuously.

3. The method as recited in claim 2, wherein the prefix comprises a leading group of segments, and wherein the suffix comprises a trailing group of segments.

4. The method as recited in claim 3, wherein the prefix and suffix are chosen so as to reduce the combined storage and bandwidth costs associated with transmitting an entire given media program to the plurality of clients.

5. The method as recited in claim 4, wherein the prefix and suffix are chosen so as to average down the combined storage and bandwidth costs associated with transmitting a plurality of media programs to the plurality of clients.

6. The method of claim 1, wherein the continuous media program is transmitted in accordance with a skyscrapering technique.

7. The method as recited in claim 1, wherein the prefix and suffix comprise a plurality of sequential segments of data.

8. The method as recited in claim 7, wherein the segments of the prefix are smaller than the segments of the suffix.

9. The method as recited in claim 1, wherein the media program may be transmitted via at least one of phone lines, cable systems, broadcast radio, and satellite links.

10. The method as recited in claim 1, wherein the prefix and suffix are further split as a function of costs associated with transmitting the prefix.

11. The method as recited in claim 1, wherein the prefix and suffix are further split as a function of costs associated with storing the suffix.

12. A method of reducing operation costs of an on-demand media file delivery system, wherein the media file is transmitted, from at least one of a plurality of regional storage locations and a remote storage location located remotely from the plurality of regional storage locations, in response to a plurality of client requests, the method comprising:

(a) splitting the media file into a fixed prefix and a fixed suffix;

(b) storing the prefix at the at least one regional storage location;

(c) storing the suffix at the remote storage location;

(d) transmitting the prefix to the plurality of clients from the at least one regional storage location; and

(e) transmitting the suffix to the plurality of clients from the remote storage location.

13. The method as recited in claim 12, wherein the prefix and suffix are further determined so as to reduce the storage costs of the prefix, and to reduce the transmission costs of the suffix.

20. The method as recited in claim 12, wherein the prefix and suffix are determined so as to reduce costs associated with transmitting the media file to the plurality of clients.

14. A method of improving an efficiency of transmitting a plurality of continuous media program on-demand to multiple consumers, wherein the media programs are transmitted from at least one regional server serving a corresponding plurality of consumers and a remote server in communication with the at least one regional server, in response to a plurality of consumer requests, the method comprising:

(a) splitting the programs into prefixes and a suffixes as a function of at least

     1) costs associated with storing the prefixes at the at least one regional storage location and

     2) costs of transmitting the suffix from the remote storage location;

(b) storing some of the prefixes in the at least one regional server;

(c) storing some of the suffixes in the remote server;

(d) transmitting the prefix of a requested media program to a plurality of requesting consumers from the corresponding at least one regional server; and

(e) transmitting the suffix of the requested media program to the plurality of requesting consumers from the remote server.

15. The method as recited in claim 14, wherein the prefix of the requested media program is empty, and the suffix comprises the entire media program.

16. The method as recited in claim 14, wherein the suffix of the requested media program is empty, and the prefix comprises the entire media program.

17. The method as recited in claim 14, wherein the prefixes and suffixes are determined for the plurality of media programs based at least in part on popularity levels of the media programs.

18. The method as recited in claim 14, wherein the prefixes and suffixes may be chosen according to the optimization model:

$\underset{\mathrm{\theta <br><br>}}{\min }<br><br>C_{\mathrm{remote}}<br><br>\left(\mathrm{\theta <br><br>}\right)+P<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\beta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>C_{\mathrm{regional}}<br><br>\left(\mathrm{\theta <br><br>}\right)$

wherein;

C_remote is a number of channels for remote server multicasts;

C_regional is a number of channels for regional server multicasts;

P is a number of regional servers;

β

is a cost of a regional server channel, relative to that of a remote server channel, and

θ

represents whether one of all and a portion of an object are stored at least at one of the regional and remote servers.

19. The method as recited in claim 14, wherein the model is subject to the conditions of:

C_regional(θ

)≦

N_channels;

D_regional(θ

)-≦

N_segments;

θ

_i^R,+θ

_i^P+, θ

_i^r=, 1,i=1,2, . . . , n; and

θ

_i^R,θ

_i^P, θ

_i^rε

{0,1}, i=1,2, . . . ,n,

wherein;

i is the media program;

D_regional defines storage needed at each regional server;

θ

_i^R has a value of 1 if the media program is stored only at the remote server, and has a value of 0 if the media program is not stored at the remote server;

θ

_i^P has a value of 1 if the prefix is stored at the regional server, and has a value of 0 if the prefix is not stored at the regional server;

θ

_i^r has a value of 1 if the entire media file is stored regionally, and has a value of 0 if the entire media file is not stored regionally;

N_channels is a maximum number of channels at each regional storage location; and

N_segments is a storage capacity at each regional server.