Method and system for adaptive prefetching

• US 8,275,778 B2
• Filed: 04/04/2011
• Issued: 09/25/2012
• Est. Priority Date: 12/06/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Corporation
• Original Assignee: Parallel Networks, LLC (epicRealm Licensing LP)
• Inventors: Saxena, Avinash C.
• Primary Examiner(s): BURKE, JEFF A
• Application Number:
  US13/079,557
• Publication Number:
  US 20110185004A1
• Time in Patent Office: 540 Days
• Field of Search: 707/736, 707/748, 707/751, 711/133
• 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 (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 in a network environment, comprising:

generating a graph having one or more links from one web page to one or more other web pages;

assigning a user weight and a transaction weight to each link in the graph, the transaction weight indicating a relative importance of a web page by a source of the web page compared to other web pages at the source and the user weight indicating a priority of the user;

receiving a request from a user for a particular web page, the request being associated with a link in the graph;

updating the graph in response to the request and the particular web page;

queuing the request with other requests, all requests having a priority and an associated link with an associated user weight and transaction weight;

updating the user weight and the transaction weight of each link in the graph based on the particular web page and the user;

prefetching one or more other web pages linked to the particular page in accordance with the transaction weight;

servicing the request based on the user weight and the priority in response to the request having a higher updated priority than all other requests waiting to be serviced.

2. The method of claim 1, further comprising:

comparing the transaction weights associated with the one or more other web pages linked to the particular web page to a prefetch threshold;

prefetching those other web pages having a transaction weight exceeding the prefetch threshold.

3. The method of claim 2, wherein the prefetch threshold is determined by an origin server storing the particular web page.

4. The method of claim 1, wherein the graph is generated incrementally upon receipt of the request.

5. The method of claim 1, wherein the graph is generated based on historical information related to web page requests from one or more users.

6. The method of claim 1, wherein the graph is uniquely associated with a particular origin server storing the particular web page.

7. The method of claim 1, wherein the graph is generated with all links from the particular web page.

8. A non-transitory computer readable storage medium including code for data processing in a network environment, the code upon execution operable to:

generate a graph having one or more links from one web page to one or more other web pages;

assign a user weight and a transaction weight to each link in the graph, the transaction weight indicating a relative importance of a web page by a source of the web page compared to other web pages at the source and the user weight indicating a priority of the user;

receive a request from a user for a particular web page, the request being associated with a link in the graph;

update the graph in response to the request and the particular web page;

queue the request with other requests, all requests having a priority and an associated link with an associated user weight and transaction weight;

update the user weight and the transaction weight of each link in the graph based on the particular web page and the user;

prefetch one or more other web pages linked to the particular page in accordance with the transaction weight;

service the request based on the user weight and the priority in response to the request having a higher updated priority than all other requests waiting to be serviced.

9. The non-transitory computer readable storage medium of claim 8, the code further operable to:

compare the transaction weights associated with the one or more other web pages linked to the particular web page to a prefetch threshold;

prefetch those other web pages having a transaction weight exceeding the prefetch threshold.

10. The non-transitory computer readable storage medium of claim 9, wherein the prefetch threshold is determined by an origin server storing the particular web page.

11. The non-transitory computer readable storage medium of claim 8, wherein the graph is generated incrementally upon receipt of the request.

12. The non-transitory computer readable storage medium of claim 8, wherein the graph is generated based on historical information related to web page requests from one or more users.

13. The non-transitory computer readable storage medium of claim 8, wherein the graph is uniquely associated with a particular origin server storing the particular web page.

14. The non-transitory computer readable storage medium of claim 8, wherein the graph is generated with all links from the particular web page.

15. A system for data processing in a network environment, comprising:

means for generating a graph having one or more links from one web page to one or more other web pages;

means for assigning a user weight and a transaction weight to each link in the graph, the transaction weight indicating a relative importance of a web page by a source of the web page compared to other web pages at the source and the user weight indicating a priority of the user;

means for receiving a request from a user for a particular web page, the request being associated with a link in the graph;

means for updating the graph in response to the request and the particular web page;

means for queuing the request with other requests, all requests having a priority and an associated link with an associated user weight and transaction weight;

means for updating the user weight and the transaction weight of each link in the graph based on the particular web page and the user;

means for prefetching one or more other web pages linked to the particular page in accordance with the transaction weight;

means for servicing the request based on the user weight and the priority in response to the request having a higher updated priority than all other requests waiting to be serviced.

16. The system of claim 15, further comprising:

means for comparing the transaction weights associated with the one or more other web pages linked to the particular web page to a prefetch threshold;

means for prefetching those other web pages having a transaction weight exceeding the prefetch threshold.

17. The system of claim 15, wherein the graph is generated incrementally upon receipt of the request.

18. The system of claim 15, wherein the graph is generated based on historical information related to web page requests from one or more users.

19. The system of claim 15, wherein the graph is uniquely associated with a particular origin server storing the particular web page.

20. The system of claim 15, wherein the graph is generated with all links from the particular web page.