Method and apparatus for intelligent network bandwidth and system resource utilization for web content fetch and refresh

• US 6,701,316 B1
• Filed: 08/31/2000
• Issued: 03/02/2004
• Est. Priority Date: 04/07/2000
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Candan, Kasim Selcuk, Agrawal, Divyakant, Li, Wen-Syan
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): BAUGH, APRIL L
• Application Number:
  US09/654,106
• Time in Patent Office: 1,279 Days
• Field of Search: 709/232, 709/203, 709/219
• US Class Current: 370/395.41
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/959 Network

Abstract

A content delivery services provider is disclosed for directing the at least one proxy server to pre-fetch content from the at least one content provider original site using an optimum pre-fetch bandwidth allocation value. The content delivery services provider is part of a system for storing and delivering content, which includes a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content. These elements are coupled over a network for communicating with each other. The content delivery services provider programmed for: (1) modeling a retrieval time of content o of size size(o) using b units of bandwidth as ret(o)=congestion×size(o)×d(b), wherein d(b) is a unit delay observed when b units of bandwidth is used for pre-fetching the content, and congestion(Util) can be represented as $\mathrm{congestion}\left(\mathrm{Util}\right)=\frac{\beta }{{\mathrm{Util}}^{\theta }+\alpha }+\phi$

or congestion(Util)=β×(1.0−Util)^α+φ; (2) modeling an amount of delay observed by the at least one proxy server for the content fetched from the at least one content provider original site at time t₀ as $\mathrm{ret}\left(P\right)=\mathrm{congestion}\left(\frac{P+r\left(t_0\right)}{B}\right)\times r\left(t_0\right)\times d,$

wherein P is a pre-fetch bandwidth size, B is a total bandwidth available to the system, r(t)=(1−σ(P))×u(t) is an amount of bandwidth the system uses for retrieving end user browser requests for content that is not stored in the at least one proxy server, σ(P) is a cache freshness and availability value given a bandwidth P, and u(t) is a user access rate; (3) calculating the optimum pre-fetch bandwidth allocation value P by solving $\frac{\delta \mathrm{ret}\left(P\right)}{\delta P}=0;$

and (4) communicating the optimum pre-fetch bandwidth allocation value P to the at least one proxy server.

Claims

1. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site using a pre-fetch bandwidth allocation value, the content delivery services provider programmed for:

modeling a retrieval time of content o of size size(o) using b units of bandwidth as ret(o)=congestion×

size(o)×

d(b), wherein d(b) is a unit delay observed when b units of bandwidth is used for pre-fetching the content, congestion(Util) is a function that can be represented as $\mathrm{congestion}\left(\mathrm{Util}\right)=\frac{\mathrm{\beta <br><br>}}{{\mathrm{Util}}^{\mathrm{\theta <br><br>}}+\mathrm{\alpha <br><br>}}+\mathrm{\phi <br><br>}$

or congestion(Util)=β

×

(1.0−

Util)^α

+φ

, Util describes a ratio of network bandwidth used with respect to a maximum network bandwidth, and parameters α

, β

, and φ

are used for fitting the congestion function onto a congestion curve;

modeling an amount of delay observed by the at least one proxy server for the content fetched from the at least one content provider original site at time t₀ as $\mathrm{ret}<br><br>\left(P\right)=\mathrm{congestion}\left(\frac{P+r<br><br>\left(t_0\right)}{B}\right)\times <br><br>r<br><br>\left(t_0\right)\times <br><br>d,$

wherein P is a pre-fetch bandwidth size, B is a total bandwidth available to the system, r(t)=(1−

σ

(P))×

u(t) is an amount of bandwidth the system uses for retrieving end user browser requests for content that is not stored in the at least one proxy server, σ

(P) is a cache freshness and availability value given a bandwidth P, and u(t) is a user access rate;

calculating an optimum pre-fetch bandwidth allocation value P by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0;<br><br>$

and

