[Nrg-l] PhD Defense: Georgios Smaragdakis (TODAY @ 2PM)

Azer Bestavros best at cs.bu.edu
Mon Aug 25 10:28:13 EDT 2008


Computer Science Department
Boston University

Date: Monday August 25, 2008
Time: 2:00PM
Place: Room MCS 135, 111 Cummington Street

Georgios Smaragdakis
A foundational issue underlying many overlay network applications
ranging from routing to peer-to-peer file sharing to content
distribution is that of network creation and maintenance. Network
creation is concerned with folding new arrivals into an existing
overlay, whereas network maintenance is concerned with re-wiring to cope
with changing network conditions. Previous work has considered these
problems 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. The contributions of
this thesis are threefold. It unifies the above mentioned thrusts in
modeling the wiring strategies on behalf of selfish users, evaluates the
performance of overlay networks that consist of such users, and examines
the implications to overlay protocol design and service provisioning. 

In this thesis, a game-theoretic framework is developed that provides a
unified approach to modeling Selfish Neighbor Selection (SNS) wiring
procedures. The model is general enough to take into consideration costs
reflecting network latency and user preference profiles, the inherent
directionality in overlay maintenance protocols and connectivity
constraints imposed on the system designer. Within this framework the
notion of user's "best response" wiring strategy is formalized as a
k-median problem on asymmetric distance, and used to obtain pure Nash
equilibria. Evaluation results presented in this thesis indicate that
selfish users can reap substantial performance benefits when connecting
to overlay networks composed of non-selfish users. In addition, in
overlays that are dominated by selfish users, the resulting stable
wirings are optimized to such great extent that even non-selfish
newcomers can extract near-optimal performance through naive wiring
strategies. To capitalize on the performance advantages of best response
and the emergent stable global wirings that result, this thesis presents
EGOIST: an SNS-inspired distributed overlay network creation and
maintenance routing system that was deployed and evaluated on PlanetLab.
Using extensive measurements of paths between overlay nodes, results
presented in this thesis show that EGOIST's neighbor selection
primitives significantly outperform existing heuristics on a variety of
performance metrics, including delay, available bandwidth, and node
utilization. Moreover, these results 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 overheads. This thesis also provides evidence in support
of the potential benefits SNS offers to applications other than routing,
focusing on swarming applications, among others. 

In the context of service provisioning, this thesis examines the use of
distributed and scalable approaches that enable a provider to determine
the number and location of servers for optimal delivery of content or
services to its selfish end-users. The classical, centralized service
provisioning approach requires knowledge of topological and a-priori
demand information, both of which are intractable to obtain in
large-scale dynamic networks. To leverage recent advances in
virtualization technologies, this thesis develops and evaluates a
distributed protocol to migrate servers based on end-users demand and
only local topological knowledge. Results under a range of network
topologies and workloads suggest that the performance of the proposed
approach is comparable to that of the optimal but unscalable centralized
PhD Thesis Examination Committee:
 - Azer Bestavros (1st Reader)
 - Nikos Laoutaris (2nd Reader)
 - John Byers (3rd Reader)
 - Mark Crovella
 - Steve Homer
 - Ibrahim Matta
 - Shanghua Teng (Committee Chair)

More information about the Nrg-l mailing list