Azer Bestavros
Boston University
Computer Science Department
111 Cummington Street
Boston, MA 02215
Email: BEST@CS.BU.EDU
URL:  HTTP://WWW.CS.BU.EDU/~BEST


DVP term expires December 2012

Azer Bestavros (PhD’92, Harvard U) is Professor in the Computer Science Department at Boston
University, which he joined in 1991, and which he chaired from 2000 to 2007. Azer's research
interests are in the broad areas of networking and real-time embedded systems. His contributions
include his pioneering the distribution model adopted years later by CDNs, his seminal work on
Internet and web characterization, and his work on compositional certification of networked
systems and software. Funded by grants totaling over $16M from various government agencies
and industrial labs, his research work yielded 13 PhD theses, over 80 masters projects, 4 issued
patents, 2 startup companies, over 160 refereed papers, and over 3,700 citations. He is the chair of the IEEE Computer Society TC on the Internet, served on the program committees and editorial
boards of major conferences and journals in networking and real-time systems, and received
distinguished service awards from both the ACM and the IEEE.


Network and Cloud Resource Management Games
In many emerging settings where users are empowered to make autonomous resource
acquisition decisions, and in which infrastructure providers and users are interested in
selfishly maximizing their own utilities, resource management must be viewed through a
game-theoretic (as opposed to a global optimization) perspective. In this talk, I will
present such a perspective in three distinct settings: overlay network connectivity
management, cloud resource colocation, and shared bandwidth arbitration.
For overlay networks, I will present “Selfish Neighbor Selection” (SNS) as a gametheoretic
connectivity management framework for folding new arrivals into an existing
overlay, and for re-wiring to cope with changing network conditions. I will show that
under typical resource constraints, SNS yields efficient Nash-like equilibria. I will
present experimental results showing the properties of stable SNS wirings on synthetic
and real Internet topologies, as well as results obtained by deploying Egoist – a PlanetLab
SNS prototype system.

For cloud computing, I will present “Colocation Games” (CG) as an economically-sound
framework upon which emerging cloud architectures could be implemented. CGs enable
the modeling and analysis of the dynamics that result when rational, selfish parties
interact in an attempt to minimize the individual costs they incur to secure the shared
cloud resources necessary to support their application QoS or SLA requirements. In
addition to various game-theoretic results, I will overview implementation considerations
as well as results from experimental evaluations.

For shared bandwidth arbitration, I will present “Trade and Cap” (TC) as an economicsinspired
mechanism that incentivizes users to voluntarily coordinate their consumption of
a shared resource so as to converge to what they perceive to be an equitable allocation,
while ensuring efficient resource utilization. Under TC, rather than acting as an arbiter,
providers act as enforcers of what a community of rational users decides is a fair
allocation. In addition to presenting the analytical underpinnings of TC and results from
trace-driven simulations, I will briefly discuss implementation considerations for lastmile
bandwidth arbitration.

This work was pursued at Boston University, primarily in collaboration with Nikos Laoutaris
(now at Telefonica Research), Jorge Londono, and George Smaragdakis (now at Deutche
Telecom).

Mobility Coordination in Sensor and Ad-Hoc Networks
Commonly, research work dealing with (or leveraging) mobility in ad-hoc and/or sensor
networks assumes that node encounters are predestined, in the sense that they are the
result of unknown, exogenous processes that control the mobility of these nodes. In this
talk, I argue that for many applications such an assumption is too restrictive: while the
spatio-temporal coordinates of the start and end points of a node’s journey are determined
by exogenous processes, the specific path that a node may take in space-time, and hence
the set of nodes it may encounter could be influenced in such a way so as to improve the
performance of applications deployed atop such mobile networks. To that end, I will
consider two representative applications: DTN routing in ad-hoc networks and field
monitoring in sensor networks. In both of these settings, mobile nodes are governed by
schedules which exhibit some level of slack – slack that could be leveraged for improved
performance. To that end, we define the Mobility Coordination Problem (MCP) as
follows: Given a set of nodes, each with its own schedule, devise a set of node encounters
that maximizes a given objective function. For DTN routing, I will show that MCP is NPhard,
and propose two detour-based solutions. The first (DMD) is a centralized heuristic
that leverages knowledge of the message workload to suggest specific detours to optimize
message delivery. The second (DNE) is a distributed heuristic that is oblivious to the
message workload, and which selects detours so as to maximize node encounters. We
evaluate the performance of these detour-based approaches using extensive simulations
based on synthetic workloads as well as real schedules obtained from taxi logs in a major
metropolitan area. Our evaluation shows that our centralized, workload-aware DMD
approach yields the best performance, in terms of message delay and delivery success
ratio, and that our distributed, workload-oblivious DNE approach yields favorable
performance when compared to approaches that require the use of data mules and
message ferries. Time permitting; I will summarize results related to mobility
coordination in support of improved field coverage in sensor networks.
This work was pursued in collaboration with Hany Morcos.

Thou Shalt Be A Selfish Overlay Neighbor
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 Nikolaos Laoutaris, Georgios Smaragdakis, Vassilis
Lekakis, Pietro Michiardi, John Byers, and Mema Roussopoulos.

Typed Representation and Analysis of Network Flows for Scalable
and Practical Interoperability Checks
The heterogeneity and open nature of networked systems make analysis of compositions
of components quite challenging, consequently making the design and implementation of
robust network services largely inaccessible to average network architects and network
application programmers. In this talk I will overview a novel type system and associated
type spaces, which constitute accessible representations of the results and conclusions
that are derivable using complex compositional theories. These representations allow a
networking system architect or programmer to be exposed only to the inputs and output
of compositional analysis without having to be familiar with the ins and outs of its
internals. Toward this end, I will present the TRAFFIC (Typed Representation and
Analysis of network Flows For Interoperability Checks) framework, a simple flowcomposition
and typing language with corresponding type system. Next, I will discuss
and demonstrate the expressive power of a type space for TRAFFIC derived from the
network calculus, which allows us to reason about and infer such properties as data
arrival, transit, and loss rates in large composite network applications. The TRAFFIC
compositional analysis framework will be put in action using a prototype implementation
of a type checking and inference engine, which is available for demonstration purposes
using a web interface.

Time permitting, I will also talk about our continuing efforts to integrate the TRAFFIC
framework within snBench, an integrated programming and verification environment for
the compositional development of cyber-physical systems.
This work is pursued in collaboration with Assaf Kfoury, Likai Liu, Ibrahim Matta, and Michael
Ocean, building on prior work with Adam Bradley (PhD'03, now at Amazon Research).