Analysis and design of ring-based transport networks

We introduce several new methods for the design of near-optimal telecommunication transport networks based on survivable ring architectures. Network survivability is an increasingly important issue for customers and network operators alike due to increased reliance on telecommunications services and the deployment of ultra-high capacity transmission systems. Survivable ring architectures provide a robust and cost-effective means to maintain service availability in the presence of network faults such as cable cuts, equipment failure and human error. For these reasons, they have already been widely deployed in current SONET transport networks and are a promising candidate for providing network survivability in emerging optical transport networks based on wavelength-division multiplexing.; The design of ring-based transport networks, however, is a notoriously difficult combinatorial optimization problem. For networks of any real practical size, the number of possible designs is virtually infinite and network construction costs can vary substantially from one design to another. Yet surprisingly, much this design work is still done using manual approaches that can take months to generate a single solution. Although several automated design methods have been proposed in the literature, none of these methods guarantees optimal solutions. With typical constructions costs in the range of billions of dollars, even modest improvements of only a few percent can translate into millions of dollars in savings.; We develop several improvement heuristics for a greedy heuristic that constructs a design one ring at a time. These improvement heuristics include a balanced ring loading heuristic that optimizes the routing of demands around a ring, a demand packing algorithm that routes unserved demands within the slack capacity available at each iteration, and a dithered sequencing approach that randomizes the constructive process to yield several alternative designs. We also introduce three new mathematical programming formulations of the design problem as well as a new Tabu Search meta-heuristic that explores alternative solutions by guiding a local search method.; The performance of these methods is compared using a defined set of study network models. Results show that these methods provide significant improvements in the design optimality relative to benchmark solutions. In one test case, for example, the best solution was 38% lower in cost than the previous benchmark solution. A novel lower bounding procedure and statistical inference are also used to quantify the gap from optimality of the design results.