Method and apparatus for optimizing memory use in network caching

ABSTRACT

Techniques for handling objects in a network cache are described. A cost function value is calculated for each of a plurality of data objects. The cost function value relates to at least one metric relating to a total time required to download a corresponding one of the plurality of data objects. Each of the plurality of data objects are handled by the network cache according to its cost function value.

INFORMATION

DETAILED DESCRIPTION OF THE INVENTION

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

FIG. 1 shows a hardware environment in which the present invention may be implemented. A plurality of client platforms are interconnected via LAN . LAN is connected to router which is connected via network to destination platform . It will be assumed for the purposes of this discussion that client platforms are single personal computers or work stations, that router connects platform to the Internet, i.e., network , and that destination platform is a server on the World Wide Web. It should be noted, however, that a variety of configurations similar to this simple model may be employed without departing from the scope of the invention. For example, client platforms could be connected via a wide area network. Router could be an internal router in a LAN or a WAN (e.g., an intranet connection to an internal web page), the network's general gateway to the Internet, a direct connection to destination platform , or some intermediate platform between the network and destination platform . The connection between router and client platforms could include several intervening routers. Network could represent a local or wide area network which includes client platforms and router , or the Internet. Destination platform could be part of the local or wide area network, or a remote server on the Internet. Referring back to FIG. 1, network caches and are connected to router . Additional router is connected to router and has an additional network cache connected thereto.

It will be understood that the network caches described herein may employ any of a variety of existing file systems and remain within the scope of the invention. For example, the invention may be implemented using a Unix general purpose file system or the equivalent. A particular embodiment of the invention employs the file system described in commonly assigned, U.S. Pat. No. 5,950,205 for DATA TRANSMISSION OVER THE INTERNET USING A CACHE MEMORY FILE SYSTEM issued on Sep. 7, 1999, the entire specification of which is incorporated herein by reference for all purposes.

During normal operation, a client platform transmits a request to retrieve data such as, for example, a multimedia object from destination platform . Cache-enabled router receives the request in the form of at least one data packet. Router reads the packet header to determine whether, for example, it is a TCP packet and indicates port 80 as its destination port. If the packet is of a different protocol or is not destined for the World Wide Web, the packet is simply passed through the router and routed according to standard Internet protocols.

If, on the other hand, the packet is TCP and port 80 is specified, router determines to which of its associated network caches ( and ) it will redirect the packet based on the destination IP address specified in the packet. Before sending the packet to one of its associated network caches, router encapsulates the packet for transmission to the selected network cache by adding another TCP/IP header which designates the router as the source of the packet and the network cache as the destination. That is, the router encapsulates the packet for transmission to a network cache which might be several “hops” away. So, for example, router might encapsulate the packet for transmission to network cache which is connected to router via router . Thus, not only may multiple network caches be associated with a particular router, but multiple routers may be supported by an individual network cache or a group of network caches. This allows a tremendous amount of flexibility in where the network cache and router need to be in relation to each other. It will, of course, be understood that the present invention is not limited to port 80 or any particular packet encapsulation scheme (e.g., GRE, MAC, etc.)

A TCP connection is established between the client and the selected network cache and router transmits the encapsulated packet to the network cache. The network cache determines if it has the requested object stored locally by comparing the destination URL to its directory. If the object is determined to be locally stored in the network cache, it is transmitted to client platform . If, on the other hand the object is not in the cache, the network cache makes its own request for the object (using its own address as the source IP address) to destination platform via router . That is, a TCP connection is established between the network cache and destination platform . The router sees that the new request is from the network cache (by looking at the source address) and thereby knows not to redirect the packet to the network cache. This request and the subsequent retrieval of the object from destination platform is done according to standard TCP/IP protocols. The retrieved object is then transmitted to client platform .

FIG. 2 is a block diagram of a network cache such as, for example, cache of FIG. 1. A central processor controls operation of cache and its various subsystems using system memory and bus . Data objects are stored in cache memory which, in a specific embodiment, comprises multiple queues of volatile. RAM . According to various embodiments, memory may comprise one or more nonvolatile disk drives. According to yet other embodiments, memory may comprise any combination of volatile and nonvolatile memory.

According to a specific embodiment, a nonvolatile disk drive is provided as additional storage for cached objects. According to a more specific embodiment, cache objects below a certain size, e.g., html objects, are stored in RAM queues and those above a certain size, e.g., graphic objects, are stored in nonvolatile memory . In one such embodiment, the size threshold for determining in which memory to cache an object is 16 K. That is, objects which are 16 kilobytes or smaller would be stored in RAM queues , while object larger than 16 kilobytes would be stored in memory . In another such embodiment, the size threshold is 32 K. This segregation of objects by size allows extremely fast access to most cache objects via the RAM without the potential for very large objects to completely swamp a particular RAM queue and undermine the efficiency of cache operation.

A network interface enables communication with external devices. Portions of memory may also be employed for other purposes such as, for example, storing software code for directing the operation of various functionalities of cache . Alternatively, program instructions for execution by processor directing operation of the functionalities of cache may be stored in a separate program memory . It will be understood that the cache architecture shown in FIG. 2 is merely illustrative and should not be construed to limit the scope of the present invention. That is, any of a wide variety of cache architectures may be employed to implement the present invention.

