H208842 near Distance to Hotspot √+ A Figure 8: The total number of put RPCs hitting each Coral node per minute, sorted by distance from node Id to target X noda level-0 cluster. At the same time all Planetlab nodes be- gan to issue back-to-back put/get requests at their max imum(non-concurrent)rates. All operations referenced Figure 7: World view of level-1 clusters(60 msec threshold), the same key, the values stored during put requests were and United States view of level-2 clusters(20 msec threshold) Each unique, non-singleton cluster is assigned a letter; the randomized. On average, each node issued 400 put/get of the letter corresponds to collocated nodes in the same cluster. operation pairs per second, for a total of approximately 12 million put/get requests per minute, although only a The world map shows that Coral found natural divi- get requests are satisfied locally. Once it is loaded, each sions between sets of nodes along geospatial lines at a 60 node only allows the leakage rate B RPCs"through"it per the most dramatic being the Eastern U.S. (70 nodes), the The graphs show the number of put RPCs that hit each Western U.S.(37 nodes), and Europe(19 nodes). The node in steady-state, sorted by the XOR distance of the close correlation between network and physical distance node's id to the key. During the first minute, the clos- suggests that speed-of-light delays dominate round-trip- est node received 106 put RPCs. In the second minute, times. Note that, as we did not plot singleton clusters, the map does not include three Asian nodes(in Japan, Taiwan, as shown in Figure 8, the system reached steady-state and the Philippines, respectively) with the closest node receiving 83 put RPCs per minute Recall that our equation in Section 4. 2 predicts that it The United States map shows level-2 clusters again should receive(B. log n)=108 RPCs per minute.The roughly separated by physical locality. The map shows plot strongly emphasizes the efficacy of the leakage rate 16 distinct clusters; obvious clusters include California B=12, as the number of RPCs received by the majority (22 nodes ), the Pacific Northwest(9 nodes), the South, the of nodes is a low multiple of 12 Midwest,etc. The Northeast Corridor cluster contains 29 No nodes on the far side of the graph received any nodes, stretching from North Carolina to Massachusetts. RPCS. Corals routing algorithm explains this condition One interesting aspect of this map is the three separate, these nodes begin routing by flipping their ID's most- non-singleton clusters in the San Francisco Bay Area. significant bit to match the key's, and they subsequently Close examination of individual RTTs between these sites contact a node on the near side. We have omitted the graph shows widely varying latencies; Coral clustered correctly of get RPCs: During the first minute, the most-loaded given the underlying network topology node received 27 RPCs; subsequently, the key was widel distributed and the system quiesced 6.4 Load Balancing Finally, Figure 8 shows the extent to which a DShT bal-7 Related work ances requests to the same key ID. In this experiment, 3 nodes on each of the earlier hosts for a to- CoralCDn builds on previous work in peer-to-peer sys- tal of 494 nodes. We configured the system as a single tems and web-based content deliveryAA B C C D E F G G HH H H HH HH H H H H HH I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H HH H H H I I I I I I I II I I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I I I I J J J J J J J J J J J J K K AA B C C D E F G G HH HH H H H H H H I I I I I I II I I I I I I I I I I I I II I I I I I I I I I I I I I I I I I I J J J J J J J J J J J K K A C C G G H H H H H H I I I I I I I I I I I II I I I I I I I I I I I I I J J J J J J K X X X 3 nodes 2 nodes 1 node A A A A A A A B B B B C C D D E E E E F F G H H I J J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H I J J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H I J J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H I J J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H I J J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H I J J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H I J J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H I J JJ K K K L M N O O O O O O O O O O O O O O O O O P P P P A A A A A A B B B B C C D D E E E E F F G H H J J K K L M N O O O O O O O O O O O O O O P P P P A A A A B B C C D D E E E F F H H J J K K L O O O O O O O P P X X X 3 nodes 2 nodes 1 node Figure 7: World view of level-1 clusters (60 msec threshold), and United States view of level-2 clusters (20 msec threshold). Each unique, non-singleton cluster is assigned a letter; the size of the letter corresponds to collocated nodes in the same cluster. The world map shows that Coral found natural divi￾sions between sets of nodes along geospatial lines at a 60 msec threshold. The map shows several distinct regions, the most dramatic being the Eastern U.S. (70 nodes), the Western U.S. (37 nodes), and Europe (19 nodes). The close correlation between network and physical distance suggests that speed-of-light delays dominate round-trip￾times. Note that, as we did not plot singleton clusters, the map does not include three Asian nodes(in Japan, Taiwan, and the Philippines, respectively). The United States map shows level-2 clusters again roughly separated by physical locality. The map shows 16 distinct clusters; obvious clusters include California (22 nodes), the Pacific Northwest (9 nodes), the South, the Midwest, etc. The Northeast Corridor cluster contains 29 nodes, stretching from North Carolina to Massachusetts. One interesting aspect of this map is the three separate, non-singleton clusters in the San Francisco Bay Area. Close examination of individual RTTs between these sites shows widely varying latencies; Coral clustered correctly given the underlying network topology. 6.4 Load Balancing Finally, Figure 8 shows the extent to which a DSHT bal￾ances requests to the same key ID. In this experiment, we ran 3 nodes on each of the earlier hosts for a to￾tal of 494 nodes. We configured the system as a single 0 12 24 36 48 60 72 84 near far Requests / Minute Distance to Hotspot Figure 8: The total number of put RPCs hitting each Coral node per minute, sorted by distance from node ID to target key. level-0 cluster. At the same time, all PlanetLab nodes be￾gan to issue back-to-back put/get requests at their max￾imum (non-concurrent) rates. All operations referenced the same key; the values stored during put requests were randomized. On average, each node issued 400 put/get operation pairs per second, for a total of approximately 12 million put/get requests per minute, although only a fraction hit the network. Once a node is storing a key, get requests are satisfied locally. Once it is loaded, each node only allows the leakage rate β RPCs “through” it per minute. The graphs show the number of put RPCs that hit each node in steady-state, sorted by the XOR distance of the node’s ID to the key. During the first minute, the clos￾est node received 106 put RPCs. In the second minute, as shown in Figure 8, the system reached steady-state with the closest node receiving 83 put RPCs per minute. Recall that our equation in Section 4.2 predicts that it should receive (β · log n) = 108 RPCs per minute. The plot strongly emphasizes the efficacy of the leakage rate β = 12, as the number of RPCs received by the majority of nodes is a low multiple of 12. No nodes on the far side of the graph received any RPCs. Coral’s routing algorithm explains this condition: these nodes begin routing by flipping their ID’s most￾significant bit to match the key’s, and they subsequently contact a node on the nearside. We have omitted the graph of get RPCs: During the first minute, the most-loaded node received 27 RPCs; subsequently, the key was widely distributed and the system quiesced. 7 Related work CoralCDN builds on previous work in peer-to-peer sys￾tems and web-based content delivery. 11