CDN: Content Distribution Network\thanks{Technical Report TR-125 of Experimental Computer Systems Lab in Stony Brook University.}
Gang Peng
Department of Computer Science
Stony Brook
NY 11794-4400.
\input{abstract}
abstract.tex
Internet evolves and operates largely without a central coordination,
the lack of which was and
is critically important to the rapid growth and evolution of Internet.
However, the
lack of management in turn makes it very difficult to guarantee
proper performance and to deal systematically with performance problems.
Meanwhile, the available network bandwidth and server capacity
continue to be overwhelmed by the skyrocketing Internet utilization and
the accelerating growth of bandwidth intensive content.
As a result, Internet service quality perceived 
by customers is largely unpredictable and unsatisfactory.
\emph{Content Distribution Network} (CDN) is an effective 
approach to improve Internet service quality.
CDN replicates the content from the
place of origin to the replica servers scattered over the Internet and serves
a request from a replica server close to where the request originates.
In this paper, we first give an overview about CDN.
We then present the critical issues involved in designing and
implementing an effective CDN and survey the approaches proposed in literature
to address these problems. An example of CDN is described to show how
a real commercial CDN operates. After this, we present a scheme that provides
fast service location for peer-to-peer systems,
a special type of CDN with no infrastructure support.
We conclude with a brief
projection about CDN.
\mycomment{We go on to propose a scheme to...}

%Background of CDN emerging
%Issues discussed in this article
%Web caching system
%General CDN architecture
%two key challenges of designing a CDN
%Issue we want to address

akamai.tex

\section{An Example of CDN -- Akamai}
Akamai \cite{Akamai} is one of the successful commercial CDNs, which hosts
some very popular websites, like Yahoo and Monster.com, and websites of many
big companies, like IBM and FedEx. \mycomment{However, Based on its' white
papers and some
papers published, we describe the conjecture on how Akamai works
as an representative instance of commercial CDNs,
although the details are not publicly
available as a business proprietary.}
By July 2002, Akamai has deployed more than 9,700 replica servers across 56
countries. These replica servers store the replication of the content for the
websites Akamai hosts. To achieve network diversity and proximity to users,
these replica servers sit in data centers and Points of Presence (POPs) of major
Internet and communication carriers. Akamai also built its own DNS network.
This Akamai DNS network
ensures fast delivery of the requested content by resolving the host name
of the URL for the requested content to the IP address of the Akamai replica
server that will deliver the desired content to the user most quickly.
Based on some white papers and published papers, we describe our conjectures on
two major processes involved in the operation of Akamai: one is how to direct
Internet traffic to the Akamai server network, another is how to direct
requests to the suitable Akamai replica servers.

\subsection{ARLs and Akamaizer}
Akamaizer is the tool that tags embedded Web objects for delivery via the Akamai
network, transforming ("akamaizing") their URLs into Akamai Resource Locators
(ARLs). ARLs contain a number of fields that aid in the content delivery
process. Their format is described in the following example.

A typical embedded object URL such as {\em http://www.foo.com/a.gif}
would be transformed into the following ARL:
\[http://a\overbrace{836}^\mathbf{\scriptscriptstyle Serial\,\#}.\overbrace{g.akamaitech.net}^\mathbf{\scriptscriptstyle Akamai\,Domain}/\overbrace{7}^\mathbf{\scriptscriptstyle Type}/\overbrace{836}^\mathbf{\scriptscriptstyle Serial\,\#}/\overbrace{123}^\mathbf{\scriptscriptstyle Provider\,Code}/\overbrace{e358f5db0045}^\mathbf{\scriptscriptstyle Object\,Data}/\overbrace{www.foo.com/a.gif}^\mathbf{\scriptscriptstyle absolute URL}\]
The {\em serial number} identifies a virtual "bucket" of content -- a group of
akamaized objects that will always be served from the same set of Akamai replica
servers. The {\em Akamai domain} ensures that requests for akamaized content
travel directly from the user to the Akamai network, completely avoiding the
object's origin site. The {\em type} field aids in interpreting an ARL. The
{\em provider code} uniquely identifies an Akamai customer.
The {\em object data} is used to guarantee object freshness. Depending on the
type in use, this field contains either the object's expiration time, or a 
string that uniquely identifies a particular version of the object, e.g., the
MD5 hash value of the object content. In the latter case, when the object is
modified, its object data field changes, so its ARL changes as well.
The last field {\em absolute URL} is used by Akamai replica servers to retrieve
the object from the content provider's origin site the first time the object
is requested.

\subsection{The Akamai DNS System}
All user requests for ARLs are directed to the Akamai network by the server
domain field (set to {\em g.akamai.net}) in each ARL. Then, the Akamai DNS
system chooses the Akamai replica server that will deliver the content to the
user most quickly and resolve the {\em *.g.akamai.net} server name using this
server's IP address. Unlike
the conventional DNS name resolution, this resolution relies not only on the
server name, but also on the source address of
the DNS query, current network condition and replica servers status.

The Akamai DNS system is implemented as a 2-level hierarchy of DNS servers:
by April 2000, 50 {\em high-level .akamai.net servers} (HLDNS) and 2000
{\em low-level .g.akamai.net servers} (LLDNS). Each HLDNS server is responsible
for directing each DNS query it receives to a LLDNS server that is close to
the requesting client. The LLDNS servers perform the final resolution of server
name to IP address, directing each client to the Akamai replica server
that is optimally located to serve the client's requests. As Akamai
continuously monitors network condition as well as the status of replica
servers, it can respond to network events within a matter of seconds.

When a browser makes a request for an ARL, whose server name is
{\em a9.g.akamai.net} for example, it first contacts its local DNS server,
asking it to resolve the server name. In the absence of a cached response, the
local DNS server resolves the server name by using iterative DNS queries. It
first contacts a {\em .net} root server, which responds with a list of Akamai
HLDNS servers. When the local DNS server contacts one of these HLDNS servers,
it receives
a list of LLDNS servers that are close to it. It then contacts one of the LLDNS
servers, which returns the IP address of the optimal replica server for this
request. Eventually, the local DNS server returns this IP address to the
requesting browser, which then fetches the content from that server.

The Akamai DNS system enables caching of DNS responses, just as in conventional
DNS name resolution, so as to avoid every request incurring the delay of three
levels of DNS queries. The Time-to-Live (TTL)
of the DNS responses are set in such a way
as to balance the benefits of caching with the chief goal of the Akamai DNS
system: keeping the client-to-server mapping
up to date with current network condition as well as replica servers status. As
the responses obtained from the root {\em .net} servers do not vary with
network conditions, they have a TTL of two days. The responses returned by
HLDNS servers are based on a network map that is recomputed every 7-10 minutes,
so these responses have a TTL of 20 minutes. Since LLDNS servers generate
name resolution based on maps that are updated every 2-10 seconds, the TTL 
in the responses from LLDNS servers is set to 20 seconds.

%DNS redirection
%Akamizer
%redirect requests at run-time
%freshness vs. overhead for DNS cache

%performance monitor

cdn.tex
\section{Overview}
%expect 4 pages
%What is CDN.
%Advantage compared with Web caching system.
%\cite{Baentsch}, Gemini

CDN distributes the contents from the origin server to
the replica servers close to the end clients. The replica servers in a CDN
store a very selective set of content and only the requests for that
set of content are served by the CDN so that the hit ratio can approach 100\%.
This fact implies that CDN can present short access delay and consume
less network bandwidth. In addition,
CDNs offer compelling benefits to content providers,
including the popular Web sites \cite{Gadde}.
This is because a CDN can
serve multiple content providers, and the shared resources offer economies of
scale and allow the CDN to dynamically adjust content placement, request
routing and capacity provisioning to respond to demand and network conditions 
\cite{Gadde, CDD101, Day1}.  Moreover,
the fact that many objects are not cacheable but replicable,
which include dynamic objects with read-only access and personalized objects 
(e.g., "cookied" requests), makes CDN
indispensable.

\subsection{A General Architecture of CDN} %1.2 page
\myfig{cdn_arch}{4.2 in}{System Architecture Components of a CDN}
The general architecture of a CDN system is shown in Figure
\ref{cdn_arch:fig}. It
consists of seven components:
\emph{client}, \emph{replica servers},
\emph{origin server}, \emph{billing organization}, \emph{request routing system},
\emph{distribution system} and \emph{accounting system}. The relationships among
these components are represented with the numbered lines in Figure
\ref{cdn_arch:fig} and are described as
follows \cite{Green, Day1}:
\begin{enumerate}
\item The \emph{origin server}
delegates its URI name space for document objects to be
distributed and delivered by the CDN to the \emph{request routing system}.
\item The \emph{origin server} publishes content that is to be distributed and
delivered by the CDN into the \emph{distribution system}.
\item The \emph{distribution system} moves content to replica servers.
In addition, this system interacts with the \emph{request routing system}
through feedback to assist in the \emph{replica server} selection process for 
\emph{client} requests.
\item The \emph{client} requests documents from what it perceives to be the
origin. However, due to URI name space delegation, the request is actually
directed to the \emph{request routing system}.
\item The \emph{request routing system} routes the request to a suitable
\emph{replica server} in CDN.
\item The selected \emph{replica server} delivers the requested
content to the \emph{client}. Additionally, the \emph{replica server} sends
accounting information for delivered content to the \emph{accounting system}.
\item The \emph{accounting system} aggregates and distills the accounting
information into statistics and content detail records for use by the 
\emph{origin server} and \emph{billing organization}.
Statistics are also used as
feedback to the \emph{request routing system}.
\item The \emph{billing organization} uses the content detail records to settle
with each of the parties involved in the content distribution and delivery
process.
\end{enumerate}

\mycomment{
One example of this architecture is the CDN of Akamai \cite{Akamai}.
When an end-user of
an Web application visits an {\em Akamaied} web site, the user's local
name server gets directed to the Akamai Domain Name Service (DNS). The Akamai
DNS then resolves the reference to the optimally located edge server. This
edge server assembles the relevant content based on the rules established in
the meta-data instructions that are stored locally. Static content is typically
retrieved from cache to be served to the browser. Dynamic content is either
assembled from page fragments stored in the cache, or retrieved from the
origin server via optimized communication methods. The page assembly
engine on the edge server then
assembles these fragments to be tailored and personalized to the user's
geographic location, cookie, device or other chosen mechanisms.
}

%\subsubsection{Requirements of CDN} %1 page
%\subsubsection{Desirable Properties of CDN} %1 page
%General requirements for each subsystems
%Focus on why the issues we study here are important to CDN.
%In the following several sections, discuss the solutions in detail.

%see {Green}
\mycomment{
\subsection{Content Distribution System} %1 page
%3 subsystems: replication, signaling and advertising.
%What does it do?
%Problems to solve. functional and performance.
Content distribution system in CDN is used to distribute the replicas
of the origin server's designated content to replica servers
that are spread over the 
Internet. It has to prevent replica servers from being overloaded. Some
mechanisms are necessary to keep all the content replica up to date, i.e.,
consistent with the master document in the origin servers. In addition,
content distribution propagates the meta-data information about the replica
contents on replica servers (i.e., replicas of what document are stored in
which replica servers) to the request routing system.
The request routing system uses
these meta-data information to direct the requests to the suitable
replica servers which
hold the desired document replica.

Two major problems in making content distribution system work
properly are as follows. }

\subsection{Distribution System}
%How many literature talk about this?
There are two dominating approaches to distribute content to replica servers:
using the Internet, and using broadcast satellite. Internet distribution
of content is simpler. In such an approach, a CDN establishes and maintains a
distribution tree or an overlay network over the existing Internet
infrastructure
and disseminates content from the origin server to the replica servers via the
tree or overlay. How to establish and maintain the
distribution overlay or tree is the major
technical concern. This approach might suffer from the unpredictability and
problematic performance of the Internet itself. Akamai Technologies and
Sandpiper
Networks use this model. Data satellite broadcast has the potential for
remarkable cost savings, and it provides a high-quality, predictable performance
path for sending critical content such as real-time streaming media.
The content distribution schemes in CyberStar and Edgix utilize
data satellite broadcast.

\subsection{Replica Placement}
Replica placement deals with
how many replicas each object has and where in the
network to place them.
This problem can be further divided into two issues:
replica server placement and object replica placement.
Replica server placement deals with the problem of placing the replica servers
on the Internet. Object replica placement is about on which replica
server and how to place a particular object replica, e.g., a web page.
%There are two major goals of placing replicas. First,
Intuitively, replica servers should be placed in such a manner that
they are \emph{closer} to the
clients, thereby reducing latency and bandwidth consumption. Also, object
replicas should be placed to even the load of the replica servers in CDN, that
is, trying to balance the load among replica servers \cite{Aggarwal}.

Some theoretical approaches are proposed to model the replica server placement
problem. These models are variations of or based on the
{\em center placement problem}. Due to the computational complexity of these
algorithms, heuristics have been developed. These suboptimal algorithms take
into account the existing information from CDN, such as the workload pattern
and the network topology. They provide sufficient solutions with less
computation cost.

Object replica placement has been well studied in Web caching system.
Korupolu et al. \cite{Korupolu1, Korupolu2} show that the cooperation between
caching nodes can improve the overall performance significantly.
For the object replica placement issue in CDN, Kangasharju et al. \cite{Kangasharju1} discussed a simple cost model and evaluated some heuristic approaches,
and proposed an improved heuristic exploiting the coordination between
replica servers. The essence of the work of Kangasharju et al.
is similar to the idea that Korupolu et al. present.

\mycomment{
More concretely, there are three issues in replica placement.
\begin{enumerate}
\item Which replica placement policy to choose, static replica placement or
dynamic replica placement? Static placement imposes less stringent requirements
for the request routing system. However, static placement is error prone, and
can become infeasible for large-scale system when the content get
changed frequently. On the other hand, dynamic replica
placement can adapt to large-scale system more easily.
\item What is the granularity of replication? Finer granularity imposes higher
overhead for collecting and maintaining access statistics and for placement
decision. Coarser granularity may increase the overhead for
disseminating objects to replica servers as. For example, if taking a site
as the unit to distribute content, some unpopular pages on a site may have to be
propagated to every replica server as the popular ones, which can be avoided
using finer content distribution granularity.
\item How to propagate replica placement information to the request routing
system in time? This problem is difficult to solve especially for the dynamic
placement policy because migration of objects among replica servers
may happen frequently and the database of storing the
location of replica objects used by the request routing system has to be kept
up-to-date accordingly.
\end{enumerate}
}

\subsection{Request Routing System} %1 page
Request routing system is used to select a suitable replica server that
holds the
copy of the requested content and direct the incoming requests to that server.
Proximity between the client and the selected replica server and the
replica server
load are the two major criteria used to choose a proper
replica server.

\paragraph{Server location}
The question of how to choose a suitable replica server within a CDN to service
a given request involves the following issues:
\begin{itemize}
\item Determine the distance between the requesting client and a server. 
Hop counts and round-trip times are two often used metrics to measure
the distance. ``ping" and ``traceroute" are the common tools to obtain these two
parameters.
However, neither of these two metrics is sufficient and accurate to 
indicate the proximity between the clients and the replica servers because
the former does not account for the network traffic situation and the latter
is highly variable.
\item Determine the load of a replica server.
The techniques widely used to determine
the server load are {\em server push} and {\em client probe}.
In the first technique, the replica
servers propagate the load information to some agents. In the 
second approach, the agents probe the status of the servers of interest
periodically. There is trade-off between the frequencies of probing for
accurate measurement and the traffic incurred by probing.
\end{itemize}

\paragraph{Request routing}
Many techniques have been used to guide clients to use a particular
server among a set of replica servers. In general, they can be classified into
five categories.
\begin{itemize}

\item {\em Client multiplexing}:
In this scheme, the client or a proxy server close to the client
receives the addresses of a set
of candidate replica servers and chooses one to send the request.
Generally, this scheme imposes additional overhead in sending the set of
candidate replica servers to the client when requesting some content. Also,
due to lack of overall information, the client may choose a server with high
load, which could result in overloading servers and hence larger access latency.

\item {\em HTTP redirection}:
%see {Fei, Guyton, Kangasharju}
This is simplest and probably the least efficient means of redirecting requests.
In
this scheme, requests for content make it all the way to the origin server, at
which point the server re-directs the browser to a new URL at the HTTP protocol
level. Because the origin server or server cluster is the only point responsible
for redirecting requests, it could become a bottleneck and is quite
error prone.

\item {\em DNS indirection}:
This scheme uses Domain Name System (DNS) modifications to return the IP address
of one of a set of replica servers when the DNS server is queried by the client.
Choosing a server may depend on the location of the client. This technique is
transparent to the client.
The quality of server selection can be improved by
taking into account the server performance. Some commercial CDNs, such as
Akamai, are taking this approach.
\mycomment{uses a round robin
mechanism to allocate servers to clients because it maintains no server
performance information on which to base its selection decision.
Additionally, 
DNS redirection does not scale well because it requires the world-wide clients
of a Web site, on a DNS cache miss, to incur the long round-trip time to a
centralized name server as part of accessing the site, from wherever the client
is located.}
\mycomment{
Additionally,
DNS redirection does not scale well because when the size of the system
grows,
it may take the clients a long round-trip time to a centralized name server
to resolve a site name on a DNS cache miss. }
\mycomment{
it requires the world-wide clients
of a Web site, on a DNS cache miss, to incur the long round-trip time to a
centralized name server as part of accessing the site, from wherever the client
is located. }

%see {Gritter, Adjie-Winoto}
\item {\em Anycasting}:
Essentially, request routing in CDN can be viewed as an application of locating
nearby copies of replicated Internet servers. Techniques such as anycasting
developed for server location can be used for request routing in CDN.
In this scheme, an \emph{anycast address/domain name}, which can be
an \emph{IP anycast address} or \emph{a URL of content}, is used to define a
group of servers that provide the same service. A client desiring to communicate
with only one of the servers sends packets with the anycast address in the
destination address field. The packet is then routed via anycast-aware
routers to at least one of the servers identified by the anycast address. This
anycast-aware routing can be integrated into the existing Internet routing
infrastructure, thereby providing request routing service to all the CDNs. In
addition, this scheme has the potential to scale up well with the growth of
the Internet.

\item{\em Peer-to-Peer Routing}:
Peer-to-peer systems are becoming widely deployed on the
Internet to disseminate content.
The participant nodes in a peer-to-peer system generally belong to different
affiliations and themselves constitute an ad-hoc network. As the network is
constantly changing, no nodes have the complete global information in time
about the network. The problem of routing requests efficiently in a distributed
manner without incurring high overhead of propagating the routing information is
a major research concern.

\end{itemize}

%For more detailed discussion, see "Rabinovich2".

%proximity probing is also a problem of request routing scheme.

cds.tex
%\section{Content Distribution in CDN}
\section{Server Placement}
%expect 5 - 6 pages
%Mainly about replica placement.

In this section, we
survey the approaches to server placement described in the literature along with
their contributions and inadequacies.
The issue here is to decide where on the Internet to place the servers,
which store replicates of objects.
The goal is to minimize the following two metrics:
the average content access latency perceived by clients and the
overall network bandwidth consumption for
transferring replicated documents from servers to clients. These two
are correlated in sense that optimizing one metric generally will
lead to the minimization of another one.

\subsection{Theoretical Approaches}
The server placement problem can be modeled as a
\emph{center placement problem}.
The center placement problem is defined as follows:
for the placement of a given number of centers, one
could consider the metric \((P_{minK})\) of minimizing the maximum
distance between a node and the nearest center.
This problem is also known as the {\em minimum K-center problem} \cite{Jamin}.
A problem
similar to the minimum K-center problem is the {\em facility location problem},
where the total cost in terms of building facilities and servicing clients
is a given constrain \cite{Qiu}.
Another theoretical approach to solve the center
placement problem based on graph theory is the
{\em k-hierarchically well-separated trees} (k-HST) \cite{Jamin, Bartal}.
We first define some notations
and then describe the k-HST and the  minimum $K$-center approaches.
\mycomment{After that,
the technique based on the facility location model is presented briefly
because of its similarity to the minimum $K$-center problem. }

\emph{Notations:} We adopt the following notations in this section: the network
is represented by a graph \(G(V,E)\), where \(V\) is the set of nodes, and
\(E \subseteq V \times V\) is the set of links. We use \(N=|V|\) to denote the 
number of nodes in $G$, and $\mathcal{T}$ to denote the number of centers we
place in the graph. We denote the distance between nodes \(u\) and \(v\) in the
graph $G$ by $d_{G}(u,v)$; we will omit $G$ when it can be deduced from the
context.

%\subparagraph{\emph{k}-HST}
\subsubsection{\emph{k}-HST}
The {\em k}-HST algorithm consists
of two phases. In the first phase, the graph is recursively partitioned as
follows. A node is arbitrarily selected from the current (parent) partition,
which is the complete graph at the beginning,
and all the nodes that are within a random radius from this node form a new 
(child) partition. The value of the radius of the child partition is a factor
of $k$ smaller than the diameter of the parent partition. This process recurs
for each partition, until each node is in a partition of its own. It then
obtains a tree of partitions with the root node being the entire network and
leaf nodes being individual nodes in the network. In the second phase, a virtual
node is assigned to each of the partitions at each level. Each virtual node in
a parent partition becomes the parent of the virtual nodes of the child
partitions. The length of the links from a virtual node to its children is
half of the partition diameter.
Together, the virtual nodes also form a tree.
Figure \ref{hst:fig} gives an example of generating a 1-HST tree based on
the algorithm described above from a graph. All the links on the graph
have the length of one.

\myfig{hst}{4.2 in}{Example of Generating {\em 1}-HST}

The randomization of a partition radius is done so that the probability of a 
short link being cut by partitioning decreases exponentially as one climbs the
tree. Hence nodes close together are more likely to be partitioned lower down
the tree. Taking advantage of this characteristics of the resulting $k$-HST
tree, the following greedy algorithm can be devised to find the number of
centers needed when the maximum center-node distance is bounded
by $\mathcal{D}$.

Let node $r$ be the root of the partition tree, $\mathcal{N}_{i}$ be the
children of node $i$ on the partition tree, and $\mathcal{L}$ be a list of
partitions sorted in the decreasing order of the partition diameter at all
times. $H_{\mathcal{L}}$ denotes the partition at the head of the list, and
$diam(H_{\mathcal{L}})$ its diameter. The following shows the greedy algorithm
on the $k$-HST tree.
{\tt
\\ $\mathcal{L} \leftarrow \mathcal{N}_{r}$ \\
while( $diam(H_{\mathcal{L}}) > \mathcal{D})$ \\
begin \\
\indent
$h \leftarrow H_{\mathcal{L}}$ \\
\indent
$\mathcal{L} \leftarrow \mathcal{L} - H_{\mathcal{L}}$ \\
\indent
$\mathcal{L} \leftarrow \mathcal{L} \cup \mathcal{N}_{h}$ \\
end \\
}
The algorithm pushes the centers down the tree until it discovers a partition
with diameter $\leq \mathcal{D}$. The number of partitions, $|\mathcal{L}|$, 
is the minimum number of centers required to satisfy the performance metric
$P_{diam}$. To select the actual centers, it simply needs to
set the virtual nodes of these partitions in $\mathcal{L}$ to be the centers.
Using the example of Figure \ref{hst:fig}, if we set $\mathcal{D}$ as $2$,
we will get the partition of $\{\{C,E,F,G\}, \{A,B,D\}\}$ after running the
above greedy algorithm. This result shows that if we need to ensure that the
distance between any single node and the closest server to be no greater than
two,
we have to deploy two servers with each located within node set $\{C,E,F,G\}$
and $\{A,B,D\}$, respectively.

The $k$-HST-based greedy placement algorithm presented above can not only
tell us the
number of centers needed to satisfy the performance metric $P_{diam}$,
but it can also be used to determine
their placement for any given budget of centers.
For example, to place $K$ centers, it simply needs to change
line 2 in the above algorithm with "while( $|\mathcal{L}| < K$ )".
Obviously, the performance metric $P_{diam}$ may no longer be satisfied
for $K$ below a certain number.

%\subparagraph{Minimum \emph{K}-center}
\subsubsection{Minimum \emph{K}-center}
The minimum $K$-center problem is NP-complete \cite{Garey}.
However, if we are willing
to tolerate inaccuracies within a factor of 2, i.e.,
the maximum distance between
a node and the nearest center being no worse than twice the maximum in the
optimal case, the problem is solvable in $O(N|E|)$ \cite{Vazirani} as follows.

Given a graph $G=(V,E)$ and all its edges arranged in non-decreasing order by
edge cost, $c: c(e_{1}) \leq c(e_{2}) \leq ... \leq c(e_{m})$, let
$G_{i} = (V,E_{i})$, where $E_{i} = \{ e_{1},e_{2},...e_{i}\}$. A {\em square
graph} of $G$, $G^{2}$ is the graph containing $V$ and edge $(u,v)$ wherever
there is a path between $u$ and $v$ in $G$ of at most two hops, $u \neq v$ ---
hence some edges in $G^{2}$ are pseudo edges, in that they do not exist in $G$.
An {\em independent set} of a graph $G=(V,E)$ is a subset $V' \subseteq V$ such
that, for all $u,v \in V'$, the edge $(u,v)$ is {\em not} in $E$. An independent
set of $G^{2}$ is thus a set of nodes in $G$ that are at least three hops apart
in $G$. We also define a {\em maximal} independent set $M$ as an independent
set $V'$ such that all nodes in $V - V'$ are at most one hop away from nodes
in $V'$.

The outline of the minimum $K$-center algorithm from \cite{Vazirani} is shown as
follows:
\begin{enumerate}
\item Construct $G_{1}^{2}$, $G_{2}^{2}$, ... ,$G_{m}^{2}$
\item Compute $M_{i}$ for each $G_{i}^{2}$
\item Find smallest $i$ such that $|M_{i}| \leq K$, say $j$
\item $M_{j}$ is the set of $K$ center.
\end{enumerate}

The basic observation is that the cost of the optimal solution to the $K$-center
problem is the cost of $e_{i}$, where $i$ is the smallest index such that
$G_{i}$ has a dominating set\footnote{A dominating set is a set of
$\mathcal{D}$ nodes such that every $v \in V$ is either in $\mathcal{D}$ or
has a neighbor in $\mathcal{D}$.} of size at most $K$. This is true since the
set of center nodes is a dominating set, and if $G_{i}$ has a dominating set
of size $K$, then choosing this set to be the centers guarantees that the
distance from a node to the nearest center is bounded by $e_{i}$. The second
observation is that a star topology in $G_{i}$ transfers into a clique 
(full-mesh) in $G_{i}^{2}$. Thus, a maximal independent set of size $K$ in
$G_{i}^{2}$ implies that there exists a set of $K$ stars in $G$, such that the
cost of each edge in it is bounded by $2e_{i}$: the smaller the $i$, the
larger the $K$. The solution to the minimum $K$-center problem is the
$G_{i}^{2}$ with $K$ stars. Note that this approximation does not always
yield a unique solution.

The 2-approximation minimum $K$-center algorithm can also be used to determine
the number of centers needed to satisfy the performance metric $P_{diam}$ by
picking an index $k$ such that $c(e_{k}) \leq \mathcal{D} / 2$. The maximum
distance between a node and the nearest center in $G_{k}$ is then at most
$\mathcal{D}$, and the number of centers needed is $|M_{k}|$.

%\subparagraph{Facility location problem}
\mycomment{
\subsubsection{Facility Location Problem}
Given a set of locations
at which facilities (centers) may be built, building a facility at location
\(i\) incurs a cost of \(f_{i}\). Each client \(j\) must be assigned to one
facility, incurring a cost of \(d_{j}d_{G}(i,j)\), where \(d_{j}\) denotes the
demand of the client \(j\). \mycomment{
and \(c_{ij}\) denotes the distance between \(i\) and
\(j\). }
The objective is to find a solution (i.e., both the number of facilities
and the locations of the facilities) of the minimum total cost.

There have been a number of approximation algorithms developed for this NP-hard
problem in the metric space. A \emph{$\rho$-approximation
algorithm} is a polynomial-time algorithm that always finds a feasible solution
with an objective function value within a factor $\rho$ of the optimal solution.
The best approximation algorithm known today was developed by Charikar and Guha 
\cite{Charikar}, who gave a 1.728-approximation algorithm. }

%\emph{}

\subsection{Heuristic Solutions}
%\paragraph{Heuristic solutions}
%why heuristic solutions

The theoretical solutions described above
are either computationally expensive or do not consider the characteristics
of the network and workload. Thereby, they are very difficult to apply in
practice \cite{Radoslavov} and may not be suitable for the real CDN systems.
Some heuristic or suboptimal algorithms were
proposed, which leverage some existing information from CDNs,
such as the work load pattern and the network topology 
\cite{Krishnan,Qiu,Jamin1,Radoslavov}, and offer adequate 
solution with much lower computation complexity.

%\subparagraph{Greedy algorithm}
\subsubsection{Greedy Algorithm}
A greedy algorithm was proposed by P. Krishnan et al. \cite{Krishnan} for the
cache location problem.
Qiu et al. \cite{Qiu} adapted this algorithm for the server placement problem in
CDN.

The basic idea of the greedy algorithm is as follows. Suppose it needs to choose
$M$ servers among $N$ potential sites. It chooses one site at a time. In
the first iteration, it evaluates each of the $N$ potential sites individually
to determine its suitability for hosting a server. It computes the cost
associated with each site under the assumption that accesses from all
clients converge at that site, and picks the site that yields the lowest cost,
e.g., the bandwidth consumption.
In the second iteration, it searches for a second site that, in
conjunction with the site already picked, yields the lowest cost. In general,
in computing the cost, the algorithm
assumes that clients direct their accesses to the 
nearest server, i.e., one that can be reached with the lowest cost.
The iteration continues until $M$ servers have been chosen.

Jamin et al. \cite{Jamin1} discussed a more general algorithm:
$\ell$-backtracking greedy algorithm. It differs from the basic one as
follows: in each iteration, the $\ell$-backtracking greedy algorithm
checks all the possible combinations achievable
by removing $l$ of the already placed servers and replacing them with
$\ell + 1$ new servers. Thus, the basic greedy algorithm is 
0-backtracking greedy algorithm.

%advantages:
%inadequacies:
In evaluating the relative performance of the greedy replica placement
strategy to that of the optimal ones, Qiu et al. \cite{Qiu}
extracted the client locations from the workload
traces from MSNBC, ClarkNet and NASA Kennedy
and reduced the number of the locations to the scale of thousands 
by clustering the clients that
are topologically close together. They utilized two types of network topologies:
one by simulating the network as random graph and another one by
deriving the real topology
from BGP routing table. Under this experimental configuration, 
the greedy algorithm
performs remarkably well (within a factor of 1.1-1.5) 
compared to the computationally expensive optimal solution and the computation
needed is several magnitudes less.
Also, the greedy algorithm is relatively insensitive to imperfect input data.
Unfortunately, this greedy placement requires knowledge of the client
locations in the network and all pairwise inter-node distances. This
information in many cases may not be available.

%\subparagraph{Topology-informed placement strategy}
\subsubsection{Topology-informed Placement Strategy}
A topology-informed placement strategy, called "Transit Node",
was first discussed by Jamin et al. \cite{Jamin1}. It works as follows.
Assuming that nodes with the highest outdegrees\footnote{The outdegree of a node
is the number of other nodes it is connected to.} can reach more nodes with
smaller latency, we place servers on candidate hosts in descending
order of outdegrees. This is called \emph{Transit Node} heuristic under the
assumption that nodes in the core of the Internet transit points will
have the highest outdegrees. \mycomment{Their result shows that the
transit node heuristic can perform almost as well as the greedy placement.
However,} Due to the lack of more detailed network topology, it uses only
Autonomous Systems (AS) topologies where each node represents a single AS, and
node link corresponds to AS-level BGP peering.
An improved topology-informed placement strategy is proposed by Radoslavov et
al \cite{Radoslavov}. They leverage the router-level Internet topology, instead
of only AS-level topology. In this strategy, each LAN associated with a router
is a potential site to place a server, rather than each AS being a site.
\mycomment{
Their finding shows that using router-level topology information results in
better performance than that achieved by only exploiting AS-level topology
knowledge.}

%pro and con
\mycomment{
Compared to the greedy algorithm, the topology-informed placement strategy
does not need the detailed knowledge of the network topology and
the expected client locations on the topology, and can achieve similar
performance result as the greedy algorithm does.
}

In the experiments of both strategies,
the network topology is extracted from the Internet and
the set of client locations is derived from some Web site trace log.
The result shows that the
transit node heuristic can perform almost as well as the greedy placement,
and that using router-level topology information results in
better performance than that achieved by only exploiting AS-level topology
knowledge. Also, they found that the performance improvement diminishes
when increasing the number of the servers and only explored
the performance of up to tens of servers.

In practice, due to the capacity
limit of a single site, a CDN may consist of much more servers, e.g.,
Akamai deploys around 13,000 servers in 64 countries \cite{Akamai}. To
the best of our knowledge, the problem of optimizing the placement of
such a large number 
of servers on the Internet is not well explored.

conclude.tex
\section{Summary}

%outline of this paper.
With the increasing use of the Internet for content distribution,
caching and replication techniques are receiving more and more attention.
These are effective approaches to alleviate 
congestion on the Internet and to make the Internet more responsive. With many
unique features, CDN renders appreciable benefits to the content providers,
e.g., the popular web sites. In this report,
we studied the core challenging issues involved in
designing and building efficient CDNs, especially the content distribution
and request routing problems. A scheme for fast service location in peer-to-peer
systems is proposed.

%trend about the future research
Nowadays, new forms of Internet content and services, 
such as video-on-demand, which requires intensive bandwidth and predictable 
data transmission delay, are emerging. Meanwhile, the number
of content providers turning to CDNs to better service their customers is
growing rapidly. These two facts open several new issues to the 
design and architecture of CDNs in the future,
such as support for streaming content or real-time events,
scalability, built-in security mechanism, and so forth.
The research
on these issues are still undergoing and we believe that the successful
solutions to these problems will make the next-generation CDNs fly.

%

dht.tex

\section{Iridium: A Fast Content Location Service for Large-Scale Peer-to-Peer Systems}

\subsection{Related Work}
The present routing protocols or services in peer-to-peer systems can be
roughly classified into three categories according to the number of nodes
performing the routing operation. 
\begin{itemize}
\item The first category relies on a central
node for servicing all the routing requests in the system. Napster
\cite{Napster} and Audiogalaxy \cite{Audiogalaxy}
are the instances. Obviously, this centralized
structure can not scale well for large system and is error prone. A more
significant demerit of this structure is that the system using this routing
structure can be easily censored. The suspension of Napster shows this defect.
\item Some peer-to-peer systems
choose a small set of ``superpeers" or ``supernodes" by consensus to
service the routing requests in the system rather than replying on a central
node for routing.  Kazaa/Fasttrack \cite{Kazaa},
WinMx \cite{WinMx} and edonkey2000 \cite{edonkey2000} take this
approach. Gnutella \cite{Gnutella} also
has a slightly structured network for routing requests
but delivers requests in an expanding search, which incurs enormous
amount of search traffic. Fast content location generally is not an explicit
concern in these systems.
\item Tapestry \cite{zhao01tapestry}, CAN \cite{ratnasamy01scalable},
Chord \cite{Stoica} and Pastry \cite{rowstron01pastry}
constitute the peer-to-peer system in a completely
distributed structure where each node participates in the routing procedure.
They distribute the routing
information on each node. Each node maintains information only about $O(logN)$
\footnote{$N$ is the total number of nodes in the system.}
other nodes, and a request requires $O(logN)$ overlay hops to complete.
These systems
achieve the excellent scalability at the cost of large lookup latency. This
issue becomes worse in practice as each overlay hop
could take very long time, especially when
the physical path between the source and the sink of a hop is congested.
Brocade \cite{zhao02brocade} improves over Tapestry on this issue
by shortcutting the lookup messages through some
selected ``supernodes" which have high bandwidth and fast access to
the wide-area
network. However, it will still take $O(logN)$ overlay hops to finish a request.
\end{itemize}
To address the large lookup latency issue of Tapestry etc. have,
the proposed system in Iridium constructs
a routing fabric consisting of a set of ``supernodes".
The system is divided into multiple partitions each consisting of a supernode
and a set of regular nodes. Using consistent hashing \cite{karger97consistent},
the routing fabric takes constant time to find out which partition
stores the key being requested and service the request.
In the meanwhile, the routing system in Iridium scales well
as the routing operations are conducted in a distributed manner.

\subsection{System Structure}
Essentially, Iridium provides distributed computation of a hash function
mapping keys to nodes responsible for them within constant time. It uses
consistent hashing \cite{karger97consistent},
which has several good properties. With high
probability the hash function balances load. Also with high probability,
when an $N^{th}$ node joins (or leaves) the network, only an $O(1/N)$ fraction
of the keys are moved to a different location.

The consistent hash function assigns each node and key an $m$-bit $identifier$
using a base hash function such as SHA-1 \cite{sha}.
A node's identifier is chosen
by hashing the node's IP address, while a key identifier is calculated by
hashing the key. We will use the term ``key" to refer to
both the original key and
its identifier. Similarly, the term ``node" will refer to both the node and its
identifier under the hash function.

\mycomment{
There are two types of nodes in Iridium: {\em supernode} and {\em regular node}.
A supernode performs the functionality of regular nodes as well.
Consistent hashing assigns the keys to the regular nodes and the nodes to
the supernodes. Supernodes also store the IP addresses of all the supernodes.
In concrete, all the identifiers are ordered in an {\em identifier circle}
modulo $2^m$. Key $k$ is assigned to the first regular node whose identifier is
equal to or follows $k$ in the identifier space.
This regular node is called the {\em successor node} of key $k$. Similarly,
node $n$ is assigned to the first supernode whose identifier is equal to or
follows $n$ in the supernode identifier space. This supernode is called the {\em
associated supernode} of node $n$.
Correspondingly, we call the regular nodes
which are associated with supernode $s$ the {\em bound set} of $s$, denoted as
$b(s)$. To enhance
the reliability, a key $k$ is stored in its successor node
and the $p-1$ regular nodes that follow key $k$'s successor node immediately.
These $p$ regular nodes together we call
them the key $k$'s {\em successor node set}.\mycomment{, denoted as $S(k)$}
Similarly, a node $n$ is assigned to its associated supernode and the
$q-1$ supernodes that follow node $n$'s associated supernode immediately.
We name these $q$ supernodes the node $n$'s {\em associated supernode set}
\mycomment{, denoted as $A(n)$}.
Here $p$ and $q$ are
tunable system parameters.
Supposing the total number of nodes in the system is $N$, we
denote the number of supernodes as $f(N)$ and
the average number of nodes each supernode
stores as $B(N)$, where $B(N)$ is equal to $q * N / f(N)$.}

There are two types of nodes in Iridium: {\em supernode} and {\em regular node}.
\begin{itemize}
\item Regular nodes store the keys.
The keys are assigned by using the consistent
hashing as follows: All the identifiers are ordered in an
{\em identifier circle} modulo $2^m$. Key $k$ is assigned to the first regular
node whose identifier is equal to or follows $k$ in the identifier space. This
regular node is called the {\em successor node} of key $k$.
\item Supernodes store the node identifiers assigned by consistent hashing.
A node $n$ is assigned to the first supernode whose identifier is equal to
or follows $n$ in the supernode identifier space. This supernode is called the
{\em associated supernode} of node $n$. Correspondingly, we call the regular
nodes that are associated with supernode $s$ the {\em bound set} of $s$, denoted
as $b(s)$. A supernode performs the functionality of regular nodes as well.
\end{itemize}
To enhance the reliability, a key $k$ is stored in its successor node
and the $p-1$ regular nodes that follow key $k$'s successor node immediately.
These $p$ regular nodes together we call them the key $k$'s
{\em successor node set}. Similarly,
a node $n$ is assigned to its associated supernode and the
$q-1$ supernodes that follow node $n$'s associated supernode immediately.
We name these $q$ supernodes the node $n$'s {\em associated supernode set}.
Here $p$ and $q$ are tunable system parameters.
Supposing the total number of nodes in the system is $N$, we
denote the number of supernodes as $f(N)$ and
the average number of nodes each supernode
stores as $B(N)$, where $B(N)$ is equal to $q * N / f(N)$.

\myfig{iridium}{1.9 in}
{An identifier circle consisting of the six nodes $0$, $2$,
$4$, $8$, $10$ and $11$. In them, node $2$, $8$ and $12$ are regular nodes and
node $0$, $4$ and $10$ are supernodes. Regular node $12$ is assigned to
supernode $0$, $2$ to $4$ and $8$ to $10$. Key $1$ is assigned to node $2$,
key $6$ to node $8$, key $9$ to node $10$ and key $11$ to node $12$.}

When a node $i$ is looking for a key $k$, it first randomly selects one
supernode, say $I$, from its associated supernode set to send a query to
asking for the location of key $k$. Supernode $I$ checks which supernode is
the clockwise closest supernode to key $k$ in the identifier space and
forwards the query to that supernode, say $J$.
Supernode $J$ then looks up which regular nodes in its bound set are holding
$k$ and
randomly chooses one, say $j$,
to deliver the query to. After finding the desired
key, the result will be sent back from $j$ to $J$, then $I$ and eventually
$i$. In total, each key lookup involves only constant number of hops.
For example, in Figure \ref{iridium:fig}, when node $2$ looks up for key $6$,
it first sends a query
to its associated supernode $4$. Supernode $4$ then sends this query to
supernode $10$, which is the clockwise closest supernode to key $6$ in the
identifier space. Supernode $10$ furthers 
the query to regular node $8$, which is the successor node of key $6$ and
stores the key $6$. Eventually, node $8$
sends the result through node $10$, $4$ back to the requesting node $2$.

\subsection{System Maintenance}

\subsubsection{Node Joins}
When a node wants to join the peer-to-peer system,
it needs to find out its associated
supernode first. It does this by flooding or broadcasting request looking for
a supernode to its topological neighbors. Once it gets the location of a
supernode, it queries the supernode for its associated supernode set.
After that,
it registers itself to its associated supernode set
by sending information to these supernodes including its identifier and address.

\subsubsection{Supernode Selection}
When the number of nodes in the system exceeds certain threshold or the routing
core consisting of the supernodes is overloaded,
we need to select new supernodes out of the regular nodes
to shed the workload.

First we determine the supernode from whose bound set to
choose a supernode candidate. The supernode could be the most loaded one or
the one having the largest bound set.
We then select a supernode candidate from the bound set.
We account the computation resources, including memory and CPU, and the
average up time when choosing a candidate. The time complexity of selecting
candidate is $B(N)$ if we search the bound set linearly
as each supernode will hold around $B(N)$
regular nodes. It could be optimized to constant time if each
supernode keeps its bound set sorted.
After a new supernode is selected, its previous associated supernode migrates
the regular nodes whose closest successor supernode becomes the
new supernode to the newly selected supernode.
\mycomment{This process could be done by sending one message in constant time.}
The next operation is to propagate the existence of this new supernode to other
supernodes. The simplest way to do this is to do broadcasting, which requires 
$f(N)$ messages for each supernode birth. This work could be optimized by
using lazy update. If a supernode needs to lookup some keys which are held by
certain regular nodes which
are in the bound set of the new supernode, it queries the old associated
supernode of the new supernode first. Besides forwarding the query to the
new supernode, the old associated supernode of the new supernode will sends
back response including the information about the new supernode to the
requesting supernode so that the information about the new supernode is
delivered to the interested supernodes gradually.

\subsubsection{Node Leaves}
Iridium handles the node leaving or death for supernodes and regular nodes in
different ways.
Normally, a regular node updates its identifier and address stored in its
associated supernode set either by explicitly sending message to its
associated supernode set periodically or attaching these information into the
query messages. The supernode simply
cache these information constructing the bound set. When a regular
node leaves, it notifies its associated supernode set its exit
so that the supernodes
can update their bound set. It also needs to migrate the keys
it stores to its successor node. When a regular node dies, its associated
supernode set will detect its death
by the timeout of the corresponding regular node information.
\mycomment{However, the keys stored on the dead node may get lost and we presume
the application utilizing the routing service has some mechanism to handle
this exception.}

It is more sophisticated to handle the leaving of supernodes as more information
need to be migrated or updated when a supernode leaves or dies compared to what we do in case of regular node leaving. Basically, when a supernode leaves,
it will
migrate its bound set to its living successor supernode. Also, it has to
tell the regular nodes to add one more successor
supernode to their associated supernode set to keep the size of the set
constant. To avoid the possible high instant traffic due to this operation,
each regular
node in the bound set of the leaving supernode waits for a random short period
before executing this operation.
\mycomment{The second operation will incur high instant traffic.
We alleviate
this problem by letting each regular node associate itself with a set of
successor
supernodes instead of just its closest successor supernode. We call this set
the regular node's {\em associated supernode set} and its closest successor
supernode its {\em private supernode}. This implies that the index
information of each regular node is replicated in several supernodes. This
replication will make the service more fault-tolerant, which we will discuss
further in the next subsection.}

When a supernode dies, other nodes could not notice
this event right at that moment. One straightforward approach to help the living
nodes detect the death of a supernode is to let each supernode broadcasts its
own identifier and address to other nodes periodically.
Obviously, this will incur too much traffic over the
Internet. For this reason, we take a lazy update approach to help detect the
death of a supernode but avoid the unnecessary message transmission.
This approach works as follows. After a supernode dies,
as the living supernodes do not know about its death,
they will forward the requests
for the key held by the bound set of the dead supernode to the dead supernode
as if it was alive. These requests will eventually timeout and as a result,
the living
supernodes forwarding the requests will find out that one supernode is down and
update their supernode information
accordingly. The same approach can be used by the regular nodes in the bound set
of the dead supernode to update their own associated supernode sets.
They send requests to the dead supernode as usual but
detect the death of their associated supernode by timeout.
Once they are aware of the death of their previous associated supernode,
they add one more successor supernode to their
associated supernode sets.
\mycomment{Once they are aware
of the death, they select the closest living successor supernode from their
associated supernode set as the new private supernode.} In this approach,
broadcasting the information of supernodes is avoided and also we do not need to
send the information about a supernode to the nodes that are not interested.

%\subsection{Enhance Reliability}
%\subsection{Enhance Reliability}
\subsection{Some Issues}

%rewrite to explain how to replicating content information on multiple
%supernodes in order to improve the reliability. The queries could also
%be shouldered on the replications. some timeout mechanisms. (???)
\paragraph {Reliability} 
When a regular node dies, the keys held by this node will lose.
Similarly, if a supernode dies, we lose information about the bound set of
this supernode. As a result of these information losing, the query will
be disrupted.
To guarantee the success of queries, we replicate information needed for
forwarding queries. In concrete, each key is replicated in
$p$ regular nodes. The queries for a key are almost equally shared by the
regular nodes holding the key. Similarly,
each regular node is associated with $q$ supernodes and anyone of these
supernodes has the same probability to
forward the query to or from the regular node.
To determine which values $p$ and $q$ should be so as to 
achieving an appropriate trade-off between reliability and scalability,
a simulation study is necessary.

\mycomment{
We think that the lost of regular node index is more serious than the lost of
content keys. The latter case could be handled by the application running on the
overlay. In order to reduce the probability of occurrence of the former case, we
should set some criteria, like reliability or average up time of the nodes,
when selecting supernodes. Supposing the probability of supernode failure is
$1/10$, which is a reasonable assumption given the supernode selection
procedure,
the probability of query failure due to supernode death is $10^{-q}$. When we
set $q$ to $8$, the probability of query being successful is $99.999999\%$. This
is satisfactory in practice. }

\mycomment{
As a query can only fail when either all the copies of the required content key
are gone or all the supernodes holding the index of the successor node list of
the required key are down. Taking the bigger of $p$ and $q$ as $r$, if the
probability of failure of one node is $1/2$, the probability of one query
failure is $2^{-r}$. When $r$ is $10$, which is a reasonable value,
the probability of query being success is $1023/1024$, which is bigger than
$99.9\%$. 
}

\mycomment{
\subsubsection{Recovery from Failure}
We think that the failure is inevitable even we replicate the information
necessary for routing to reasonably large extent. In case of node failure,
one question we need to answer to ensure a query would go through eventually is:
can we reconstruct the information when all the replication of one piece of
information are gone ?

The answer is yes.}

%\subsection{Scalability}
\paragraph {Scalability}
Unlike Tapestry etc., where each node participates in routing operation,
in Iridium, the routing work is taken by a limited set of supernodes.
As a result, Iridium may not scale as well as Tapestry etc. do.
One possible reason for this is the space each supernode has is limited.
However, to
be a first approximation, supposing $N$ is $10^7$, $f(N)$ chosen as
$N^{1/2}$, $q$ as $10$ and
each node information needs 12 bytes (6 bytes for IP address and 6 for
identifier), each supernode needs only about 760 KB to store the whole
bound set as well as the information about all the supernodes.
This amount of resource is
negligible in practice. Another issue which could possibly prevent
Iridium from scaling 
in practice is the amount of extra traffic supernodes may incur,
which includes the messages for routing and for maintenance of the system. To
answer this question, we need to perform extensive simulation study
under different functions of $f(N)$. On the other hand, regular routing load
is reduced heavily helping scalability.

\subsection{Summary}
%what current situation is?
%what weakness we want to address?
%what weakness our proposal has? mention well-known problems our proposal has.
%what are the possible solutions to them? what for the unsolved ones?
In summary, Iridium is designed to provide fast content location service for
large-scale
peer-to-peer systems. As the design shows, the routing work is taken by a
set of supernodes leveraging consistent hashing and
a lookup can be done within constant time. We need to perform
extensive simulation experiments to study the scalability and reliability of
Iridium under various setups and scenarios.

intro.tex
\section {Introduction}

Over the past several years, the Internet has effectuated 
serious changes in how we transact business. For most businesses,
the performance
of Web connections has a direct impact on their profitability.
Although the time to
load the content of key Internet sites has improved constantly over the last
several years, overall Web content access latency is still in the range of
a few seconds, which is several times the
threshold believed to represent
natural human reading/scanning speeds. One might think that the constant
improvement in the bandwidth of Internet infrastructure, for example, the
availability of high-speed
"last mile" connection of the subscribers to the Internet and the backbone
fibers,
and the increasing capacity of the various servers would reduce or eliminate
the access
delay problem eventually.
However, the reality is quite the opposite. Even with these
improvements, users still suffer from very significant access delays.

The poor Internet service quality, typically represented as the long content
delivery delay, is primarily
due to two phenomena. The first is the lack
of overall management for Internet. Although the fact that the Internet evolves
and operates largely without central supervision was and is critically
important to the rapid growth and change,
the absence of overall administration in turn
makes it very difficult to guarantee proper performance and deal systematically
with performance problems. The second is that as the
load on Internet and the richness of its content continue to soar, any
increase in available network bandwidth and server capacity will
continue to be overwhelmed. These two facts not only elevate the delay in 
accessing content on Internet, but also make the access latency unpredictable.
With the emergence of new forms of Internet content, such as media
streams, the Internet performance problem will become even worse because
the fluctuation and irregularity of the access delay
will have a serious impact on the quality of the
streaming content that the customer perceives \cite{Gadde}.

The basic approach to address the performance problem is to
move the content from the
places of origin servers to the places at the edge of the Internet.
Serving content from a local replica server typically has better performance 
(lower access latency, higher transfer rate) than from
the origin server, and using multiple replica servers for servicing requests
costs less than using only the data communications network does.
CDN takes precisely this approach. In concrete, CDN
replicates a very selective set of content to the replica servers and
only sends those requests for the replicated content to a replica server.
\mycomment{Both Web caching system and CDN are the applications of using storage
to replicate content as a
means to accelerate Internet performance. They are complementary
in functionality to each other.
In Web caching system, the cache sees all requests from the
community of users served by the cache. The benefit from such a cache derives
from the commonality of Internet access within the
community -- the cache provides benefits if the requested object has already
been requested recently. In such an application, a cache demonstrates a
"hit ratio" on the order of 40\% \cite{CDD101, Abrams}. In contrast, CDN
replicates a very selective set of content to the replica servers and
only sends those requests for the replicated content to a replica server
so that all
requests hit. This higher hit ratio implies better performance of serving
requests compared to that using Web caching system solely.}
How to place replica servers and distribute content copies to replica servers
and how to route
the requests to the proper replica server having the desired content
are the key challenges in designing an
effective CDN, and are the major topics we will discuss.

The rest of the paper is organized as following: Section 2 gives an overview
about CDN, including the general CDN architecture and
the issues to be addressed in constructing a capable CDN.
In Section 3, we
describe the issues involved in replica placement in CDN and
compare some representative strategies.
We then proceed to Section 4, which discusses the problems we need to solve
for request routing and survey effective approaches proposed in literature to
resolve them.\mycomment{
as well as correlation between the content distribution and the
request routing.}
\mycomment{ Section 5 proposes a scheme... Section 6 Section 5 discusses
correlation between the content distribution and the request routing.}
Section 5 describes how a commercial CDN works and Section 6 presents a
request routing scheme for fast service location in
large-scale peer-to-peer systems.
We conclude in Section 6 with a brief projection about CDN.

%Comments for this article
%Issue of current Internet infrastructure:
%Bandwidth improvement lags behind increasing demand.
%No centralized supervision on Internet.
%Two effects:
%Long delay loading home pages.
%Big variation of content loading time due to unexpected congestion on some key points of Internet, which has very seriously impact on the quality of stream content perceived by the customers.
%Traditional Web Cache uses passive fashion trying to address the issue.
%Shortcomings of Web Cache ... (see reference)
%CDN (see [GCR00] [CDD]), supplementary to Web caching system
%Organization of this paper

psfig.tex
% Psfig/TeX 
\def\PsfigVersion{1.9}
% dvips version
%
% All psfig/tex software, documentation, and related files
% in this distribution of psfig/tex are 
% Copyright 1987, 1988, 1991 Trevor J. Darrell
%
% Permission is granted for use and non-profit distribution of psfig/tex 
% providing that this notice is clearly maintained. The right to
% distribute any portion of psfig/tex for profit or as part of any commercial
% product is specifically reserved for the author(s) of that portion.
%
% *** Feel free to make local modifications of psfig as you wish,
% *** but DO NOT post any changed or modified versions of ``psfig''
% *** directly to the net. Send them to me and I'll try to incorporate
% *** them into future versions. If you want to take the psfig code 
% *** and make a new program (subject to the copyright above), distribute it, 
% *** (and maintain it) that's fine, just don't call it psfig.
%
% Bugs and improvements to trevor@media.mit.edu.
%
% Thanks to Greg Hager (GDH) and Ned Batchelder for their contributions
% to the original version of this project.
%
% Modified by J. Daniel Smith on 9 October 1990 to accept the
% %%BoundingBox: comment with or without a space after the colon.  Stole
% file reading code from Tom Rokicki's EPSF.TEX file (see below).
%
% More modifications by J. Daniel Smith on 29 March 1991 to allow the
% the included PostScript figure to be rotated.  The amount of
% rotation is specified by the "angle=" parameter of the \psfig command.
%
% Modified by Robert Russell on June 25, 1991 to allow users to specify
% .ps filenames which don't yet exist, provided they explicitly provide
% boundingbox information via the \psfig command. Note: This will only work
% if the "file=" parameter follows all four "bb???=" parameters in the
% command. This is due to the order in which psfig interprets these params.
%
%  3 Jul 1991	JDS	check if file already read in once
%  4 Sep 1991	JDS	fixed incorrect computation of rotated
%			bounding box
% 25 Sep 1991	GVR	expanded synopsis of \psfig
% 14 Oct 1991	JDS	\fbox code from LaTeX so \psdraft works with TeX
%			changed \typeout to \ps@typeout
% 17 Oct 1991	JDS	added \psscalefirst and \psrotatefirst
%

% From: gvr@cs.brown.edu (George V. Reilly)
%
% \psdraft	draws an outline box, but doesn't include the figure
%		in the DVI file.  Useful for previewing.
%
% \psfull	includes the figure in the DVI file (default).
%
% \psscalefirst width= or height= specifies the size of the figure
% 		before rotation.
% \psrotatefirst (default) width= or height= specifies the size of the
% 		 figure after rotation.  Asymetric figures will
% 		 appear to shrink.
%
% \psfigurepath#1	sets the path to search for the figure
%
% \psfig
% usage: \psfig{file=, figure=, height=, width=,
%			bbllx=, bblly=, bburx=, bbury=,
%			rheight=, rwidth=, clip=, angle=, silent=}
%
%	"file" is the filename.  If no path name is specified and the
%		file is not found in the current directory,
%		it will be looked for in directory \psfigurepath.
%	"figure" is a synonym for "file".
%	By default, the width and height of the figure are taken from
%		the BoundingBox of the figure.
%	If "width" is specified, the figure is scaled so that it has
%		the specified width.  Its height changes proportionately.
%	If "height" is specified, the figure is scaled so that it has
%		the specified height.  Its width changes proportionately.
%	If both "width" and "height" are specified, the figure is scaled
%		anamorphically.
%	"bbllx", "bblly", "bburx", and "bbury" control the PostScript
%		BoundingBox.  If these four values are specified
%               *before* the "file" option, the PSFIG will not try to
%               open the PostScript file.
%	"rheight" and "rwidth" are the reserved height and width
%		of the figure, i.e., how big TeX actually thinks
%		the figure is.  They default to "width" and "height".
%	The "clip" option ensures that no portion of the figure will
%		appear outside its BoundingBox.  "clip=" is a switch and
%		takes no value, but the `=' must be present.
%	The "angle" option specifies the angle of rotation (degrees, ccw).
%	The "silent" option makes \psfig work silently.
%

% check to see if macros already loaded in (maybe some other file says
% "\input psfig") ...
\ifx\undefined\psfig\else\endinput\fi

%
% from a suggestion by eijkhout@csrd.uiuc.edu to allow
% loading as a style file. Changed to avoid problems
% with amstex per suggestion by jbence@math.ucla.edu

\let\LaTeXAtSign=\@
\let\@=\relax
\edef\psfigRestoreAt{\catcode`\@=\number\catcode`@\relax}
%\edef\psfigRestoreAt{\catcode`@=\number\catcode`@\relax}
\catcode`\@=11\relax
\newwrite\@unused
\def\ps@typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}
\ps@typeout{psfig/tex \PsfigVersion}

%% Here's how you define your figure path.  Should be set up with null
%% default and a user useable definition.

\def\figurepath{./}
\def\psfigurepath#1{\edef\figurepath{#1}}

%
% @psdo control structure -- similar to Latex @for.
% I redefined these with different names so that psfig can
% be used with TeX as well as LaTeX, and so that it will not 
% be vunerable to future changes in LaTeX's internal
% control structure,
%
\def\@nnil{\@nil}
\def\@empty{}
\def\@psdonoop#1\@@#2#3{}
\def\@psdo#1:=#2\do#3{\edef\@psdotmp{#2}\ifx\@psdotmp\@empty \else
    \expandafter\@psdoloop#2,\@nil,\@nil\@@#1{#3}\fi}
\def\@psdoloop#1,#2,#3\@@#4#5{\def#4{#1}\ifx #4\@nnil \else
       #5\def#4{#2}\ifx #4\@nnil \else#5\@ipsdoloop #3\@@#4{#5}\fi\fi}
\def\@ipsdoloop#1,#2\@@#3#4{\def#3{#1}\ifx #3\@nnil 
       \let\@nextwhile=\@psdonoop \else
      #4\relax\let\@nextwhile=\@ipsdoloop\fi\@nextwhile#2\@@#3{#4}}
\def\@tpsdo#1:=#2\do#3{\xdef\@psdotmp{#2}\ifx\@psdotmp\@empty \else
    \@tpsdoloop#2\@nil\@nil\@@#1{#3}\fi}
\def\@tpsdoloop#1#2\@@#3#4{\def#3{#1}\ifx #3\@nnil 
       \let\@nextwhile=\@psdonoop \else
      #4\relax\let\@nextwhile=\@tpsdoloop\fi\@nextwhile#2\@@#3{#4}}
% 
% \fbox is defined in latex.tex; so if \fbox is undefined, assume that
% we are not in LaTeX.
% Perhaps this could be done better???
\ifx\undefined\fbox
% \fbox code from modified slightly from LaTeX
\newdimen\fboxrule
\newdimen\fboxsep
\newdimen\ps@tempdima
\newbox\ps@tempboxa
\fboxsep = 3pt
\fboxrule = .4pt
\long\def\fbox#1{\leavevmode\setbox\ps@tempboxa\hbox{#1}\ps@tempdima\fboxrule
    \advance\ps@tempdima \fboxsep \advance\ps@tempdima \dp\ps@tempboxa
   \hbox{\lower \ps@tempdima\hbox
  {\vbox{\hrule height \fboxrule
          \hbox{\vrule width \fboxrule \hskip\fboxsep
          \vbox{\vskip\fboxsep \box\ps@tempboxa\vskip\fboxsep}\hskip 
                 \fboxsep\vrule width \fboxrule}
                 \hrule height \fboxrule}}}}
