Method of prefetching reference objects using weight values of referrer objects

• US 7,107,406 B2
• Filed: 06/12/2002
• Issued: 09/12/2006
• Est. Priority Date: 06/13/2001
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kurasugi, Toshiyasu
• Primary Examiner(s): Moazzami, Nasser
• Assistant Examiner(s): Farrokh, Hahem
• Application Number:
  US10/166,604
• Publication Number:
  US 20020194434A1
• Time in Patent Office: 1,553 Days
• Field of Search: 711113-146, 711/154, 711/162, 707 1- 5, 707/10, 707/104.1, 707/202, 370/235, 370 29-230, 370/335, 370/346, 370/389, 370/395.41
• US Class Current: 711/137
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

In a client-cache-server system, the weight value of a first object which is maintained in the cache and linked to a second object maintained in the server is determined. Based on the weight value, a decision is made as to whether prefetching is necessary. If the decision indicates that prefetching is necessary, the second object is prefetched from the server to refresh the cache. A further decision is made as to whether update enquiry is necessary based on the weight value. If the further decision indicates that update enquiry is necessary, a message is sent to the server for inquiring whether the first object has been updated in the server. If the server responds with a reply that indicates that the first object has been updated, the second object is prefetched from the server to refresh the cache.

Claims

1. A method of operating a cache, comprising the steps of:

a) determining a weight value of a first object maintained in the cache, said first object having a link to a second object maintained in a server;

b) making a decision as to whether prefetching is necessary based on said weight value; and

c) if the decision of step (b) indicates that prefetching is necessary, prefetching said second object from said server.

2. The method of claim 1, wherein step (b) comprises making a decision that said prefetching is necessary if said weight value is higher than a predetermined value.

3. The method of claim 1, wherein step (a) comprises incrementing said weight value in response to a request from a client device.

4. The method of claim 3, wherein said request contains an identifier and ancillary information, said identifier identifying said first object.

5. The method of claim 1, wherein step (a) comprises determining said weight value from a count number of different links through which said first object is linked to a plurality of second objects maintained in said server.

6. The method of claim 1, wherein step (b) comprises:

determining ranks of weight values of a plurality of objects maintained in said cache, said plurality of objects including said first object, wherein the rank of the first object represents said weight value; and

making said decision based on the rank of said first object relative to a predetermined rank.

7. The method of claim 1, wherein step (a) comprises:

retrieving an identifier of said second object maintained in said cache;

identifying an object associated with said retrieved identifier as said first object; and

incrementing the weight value of the first object,

wherein step (b) comprises;

determining ranks of weight values of a plurality of objects maintained in said cache, said plurality of objects including said first object, wherein the rank of the first object represents said weight value; and

making said decision based on the rank of said first object relative to a predetermined rank.

8. The method of claim 1, wherein step (c) comprises:

mapping identifiers of a plurality of objects maintained in said server to a plurality of objects maintained in said cache in a management table;

comparing identifier of said second object with each of the identifiers of said objects maintained in said cache;

prefetching said second object from said server if the identifier of said second object do not coincide with any of the identifiers of said objects maintained in said cache; and

updating said management table by mapping the identifier of said second object to said first object.

9. The method of claim 1, wherein step (c) comprises the steps of:

estimating a timing parameter in response to a request from said client device based on client-server information records;

storing a plurality of said requests in a buffer;

scheduling the stored requests according to the respective timing parameters of the requests and data size of said requests so that a total data size of said requests during a predetermined time interval does not exceed a predetermined size; and

prefetching data of said scheduled requests from said server.

10. The method of claim 9, wherein the step of estimating comprises the steps of:

estimating start timing at which the prefetching of said data can be started based on said client-server information records;

estimating end timing at which the prefetching of said data must be completed based on said client-server information records;

estimating a time interval required to retrieve said data from said server based on said client-server information records; and

estimating said timing parameter using at least one of said estimated start timing, said estimated end timing and said estimated time interval.

11. The method of claim 9, wherein the step of scheduling comprises monitoring a data rate of total downlink transmissions and additionally scheduling the stored requests according to the monitored data rate.

12. The method of claim 1, wherein step (c) comprises the steps of:

estimating update enquiry timing for an object of a request from said client device;

storing a plurality of requests in a buffer according to the estimated update enquiry timing;

scheduling the stored requests according to data size of the requests so that a total data size of a time slot does not exceed a predetermined size; and

sending said update enquiry message to said server during said time slot.

13. The method of claim 12, wherein the step of estimating comprises the steps of:

estimating start timing at which said update enquiry message can be transmitted based on said client-server information records;