communicating the optimum pre-fetch bandwidth allocation value P to the at least one proxy server.

2. A content delivery services provider as recited in claim 1, the content delivery services provider further programmed for computing an adjusted pre-fetch bandwidth allocation value which takes into account estimated worst-case bandwidth utilization by:

solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using a current bandwidth consumption (R=r(t₀)) for P;

calculating ret(P) using the current bandwidth consumption(R=r(t₀));

estimating a maximum bandwidth consumption R_max within the period [t₀, t₀+ret(P)×

p] using a history function h_r(t) which describes the behavior of r(t) until time t₀, where p is a degree of future look-up;

calculating an adjusted pre-fetch bandwidth allocation value P_adjusted by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using the estimated maximum bandwidth consumption (R=R_max); and

communicating the adjusted pre-fetch bandwidth allocation value P_adjusted to the at least one proxy server.

3. A content delivery services provider as recited in claim 2, the content delivery services provider further programmed for computing an averaged pre-fetch bandwidth allocation value which takes into account estimated average bandwidth utilization by:

calculating Δ

t=ret(P_adjusted)×

p using the estimated maximum bandwidth consumption (R_max);

defining average utility as ${\mathrm{Util}}_{\mathrm{avg}}=\frac{P_{\mathrm{avg}}\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+{\int <br><br>}_{t_0}^{t_0+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}<br><br>r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t}{B\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t},$

wherein ${\int <br><br>}_{t_0}^{t_0+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}<br><br>r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t$

is estimated using advance knowledge about bandwidth consumption or the history function h_r(t);

defining expected retrieval time Ret_exp(P_avg) using Util_avg and P_avg;

calculating an estimated averaged pre-fetch bandwidth allocation value P_avg by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{ret}}_{\exp }<br><br>\left(P_{\mathrm{avg}}\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{avg}}}=0;<br><br>$

and

communicating the averaged pre-fetch bandwidth allocation value P_avg to the at least one proxy server.

4. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the content delivery services provider programmed for:

calculating a priority value for pre-fetching content O_i as $\mathrm{priority}<br><br>\left(O_i\right)=\frac{\mathrm{query}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{frequency}\left(O_i\right)}^{c_1}\times <br><br>\mathrm{update}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{frequency}\left(O_i\right)}^{c_2}}{\mathrm{time}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{expire}<br><br>\left(O_i\right)}^{c_3}},$

wherein query frequency(O_i), update frequency(O_i), and time to expire(O_i) for each content O_i is obtained from a cache log file, and c₁, c₂, and c₃ are order coefficients which may be assigned using statistics from a prior time period or empirical computations over fixed time intervals;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time using the calculated priority values and a given pre-fetch bandwidth; and

communicating this set of content O_p to the at least one proxy server.

5. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the content delivery services provider programmed for:

calculating an expected number of stale objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{prob}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accessed}\right)\times <br><br>\mathrm{prob}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{stale}\right),<br><br>\text{\hspace{1em}<br><br>}$

wherein prob(o_i is accessed)=1−

(1−

q(o_i))<sup>Δ

t</sup>, prob(o_i is stale)=1−

(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>, q(o_i) is a query probability (for a unit time) for all o_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all O_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>1-\left[\left(1-{\left(1-q<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}\right)\times <br><br>\left(1-{\left(1-u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}\right)\right]$

while maintaining $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\mathrm{size}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t$

as a true statement, wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

communicating this set of content O_p to the at least one proxy server.

6. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the content delivery services provider programmed for:

calculating an expected number of fresh objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\sum <br><br>}<br><br>\mathrm{expected}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accesses}<br><br>\left(o_i\right)\times <br><br>\mathrm{prob}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{fresh}\right),$

wherein the expected number of accesses to object o_i in Δ

t units of time is Δ

t×