\fi
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% file reading stuff from epsf.tex
%   EPSF.TEX macro file:
%   Written by Tomas Rokicki of Radical Eye Software, 29 Mar 1989.
%   Revised by Don Knuth, 3 Jan 1990.
%   Revised by Tomas Rokicki to accept bounding boxes with no
%      space after the colon, 18 Jul 1990.
%   Portions modified/removed for use in PSFIG package by
%      J. Daniel Smith, 9 October 1990.
%
\newread\ps@stream
\newif\ifnot@eof       % continue looking for the bounding box?
\newif\if@noisy        % report what you're making?
\newif\if@atend        % %%BoundingBox: has (at end) specification
\newif\if@psfile       % does this look like a PostScript file?
%
% PostScript files should start with `%!'
%
{\catcode`\%=12\global\gdef\epsf@start{%!}}
\def\epsf@PS{PS}
%
\def\epsf@getbb#1{%
%
%   The first thing we need to do is to open the
%   PostScript file, if possible.
%
\openin\ps@stream=#1
\ifeof\ps@stream\ps@typeout{Error, File #1 not found}\else
%
%   Okay, we got it. Now we'll scan lines until we find one that doesn't
%   start with %. We're looking for the bounding box comment.
%
   {\not@eoftrue \chardef\other=12
    \def\do##1{\catcode`##1=\other}\dospecials \catcode`\ =10
    \loop
       \if@psfile
	  \read\ps@stream to \epsf@fileline
       \else{
	  \obeyspaces
          \read\ps@stream to \epsf@tmp\global\let\epsf@fileline\epsf@tmp}
       \fi
       \ifeof\ps@stream\not@eoffalse\else
%
%   Check the first line for `%!'.  Issue a warning message if its not
%   there, since the file might not be a PostScript file.
%
       \if@psfile\else
       \expandafter\epsf@test\epsf@fileline:. \\%
       \fi
%
%   We check to see if the first character is a % sign;
%   if so, we look further and stop only if the line begins with
%   `%%BoundingBox:' and the `(atend)' specification was not found.
%   That is, the only way to stop is when the end of file is reached,
%   or a `%%BoundingBox: llx lly urx ury' line is found.
%
          \expandafter\epsf@aux\epsf@fileline:. \\%
       \fi
   \ifnot@eof\repeat
   }\closein\ps@stream\fi}%
%
% This tests if the file we are reading looks like a PostScript file.
%
\long\def\epsf@test#1#2#3:#4\\{\def\epsf@testit{#1#2}
			\ifx\epsf@testit\epsf@start\else
\ps@typeout{Warning! File does not start with `\epsf@start'.  It may not be a PostScript file.}
			\fi
			\@psfiletrue} % don't test after 1st line
%
%   We still need to define the tricky \epsf@aux macro. This requires
%   a couple of magic constants for comparison purposes.
%
{\catcode`\%=12\global\let\epsf@percent=%\global\def\epsf@bblit{%BoundingBox}}
%
%
%   So we're ready to check for `%BoundingBox:' and to grab the
%   values if they are found.  We continue searching if `(at end)'
%   was found after the `%BoundingBox:'.
%
\long\def\epsf@aux#1#2:#3\\{\ifx#1\epsf@percent
   \def\epsf@testit{#2}\ifx\epsf@testit\epsf@bblit
	\@atendfalse
        \epsf@atend #3 . \\%
	\if@atend	
	   \if@verbose{
		\ps@typeout{psfig: found `(atend)'; continuing search}
	   }\fi
        \else
        \epsf@grab #3 . . . \\%
        \not@eoffalse
        \global\no@bbfalse
        \fi
   \fi\fi}%
%
%   Here we grab the values and stuff them in the appropriate definitions.
%
\def\epsf@grab #1 #2 #3 #4 #5\\{%
   \global\def\epsf@llx{#1}\ifx\epsf@llx\empty
      \epsf@grab #2 #3 #4 #5 .\\\else
   \global\def\epsf@lly{#2}%
   \global\def\epsf@urx{#3}\global\def\epsf@ury{#4}\fi}%
%
% Determine if the stuff following the %%BoundingBox is `(atend)'
% J. Daniel Smith.  Copied from \epsf@grab above.
%
\def\epsf@atendlit{(atend)} 
\def\epsf@atend #1 #2 #3\\{%
   \def\epsf@tmp{#1}\ifx\epsf@tmp\empty
      \epsf@atend #2 #3 .\\\else
   \ifx\epsf@tmp\epsf@atendlit\@atendtrue\fi\fi}


% End of file reading stuff from epsf.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% trigonometry stuff from "trig.tex"
\chardef\psletter = 11 % won't conflict with \begin{letter} now...
\chardef\other = 12

\newif \ifdebug %%% turn me on to see TeX hard at work ...
\newif\ifc@mpute %%% don't need to compute some values
\c@mputetrue % but assume that we do

\let\then = \relax
\def\r@dian{pt }
\let\r@dians = \r@dian
\let\dimensionless@nit = \r@dian
\let\dimensionless@nits = \dimensionless@nit
\def\internal@nit{sp }
\let\internal@nits = \internal@nit
\newif\ifstillc@nverging
\def \Mess@ge #1{\ifdebug \then \message {#1} \fi}

{ %%% Things that need abnormal catcodes %%%
	\catcode `\@ = \psletter
	\gdef \nodimen {\expandafter \n@dimen \the \dimen}
	\gdef \term #1 #2 #3%
	       {\edef \t@ {\the #1}%%% freeze parameter 1 (count, by value)
		\edef \t@@ {\expandafter \n@dimen \the #2\r@dian}%
				   %%% freeze parameter 2 (dimen, by value)
		\t@rm {\t@} {\t@@} {#3}%
	       }
	\gdef \t@rm #1 #2 #3%
	       {{%
		\count 0 = 0
		\dimen 0 = 1 \dimensionless@nit
		\dimen 2 = #2\relax
		\Mess@ge {Calculating term #1 of \nodimen 2}%
		\loop
		\ifnum	\count 0 < #1
		\then	\advance \count 0 by 1
			\Mess@ge {Iteration \the \count 0 \space}%
			\Multiply \dimen 0 by {\dimen 2}%
			\Mess@ge {After multiplication, term = \nodimen 0}%
			\Divide \dimen 0 by {\count 0}%
			\Mess@ge {After division, term = \nodimen 0}%
		\repeat
		\Mess@ge {Final value for term #1 of 
				\nodimen 2 \space is \nodimen 0}%
		\xdef \Term {#3 = \nodimen 0 \r@dians}%
		\aftergroup \Term
	       }}
	\catcode `\p = \other
	\catcode `\t = \other
	\gdef \n@dimen #1pt{#1} %%% throw away the ``pt''
}

\def \Divide #1by #2{\divide #1 by #2} %%% just a synonym

\def \Multiply #1by #2%%% allows division of a dimen by a dimen
       {{%%% should really freeze parameter 2 (dimen, passed by value)
	\count 0 = #1\relax
	\count 2 = #2\relax
	\count 4 = 65536
	\Mess@ge {Before scaling, count 0 = \the \count 0 \space and
			count 2 = \the \count 2}%
	\ifnum	\count 0 > 32767 %%% do our best to avoid overflow
	\then	\divide \count 0 by 4
		\divide \count 4 by 4
	\else	\ifnum	\count 0 < -32767
		\then	\divide \count 0 by 4
			\divide \count 4 by 4
		\else
		\fi
	\fi
	\ifnum	\count 2 > 32767 %%% while retaining reasonable accuracy
	\then	\divide \count 2 by 4
		\divide \count 4 by 4
	\else	\ifnum	\count 2 < -32767
		\then	\divide \count 2 by 4
			\divide \count 4 by 4
		\else
		\fi
	\fi
	\multiply \count 0 by \count 2
	\divide \count 0 by \count 4
	\xdef \product {#1 = \the \count 0 \internal@nits}%
	\aftergroup \product
       }}

\def\r@duce{\ifdim\dimen0 > 90\r@dian \then   % sin(x+90) = sin(180-x)
		\multiply\dimen0 by -1
		\advance\dimen0 by 180\r@dian
		\r@duce
	    \else \ifdim\dimen0 < -90\r@dian \then  % sin(-x) = sin(360+x)
		\advance\dimen0 by 360\r@dian
		\r@duce
		\fi
	    \fi}

\def\Sine#1%
       {{%
	\dimen 0 = #1 \r@dian
	\r@duce
	\ifdim\dimen0 = -90\r@dian \then
	   \dimen4 = -1\r@dian
	   \c@mputefalse
	\fi
	\ifdim\dimen0 = 90\r@dian \then
	   \dimen4 = 1\r@dian
	   \c@mputefalse
	\fi
	\ifdim\dimen0 = 0\r@dian \then
	   \dimen4 = 0\r@dian
	   \c@mputefalse
	\fi
%
	\ifc@mpute \then
        	% convert degrees to radians
		\divide\dimen0 by 180
		\dimen0=3.141592654\dimen0
%
		\dimen 2 = 3.1415926535897963\r@dian %%% a well-known constant
		\divide\dimen 2 by 2 %%% we only deal with -pi/2 : pi/2
		\Mess@ge {Sin: calculating Sin of \nodimen 0}%
		\count 0 = 1 %%% see power-series expansion for sine
		\dimen 2 = 1 \r@dian %%% ditto
		\dimen 4 = 0 \r@dian %%% ditto
		\loop
			\ifnum	\dimen 2 = 0 %%% then we've done
			\then	\stillc@nvergingfalse 
			\else	\stillc@nvergingtrue
			\fi
			\ifstillc@nverging %%% then calculate next term
			\then	\term {\count 0} {\dimen 0} {\dimen 2}%
				\advance \count 0 by 2
				\count 2 = \count 0
				\divide \count 2 by 2
				\ifodd	\count 2 %%% signs alternate
				\then	\advance \dimen 4 by \dimen 2
				\else	\advance \dimen 4 by -\dimen 2
				\fi
		\repeat
	\fi		
			\xdef \sine {\nodimen 4}%
       }}

% Now the Cosine can be calculated easily by calling \Sine
\def\Cosine#1{\ifx\sine\UnDefined\edef\Savesine{\relax}\else
		             \edef\Savesine{\sine}\fi
	{\dimen0=#1\r@dian\advance\dimen0 by 90\r@dian
	 \Sine{\nodimen 0}
	 \xdef\cosine{\sine}
	 \xdef\sine{\Savesine}}}	      
% end of trig stuff
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\psdraft{
	\def\@psdraft{0}
	%\ps@typeout{draft level now is \@psdraft \space . }
}
\def\psfull{
	\def\@psdraft{100}
	%\ps@typeout{draft level now is \@psdraft \space . }
}

\psfull

\newif\if@scalefirst
\def\psscalefirst{\@scalefirsttrue}
\def\psrotatefirst{\@scalefirstfalse}
\psrotatefirst

\newif\if@draftbox
\def\psnodraftbox{
	\@draftboxfalse
}
\def\psdraftbox{
	\@draftboxtrue
}
\@draftboxtrue

\newif\if@prologfile
\newif\if@postlogfile
\def\pssilent{
	\@noisyfalse
}
\def\psnoisy{
	\@noisytrue
}
\psnoisy
%%% These are for the option list.
%%% A specification of the form a = b maps to calling \@p@@sa{b}
\newif\if@bbllx
\newif\if@bblly
\newif\if@bburx
\newif\if@bbury
\newif\if@height
\newif\if@width
\newif\if@rheight
\newif\if@rwidth
\newif\if@angle
\newif\if@clip
\newif\if@verbose
\def\@p@@sclip#1{\@cliptrue}


\newif\if@decmpr

%%% GDH 7/26/87 -- changed so that it first looks in the local directory,
%%% then in a specified global directory for the ps file.
%%% RPR 6/25/91 -- changed so that it defaults to user-supplied name if
%%% boundingbox info is specified, assuming graphic will be created by
%%% print time.
%%% TJD 10/19/91 -- added bbfile vs. file distinction, and @decmpr flag

\def\@p@@sfigure#1{\def\@p@sfile{null}\def\@p@sbbfile{null}
	        \openin1=#1.bb
		\ifeof1\closein1
	        	\openin1=\figurepath#1.bb
			\ifeof1\closein1
			        \openin1=#1
				\ifeof1\closein1%
				       \openin1=\figurepath#1
					\ifeof1
					   \ps@typeout{Error, File #1 not found}
						\if@bbllx\if@bblly
				   		\if@bburx\if@bbury
			      				\def\@p@sfile{#1}%
			      				\def\@p@sbbfile{#1}%
							\@decmprfalse
				  	   	\fi\fi\fi\fi
					\else\closein1
				    		\def\@p@sfile{\figurepath#1}%
				    		\def\@p@sbbfile{\figurepath#1}%
						\@decmprfalse
	                       		\fi%
			 	\else\closein1%
					\def\@p@sfile{#1}
					\def\@p@sbbfile{#1}
					\@decmprfalse
			 	\fi
			\else
				\def\@p@sfile{\figurepath#1}
				\def\@p@sbbfile{\figurepath#1.bb}
				\@decmprtrue
			\fi
		\else
			\def\@p@sfile{#1}
			\def\@p@sbbfile{#1.bb}
			\@decmprtrue
		\fi}

\def\@p@@sfile#1{\@p@@sfigure{#1}}

\def\@p@@sbbllx#1{
		%\ps@typeout{bbllx is #1}
		\@bbllxtrue
		\dimen100=#1
		\edef\@p@sbbllx{\number\dimen100}
}
\def\@p@@sbblly#1{
		%\ps@typeout{bblly is #1}
		\@bbllytrue
		\dimen100=#1
		\edef\@p@sbblly{\number\dimen100}
}
\def\@p@@sbburx#1{
		%\ps@typeout{bburx is #1}
		\@bburxtrue
		\dimen100=#1
		\edef\@p@sbburx{\number\dimen100}
}
\def\@p@@sbbury#1{
		%\ps@typeout{bbury is #1}
		\@bburytrue
		\dimen100=#1
		\edef\@p@sbbury{\number\dimen100}
}
\def\@p@@sheight#1{
		\@heighttrue
		\dimen100=#1
   		\edef\@p@sheight{\number\dimen100}
		%\ps@typeout{Height is \@p@sheight}
}
\def\@p@@swidth#1{
		%\ps@typeout{Width is #1}
		\@widthtrue
		\dimen100=#1
		\edef\@p@swidth{\number\dimen100}
}
\def\@p@@srheight#1{
		%\ps@typeout{Reserved height is #1}
		\@rheighttrue
		\dimen100=#1
		\edef\@p@srheight{\number\dimen100}
}
\def\@p@@srwidth#1{
		%\ps@typeout{Reserved width is #1}
		\@rwidthtrue
		\dimen100=#1
		\edef\@p@srwidth{\number\dimen100}
}
\def\@p@@sangle#1{
		%\ps@typeout{Rotation is #1}
		\@angletrue
%		\dimen100=#1
		\edef\@p@sangle{#1} %\number\dimen100}
}
\def\@p@@ssilent#1{ 
		\@verbosefalse
}
\def\@p@@sprolog#1{\@prologfiletrue\def\@prologfileval{#1}}
\def\@p@@spostlog#1{\@postlogfiletrue\def\@postlogfileval{#1}}
\def\@cs@name#1{\csname #1\endcsname}
\def\@setparms#1=#2,{\@cs@name{@p@@s#1}{#2}}
%
% initialize the defaults (size the size of the figure)
%
\def\ps@init@parms{
		\@bbllxfalse \@bbllyfalse
		\@bburxfalse \@bburyfalse
		\@heightfalse \@widthfalse
		\@rheightfalse \@rwidthfalse
		\def\@p@sbbllx{}\def\@p@sbblly{}
		\def\@p@sbburx{}\def\@p@sbbury{}
		\def\@p@sheight{}\def\@p@swidth{}
		\def\@p@srheight{}\def\@p@srwidth{}
		\def\@p@sangle{0}
		\def\@p@sfile{} \def\@p@sbbfile{}
		\def\@p@scost{10}
		\def\@sc{}
		\@prologfilefalse
		\@postlogfilefalse
		\@clipfalse
		\if@noisy
			\@verbosetrue
		\else
			\@verbosefalse
		\fi
}
%
% Go through the options setting things up.
%
\def\parse@ps@parms#1{
	 	\@psdo\@psfiga:=#1\do
		   {\expandafter\@setparms\@psfiga,}}
%
% Compute bb height and width
%
\newif\ifno@bb
\def\bb@missing{
	\if@verbose{
		\ps@typeout{psfig: searching \@p@sbbfile \space  for bounding box}
	}\fi
	\no@bbtrue
	\epsf@getbb{\@p@sbbfile}
        \ifno@bb \else \bb@cull\epsf@llx\epsf@lly\epsf@urx\epsf@ury\fi
}	
\def\bb@cull#1#2#3#4{
	\dimen100=#1 bp\edef\@p@sbbllx{\number\dimen100}
	\dimen100=#2 bp\edef\@p@sbblly{\number\dimen100}
	\dimen100=#3 bp\edef\@p@sbburx{\number\dimen100}
	\dimen100=#4 bp\edef\@p@sbbury{\number\dimen100}
	\no@bbfalse
}
% rotate point (#1,#2) about (0,0).
% The sine and cosine of the angle are already stored in \sine and
% \cosine.  The result is placed in (\p@intvaluex, \p@intvaluey).
\newdimen\p@intvaluex
\newdimen\p@intvaluey
\def\rotate@#1#2{{\dimen0=#1 sp\dimen1=#2 sp
%            	calculate x' = x \cos\theta - y \sin\theta
		  \global\p@intvaluex=\cosine\dimen0
		  \dimen3=\sine\dimen1
		  \global\advance\p@intvaluex by -\dimen3
% 		calculate y' = x \sin\theta + y \cos\theta
		  \global\p@intvaluey=\sine\dimen0
		  \dimen3=\cosine\dimen1
		  \global\advance\p@intvaluey by \dimen3
		  }}
\def\compute@bb{
		\no@bbfalse
		\if@bbllx \else \no@bbtrue \fi
		\if@bblly \else \no@bbtrue \fi
		\if@bburx \else \no@bbtrue \fi
		\if@bbury \else \no@bbtrue \fi
		\ifno@bb \bb@missing \fi
		\ifno@bb \ps@typeout{FATAL ERROR: no bb supplied or found}
			\no-bb-error
		\fi
		%
%\ps@typeout{BB: \@p@sbbllx, \@p@sbblly, \@p@sbburx, \@p@sbbury} 
%
% store height/width of original (unrotated) bounding box
		\count203=\@p@sbburx
		\count204=\@p@sbbury
		\advance\count203 by -\@p@sbbllx
		\advance\count204 by -\@p@sbblly
		\edef\ps@bbw{\number\count203}
		\edef\ps@bbh{\number\count204}
		%\ps@typeout{ psbbh = \ps@bbh, psbbw = \ps@bbw }
		\if@angle 
			\Sine{\@p@sangle}\Cosine{\@p@sangle}
	        	{\dimen100=\maxdimen\xdef\r@p@sbbllx{\number\dimen100}
					    \xdef\r@p@sbblly{\number\dimen100}
			                    \xdef\r@p@sbburx{-\number\dimen100}
					    \xdef\r@p@sbbury{-\number\dimen100}}
%
% Need to rotate all four points and take the X-Y extremes of the new
% points as the new bounding box.
                        \def\minmaxtest{
			   \ifnum\number\p@intvaluex<\r@p@sbbllx
			      \xdef\r@p@sbbllx{\number\p@intvaluex}\fi
			   \ifnum\number\p@intvaluex>\r@p@sbburx
			      \xdef\r@p@sbburx{\number\p@intvaluex}\fi
			   \ifnum\number\p@intvaluey<\r@p@sbblly
			      \xdef\r@p@sbblly{\number\p@intvaluey}\fi
			   \ifnum\number\p@intvaluey>\r@p@sbbury
			      \xdef\r@p@sbbury{\number\p@intvaluey}\fi
			   }
%			lower left
			\rotate@{\@p@sbbllx}{\@p@sbblly}
			\minmaxtest
%			upper left
			\rotate@{\@p@sbbllx}{\@p@sbbury}
			\minmaxtest
%			lower right
			\rotate@{\@p@sbburx}{\@p@sbblly}
			\minmaxtest
%			upper right
			\rotate@{\@p@sbburx}{\@p@sbbury}
			\minmaxtest
			\edef\@p@sbbllx{\r@p@sbbllx}\edef\@p@sbblly{\r@p@sbblly}
			\edef\@p@sbburx{\r@p@sbburx}\edef\@p@sbbury{\r@p@sbbury}
%\ps@typeout{rotated BB: \r@p@sbbllx, \r@p@sbblly, \r@p@sbburx, \r@p@sbbury}
		\fi
		\count203=\@p@sbburx
		\count204=\@p@sbbury
		\advance\count203 by -\@p@sbbllx
		\advance\count204 by -\@p@sbblly
		\edef\@bbw{\number\count203}
		\edef\@bbh{\number\count204}
		%\ps@typeout{ bbh = \@bbh, bbw = \@bbw }
}
%
% \in@hundreds performs #1 * (#2 / #3) correct to the hundreds,
%	then leaves the result in @result
%
\def\in@hundreds#1#2#3{\count240=#2 \count241=#3
		     \count100=\count240	% 100 is first digit #2/#3
		     \divide\count100 by \count241
		     \count101=\count100
		     \multiply\count101 by \count241
		     \advance\count240 by -\count101
		     \multiply\count240 by 10
		     \count101=\count240	%101 is second digit of #2/#3
		     \divide\count101 by \count241
		     \count102=\count101
		     \multiply\count102 by \count241
		     \advance\count240 by -\count102
		     \multiply\count240 by 10
		     \count102=\count240	% 102 is the third digit
		     \divide\count102 by \count241
		     \count200=#1\count205=0
		     \count201=\count200
			\multiply\count201 by \count100
		 	\advance\count205 by \count201
		     \count201=\count200
			\divide\count201 by 10
			\multiply\count201 by \count101
			\advance\count205 by \count201
			%
		     \count201=\count200
			\divide\count201 by 100
			\multiply\count201 by \count102
			\advance\count205 by \count201
			%
		     \edef\@result{\number\count205}
}
\def\compute@wfromh{
		% computing : width = height * (bbw / bbh)
		\in@hundreds{\@p@sheight}{\@bbw}{\@bbh}
		%\ps@typeout{ \@p@sheight * \@bbw / \@bbh, = \@result }
		\edef\@p@swidth{\@result}
		%\ps@typeout{w from h: width is \@p@swidth}
}
\def\compute@hfromw{
		% computing : height = width * (bbh / bbw)
	        \in@hundreds{\@p@swidth}{\@bbh}{\@bbw}
		%\ps@typeout{ \@p@swidth * \@bbh / \@bbw = \@result }
		\edef\@p@sheight{\@result}
		%\ps@typeout{h from w : height is \@p@sheight}
}
\def\compute@handw{
		\if@height 
			\if@width
			\else
				\compute@wfromh
			\fi
		\else 
			\if@width
				\compute@hfromw
			\else
				\edef\@p@sheight{\@bbh}
				\edef\@p@swidth{\@bbw}
			\fi
		\fi
}
\def\compute@resv{
		\if@rheight \else \edef\@p@srheight{\@p@sheight} \fi
		\if@rwidth \else \edef\@p@srwidth{\@p@swidth} \fi
		%\ps@typeout{rheight = \@p@srheight, rwidth = \@p@srwidth}
}
%		
% Compute any missing values
\def\compute@sizes{
	\compute@bb
	\if@scalefirst\if@angle
% at this point the bounding box has been adjsuted correctly for
% rotation.  PSFIG does all of its scaling using \@bbh and \@bbw.  If
% a width= or height= was specified along with \psscalefirst, then the
% width=/height= value needs to be adjusted to match the new (rotated)
% bounding box size (specifed in \@bbw and \@bbh).
%    \ps@bbw       width=
%    -------  =  ---------- 
%    \@bbw       new width=
% so `new width=' = (width= * \@bbw) / \ps@bbw; where \ps@bbw is the
% width of the original (unrotated) bounding box.
	\if@width
	   \in@hundreds{\@p@swidth}{\@bbw}{\ps@bbw}
	   \edef\@p@swidth{\@result}
	\fi
	\if@height
	   \in@hundreds{\@p@sheight}{\@bbh}{\ps@bbh}
	   \edef\@p@sheight{\@result}
	\fi
	\fi\fi
	\compute@handw
	\compute@resv}

%
% \psfig
% usage : \psfig{file=, height=, width=, bbllx=, bblly=, bburx=, bbury=,
%			rheight=, rwidth=, clip=}
%
% "clip=" is a switch and takes no value, but the `=' must be present.
\def\psfig#1{\vbox {
	% do a zero width hard space so that a single
	% \psfig in a centering enviornment will behave nicely
	%{\setbox0=\hbox{\ }\ \hskip-\wd0}
	%
	\ps@init@parms
	\parse@ps@parms{#1}
	\compute@sizes
	%
	\ifnum\@p@scost<\@psdraft{
		%
		\special{ps::[begin] 	\@p@swidth \space \@p@sheight \space
				\@p@sbbllx \space \@p@sbblly \space
				\@p@sbburx \space \@p@sbbury \space
				startTexFig \space }
		\if@angle
			\special {ps:: \@p@sangle \space rotate \space} 
		\fi
		\if@clip{
			\if@verbose{
				\ps@typeout{(clip)}
			}\fi
			\special{ps:: doclip \space }
		}\fi
		\if@prologfile
		    \special{ps: plotfile \@prologfileval \space } \fi
		\if@decmpr{
			\if@verbose{
				\ps@typeout{psfig: including \@p@sfile.Z \space }
			}\fi
			\special{ps: plotfile "`zcat \@p@sfile.Z" \space }
		}\else{
			\if@verbose{
				\ps@typeout{psfig: including \@p@sfile \space }
			}\fi
			\special{ps: plotfile \@p@sfile \space }
		}\fi
		\if@postlogfile
		    \special{ps: plotfile \@postlogfileval \space } \fi
		\special{ps::[end] endTexFig \space }
		% Create the vbox to reserve the space for the figure.
		\vbox to \@p@srheight sp{
		% 1/92 TJD Changed from "true sp" to "sp" for magnification.
			\hbox to \@p@srwidth sp{
				\hss
			}
		\vss
		}
	}\else{
		% draft figure, just reserve the space and print the
		% path name.
		\if@draftbox{		
			% Verbose draft: print file name in box
			\hbox{\frame{\vbox to \@p@srheight sp{
			\vss
			\hbox to \@p@srwidth sp{ \hss \@p@sfile \hss }
			\vss
			}}}
		}\else{
			% Non-verbose draft
			\vbox to \@p@srheight sp{
			\vss
			\hbox to \@p@srwidth sp{\hss}
			\vss
			}
		}\fi	



	}\fi
}}
\psfigRestoreAt
\let\@=\LaTeXAtSign





rpe.tex
\documentclass[11pt]{article}
\usepackage{epsf}
\usepackage{epsfig}  
\usepackage{url}

\input{psfig}
\setlength{\topmargin}{-0.3in}
\setlength{\textheight}{8.6in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{-0.12in}
\setlength{\evensidemargin}{0.0in} 

\newcommand{\mycomment}[1]{}
\newcommand{\myfig}[3]
{
\begin{figure}
\centerline{\psfig{figure=#1.eps,width=#2}}
\caption{#3}
\label{#1:fig}
\end{figure}
}
\newcommand{\mypfig}[3]
{
\begin{figure}
\centerline{\psfig{figure=#1.ps,width=#2}}
\caption{#3}
\label{#1:fig}
\end{figure}
}
\newcommand{\Hl}{\hline}
\newcommand{\K}{\emph{K}}

\begin{document}
\ifx\href\undefined\else\hypersetup{linktocpage=true}\fi 

\title{CDN: Content Distribution Network\thanks{Technical Report TR-125 of Experimental Computer Systems Lab in Stony Brook University.}}
\author{
Gang Peng \\ 
Department of Computer Science, \\
State University of New York at Stony Brook, \\
Stony Brook, NY 11794-4400. \\
{\tt gpeng@cs.sunysb.edu} }
%\date{}
\maketitle

\begin{abstract}
\input{abstract}
\end{abstract}

%\newpage
%\tableofcontents
%\listoffigures
%\listoftables
%\newpage
\setcounter{page}{1}

\input{intro}
\input{cdn}
\input{cds}
\input{rr}
\input{akamai}
\input{dht}
\input{conclude}

%\appendix
%\input{append}

\bibliographystyle{alpha}
%\bibliography{paperlist}
\bibliography{rpe}

\end{document}

rr.tex
%\section{Request Routing in CDN}
%\section{Servicing Request}
\section{Request Service}
%expect 5 - 6 pages
Two steps of operations are involved in servicing a request in a CDN:
locating a suitable server holding the replicates of the requested object,
which we name as {\em server location},
and redirecting the request to the selected server,
which is called {\em request routing}.
In a totally distributed request routing system, such as 
anycasting, the request is forwarded directly to the proper
servers via anycast-aware routers, in which these two
operations are combined together indeed. In this section, we first investigate
these two issues and then explore the known anycasting schemes in depth.
As one special type of CDN with no infrastructure support, peer-to-peer systems
have been shed spotlight, either from academic or industry.
We will also discuss the request routing problem in these systems in the last
subsection.

\subsection{Server Location}

\myfig{server_loc}{4 in}{Server Location Techniques}
%see Guyton's paper and write a new outline for server location.
There are a number of possible ways to locate a nearby or suitable server
in an internetwork environment, as summarized in
Figure \ref{server_loc:fig} \cite{Guyton}. The first choice about server
location strategy is whether server
location information is gathered in {\em reaction} to client requests for
nearby servers, e.g., using a multicast scheme, or whether this
information is gathered {\em proactively}. The next choice is whether support
should be provided by the routing layer. Such support can reduce gathering
costs, but given the practical difficulties of implementing widespread
router changes,
we also consider techniques to gather server location information in the
application layer. Finally, we compare the cost of polling routing table against
gathering information via network probes.

\paragraph{Reactive vs. proactive gathering}
Broadcast and multicast are two typical reactive approaches to locate
suitable servers. Boggs \cite{Boggs} proposed an
{\em expanding ring} broadcast mechanism
that iteratively enlarges concentric rings around
the broadcasting host. More recent approaches have considered
various forms of multicast routing. That is, given a multicast group joined
by all instances of a particular type of server, one can choose the server
that responds most quickly to a group multicast message. Since each time
a client wants to locate a server providing a particular service, a message
has to be multicasted to the entire group of servers, this approach 
wastes the precious network bandwidth. 
In contrast, in a proactive scheme, some agents, such as routers
or dedicated applications, gather the network and server information by
sending probe messages to the candidate servers or collect load information
dispatched by servers, and maintain the server location or load database.
Clients that
request some service can locate a proper server providing the desired service
by only sending a query to the agents. This way, the unnecessary message 
transmission can be avoided.

\paragraph{Routing layer vs. application layer}
Partridge et al. \cite{Partridge} proposed an {\em anycasting} mechanism,
particularly in IP layer, which attempts to deliver a request to
one nearby server.
Anycasting is appealing because it can avoid burdening links with repeated
requests to gather server distance information.
However, a downside is that IP
anycasting assumes that all servers provide equal service\footnote{
Partridge et al. \cite{Partridge}
specifies that a single server is selected in response to an anycast request,
and that any of the servers in the anycast group are equally usable.}. It
therefore cannot handle server quality differences without programming
policy constraints into routers. In contrast to IP anycasting,
an application-level
location service could include server quality into the selection criterion, 
after a handful of nearby servers have been selected from the
database. As an additional practical advantage, an application-level service
could be implemented without routing support, albeit at higher network cost.
The main disadvantage of building the server location database at the
application-level is that doing so requires periodic updating. At the routing
layer the location database can be constructed incrementally by monitoring
routing update traffic and group join/leave requests. Some approaches were
proposed which aim to enjoy the benefits of both. Wood et al. \cite{Wood}
built an
application-level location service that constructs the server location
database by monitoring the routing-layer traffic. Fei et al. \cite{Fei}
proposed an application-level anycasting mechanism to provide server
location service. In their system, only when the load on a server changes
{\em significantly}, the server pushes the changed status to the agents and
then triggers updating the database so as to cut down the updating operation
cost.

\paragraph{Polling routing table vs. network probing}
By polling routing tables, we can build a
connectivity graph from a measurement beacon to one server by retrieving the
local routing table, determining the next hop along the path, retrieving the
routing table for that router, and so on, until we reach the destination.
We can extend this algorithm to discover routes to all servers by iterating
over the servers, taking care not to retrieve a routing table that has
already been retrieved.
%Therefore, the cost of discovering the routes to
%all replicated servers is simply the cost of retrieving all of the routing
%tables in the set of paths to all of the servers.
In network probing approach,
some measurement servers are responsible to explore the route to each of the
replica servers by probing the servers. When a client asks one of the
measurement servers for a list of nearby replica servers, a measurement
server explores the route back to the client and adds that information to
its connectivity database. It then searches the databases for servers near
the client.

%brief other work relevant to server selection: evaluations of server metrics,
%studies that characterize the behavior of existing mirror servers in order
%to draw conclusions about the the design of server selection systems.
%see "Andy Myers' Performance Characteristics of Mirror Servers on the Internet"

%server selection within diff service network
%discuss it as a paragraph

\subsection{Request Routing}
The request routing schemes proposed so far fall into the five categories:
{\em client multiplexing}, {\em DNS indirection}, {\em HTTP redirection},
{\em anycasting} and {\em peer-to-peer routing}.
We will discuss the former three in the remaining part of this subsection and
the latter two in the other two subsections.

\subsubsection{Client Multiplexing}
In this approach, the client (Web browser or a proxy server) obtains
the addresses of a set of
physical replica servers and chooses one to send its request to. Three main
mechanisms belong in this category.

The first one is that the DNS server of the service provider returns the IP
addresses of servers holding a replica of the object. The client's DNS resolver
chooses a server among these. To decide, the resolver may issue probes to the
servers and choose based on response times to these probes, or it may collect
reports from the clients on performance of past accesses to these servers.
This approach is used by Bhattacharjee et al. \cite{Bhattacharjee}
and by Beck and Moore \cite{Beck}. Its advantage is that no extra communication
is added to the critical path of request processing. There are also several
shortcomings. First, the approach relies on clients using a customized DNS
resolver. If this resolver relies on client performance reports, then the
client (i.e., browser or proxy) software must be modified as well. Second,
the DNS infrastructure relies heavily on DNS response caching to cope with
its load. Therefore, replica server sets cannot be changed frequently
without the
danger of resolvers using stale replica server sets. At the same time, reducing
the caching time may incur DNS queries more frequently and hence just moves the
stability bottleneck to the DNS
infrastructure, provided enough clients adopt the approach.\mycomment{
Thus, this approach
is most appropriate for static replication. }

The second approach relies on Java applets to perform replica server selection
on the client \cite{Yoshikawa}. The URL of an object actually points to a Java
applet, which embeds the knowledge about the current replica server set and the
procedure for replica server selection.
This approach requires no changes to clients.
However, unlike the previous approach, it involves an extra TCP communication
to download the applet.

The third approach, proposed by \cite{Baentsch},
 propagates information about replica server
sets in HTTP headers. It requires changes to both Web servers and clients 
(proxy servers in this case) to process extra headers. Clients must also be
modified to implement replica server selection.

\mycomment{\subsubsection{IP Multiplexing}
A plethora of commercial products offers multiplexing routers. In this approach,
a special multiplexing router (or a multiplexer) is placed in front of a
server farm. The domain name of the Web site is mapped to the IP address of
this router, so all clients send their packets to it. When the first packet
from a client arrives, the multiplexer selects a server in the farm and
forwards the packet (and all subsequent packets in the same session) to this
server. The multiplexer also intercepts the response packets and modifies
their headers to contain its IP address rather than that of the server. The
multiplexer maintains a {\em sessions database}, which records a server chosen
for each active communication session. The sessions database is needed to ensure
that, once a server is chosen for servicing a request, all packets from this
client in this communication session go the same server.

This approach uses standard clients and DNS and Web servers. However, by
having a focal communication point, it does not scale geographically. Thus,
it is mostly used for load sharing in a server farm on a local-area network. }

\subsubsection{DNS Indirection}
Several domain name server implementations allow the Web site's DNS server
to map a host domain name to a set of IP addresses and choose one of them for
every client query, based on such factors as the query origin and the load
of replica servers. The difference with DNS-based client multiplexing is
that choosing a replica server occurs at the Web site or the DNS infrastructure,
not at the client's DNS
resolver. \mycomment{This approach can scale well geographically.}
Unfortunately,
DNS response caching by clients complicates changing replica server sets and
controlling request distribution among replica servers.
At the same time, reducing
the lifetime of cached DNS responses may shift the performance bottleneck
to the DNS infrastructure.
In general, DNS system was designed for mostly an append-only database of
existing mappings between a host name and an IP address that
rarely ever changes.
\mycomment{
Dynamic replication schemes, however, constantly change the
set of replicas for a given object. }

%typical systems.
%\cite{Tang}, \cite{Brisco}, \cite{Shaikh}

\subsubsection{HTTP Redirection}

HTTP protocols allow a Web server to respond to a client request with a
special message that tells the client to re-submit its request to another
server. This mechanism can be used to build a special Web server which accepts
client requests, chooses replica servers for them and redirects clients to these
servers. Commercially, Cisco Distributed Director \cite{Cisco} and
WindDance Web Challenger \cite{WindDance} implemented this functionality.

%for comments about CISCO DD, see {Adjie-Winoto}

An advantage of HTTP-level redirection is that replication can be managed
at fine granularity, down to individual Web pages, whereas other mechanisms
postulate the entire Web site as the granule. A disadvantage is that this
mechanism is quite heavyweight. Not only does it introduce an extra message
round-trip into request processing, but also this round-trip is done over HTTP,
which uses the expensive TCP protocol as the transport layer.

%cite{Kangasharju}

\mycomment{
\subsection{Anycasting}

As defined \cite{Partridge}, anycasting provides:
``a stateless best effort delivery of an anycast packet to at least one host,
and preferably only one host, which serves the anycast address". The anycasting
schemes proposed in literature so far can be classified into two classes:
IP anycasting and application-layer anycasting.
}

%\subsubsection{IP Anycasting}
\subsection{Anycasting}

As defined \cite{Partridge}, anycasting provides:
``a stateless best effort delivery of an anycast packet to at least one host,
and preferably only one host, which serves the anycast address". The anycasting
schemes proposed in literature so far can be classified into two classes:
IP anycasting and application-level anycasting.

\subsubsection{IP Anycasting}

\mycomment{In the next generation of the Internet routing protocol (IPv6),
an {\em anycast}
service \cite{} will be supported. This service assume that the same IP address
is assigned to a set of hosts, and each IP router has in its routing table
a path to the host that is the closest to this router. Thus, different IP
routers have paths to different hosts with the same IP address.

There is virtually no overhead for request indirection with anycast, since
packets travel along router paths anyway. However, it assumes very static
replica sets (since a change in the replica set would take long time to 
reflect in router tables throughout the Internet) and a rigid request
distribution (because all requests from a given client normally go to the same
host, chosen based on the network proximity). Advances in research on
{\em active networks} \cite{}, where applications can inject ad-hoc programs
into network router, may alleviate the last limitation. }

\myfig{IP_anycast}{3 in}{Illustration of IP Anycast}

IP anycasting was proposed by Partridge et al. \cite{Partridge}. Such service
assumes that the same IP address is assigned to a set of hosts, and each
IP router has in its routing table a path to the host that is the
closest\footnote{'closest' is defined according to the routing system's
measure of distance.} to
this router. Thus, different IP routers have paths to different hosts with
the same IP address. Figure \ref{IP_anycast:fig} illustrates IP anycasting.

The traditional approach routes IP anycast addresses using the unicast routing
protocols, a design decision that makes IP anycast unscalable.
The anycast group topology may not be hierarchical or comply with the unicast
topology and thereby routing anycast packets using the unicast routing
protocols requires advertising each global anycast address separately. This
requirement causes the routing tables to grow proportionally to the
number of all global anycast groups in the entire Internet, and hence does
not scale.

\myfig{IP_anycast_class}{3 in}{Anycast Group Classification at An Edge Domain}

Katabi et al. \cite{Katabi} proposed a framework for scalable global IP
anycast (GIA).
The framework
scales by capturing the special characteristics of the anycast service in its
inter-domain routing protocol, which generates two types of routes:
default inexpensive routes that consume no bandwidth or storage space,
and enhanced shortest path routes that are customized according to the
beneficiary domain's interests.
Figure \ref{IP_anycast_class:fig} shows the anycast group classification at an
edge domain.

For routing internal anycast groups, GIA uses
the unicast intra-domain routing protocol,
either based on the distance-vector algorithm, e.g., RIP, or on the link-state
algorithm, such as OSPF. This approach stays scalable because the number of
internal group is controllable by the domain itself. To route an
unpopular anycast group, GIA uses a default route. A default route is determined
by the unicast prefix of the home domain,
which is part of the anycast address, and does not consume any bandwidth
to be generated and does not need any storage space in the routing
tables.
A router that receives an anycast packet addressed to an unpopular anycast
group forwards the packet to the group member in the home domain.
For popular anycast groups, GIA generates shortest path routes and forwards
the packet address to a popular anycast group via the shortest path route.

Although IP anycast is suitable for request routing and service location,
it has the following limitations:
\begin{itemize}
\item Some part of the IP address space must be allocated to anycast address.
\item Anycast addresses requires router support.
\item The selection of the server to which an anycast packet is sent is
made entirely within the network with no option for user selection or input.
\item Consistent with the stateless nature of IP, the destination is
determined on a per-packet basis.
\end{itemize}

%\subsubsection{Application-Level Anycasting}
%\subsection{Anycasting -- Application-Level Anycasting}
\subsubsection{Application-Level Anycasting}

Since the network layer is able to effectively determine the shortest path,
it is well suited for the IP anycasting service that selects the closest
server based upon a shortest path metric such as hop count. On the other
hand, an application layer approach is better suited at handling a
variety of other metrics such as server throughput.
Here we survey some typical systems in this field, which we call content
routing network.

%\subsubsection{Content Routing Network}

%Several schemes of content routing were proposed to overcome the
%limitations of IP anycast.
Fei et al. \cite{Fei} observed the shortcomings of IP anycast and proposed
a framework for application-level anycasting service. In their design, the
service consists of a set of {\em anycast resolvers}, which performs the
{\em anycast domain names} (ADN) to IP address mapping. Clients interact with
the anycast resolvers by generating an anycast query. The resolver processes
the query and replies with an anycast response. A key feature of the system
is the presence of a metric database, associated with each anycast resolver,
containing performance data about replica servers.
The performance data can be used
in the selection of a server from a group, based on user-specified performance
criteria. It estimates the server performance 
with manageable overhead by combining server pushes with client probes. However,
deploying such a system requires the changes to the servers as well as
the clients, which is prohibitively costly considering the possibly huge 
number of servers and clients.

\myfig{content_routing}{2.2 in}{Content Layer Routing}

Adjie-Winoto et al. \cite{Adjie-Winoto} proposed an intentional naming
system (INS), which is designed as a resource discovery and service
location system for
dynamic and mobile networks of devices and computers. INS applications may be
{\em services} or {\em clients}: services provide functionality or data and
clients request and access these. {\em Intentional Name Resolvers (INRs)} form
an application-level overlay network to exchange services descriptions,
construct a local cache based on these advertisements and route
client requests to the appropriate services. INS uses a simple language based
on attributes and values for its names, which enable the service to be
specified precisely. In addition, INS implements a late binding
mechanism that integrates name resolution and message routing, enabling
clients to continue communicating with end-nodes even if the name-to-address
mappings change while a session is in progress. However, INS is not designed
to provide global reachability information, and the attribute-based naming 
is less scalable than a hierarchical namespace provided by URL. Also, INS's
late binding, where every message packet contains a name, is too expensive to
use for content distribution.

%\myfig{content_routing}{2.2 in}{Content Layer Routing}

Gritter et al. \cite{Gritter} designed a framework for content routing
support in the Internet. Replica servers can be viewed as offering
alternate routes to access the content that the client requests, as depicted in
Figure \ref{content_routing:fig}. Network-integrated content routing provides
support in the core of the Internet to distribute, maintain and make use of
information about content reachability. This is performed by routers that
are extended to support naming. They designed the {\em Name-Based Routing
Protocol (NBRP)}, which performs routing by name with a structure similar to
BGP. Like BGP, NBRP is a distance-vector routing algorithm with path
information: an NBRP routing advertisement contains the path of content routers
toward a content server. An {\em Internet Name Resolution Protocol (INRP)} is
developed to perform efficient lookup on the distributed integrated
name-based routing system.

%\myfig{inrp}{2.0 in}{Internet Name Resolution Protocol}

Clients that desire some content initiate content request by contacting a local
content router. Each content router maintains a set of name-to-next-hop
mappings, just as an IP router maps address prefixes to next hops. When an
INRP request arrives, the desired name is looked up in the name routing table,
and the next hop is chosen based on the information associated with the known
routes. The content router forwards the request to the next content router, and
in this way the request proceeds toward the ``best" content server, as shown in
Figure \ref{inrp:fig} (The routing information kept for a name is typically
just the path of content routers to the content server, although it may be
augmented with load information or metrics directly measured by a content
router). When an INRP request reaches the content router adjacent
to the ``best" content server, that router sends back a response message
containing the address of the preferred server. This response is sent back
along the same path of content routers. If no response appears, intermediate
content routers can select alternate routes and retry the name lookup.
In this fashion, client requests are routed over the best path to the desired
content. INRP thus provides an ``anycast" capability at the content level.

\myfig{inrp}{2.0 in}{Internet Name Resolution Protocol}

\subsection{Peer-to-Peer Systems}
Peer-to-peer systems build the information retrieval network on the members
themselves instead of relying on a dedicated infrastructure like the
traditional CDNs do. As a result, peer-to-peer systems are more fault-tolerant
than the common CDNs.
Also, peer-to-peer
systems are more suitable for content producers who are individuals, who may
not be able to access or afford the common CDNs, most of which are commercial
ones.


Ian Clarke et al. \cite{clarke00freenet}
designed Freenet, a distributed adaptive peer-to-peer system that
enables the storage and retrieval of data while maintaining the anonymity
of readers and authors. Freenet operates as a peer-to-peer system where nodes
request a file store or retrieve service to their immediate neighbors using
a location-independent naming key. Requests are forwarded hop-by-hop,
a way similar
to IP routing, and have a limited hops-to-live as well as a unique random id
number to avoid loops in routing. Each node has a data store to which it must
allow network access, as well as a dynamic routing table with keys associated
with node addresses. File keys are generated using hash functions. Each file
has a random public/private key pair to serve as a namespace called
signed-subspace key (SSK) and a keyword-signed key (KSK) generated by a short
descriptive text. A user publishes his descriptive string and subspace
public key, and keeps his private key secret so that
no other ones can add files to his
subspace. A content-hash key is useful for updating and splitting files
since the old version of the file remains temporarily available while a new
version is being added to the system. There is more than one solutions proposed
to search for keys, including insertion of indirect files by users with
pointer to the real files, and publicizing public key compilations by users.
Once the file key is known, a user will ask its node to retrieve the file. This
node will check its own data store, and use its routing table to forward the
request to a neighboring node if it does not have a copy of the file. Requests
propagate as a steepest-ascent hill-climbing search with backtracking until
the file is found or the request times out. A similar search is performed to
insert new files. Similar keys are located and success is returned if the
hops-to-live is reached without any collisions. Essentially, a trend will
form where nodes become experts on similar keys located on the
same node, and caching brings copies of file closer to the requester. When
the system starts running out storage, the least recently used files are
replaced. The system achieves security by enforcing anonymous requesters
and senders, as well as employing a cryptographic protocol to add new nodes to
the system. Freenet does not assign responsibility for documents
to specific servers; instead, its lookups take the form of searches for
cached copies. This allows Freenet to provide a degree of anonymity, but
prevents it from guaranteeing retrieval of existing documents or from
providing low bounds on retrieval costs.

\myfig{chord_hash}{3 in}{An identifier circle consisting of the three nodes
0, 1, and 3. In this example, key 1 is located at node 1, key 2 at node 3,
and key 6 at node 0.}


Ion Stoica et al. \cite{Stoica} presented the Chord protocol that is designed to
map a key onto a node in a distributed, peer-to-peer network
whose size and composition change intermittently. Chord is proposed to meet
the challenges faced by large-scale peer-to-peer network, namely, load balance,
decentralization, scalability, availability and flexible naming. The Chord
protocol employs the consistent hashing function to acquire two $m$-bit
identifiers for the node and the key, respectively. The identifiers are ordered
in an identifier circle modulo $2^{m}$ ($m$ is in the range of $O(logN)$ and
$N$ is
the number of nodes in the network), using which the keys may be assigned
to the nodes with the successor node technique, as shown in Figure
\ref{chord_hash:fig}. Consistent hashing is designed
to let nodes enter and leave the network with minimal disruption. Further more,
it is proven that each node is responsible for at most $(1+\epsilon)K/N$ keys,
where $K$ is the total number of keys.
Each node, $n$, maintains a routing table with (at most) $m$ entries, called
the {\em finger table}. The $i^{th}$ entry in the table at node $n$ contains
the identity of the {\em first} node, $s$, that succeeds $n$ by at least
$2^{i-1}$ on the identifier circle, i.e., $s=successor(n+2^{i-1})$, where
$1 \leq i \leq m$. When a node $n$ looks for the node holding key $k$,
it searches
its finger table for the node $j$ whose ID most immediately precedes $k$, and
asks $j$ for the node it knows whose ID is closest to $k$. By repeating this
process, $n$ learns about nodes with IDs closer and closer to $k$. Eventually,
node $n$ finds the node holding $k$ in $O(logN)$ steps.
Also, Chord is designed to ease the additions and withdrawals
of nodes, and the main idea for achieving this is to find the new predecessor
and successor nodes on the identifier circle after addition/withdrawal
of nodes in the network. When multiple nodes join or fail, a stabilizing routine
is executed in the Chord in order to remap keys to the nodes so that the
integrity of the identifier circle is maintained. In a word, Chord features
simplicity, provable correctness and provable performance even in the face of
concurrent node arrivals and departures. However, Chord needs specific
mechanism to heal partitioned rings and security mechanism to tackle
safety issues, e.g., malicious or buggy set of participants,
which may present an incorrect view of
the Chord ring. Also, anonymity of participant is not taken into account
in Chord.



%\input{cr}

rpe.bbl
\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{AWSBL99}

\bibitem[{Aka}]{Akamai}
{Akamai Technologies, Inc}.
\newblock {\em A Distributed Infrastructure for e-Business --- Real Benefits,
  Measurable Returns}.

\bibitem[AR98]{Aggarwal}
Amit Aggarwal and Michael Rabinovich.
\newblock Performance of dynamic replication schemes for an internet hosting
  service.
\newblock Technical Report HPL-2001-8, AT\&T Labs, October 1998.

\bibitem[Aud]{Audiogalaxy}
Audiogalaxy.
\newblock http://www.audiogalaxy.com/.

\bibitem[AWSBL99]{Adjie-Winoto}
William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, and Jeremy Lilley.
\newblock The design and implementation of an intentional naming system.
\newblock In {\em Proceedings of the 17th ACM Symposium on Operating System
  Principals}, December 1999.

\bibitem[Bar96]{Bartal}
Yair Bartal.
\newblock Probabilistic approximation of metric space and its algorithmic
  applications.
\newblock In {\em 37th Annual IEEE Symposium on Foundations of Computer
  Science}, October 1996.

\bibitem[BAZF97]{Bhattacharjee}
S.~Bhattacharjee, M.~Ammar, E.~Zegura, and Z.~Fei.
\newblock Application-layer anycasting.
\newblock In {\em Proceedings of IEEE INFOCOM'97}, 1997.

\bibitem[BBM{\etalchar{+}}97]{Baentsch}
M.~Baentsch, L.~Baum, G.~Molter, S.~Rothkugel, and P.~Sturm.
\newblock Enhancing the web infrastructure - from caching to replication.
\newblock {\em IEEE Internet Computing}, pages 18--27, Mar-Apr 1997.

\bibitem[BM98]{Beck}
Micah Beck and Terry Moore.
\newblock The internet-2 distributed storage infrastructure project: An
  architecture for internet content channels.
\newblock In {\em Proceedings of the 3rd International WWW Caching Workshop},
  Manchester, UK, June 1998.

\bibitem[Bog83]{Boggs}
David~R. Boggs.
\newblock Internet broadcasting.
\newblock Ph.D. Thesis, available as Technical Report CSL-83-3, Xerox Palo Alto
  Research Center, October 1983.

\bibitem[CDD]{CDD101}
Cdd101: An introduction to content distribution and delivery.
\newblock http://www.cddcenter.com/101/.

\bibitem[{Cis}]{Cisco}
{Cisco Systems, Inc.}
\newblock {\em DistributedDirector. White paper.}
\newblock \url{http://www.cisco.com/warp/public/734/distdir/dd_wp.htm}.

\bibitem[CSWH00]{clarke00freenet}
Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore~W. Hong.
\newblock Freenet: A distributed anonymous information storage and retrieval
  system.
\newblock In {\em Workshop on Design Issues in Anonymity and Unobservability},
  pages 46--66, 2000.

\bibitem[DCTR01]{Day1}
M.~Day, B.~Cain, G.~Tomlinson, and P.~Rzewski.
\newblock A model for content internetworking.
\newblock Internet-Draft, March 2001.

\bibitem[edo]{edonkey2000}
edonkey2000.
\newblock http://www.edonkey2000.com/.

\bibitem[FBZA98]{Fei}
Zongming Fei, Samrat Bhattacharjee, Ellen~W. Zegura, and Mostafa~H. Ammar.
\newblock A novel server selection technique for improving the response time of
  a replicated service.
\newblock In {\em Proceedings of IEEE INFOCOM'98}, San Francisco, California
  USA, March 1998.

\bibitem[GC01]{Gritter}
Mark Gritter and David~R. Cheriton.
\newblock An architecture for content routing support in the internet.
\newblock In {\em Proceedings of the 3rd USENIX Symposium on Internet
  Technologies and Systems(USITS'01)}, San Francisco, CA, USA, March 2001.

\bibitem[GCR00]{Gadde}
Syam Gadde, Jeff Chase, and Michael Rabinovich.
\newblock Web caching and content distribution: A view from the interior.
\newblock In {\em Proceedings of the 5th International Web Caching and Content
  Delivery Workshop}, Lisbon, Portugal, May 2000.

\bibitem[GCTT00]{Green}
M.~Green, B.~Cain, G.~Tomlinson, and S.~Thomas.
\newblock Cdn peering architectural overview.
\newblock Internet-Draft, November 2000.

\bibitem[GJ79]{Garey}
Michael~R. Garey and David~S. Johnson.
\newblock Computers and intractability.
\newblock NY, NY:W.H.Freeman and Co., 1979.

\bibitem[Gnu]{Gnutella}
Gnutelliums.
\newblock http://www.gnutelliums.com/.

\bibitem[GS95]{Guyton}
James~D. Guyton and Michael~F. Schwartz.
\newblock Locating nearby copies of replicated internet servers.
\newblock In {\em Proceedings of ACM SIGCOMM'95}, pages 288--298, Cambridge,
  MA, August 1995.

\bibitem[JJJ{\etalchar{+}}00]{Jamin}
Sugih Jamin, Cheng Jin, Yixin Jin, Danny Raz, Yuval Shavitt, and Lixia Zhang.
\newblock On the placement of internet instrumentation.
\newblock In {\em Proceedings of IEEE INFOCOM 2000 Conference}, pages 295--304,
  Tel-Aviv, Israel, March 2000.

\bibitem[JJR{\etalchar{+}}01]{Jamin1}
Sugih Jamin, Cheng Jin, Anthony R.Kure, Danny Raz, and Yuval Shavitt.
\newblock Contrained mirror placement on the internet.
\newblock In {\em Proceedings of IEEE INFOCOM 2001 Conference}, Anchorage,
  Alaska USA, April 2001.

\bibitem[Kaz]{Kazaa}
Kazaa.
\newblock http://www.kazaa.com/.

\bibitem[KD99]{Korupolu2}
M.~Korupolu and M.~Dahlin.
\newblock Coordinated placement and replacement for large-scale distributed
  caches.
\newblock In {\em Proceedings of the 1999 IEEE Workshop on Internet
  Applications}, June 1999.

\bibitem[KLL{\etalchar{+}}97]{karger97consistent}
David Karger, Eric Lehman, Tom Leighton, Mathhew Levine, Daniel Lewin, and Rina
  Panigrahy.
\newblock Consistent hashing and random trees: Distributed caching protocols
  for relieving hot spots on the world wide web.
\newblock In {\em {ACM} Symposium on Theory of Computing}, pages 654--663, May
  1997.

\bibitem[KPR99]{Korupolu1}
M.~Korupolu, G.~Plaxton, and R.~Rajaraman.
\newblock Placement algorithms for hierarchical cooperative caching.
\newblock In {\em Proceedings of 10th ACM-SIAM SODA}, 1999.

\bibitem[KRR01]{Kangasharju1}
Jussi Kangasharju, James Roberts, and Keith~W. Ross.
\newblock Object replication strategies in content distribution network.
\newblock In {\em Proceedings of Sixth International Workshop on Web Caching
  and Content Distribution}, Boston, Massachusetts, June 2001.

\bibitem[KRS00]{Krishnan}
P.~Krishnan, Danny Raz, and Yuval Shavitt.
\newblock The cache location problem.
\newblock {\em IEEE/ACM Transactions on Networking}, 8(5), 2000.

\bibitem[KW00]{Katabi}
Dina Katabi and John Wroclawski.
\newblock A framework for scalable global ip-anycast(gia).
\newblock In {\em Proceedings of ACM SIGCOMM 2000}, pages 3--15, Stockholm,
  Sweden, August 2000.

\bibitem[Nap]{Napster}
Napster.
\newblock http://www.napster.com/.

\bibitem[PMM93]{Partridge}
Craig Partridge, Trevor Mendez, and Walter Milliken.
\newblock Host anycasting service.
\newblock IETF RFC 1546, November 1993.

\bibitem[QPV01]{Qiu}
Lili Qiu, Venkata~N. Padmanabhan, and Geoffrey~M. Voelker.
\newblock On the placement of web server replicas.
\newblock In {\em Proceedings of IEEE INFOCOM 2001 Conference}, Anchorage,
  Alaska USA, April 2001.

\bibitem[RD01]{rowstron01pastry}
Antony Rowstron and Peter Druschel.
\newblock Pastry: Scalable, decentralized object location, and routing for
  large-scale peer-to-peer systems.
\newblock {\em Lecture Notes in Computer Science}, 2218:329--??, 2001.

\bibitem[RFH{\etalchar{+}}01]{ratnasamy01scalable}
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker.
\newblock A scalable content addressable network.
\newblock In {\em Proceedings of ACM SIGCOMM 2001}, 2001.

\bibitem[RGE01]{Radoslavov}
Pavlin Radoslavov, Ramesh Govindan, and Deborah Estrin.
\newblock Topology-informed internet replica placement.
\newblock In {\em Proceedings of Sixth International Workshop on Web Caching
  and Content Distribution}, Boston, Massachusetts, June 2001.

\bibitem[sha95]{sha}
Fips 180-1. secure hash standard.
\newblock U.S. Department of Commerce/NIST, National Technical Information
  Service, 1995.

\bibitem[SMK{\etalchar{+}}01]{Stoica}
I.~Stoica, R.~Morris, D.~Karger, M.F. Kasshoek, and H.~Balakrishnan.
\newblock Chord: A scalable peer-to-peer lookup service for internet
  applications.
\newblock In {\em Proceedings of ACM SIGCOMM'01}, San Diego, CA, September
  2001.

\bibitem[Vaz99]{Vazirani}
Vijay Vazirani.
\newblock Approximation methods.
\newblock Springer-Verlag, 1999.

\bibitem[WCS93]{Wood}
David C.~M. Wood, Sean~S. Coleman, and Michael~F. Schwartz.
\newblock Fremont: A system for discovering network characteristics and
  problems.
\newblock In {\em Proceedings of the USENIX Winder Conference}, pages 335--348,
  January 1993.

\bibitem[Wina]{WinMx}
Winmx.
\newblock http://www.winmx.com/.

\bibitem[{Win}b]{WindDance}
{WindDance Networks Corp.}
\newblock {\em Webchallenger}.
\newblock
  \url{http://www.winddancenet.com/webchallenger/products/frame_products.htm}.

\bibitem[YCE{\etalchar{+}}97]{Yoshikawa}
Chad Yoshikawa, Brent Chun, Paul Eastham, Amin Vahdat, Thomas Anderson, and
  David Culler.
\newblock Using smart clients to build scalable services.
\newblock In {\em Proceedings of the USENIX 1997 Annual Technical Conference},
  Anaheim, California USA, January 1997.

\bibitem[ZDH{\etalchar{+}}02]{zhao02brocade}
B.~Zhao, Y.~Duan, L.~Huang, A.~Joseph, and J.~Kubiatowicz.
\newblock Brocade: Landmark routing on overlay networks, 2002.

\bibitem[ZKJ01]{zhao01tapestry}
B.~Y. Zhao, J.~D. Kubiatowicz, and A.~D. Joseph.
\newblock Tapestry: An infrastructure for fault-tolerant wide-area location and
  routing.
\newblock Technical Report UCB/CSD-01-1141, UC Berkeley, April 2001.

\end{thebibliography}
