~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
CCS Seminar

Friday, February 8, 2008
12:00
Physics Research Building - Room 595
3 Cummington Street
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Professor Azer Bestavros
Boston University
Computer Science Department

"Network Creation Games"

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 (Telefonica), John Byers, and Mema Roussopoulos(Harvard).



Cheryl Endicott
Administrative Assistant
Center for Computational Science
3 Cummington Street
Boston, MA 02215
tel: 617-358-1470
fax: 617-358-2487
http://ccs.bu.edu

Created for the Boston University/SCV Projects Page.

Created by The CoCoBoard.