q(o_i), prob(o_i is fresh)=(1−

(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>), q(o_i) is a query probability (for a unit time) for all O_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all o_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>q<br><br>\left(o_i\right)\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>{\left(1-u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}$

while maintaining $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\mathrm{size}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t$

as a true statement, wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

communicating the set of content O_p to the at least one proxy server.

7. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site using a number of pre-fetch connections, the content delivery services provider programmed for:

modeling a retrieval time of content o of size size(o) as ret(o)=congestion×

size(o), wherein congestion(Util) can be represented as $\mathrm{congestion}<br><br>\left(\mathrm{Util}\right)=\frac{\mathrm{\beta <br><br>}}{{\mathrm{Util}}^{\mathrm{\theta <br><br>}}+\mathrm{\alpha <br><br>}}+\mathrm{\phi <br><br>}$

or congestion(Util)=β

×

(1.0−

Util)^α

+φ

, Util describes a ratio of connections open with respect to a maximum number of allowed connections, and parameters α

, β

, and φ

are used for fitting the congestion function onto a congestion curve;

modeling an amount of delay observed at the at least one proxy server for the content fetched from the at least content provider original site at time t₀ as $\mathrm{ret}<br><br>\left(P\right)=\mathrm{congestion}<br><br>\left(\frac{P+r<br><br>\left(t_o\right)+u<br><br>\left(t_o\right)}{B}\right)\times <br><br>\left(u<br><br>\left(t_o\right)+r<br><br>\left(t_o\right)\right)\times <br><br>\mathrm{avg}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{obj}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{size},$

wherein P is a number of pre-fetch connections, B is a maximum number of connections allowed, r(t)=(1−

σ

(P))×

u(t) is an amount of connections the system uses to request-fetch content that is not stored in the at least one proxy server, σ

(P) is a cache freshness and availability value given a bandwidth P, and u(t) is a user connection access rate;

calculating an optimum number of pre-fetch connections P by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0;<br><br>$

and

communicating the optimum number of pre-fetch connections P to the at least one proxy server.

8. A content delivery services provider as recited in claim 7, the content delivery services provider further programmed for computing an adjusted number of pre-fetch connections which takes into account estimated worst-case connection utilization by:

solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using a current number of connections used (R=r(t₀)) for P;

finding an amount of time ρ

required to prefetch P content using the congestion calculated using R and P;

estimating a maximum number of request-fetch connections R_max within the period [t₀, t₀+p] using a history function h_r(t) which describes the behavior of r(t) until time t₀, where p is a time required to prefetch the P content;

calculating an adjusted number of pre-fetch connections P_adjusted by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using the estimated maximum number of request-fetch connections (R=R_max); and

communicating the adjusted number of pre-fetch connections P_adjusted to the at least one proxy server.

9. A content delivery services provider as recited in claim 8, the content delivery services provider further programmed for computing an averaged number of pre-fetch connections which takes into account estimated average connection utilization by:

defining Δ

t as a worst-case amount of time required to pre-fetch P_adjusted connections;

defining average utilization as ${\mathrm{Util}}_{\mathrm{avg}}=\frac{P_{\mathrm{avg}}\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+{\int <br><br>}_{t_0}^{t_0+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}<br><br>\left(r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t+u<br><br>\left(t\right)\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t}{B\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t},$

wherein ${\int <br><br>}_{t_0}^{t_0+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}<br><br>r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t$

is estimated using advance knowledge about pre-fetch connections or the history function h_r(t);

defining expected retrieval time ret_exp(P_avg) using Util_avg and P_avg;

calculating an estimated averaged number of pre-fetch connections P_avg by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{ret}}_{\exp }<br><br>\left(P_{\mathrm{avg}}\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{avg}}}=0;<br><br>$

and

communicating the estimated averaged number of pre-fetch connections P_avg to the at least one proxy server.

10. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the content delivery services provider programmed for:

calculating a priority value for pre-fetching content O_i as $\mathrm{priority}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(O_i\right)=\frac{\mathrm{query}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{frequency}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(O_i\right)}^{c_1}\times <br><br>\mathrm{update}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{frequency}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(O_i\right)}^{c_2}}{\mathrm{time}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{expire}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(O_i\right)}^{c_3}},$

