Method and apparatus for economical cache population

• US 20020103974A1
• Filed: 11/29/2000
• Published: 08/01/2002
• Est. Priority Date: 11/29/2000
• Status: Abandoned Application

• Current Assignee: Augur Vision, Inc., Broadspider Networks, Inc. (OpenLocker Holdings, Inc.)
• Original Assignee: Augur Vision, Inc.
• Inventors: Pitio, Walter Michael, Giacomini, Peter Joseph, Shugard, Donald David, Rodriguez, Hector Francisco
• Application Number:
  US09/725,737
• Publication Number:
  US 20020103974A1
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A technique for efficiently populating a cache in a data processing system with resources is disclosed. In particular, a node in accordance with the illustrative embodiment of the present invention defers populating its cache with a resource until at least two requests for the resource have been received. This is advantageous because it prevents the cache from being populated with infrequently requested resources. Furthermore, the illustrative embodiment of the present invention populates a cache with a resource only when: at least i requests for the resource have been received at a given node within an elapsed time interval, Δt, wherein i is an integer greater than one; and at least one request for the resource has been received from at least n of the m filial nodes of the given node within an elapsed time interval, Δt, wherein m is an integer greater than one, n is an integer greater than one, and m≧n. Embodiments of the present invention are particularly advantageous in computer networks that comprise a logical hierarchical topology, but are useful an any computer network, and in individual data processing systems and routers that comprise a cache memory.

Claims

1. A method comprising:

populating a cache with a resource only when at least i requests for said resource have been received;

wherein at least occassionally i is an integer greater than one.

2. The method of claim 1 wherein the value of i is invariant.

3. The method of claim 1 wherein the value of i is based on calendrical time.

4. The method of claim 1 wherein said cache is populated with said resource only when at least i requests for said resource have been received within an elapsed time interval, Δ

t.

5. The method of claim 4 wherein the duration of said elapsed time interval, Δ

t, is based on the value of i.

6. The method of claim 4 wherein the value of i is based on calendrical time.

7. The method of claim 4 wherein the duration of said elapsed time interval, Δ

t, is based on calendrical time.

8. A data processing system comprising:

a cache for storing a resource; and

a processor for populating said cache with said resource only when at least i requests for said resource have been received;

wherein i is an integer greater than one.

9. The data processing system of claim 8 wherein the value of i is invariant.

10. The data processing system of claim 8 wherein the value of i is based on calendrical time.

11. The data processing system of claim 8 wherein said cache is populated with said resource only when at least i requests for said resource have been received within an elapsed time interval, Δ

t.

12. The data processing system of claim 8 wherein the duration of said elapsed time interval, Δ

t, is based on the value of i.

13. The data processing system of claim 8 wherein the value of i is based on calendrical time.

14. The data processing system of claim 8 wherein the duration of said elapsed time interval, Δ

t, is based on calendrical time.

16. The method of claim 15 wherein the value of i is invariant.

17. The method of claim 15 wherein the value of i is based on calendrical time.

18. The method of claim 15 wherein said cache is populated with said resource only when at least i requests for said resource have been received within an elapsed time interval, Δ

t.

19. The method of claim 18 wherein the duration of said elapsed time interval, Δ

t, is based on the value of i.

20. The method of claim 18 wherein the value of i is based on calendrical time.

21. The method of claim 18 wherein the duration of said elapsed time interval, Δ

t, is based on calendrical time.

15. A method comprising:

receiving at a first node in a computer network at least one request for a resource;

retrieving said resource from a second node in said computer network; and

populating a cache in said first node with said resource only when at least i requests for said resource have been received at said first node;

wherein i is an integer greater than one.

22. The method of claim 15:

wherein said computer network is a hierarchical computer network and said first node has m filial nodes;

wherein said cache is populated with said resource only when at least one request for said resource has been received from at least n of said m filial nodes; and

wherein m is an integer greater than one, n is an integer greater than one, and m≧

n.

23. The method of claim 15:

wherein said computer network is a hierarchical computer network and said first node has m filial nodes;

wherein said cache is populated with said resource only when at least one request for said resource has been received from at least n of said m filial nodes within an elapsed time interval, Δ

t; and

wherein m is an integer greater than one, n is an integer greater than one, and m≧

n.

25. The first node of claim 24 wherein the value of i is invariant.

26. The first node of claim 24 wherein the value of i is based on calendrical time.

27. The first node of claim 24 wherein said cache is populated with said resource only when at least i requests for said resource have been received within an elapsed time interval, Δ

t.

28. The first node of claim 27 wherein the duration of said elapsed time interval, Δ

t, is based on the value of i.

29. The first node of claim 27 wherein the value of i is based on calendrical time.

30. The first node of claim 27 wherein the duration of said elapsed time interval, Δ

t, is based on calendrical time.

24. A first node in a computer network, said first node comprising:

a cache;

at least one receiver for receiving at least one request for a resource; and

a processor for retrieving said resource from a second node in said computer network, and for populating said cache in said first node with said resource only when at least i requests for said resource have been received at said first node;

wherein i is an integer greater than one.

31. The first node of claim 24:

wherein said computer network is a hierarchical computer network and said first node has m filial nodes;

wherein said cache is populated with said resource only when at least one request for said resource has been received from at least n of said m filial nodes; and

wherein m is an integer greater than one, n is an integer greater than one, and m >

n.

32. The first node of claim 24:

wherein said computer network is a hierarchical computer network and said first node has m filial nodes;

wherein said cache is populated with said resource only when at least one request for said resource has been received from at least n of said m filial nodes within an elapsed time interval, Δ

t; and

wherein m is an integer greater than one, n is an integer greater than one, and m≧

n.