US6317778B1 — System and method for replacement and duplication…

Claim 1

Independent Claim 169 words

In a system adapted to receive requests for objects from one or more clients, the system having at least one of a plurality of nodes, each node including at least one of a plurality of caches, a method for replacing any one of said objects stored in said at least one of the plurality of caches comprising the steps of: selecting more than one performance criterion of the system from a plurality of performance criteria; assigning at least one of a plurality of metrics to said more than one performance criterion; calculating the desirability of storing an object of said objects in any one of the plurality of caches by calculating at least one of a plurality of desirability values for at least one of said objects based on said at least one of the plurality of metrics; and replacing said any one of said objects stored in said at least one of the plurality of caches based on said at least one of the plurality of desirability values.

Claim 2

Dependent Claim 169 words

In a system adapted to receive requests for objects from one or more clients, the system having at least one of a plurality of nodes, each node including at least one of a plurality of caches, a method for replacing any one of said objects stored in said at least one of the plurality of caches comprising the steps of: selecting more than one performance criterion of the system from a plurality of performance criteria; assigning at least one of a plurality of metrics to said more than one performance criterion; calculating the desirability of storing an object of said objects in any one of the plurality of caches by calculating at least one of a plurality of desirability values for at least one of said objects based on said at least one of the plurality of metrics; and replacing said any one of said objects stored in said at least one of the plurality of caches based on said at least one of the plurality of desirability values.

Claim 3

Dependent Claim 47 words

The method of claim 1 , wherein a metric of the plurality of metrics is correlated with an amount by which storing a copy of one of the plurality of objects in a cache of the plurality of caches reduces utilization of a resource of the system.

Claim 4

Dependent Claim 23 words

The method of claim 2 , wherein the resource of the system includes processing capacity of a node of the plurality of nodes.

Claim 5

Dependent Claim 54 words

The method of claim 2 , wherein the plurality of nodes includes at least one of a plurality of level one nodes which is coupled to at least one of a plurality of level two nodes, and wherein the resource of the system includes processing capacity of any one of said level two nodes.

Claim 6

Dependent Claim 49 words

The method of claim 2 , wherein the plurality of nodes includes at least one of a plurality of level one nodes which is coupled to at least one of a plurality of level two nodes via a network, and wherein the resource of the system includes the network.

Claim 7

Dependent Claim 70 words

The method of claim 4 , wherein a desirability value of the plurality of desirability values for the copy of one of the plurality of objects is correlated with an expected number of hits to the object per unit time multiplied by an expected processing time on said any one of the plurality of level two nodes to fetch or calculate the object divided by a size of the object.

Claim 8

Dependent Claim 95 words

The method of claim 6 , wherein the desirability value for the copy of one of the plurality of objects is correlated with the quantity (t/a−t*p/u)/s, a being an expected time between successive requests for the object, t being the expected processing time for said any one of the plurality of level two nodes to fetch or calculate the object, u being an expected time between successive updates of the object, p being a probability that the object will be accessed between successive updates to the object, and s being the size of the object.

Claim 9

Dependent Claim 45 words

The method of claim 5 , wherein a desirability value of a plurality of desirability values for the copy of one of the plurality of objects is correlated with an expected number of hits to the object per unit time if the object is cached.

Claim 10

Dependent Claim 65 words

The method of claim 8 , wherein the desirability value for the copy of one of the plurality of objects is correlated with the quantity 1/a−p/u, a being an expected time between successive requests for the object, u being an expected time between successive updates of the object, and p being a probability that the object will be accessed between successive updates to the object.

Claim 11

Dependent Claim 24 words

The method of claim 1 , further comprising the step of varying a frequency with which said more than one performance criterion are selected.

Claim 12

Dependent Claim 44 words

The method of claim 2 , further comprising the steps of: (i) determining the resource of the system causing a bottleneck; and (ii) varying in response to the determination of step (i) a frequency with which said more than one performance criterion are selected.

Claim 13

Dependent Claim 61 words

The method of claim 11 , wherein step (ii) includes increasing the frequency of selection of said more than one performance criterion corresponding to the metric correlated with the amount by which storing the copy of one of the plurality of objects in the cache of the plurality of caches reduces utilization of the resource of the system causing the bottleneck.

Claim 14

Dependent Claim 87 words

The method of claim 12 , wherein the plurality of nodes includes at least one of a plurality of level one nodes which is coupled to at least one of a plurality of level two nodes via a network, and wherein the resource of the system causing the bottleneck is associated with at least one of processing power of any one of the plurality of level one nodes, processing power of at any one of the plurality of level two nodes, and a bandwidth of the network.

Claim 15

Dependent Claim 98 words

The method of claim 1 , the plurality of nodes includes at least one of a plurality of level one nodes which is coupled to at least one of a plurality of level two nodes, said method further comprising the step of: (i) determining a level one node to be a bottleneck in the system; and (ii) transmitting in response to the determination of step (i) one or more requests to any one of the plurality of level two nodes without first attempting to satisfy said one or more requests from a cache of the level one node.

Claim 16

Dependent Claim 123 words