wherein query frequency(O_i), update frequency(O_i), and time to expire(O_i) for each content O_i is obtained from a cache log file, and c₁, c₂, and c₃ are order coefficients which may be assigned using statistics from a prior time period or empirical computations over fixed time intervals;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time using the calculated priority values and a given number of network connections; and

communicating this set of content O_p to the at least one proxy server.

11. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the content delivery services provider programmed for:

calculating an expected number of stale objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{prob}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accessed}\right)\times <br><br>\mathrm{prob}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{stale}\right),$

wherein prob(o_i is accessed)=1−

(1−

q(o_i))<sup>Δ

t</sup>, prob(o_i is stale)=1−

(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>, q(o_i) is a query probability (for a unit time) for all o_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all o_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>1-\left[\left(1-{\left(1-q<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}\right)\times <br><br>\left(1-{\left(1-u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}\right)\right]$

while maintaining $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{size}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>\mathrm{average}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{bandwidth}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{consumption}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{per}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{connection}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{as}<br><br>\text{\hspace{1em}<br><br>}<br><br>a<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{true}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{statement},$

wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

communicating the set of content O_p to the at least one proxy server.

12. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a content delivery services provider for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the content delivery services provider programmed for:

calculating an expected number of fresh objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{expected}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accesses}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i\right)\times <br><br>\mathrm{prob}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{fresh}\right),$

wherein the expected number of accesses to object o_i in Δ

t units of time is Δ

t×

q(o_i), prob(o_i is fresh)=(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>, q(o_i) is a query probability (for a unit time) for all o_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all o_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>q<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>{\left(u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}$

while maintaining $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{size}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>\mathrm{average}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{bandwidth}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{consumption}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{per}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{connection}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{as}<br><br>\text{\hspace{1em}<br><br>}<br><br>a<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{true}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{statement},$

wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

communicating the set of content O_p to the at least one proxy server.

13. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for pre-fetching content from the at least one content provider original site using a pre-fetch bandwidth allocation value, the method comprising the steps of:

modeling a retrieval time of content o of size size(o) using b units of bandwidth as ret(o)=congestion×

size(o)×

d(b), wherein d(b) is a unit delay observed when b units of bandwidth is used for pre-fetching the content, congestion(Util) can be represented as $\mathrm{congestion}\left(\mathrm{Util}\right)=\frac{\mathrm{\beta <br><br>}}{{\mathrm{Util}}^{\mathrm{\theta <br><br>}}+\mathrm{\alpha <br><br>}}+\mathrm{\phi <br><br>}$

or congestion(Util)=β

×

(1.0−

Util)^α

+φ

, Util describes a ratio of network bandwidth used with respect to a maximum network bandwidth, and parameters α

, β

, and φ

are used for fitting the congestion function onto a congestion curve;

modeling an amount of delay observed by the at least one proxy server for the content fetched from the at least one content provider original site at time t₀ as $\mathrm{ret}<br><br>\left(P\right)=\mathrm{congestion}\left(\frac{P+r<br><br>\left(t_0\right)}{B}\right)\times <br><br>r<br><br>\left(t_0\right)\times <br><br>d,$

wherein P is a pre-fetch bandwidth size, B is a total bandwidth available to the system, r(t)=(1−

σ

(P))×

u(t) is an amount of bandwidth the system uses for retrieving end user browser requests for content that is not stored in the at least one proxy server, σ

(P) is a cache freshness and availability value given a bandwidth P, and u(t) is a user access rate;

calculating an optimum pre-fetch bandwidth allocation value P by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0;<br><br>$

and

pre-fetching content from the at least one content provider original site using the optimum pre-fetch bandwidth allocation value P.

14. A method for pre-fetching content from the at least one content provider original site using a pre-fetch bandwidth allocation value as recited in claim 13, the method for further computing an adjusted pre-fetch bandwidth allocation value which takes into account estimated worst-case bandwidth utilization, the method further including the steps of:

solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using a current bandwidth consumption (R=r(t₀)) for P;

calculating ret(P) using the current bandwidth consumption(R=r(t₀));

estimating a maximum bandwidth consumption R_max within the period [t₀, t₀+ret(P)×

p] using a history function h_r(t) which describes the behavior of r(t) until time t₀, where p is a degree of future look-up;

calculating an adjusted pre-fetch bandwidth allocation value P_adjusted by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using the estimated maximum bandwidth consumption (R=R_max); and

pre-fetching content from the at least one content provider original site using the adjusted pre-fetch bandwidth allocation value P_adjusted.

15. A method for pre-fetching content from the at least one content provider original site using a pre-fetch bandwidth allocation value as recited in claim 14, the method for further computing an averaged pre-fetch bandwidth allocation value which takes into account estimated average bandwidth utilization, the method further including the steps of:

calculating Δ

t=ret(P_adjusted)×

p using the estimated maximum bandwidth consumption (R_max);

defining average utility as ${\mathrm{Util}}_{\mathrm{avg}}=\frac{P_{\mathrm{avg}}\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+{\int <br><br>}_{t_0}^{t_0+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}<br><br>r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t}{B\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t},$

wherein ${\int <br><br>}_{t_0}^{t_0+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}<br><br>r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t$

is estimated using advance knowledge about bandwidth consumption or the history function h_r(t);

defining expected retrieval time Ret_exp(P_avg) using Util_avg and P_avg;

calculating an estimated averaged pre-fetch bandwidth allocation value P_avg by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{ret}}_{\exp }<br><br>\left(P_{\mathrm{avg}}\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{avg}}}=0;<br><br>$

