6 multi-level multi-level multi-level traceroute 43210 0.1 0.2040.60.8 0.2040.60.8 Fraction of Requests raction of Requests Figure 6: Latencies for proxy to get keys from Coral 6 Asia, multi-level bination of hosts sharing networks with CoralProxies- 05 within the same IP prefix as registered with Coral-and hosts without. Although the multi-level network using 3 traceroute provides the lowest latency the multi-level system without traceroute also performs better than the single-level system. Clustering has a clear performance benefit for clients, and this benefit is partic ularly apparent for poorly-connected hosts Figure 6 shows the latency of get operations, as seen by 0.6 CoralProxies when they lookup URLS in Coral ( Step 8 of Fraction of Requests Section 2.2). We plot the get latency on the single level-0 system vs. the multi-level systems. The multi-level sys- Request latency(sec) All nodes Asian nodes tem is 2-5 times faster up to the 80% percentile. After the 98%p percentile ngle-level 0.两99.542.528.01 the single-level system is actually faster multi-level0.31.170044.16 Under heavy packet loss, the multi-system requires a few multi-level, traceroute 0.192 more timeouts as it traverses its hierarchy levels Figure 5: End-to-End client latency for requests for Coralized 6.3 Clustering URLS, comparing the effect of single-level vS. multi-level clus- ters and of using traceroute during DNS redirection. The top Figure 7 illustrates a snapshot of the clusters from the pre graph includes all nodes; the bottom only nodes in Asia. vious experiments, at the time when clients began fetch ing URLS (30 minutes out). This map is meant to provide a qualitative feel for the organic nature of cluster devel discovered CoralProxy. The proxy attempts to fulfill the opment, as opposed to offering any quantitative measure- client request first through its local cache, then through ments. On both maps, each unique, non-singleton clus- Coral, and finally through the origin web server. We note ter within the network is assigned a letter. We have plot- that CoralProxy implements cut-through routing by for- ted the location of our nodes by latitude/longitude coor- ding data to the client prior to receiving the entire file. dinates. If two nodes belong to the same cluster, they are latency of clien ort three results: ( 1)the distribution of represented by the same letter. As each PlanetLab site These fis solid line), (2)the distribution of latencies of clients using expresses the number of nodes at that site that belong to multi-level clusters(dashed), and (3)the same hierarchi- the same cluster. For example, the very large"H(world cal network, but using traceroute during DNS resolution map)and"A(U.S. map) correspond to nodes collocated to map clients to nearby proxies( dotted) at U.C. Berkeley. We did not include singleton clusters on All clients ran on the same subnet (and hos he maps to improve readability, post-run analysis showed oralProxy in our experimental setup This would not be that such nodes RTTs to others(surprisingly, sometimes the case in the real deployment: We would expect a com- even at the same site)were above the coral thresholds0 1 2 3 4 5 6 7 0 0.2 0.4 0.6 0.8 1 Latency (sec) Fraction of Requests single-level multi-level multi-level, traceroute 0 1 2 3 4 5 6 7 0 0.2 0.4 0.6 0.8 1 Latency (sec) Fraction of Requests Asia, single-level Asia, multi-level Asia, multi-level, traceroute Request latency (sec) All nodes Asian nodes 50% 96% 50% 96% single-level 0.79 9.54 2.52 8.01 multi-level 0.31 4.17 0.04 4.16 multi-level, traceroute 0.19 2.50 0.03 1.75 Figure 5: End-to-End client latency for requests for Coralized URLs, comparing the effect of single-level vs. multi-level clus￾ters and of using traceroute during DNS redirection. The top graph includes all nodes; the bottom only nodes in Asia. discovered CoralProxy. The proxy attempts to fulfill the client request first through its local cache, then through Coral, and finally through the origin web server. We note that CoralProxy implements cut-through routing by for￾warding data to the client prior to receiving the entire file. These figures report three results: (1) the distribution of latency of clients using only a single level-0 cluster (the solid line), (2) the distribution of latencies of clients using multi-level clusters (dashed), and (3) the same hierarchi￾cal network, but using traceroute during DNS resolution to map clients to nearby proxies (dotted). All clients ran on the same subnet (and host, in fact) as a CoralProxy in our experimental setup. This would not be the case in the real deployment: We would expect a com- 0.01 0.1 1 10 0 0.2 0.4 0.6 0.8 1 Latency (sec) Fraction of Requests single-level multi-level Figure 6: Latencies for proxy to get keys from Coral. bination of hosts sharing networks with CoralProxies— within the same IP prefix as registered with Coral—and hosts without. Although the multi-level network using traceroute provides the lowest latency at most percentiles, the multi-level system without traceroute also performs better than the single-level system. Clustering has a clear performance benefit for clients, and this benefit is partic￾ularly apparent for poorly-connected hosts. Figure 6 shows the latency of get operations, as seen by CoralProxies when they lookup URLs in Coral (Step 8 of Section 2.2). We plot the get latency on the single level-0 system vs. the multi-level systems. The multi-level sys￾tem is 2-5 times faster up to the 80% percentile. After the 98% percentile, the single-level system is actually faster: Under heavy packet loss, the multi-system requires a few more timeouts as it traverses its hierarchy levels. 6.3 Clustering Figure 7 illustrates a snapshot of the clusters from the pre￾vious experiments, at the time when clients began fetch￾ing URLs (30 minutes out). This map is meant to provide a qualitative feel for the organic nature of cluster devel￾opment, as opposed to offering any quantitative measure￾ments. On both maps, each unique, non-singleton clus￾ter within the network is assigned a letter. We have plot￾ted the location of our nodes by latitude/longitude coor￾dinates. If two nodes belong to the same cluster, they are represented by the same letter. As each PlanetLab site usually collocates several servers, the size of the letter expresses the number of nodes at that site that belong to the same cluster. For example, the very large “H” (world map) and “A” (U.S. map) correspond to nodes collocated at U.C. Berkeley. We did not include singleton clusters on the maps to improve readability; post-run analysis showed that such nodes’ RTTs to others (surprisingly, sometimes even at the same site) were above the Coral thresholds. 10