TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

Selfish Overlay Network Creation and Maintenance
Citation key SLLBBR-SONCM-12
Author Smaragdakis, Georgios and Laoutaris, Nikolaos and Lekakis, Vassilis and Bestavros, Azer and Byers, John W. and Roussopoulos, Mema
Year 2012
ISSN 1063-6692
DOI http://dx.doi.org/10.1109/TNET.2011.2129528
Journal IEEE/ACM Transactions on Networking (ToN)
Abstract A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of the network formation, 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 the case of cooperative peers, and performing game theoretic analysis for the case of selfish peers. In our work, we unify the aforementioned thrusts by defining and studying the Selfish Neighbor Selection (SNS) game and its application to overlay routing. At the heart of SNS stands the restriction that peers are allowed up to a certain number of neighbors. This makes SNS substantially different from existing network formation games that impose no bounds on peer degrees. Having bounded degrees has important practical consequences as it permits the creation of overlay structures that require O(n) instead of O(n²) link monitoring overhead. We show that a node's
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe