Method and apparatus for optimizing memory use in network caching

• US 7,107,321 B1
• Filed: 10/28/2004
• Issued: 09/12/2006
• 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): Cardone, Jason
• Assistant Examiner(s): Swearingen, Jeffrey R.
• Application Number:
  US10/978,042
• Time in Patent Office: 684 Days
• Field of Search: 709/219, 709/213, 709/217, 709/214, 709/216
• 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 processing 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 measure of a cost of caching the corresponding object;

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; and

adding a first data object to the network cache in response to said determining, if it is determined that the first data object is to be added to the network cache.

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

3. 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.

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

5. 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.

6. The method of claim 1, wherein the determining step further comprises sorting a subset of the plurality of data objects stored in the network cache with reference to the corresponding cost value functions thereby generating a sorted list.

7. 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.

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

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

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

11. The method of claim 6, wherein the determining step further comprises evicting selected ones of the subset of data objects from the network cache to accommodate storage of new data objects;

wherein the selection of the subset of data objects is based at least in part on positions of the data objects in the sorted list.

12. The method of claim 6, wherein the determining step further comprises resorting the subset of data objects each time the cost function value corresponding to any of the subset of data objects changes.

13. The method of claim 6, wherein the determining step further comprises resorting the subset of data objects each time a new data object is stored in the network cache.

14. The method of claim 9, wherein the cost function value for each object is also determined with reference to an object access time.

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

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

17. A device, comprising:

cache memory for storing a plurality of objects; and

one or more processors 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 measure of a cost of caching the corresponding object;

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 any attributes of currently cached objects; and

add a first data object to the network cache in response to a determination that the first data object is to be added to the network cache.

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

19. The device of claim 17, 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.

20. The device of claim 17, further comprising determining whether the corresponding cost function value exceeds cost function values associated with a number of the currently cached objects.

21. The device of claim 17, 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.

22. The device of claim 17, wherein the determining step further comprises sorting a subset of the plurality of data objects stored in the network cache with reference to the corresponding cost value functions thereby generating a sorted list.

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

24. The device of claim 18, wherein the cost function value for each object is determined with reference to a download time.

25. The device of claim 18, wherein the cost function value for each object is determined with reference to each of the object access time, the download time, the object size, and the number of object requests.

26. The device of claim 22, wherein the determining step further comprises evicting selected ones of the subset of data objects from the network cache to accommodate storage of new data objects;

wherein the selection of the subset of data objects is based at least in part on positions of the data objects in the sorted list.

27. The device of claim 22, wherein the determining step further comprises resorting the subset of data objects each time the cost function value corresponding to any of the subset of data objects changes.

28. The device of claim 22, wherein the determining step further comprises resorting the subset of data objects each time a new data object is stored in the network cache.

29. The device of claim 25, wherein the cost function value for each object is also determined with reference to an object access time.

30. The device of claim 26, wherein the cost function value for each object is proportional to each of the object access time, the download time, the object size, and the number of object requests.

31. The device of claim 30, wherein the cost function value for each object comprises the product of the object access time, the download time, and the number of object requests divided by the object size.

32. A computer-readable medium having computer program instructions stored therein for controlling one or more processors to perform the following steps:

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 measure of a cost of caching the corresponding object;

determining whether each of the data objects will be added to the network cache based upon its cost function value and not based upon any attributes of currently cached objects; and

adding a first data object to the network cache in response to said determining, if it is determined that the first data object is to be added to the network cache.

33. The computer-readable medium of claim 32, wherein the at least one metric for each object includes at least one of an object access time, a download time, an object size, and a number of object requests.

34. The computer-readable medium of claim 32, 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.

35. The computer-readable medium of claim 32, further comprising determining whether the corresponding cost function value exceeds cost function values associated with a number of the currently cached objects.

36. The computer-readable medium of claim 32, 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.

37. The computer-readable medium of claim 32, wherein the determining step further comprises sorting a subset of the plurality of data objects stored in the network cache with reference to the corresponding cost value functions thereby generating a sorted list.

38. The computer-readable medium of claim 32, wherein the plurality of metrics for each object includes a number of object requests, the computer program further comprising instructions for recalculating the cost function value for a particular data object each time the particular data object is requested.

39. The computer-readable medium of claim 33, wherein the cost function value for each object is determined with reference to a download time.

40. The computer-readable medium of claim 33, wherein the cost function value for each object is determined with reference to each of the object access time, the download time, the object size, and the number of object requests.

41. The computer-readable medium of claim 37, wherein the determining step further comprises evicting selected ones of the subset of data objects from the network cache to accommodate storage of new data objects;

wherein the selection of the subset of data objects is based at least in part on positions of the data objects in the sorted list.

