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)
Abstract:
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.
Bio:
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.
|