Meridian: a lightweight network location service without virtual coordinates

Abstract

This paper introduces a lightweight, scalable and accurate framework, called Meridian, for performing node selection based on network location. The framework consists of an overlay network structured around multi-resolution rings, query routing with direct measurements, and gossip protocols for dissemination. We show how this framework can be used to address three commonly encountered problems, namely, closest node discovery, central leader election, and locating nodes that satisfy target latency constraints in large-scale distributed systems without having to compute absolute coordinates. We show analytically that the framework is scalable with logarithmic convergence when Internet latencies are modeled as a growth-constrained metric, a low-dimensional Euclidean metric, or a metric of low doubling dimension. Large scale simulations, based on latency measurements from 6.25 million node-pairs as well as an implementation deployed on PlanetLab show that the framework is accurate and effective.

References

1. D. Andersen, H. Balakrishnan, M. Kaashoek, and R. Morris. Resilient Overlay Networks. In Symposium on Operating Systems Principles, Banff, AB, Canada, October 2001.
2. P. Assouad. Plongements Lipschitziens dans Rn. Bull. Soc. Math. France, 111(4), 1983.
3. S. Banerjee, C. Kommareddy, and B. Bhattacharjee. Scalable Peer Finding on the Internet. In Global Internet Symposium, Taipei, Taiwan, November 2002.
4. A. Bavier, M. Bowman, B. Chun, D. Culler, S. Karlin, S. Muir, L. Peterson, T. Roscoe, T. Spalink, and M. Wawrzoniak. Operating System Support for Planetary-Scale Network Services. In Networked Systems Design and Implementation, San Francisco, CA, March 2004.
5. A. Bharambe, M. Agrawal, and S. Seshan. Mercury: Supporting Scalable Multi-Attribute Range Queries. In SIGCOMM, Portland, OR, August 2004.
6. R. Carter and M. Crovella. Server Selection Using Dynamic Path Characterization in Wide-Area Networks. In INFOCOM, Kobe, Japan, April 1997.
7. R. Carter and M. Crovella. On the Network Impact of Dynamic Server Selection. Computer Networks, 31, 1999.
8. M. Castro, P. Druschel, Y. Hu, and A. Rowstron. Exploiting Network Proximity in Peer-to-Peer Overlay Networks. In Technical Report MSR-TR-2003-82, Microsoft Research, 2002.
9. M. Castro, P. Druschel, Y. Hu, and A. Rowstron. Proximity Neighbor Selection in Tree-Based Structured Peer-to-Peer Overlays. In Technical Report MSR-TR-2003-52, Microsoft Research, 2003.
10. U. G. Center. QHull. UIUC Geometry Center, QHull Computational Geometry Package, http://www.qhull.org, 2004.
11. Y. Chu, S. Rao, and H. Zhang. A Case for End System Multicast. In SIGMETRICS, Santa Clara, CA, June 2000.
12. M. Costa, M. Castro, A. Rowstron, and P. Key. PIC: Practical Internet Coordinates for Distance Estimation. In Intl. Conference on Distributed Computing Systems, Tokyo, Japan, March 2004.
13. A. Crainiceanu, P. Linga, J. Gehrke, and J. Shanmugasundaram. Querying Peer-to-Peer Networks Using P-Trees. In Intl. Workshop on the Web and Databases, Paris, France, June 2004.
14. W. Cui, I. Stoica, and R. Katz. Backup Path Allocation based on a Correlated Link Failure Probability Model in Overlay Networks. In Intl. Conference on Network Protocols, Paris, France, November 2002.
15. F. Dabek, R. Cox, F. Kaashoek, and R. Morris. Vivaldi: A Decentralized Network Coordinate System. In SIGCOMM, Portland, OR, August 2004.
16. F. Dabek, M. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-Area Cooperative Storage with CFS. In Symposium on Operating Systems Principles, Banff, AB, Canada, October 2001.
17. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic Algorithms for Replicated Database Maintenance. In Symposium on Principles of Distributed Computing, Vancouver, BC, Canada, August 1987.
18. Z. Fei, S. Bhattacharjee, E. Zegura, and M. Ammar. A Novel Server Selection Technique for Improving the Response Time of a Replicated Service. In INFOCOM, San Francisco, CA, March 1998.
19. P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. IDMaps: A Global Internet Host Distance Estimation Service. Transactions on Networking, 9:525--540, October 2001.
20. K. Gummadi, S. Saroiu, and S. Gribble. King: Estimating Latency between Arbitrary Internet End Hosts. In Internet Measurement Workshop, Marseille, France, November 2002.
21. A. Gupta, R. Krauthgamer, and J. Lee. Bounded Geometries, Fractals, and Low-Distortion Embeddings. In Symposium on Foundations of Computer Science, Cambridge, MA, October 2003.
22. J. Guyton and M. Schwartz. Locating Nearby Copies of Replicated Internet Servers. In SIGCOMM, Cambridge, MA, August 1995.
23. J. Heinonen. Lectures on Analysis on Metric Spaces. Springer Verlag, Universitext 2001.
24. K. Hildrum, R. Krauthgamer, and J. Kubiatowicz. Object Location in Realistic Networks. In Symposium on Parallelism in Algorithms and Architectures, Barcelona, Spain, June 2004.
25. K. Hildrum, J. Kubiatowicz, S. Ma, and S. Rao. A Note on Finding the Nearest Neighbor in Growth-Restricted Metrics. In Symposium on Discrete Algorithms, New Orleans, LA, January 2004.
26. K. Hildrum, J. Kubiatowicz, and S. Rao. Another Way to Find the Nearest Neighbor in Growth-Restricted Metrics. In UC Berkeley CSD ETR, UCB/CSD-03-1267, UC Berkeley, August 2003.
27. K. Hildrum, J. Kubiatowicz, S. Rao, and B. Zhao. Distributed Object Location in a Dynamic Network. In Symposium on Parallel Algorithms and Architectures, Winnipeg, MB, Canada, August 2002.
28. S. Hotz. Routing Information Organization to Support Scalable Interdomain Routing with Heterogeneous Path Requirements. PhD thesis, Univ. of Southern California, 1994.
29. K. Johnson, J. Carr, M. Day, and M. Kaashoek. The Measured Performance of Content Distribution Networks. In Web Caching and Content Delivery Workshop, Lisbon, Portugal, May 2000.
30. D. Karger and M. Ruhl. Finding Nearest Neighbors in Growth-restricted Metrics. In Symposium on Theory of Computing, Montreal, QC, Canada, May 2002.
31. D. Kempe, J. Kleinberg, and A. Demers. Spatial Gossip and Resource Location Protocols. In Symposium on Theory of Computing, Heraklion, Greece, July 2001.
32. J. Kleinberg, A. Slivkins, and T. Wexler. Triangulation and Embedding using Small Sets of Beacons. In Symposium on Foundations of Computer Science, Rome, Italy, October 2004.
33. C. Kommareddy, N. Shankar, and B. Bhattacharjee. Finding Close Friends on the Internet. In Intl. Conference on Network Protocols, Riverside, CA, November 2001.
34. R. Krauthgamer and J. Lee. The Intrinsic Dimensionality of Graphs. In Symposium on Theory of Computing, San Diego, CA, June 2003.
35. R. Krauthgamer and J. Lee. Navigating Nets: Simple Algorithms for Proximity Search. In Symposium on Discrete Algorithms, New Orleans, LA, January 2004.
36. R. Krauthgamer and J. Lee. The Black-Box Complexity of Nearest Neighbor Search. In Intl. Colloquium on Automata, Languages and Programming, Turku, Finland, July 2004.
37. R. Krauthgamer, J. Lee, M. Mendel, and A. Naor. Measured Descent: A New Embedding Method for Finite Metrics. In Symposium on Foundations of Computer Science, Rome, Italy, October 2004.
38. R. Lawrence. Running Massively Multiplayer Games as a Business, March 2004. Keynote speech from Networked Systems Design and Implementation.
39. L. Lehman and S. Lerman. PCoord: Network Position Estimation Using Peer-to-Peer Measurements. In Intl. Symposium on Network Computing and Applications, Cambridge, MA, August 2004.
40. H. Lim, J. Hou, and C. Choi. Constructing Internet Coordinate System Based on Delay Measurement. In Internet Measurement Conference, Miami, Florida, October 2003.
41. P. Maniatis, M. Roussopoulos, T. Giuli, D. Rosenthal, M. Baker, and Y. Muliadi. Preserving Peer Replicas by Rate-Limited Sampled Voting. In Symposium on Operating Systems Principles, Bolton Landing, NY, October 2003.
42. T. Ng and H. Zhang. Predicting Internet Network Distance with Coordinates-Based Approaches. In INFOCOM, New York, NY, June 2002.
43. T. Ng and H. Zhang. A Network Positioning System for the Internet. In USENIX, Boston, MA, June 2004.
44. M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti. Lighthouses for Scalable Distributed Location. In Intl. Workshop on Peer-To-Peer Systems, Berkeley, CA, February 2003.
45. C. Plaxton, R. Rajaraman, and A. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. In Symposium on Parallel Algorithms and Architectures, Newport, RI, June 1997.
46. S. Ratnasamy, P. Francis, M. Hadley, R. Karp, and S. Shenker. A Scalable Content-Addressable Network. In SIGCOMM, San Diego, CA, August 2001.
47. S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Topologically-Aware Overlay Construction and Server Selection. In INFOCOM, New York, NY, June 2002.
48. A. Rowstron and P. Druschel. Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-to-Peer Systems. In Middleware, Heidelberg, Germany, November 2001.
49. A. Rowstron and P. Druschel. Storage Management and Caching in PAST, a Large-Scale, Persistent Peer-to-Peer Storage Utility. In Symposium on Operating Systems Principles, Banff, AB, Canada, October 2001.
50. S. Savage, A. Collins, and E. Hoffman. The End-to-End Effects of Internet Path Selection. In SIGCOMM, Cambridge, MA, September 1999.
51. K. Shanahan and M. Freedman. Locality Prediction for Oblivious Clients. In Intl. Workshop on Peer-To-Peer Systems, Ithaca, NY, February 2005.
52. Y. Shavitt and T. Tankel. Big-Bang Simulation for Embedding Network Distances in Euclidean Space. In INFOCOM, San Francisco, CA, April 2003.
53. A. Slivkins. Distance Estimation and Object Location via Rings of Neighbors. In Symposium on Principles of Distributed Computing, Las Vegas, NV, July 2005.
54. A. Slivkins. Distributed Approaches to Triangulation and Embedding. In the Symposium on Discrete Algorithms, Vancouver, BC, Canada, January 2005.
55. I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. In SIGCOMM, San Diego, CA, August 2001.
56. K. Talwar. Bypassing the Embedding: Approximation Schemes and Compact Representations for Growth Restricted Metrics. In Symposium on Theory of Computing, Chicago, IL, June 2004.
57. L. Tang and M. Crovella. Virtual Landmarks for the Internet. In Internet Measurement Conference, Miami, Florida, October 2003.
58. M. Waldvogel and R. Rinaldi. Efficient Topology-Aware Overlay Network. In Hot Topics in Networks, Princeton, NJ, October 2002.
59. H. Weatherspoon, T. Moscovitz, and J. Kubiatowicz. Introspective Failure Analysis: Avoiding Correlated Failures in Peer-to-Peer Systems. In Intl. Workshop on Reliable Peer-to-Peer Distributed Systems, Osaka, Japan, October 2002.
60. B. Wong, A. Slivkins, and E. Sirer. Meridian: A Lightweight Network Location Service without Virtual Coordinates. In Computing and Information Science Technical Report TR2005-1982, Cornell University, May 2005.
61. B. Zhao, J. Kubiatowicz, and A. Joseph. Tapestry: An Infrastructure for Fault-Tolerant Wide-Area Location and Routing. In Technical Report UCB/CSD-01-1141, UC Berkeley, April 2001.

Index Terms

• Networks

  • Network properties

    • Network structure