7.TheclientsendstheHttprequesthttp://www..nodes(level,counttargetservices):Returns x.com.nyud.net8090/tothespecifiedproxy count neighbors belonging to the node's cluster as If the proxy is caching the file locally, it returns the specified by level. target, if supplied, specifies the file and stops. Otherwise, this process continues IP address of a machine to which the returned nodes 8. The proxy looks up the web objects URL in Coral. would ideally be near. Coral can probe target and 9. If Coral returns the address of a node caching the exploit network topology hints stored in the dsht object, the proxy fetches the object from this node to satisfy the request. If services is specified, Coral Otherwise, the proxy downloads the object from the will only return nodes running the particular service, originserverwww.x.com(notshown e. g., an Http proxy or Dns server 10. The proxy stores the web object and returns it to the levels(: Returns the number of levels in Corals hi- client browser erarchy and their corresponding rtt thresholds 11. The proxy stores a reference to itself in Coral, recording the fact that is now caching the URL The next section describes the design of CoralCDN's Dns redirector and Http proxy-especially with regard 2.3 The Coral Indexing abstraction to their use of Corals dsht abstraction and clustering hierarchy--before returning to Coral in Section This section introduces the Coral indexing infrastructu as used by CoralCDN Coral provides a distributed sloppy 3 Application-Layer Components hash table(dsht) abstraction. DSHTs are designed for applications storing soft-state key/value pairs, where mul- The Coral DNS server directs browsers fetching Coralized tiple values may be stored under the same key Coral- Urls to cOral Http proxies attempting to find ones near CDN uses this mechanism to map a variety of types of he requesting client These Http proxies exploit each key onto addresses of CoralCDN nodes. In particular, it others caches in such a way as to minimize both transfer uses DSHTs to find Coral nameservers topologically close latency and the load on origin web servers clients'networks, to find Http proxies caching particu- 3.1 The Coral Dns server lar web objects, and to locate nearby Coral nodes for the purposes of minimizing internal request latency The Coral dns server. dnssry. returns ip addresses of Instead of one global overlay as in [5, 14, 27], each Coral Http proxies when browsers look up the host Coral node belongs to several distinct DSHTs called clus- names in Coralized URLS. To improve locality, it at ters. Each cluster is characterized by a maximum desired tempts to return proxies near requesting clients. In partic network round-trip-time(RTT) we call the diameter. The ular, whenever a dNS resolver(client) contacts a nearby system is parameterized by a fixed hierarchy of diameters dnssrv instance, dnssrv both returns proxies within an ap- known as levels. Every node is a member of one DSht propriate cluster, and ensures that future DNS requests at each level. A group of nodes can form a level-i cluster from that client will not need to leave the cluster. Using if a high-enough fraction their pair-wise RTTs are below the nodes function, dnssrv also exploits Corals on-the- the level-i diameter threshold. Although Corals imple- fly network measurement capabilities and stored topology mentation allows for an arbitrarily-deep dShT hierarchy, hints to increase the chances of clients discovering nearby this paper describes a three-level hierarchy with thresh- DNS servers olds of oo, 60 msec, and 20 msec for level-0,-1, and-2 More specifically, every instance of dnssrv is an au- clusters respectively. Coral queries nodes in higher-level, thoritative nameserver for the domain nyucd. net. AS- fast clusters before those in lower-level, slower clusters. suming a 3-level hierarchy, as Coral is generally config- ThisbothreducesthelatencyoflookupsandincreasesureddnssrvmapsanydomainnameendinghttpL2 the chances of returning values stored by nearby nodes L1. l0. nyucd. net to one or more cOral Httpprox Coral provides the following interface to higher-level ies.(For an(n+ 1)-level hierarchy, the domain name applicatior is extended out to Ln in the obvious way. ) Because put(key,val,ttl,[llEvels):InsertsamappingfromDnsDnaMealias[4),nyud.netwithtargethttp the key to some arbitrary value, specifying the time- L2 L1. LO nyucd. net. Any domain name ending to-live of the reference. The caller nyud. net is therefore equivalent to the same name with specifyasubsetoftheclusterhierarchytorestrictsuffixhttp.L2.l1.lo.nyucd.net,allowingCor- the operation to certain levels alizedUrlstohavethemoreconciseformhttp:// .get(key,Llevels):reTrievessomesubsetoftheval-www.x.com.nyud.net:8090/ es stored under a key. Again, one can optionally dnssrv assumes that web browsers are generally pecify a subset of the cluster hierarchy. to their resolvers on the network so that the source7. The client sends the HTTP request http://www. x.com.nyud.net:8090/ to the specified proxy. If the proxy is caching the file locally, it returns the file and stops. Otherwise, this process continues. 8. The proxy looks up the web object’s URL in Coral. 9. If Coral returns the address of a node caching the object, the proxy fetches the object from this node. Otherwise, the proxy downloads the object from the origin server, www.x.com (not shown). 10. The proxy stores the web object and returns it to the client browser. 11. The proxy stores a reference to itself in Coral, recording the fact that is now caching the URL. 2.3 The Coral Indexing Abstraction This section introduces the Coral indexing infrastructure as used by CoralCDN. Coral provides a distributed sloppy hash table (DSHT) abstraction. DSHTs are designed for applications storing soft-state key/value pairs, where mul￾tiple values may be stored under the same key. Coral￾CDN uses this mechanism to map a variety of types of key onto addresses of CoralCDN nodes. In particular, it uses DSHTs to find Coral nameserverstopologically close clients’ networks, to find HTTP proxies caching particu￾lar web objects, and to locate nearby Coral nodes for the purposes of minimizing internal request latency. Instead of one global overlay as in [5, 14, 27], each Coral node belongs to several distinct DSHTs called clus￾ters. Each cluster is characterized by a maximum desired network round-trip-time (RTT) we call the diameter. The system is parameterized by a fixed hierarchy of diameters known as levels. Every node is a member of one DSHT at each level. A group of nodes can form a level-i cluster if a high-enough fraction their pair-wise RTTs are below the level-i diameter threshold. Although Coral’s imple￾mentation allows for an arbitrarily-deep DSHT hierarchy, this paper describes a three-level hierarchy with thresh￾olds of ∞, 60 msec, and 20 msec for level-0, -1, and -2 clusters respectively. Coral queries nodes in higher-level, fast clusters before those in lower-level, slower clusters. This both reduces the latency of lookups and increases the chances of returning values stored by nearby nodes. Coral provides the following interface to higher-level applications: • put(key, val, ttl, [levels]): Inserts a mapping from the key to some arbitrary value, specifying the time￾to-live of the reference. The caller may optionally specify a subset of the cluster hierarchy to restrict the operation to certain levels. • get(key, [levels]): Retrieves some subset of the val￾ues stored under a key. Again, one can optionally specify a subset of the cluster hierarchy. • nodes(level, count, [target], [services]): Returns count neighbors belonging to the node’s cluster as specified by level. target, if supplied, specifies the IP address of a machine to which the returned nodes would ideally be near. Coral can probe target and exploit network topology hints stored in the DSHT to satisfy the request. If services is specified, Coral will only return nodes running the particular service, e.g., an HTTP proxy or DNS server. • levels(): Returns the number of levels in Coral’s hi￾erarchy and their corresponding RTT thresholds. The next section describes the design of CoralCDN’s DNS redirector and HTTP proxy—especially with regard to their use of Coral’s DSHT abstraction and clustering hierarchy—before returning to Coral in Section 4. 3 Application-Layer Components The Coral DNS server directs browsersfetching Coralized URLs to Coral HTTP proxies, attempting to find ones near the requesting client. These HTTP proxies exploit each others’ caches in such a way as to minimize both transfer latency and the load on origin web servers. 3.1 The Coral DNS server The Coral DNS server, dnssrv, returns IP addresses of Coral HTTP proxies when browsers look up the host￾names in Coralized URLs. To improve locality, it at￾tempts to return proxies near requesting clients. In partic￾ular, whenever a DNS resolver (client) contacts a nearby dnssrv instance, dnssrv both returns proxies within an ap￾propriate cluster, and ensures that future DNS requests from that client will not need to leave the cluster. Using the nodes function, dnssrv also exploits Coral’s on-the- fly network measurement capabilities and stored topology hints to increase the chances of clients discovering nearby DNS servers. More specifically, every instance of dnssrv is an au￾thoritative nameserver for the domain nyucd.net. As￾suming a 3-level hierarchy, as Coral is generally config￾ured, dnssrv maps any domain name ending http.L2. L1.L0.nyucd.net to one or more Coral HTTP prox￾ies. (For an (n + 1)-level hierarchy, the domain name is extended out to Ln in the obvious way.) Because such names are somewhat unwieldy, we established a DNS DNAME alias [4], nyud.net, with target http. L2.L1.L0.nyucd.net. Any domain name ending nyud.net is therefore equivalent to the same name with suffix http.L2.L1.L0.nyucd.net, allowing Cor￾alized URLs to have the more concise form http:// www.x.com.nyud.net:8090/. dnssrv assumes that web browsers are generally close to their resolvers on the network, so that the source ad- 3