Robust Network Design for Stochastic Traffic Demands

This paper addresses the problem of logical topology design for optical backbone networks subject to stochastic traffic demands. The network design problem is broken into three tasks: traffic routing, capacity allocation, and link placement. While the routing and capacity allocation subproblem can be formulated using convex optimization, it is prohibitive to add the link placement component to the nonlinear formulation since the link placement problem involves integer variables. To address this issue, we develop a linear formulation for the routing and capacity allocation subproblem by applying tools from robust optimization. We show that this linear formulation performs comparably to the optimal nonlinear formulation. Our formulation can then be used to solve the link-placement subproblem for stochastic traffic. We show that optimal logical topologies for deterministic traffic demands are not necessarily optimal for stochastic traffic demands. We develop algorithms for finding logical topologies optimized for stochastic traffic.