On the difficulty of finding the nearest peer in p2p systems

ABSTRACT

Finding the nearest peer, in terms of latency, is an important problem in many Internet applications. In this paper, we argue that existing solutions, which only examine inter-peer latencies as part of their operation will find it costly, in certain commonly occurring scenarios, to discover the nearest peer in P2P systems. The difficulty arises out of the way the PoP access networks are laid out in the Internet, where a single PoP (point of presence) belonging to an ISP provides connectivity to numerous client networks. This setup makes a group of peers all appear roughly the same distance from each other, leading to inefficiencies in the existing solutions. In this paper, we use large-scale measurements to show that the problematic topology does occur, use simulations of the Meridian closest-server algorithm to show that the condition does indeed lead to difficulty in finding the exact-closest peer, and propose solutions.

REFERENCES

• 1: 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]
• 2: 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
• 3: Marcel Waldvogel , Roberto Rinaldi, Efficient topology-aware overlay network, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.101-106, January 2003 [doi>10.1145/774763.774779]
• 4: Manuel Costa , Miguel Castro , Antony Rowstron , Peter Key, PIC: Practical Internet Coordinates for Distance Estimation, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.178-187, March 24-26, 2004
• 5: Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 6: Miguel Castro, Peter Druschel, Y. Charlie Hu, and Antony Rowstron. Proximity neighbor selection in tree-based structured peer-to-peer overlays. In Technical report MSR-TR-2003-52, 2003.
• 8: Aleksandrs Lev Slivkins , Jon M. Kleinberg, Embedding, distance estimation and object location in networks, Cornell University, Ithaca, NY, 2006
• 9: Jonathan Ledlie, Paul Gardner, and Margo Seltzer. Network Coordinates in the Wild. In Proc. NSDI, 2007.
• 10: Network Coordinate Research at Harvard. http://www.eecs.harvard.edu/~syrah/nc/, Accessed June 2008.
• 11: Hitesh Ballani , Paul Francis , Sylvia Ratnasamy, A measurement-based deployment proposal for IP anycast, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177109]
• 12: Neil Spring , David Wetherall , Tom Anderson, Scriptroute: a public internet measurement facility, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.17-17, March 26-28, 2003, Seattle, WA
• 13: Krishna P. Gummadi , Stefan Saroiu , Steven D. Gribble, King: estimating latency between arbitrary internet end hosts, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637203]
• 14: Meridian: Lightweight Positioning. http://www.cs.cornell.edu/People/egs/meridian/, Accessed June 2008.
• 15: Michael J. Freedman , Eric Freudenthal , David Mazières, Democratizing content publication with coral, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.18-18, March 29-31, 2004, San Francisco, California
• 16: Michael J. Freedman , Mythili Vutukuru , Nick Feamster , Hari Balakrishnan, Geographic locality of IP prefixes, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.13-13, October 19-21, 2005, Berkeley, CA
• 17: Michael J. Freedman , Karthik Lakshminarayanan , David Mazières, OASIS: anycast for any service, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.10-10, May 08-10, 2006, San Jose, CA
• 71: Vivek Vishnumurthy and Paul Francis. On The Difficulty In Finding the Nearest Peer in P2P Systems. Cornell University, CIS Technical Report. http://hdl.handle.net/1813/11220, 2008.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

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

General Terms:
Measurement, Performance

Keywords:
last-hop, latency, nearest peer