In a typical overlay network for routing or content
sharing, each node must select a fixed number of immediate
overlay neighbors for routing traffic or content queries. A selfish
node entering such a network would select neighbors so as to
minimize the weighted sum of expected access costs to all its
destinations. Previous work on Selfish Neighbor Selection (SNS) has
built intuition with simple models where edges are undirected,
access costs are modeled by hop-counts, and nodes have potentially
unbounded degrees. However, in practice, important
constraints not captured by these models lead to richer games
with substantively and fundamentally different outcomes.
Main Results
A realistic Model of Overlay Networks:
Our work models neighbor selection as a game involving directed
links, constraints on the number of allowed neighbors, and
costs reflecting both network latency and node preference. We
express a node's ``best response" wiring strategy as a k-median
problem on asymmetric distance, and use this formulation to
obtain pure Nash equilibria.
Characterization of Stable Wirings:
We experimentally examine the
properties of such stable wirings on synthetic topologies, as well
as on real topologies and maps constructed from PlanetLab and
the AS-level Internet measurements.
Performance evaluation of the Best Response wiring strategy:
Our results indicate that
selfish nodes can reap substantial performance benefits when
connecting to overlay networks composed of non-selfish nodes.
On the other hand, in overlays that are dominated by selfish
nodes, the resulting stable wirings are optimized to such great
extent that even non-selfish newcomers can extract near-optimal
performance through naive wiring strategies.
Design and Implementation of a Selfish Neighbor Selection System:
We designed and implemented a prototype SNS, the Egoist overlay routing system, over PlanetLab.
Our experimental results demonstrate that our neighbor selection primitives significantly
outperform existing heuristics on a variety of performance metrics. Our system is highly
effective under node churn and cheating, while its performance is competitive with the optimal but not scalable
full mesh overlay system.
SNS and File Sharing:
We demonstrate how SNS yields significant improvement of search performance in unstructured peer-to-peer
file sharing overlays, based on the use of primitives such as scoped-flooding rather than routing.
SNS and Swarming:
We also demonstrate the potential benefits SNS-inspired formations may offer to swarming applications,
especially to the family of n-way broadcast applications, where each overlay node wants to push
its own distinct large data file to all other destinations as well as download their respective data files.
Contact
For any further
information or bug report please send e-mail to Georgios Smaragdakis
Sponsors:
last update: December 2, 2007
All code on this page is licensed under a Creative Commons License.
Sponsors: The SNS project is supported partially by a
number of National Science Foundation grants, including CISE/CSR Award
#0720604, ENG/EFRI Award #0735974, CISE/CNS Award #0524477, CNS/CNS
Award #0520166, CNS/ITR Award #0205294, and CISE/EIA RI Award #0202067.
Disclaimer: Any opinions, findings, conclusions, or recommendations
expressed in materials available from this site are those of their
author(s) and do not necessarily reflect the views of Boston University
or of the National Science Foundation.
