EGOIST: overlay routing using selfish neighbor selection

ABSTRACT

A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of connectivity management, i.e., folding new arrivals into an existing overlay, and re-wiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for specific applications designed to work well in real deployments, and providing abstractions for the underlying problem that are analytically tractable, especially via game-theoretic analysis. In this paper, we unify these two thrusts by using insights gleaned from novel, realistic theoretic models in the design of EGOIST -- a distributed overlay routing system that we implemented, deployed, and evaluated on PlanetLab. Using extensive measurements of paths between nodes, we demonstrate that EGOIST'S neighbor selection primitives significantly outperform existing heuristics on a variety of performance metrics, including delay, available bandwidth, and node utilization. Moreover, we demonstrate that EGOIST is competitive with an optimal, but unscalable full-mesh approach, remains highly effective under significant churn, is robust to cheating, and incurs minimal overhead. Finally, we use a multiplayer peer-to-peer game to demonstrate the value of EGOIST to end-user applications.

REFERENCES

• 1: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 2: Vijay Arya , Naveen Garg , Rohit Khandekar , Adam Meyerson , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece [doi>10.1145/380752.380755]
• 3: Moshe Babaioff , Robert Kleinberg , Christos H. Papadimitriou, Congestion games with malicious players, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250926]
• 4: Ashwin Bharambe , Jeffrey Pang , Srinivasan Seshan, Colyseus: a distributed architecture for online multiplayer games, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.12-12, May 08-10, 2006, San Jose, CA
• 5: Ashwin Bharambe , John R. Douceur , Jacob R. Lorch , Thomas Moscibroda , Jeffrey Pang , Srinivasan Seshan , Xinyu Zhuang, Donnybrook: enabling large-scale, high-speed, peer-to-peer games, Proceedings of the ACM SIGCOMM 2008 conference on Data communication, August 17-22, 2008, Seattle, WA, USA
• 6: A. Blanc, Y.-K. Liu, A. Vahdat, and S. Shenker. Designing incentives for peer-to-peer routing. In P2PEcon '04.
• 7: Miguel Castro , Peter Druschel , Ayalvadi Ganesh , Antony Rowstron , Dan S. Wallach, Secure routing for structured peer-to-peer overlay networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060317]
• 8: B.-G. Chun, R. Fonseca, I. Stoica, and J. Kubiatowicz. Characterizing selfishly constructed overlay routing networks. In INFOCOM '04.
• 9: Jacomo Corbo , David Parkes, The price of selfish behavior in bilateral network formation, 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.1073833]
• 10: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 11: Özgür Erçetin , Leandros Tassiulas, Market-Based Resource Allocation for Content Delivery in the Internet, IEEE Transactions on Computers, v.52 n.12, p.1573-1585, December 2003 [doi>10.1109/TC.2003.1252853]
• 12: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 13: Michal Feldman , Kevin Lai , Ion Stoica , John Chuang, Robust incentive techniques for peer-to-peer networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988788]
• 14: P. Brighten Godfrey , Scott Shenker , Ion Stoica, Minimizing churn in distributed systems, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 15: 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]
• 16: J. Han, D. Watson, and F. Jahanian. Topology aware overlay networks. In INFOCOM '05.
• 17: N. Laoutaris, L. Poplawski, R. Rajaraman, R. Sundaram, and S.-H. Teng. A Bounded-Degree Network Formation Game. In PODC '08.
• 18: Nikolaos Laoutaris , Pablo Rodriguez , Laurent Massoulie, ECHOS: edge capacity hosting overlays of nano data centers, ACM SIGCOMM Computer Communication Review, v.38 n.1, January 2008 [doi>10.1145/1341431.1341442]
• 19: N. Laoutaris, G. Smaragdakis, A. Bestavros, and J. Byers. Implications of Selfish Neighbor Selection in Overlay Networks. In INFOCOM '07.
• 20: J. Ledlie, P. Pietzuch, and M. Seltzer. Network Coordinates in the Wild. In NSDI '07.
• 21: Z. Li and P. Mohapatra. Impact of Topology On Overlay Routing Service. In INFOCOM '04.
• 22: Z. Li and P. Mohapatra. QRON: QoS-aware routing in overlay networks. IEEE JSAC, 22(1): 29--40, Jan 2004.
• 23: Y. Liu, H. Zhang, W. Gong, and D. F. Towsley. On the interaction between overlay routing and underlay routing. In INFOCOM '05.
• 24: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 25: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, On the topologies formed by selfish peers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146403]
• 26: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 27: S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. Topologically aware overlay construction and server selection. In INFOCOM '02.
• 28: Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz, Handling churn in a DHT, Proceedings of the annual conference on USENIX Annual Technical Conference, p.10-10, June 27-July 02, 2004, Boston, MA
• 29: V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell. pathChirp: Efficient Available Bandwidth Estimation for Network Paths. In PAM '03.
• 30: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 31: Stefan Savage , Thomas Anderson , Amit Aggarwal , David Becker , Neal Cardwell , Andy Collins , Eric Hoffman , John Snell , Amin Vahdat , Geoff Voelker , John Zahorjan, Detour: Informed Internet Routing and Transport, IEEE Micro, v.19 n.1, p.50-59, January 1999 [doi>10.1109/40.748796]
• 32: S. Seetharaman and M. Ammar. On the Interaction between Dynamic Routing in the Overlay and Native Layers. In INFOCOM '06.
• 33: A. Shriram, M. Murray, Y. Hyun, N. Brownlee, A. Broido, M. Fomenkov, and K. C. Claffy. Comparison of Public End-to-End Bandwidth Estimation Tools on High-Speed Links. In PAM '05.
• 34: G. Smaragdakis. Overlay Network Creation and Maintenance with Selfish Users. PhD Dissertation, Computer Science Department, Boston University, 2008.
• 35: G. Smaragdakis, N. Laoutaris, A. Bestavros, J. Byers, and M. Roussopoulos. EGOIST: Overlay Routing using Selfish Neighbor Selection. Technical Report BUCS-TR-2007-013, CS Department, Boston University.
• 36: G. Smaragdakis, N. Laoutaris, P. Michiardi, A. Bestavros, J. W. Byers, and M. Roussopoulos. Swarming on Optimized Graphs for n-way Broadcast. In INFOCOM '08.
• 37: Srinivasan Seetharaman and Voler Hilt and Markus Hofmann and Mostafa Ammar. Preemptive strategies to improve routing performance of native and overlay layers. In INFOCOM '07.
• 38: Vivek Vishnumurthy , Paul Francis, A comparison of structured and unstructured P2P approaches to heterogeneous random peer selection, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 39: Limin Wang , Kyoung Soo Park , Ruoming Pang , Vivek Pai , Larry Peterson, Reliability and security in the CoDeeN content distribution network, Proceedings of the annual conference on USENIX Annual Technical Conference, p.14-14, June 27-July 02, 2004, Boston, MA
• 40: Zhongmei Yao , Derek Leonard , Xiaoming Wang , Dmitri Loguinov, Modeling Heterogeneous User Churn and Local Resilience of Unstructured P2P Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.32-41, November 12-15, 2006 [doi>10.1109/ICNP.2006.320196]
• 41: A. Young, J. Chen, Z. Ma, A. Krishnamurthy, L. L. Peterson, and R. Wang. Overlay Mesh Construction Using Interleaved Spanning Trees. In INFOCOM '04.
• 42: Yong Zhu , Constantinos Dovrolis , Mostafa Ammar, Dynamic overlay routing based on available bandwidth estimation: a simulation study, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.6, p.742-762, 13 April 2006 [doi>10.1016/j.comnet.2005.07.015]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Design, Experimentation, Performance

Keywords:
overlay network creation and maintenance, overlay routing, selfish neighbor selection