Toronto Networking Seminar

Thou Shalt Be A Selfish Overlay Neighbor:
Implications on the Design and Performance of Overlay Network Protocols

Azer Bestavros
Computer Science Department
Boston University

Date:  Friday, October 19, 2:10pm
Location: BA1220 (Bahen Center)


A foundational issue underlying many overlay network applications ranging from routing to P2P file sharing is that of connectivity management, i.e., folding new arrivals into the existing overlay, and re-wiring to cope with changing network conditions. 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 unifies these two thrusts by using insights gleaned from novel, realistic theoretic models in the design of Egoist, a prototype overlay routing system that we have implemented and evaluated on PlanetLab.

In the first part of this talk, I will offer a game-theoretic formulation of the neighbor selection problem, showing that under typical resource constraints, selfish players can select neighbors so as to efficiently reach Nash-like equilibria that also provide high global performance. I will present experimental results showing the properties of such stable wirings on synthetic topologies, as well as on real topologies and maps constructed from PlanetLab and AS-level Internet measurements. These results indicate that selfish nodes can reap substantial performance benefits when connecting to overlay networks constructed by naive nodes. Conversely, in overlays dominated by selfish nodes, the resulting stable wirings are optimized to such great extent that even uninformed newcomers can extract near-optimal performance through naive wiring strategies. In the second part of this talk, I will overview our Egoist prototype system, and present results from extensive experiments on PlanetLab. These results show that the neighbor selection primitives implemented in Egoist outperform existing heuristics on a variety of performance metrics; that Egoist is competitive with an optimal, but unscalable full-mesh overlay construction approach; and that it remains highly effective under significant churn. Time permitting, I will also describe variants of Egoist’s current design that would enable it to scale to overlays of much larger scale and allow it to cater effectively to applications, such as P2P file sharing in unstructured overlays, based on novel formulations of the neighbor selection problem that make use of primitives such as scoped-flooding and n-way broadcast, rather than routing.

This work is pursued in collaboration with Georgios Smaragdakis, Nikolaos Laoutaris, Pietro Michiardi (Eurocom), John Byers, and Mema Roussopoulos.


Azer Bestavros (PhD’92, Harvard U) is Professor in the Computer Science Department at Boston University, which he joined in 1991, and which he chaired from 2000 to 2007. Azer's research work, which has been funded by grants totaling over $15M from various government agencies and industrial labs, is in the broad areas of networking and real-time systems. His highly-cited research contributions (with dozens of students and collaborators) include his pioneering of the push content distribution model adopted years later by CDNs, his seminal work on Internet traffic characterization, his work on various network transport, caching, and streaming media delivery protocols, his work on end-to-end inference of network caricatures, his work on identifying and countering adversarial exploits of system dynamics, his work on game-theoretic approaches to overlay and P2P networking applications, his generalization of classical rate-monotonic analysis to accommodate uncertainties in resource availability, his use of redundancy-injecting codes for timely access to periodic broadcasts, his work on verification of network protocol compositions, including the identification of deadlock-prone arrangements of HTTP agents, and his work on virtualization services and programming environments for embedded sensor networks. Azer is a distinguished speaker of the IEEE and chairs the IEEE-CS TC on the Internet. He served on the program committees and editorial boards of major conferences and journals in networking and real-time systems and received distinguished service awards from both the ACM and the IEEE.