Adaptive prefetching for computer network and web browsing with a graphic user interface

• US 6,385,641 B1
• Filed: 06/05/1998
• Issued: 05/07/2002
• Est. Priority Date: 06/05/1998
• Status: Expired due to Term

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Jiang, Zhimei, Kleinrock, Leonard
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): Thompson, Marc D.
• Application Number:
  US09/092,108
• Time in Patent Office: 1,432 Days
• Field of Search: 709/226, 709/229, 709/203, 709/219, 709/217
• US Class Current: 709/203
• 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: H04L 9/40 Network security protocols

Abstract

The present invention is based on a prefetching scheme consisting of two modules: a prediction module and a threshold module. After a use'"'"'s request for a new file is satisfied, the prediction module immediately updates a database of history information if needed, and computes the access probability for each candidate file, where the access probability of a file is an estimate of the probability with which that file will be requested by the user in the near future. Next the threshold module determines the prefetch threshold for each related server, which contains at least one candidate file with nonzero access probability. The threshold is determined in real time based on then current network conditions. Finally, each file whose access probability exceeds or equals its server'"'"'s prefetch threshold is prefetched. When prefetching a file, the file is actually downloaded if and only if no up-to-date version of the file is available on the local computer; otherwise no action is taken. Although web browsing is an important application for prefetching, the prefetch scheme of the present invention may be advantageously applied to any network application in which prefetching is possible.

Claims

1. A method for reducing latency of requests by a local computer for computer files available from a network computer by prefetching a subset of available computer files to the local computer comprising the steps of:

calculating an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein

calculating the access probability employs an application specific algorithm based on access history at the local computer, or network computer, or both;

calculating a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability and wherein calculating a prefetch threshold employs an algorithm that is not application specific, but is a function of system load, capacity, and cost of a time unit and a system resource unit to a user; and

accessing each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer.

2. The method of claim 1, wherein the step of calculating an access probability employs an algorithm particularly suited to a web browsing application and wherein a computer file is considered as being available only if the computer file is directly linked to a page be displayed by the local computer.

3. A method for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising the steps of:

determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer;

wherein the step of determining an access probability employs an algorithm particularly suited to a web browsing application and wherein a computer file is considered as being available only if the computer file is directly linked to a page being currently displayed by the local computer,

further comprising the steps of;

maintaining a page counter C_A for each page A;

determining if a link to a page B exists from page A and maintaining a link counter C_(A,B) for the pair if the link exists;

incrementing C_A whenever page A is downloaded;

incrementing C_(A,B) whenever page B is accessed by means of the link; and

determining the access probability ρ

of a page B_i linked to the page A being displayed by the local computer according to $p<br><br>\left(\mathrm{Bi}|A\right)=\min <br><br>\left(1,\frac{C_{\left(A,B_i\right)}}{C_A}\right)$

 

for C_A≧

5, and 0 for C_A<

5.

4. A method for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising the steps of:

determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer;

wherein the prefetch threshold is determined using an equation where α

_T represents a delay cost, α

_B represents a system resource cost, b represents capacity of a pathway for conducting a prefetched file to the local computer, ρ

