Method and apparatus for optimizing memory use in network caching

• US 6,826,599 B1
• Filed: 06/15/2000
• Issued: 11/30/2004
• Est. Priority Date: 06/15/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shaffer, Shmuel, Cieslak, Martin, Aviani, James A. Jr.
• Primary Examiner(s): Wiley, David
• Assistant Examiner(s): Collins, Scott M.
• Application Number:
  US09/594,658
• Time in Patent Office: 1,629 Days
• Field of Search: 709/213, 709/214, 709/216, 711/133, 711/138, 711/139
• US Class Current: 709/213
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

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.

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.