\batchmode
\documentstyle[proc]{article}
\makeatletter













\title{\bf Cost-Aware WWW Proxy Caching Algorithms}
\author{\begin{tabular}{ccc}
	{\Large Pei Cao} & \hspace{1cm} & {\Large Sandy Irani} \\ 
	{\em Department of Computer Science,} & &
		{\em Information and Computer Science Department,} \\ 
	{\em University of Wisconsin-Madison.} & &
		{\em University of California-Irvine.}\\ 
	cao@cs.wisc.edu  & & irani@ics.uci.edu  
	\end{tabular}
}








\newcommand {\comment}[1]{{}}

\def\BEGIN{{\bf begin}\ }

\def\END{{\bf end}\ }

\def\IF{{\bf if}\ }

\def\THEN{{\bf then}\ }

\def\ELSE{{\bf else}\ }

\def\WHILE{{\bf while}\ }

\def\FOR{{\bf for}\ }

\def\TO{{\bf to}\ }

\def\RETURN{{\bf return}\ }

\def\blo{\noindent\begin{center}
        \begin{tabular}{|@{\quad}l@{\quad}|}\hline
        \begin{minipage}{1in}\tt
        \begin{tabbing}
        \qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill}

\def\elo{\end{tabbing}\end{minipage}\\ \hline\end{tabular}\end{center}}

\newenvironment {algorithm}{\blo}{\elo}

\def\PsfigVersion{1.9}

\def\begin@lgo{\noindent\begin{center}
        \begin{tabular}{|@{\quad}l@{\quad}|}\hline
        \begin{minipage}{1in}\tt
        \begin{tabbing}
        \qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill}

\def\end@lgo{\end{tabbing}\end{minipage}\\ \hline\end{tabular}\end{center}}

\newtheorem {lemma}{Lemma}

\newtheorem {claim}[lemma]{Claim}

\newtheorem {theorem}[lemma]{Theorem}

\newtheorem {corollary}[lemma]{Corollary}

\newtheorem {observation}[lemma]{Observation}

\newtheorem {conclusion}[lemma]{Conclusion}

\newtheorem {assumption}[lemma]{Assumption}

\newtheorem {conjecture}[lemma]{Conjecture}

\newtheorem {fact}[lemma]{Fact}

\newcommand {\mod}[1]{\!\!\!\pmod{#1}}

\newcommand {\etal}{{\em et al.}}

\newcommand {\hO}{{\hat O}}

\newcommand {\hatt}{{\hat t}}

\def\nin{\noindent}

\def\bgno{\bigbreak\noindent}

\def\definition{\bgno{\bf Definition. }}

\def\notation{\nin{\bf Notation.}}

\def\remark{\nin{\bf Remark.}}

\def\concat{\widehat{\phantom\al}}

\def\lim{\mathop{\rm lim}\nolimits }

\def\liminf{\mathop{\rm lim\,inf}\nolimits }

\def\st{\rm such that}

\def\proof{\paragraph{Proof.}}

\def\proofof#1{\paragraph{Proof of #1.}}

\def\sketch{\paragraph{Proof Sketch.}}

\def\pair#1{\langle#1\rangle}

\newcommand {\qed}{\mbox{}\hspace*{\fill}\nolinebreak\mbox{$\Box$}\smallskip}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
{\newpage
\clearpage
\samepage \begin{tabular}{ccc}
	{\Large Pei Cao} & \hspace{1cm} & {\Large Sandy Irani} \\ 
	{\em Department of Computer Science,} & &
		{\em Information and Computer Science Department,} \\ 
	{\em University of Wisconsin-Madison.} & &
		{\em University of California-Irvine.}\\ 
	cao@cs.wisc.edu  & & irani@ics.uci.edu  
	\end{tabular}
}

\stepcounter{section}
\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$c_s$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline770: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$b_s$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline774: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$n_p$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline778: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$z_p$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline782: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}\frac{\left(c_s + \frac{W_b}{b_s}\right)(n_p)^{W_n}}{z_p}\end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$W_b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline788: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$W_n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline790: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P_i$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline800: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$D_{i+1}/D_i$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline808: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$D_i$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline810: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P_i(s)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline814: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{displaymath}D(t) = .035\log(t+1) + .45\left( 1- e^{\frac{-t}{2e6}}\right).\end{displaymath}
}

{\newpage
\clearpage
\samepage \begin{displaymath}V(i,t,s)= \left\{\begin{array}{ll}
P_1(s)(1 - D(t))*c/s & \mbox{~if~}i=1\\ 
P_i(1-D(t))*c/s &\mbox{~otherwise~}\\ 
\end{array}
\right.
\end{displaymath}
}

\stepcounter{subsubsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$O(\log k)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline848: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{figure}\psfig{figure=graphs/locality/9-12-9-19.alluser.latex.ps}

\label{alluser-reaccess}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}\psfig{figure=graphs/locality/9-12-9-19.peruser.latex.ps}

\label{peruser-reaccess}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\psfig{figure=graphs/locality/cumulative_hitratio.latex.ps}

\label{accumulative-reaccess}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure*}\psfig{figure=graphs/locality/group_size_correlation.latex.ps}

