Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
Selfish Overlay Network Creation and
Link zur Publikation 
Download Bibtex Eintrag
||Smaragdakis, Georgios and Laoutaris, Nikolaos and Bestavros, Azer
and Byers, John W.
Transactions on Networking (ToN)
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 ''best response'' wiring
strategy amounts to solving a k-median problem on asymmetric distance.
Best response wirings have substantial practical utility as they
permit selfish nodes to reap substantial performance benefits when
connecting to overlays of non-selfish nodes. A more intricate
consequence is that even non-selfish nodes can benefit from the
existence of some selfish nodes since the latter, via their local
optimizations, create a highly optimized backbone, upon which even
simple heuristic wirings yield good performance. To capitalize on the
above properties we design, build and deploy, EGOIST, an SNS-inspired
prototype overlay routing system for PlanetLab. We demonstrate that
EGOIST outperforms existing heuristic overlays on a variety of
performance metrics, including delay, available bandwidth, and node
utilization, while it remains competitive with an optimal, but
unscalable full-mesh overlay.