Precomputation of web documents

• US 7,343,396 B2
• Filed: 06/11/2003
• Issued: 03/11/2008
• Est. Priority Date: 06/20/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Fineground Networks LLC
• Inventors: Jawahar, Janardhanan, Kausik, Balas Natarajan
• Primary Examiner(s): Burgess; Glenton B.
• Assistant Examiner(s): Higa; Brendan Y.
• Application Number:
  US10/459,365
• Publication Number:
  US 20040073867A1
• Time in Patent Office: 1,735 Days
• Field of Search: 709213-216, 709/224, 709/217, 709/219, 709/203, 711/118, 711/133
• US Class Current: 709/217
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Techniques are disclosed for anticipating a user'"'"'s request for documents or other content from a server (typically via a URL), precomputing the anticipated content, and caching the precomputed information at a cache in proximity to the content server. The cache stores the response to the anticipated request, until the user requests the same content. The anticipated requests can be precomputed based on triggers reflecting users'"'"' historical access patterns.

Claims

1. A method for improving the efficiency of document presentation, the method comprising:

precomputing dynamic content anticipated to be requested by a particular user computer from a content server;

storing said precomputed dynamic content in a cache at a proxy server between said content server and said user computer;

intercepting, at said proxy server, a request from said user computer to said content server for a document expected to include said dynamic content;

determining a load on said content server, and prorating an amount of precomputation based upon said load;

using said precomputed dynamic content in responding to said request from said user computer; and

managing freshness of said precomputed dynamic content, said freshness determined by validity enforcement techniques.

2. The method of claim 1, further comprising determining freshness based upon said validity enforcement techniques which include finding a difference between a moving average of a response time and a desired response time in retrieving a cache value, starting with an initial response time and determining exponential growth of this initial response time up to an optional preset time limit so long as said moving average of said response time exceeds a desired response time, setting a manual expiry time for a cache value, and using an expiration of a cache value on a message board as a basis to determine an expiry time.

3. The method of claim 2, further comprising:

monitoring said load o a content server;

and

prorating an amount of precomputation, said prorating occurring where a load on the content server is heavy.

4. The method of claim 1, further comprising:

maintaining a record of identifiers of documents deemed likely to trigger subsequent requests for dynamic content; and

maintaining a record of identifiers of documents deemed likely to comprise follow-on requests associated with a triggering document.

5. The method of claim 4, further comprising storing references, to at least some of said records, at said user computer.

6. The method of claim 4, where said record of identifiers of document are specific to particular users.

7. The method of claim 4, wherein said record of identifiers of documents deemed likely to trigger subsequent requests for dynamic content comprising a preexisting document.

8. The method of claim 4, wherein said record of identifiers of documents deemed likely to trigger subsequent requests for dynamic content comprising documents that are newly computed.

9. The method of claim 1, further comprising:

measuring a load on said content server; and

reducing precomputation during high load situations.

10. The method of claim 1, wherein said precomputed dynamic content in responding to said user'"'"'s request includes:

determining whether said request falls within a trigger class and, if so;

determining one or more associated document(s) from an anticipation class associated with said trigger class; and

storing said associated document(s) in said cache.

11. The method of claim 1, further comprising repeating said method for another requested document.

12. The method of claim 1, where said load is measured by at least one of comparing a response time of said content server with an absolute and predetermined desired response time, or by comparing a short term moving average of said content server with a long-term moving average of said response time.

13. A computer-readable medium for improving the efficiency of document presentation, comprising logic instructions that when executed:

precompute dynamic content anticipated to be requested by a particular user computer from a content server;

store said precomputed dynamic content in a cache at a proxy server between said content server and said user computer;

intercept, at said proxy server, a request from the user computer to said content server for a document expected to include said dynamic content;

determining a load on said content server, and prorating an amount of precomputation based upon said load;

use said precomputed dynamic content in responding to said request from said user computer; and

manage freshness of the precomputed dynamic content, the freshness determined by validity enforcement techniques.

14. The computer-readable medium of claim 13, further comprising logic instructions that when executed determine freshness based upon said validity enforcement techniques which include finding a difference between a moving average of a response time and a desired response time in retrieving a cache value, starting with an initial response time and determining exponential growth of this initial response time up to an optional preset time limit so long as said moving average of said response time exceeds a desired response time, setting a manual expiry time for a cache value, and using an expiration of a cache value on a message board as a basis to determine an expiry time.

15. The computer-readable medium of claim 13, further comprising logic instructions that when executed:

maintain a record of identifiers of documents deemed likely to trigger subsequent requests for dynamic content; and

