Title: Implications of Selfish Neighbor Selection in Overlay Networks
Authors: Nikolaos Laoutaris, Georgios Smaragdakis, Azer Bestavros, and John Byers
Date: July 14, 2006
Abstract:
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 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. 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. 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. 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.