Caching techniques for streaming media

• US 20030217113A1
• Filed: 04/08/2002
• Published: 11/20/2003
• Est. Priority Date: 04/08/2002
• Status: Active Grant

• Current Assignee: eTotalSource, Inc., Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Heckerman, David E., Katz, Ariel, Goodman, Joshua, Sagiv, Yifat, Friedel, Guy
• Granted Patent: US 7,076,544 B2
• Time in Patent Office: Days
• US Class Current: 709/213
• CPC Class Codes: H04L 67/2876 Pairs of inter-processing entities at each side of the network, e.g. split proxies
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A streaming media caching mechanism and cache manager efficiently establish and maintain the contents of a streaming media cache for use in serving streaming media requests from cache rather than from an original data source when appropriate. The cost of caching is incurred only when the benefits of caching are likely to be experienced. The caching mechanism and cache manager evaluate the request count for each requested URL to determine whether the URL represents a cache candidate, and further analyze the URL request rate to determine whether the content associated with the URL will be cached. In an embodiment, the streaming media cache is maintained with a predetermined amount of reserve capacity rather than being filled to capacity whenever possible.

Claims

1. A method of managing a cache in a computer network environment comprising at least one client computer resident as a node on a first network, a proxy server communicably linked to the first network and to a second network, and at least one server computer resident as a node on the second network, the method comprising:

receiving at the proxy server a request from a requesting one of the at least one client computers to a serving one of the at least one server computers for selected content associated with a selected resource identifier, wherein caching of the selected content would require the use of additional network resources in addition to those required for serving the content to the requesting client computer;

computing a count value associated with a number of times that the selected content has been requested by any of the at least one client computers; and

as a function of the determined count value, determining whether to store the selected content in the cache whereby while the selected content remains in the cache, future requests for the selected content by any of the at least one client computers will be served from the cache rather than from the serving one of the at least one server computers.

2. The method according to claim 1, further comprising deriving a rate value associated with a rate at which the selected content has been requested by any of the at least one client computers, and wherein determining whether to store the selected content in the streaming media cache further comprises determining as a function of the derived rate value whether to store the selected content in the streaming media cache.

3. The method according to claim 2, wherein the resource identifier is a URL, and wherein the second network is a wide area network.

4. The method according to claim 3, wherein the wide area network comprises the Internet, and the first network comprises a local area network.

5. A computer-readable medium having thereon instructions for performing the method according to claim 2.

6. The method according to claim 2, wherein the selected content comprises selected streaming media content, and wherein computing the count value associated with the number of times that the selected streaming media content has been requested by any of the at least one client computers further comprises:

ascertaining whether the received request for the selected streaming media content is the first request from any of the at least one client computers for the selected streaming media content; and

adding the selected resource identifier to a list of previously requested resource identifiers if the received request for the selected streaming media content is the first request for the selected streaming media content, wherein each resource identifier in the list is associated with an identity of a client computer previously requesting content associated with that resource identifier.

7. The method according to claim 6, further comprising:

determining via the list of previously requested resource identifiers whether the requesting client computer is the same as any client computer previously requesting content associated with the selected resource identifier;

incrementing a counter by a first predetermined value if the requesting client computer is not the same as any client computer previously requesting content associated with the selected resource identifier; and

incrementing the counter by a second predetermined value if the requesting client computer is the same as a client computer previously requesting content associated with the selected resource identifier, whereby the counter identifies the count value associated with the number of times that the selected streaming media content has been requested by any of the at least one client computers.

8. The method according to claim 7, wherein deriving a rate value associated with a rate at which the selected streaming media content has been requested by any of the at least one client computers comprises:

computing a first rate quotient of a predetermined number of requests for the selected streaming media content and an amount of time over which the predetermined number of requests were received, wherein the rate value is equal to the first rate quotient, if at least the predetermined number of requests have been received; and

computing a second rate quotient of a number of requests received for the selected streaming media content and the sum of an amount of time over which the number of requests were received and a nonzero padding factor, wherein the rate value is equal to the second rate quotient, if less than the predetermined number of requests have been received.

9. The method according to claim 8, wherein the nonzero padding factor is derived by steps comprising:

calculating an average time elapsed between at least some of a total of first and second received requests for streaming media content;

computing a potential padding factor by multiplying the average time by a multiplier factor;

setting the padding factor equal to the potential padding factor if the potential padding factor is not greater than a total amount of time elapsed from a predetermined start time; and

setting the padding factor equal to the total amount of time elapsed if the potential padding factor is greater than the total amount of time elapsed.

10. The method according to claim 8, wherein determining whether to store the selected streaming media content in the cache further comprises:

comparing the count value to a predetermined count threshold;

determining that the selected streaming media content is a cache candidate if the count value exceeds the predetermined count threshold, and determining that the selected streaming media content is not a cache candidate if the count value does not exceed the predetermined count threshold;

checking the cache to determine whether there is sufficient capacity remaining in the cache in which to store the selected streaming media content; and

if there is sufficient capacity remaining in the cache in which to store the selected streaming media content, storing the streaming media content corresponding to the cache candidate in the cache; and

if there is not sufficient capacity remaining in the cache in which to store the selected streaming media content, sorting a plurality of cached items in the cache according to a respective request rate value for each cached item;

progressively summing the sizes of the cached items in order of increasing request rate value until the sum of sizes exceeds the size of the cache candidate; and

removing the summed items from the cache if the rate value for the cache candidate exceeds the rate value for each such item, and storing the streaming media content corresponding to the cache candidate in the cache, and otherwise determining that the cache candidate will not be stored in the cache if the rate value for the cache candidate does not exceed the rate value for each such item.

