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

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 n1-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.