estimating end timing at which said update reply message must be received based on said client-server information records;

estimating a time interval required to receive said reply message from said server based on said client-server information records; and

estimating said timing parameter using at least one of said estimated start timing, said estimated end timing and said estimated time interval.

14. The method of claim 12, wherein the step of scheduling comprises monitoring a data rate of total downlink transmissions and additionally scheduling the stored requests according to the monitored data rate.

15. The method of claim 12, wherein the step of scheduling further comprises scheduling the stored requests according to priorities of said requests.

16. The method of claim 1, wherein step (c) comprises the steps of:

c₁) estimating a timing parameter for a prefetch request in response to a request from said client device based on client-server information records;

c₂) storing a plurality of said prefetch requests in sequential positions of a buffer;

c₃) reading a given prefetch request from a position of said buffer during a time interval of a predetermined length;

c₄) examining the timing parameter of said given prefetch request and discarding the given prefetch request if the timing parameter thereof indicates that current time has past;

c₅) producing a sum of a data size of the given prefetch request plus a data size of prefetch requests which have been transmitted to said server;

c₆) shifting the position of the buffer and returning to step (c₃) if said sum exceeds a predetermined data size; and

c₇) transmitting the given prefetch request to the server if said sum does not exceed said predetermined data size, shifting the position of the buffer and repeating steps (c₃) to (c₆).

17. The method of claim 16, further comprising the steps of:

monitoring downlink transmissions and detecting data rate of the monitored downlink transmissions; and

estimating said predetermined data size from the detected data rate.

29. The method of claim 9, wherein step (c) comprises the steps of;

c₁) estimating a timing parameter for an update enquiry request in response to a request from said client device based on client-server information records;

c₂) storing a plurality of said an update enquiry requests in sequential positions of a buffer;

c₃) reading a given an update enquiry request from a position of said buffer during a time interval of a predetermined length;

c₄) examining the timing parameter of said given update enquiry request and discarding the given update enquiry request if the timing parameter thereof indicates that current time has past;

c₅) producing a sum of a data size of the given update enquiry request plus a data size of update enquiry requests which have been transmitted to said server;

c₆) shifting the position of the buffer and returning to step (c₃) if said sum exceeds a predetermined data size; and

c₇) transmitting the given update enquiry request to the server if said sum does not exceed said predetermined data size, shifting the position of the buffer and repeating steps (c₃) to (c₆).

30. The method of claim 29, further comprising the steps of:

monitoring downlink transmissions and detecting data rate of the monitored downlink transmissions; and

estimating said predetermined data size from the detected data rate.

18. A method of operating a cache, comprising the steps of:

a) determining a weight value of a first object maintained in said cache, said first object having a link to a second object maintained in a server;

b) making a decision as to whether update enquiry is necessary based on said weight value; and

c) if the decision of step (b) indicates that update enquiry is necessary, sending an update enquiry message to said server and receiving a reply message therefrom; and

d) prefetching said second object from said server if said reply message indicates that said first object has been updated.

19. The method of claim 18, wherein step (d) further comprises:

retrieving an identifier of said second object maintained in said cache;

identifying an object associated with said retrieved identifier as said first object; and

prefetching said second object according to the retrieved identifier.

20. The method of claim 18, wherein step (b) comprises making a decision that said update enquiry is necessary if said weight value is higher than a predetermined value.

21. The method of claim 18, wherein step (a) comprises incrementing said weight value in response to a request from a client device.

22. The method of claim 21, wherein said request contains an identifier and ancillary information, said identifier identifying said first object.

23. The method of claim 18, wherein step (a) comprises determining said weight value from a count number of different links through which said first object is linked to a plurality of second objects maintained in said server.

24. The method of claim 18, wherein step (b) comprises:

determining ranks of weight values of a plurality of objects maintained in said cache, said plurality of objects including said first object, wherein the rank of the first object represents said weight value; and

making said decision based on the rank of said first object relative to a predetermined rank.

25. The method of claim 18, wherein step (a) comprises:

retrieving an identifier of said second object maintained in said cache;

identifying an object associated with said retrieved identifier as said first object; and

incrementing the weight value of the first object,

wherein step (b) comprises;

determining ranks of weight values of a plurality of objects maintained in said cache, said plurality of objects including said first object, wherein the rank of the first object represents said weight value; and

making said decision based on the rank of said first object relative to a predetermined rank.

26. The method of claim 18, wherein step (c) comprises:

mapping identifiers of a plurality of objects maintained in said server to a plurality of objects maintained in said cache in a management table;