and

pre-fetching content from the at least one content provider original site using the averaged pre-fetch bandwidth allocation value P_avg.

16. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the method comprising the steps of:

calculating a priority value for pre-fetching content O_i as $\mathrm{priority}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(O_i\right)=\frac{\mathrm{query}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{frequency}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(O_i\right)}^{c_1}\times <br><br>\mathrm{update}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{frequency}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(O_i\right)}^{c_2}}{\mathrm{time}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{expire}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(O_i\right)}^{c_3}},$

wherein query frequency(O_i), update frequency(O_i), and time to expire(O_i) for each content O_i is obtained from a cache log file, and c₁, c₂, and c₃ are order coefficients which may be assigned using statistics from a prior time period or empirical computations over fixed time intervals;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time using the calculated priority values and a given pre-fetch bandwidth; and

communicating this set of content O_p to the at least one proxy server.

17. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the method comprising the steps of:

calculating an expected number of stale objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{prob}\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accessed}\right)\times <br><br>\mathrm{prob}\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{stale}\right),$

wherein prob(o_i is accessed)=1−

(1−

q(o_i))<sup>Δ

t</sup>, prob(o_i is stale)=1−

(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>, q(o_i) is a query probability (for a unit time) for all o_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all o_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>1-\left[\left(1-{\left(1-q<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}\right)\times <br><br>\left(1-{\left(1-u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}\right)\right]$

while maintaining $\underset{o_i\in <br><br>O_p}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{size}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t$

as a true statement, wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

pre-fetching content from the at least one content provider original site in the next Δ

t units of time-from the set of content O_p.

18. In a system for storing and delivering content, the system including a plurality of end-user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the method comprising the steps of:

calculating an expected number of fresh objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{expected}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accesses}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(o_i\right)\times <br><br>\mathrm{prob}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{fresh}\right),$

wherein the expected number of accesses to object o_i in Δ

t units of time is Δ

t×

q(o_i), prob(o_i is fresh)=(1−

(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>), q(o_i) is a query probability (for a unit time) for all o_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all o_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>q<br><br>\left(o_i\right)\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>{\left(1-u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}$

while maintaining $\underset{o_i\in <br><br>O_p}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{size}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t$

as a true statement, wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

pre-fetching content from the at least one content provider original site in the next Δ

t units of time from the set of content O_p.

19. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site using a number of pre-fetch connections, the method comprising the steps of:

modeling a retrieval time of content o of size size(o) as ret(o)=congestion×

size(o), wherein congestion(Util) can be represented as $\mathrm{congestion}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{Util}\right)=\frac{\mathrm{\beta <br><br>}}{{\mathrm{Util}}^{\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}}+\mathrm{\alpha <br><br>}}+\mathrm{\phi <br><br>}$

or congestion(Util)=β

×

(1.0−

Util)^α

+φ

, Util describes a ratio of connections open with respect to a maximum number of allowed connections, and parameters α

, β

, and φ

are used for fitting the congestion function onto a congestion curve;

modeling an amount of delay observed at the at least one proxy server for the content fetched from the at least content provider original site at time t₀ as $\mathrm{ret}<br><br>\left(P\right)=\mathrm{congestion}<br><br>\left(\frac{P+r<br><br>\left(t_o\right)+u<br><br>\left(t_o\right)}{B}\right)\times <br><br>\left(u<br><br>\left(t_o\right)+r<br><br>\left(t_o\right)\right)\times <br><br>\mathrm{avg}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{obj}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{size},$

wherein P is a number of pre-fetch connections, B is a maximum number of connections allowed, r(t)=(1−

σ

(P))×

u(t) is an amount of connections the system uses to request-fetch content that is not stored in the at least one proxy server, σ

(P) is a cache freshness and availability value given a bandwidth P, and u(t) is a user connection access rate;

calculating the optimum number of pre-fetch connections P by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0;<br><br>$

and

pre-fetching content from the at least one content provider original site using the optimum number of pre-fetch connections P.

20. A method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site using a number of pre-fetch connections as recited in claim 19, the method for further computing an adjusted number of pre-fetch connections which takes into account estimated worst-case connection utilization, the method further including the steps of:

solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using a current number of connections used (R=r(t₀)) for P;

finding an amount of time ρ

required to prefetch P content using the congestion calculated using R and P;

estimating a maximum number of request-fetch connections R_max within the period [t₀, t₀+P] using a history function h_r(t) which describes the behavior of r(t) until time t₀, where p is a time required to prefetch the P content;

calculating an adjusted number of pre-fetch connections P_adjusted by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ret}<br><br>\left(P\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P}=0$