A specific embodiment of the present invention will now be described with reference to flowchart of FIG. . When a request for an object is received by a cache configured according to the invention () and the object is determined not to be in the cache () the requested object is retrieved from the destination platform to which the original request was directed (). A cost function value for the retrieved object is then calculated ().

According to specific embodiments of the present invention, the cost function (CF) is based on at least one metric which affects the total time required to download the corresponding object. According to various embodiments, such metrics may include (but are not limited to) the number (n) of cache requests for the particular object, the access time (AT) for the object, the download time (DT) for the object, and the size (S) of the object. According to one embodiment, AT is determined by measuring the time between the first request from the cache to the destination platform and the first response received by the cache from the destination platform. According to one embodiment, DT is the time required for downloading the requested object from the destination platform to the cache.

According to a more specific embodiment, the cost function is simply the download time DT for the object. According to another embodiment, the cost function is the download time DT plus the access time AT. According to another more specific embodiment, the cost function is a function of all of these metrics, i.e., CF=f(n, AT, DT, S). According to a still more specific embodiment, the cost function is given by CF=n*AT*DT/S. Note that the DT/S term in this expression relates to the speed of the link. Note also that the lower the cost value, the less desirable it is to cache the corresponding object. That is, if the number of hits is low for a cached object, or the access or download times for a requested object are low, or the object is very large it is less likely that the object will be cached or stay in the cache very long. This makes sense in that, as discussed above, the desirability of caching an object tracks the number of times it is requested. In addition, if the AT or DT are very small, there is not much of an advantage for the end user in terms of performance and therefore such objects should not take up space in the cache. Finally, large objects are not favored in caching because they take up a lot of the memory for their share of cache hits.

Of course, it will be understood that the present invention is not limited to any particular formulation for the cost function. That is, cost functions using any of these metrics in various combinations which may include other metrics not described herein are also within the scope of the present invention. In addition, other metrics may be employed which relates to any of the metrics described above. For example, a bandwidth metric relating to the bandwidth of the connection between the cache and the destination platform may be employed. As will be understood, such a metric relates to the access time and download time for a given size object.

According to yet another embodiment, the network cache maintains a dynamic list of domain names for which the CF values are consistently low. According to this embodiment, objects from domains on the list are not cached to save I/O bandwidth. Thus, the determination of cacheability at may also be done with reference to such a list of domains or object sources.

Referring again to FIG. 3, and according to a specific embodiment of the invention, the cache determines whether the requested object is cacheable with reference to the cost function value (). According to a specific embodiment, this is done by comparing the cost function value to a configurable threshold value below or above which (depending on CF) the object is not considered worth caching. If cacheable, and there is not sufficient room in the cache (), and there are enough objects in the cache which may be discarded or evicted from the cache memory to accommodate the requested object (), such objects are evicted to make room for the requested object. According to a specific embodiment, this determination is done with reference again to the CF value. That is, according to this embodiment, all of the objects in the cache are sorted according to their CF values. The least valuable objects in the cache according to this sorting are discarded first. According to such embodiments, there must be a sufficient number of objects in the cache having CF values indicating a lower value than the requested object for the requested object to be cached.

If there was sufficient room in the cache () or there was a sufficient number of objects of lower value to be discarded to accommodate the new object () the requested object is placed in the cache memory and the sort according to its CF value (). The object is then transmitted to the requesting platform (). If at it was determined that the object was not cacheable or if at there was not a sufficient number of lower value objects in the cache to be evicted, it is also transmitted to the requesting platform () without being cached.

If at it is determined that the requested object is already stored in the cache, the object is transmitted to the requesting platform () and the cost function value for the object is updated (). That is, where the cost function depends on the number of requests received by the cache for the object, the cost function value needs to have this metric updated. The position of the requested object in the CF value sort is then adjusted based on the updated CF value (). Thus, to the extent that an object continues to be requested, its chances for remaining in the cache are enhanced.

While the invention has been particularly shown and described with reference to specific embodiments thereof, it will be understood by those skilled in the art that changes in the form and details of the disclosed embodiments may be made without departing from the spirit or scope of the invention. For example, the embodiments described above with reference to FIG. 3 include the combination of using the CF to determine cacheability, to identify particular domains, and to discard cached objects. It will be understood, however, that the present invention may use any one of these alone or in combination with any of the others and still remain within the scope of the invention. Therefore, the scope of the invention should be determined with reference to the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of a network environment in which specific embodiments of the present invention may be implemented;

FIG. 2 is a block diagram of a network cache for use with specific embodiments of the present invention; and

FIG. 3 is a flowchart illustrating the caching of objects according to a specific embodiment of the present invention.

CLAIMS

1. A computer implemented method for handling objects in a network cache comprising: calculating a cost function value for each of a plurality of data objects, the cost function value being determined with reference to at least one metric relating to a total time required to download a corresponding one of the plurality of data objects and providing a relative measure of a cost of caching the corresponding object; and evaluating each of the plurality of data objects according to its cost function value, wherein evaluating each of the plurality of data objects according to its cost function value comprises determining whether each of the data objects will be added to the network cache based directly upon its cost function value and not based upon any attributes of currently cached objects.