The method of claim 1 , wherein the plurality of nodes includes at least one of a plurality of level one nodes which is coupled to at least one of a plurality of level two nodes via a network, the method further comprising the steps of: (i) determining at least one of a portion of the network and any one of the plurality of level two nodes to be a bottleneck in the system; and (ii) reducing in response to the determination of step (i) a number of requests sent to said any one of the plurality of level two nodes without first attempting to satisfy the request from a cache on a level one node of the plurality of level one nodes.

Claim 17

Independent Claim 165 words

A method for caching objects in a system adapted to receive requests for said objects from one or more clients, the system having at least one of a plurality of nodes, each node of the plurality of nodes including at least one of a plurality of caches, said method comprising the steps of: (a) selecting more than one performance criterion of the system from a plurality of performance criteria; (b) assigning at least one of a plurality of metrics to said more than one performance criterion; (c) calculating the desirability of storing an object of said objects in any one of the plurality of caches by calculating at least one of a plurality of desirability values for at least one of said objects based on said at least one of the plurality of metrics; and (d) duplicating any one of said objects stored in said at least one of the plurality of caches based on said at least one of the plurality of desirability values.

Claim 18

Independent Claim 165 words

A method for caching objects in a system adapted to receive requests for said objects from one or more clients, the system having at least one of a plurality of nodes, each node of the plurality of nodes including at least one of a plurality of caches, said method comprising the steps of: (a) selecting more than one performance criterion of the system from a plurality of performance criteria; (b) assigning at least one of a plurality of metrics to said more than one performance criterion; (c) calculating the desirability of storing an object of said objects in any one of the plurality of caches by calculating at least one of a plurality of desirability values for at least one of said objects based on said at least one of the plurality of metrics; and (d) duplicating any one of said objects stored in said at least one of the plurality of caches based on said at least one of the plurality of desirability values.

Claim 19

Dependent Claim 66 words

The method of claim 16 , wherein the plurality of nodes includes at least one of a plurality of level one nodes and a request of said requests is transmitted to a level one node of the plurality of level one nodes which does not contain a requested object of said objects, and the requested object is contained in a cache of the plurality of caches.

Claim 20

Dependent Claim 22 words

The method of claim 17 , wherein said more than one performance criterion includes reduction of a frequency of cache member misses.

Claim 21

Dependent Claim 24 words

The method of claim 17 , wherein said more than one performance criterion includes reduction of cache node misses due to a cache failure.

Claim 22

Dependent Claim 62 words

The method of claim 17 , wherein step (c) further includes calculating the desirability of storing the object of said objects in said any one of the plurality of caches based on an amount by which storing the object in said any one of the plurality of caches reduces utilization of resources of any one of the plurality of level one nodes.

Claim 23

Dependent Claim 118 words

The method of claim 20 , wherein a desirability value d 2 (o,i+1) of the plurality of desirability values for duplicating object o and storing an (i+1) th copy of object o in said any of the plurality of caches is given by d 2 ( o,i+ 1)=(1 /a−p/u )*savings( i+ 1)/ s, a being an expected time between successive requests for object o, p being a probability that object o may be accessed between successive updates to object o, u being an expected time between successive updates of object o, s being the size of object o, and savings(i+1) being an expected savings in cache processing time resulting from copying object o to an additional cache node.

Claim 24

Dependent Claim 63 words

The method of claim 21 , wherein savings( 1 ) is correlated with miss_time−hit_time( 1 ), miss_time being an expected cache array processing time to satisfy a request for object o in case of a cache array miss, and hit_time( 1 ) being an expected cache array processing time to satisfy a request for object o in case of a cache array hit.

Claim 25

Dependent Claim 59 words

The method of claim 21 , wherein savings(i) is correlated with hit_time(i)−hit_time(i+1), for i>1, miss_time being an expected cache array processing time to satisfy a request for object o in case of a cache array miss, and hit_time(i+1) being an expected cache array processing time to satisfy a request for object o in case of a cache array hit.

Claim 26

Dependent Claim 67 words

The method of claim 20 , further comprising the step of increasing the desirability of storing the object to be greater than the amount by which storing the object in said any one of the plurality of caches reduces utilization of resources of any one of the plurality of level one nodes to improve system performance in case of failure of the cache containing the requested object.

Claim 27

Dependent Claim 175 words

The method of claim 17 , further comprising the step of in response to said any one of the plurality of caches containing insufficient space for a new copy of the object: (i) determining at least one of a plurality of replacement candidates of said objects, wherein removal of said at least one of the plurality of replacement candidates from said any one of the plurality of caches provides sufficient space to store the new copy of the object; and (ii) removing said at least one of the plurality of replacement candidates from said any one of the plurality of caches and adding the new copy to said any one of the plurality of caches in response to a sum of said at least one of the plurality of desirability values assigned to said at least one of the plurality of replacement candidates weighted by the size of said at least one of the plurality of replacement candidates being less than a desirability of the new copy weighted by the size of the new copy.

Claim 28

Dependent Claim 21 words

The method of claim 1 , wherein the plurality of metrics includes a location of the object in a data structure.

Claim 29

Dependent Claim 26 words

The method of claim 26 , wherein the location of the object in the data structure is a position of the object in a linked list.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-11-12	2005-05-14	2005-11-13	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-11-12	2009-05-14	2009-11-13	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-11-12	2013-05-14	2013-11-13	$7700.00	Window Closed / Lapsed

System and method for replacement and duplication of objects in a cache

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag