Method and system for adaptive prefetching

• US 7,113,935 B2
• Filed: 12/06/2000
• Issued: 09/26/2006
• Est. Priority Date: 12/06/2000
• Status: Expired due to Term

• Current Assignee: Parallel Networks, LLC (epicRealm Licensing LP)
• Original Assignee: Epicrealm Operating Inc.
• Inventors: Saxena, Avinash C.
• Primary Examiner(s): RIMELL, SAMUEL G
• Application Number:
  US09/731,365
• Publication Number:
  US 20020103778A1
• Time in Patent Office: 2,120 Days
• Field of Search: 709/219, 709/300, 709/226, 709/229, 709/203, 707/2, 707/3, 707/6, 705/26, 705/27
• US Class Current: 707/748
• 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 prefetches one or more web pages from an origin server prior to those web pages being requested by a user. The cache server determines which web pages to prefetch based on a graph associated with a prefetch module 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 and one or more links connecting the nodes. Each link has an associated transaction weight and user weight. 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 associated with a request for a web page. The user weight and transaction weight may change based on criteria associated with the origin server.

Claims

1. A method for data processing comprising:

receiving a web page request having an associated priority, 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, the transaction weight of a link indicating an importance of the link, each link having a respective associated user weight, the user weight of an link indicating a degree to which to modify the priority of the web page request at the link;

modifying the priority of the web page request at an link of the links in accordance with the user weight of the link;

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

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

7. The method for data processing according to claim 5, 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.

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

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

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

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

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

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

14. 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, the web page request having an associated priority;

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 node and the first node, the first link having an associated first user weight and an associated first transaction weight, the first user weight of the first link indicating a degree to which to modify the priority of the web page request at the first link, the first transaction weight of the first link indicating an importance of the first link;

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, the second user weight of the second link indicating a degree to which to modify the priority of the web page request at the second link, the second transaction weight of the second link indicating an importance of the second link;

modifying the priority of the web page request at a link of the first and second link in accordance with the user weight of the link;

selecting a second web page to retrieve based on the prefetch graph; and

storing the second web page at a cache server.

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

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

17. The method for data processing according to claim 14, 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.

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

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

20. The method for data processing according to claim 14, 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.

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

22. 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, the web page request having an associated priority;

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, the transaction weight of the first link indicating an importance of the first link;

associate a user weight with the first link based on the prefetch criteria, the user weight of the first link indicating a degree to which to modify the priority of the web page request at the first link;

modify the priority of the web page request at the first link in accordance with the user weight of the first link;

retrieve the first web page according to the prefetch graph; and

store the first web page.