[Nrg-l] PhD Defense: Georgios Smaragdakis (Mon 8/25 @ 2PM)
best at cs.bu.edu
Mon Aug 18 10:52:08 EDT 2008
PHD THESIS DEFENSE
Computer Science Department
Date: Monday August 25, 2008
Place: Room MCS 135, 111 Cummington Street
OVERLAY NETWORK CREATION AND MAINTENANCE WITH SELFISH USERS
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 na¨ıve 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)
- Steve Homer
- Ibrahim Matta
- Shanghua Teng (Committee Chair)
More information about the Nrg-l