cordingly; (2)cluster information is accumulated to drive preference function 8 that shifts every hour. A node se- cluster management. as described next lects the larger cluster only if the following holds 4. 4 Joining and managing clusters log(size A)-log(size b)>8(min(age A, ageB) As in any peer-to-peer system, a peer contacts an existing node to join the system. Next, a new node makes sev- where age is the current time minus the cluster eral queries to seed its routing tables. However, for non- time. Otherwise, a node simply selects the cluster with global clusters, Coral adds one important requirement: A the lower cluster ID node will only join an acceptable cluster, where accept- We use a square wave function for o that takes a value ability requires that the latency to 80% of the nodes be 0 on an even number of hours and 2 on an odd number below the cluster s threshold. A node can easily deter- For clusters of disproportionate size, the selection func mine whether this condition holds by recording minimum tion immediately favors the larger cluster. Otherwise,&'s transition perturbs clusters to a steady state. 4 round-trip-times (RTTs)to some subset of nodes belong- In either case, a node that switches clusters still remains While nodes learn about clusters as a side effect of nor- in the routing tables of nodes in its old cluster. Thus, mal lookups, Coral also exploits its DSHTs to store hints. old neighbors will still contact it and learn of its new. When Coral starts up, it uses its built-in fast traceroute potentially-better, cluster. This produces an avalanche ef- mechanism(described in Section 3. 1) to determine the ad- fect as more and more nodes switch to the larger cluster dresses of routers up to five hops out. Excluding any pri- This merging of clusters is very beneficial. While a small vate("RFC1918")iP addresses, Coral uses these router cluster diameter provides fast lookup, a large cluster ca- addresses as keys under which to index clustering hints in pacity increases the hit rate its DSHTS. More specifically, a node R stores mappings from each router address to its own IP address and UDP 5 Implementation port number. When a new node S, sharing a gateway with R, Joins the network, it will find one or more of R's hints The Coral indexing system is composed of a client library and quickly cluster with it, assuming R is, in fact, near s. and stand-alone daemon. The simple client library allows applications such as our Dns server and Http ProxY,to In addition, nodes store mappings to themselves using connect to and interface with the Coral daemon. Coral is as keys any IP subnets they directly connect to and the 24-bit prefixes of gateway router addresses. These prefix 4,000 lines ofC++. the DNS server, dnssrv, is 2, 000lines ofC++,andthehttpproxyisanadditional4,000lines hints are of use to Coral's level function, which tracer- All three components use the asynchronous I/O libra outes clients in the other direction addresses on forward and reverse traceroute paths often share 24-bit prefixes. provided by the SFS toolkit [19] and are structured by Nodes continuously collect clustering information from asynchronous events and callbacks. Coral network com- peers: All RPCs include round-trip-times, cluster mem- bership, and estimates of cluster size. Every five m run Coral on Linux, OpenBSD, FreeBSD, and Mac OS X utes, each node considers changing its cluster member- ship based on this collected data. If this collected data 6 Evaluation indicates that an alternative candidate cluster is desirable the node first validates the collected data by contacting port our following hypotheses.rimental results that sup- In this section, we provide ex several nodes within the candidate cluster by routing to selected keys. A node can also form a new singleton clus- ter when 50% of its accesses to members of its present 1. Coralcdn dramatically reduces load on servers, cluster do not meet the rtt constraints solving the"flash crowd problem If probes indicate that 80% of a cluster's nodes are 2. Clustering provides performance gains for popular within acceptable TTLs and the cluster is larger, it re- data, resulting in good client performance places a node's current cluster. If multiple clusters are acceptable, then Coral chooses the largest cluster 3. Coral naturally forms suitable clusters Unfortunately, Coral has only rough approximations of 4. Coral prevents hot spots within its indexing system cluster size, based on its routing-table size. If nearby clus- ters a and B are of similar sizes. inaccurate estimations Should clusters of similar size continuously exchange could lead to oscillation as nodes flow back-and-forth(al- when d is zero, as soon as d transitions, nodes will all fbw to the though we have not observed such behavior). To perturb the estimations hit"with one around 2 2-times larger), the node an oscillating system into a stable state, Coral employs a fbw to the larger one when 8 returns to zerocordingly; (2) cluster information is accumulated to drive cluster management, as described next. 4.4 Joining and Managing Clusters As in any peer-to-peer system, a peer contacts an existing node to join the system. Next, a new node makes sev￾eral queries to seed its routing tables. However, for non￾global clusters, Coral adds one important requirement: A node will only join an acceptable cluster, where accept￾ability requires that the latency to 80% of the nodes be below the cluster’s threshold. A node can easily deter￾mine whether this condition holds by recording minimum round-trip-times (RTTs) to some subset of nodes belong￾ing to the cluster. While nodes learn about clusters as a side effect of nor￾mal lookups, Coral also exploits its DSHTs to store hints. When Coral starts up, it uses its built-in fast traceroute mechanism (described in Section 3.1) to determine the ad￾dresses of routers up to five hops out. Excluding any pri￾vate (“RFC1918”) IP addresses, Coral uses these router addresses as keys under which to index clustering hints in its DSHTs. More specifically, a node R stores mappings from each router address to its own IP address and UDP port number. When a new node S, sharing a gateway with R, joins the network, it will find one or more of R’s hints and quickly cluster with it, assuming R is, in fact, near S. In addition, nodes store mappings to themselves using as keys any IP subnets they directly connect to and the 24-bit prefixes of gateway router addresses. These prefix hints are of use to Coral’s level function, which tracer￾outes clients in the other direction; addresses on forward and reverse traceroute paths often share 24-bit prefixes. Nodes continuously collect clustering information from peers: All RPCs include round-trip-times, cluster mem￾bership, and estimates of cluster size. Every five min￾utes, each node considers changing its cluster member￾ship based on this collected data. If this collected data indicates that an alternative candidate cluster is desirable, the node first validates the collected data by contacting several nodes within the candidate cluster by routing to selected keys. A node can also form a new singleton clus￾ter when 50% of its accesses to members of its present cluster do not meet the RTT constraints. If probes indicate that 80% of a cluster’s nodes are within acceptable TTLs and the cluster is larger, it re￾places a node’s current cluster. If multiple clusters are acceptable, then Coral chooses the largest cluster. Unfortunately, Coral has only rough approximations of cluster size, based on its routing-table size. If nearby clus￾ters A and B are of similar sizes, inaccurate estimations could lead to oscillation as nodes flow back-and-forth (al￾though we have not observed such behavior). To perturb an oscillating system into a stable state, Coral employs a preference function δ that shifts every hour. A node se￾lects the larger cluster only if the following holds:   log(sizeA) − log(sizeB)    > δ (min(age A, ageB)) where age is the current time minus the cluster’s creation time. Otherwise, a node simply selects the cluster with the lower cluster ID. We use a square wave function for δ that takes a value 0 on an even number of hours and 2 on an odd number. For clusters of disproportionate size, the selection func￾tion immediately favors the larger cluster. Otherwise, δ’s transition perturbs clusters to a steady state.4 In either case, a node that switches clusters still remains in the routing tables of nodes in its old cluster. Thus, old neighbors will still contact it and learn of its new, potentially-better, cluster. This produces an avalanche ef￾fect as more and more nodes switch to the larger cluster. This merging of clusters is very beneficial. While a small cluster diameter provides fast lookup, a large cluster ca￾pacity increases the hit rate. 5 Implementation The Coral indexing system is composed of a client library and stand-alone daemon. The simple client library allows applications, such as our DNS server and HTTP proxy, to connect to and interface with the Coral daemon. Coral is 14,000 lines of C++, the DNS server, dnssrv, is 2,000 lines of C++, and the HTTP proxy is an additional 4,000 lines. All three components use the asynchronous I/O library provided by the SFS toolkit [19] and are structured by asynchronous events and callbacks. Coral network com￾munication is via RPC over UDP. We have successfully run Coral on Linux, OpenBSD, FreeBSD, and Mac OS X. 6 Evaluation In this section, we provide experimental results that sup￾port our following hypotheses: 1. CoralCDN dramatically reduces load on servers, solving the “flash crowd” problem. 2. Clustering provides performance gains for popular data, resulting in good client performance. 3. Coral naturally forms suitable clusters. 4. Coral prevents hot spots within its indexing system. 4Should clusters of similar size continuously exchange members when δ is zero, as soon as δ transitions, nodes will all flow to the cluster with the lower cluster id. Should the clusters oscillate when δ = 2 (as the estimations “hit” with one around 2 2 -times larger), the nodes will all flow to the larger one when δ returns to zero. 8