Sem Borst, Alcatel-Lucent Bell Labs
& Eindhoven Univ. of Techology
Some Distributed Resource Sharing and Scheduling Problems in
Wireless Networks
We present preliminary results for three loosely related problems
in wireless resource sharing and distributed scheduling.
First, we consider a wireless multi-hop network operating under
a CSMA/CA protocol, where we explicitly track the flow of individual
packets along their end-to-end path. We analyze the joint distribution
of the number of packets pending for transmission at the various
nodes. The results show that the end-to-end throughput may be non-monotone
as function of the ingestion rate of packets. Second, we examine
the problem of distributed scheduling in a system with channel variations.
We discuss a scheme for determining the optimal transmission thresholds
in an adaptive and distributed fashion. Thirdly, we investigate
the performance of various MaxWeight type
scheduling strategies in a system with channel variations and session-level
dynamics. We show that the usual queue-based algorithms no longer
ensure maximum throughput, and explore the scope for alternative
strategies that do achieve stability whenever possible.
Based on joint work with Dee Denteneer, Yahya Al-Harthi, Seva Shneer
and Peter van de Ven.
Short Bio:
Sem Borst received the MSc degree in applied mathematics from the
University of Twente, The Netherlands, in 1990, and the PhD degree
from the University of Tilburg, The Netherlands, in 1994. During
the fall of 1994, he was a visiting scholar at the Statistical Laboratory
of the University of Cambridge, England. In 1995, he joined the
Mathematics of Networks and Systems department of Bell Laboratories
in Murray Hill, USA. He also holds a part-time position as a professor
of Stochastic Operations Research at Eindhoven University of Technology.
Sem Borst is a member of IFIP Working Group 7.3, and serves or has
served as a member of several program committees and editorial boards.
His main research interests are in the area of performance evaluation
and resource allocation algorithms for communication networks.
Ed Knightly, Rice University
Modeling and Experimental Validation of Congestion Control and
Medium Access in Multi-Hop Wireless Networks
Multi-hop wireless networks seek to provide low-cost high-performance
wireless access over large coverage areas. Unfortunately, we will
show that cross-layer interactions of congestion control and carrier
sense multiple access yield starvation of multi-hop flows when competing
with single-hop flows, even with only two competing flows. We will
use a combination of analytical modeling and experiments on a deployed
urban mesh network to understand the origins of starvation, to study
the reasons for failure of prior solutions, and to explore new directions
in protocol design.
Short Bio:
Edward Knightly is a professor of Electrical and Computer Engineering
at Rice University. He received the B.S. degree from Auburn University
in 1991 and the M.S. and Ph.D. degrees from the University of California
at Berkeley in 1992 and 1996 respectively. He served as associate
editor of numerous journals and special issues including IEEE/ACM
Transactions on Networking and IEEE Journal on Selected Areas of
Communications Special Issue on Multi-Hop Wireless Mesh Networks.
He served as technical co-chair of IEEE INFOCOM 2005, general chair
of ACM MobiSys 2007, and served on the program committee for numerous
networking conferences including ICNP, INFOCOM, MobiCom, and SIGMETRICS.
He received the National Science Foundation CAREER Award in 1997
and is a Sloan Fellow since 2001. His research interests are in
the areas of mobile and wireless networks and high-performance and
denial-of-service resilient protocol design.
Vikram Krishnamurthy, University of British
Columbia
Global Games and Correlated Equilibria for Decentralized Spectrum
Access
This talk illustrates two methodologies for decentralized spectrum
access in cognitive radio systems.
In the first approach, given a large number of secondary users that
can access a spectrum hole, we illustrate how a global games approach
can lead to a simple characterization of the Nash equilibrium. We
formulate Bayes-Nash equilibrium conditions
for which a simple threshold strategy is competitively optimal for
each secondary user, and propose a scheme for
decentralized threshold computation. We show that there is a remarkable
phase transition in the behavior as the variance of the estimate
reduces.
In the second methodology, we illustrate how secondary users can
deploy regret based stochastic approximation algorithms for learning
the correlated equilibrium. For the case of agile primary users,
the asymptotic analysis of the algorithm results in a switched differential
inclusion.
Short Bio:
Vikram Krishnamurthy is a professor and Canada Research Chair at
the Department of Electrical Engineering, University of British
Columbia, Vancouver, Canada.Prior to 2002, he was a chaired professor
at the Department of Electrical and Electronic Engineering, University
of Melbourne, Australia. His current research interests include
statistical signal processing,computational game theory, and stochastic
dynamical systems. Much of his recent work focuses on applications
of these methods in wireless communications, sensor networks and
biomolecular simulation.
Armand Makowski, University of Maryland
Intersecting Random Graphs
Given two graphs $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ with same
vertex set $V$, we define their intersection as the graph $(V,E)$
with vertex set $V$ and edge set $E = E_1 \cap E_2$. In this talk
we consider the situation where each of the component graphs is
itself a random graph, e.g.,a Bernoulli random graph, a geometric
random graph or a random key graph. The resulting random graphs
occur naturally as simple models for a number of issues in wireless
networking.
We are interested in understanding how the structural properties
of the component random graphs shape those of the random graph obtained
by intersection. Particular attention will be given to the existence
of zero-one laws for the properties of graph connectivity and the
absence of isolated nodes, and to the form of the associated critical
scalings.
Short Bio:
Armand M. Makowski received the Licence en Sciences Mathematiques
from the Universite Libre de Bruxelles in 1975, the M.S. degree
in Engineering-Systems Science from U.C.L.A. in 1976 and the Ph.D.
degree in Applied Mathematics from the University of Kentucky in
1981. In August 1981, he joined the faculty of the Electrical Engineering
Department at the University of Maryland College Park, where he
is now Professor of Electrical and Computer Engineering. He has
held a joint appointment with the Institute for Systems Research
since its establishment in 1985.
Armand Makowski was a C.R.B. Fellow of the Belgian-American Educational
Foundation (BAEF) for the academic year 1975-76; he is also a 1984
recipient of the NSF Presidential Young Investigator Award and became
an IEEE Fellow in 2006.
His research interests lie in applying advanced methods from the
theory of stochastic processes to the modeling, design and performance
evaluation of engineering systems, with particular emphasis on communication
systems and networks.
Laurent Massoulie, Thomson Research
Content Popularity and User Profiling for Content Placement in
Peer-to-Peer VoD Systems
In this talk we consider the problem of pre-loading video content
at users of a peer-to-peer system, so as to meet content demands
with minimal access to infrastructure servers. We propose to leverage
content popularity distribution as well as user profiling to obtain
maximal benefits. We will discuss optimisation formulations, and
resulting replication strategies that exploit expected demand and
its volatility. We will also discuss ongoing work on user profiling,
in which we advocate the use of particular spectral clustering techniques
to identify profiles of users. Corresponding theoretical guarantees
as well as empirical validation on the NetFlix dataset will be presented.
Based on joint work with Peter Marbach and Dan-Cristian Tomozei
Short Bio:
Laurent Massoulié graduated from Ecole Polytechnique in 1991,
and received a PhD in Automatic Control from Université Paris
Sud in 1995. >From 1995 to 1998 he worked in France Télécom
R&D on traffic control of ATM and IP networks. From 1999 to
2006 he was with Microsoft Research Cambridge. There he worked on
congestion control, overlay management, and peer-to-peer applications
over the Internet. Since 2006 he is a senior researcher in Thomson
Corporate Research, where he is involved in the design of peer-to-peer
applications for multimedia content distribution. He is the recipient
of several best paper awards (IEEE Infocom 1999, ACM Sigmetrics
2005, and ACM Conext 2007).
Mike Neely, University of Southern California
Dynamic Data Compression for Wireless Transmission over a Fading
Channel
We consider a wireless node that randomly receives data from different
sensor units. The arriving data must be compressed, stored, and
transmitted over a wireless link, where both the compression and
transmission operations consume power. Specifically, the controller
must choose from one of multiple compression options every timeslot.
Each option requires a different amount of power and has different
compression ratio properties. Further, the wireless link has potentially
timevarying channels, and transmission rates depend on current channel
states and transmission power allocations. We design a dynamic algorithm
for joint compression and transmission, and prove that it comes
arbitrarily close to minimizing average power expenditure, with
an explicit tradeoff in average delay. The algorithm is simple to
implement and does not require knowledge of probability distributions
for packet arrivals or channel states.
Short Bio:
Michael J. Neely received B.S. degrees in both Electrical Engineering
and Mathematics from the University of Maryland, College Park, in
1997. He then received a 3 year Department of Defense NDSEG Fellowship
for graduate study at the Massachusetts Institute of Technology,
where he received an M.S. degree in EECS in 1999 and a Ph.D. in
2003. During the Summer of 2002, he worked as an intern in the Distributed
Sensor Networks group at Draper Labs in Cambridge. He is currently
an Assistant Professor in the Communication Sciences Institute (CSI),
within the Electrical Engineering Department at the University of
Southern California. His research interests are in the areas of
stochastic network optimization and queueing theory, with applications
to wireless, satellite, mobile ad-hoc networks, and switching systems.
Michael is a member of Tau Beta Pi and Phi Beta Kappa.
Alexandre Proutiere, Microsoft Research
Scheduling Mobile Users in Wireless Systems
In this talk, we present new results for the design and the performance
evaluation of centralized and distributed scheduling schemes in
wireless networks where users / nodes may move. We first explore
the case of networks without user mobility, and briefly recall existing
results on their performance. We also give a new and provably accurate
characterization of the throughput region of random distributed
schemes, such as Aloha or CSMA. We then focus on systems where users
move, and quantify the impact of this mobility on the performance
of scheduling schemes. We finally explain how to design scheduling
algorithms that are able to exploit mobility.
Short Bio:
Alexandre Proutiere is a researcher in the Systems and Networking
group at Microsoft Research, Cambridge, Great Britain. His research
interests are in the design and the performance evaluation of computer
networks, with a specific interest in resource allocation and control
in wireless systems. Before joining Microsoft in June 2007, he was
a senior expert researcher at France Telecom R&D and an assistant
professor in the computer science department of Ecole Normale Superieure
(Paris). He received a PhD in mathematics from Ecole Polytechnique
(Palaiseau, France) in 2003, graduated in mathematics from Ecole
Normale Superieure (Paris), and qualified as an engineer at Ecole
Nationale Superieure des Telecommunications (Paris). He is with
Thomas Bonald the recipient of the best paper award of ACM Sigmetrics
/Performance 2004.
Devavrat Shah, Massachusetts Institute
of Technology
On capacity scaling in arbitrary wireless networks
Information theoretic characterization of exact capacity region
for any reasonable network model remains a non-trivial question
of interest
for information theorists. The notion of scaling of capacity, starting
with work by Gupta and Kumar (2000), has given some traction on
this question and therefore resulted in a sequence of interesting
results over the past decade. The main limitation of this approach
has been two folds: (a) regular network structure and (b) regular
traffic requirement.
In this talk, I will try to get away from these two restrictions
to get closer to the scaling of the whole capacity region for abritrary
networks. Specifically, we will consider network where nodes are
placed arbitrarily in an extended network (with minimum distance
constraint) and traffic requirements are arbitrary. Under standard
(additive i.i.d. Gaussian noise and random fading) channel model,
we will separate our presentation for qualitatively two different
regimes of power attenuation parameter : between (2, 3) and larger
than 3. For both of these cases, we will discuss when we can characterize
the exact capacity scaling and schemes achieving them. We will also
discuss the questions that remain open and the technical difficulties
that we are facing to complete the "scaling program".
This is based on joint works with (a) R. Madan and O. Leveque;
(b) U. Niesen and P. Gupta.
Short Bio:
Devavrat Shah is currently an assistant professor with EECS, MIT
since Fall 2005. He is a member of the Laboratory of Information
and Decision Systems (LIDS). He is also a member of the Operations
Research Center (ORC). He received his BTech degree in Computer
Science & Engg. from IIT-Bombay in 1999 with the honor of the
President of India Gold Medal.
He received his Ph.D. from the Computer Science department, Stanford
University in October 2004. He was a post-doc in the Statistics
department at Stanford in 2004-05.
He was co-awarded the IEEE INFOCOM best paper award in 2004 and
ACM SIGMETRIC/Performance best paper awarded in 2006. He received
2005 George B. Dantzig best disseration award from the INFORMS.
He received NSF CAREER award in 2006. His research interests include
network algorithms, stochastic networks, network information theory
and statistical inference.
Ness Shroff, Ohio State University
Optimizing Energy Efficiency for Sleep-Wake Enabled Sensor Networks
Using "Anycasting"
In wireless sensor networks, a significant fraction of the total
energy consumed is due to the wireless radio. Thus, sending nodes
to sleep results in substantial energy savings. Thus a large number
of papers that have been devoted to the development of efficient
sleep-wake scheduling mechanisms. However, sending the radio to
sleep could also result in excessive delays, which need to be carefully
controlled. To that end, there has been a recent development to
reduce the delay with minimal, if any, additional cost by exploiting
the wireless broadcast medium. This technique is called "anycasting"
and is especially useful for asynchronous wireless sensor networks.
Unlike traditional sleep-wake scheduling mechanisms, in anycasting,
the sending nodes transmits to the first node that awakes in its
forwarding set, which results in significant reduction on the end-to-end
delay. However, the critical challenges with anycasting are in selecting
the forwarding set without an a priori hierarchical structure imposed
in the network, and avoiding looping, without resorting to expensive
global cooperation mechanisms.
The anycasting problem can be formulated as an optimization problem,
e.g., maximizing the network lifetime subject to delay constraints.
However, the problem is inherently non-linear and non-convex and
requires the use of non-traditional tools to solve it. In this talk,
I will describe how we have solved the anycasting problem which
is a joint control problem of how to optimally choose the forwarding
sets, the priorities assigned to the nodes in case more than one
node in a forwarding set is awake, and the rates at which nodes
wake up. I will also describe an optimal anycast algorithm that
minimizes the end-to-end delay of all the nodes simultaneously,
(or alternatively maximizes the network lifetime for a given delay),
is fully distributed, and does not require complex computations.
This is joint work with Joohwan Kim, Xiaojun Lin, and Prasun Sinha
Short Bio:
Ness B. Shroff received his Ph.D. degree from Columbia University,
NY in 1994. He joined Purdue University in November 1994, where
he is currently Professor of Electrical and Computer Engineering
and director of CWSA, a university-wide center on wireless systems
and applications.
His research interests span the areas of wireless and wireline
communication networks. He is especially interested in fundamental
problems in the design, performance, pricing, and security of these
networks. His research is funded by various companies such as Intel,
Hewlett Packard, Nortel, AT&T, BAE systems, and L. G. Electronics;
and government agencies such as the National Science Foundation
(NSF), Defense Advanced Research Projects Agency (DARPA), Indiana
Dept. of Transportation, and the Indiana 21st Century fund.
Dr. Shroff is an editor for IEEE/ACM Trans. on Networking and the
Computer Networks Journal, and past editor of IEEE Communications
Letters. He has served on the technical and executive committees
of several major conferences and workshops. He was the technical
program co-chair of IEEE INFOCOM'03, the premier conference in communication
networking. He was also the conference chair of the 14th Annual
IEEE Computer Communications Workshop (CCW'99), the program co-chair
for the symposium on high-speed networks, Globecom 2001, and the
panel co-chair for ACM Mobicom'02. Dr. Shroff was also a co-organizer
of the NSF workshop on Fundamental Research in Networking, held
in Arlie House Virginia, in 2003.
He received the IEEE INFOCOM 2006 best paper award, the IEEE IWQoS
2006 best student paper award, the 2005 best paper of the year award
for the Journal of Commnications and Networking, the 2003 best paper
of the year award for Computer Networks, and the NSF CAREER award
in 1996 (his INFOCOM 2005 paper was also selected as one of two
runner-up papers for the best paper award).
Patrick Thiran, EPFL Lausanne
Fairness, Spatial Reuse and Phase Transition in 802.11 Networks
IEEE 802.11 is probably the most widely used Medium Access Control
protocol in current wireless networks. In the single-hop setting
(wireless LAN), its performance is quite well understood. In the
multi-hop setting however, there is, to date, no widely accepted
model that captures rigorously all the essential features of the
protocol while staying simple enough to provide insight. Consequently,
when confronted with experimental results, people often find it
hard to interpret them.
We use a continuous-time Markovian loss network to model protocols
``à la 802.11'' in the context of multi-hop ad hoc networks.
It enables us to explore systematically the trade-off between spatial
reuse and fairness, which is inherent to these decentralized CSMA/CA
MAC protocols. We show in particular that the widely observed unfairness
of the protocol in small network topologies does not always persist
in large topologies. In large 1-dim. networks, nodes sufficiently
far away from the border of the network have equal access to the
channel. In 2-dim. networks, we observe a phase transition, linked
to the existence of multiple Gibbs measures in the Markov Random
Field model. If the access intensity of the protocol is small, border
effects remain local and the protocol is long term fair as in 1-dim.
networks. However, for a large enough access intensity, the border
effects persist independently of the size of the network and the
protocol is strongly unfair.
This is joint work with Mathilde Durvy and Olivier Dousse.
Short Bio:
Patrick Thiran is an associate professor at EPFL. He received the
electrical engineering degree from the Université Catholique
de Louvain, Louvain-la-Neuve, Belgium, in 1989, the M.S. degree
in electrical engineering from the University of California at Berkeley,
USA, in 1990, and the PhD degree from EPFL, in 1996. He became an
adjunct professor in 1998, an assistant professor in 2002 and an
associate professor in 2006. From 2000 to 2001, he was with Sprint
Advanced Technology Labs, Burlingame, CA. His research interests
include communication networks, performance analysis, dynamical
systems and stochastic models. He is currently active in the analysis
and design of wireless multi-hop networks and in network monitoring.
He served as an associate editor for the IEEE Transactions on Circuits
and Systems in 1997-99, and he is currently an associate editor
for the IEEE/ACM Transactions on Networking. He was the recipient
of the 1996 EPFL Ph.D. award.
Jean Walrand, University of California,
Berkeley
A Distributed Algorithm for Optimal Throughput and Fairness in
Wireless Networks with a General Interference Model
In multi-hop wireless networks, earlier research on joint scheduling
and congestion control has suggested that MAC-layer scheduling is
the bottleneck. Distributed scheduling for maximal throughput is
difficult since the conflicting relationship between different links
is complex. Existing works on maximal-throughput scheduling usually
assumes synchronized time slots, and in each slot, a maximal-weighted
``independent set'' needs to be found or approximated. However,
this is hard to implement in distributed networks. On the other
hand, a distributed greedy protocol similar to IEEE 802.11 can only
achieve a fraction of the throughput region. In this paper, we introduce
an adaptive CSMA algorithm, which can achieve the maximal throughput
distributedly under some assumptions. The intuitive idea is that
each link should adjust its aggressiveness of transmission based
on its backlog. Furthermore, we combine the algorithm with end-to-end
flow control to achieve fairness among competing flows. The effectiveness
of the algorithm is verified by simulations.
This is joint work with Libin Jiang.
Short Bio:
Jean Walrand has been a professor in the Department of Electrical
Engineering and Computer Science at U.C. Berkeley since 1982. His
research interests include stochastic processes, queuing theory,
communication networks, control systems and applied game theory.
He has published three books. He is a fellow of the IEEE.
Edmund Yeh, Yale University
Information Dissemination in Mobile Wireless Networks
In wireless networks, node mobility may be exploited to assist
in information dissemination over time. We analyze the latency for
information dissemination in large-scale mobile wireless networksTo
study this problem, we map a network of mobile nodes to a network
of stationary nodes with dynamic links. We then use results from
percolation theory to show that under a constrained i.i.d. mobility
model, the scaling behavior of the latency falls into two regimes.
When the network is not percolated (subcritical), the latency scales
linearly with the initial Euclidean distance between the sender
and the receiver; when the network is percolated (supercritical),
the
latency scales sub-linearly with the distance.
Joint work with Zhenning Kong, Yale University
Short Bio:
Edmund Yeh received his Bachelor of Science in Electrical Engineering
with Distinction from Stanford University in 1994. In the same year,
he was awarded one of ten Winston Churchill Scholarships for overseas
study in science and engineering at Churchill College, University
of Cambridge, in the United Kingdom. He received his Master of Philosophy
in Electrical Engineering from the University of Cambridge in 1995.
As a doctoral student, he studied under Professor Robert G. Gallager
at the Laboratory for Information and Decision Systems at the Massachusetts
Institute of Technology. He received his Ph.D. in Electrical Engineering
and Computer Science from MIT in 2001. Since July 2001, he has been
on the faculty at Yale University, New Haven, Connecticut, where
he is currently an Associate Professor of Electrical Engineering
(with joint appointments in the Departments of Computer Science
and Statistics). During the summer of 2004, Dr. Yeh was an Invited
Professor at the Information Theory Laboratory of the Swiss Federal
Institute of Technology (EPFL), Lausanne, Switzerland. In fall 2004,
Dr. Yeh was a visitor at MIT, Princeton University, and University
of California at Berkeley.
Dr. Yeh is a recipient of the U.S. Army Research Office (ARO) Young
Investigator Program (YIP) Award. He is a member of the Technical
Program Committees for IEEE Infocom (2005-2007), IEEE Globecom (2004),
and WiOpt (2006-2008). As a graduate student, he received the National
Science Foundation and Office of Naval Research Fellowships for
graduate study. As an undergraduate student, he received the Frederick
E. Terman Award in 1994, the Barry M. Goldwater Scholarship from
the United States Congress in 1993, and the Stanford President's
Award for Academic Excellence in 1991. He is a member of Phi Beta
Kappa, Tau Beta Pi, and IEEE. He has spent a number of summers working
at industrial labs, including the Mathematical Sciences Research
Center at Bell Laboratories, Lucent Technologies (1998-1999), the
Signal Processing Research Department at AT&T Bell Laboratories
(1993-1994), and the Space and Communications Group at Hughes Electronics
Corporation (1991-1992).
Dr. Yeh's research interests are in the fields of information theory,
communication theory, queueing theory, wireless systems, and data
networks.