represents an overall load of the computer network, and where the equation is given by $H=1-\frac{\left(1-\mathrm{\rho <br><br>}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}{{\left(1-\mathrm{\rho <br><br>}\right)}^2<br><br>b+\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}.$

5. A method for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising the steps of:

determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer;

wherein the prefetch threshold is determined using an equation where α

_T represents a delay cost, α

_B represents a system resource cost, b represents capacity of a pathway for conducting a prefetched file to the local computer, ρ

represents an overall load of the computer network, s represents a size of the prefetched file and where the equation is given by $H=1-\frac{\left(1-\mathrm{\rho <br><br>}\right)<br><br>\left(1+\frac{s_0}{s}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}{{\left(1-\mathrm{\rho <br><br>}\right)}^2<br><br>b+\left(1+\frac{s_0}{s}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}.$

6. A method for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising the steps of:

determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer;

wherein the prefetch threshold H_k for a user k is determined using an equation where α

_T represents a delay cost, α

_B represents a system resource cost, b represents capacity of a pathway for conducting a prefetched file to the local computer, ρ

represents an overall load of the computer network, s represents a size of the prefetched file, and λ

represents a file request rate and where the equation is given by $\begin{array}{c}{H}_k=\text{\hspace{1em}<br><br>}<br><br>1-\frac{{\mathrm{\alpha <br><br>}}_{T_k}<br><br>\left[b-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left({\mathrm{\lambda <br><br>}}_{i_1}+{\mathrm{\lambda <br><br>}}_{i_2}\right)<br><br>s\right]}{{{\mathrm{\alpha <br><br>}}_B<br><br>\left[b-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left({\mathrm{\lambda <br><br>}}_{i_1}+{\mathrm{\lambda <br><br>}}_{i_2}\right)<br><br>s\right]}^2+s<br><br>\underset{i=k}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_{i_1}<br><br>{\mathrm{\alpha <br><br>}}_{T_i}+{\mathrm{\alpha <br><br>}}_{T_k}<br><br>\left[b-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left({\mathrm{\lambda <br><br>}}_{i_1}+{\mathrm{\lambda <br><br>}}_{i_2}\right)<br><br>s\right]}\\ =\text{\hspace{1em}<br><br>}<br><br>1-\frac{\left(1-\mathrm{\rho <br><br>}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_{T_k}}{{\mathrm{\alpha <br><br>}}_B}}{{\left(1-\mathrm{\rho <br><br>}\right)}^2<br><br>b+\left(1-\mathrm{\rho <br><br>}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_{T_k}}{{\mathrm{\alpha <br><br>}}_B}+\frac{s}{b<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_B}<br><br>\underset{i=k}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_{i_1}<br><br>{\mathrm{\alpha <br><br>}}_{T_i}}.\end{array}$

7. An apparatus for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising:

means for calculating an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and, wherein calculating the access probability employs an application specific algorithm based on access history at the local computer, or network computer, or both;

means for calculating a prefetch threshold, based on current network conditions for, each computer network server containing at least one file with nonzero access probability wherein calculating a prefetch threshold employs an algorithm that is not application specific, but is a function of system load, capacity, and cost of a time unit and a, system resource unit to a user; and

means for prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer.

8. The apparatus of claim 7, wherein the means for calculating an access probability employs an algorithm particularly suited to a web browsing application and wherein a file is considered as being available only if the file is directly linked to a page being currently displayed by the local computer.

9. An apparatus for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising:

means for determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file, will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

means for determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

means for prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer,

wherein the means for determining an access probability employs an algorithm particularly suited to a web browsing application and wherein a file is considered as being available only if the file is directly linked to a page being currently displayed by the local computer,

further comprising;

means for maintaining a page counter C_A for each page A;

means for determining if a link to a page B exists from page A and for maintaining a link counter C_(A,B) for the pair if the link exists;

means for incrementing C_A whenever page A is downloaded;

means for incrementing C_(A,B) whenever page B is accessed by means of the link; and

means for determining the access probability ρ

of a page B_i linked to the page A being displayed by the local computer according to $p<br><br>\left(\mathrm{Bi}|A\right)=\min <br><br>\left(1,\frac{C_{\left(A,B_i\right)}}{C_A}\right)$

 

for C_A≳

5, and 0 for C_A<

5.

10. An apparatus for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising:

means for determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

means for determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

means for prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer,

wherein the means for determining a prefetch threshold operates according to an equation where α

_T represents a delay cost, α

_B represents a system resource cost, b represents capacity of a pathway for conducting a prefetched file to the local computer, ρ

represents an overall load of the computer network, and where the equation is given by $H=1-\frac{\left(1-\mathrm{\rho <br><br>}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}{{\left(1-\mathrm{\rho <br><br>}\right)}^2<br><br>b+\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}.$

11. An apparatus for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising:

means for determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

means for determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

means for prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer,

wherein the means for determining a prefetch threshold operates according to an equation where α

_T represents a delay cost, α

_B represents a system resource cost, b represents capacity of a pathway for conducting a prefetched file to the local computer, ρ

represents an overall load of the computer network, s represents a size of the prefetched file and where the equation is given by $H=1-\frac{\left(1-\mathrm{\rho <br><br>}\right)<br><br>\left(1+\frac{s_0}{s}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}{{\left(1-\mathrm{\rho <br><br>}\right)}^2<br><br>b+\left(1+\frac{s_0}{s}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_T}{{\mathrm{\alpha <br><br>}}_B}}.$

12. An apparatus for reducing latency of requests by a local computer for computer files available from a computer network by prefetching a subset of available computer files to the local computer comprising:

means for determining an access probability for each computer file available to the local computer wherein the access probability of a file is an estimate of the probability with which the file will be requested by the local computer and wherein determining the access probability employs an application specific algorithm;

means for determining a prefetch threshold, based on current network conditions for each computer network server containing at least one file with nonzero access probability wherein determining a prefetch threshold employs an algorithm that is not application specific; and

means for prefetching each file whose access probability exceeds or equals it'"'"'s server'"'"'s prefetch threshold if there is no current copy of the file already on the local computer,

wherein the means for determining a prefetch threshold determines a prefetch threshold H_k for a user k by using an equation where α

_T represents a delay cost, α

_B represents a system resource cost, b represents capacity of a pathway for conducting a prefetched file to the local computer, ρ

represents an overall load of the computer network, s represents a size of the prefetched file, and λ

represents a file request rate and where the equation is given by $\begin{array}{c}{H}_k=\text{\hspace{1em}<br><br>}<br><br>1-\frac{{\mathrm{\alpha <br><br>}}_{T_k}<br><br>\left[b-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left({\mathrm{\lambda <br><br>}}_{i_1}+{\mathrm{\lambda <br><br>}}_{i_2}\right)<br><br>s\right]}{{{\mathrm{\alpha <br><br>}}_B<br><br>\left[b-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left({\mathrm{\lambda <br><br>}}_{i_1}+{\mathrm{\lambda <br><br>}}_{i_2}\right)<br><br>s\right]}^2+s<br><br>\underset{i=k}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_{i_1}<br><br>{\mathrm{\alpha <br><br>}}_{T_i}+{\mathrm{\alpha <br><br>}}_{T_k}<br><br>\left[b-\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>\left({\mathrm{\lambda <br><br>}}_{i_1}+{\mathrm{\lambda <br><br>}}_{i_2}\right)<br><br>s\right]}\\ =\text{\hspace{1em}<br><br>}<br><br>1-\frac{\left(1-\mathrm{\rho <br><br>}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_{T_k}}{{\mathrm{\alpha <br><br>}}_B}}{{\left(1-\mathrm{\rho <br><br>}\right)}^2<br><br>b+\left(1-\mathrm{\rho <br><br>}\right)<br><br>\frac{{\mathrm{\alpha <br><br>}}_{T_k}}{{\mathrm{\alpha <br><br>}}_B}+\frac{s}{b<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_B}<br><br>\underset{i=k}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_{i_1}<br><br>{\mathrm{\alpha <br><br>}}_{T_i}}.\end{array}$