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. 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. Our work on Selfish Neighbor Selection (SNS) unifies these two thrusts by using insights gleaned from novel, realistic theoretic models in the design of optimized distributed systems for overlay applications.


Analysis

A realistic model of overlay networks: Our work models neighbor selection as a game involving constraints on the number of allowed neighbors, costs reflecting both network latency and node preference, and the inherent directionality in traffic routing. 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 a range of network topologies.

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.

System

the EGOIST system: To capitalize on the substantial performance improvement of best response wirings for overlay nodes, we designed, deployed and evaluated, EGOIST, an SNS inspired distributed system for overlay routing. 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. EGOIST code will be available soon and can be used as a building block for the construction of optimized overlay networks.

Applications

SNS and swarming: We 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.

SNS and real time applications: We use a multiplayer peer-to-peer game to demonstrate the value of EGOIST to end-user applications, especially in reducing the update latencies. We also discuss the benefits EGOIST may offer to p2p-voice-over-IP.

SNS and file transfers: We provide a layered architecture that end users can use to route their packets over EGOIST. We also study the case of multipath file tranfer over EGOIST.