42. The computer-readable medium of claim 37, wherein the determining step further comprises resorting the subset of data objects each time the cost function value corresponding to any of the subset of data objects changes.

43. The computer-readable medium of claim 37, wherein the determining step further comprises resorting the subset of data objects each time a new data object is stored in the network cache.

44. The computer-readable medium of claim 39, wherein the cost function value for each object is also determined with reference to an object access time.

45. The computer-readable medium of claim 40, wherein the cost function value for each object is proportional to each of the object access time, the download time, the object size, and the number of object requests.

46. The computer-readable medium of claim 45, wherein the cost function value for each object comprises the product of the object access time, the download time, and the number of object requests divided by the object size.

47. An apparatus, comprising:

mean 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 measure of a cost of caching the corresponding object;

means for determining whether each of the plurality of 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; and

means for adding a first data object to the network cache in response to a determination by the determining means that the first data object is to be added to the network cache.

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

49. The apparatus of claim 47, wherein the determining means compares the corresponding cost function value to a caching threshold.

50. The apparatus of claim 47, wherein the determining means determines whether the corresponding cost function value exceeds cost function values associated with a number of the currently cached objects.

51. The apparatus of claim 47, wherein the determining means generates a list of domains from which a majority of retrieved objects have corresponding cost function values indicating a caching cost beyond a caching threshold and determines whether each of the data objects is cacheable by determining whether each of the data objects was retrieved from one of the domains in the list.

52. The apparatus of claim 47, wherein the determining means sorts a subset of the plurality of data objects stored in the network cache with reference to the corresponding cost value functions thereby generating a sorted list.

53. The apparatus of claim 47, wherein the plurality of metrics for each object includes a number of object requests and the calculating means comprises means for recalculating the cost function value for a particular data object each time the particular data object is requested.

54. The apparatus of claim 48, wherein the calculating means determines the cost function value for each object with reference to a download time.

55. The apparatus of claim 48, wherein the calculating means determines the cost function value for each object with reference to each of the object access time, the download time, the object size, and the number of object requests.

56. The apparatus of claim 52, wherein the determine means evicts selected ones of the subset of data objects from the network cache to accommodate storage of new data objects;

wherein the selection of the subset of data objects is based at least in part on positions of the data objects in the sorted list.

57. The apparatus of claim 52, wherein the determining means resorts the subset of data objects each time the cost function value corresponding to any of the subset of data objects changes.

58. The apparatus of claim 52, wherein the determining means resorts the subset of data objects each time a new data object is stored in the network cache.

59. The apparatus of claim 54, wherein the calculating means determines the cost function value for each object with reference to an object access time.

60. The apparatus of claim 55, wherein the calculating means determines that the cost function value for each object is proportional to each of the object access time, the download time, the object size, and the number of object requests.

61. The apparatus of claim 60, wherein the calculating means determines that the cost function value for each object comprises the product of the object access time, the download time, and the number of object requests divided by the object size.

62. An apparatus for determining whether to add objects to a network cache, the apparatus comprising:

means for 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 object access time AT for the corresponding object;

means for 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; and

means for adding a first data object to the network cache in response to a determination by the determining means that the first data object is to be added to the network cache.

63. The apparatus of claim 62, wherein the cost function value is DT+AT.

64. The apparatus of claim 62, wherein the calculating means bases the cost function value upon the size S of each of the plurality of data objects.

65. The apparatus of claim 62, wherein the calculating means bases the cost function value upon the number n of cache requests for each of the plurality of data objects.

66. The apparatus of claim 62, wherein the calculating means also bases the cost function value upon the size S of and the number of cache requests n for each of the plurality of data objects.

67. The apparatus of claim 66, wherein the cost function value is n*AT*DT/S.

68. A method for determining 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 object access time AT for the corresponding object;

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; and

adding a first data object to the network cache in response to said determining, if it is determined that the first data object is to be added to the network cache.

69. The method of claim 68, wherein the cost function value is DT+AT.

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

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

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

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

77. The computer program of claim 68, wherein the cost function value is also based upon the number n of cache requests for each of the plurality of data objects.

78. The computer program of claim 68, wherein the cost function value is also based upon the size S of and the number of cache requests n for each of the plurality of data objects.

79. The computer program of claim 78, wherein the cost function value is n*AT*DT/S.

74. A computer program embodied in a machine-readable medium for determining whether to add objects to a network cache, the computer program comprising instructions for controlling at least one processor to perform the following steps:

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 object access time AT for the corresponding object;

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; and

adding a first data object to the network cache in response to said determining, if it is determined that the first data object is to be added to the network cache.

75. The computer program of claim 74, wherein the cost function value is DT+AT.

76. The computer program of claim 74, wherein the cost function value is also based upon the size S of each of the plurality of data objects.