Low traffic overlay networks with large routing tables

ABSTRACT

The routing tables of Distributed Hash Tables (DHTs) can vary from size O(1) to O(n). Currently, what is lacking is an analytic framework to suggest the optimal routing table size for a given workload. This paper (1) compares DHTs with O(1) to O(n) routing tables and identifies some good design points; and (2) proposes protocols to realize the potential of those good design points.We use total traffic as the uniform metric to compare heterogeneous DHTs and emphasize the balance between maintenance cost and lookup cost. Assuming a node on average processes 1,000 or more lookups during its entire lifetime, our analysis shows that large routing tables actually lead to both low traffic and low lookup hops. These good design points translate into one-hop routing for systems of medium size and two-hop routing for large systems.Existing one-hop or two-hop protocols are based on a hierarchy. We instead demonstrate that it is possible to achieve completely decentralized one-hop or two-hop routing, i.e., without giving up being peer-to-peer. We propose 1h-Calot for one-hop routing and 2h-Calot for two-hop routing. Assuming a moderate lookup rate, compared with DHTs that use O(log n) routing tables, 1h-Calot and 2h-Calot save traffic by up to 70% while resolving lookups in one or two hops as opposed to O(log n) hops.

REFERENCES

• 1: C. Blake and R. Rodrigues. High Availability, Scalable Storage, Dynamic Peer Networks: Pick Two. In HotOS, 2003.
• 2: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek, and R. Morris. Designing a DHT for Low Latency and High Throughput. In NSDI, 2004. The network latency data set is available at http://www.pdos.lcs.mit.edu/p2psim/kingdata.
• 4: M. J. Freedman, E. Freudenthal, and D. Maziéres. Democratizing Content Publication with Coral. In NSDI, 2004.
• 5: A. Ganesh, A.-M. Kermarrec, and L. Massoulié. HiScamp: self-organising hierarchical membership protocol. In European ACM SIGOPS Workshop, 2002.
• 6: K. Gummadi , R. Gummadi , S. Gribble , S. Ratnasamy , S. Shenker , I. Stoica, The impact of DHT routing geometry on resilience and proximity, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863998]
• 7: A. Gupta, B. Liskov, and R. Rodrigues. Efficient Routing for Peer-to-Peer Overlays. In NSDI, 2004.
• 8: I. Gupta, K. Birman, P. Linga, A. Demers, and R. V. Renesse. Kelips: building an efficient and stable P2P DHT through increased memory and background overhead. In IPTPS, 2003.
• 9: F. Kaashoek and D. R. Karger. Koorde: A simple degree-optimal hash table. In IPTPS, 2003.
• 10: KaZaA. http://www.kazaa.com.
• 11: Abhishek Kumar , Shashidhar Merugu , Jun (Jim) Xu , Xingxing Yu, Ulysses: A Robust, Low-Diameter, Low-Latency Peer-ti-Peer Network, Proceedings of the 11th IEEE International Conference on Network Protocols, p.258, November 04-07, 2003
• 12: J. Li, J. Stribling, T. Gil, R. Morris, and F. Kaashoek. Comparing the performance of distributed hash tables under churn. In IPTPS, 2004.
• 13: Dmitri Loguinov , Anuj Kumar , Vivek Rai , Sai Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863999]
• 14: Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571857]
• 15: Alper Tugay Mýzrak , Yuchung Cheng , Vineet Kumar , Stefan Savage, Structured Superpeers: Leveraging Heterogeneity to Provide Constant-Time Lookup, Proceedings of the The Third IEEE Workshop on Internet Applications, p.104, June 23-24, 2003
• 16: V. Ramasubramanian and E. G. Sirer. Beehive: O(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays. In NSDI, 2004.
• 17: S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a dht. In USENIX Annual Technical Conference, 2004.
• 18: R. Rodrigues, B. Liskov, and L. Shrira. The design of a robust peer-to-peer system. In SIGOPS European Workshop, 2002.
• 19: S. Saroiu, P. K. Gummadi, and S. D. Gribble. A measurement study of peer-to-peer file sharing systems. In MMCN, 2002.
• 20: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 21: C. Tang and S. Dwarkadas. Hybrid Global-Local Indexing for Efficient Peer-to-Peer Information Retrieval. In NSDI, 2004.
• 22: The Open DHT Project. http://openhash.org/.
• 23: J. Xu, A. Kumar, and X. Yu. On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks. JSAC, 22(1):151--163, January 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Keywords:
distributed hash table, overlay network, peer-to-peer system