11. The method according to claim 9, wherein the amount of time over which the predetermined number of requests were received, the average time elapsed between at least some of the total of first and second received requests, and the total amount of time elapsed from the predetermined start time are each measured by a global clock, wherein the global clock is adaptive, incrementing a unit of time whenever a request for streaming media content is received from any of the plurality of client computers.

12. A computer-readable medium having stored thereon a data structure comprising:

a URL data field for storing a value identifying at least one URL;

a request count data field associated with the URL data field for storing a request count value for each of the at least one URLs, wherein the request count value is derived from the number of times that streaming media content associated with the at least one URL has been requested; and

a request rate data field associated with the URL data field for storing a request rate value for the at least one URL, wherein the request rate value is derived from the time elapsed during the receipt of a predetermined number of requests for streaming media content associated with the at least one URL.

13. The computer-readable medium according to claim 12, wherein the data structure further comprises a user identification field associated with the URL data field for storing a user identification value for each of the at least one URLs, wherein the user identification value identifies at least one requester of the streaming media content associated with the at least one URL.

14. The computer-readable medium according to claim 13, wherein the user identification value is a hash of user-identifying information.

15. The computer-readable medium according to claim 14, wherein the user-identifying information comprises media player identification information.

16. The computer-readable medium according to claim 14, wherein the user-identifying information comprises network address information.

17. A method of caching streaming media content at a proxy server comprising:

analyzing a current request for an item of streaming media to determine whether the item of streaming media has been requested more than a predetermined number of times; and

determining that the item of streaming media is cachable if the item of streaming media has been requested more than the predetermined number of times.

18. The method according to claim 17, further comprising performing a caching analysis if it is found that the item of streaming media has been requested more than the predetermined number of times, the cache analysis comprising:

inspecting a streaming media cache to determine if storage of the item of streaming media in the cache would necessitate displacing one or more items already in the cache; and

if storage of the item of streaming media in the cache would necessitate displacing one or more items already in the cache, analyzing the frequency with which the item of streaming media has been requested and analyzing the frequency with which each of the one or more items has been requested; and

removing the one or more items from the cache, and adding the item of streaming media to the cache if it is found in the caching analysis that the frequency with which the item of streaming media has been requested exceeds the frequency with which each of the one or more items has been requested.

19. The method according to claim 18 wherein analyzing the current request for the item of streaming media to determine whether the item of streaming media has been requested more than a predetermined number of times further comprises:

determining whether a requesting computer associated with the current request is the same as a prior requesting computer associated with a prior request for the same item of streaming media;

counting the current request as a fraction of one request if the requesting computer associated with the current request is the same as a prior requesting computer associated with a prior request for the same item of streaming media; and

counting the current request as one request if the requesting computer associated with the current request is not the same as a prior requesting computer associated with a prior request for the same item of streaming media.

20. The method according to claim 18, wherein inspecting the streaming media cache to determine if storage of the item of streaming media in the cache would necessitate displacing one or more items already in the cache comprises determining whether the addition of the item of streaming media to the cache without displacing one or more items already in the cache would leave an amount of capacity in the cache that falls below a predetermined amount of reserve capacity.

21. The method according to claim 18, wherein analyzing the request frequency with which the item of streaming media has been requested further comprises;

giving the current request and each prior request for the item of streaming media a count value of less than or equal to one;

deriving a count sum by adding together the count values of each request starting with the current request and proceeding in reverse chronological order until the count sum is equal to or greater than a predetermined count limit or until no prior requests remain to be summed;

setting the request frequency equal to the quotient of the predetermined count limit and an amount of time that has transpired from receipt of the earliest request whose count value was summed until receipt of the current request, if the count sum is equal to or greater than the predetermined count limit; and

if the count sum is less than the predetermined count limit, setting the request frequency equal to a quotient of the count sum and a padded time factor, wherein the padded time factor comprises the sum of a buffer factor and an amount of time that has transpired from receipt of the earliest request whose count value was summed until receipt of the current request.

22. A proxy server for communicating between a local area network and a wide area network comprising:

a non-streaming media proxy and cache module for proxying requests for non-streaming media content from nodes of the local area network and responses thereto from nodes of the wide area network, and for establishing and maintaining a cache for retrievably storing requested non-streaming media content; and

a streaming media proxy and cache module comprising;

a proxy module for proxying requests from nodes of the local area network for streaming media content and responses thereto from nodes of the wide area network;

a streaming media cache for retrievably and selectively storing requested streaming media content; and

a cache manager for establishing and maintaining the contents of the streaming media cache, wherein the cache manager determines whether to add a current requested item to the cache based on a calculated request count derived from the number of requests made for the current item and a calculated request rate derived substantially from an inverse of an average period of time elapsed between each set of two temporally adjacent requests for the current item.

23. A method for retrieving an item of streaming media at a network client computer from a network server computer via a network intermediary computer comprising:

transmitting a request from the client computer to the intermediary computer for the item of streaming media, wherein the intended recipient of the request is the server computer;

receiving at the client computer from the intermediary computer the item of streaming media, wherein the item of streaming media was obtained by the intermediary computer from a streaming media cache maintained at the intermediary computer, and wherein the contents of the streaming media cache comprise a plurality of cache items of streaming media which are established and maintained as cache content as a function of a respective number of requests and frequency of requests received by the intermediary computer for each such cache item.

24. The method according to claim 23, wherein the item of streaming media comprises data selected from the group consisting of streaming audio data and streaming video data.