\label{group-size-correlation}
\end{figure*}
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$min_H$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline922: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\noindent\begin{center}
\begin{tabular}{|@{\quad}l@{\quad}|}\hline
\begin{minipage}{1in}\tt
\begin{tabbing}
\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill Algorithm {\sc GreedyDual}:\\ 
Initialize $L \leftarrow 0$.                               \\ 
Process each request document in turn:\\ 
The current request is for document $p$:\\ 
 (1)\>{\bf if}\   $p$ is already in memory,\\ 
 (2)\>\> $H(p)  \leftarrow L + c(p)/s(p)$.         \\ 
(3)\>{\bf if}\   $p$ is not in memory,\\ 
(4)\>\> {\bf while}\ there is not enough room\\ 
\>\> in memory for $p$,\\ 
(5)\>\> \>  Let $L \leftarrow \min_{q \in M} H(q)$.            \\ 
(6)\>\>\>   Evict $q$ such that $H(q) = L$.\\ 
(7)\>\>   Bring $p$ into memory and set\\ 
\>\>  $H(p) \leftarrow L+c(p)/s(p)$\\ 
\>   {\bf end}\                                                         \\ 
\end{tabbing}\end{minipage}\\   \hline\end{tabular}\end{center}   
\vspace{-\belowdisplayskip}

\label{fig:gd}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{theorem}GreedyDual-Size is $k$-competitive, where $k$ is the ratio of the size
of the cache to the size of the smallest document.
\end{theorem}
}

\stepcounter{paragraph}
{\newpage
\clearpage
\samepage \begin{displaymath}L \le \min_{p \in M} H(p) \le H(q) \le L + \frac{c(q)}{s(q)}.\end{displaymath}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$L_{final}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1014: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s_{min}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1018: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s_{cache}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1020: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$k = s_{cache}/s_{min}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1022: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s_{min} \cdot L_{final}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1024: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$s_{cache} \cdot L_{final}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1026: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$c(p)/s(p) \le c(p)/s_{min}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1052: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$L_1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1054: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$H(p) \le L_1 + c(p)/s(p)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1058: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$L_1 + c(p)/s(p)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1088: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$L_2$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1096: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$L_2 - L_1 \ge c(p)/s(p)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1116: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\Box$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1142: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$2+file\_size/536$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1158: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{table*}\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|}\hline
Trace & Clients & Total    & Total  & Hit  & Byte & Reduced & Reduced & Reduced \\  
      &         & Requests & GBytes & Rate &  HR  & Latency & Hops & WeightedHops\\  \hline
BU-272 & 5 & 17007 & 0.39 & 0.25 & 0.15 & 0.13 & 0.16 & 0.09 \\  \hline
BU-B19 & 32 & 118104 & 1.59 & 0.47 & 0.27 & 0.20 & 0.48 & 0.25 \\  \hline \hline
VT-BL & 59 & 53844 & 0.674 & 0.43 & 0.33 & - & 0.35 & 0.16 \\  \hline
VT-C  & 26 & 11250 & 0.159 & 0.45 & 0.38 & - & 0.33 & 0.15 \\  \hline
VT-G  & 26 & 47802 & 0.630 & 0.50 & 0.30 & - & 0.49 & 0.31 \\  \hline
VT-U  & 74 & 164160 & 2.30 & 0.46 & 0.33 & - & 0.40 & 0.25 \\  \hline \hline
DEC-U1:8/29-9/4 & 512 & 633881 & 9.21 & 0.42 & 0.35 & 0.24 & 0.34 & 0.25 \\  \hline
DEC-U1:9/5-9/11 & 512 & 691211 & 9.32 & 0.40 & 0.31 & 0.23 & 0.32 & 0.23 \\  \hline
DEC-U1:9/12-9/18 & 512 & 658166 & 9.23 & 0.39 & 0.31 & 0.19 & 0.39 & 0.32 \\  \hline
DEC-U1:9/19-9/22 & 512 & 280087 & 3.86 & 0.38 & 0.31 & 0.16 & 0.25 & 0.21 \\  \hline \hline
DEC-U2:8/29-9/4 & 1024 & 455858 & 5.57 & 0.33 & 0.22 & 0.20 & 0.27 & 0.19 \\  \hline
DEC-U2:9/5-9/11 & 1024 & 428719 & 5.13 & 0.30 & 0.21 & 0.18 & 0.25 & 0.16 \\  \hline
DEC-U2:9/12-9/18 & 1024 & 408503 & 4.94 & 0.29 & 0.19 & 0.15 & 0.24 & 0.17 \\  \hline
DEC-U2:9/19-9/22 & 1024 & 170397 & 2.00 & 0.26 & 0.19 & 0.15 & 0.17 & 0.11 \\  \hline \hline
\end{tabular}
\end{center}

\label{tab:inf}
\end{table*}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure*}\psfig{figure=graphs/gd/big-graph1.latex.ps}

\label{fig:graph1}
\end{figure*}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\le5\%$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1168: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure*}\psfig{figure=graphs/gd/big-graph2.latex.ps}

\label{fig:graph2}
\end{figure*}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$hops \times (2+file\_size/536)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1172: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
\stepcounter{section}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sim$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1174: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}

\end{document}