comparing identifier of said second object with each of the identifiers of said objects maintained in said cache;

prefetching said second object from said server if the identifier of said second object do not coincide with any of the identifiers of said objects maintained in said cache; and

updating said management table by mapping the identifier of said second object to said first object.

27. The method of claim 18, wherein step (c) comprises the steps of:

introducing a presettable delay time; and

following said delay time, sending said update enquiry message to said server and receiving said reply message therefrom.

28. The method of claim 18, wherein said presettable delay time is an estimated time interval from records of requests received from the client device.

31. A method of operating a cache, comprising the steps of:

a) responsive to a first request from a client device, making a decision as to whether prefetching is necessary based on a weight value of a first object maintained in said cache, said first object having a link to a second object maintained in a server;

b) if the decision of step (a) indicates that prefetching is necessary, prefetching said second object from said server;

c) incrementing said weight value in response to a second request from said client device;

d) making a decision as to whether prefetching is necessary based on said weight value;

e) if the decision of step (e) indicates that prefetching is necessary, prefetching said second object from said server; and

f) repeating steps (a) to (e).

32. A system comprising:

a cache; and

a processor for determining a weight value of a first object maintained in said cache, said first object having a link to a second object maintained in a server, making a decision as to whether prefetching is necessary based on said weight value, and prefetching said second object from said server if said decision indicates that prefetching is necessary.

33. The system of claim 32, wherein the processor makes a decision that said prefetching is necessary if said weight value is higher than a predetermined value.

34. The system of claim 32, wherein the processor increments said weight value in response to a request from a client device.

35. The system of claim 34, wherein said request contains an identifier identifying said first object and ancillary information.

36. The system of claim 32, wherein the processor determines said weight value from a count number of different links through which said first object is linked to a plurality of second objects maintained in said server.

37. The system of claim 32, wherein the processor determines ranks of weight values of a plurality of objects maintained in said cache, said plurality of objects including said first object, wherein the rank of the first object represents said weight value, and makes said decision based on the rank of said first object relative to a predetermined rank.

38. The system of claim 32, wherein the processor is arranged to:

retrieve an identifier of said second object maintained in said cache,

identify an object associated with said retrieved identifier as said first object,

increment the weight value of the first object,

determine ranks of weight values of a plurality of objects maintained in said cache, said plurality of objects including said first object, wherein the rank of the first object represents said weight value, and

makes said decision based on the rank of said first object relative to a predetermined rank.

39. The system of claim 32, wherein the processor is arranged to:

map identifiers of a plurality of objects maintained in said server to a plurality of objects maintained in said cache in a management table,

compare identifier of said second object with each of the identifiers of said objects maintained in said cache,

prefetch said second object from said server if the identifier of said second object do not coincide with any of the identifiers of said objects maintained in said cache; and

update said management table by mapping the identifier of said second object to said first object.

40. The system of claim 32, wherein the processor is arranged to:

determine a weight value of a first object maintained in said cache, said first object having a link to a second object maintained in a server;

make a decision as to whether update enquiry is necessary based on said weight value; and

if the decision of step (b) indicates that update enquiry is necessary, send an update enquiry message to said server and receiving a reply message therefrom, and

prefetch said second object from said server if said reply message indicates that said first object has been updated.

41. A computer readable storage medium containing an executable program comprising the steps of:

a) determining a weight value of a first object maintained in a cache, said first object having a link to a second object maintained in a server;

b) making a decision as to whether prefetching is necessary based on said weight value; and

c) if the decision of step (b) indicates that prefetching is necessary, prefetching said second object from said server.

42. A computer readable storage medium containing an executable program comprising the steps of:

a) determining a weight value of a first object maintained in said cache, said first object having a link to a second object maintained in a server;

b) making a decision as to whether update enquiry is necessary based on said weight value; and

c) if the decision of step (b) indicates that update enquiry is necessary, sending an update enquiry message to said server and receiving a reply message therefrom; and

d) prefetching said second object from said server if said reply message indicates that said first object has been updated.

43. A computer readable storage medium containing an executable program comprising the steps of:

a) responsive to a first request from a client device, making a decision as to whether prefetching is necessary based on a weight value of a first object maintained in said cache, said first object having a link to a second object maintained in a server;

b) if the decision of step (a) indicates that prefetching is necessary, prefetching said second object from said server;

c) incrementing said weight value in response to a second request from said client device;

d) making a decision as to whether prefetching is necessary based on said weight value;

e) if the decision of step (e) indicates that prefetching is necessary, prefetching said second object from said server; and

f) repeating steps (a) to (e).