using the estimated maximum number of request-fetch connections (R=R_max); and

pre-fetching content from the at least one content provider original site using the optimum number of pre-fetch connections P_adjusted.

21. A method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site using a number of pre-fetch connections as recited in claim 20, the method for further computing an averaged number of pre-fetch connections which takes into account estimated average connection utilization, the method further including the steps of:

defining Δ

t as a worst-case amount of time required to pre-fetch P_adjusted connections;

defining average utilization as ${\mathrm{Util}}_{\mathrm{avg}}=\frac{P_{\mathrm{avg}}\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+{\int <br><br>}_{t_0}^{t_0}<br><br>\left(r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t+u<br><br>\left(t\right)\right)<br><br><br><br>t}{B\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t},\mathrm{wherein}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\int <br><br>}_{t_0}^{t_0+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}<br><br>r<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br><br><br>t<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{estimated}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{using}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{advance}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{knowledge}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{about}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pre}<br><br>\text{-}<br><br>\mathrm{fetch}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{connections}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{or}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{history}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{function}<br><br>\text{\hspace{1em}<br><br>}<br><br>h_r<br><br>\left(t\right);<br><br>$

defining expected retrieval time Ret_exp(P_avg) using Util_avg and P_avg;

calculating an estimated averaged number of pre-fetch connections P_avg by solving $\frac{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{ret}}_{\exp }<br><br>\left(P_{\mathrm{avg}}\right)}{\mathrm{\delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>P_{\mathrm{avg}}}=0;<br><br>$

and

pre-fetching content from the at least one content provider original site using the averaged number of pre-fetch connections P_avg.

22. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the method comprising the steps of:

calculating a priority value for pre-fetching content O_i as $\mathrm{priority}<br><br>\left(O_i\right)=\frac{\mathrm{query}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{frequency}<br><br>\left(O_i\right)}^{c_1}\times <br><br>\mathrm{update}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{frequency}<br><br>\left(O_i\right)}^{c_2}}{\mathrm{time}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>\exp <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{ire}<br><br>\left(O_i\right)}^{c_3}},$

