Joint Optimization for Robust Network Design and Operation

Abstract:

The Internet is an essential part of modern life, and Internet Service Provider (ISP) backbone
networks are integral to our Internet experience. Therefore, ISPs must build networks that
limit congestion, even when some equipment fails. This network design problem is complicated, because an optimal network design must consider the eventual runtime configuration.
An ISP makes network design decisions, such as purchasing and placing equipment, on long
timescales (months or years) and network operation decisions, such as routing packets, on
short timescales (seconds). Design and operation interact such that the ISP must solve the
network operation problem as a sub-problem of network design, rendering the network design
problem difficult to formulate and computationally complex.
Today ISPs resort to a variety of simplifications; they fail to take advantage of the
reconfigurability offered by modern optical equipment or the opportunity to mix more- and
less-powerful switches throughout their networks. In this dissertation, we show how ISPs can
incorporate each of these factors into their network design and operation models to produce
less expensive networks without compromising robustness.
In Chapter 2, we explain how reconfigurable optical switches fundamentally change the
network design and operation problems by shifting the boundary between what is fixed at
design time and what is reconfigured at runtime. Then, we present an optimal formulation
for this new problem and heuristics to help our solution scale. In Chapter 3, we describe a
failure recovery protocol that allows ISPs to realize many of the benefits of outfitting their
networks with a homogeneous collection of powerful, “smart” switches, while instead using
a combination of these expensive boxes and less expensive, “dumb” switches.
We make three contributions in each chapter. First, we formulate the network design
optimization by extending the multicommodity flow framework to leverage colorless and
directionless Reconfigurable Optical Add/Drop Multiplexers (Chapter 2) or heterogeneous
nodes (Chapter 3). Second, we devise heuristics to scale our designs to larger topologies.
Finally, we evaluate our ideas on a realistic backbone topology and traffic demands