[Nrg-l] PhD Proposal Defense: Georgios Smaragdakis (Fri 12/14 @ 1pm)

Azer Bestavros best at cs.bu.edu
Tue Dec 11 12:20:54 EST 2007


Computer Science Department
Boston University

Date: Friday December 14, 2007
Time: 1:00pm
Place: Room MCS 135, 111 Cummington Street

Selfish Overlay Network Formation:
Resource Allocation Strategies and Implications on Protocol Design

Georgios Smaragdakis


This talk will present a general framework to model and analyze overlay
networks composed of selfish users (nodes). The proposed methodology
examines (i) the design and feasibility of strategic resource allocation
by individual users (ii) the effect on the quality of service users
receive in topologies that are dominated by selfish users, and (iii) the
implications on overlay network protocol design. The main focus will be
on re-examining four fundamental building blocks of overlay network
formation, namely, (1) overlay node selection, (2) overlay neighbor
selection, (3) overlay peer selection, and (4) overlay storage sharing,
under the proposed framework. 

In the overlay node selection problem, the number and location of
service facilities to be deployed has to be decided. The effectiveness
of service provisioning in large-scale networks is highly dependent on
such deployment. Within our framework, we propose a fully distributed
protocol that achieves performance which is comparable to that of an
optimal, centralized protocol requiring full topology and demand

In the overlay neighbor selection problem, each node must select a small
number of immediate overlay neighbors for routing traffic or content
queries. Within our framework, we formalize the notion of a node's best
response wiring and use this formulation to obtain and examine the
properties of pure Nash equilibria. We show that selfish nodes can reap
substantial performance benefits when connecting to overlay nodes
constructed by naive nodes. On the other hand, in overlays that are
dominated by selfish nodes, the resulting stable wirings are highly
optimized. We also demonstrate that our framework outperforms existing
heuristics on a variety of performance metrics, is highly effective
under node churn, robust to cheating, incurs minimal overhead, while its
performance is competitive with the optimal but not scalable full mesh
overlay system. We also demonstrate how selfish neighbor selection (SNS)
yields significant improvement of search performance in unstructured
peer-to-peer file sharing overlays. 

In the peer selection problem, each node must select a small number of
peers to exchange data, while participating in a content distribution
network. Within our framework, we propose two novel distributed peer set
selection policies, strive to minimize the average and total download
time respectively. We demonstrate the potential benefits that formations
based on such policies may offer to swarming applications, especially to
the family of n-way broadcast applications, where each overlay node
wants to push its own distinct large data file to all other destinations
as well as download their respective data files. 

In the overlay storage sharing problem, each node allocates storage to
form a storage network. In this setting, we explore the causes of
mistreatment in distributed caching groups. Within our framework, we
outline and evaluate a distributed emulation-based protocol to mitigate
mistreatment, whereby the level of cooperation is tied to the benefit
that a node begets from joining the overlay. We demonstrate that the
proposed adaptive protocol outperforms the existing static ones. 

While much attention has been paid to the harmful downsides of selfish
behavior, our results advocate that strategic resource allocation
primitives significantly outperforms existing ones, providing a
promising alternative to distributed overlay network formation.

Examination Committee:

- Azer Bestavros, BU/CS
- Nikolaos Laoutaris, Telefonica 
- John Byers, BU/CS
- Ibrahim Matta, BU/CS

More information about the Nrg-l mailing list