Preface
A representative of a major publishing house is on her way home from a conference
in Singapore, excited about the possibility of a new book series. On the flight home to
New York she opens her blackberry organizer, adding names of new contacts, and is
disappointed to realize she may have caught the bug that was bothering her friend Alex
at the caf´e near the conference hotel. When she returns home she will send Alex an
email to see how she’s doing, and make sure this isn’t a case of some new dangerous
flu.
Of course, the publisher is aware that she is part of an interconnected network of
other business men and women and their clients: Her value as an employee depends on
these connections. She depends on the transportation network of taxis and airplanes to
get her job done, and is grateful for the most famous network today that allows her to
contact her friend effortlessly even when separated by thousands of miles. Other net-
works of even greater importance escape her consciousness, even though consciousness
itself depends on a highly interconnected fabric of neurons and vascular tissue. Com-
munication networks are critical to support the air traffic controllers who manage the
airspace around her. A supply chain of manufacturers make her book business possible,
as well as the existence of the airplane on which she is flying.
Complex networks are everywhere. Interconnectedness is as important to business
men and women as it is to the viruses who travel along with them.
Much of the current interest in networks within physics and the biological sciences
is phenomenological. For example, given a certain degree of connectivity between in-
dividuals, what is the likelihood that a virus will spread to the extinction of the planet?
Degree and mode of connectivity in passive agents can combine to form images resem-
bling crystals or snowflakes [
463].
The main focus within our own bodies is far more utilitarian. Endocrine, immune,
and vascular systems adjust chemical reactions to maintain equilibria in the face of on-
going attacks from disease and diet. In biology this is called homeostasis. In this book,
the regulation of a network is called control.
It is not our goal to take on biology, computer science, communications, and op-
erations research in a single volume. Rather, the intended purpose of this book is an
introduction to a rapidly evolving engineering discipline. The examples come from
applications where complexity is real, but less daunting than found in the human brain.
We describe methods to model networks in order to capture essential structure, dy-
namics, and uncertainty. Based on these models we explore ways to visualize network
behavior so that effective control techniques can be synthesized and evaluated.
2
Control Techniques for Complex Networks Draft copy April 22, 2007
3
Modeling and control The operator of an electric power grid hopes to find a network
model that will help form predictions of supply and demand to maintain stability of
the power network. This requires the expertise of statisticians, economists, and power
engineers. The resulting model may provide useful simulations for forecasting, but will
fail entirely for our purposes. This book is about control, and for this it is necessary to
restrict to models that capture essential behavior, but no more.
Modeling for the purposes of control and the development of control techniques for
truly complex networks has become a major research activity over the past two decades.
Breakthroughs obtained in the stochastic networks community provide important tools
that have had real impact in some application areas, such as the implementation of
MaxWeight scheduling for routing and scheduling in communications. Other break-
throughs have had less impact due in part to the highly technical and mathematical
language in which the theory has developed. The goal of this book is to expose these
ideas in the simplest possible setting.
Most of the ideas in this book revolve around a few concepts.
(i) The fluid model is an idealized deterministic model. In a communication network
a unit of ‘fluid’ corresponds to some quantities of packets; in a power network this
might correspond to a certain number of megawatts of electricity.
A fluid model is often a starting point to understand the impact of topology,
processing rates, and external arrivals on network behavior. Based on the fluid
model we can expose the inherent conflict between short-sighted control objec-
tives, longer-range issues such as recovery from a singular external disruption,
and truly long-range planning such as the design of appropriate network topology.
(ii) Refinements of the fluid model are developed to capture variability in supply, de-
mand, or processing rates. The controlled random walk model favored in this
book is again a highly stylized model of any real network, but contains enough
structure to give a great deal of insight, and is simple enough to be tractable for
developing control techniques.
For example, this model provides a vehicle for constructing and evaluating hedg-
ing mechanisms to limit exposure to high costs, and to ensure that valuable re-
sources can operate when needed.
(iii) The concept of workload is developed for the deterministic and stochastic models.
Perhaps the most important concept in this book is the workload relaxation that
provides approximations of a highly complex network by a far simpler one. The
approximation may be crude in some cases, but its value in attaining intuition can
be outstanding.
(iv) Methods from the stability theory of Markov models form a foundation in the treat-
ment of stochastic network models. Lyapunov functions are a basis of dynamic
programming equations for optimization, for stability and analysis, and even for
developing algorithms based on simulation.
Control Techniques for Complex Networks Draft copy April 22, 2007
4
What’s in here? The book is divided into three parts. The first part entitled modeling
and control contains numerous examples to illustrate some of the basic concepts devel-
oped in the book, especially those topics listed in (i) and (ii) concerning the fluid and
CRW models. Lyapunov functions and the dynamic programming equations are intro-
duced; Based on these concepts we arrive at the MaxWeight policy along with many
generalizations.
Workload relaxations are introduced in Part II. In these three chapters we show
how a cost function defined for the network can be ‘projected’ to define the effective
cost for the relaxation. Applications to control involve first constructing a policy for
the low-dimensional relaxation, and then translating this to the original physical system
of interest. This translation step involves the introduction of hedging to guard against
variability.
Most of the control techniques are contained in the first two parts of the book.
Part III entitled Stability & Performance contains an in-depth treatment of Lyapunov
stability theory and optimization. It contains approximation techniques to explain the
apparent solidarity between control solutions for stochastic and deterministic network
models. Moreover, this part of the book develops several approaches to performance
evaluation for stochastic network models.
Who’s it for? The book was created for several audiences. The gradual development
of network concepts in Parts I and II was written with the first-year graduate student
in mind. This reader may have had little exposure to operations research concepts, but
some prior exposure to stochastic processes and linear algebra at the undergraduate
level.
Many of the topics in the latter chapters are at the frontier of stochastic networks,
optimization, simulation and learning. This material is intended for the more advanced
graduate student, as well as researchers and practitioners in any of these areas.
Acknowledgements This book has been in the making for five years and over this
time has drawn inspiration and feedback from many. Some of the ideas were developed
in conjunction with students, including Mike Chen, Richard Dubrawski, Charuhas Pan-
dit, Rong-Rong Chen, and David Eng. In particular, the numerics in Section
7.2 are
largely taken from Dubrawski’s thesis [
153], and the diffusion heuristic for hedging is
based on a paper with Chen and Pandit [
106]. Section 9.6 is based in part on research
conducted with Chen [
107].
My collaborators are a source of inspiration and friendship. Many of the ideas
in this book revolve around stochastic Lyapunov theory for Markov processes that is
summarized in the appendix. This appendix is essentially an abridged version of my
book co-authored with Richard Tweedie [
367]. Vivek Borkar’s research on Markov
decision theory (as summarized in [
74]) has had a significant influence on my own view
of optimization. My interest in networks was sparked by a lecture presented by P.R.
Kumar when he was visiting the Australian National University in 1988 while I resided
there as a postdoctoral fellow. He became a mentor and a coauthor when I joined the
University of Illinois the following year. I learned of the beauty of simulation theory
Control Techniques for Complex Networks Draft copy April 22, 2007
5
from the work of Peter Glynn and his former student Shane Henderson. More recent
collaborators are Profs. In-Koo Cho, David Gamarnik, Ioannis Kontoyiannis, and Eric
Moulines, who have provided inspiration on a broad range of topics. I am grateful to
Devavrat Shah and Damon Wischik for sharing insights on the “input-queued switch”,
and for allowing me to adapt a figure from their paper [
435] that is used to illustrate
workload relaxations in Section
6.7.1. Pierre L’Ecuyer shared his notes on simulation
from his course at the University of Montr´eal, and Bruce Hajek at the University of
Illinois shared his lecture notes on communication networks.
Profs. Cho, Kontoyiannis, Henderson, and Shah have all suggested improvements
on exposition, or warned of typos. Sumit Bhardwaj, Jinjing Jiang, Shie Mannor, Eric
Moulines, and Michael Veatch each spent significant hours pouring through selected
chapters of draft text and provided valuable feedback. Early input by Veatch moved the
book towards its present organization with engineering techniques introduced first, and
harder mathematics postponed to later chapters.
Any remaining errors or awkward prose are, of course, my own.
It would be impossible to write a book like this without financial support for grad-
uate students and release-time for research. I am sincerely grateful to the National
Science Foundation, in particular the Division of Electrical, Communications & Cyber
Systems, for on-going support during the writing of this book. The DARPA ITMANET
initiative, the Laboratory for Information and Decision Systems at MIT, and United
Technologies Research Center provided support in the final stages of this project dur-
ing the 2006-2007 academic year.
Equally important has been support from my family, especially during the last
months when I have been living away from home. Thank you Belinda! Thank you
Sydney and Sophie! And thanks also to all the poodles at South Harding Drive.
Dedication
It was a sad day on June 7, 2001 when Richard Tweedie died at the peak of his career.
A brief survey of his contributions to applied probability and statistics can be found in
[
156].
In memory of his friendship and collaboration, and in honor of his many contribu-
tions to our scientific communities, this book is dedicated to Richard.
