[Nrg-l] PhD Defense: Georgios Smaragdakis (Mon 8/25 @ 2PM)

Azer Bestavros best at cs.bu.edu
Fri Aug 22 13:28:05 EDT 2008


PHD THESIS DEFENSE

Computer Science Department
Boston University

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

OVERLAY NETWORK CREATION AND MAINTENANCE WITH SELFISH USERS
 
Georgios Smaragdakis
  
Abstract:
 
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 one.

 
_______________________________________________________________
 
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