Towards fast decentralized construction of locality-aware overlay networks

ABSTRACT

We consider a large overlay network where any two nodes can communicate directly via the underlying Internet as long as the sender knows the recipient's ip-address. Due to the scalability requirement, the overlay network must be sparse: a given node can store at most a polylogarithmic number of ip-addresses. A notion of distance (locality) in the network is given by node-to-node round-trip times. We assume that initially the overlay links are random, and hence have no explicit locality-aware properties.

We provide fast distributed constructions for various locality-aware (low-stretch) distributed data structures, such as: distance labeling schemes, name-independent routing schemes, and multicast trees. In previous work, such data structures have only been constructed via centralized algorithms. Our constructions complete in poly-logarithmic time (and thus induce at most a poly-logarithmic load on every given node), and achieve quality guarantees similar to those of the corresponding centralized algorithms.

Our algorithms use a common locality-aware, small-world-like overlay framework, constructed via concurrent random walks. Our guarantees are for growth-constrained metrics, a well-studied family of metrics which have been proposed as a reasonable abstraction of round-trip times in the Internet.

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille , Andrew V. Goldberg , Dahlia Malkhi, Routing in Networks with Low Doubling Dimension, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.75, July 04-07, 2006 [doi>10.1109/ICDCS.2006.72]
• 2: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: lower bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148143]
• 3: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007916]
• 4: Ittai Abraham , Dahlia Malkhi, Name independent routing for growth bounded networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073978]
• 5: Ittai Abraham , Dahlia Malkhi , Oren Dobzinski, LAND: stretch (1 + ε) locality-aware networks for DHTs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
• 7: B. Awerbuch and D. Peleg. Sparse partitions. In 31st Symp. on Foundations of Computer Science (FOCS), pages 503--513, 1990.
• 8: Y.-H. Chu, S. G. Rao, S. Seshan, and H. Zhang. Case for End System Multicast. IEEE J. on Selected Areas in Communication (JSAC), 20(8), 2002.
• 9: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 10: Philippe Duchon , Nicolas Hanusse , Emmanuelle Lebhar , Nicolas Schabanel, Towards small world emergence, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148145]
• 11: Paul Francis , Sugih Jamin , Cheng Jin , Yixin Jin , Danny Raz , Yuval Shavitt , Lixia Zhang, IDMaps: a global internet host distance estimation service, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.525-540, October 2001 [doi>10.1109/90.958323]
• 12: Cyril Gavoille , Michal Katz , Nir A. Katz , Christophe Paul , David Peleg, Approximate Distance Labeling Schemes, Proceedings of the 9th Annual European Symposium on Algorithms, p.476-487, August 28-31, 2001
• 13: Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003 [doi>10.1007/s00446-002-0073-5]
• 14: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004 [doi>10.1016/j.jalgor.2004.05.002]
• 15: James D. Guyton , Michael F. Schwartz, Locating nearby copies of replicated Internet servers, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.288-298, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 16: Kirsten Hildrum , John Kubiatowicz , Sean Ma , Satish Rao, A note on the nearest neighbor in growth-restricted metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 17: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 18: Valerie King , Jared Saia, Choosing a random peer, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011786]
• 19: Jon Kleinberg , Aleksandrs Slivkins , Tom Wexler, Triangulation and Embedding Using Small Sets of Beacons, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.444-453, October 17-19, 2004 [doi>10.1109/FOCS.2004.70]
• 20: C. Kommareddy , B. Bhattacharjee, Finding Close Friends on the Internet, Proceedings of the Ninth International Conference on Network Protocols, p.301, November 11-14, 2001
• 21: Dejan Kostić , Adolfo Rodriguez , Jeannie Albrecht , Amin Vahdat, Bullet: high bandwidth data dissemination using an overlay mesh, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 22: Robert Krauthgamer , James R. Lee, The intrinsic dimensionality of graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780607]
• 23: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073826]
• 24: C. Law and K.-Y. Siu. Distributed construction of random expander networks. In IEEE INFOCOM, 2003.
• 25: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 26: T. E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In IEEE INFOCOM, 2002.
• 27: G. Pandurangan, Building Low-Diameter P2P Networks, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.492, October 14-17, 2001
• 28: C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 29: Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073823]
• 30: A. Slivkins. Towards Fast Decentralized Construction of Locality-Aware Overlay Networks. Technical report, Brown University, June 2007. Available online at http://www.cs.brown.edu/people/slivkins/.
• 31: Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007399]
• 32: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]
• 33: V. Vishnumurthy and P. Francis. On Heterogeneous Overlay Construction and Random Node Selection in Unstructured P2P Networks. In IEEE INFOCOM, 2006.
• 34: Bernard Wong , Aleksandrs Slivkins , Emin Gün Sirer, Meridian: a lightweight network location service without virtual coordinates, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 35: Q. Zhang, F. Yang, W. Zhu, and Y.-Q. Zhang. A Construction of Locality-Aware Overlay Network: mOverlay and its performance. IEEE J. on Selected Areas in Communications (JSAC), 22(1):18--28, 2004.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms; Graph labeling

General Terms:
Algorithms, Performance, Theory

Keywords:
distance labeling, grid dimension, growth-constrained metrics, locality-aware networks, multi-cast trees, routing schemes, triangulation