maintain a record of identifiers of documents deemed likely to comprise follow-on requests associated with a triggering document.

16. The computer-readable medium of claim 13, further comprising logic instructions that when executed:

measure a load on said content server; and

reduce said precomputation during high load situations.

17. The computer-readable medium of claim 13, further comprising logic instructions that when executed:

determine whether said request falls within a trigger class, and, if so;

determine one or more associated document(s) from an anticipation class associated with said trigger class; and

store said associated document(s) in said cache.

18. Apparatus for improving the efficiency of document presentation, the apparatus comprising:

means for precomputing dynamic content anticipated to be requested by a particular user computer from a content server;

means for storing said precomputed dynamic content in a cache at a proxy server between said content server and said user computer;

means for intercepting, at said proxy server, a request from said user computer to said content server for a document expected to include said dynamic content;

means for determining a load on said content server, and prorating an amount of precomputation based upon said load;

means for using said precomputed dynamic content in responding to said request from said user computer; and

means for managing freshness of said precomputed dynamic content, the freshness determined by validity enforcement techniques.

19. A proxy server for improving the efficiency of document presentation from a content server to a user, comprising:

a computational module for precomputing dynamic content anticipated to be requested by a particular user computer from a content server;

a cache for storing said precomputed dynamic content anticipated to be requested by said user computer and to manage said freshness of the precomputed dynamic content via validity enforcement techniques; and

an interface connectable to said user computer and configured to;

intercept a request from said user computer to said content server for a document expected to include said dynamic content;

determine a load on said content server, and prorating an amount of precomputation based upon said load; and

serve said precomputed dynamic content to said user computer.

20. The proxy server of claim 19, further comprising a data storage including:

a record of identifiers of documents deemed likely to trigger subsequent requests for dynamic content; and

a record of identifiers of documents deemed likely to comprise follow-on requests associated with a triggering document.

21. The proxy server of claim 19, implemented as party of said content server.

22. A method for improving the efficiency of document presentation, the method comprising:

precomputing dynamic content anticipated to be requested by a particular user computer from a content server;

storing said precomputed dynamic content in a cache at a proxy server between said content server and said user computer;

intercepting, at said proxy server, a request from said user computer to said content server for a document expected to include said dynamic content;

using said precomputed dynamic content in responding to said request from said user computer;

managing freshness of said precomputed dynamic content, said freshness determined by validity enforcement techniques; and

determining freshness based upon said validity enforcement techniques which include finding a difference between a moving average of a response time and a desired response time in retrieving a cache value, starting with an initial response time and determining exponential growth of this initial response time up to an optional preset time limit so long as said moving average of said response time exceeds a desired response time, setting a manual expiry time for a cache value, and using an expiration of a cache value on a message board as a basis to determine an expiry time.

23. A computer-readable medium for improving the efficiency of document presentation, comprising logic instructions that when executed:

precompute dynamic content anticipated to be requested by a particular user computer from a content server;

store said precomputed dynamic content in a cache at a proxy server between said content server and said user computer;

intercept, at said proxy server, a request from the user computer to said content server for a document expected to include said dynamic content;

use said precomputed dynamic content in responding to said request from said user computer;

manage freshness of the precomputed dynamic content, the freshness determined by validity enforcement techniques; and

determine freshness based upon said validity enforcement techniques which include finding a difference between a moving average of a response time and a desired response time in retrieving a cache value, starting with an initial response time and determining exponential growth of this initial response time up to an optional preset time limit so long as said moving average of said response time exceeds a desired response time, setting a manual expiry time for a cache value, and using an expiration of a cache value on a message board as a basis to determine an expiry time.

24. A method for improving the efficiency of document presentation, the method comprising:

precomputing dynamic content anticipated to be requested by a particular user computer from a content server;

storing said precomputed dynamic content in a cache at a proxy server between said content server and said user computer;

intercepting, at said proxy server, a request from said user computer to said content server for a document expected to include said dynamic content;

using said precomputed dynamic content in responding to said request from said user computer;

managing freshness of said precomputed dynamic content, said freshness determined by validity enforcement techniques;

determining freshness based upon said validity enforcement techniques which include finding a difference between a moving average of a response time and a desired response time in retrieving a cache value, starting with an initial response time and determining exponential growth of this initial response time up to an optional preset time limit so long as said moving average of said response time exceeds a desired response time, setting a manual expiry time for a cache value, and using an expiration of a cache value on a message board as a basis to determine an expiry time;

monitoring said load of a content server; and

prorating an amount of precomputation, said prorating occurring where a load on the content server is heavy.