vides a new abstraction potentially of use to any applica Coral tion that needs to locate nearby instances of resources on the network. Coral also introduces an epidemic clustering algorithm that exploits distributed network measurements Coral Furthermore, Coral is the first peer-to-peer key/value in- 8,11 dex that can scale to many stores of the same key without hot-spot congestion, thanks to a new rate-limiting tech- Coral 9 Corals nique. Finally, CoralCdN contains the first peer-to-peer DNS redirection infrastructure, allowing the system to dns sr dns srv http httpprx inter-operate with unmodified web browsers Measurements of coralcdn demonstrate that it al www.x.com 7 nvod. net/ lows under-provisioned web sites to achieve dramatically www.x.comt5 10 igher capacity, and its clustering provides quantitatively Resolver better performance than locality-unaware systems owser The remainder of this paper is structured as follows Section 2 provides a high-level description of CoralCDN, Figure 1: Using CoralCDN, the steps involved in resolving a and Section 3 describes its DNS system and web caching Coralized URL and returning the corresponding fi le, per Sec- components.In Section 4, we describe the Coral index- tion 2.2. Rounded boxes represent CoralCDN nodes running ing infrastructure its underlying Dsht layers and the coRal, Dns, and Http servers Solid arrows correspond to clustering algorithms. Section 5 includes an implementa- Coral RPCs, dashed arrows to DNS traffi c, dotted-dashed arrows tion overview and Section 6 presents experimental results to network probes and dotted arrows to Http traffi c Section 7 describes related work. Section 8 discusses fu ture work. and Section 9 concludes websitesAllrelativelinksandhttpredirectsare 2 The Coral Content distribution Network automatically Coralized The Coral Content Distribution Network( CoralCDN) is 2.2 System Overview composed of three main parts:(1)a network of coop- Figure I shows the steps that occur when a client accesses Http networkofDnsnameserversfornyucd.netthatmapaCoralizedUrl,suchashttp://www.x.com clients to nearby Coral Httpproxiesand(3)theundernyud.net:8090/,usingastandardwebbrowser.the lying Coral indexing infrastructure and clustering machin two main stages-dns redirection and Http request ery on which the first two applications are built. handling-both use the coral indexing infrastructure 2.1 Usage models 1.aclientsendsaDnsrequestforwww.x.com nyud. net to its local resolver To enable immediate and incremental deployment, Coral- 2. The client's resolver attempts to resolve the host- CDN is transparent to clients and requires no software or name using some Coral DNS server(s), possibly plug-in installation. CoralCdN can be used in a variety of starting at one of the few registered under the. net Publishers. a web site publisher for x. com can 3. Upon receiving a query, a Coral DNS server probes change selected URLs in their web pages to"Cor the client to determines its round-trip-time and last alized"urls,suchashttp://www.x.com few network hops nyu. net: 8090/y. jpg 4. Based on the probe results, the DNS server checks Third-parties. An interested third-part andor Http proxies near the clients resolver poster to a web portal or a Usenet group-can Coral e a URl before publishing it, causing all embedded The DNS server replies, returning any servers found through Coral in the previous step, if none were relative links to use Coralcdn as well a random set of nam Users. Coral-aware users can manually construct proxies. In either case, if the DNS server is close to Coralized URls when surfing slow or overloaded the client, it only returns nodes that are close to itself i While Corals Http proxy defi nitely provides (see Section 3.1) it is not an Http proxy in the strict Rfc2616 sense it serves requests 6. The client 's resolver returns the address of a coral that are syntactically formatted for an ordinary HttpseRver Httpproxyforwww.x.com.nyud.net.vides a new abstraction potentially of use to any applica￾tion that needs to locate nearby instances of resources on the network. Coral also introduces an epidemic clustering algorithm that exploits distributed network measurements. Furthermore, Coral is the first peer-to-peer key/value in￾dex that can scale to many stores of the same key without hot-spot congestion, thanks to a new rate-limiting tech￾nique. Finally, CoralCDN contains the first peer-to-peer DNS redirection infrastructure, allowing the system to inter-operate with unmodified web browsers. Measurements of CoralCDN demonstrate that it al￾lows under-provisioned web sites to achieve dramatically higher capacity, and its clustering provides quantitatively better performance than locality-unaware systems. The remainder of this paper is structured as follows. Section 2 provides a high-level description of CoralCDN, and Section 3 describes its DNS system and web caching components. In Section 4, we describe the Coral index￾ing infrastructure, its underlying DSHT layers, and the clustering algorithms. Section 5 includes an implementa￾tion overview and Section 6 presents experimental results. Section 7 describes related work, Section 8 discusses fu￾ture work, and Section 9 concludes. 2 The Coral Content Distribution Network The Coral Content Distribution Network (CoralCDN) is composed of three main parts: (1) a network of coop￾erative HTTP proxies that handle users’ requests,1 (2) a network of DNS nameservers for nyucd.net that map clients to nearby Coral HTTP proxies, and (3) the under￾lying Coral indexing infrastructure and clustering machin￾ery on which the first two applications are built. 2.1 Usage Models To enable immediate and incremental deployment, Coral￾CDN is transparent to clients and requires no software or plug-in installation. CoralCDN can be used in a variety of ways, including: • Publishers. A web site publisher for x.com can change selected URLs in their web pages to “Cor￾alized” URLs, such as http://www.x.com. nyud.net:8090/y.jpg. • Third-parties. An interested third-party—e.g., a poster to a web portal or a Usenet group—can Coral￾ize a URL before publishing it, causing all embedded relative links to use CoralCDN as well. • Users. Coral-aware users can manually construct Coralized URLs when surfing slow or overloaded 1While Coral’s HTTP proxy definitely provides proxy functionality, it is not an HTTP proxy in the strict RFC2616 sense; it serves requests that are syntactically formatted for an ordinary HTTP server. .nyud.net/ www.x.com www.x.com .nyud.net dns srv http prx Coral dns srv http prx Coral dns srv http prx Coral dns srv http prx Coral dns srv http prx Coral Resolver Browser dns srv 4 4 9 8, 11 5 1 6 10 2 7 3 dns srv http prx Coral http prx Coral Figure 1: Using CoralCDN, the steps involved in resolving a Coralized URL and returning the corresponding file, per Sec￾tion 2.2. Rounded boxes represent CoralCDN nodes running Coral, DNS, and HTTP servers. Solid arrows correspond to Coral RPCs, dashed arrows to DNS traffic, dotted-dashed arrows to network probes, and dotted arrows to HTTP traffic. web sites. All relative links and HTTP redirects are automatically Coralized. 2.2 System Overview Figure 1 shows the steps that occur when a client accesses a Coralized URL, such as http://www.x.com. nyud.net:8090/, using a standard web browser. The two main stages—DNS redirection and HTTP request handling—both use the Coral indexing infrastructure. 1. A client sends a DNS request for www.x.com. nyud.net to its local resolver. 2. The client’s resolver attempts to resolve the host￾name using some Coral DNS server(s), possibly starting at one of the few registered under the .net domain. 3. Upon receiving a query, a Coral DNS server probes the client to determines its round-trip-time and last few network hops. 4. Based on the probe results, the DNS server checks Coral to see if there are any known nameservers and/or HTTP proxies near the client’s resolver. 5. The DNS server replies, returning any servers found through Coral in the previous step; if none were found, it returns a random set of nameservers and proxies. In either case, if the DNS server is close to the client, it only returns nodes that are close to itself (see Section 3.1). 6. The client’s resolver returns the address of a Coral HTTP proxy for www.x.com.nyud.net. 2