wherein query frequency (O_i), update frequency (O_i), and time to expire (O_i) for each content O_i is obtained from a cache log file, and c₁, c₂, and c₃ are order coefficients which may be assigned using statistics from a prior time period or empirical computations over fixed time intervals;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time using the calculated priority values and a given number of network connections; and

communicating this set of content O_p to the at least one proxy server.

23. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the method comprising the steps of:

calculating an expected number of stale objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\sum <br><br>}<br><br>\mathrm{prob}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accessed}\right)\times <br><br>\mathrm{prob}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{stale}\right),$

wherein prob(o_i is accessed)=1−

(1−

q(o_i))<sup>Δ

t</sup>, prob(o_i is stale)=1−

(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>, q(o_i) is a query probability (for a unit time) for all o_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all o_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>1-\left[\left(1-{\left(1-q<br><br>\left(o_i\right)\right)}^{\text{\hspace{1em}<br><br>}<br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t}\right)\times <br><br>\left(1-{\left(1-u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}\right)\right]$

while maintaining $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\mathrm{size}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>\mathrm{average}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{bandwidth}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{consumption}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{per}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{connection}$

as a true statement, wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

pre-fetching content from the at least one content provider original site in the next Δ

t units of time from the set of content O_p.

24. In a system for storing and delivering content, the system including a plurality of end user browsers for requesting content, at least one content provider original site for delivering the content, and at least one proxy server for storing the content coupled over a network for communicating with each other, a method for directing the at least one proxy server to pre-fetch content from the at least one content provider original site, the method comprising the steps of:

calculating an expected number of fresh objects that will be accessed in a following Δ

t units of time as $\underset{o_i\in <br><br>O}{\sum <br><br>}<br><br>\mathrm{expected}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{number}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{accesses}<br><br>\left(o_i\right)\times <br><br>\mathrm{prob}<br><br>\left(o_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{is}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{fresh}\right),$

wherein the expected number of accesses to object o_i in Δ

t units of time is Δ

t×

q(o_i) and prob(o_i is fresh)=(1−

u(o_i))<sup>Δ

t+(t−

lr(o_i))</sup>, q(o_i) is a query probability (for a unit time) for all o_iε

O, O is a set of objects, u(o_i) is an update probability (for a unit time) for all o_iε

O, and lr(o_i) is a last-retrieval time for all o_iε

O;

selecting a set of content O_p to pre-fetch in a next Δ

t units of time such that a number of stale objects accessed in a following Δ

t is minimized by using a 0-1 knapsack algorithm to maximize $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>q<br><br>\left(o_i\right)<br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>{\left(u<br><br>\left(o_i\right)\right)}^{\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t+\left(t-\mathrm{lr}<br><br>\left(o_i\right)\right)}$

while maintaining $\underset{o_i\in <br><br>O_p}{\sum <br><br>}<br><br>\mathrm{size}<br><br>\left(o_i\right)\le <br><br>P\times <br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t\times <br><br>\mathrm{average}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{bandwidth}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{consumption}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{per}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{connection}$

as a true statement, wherein size(o_i) is a size for all o_iε

O and P is a pre-fetch bandwidth; and

pre-fetching content from the at least one content provider original site in the next Δ

t units of time from the set of content O_p.