2. The method of claim 1 wherein the at least one metric for each object includes at least one of an access time, a download time, an object size, and a number of object requests.

3. The method of claim 2 wherein the cost function value for each object is determined with reference to a download time.

4. The method of claim 3 where the cost function value for each object is also determined with reference to an access time.

5. The method of claim 2 wherein the cost function value for each object is determined with reference to each of th access time, the download time, the object size, and tho number of object requests.

6. The method of claim 5 wherein the cost function value for each object is proportional to each of the access time, the download time, the object size, and the number of object requests.

7. The method of claim 6 wherein the cost function value for each object comprises the product of the access time the download time and the number of object requests divided by object size.

8. The method of claim 1 wherein determining whether each of the data objects will be added to the network cache comprises comparing the corresponding cost function value to a caching threshold.

9. The method of claim 1 further comprising determining whether the corresponding cost con value exceeds cost function values associated with a sufficient number of the currently cached objects.

10. The method of claim 1 further comprising generating a list of domains from which a majority of retrieved objects have corresponding cost function values indicating a caching cost beyond a caching threshold, determining whether each of the data objects is cacheable comprising determining whether each of the data objects was retrieved from one of the domains in the list.

11. The method of claim 1 wherein evaluating each of the plurality of data objects according to its cost function value further comprises sorting a subset of the plurality of data object stored in the network cache with reference to the corresponding cost value functions thereby generating a sorted list.

12. The method of claim 11 wherein evaluating each of the plurality of data objects according to its cost function value further comprises evicting selected ones of the subset of data objects from the network cache to accommodate storage of new data objects based on positions of the selected data objects in the sorted list.

13. The method of claim 11 wherein evaluating each of the plurality of data objects according to its cost function value further comprises resorting the subset of data objects each time the cost function value corresponding to any of the subset of data objects changes.

14. The method of claim 11 wherein evaluating each of the plurality of data objects according,to its cost function value further comprises resorting the subset of data objects each time a new data object is stored in the network cache.

15. The method of claim 1 wherein the plurality of metrics for each object includes a number of object requests, the method further comprising recalculating the cost function value for a particular data object each time the particular data object is requested.

16. A computer program product comprising a computer readable medium having computer program instructions stored therein for implementing the method of claim 1.

17. A network cache, comprising: cache memory for storing a plurality of objects; and an operating system which is operable to: calculate a cost function value for each of a plurality of data objects, the cost function value being determined with reference to at least one metric relating to a total time required to download a corresponding one of the plurality of data objects and providing a relative measure of a cost of caching the corresponding object; and determine whether each of the data objects will be added to the network cache based directly upon its cost function value and not based upon or attributes of currently cached objects.

18. A computer implemented method for evaluating whether to add objects to a network cache comprising: calculating a cost function value for each of a plurality of data objects, the cost function value being determined with reference to at least one metric relating to a total time required to download a corresponding one of the plurality of data objects and providing a relative measure of a cost of caching the corresponding object; and determining whether each of the data objects will be added to the network cache based directly upon its cost function value and not based upon any attributes of currently cached objects.

19. A computer program product comprising a computer readable medium having computer program instructions stored therein for implementing the method of claim 18.

20. An apparatus comprising: means for calculating a cost function value for each of a plurality of data objects, the cost function value being determined with reference to at least one metric relating to a total time required to download a corresponding one of the plurality of data objects and providing a relative measure of a cost of caching the corresponding object; and means for evaluating each of the plurality of data objects according to its cost function value, wherein evaluating each of the plurality of data objects according to its cost function value comprises determining whether each of the data objects will be added to the network cache based directly upon its cost function value and not based upon any attributes of currently cached objects.

21. A computer implemented method for evaluating whether to add objects to a network cache, the method comprising: calculating a cost function value C for each of a plurality of data objects, the cost function value being determined with reference to at least a time DT required to download a corresponding one of the plurality of data objects and an access time AT for the corresponding object; and evaluating each of the plurality of data objects according to its cost function value, wherein evaluating each of the plurality of data objects according to its cost function value comprises determining whether each of the data objects will be added to the network cache base directly upon its cost function value and not based upon any attributes of currently cached objects.

22. The method of claim 21, wherein the cost function value is DT+AT.

23. The method of claim 21, wherein the cost function value is also based upon the size S of each of the plurality of data objects.

24. The method of claim 21, wherein the cost function value is also based upon the number n of cache requests for each of the plurality of data objects.

25. The method of claim 21, wherein the cost function value is also based upon the size S of and the number of cache request n for each of the plurality of data objects.

26. The method of claim 25, wherein the cost function value is n*AT*DT/S.

COPYRIGHT

User acknowledges that Fairview Research and its third party providers retain all right, title and interest in and to this xml under applicable copyright laws. User acquires no ownership rights to this xml including but not limited to its format. User hereby accepts the terms and conditions of the License Agreement.