Latency effects on reachability in large-scale peer-to-peer networks

ABSTRACT

In this paper we study the latency effects introduced in large scale internet applications. In particular, we study the effects of heterogeneous latency on reachability in decentralized, distributed networks operating under flooding protocols. We show that the standard protocol mechanisms of time-to-live (TTL) and unique message identification (UID), used to govern flooding message transmissions, can combine to potentially devastating effect on the reachability of message broadcast. We call this combined effect short-circuiting, and we investigate consequences of this phenomenon. We show that in the worstcase, short-circuiting resulting from heterogeneous latencies can near-completely eliminate the reach of broadcast messages, even with an ability to place k ⪈ 1 broadcast servers optimally. This dramatic negative effect on reachability shows that application protocol designs need to be sensitive to latency models. In addition, we show that short-circuiting can have a negative effect on well known approximation algorithms for maximizing reachability. We show that with respect to distance measures that account for short-circuiting, the standardk-center problem can not be approximated within n^1-e, unless P = NP. Our theoretical results suggest that it may be quite difficult to find near optimal solutions to certain internet server selection problems. We consider the significance of our results on a large-scale peer-to-peer searching application, that relies on related flooding protocols. We report measurements through experimental studies with both simulated networks and a large network application known as Gnutella. Our empirical results, using statistics obtained from both the simulations and real applications, support the conclusion that, on average, the real effects of short-circuiting are significant, but not devastating to the performance of an overall large-scale system.

REFERENCES

• 1: The Gnutella Homepage. http://gnutella.wego.com.
• 2: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 3: I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: A distributed anonymous information storage and retrieval system. In ICSI Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, 2000. International Computer Science Institute.
• 4: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 5: M. Jovanovic, F. Annexstein, and K. Berman. Scalability issues in large peer-to-peer networks - a case study of gnutella. Technical report, University of Cincinnati, January 2001.
• 6: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
• 7: Jon Kleinberg, The Small-World Phenomenon: An Algorithmic Perspective, Cornell University, Ithaca, NY, 1999
• 8: G. Nemhauser and L. Woolsey. Maximizing submodular set functions: formulations and analysis of algorithms. In Studies of Graphs and Discrete Programming, pages 279-301. North-Holland, Amsterdam, 1981.
• 9: D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature, 393:440-442, June 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

Additional Classification:
  C. Computer Systems Organization

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

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Reliability, Theory, Verification