Method and system for adaptive prefetching

• US 20020103778A1
• Filed: 12/06/2000
• Published: 08/01/2002
• Est. Priority Date: 12/06/2000
• Status: Active Grant

• Current Assignee: Parallel Networks, LLC (epicRealm Licensing LP)
• Original Assignee: Epicrealm Inc.
• Inventors: Saxena, Avinash C.
• Granted Patent: US 7,113,935 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A cache server (18) may prefetch one or more web pages (30) from an origin server (16) prior to those web pages being requested by a user (13). The cache server determines which web pages to prefetch based on a graph (42) associated with a prefetch module (40) associated with the cache server. The graph represents all or a portion of the web pages at the origin server using one or more nodes (130) and one or more links (100) connecting the nodes. Each link has an associated transaction weight (102) and user weight (104). The transaction weight represents the importance of the link and associated web page to the origin server and may be used to control the prefetching of web pages by the cache server. The user weight may be used to change a priority (46) associated with a request (22) for a web page. The user weight and transaction weight may change based on criteria (50) associated with the origin server.

Claims

1. A method for data processing comprising:

receiving a web page request, the web page request requesting a first web page, the first web page being associated with an origin server;

associating the first web page with a first node in a prefetch graph;

associating a respective second node in the prefetch graph with each of a plurality of second web pages associated with the first web page;

generating at least one link in the prefetch graph between the first node and each of the second nodes, each link having a respective associated transaction weight;

selecting at least one of the second web pages to retrieve based on the graph; and

storing the selected second web pages at a cache server.

2. The method for data processing according to claim 1, wherein each link is associated with a hypertext link between each of the second web pages and the first web page.

3. The method for data processing according to claim 1 and further comprising:

receiving a selection of one of the hypertext links associated with the first web page; and

updating the transaction weight associated with the link associated with the selected hypertext link.

4. The method for data processing according to claim 3, wherein updating the transaction weight comprises changing the transaction weight based on criteria associated with the origin server.

5. The method for data processing according to claim 1, wherein each link further has a respective associated user weight.

6. The method for data processing according to claim 5, wherein the web page request has an associated priority and further comprising modifying the priority based on the user weight.

7. The method for data processing according to claim 5 and further comprising:

receiving a selection of one of the hypertext links associated with the first web page; and

updating the user weight associated with the link associated with the selected hypertext link.

8. The method for data processing according to claim 7, wherein updating the user weight comprises changing the user weight based on criteria associated with the origin server.

9. The method for data processing according to claim 7, wherein updating the user weight comprises increasing the user weight to indicate an increased value associated with the link because the hypertext link associated with link has been selected.

10. The method for data processing according to claim 1 and further comprising storing the prefetch graph at the cache server.

11. The method for data processing according to claim 1, wherein selecting the second web page comprises:

comparing a plurality of the transaction weights; and

selecting the second web page associated with the highest valued of the transaction weights.

12. The method for data processing according to claim 11, wherein the highest valued of the transaction weights comprises the transaction weight having the largest numerical value.

13. The method for data processing according to claim 11, wherein comparing the transaction weights further comprises determining which of the transaction weights exceeds a prefetch threshold associated with the cache server.

14. The method for data processing according to claim 13 and further comprising updating the prefetch threshold based on a processing load associated with the cache server.

15. The method for data processing according to claim 13 and further comprising updating the prefetch threshold based on a processing load associated with the origin server.

17. The method for data processing according to claim 16, wherein updating the first link comprises updating the first transaction weight.

18. The method for data processing according to claim 16, wherein updating the first link comprises updating the first user weight.

19. The method for data processing according to claim 16, wherein selecting the second web page comprises determining whether the selected second web page has an associated second transaction weight greater than a prefetch threshold associated with the cache server.

20. The method for data processing according to claim 19 and further comprising updating the prefetch threshold based on a processing load associated with the cache server.

21. The method for data processing according to claim 16, wherein the first and second links respectively indicate hypertext links.

22. The method for data processing according to claim 16, wherein selecting the second page comprises:

comparing a plurality of the second transaction weights; and

selecting the second web page associated with the second link having the highest valued of the transaction weights.

23. The method for data processing according to claim 22, wherein the highest valued of the transaction weights comprises the transaction weight having the largest numerical value.

16. A method for data processing comprising:

receiving a web page request for a first web page, the web page request having an associated origination web page;

associating an origination node in a prefetch graph with the origination web page;

associating a first node in the prefetch graph with the first web page, the first web page being associated with the origination web page;

updating a first link between the origination origination node and the first node, the first link having an associated first user weight and an associated first transaction weight;

associating a second node in the prefetch graph with each of a plurality of second web pages associated with the first web page;

generating a respective second link in the prefetch graph between the first node and each of the second nodes, each second link having an associated second user weight and an associated second transaction weight;

selecting a second web page to retrieve based on the transaction weight; and

storing the second web page at a cache server.

24. A system for data processing comprising:

a memory coupled to a processor;

an application stored in the memory and operable to;

receive a web page request for a first web page, the web page request having an associated origination web page;

associate an origination node in a prefetch graph with the origination web page;

associate a first node in the prefetch graph with the first web page, the first web page being associated with the origination web page;

associate a first link in the prefetch graph with a hypertext link from the origination web page to the first web page;

associate a transaction weight with the first link based on prefetch criteria associated with an origin server associated with the prefetch graph;

associate a user weight with the first link based on the prefetch criteria;

retrieve the first web page; and

store the first web page.