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.