DIMACS TR: 97-02

Demand Routing and Slotting on Ring Networks

Authors: Tamra Carpenter, Steven Cosares, and Iraj Saniee


We describe an important class of problems that arise in the economic design of "survivable" networks. Such networks are capable of accommodating all of the traffic between pairs of locations, even if some arbitrary link or node in the network is rendered unusable. Cycles play an important role in the design of survivable networks because they represent two-connected subnetworks of minimal size. To cost-effectively utilize cycles, we must determine the minimum capacity required for the links in the cycle, subject to constraints on how traffic must be routed and how capacity must be utilized. Depending upon the situation being modeled, different versions of the problem arise. The least restrictive versions are solvable in polynomial time, while the more restrictive (and more realistic) versions are NP-hard. This paper focuses on variants of the problem in which time-slot assignment constraints are enforced to model the operation of the equipment placed at the nodes of a SONET ring. We present several simple heuristic methods for addressing the problem, and we show that they are 2-approximation algorithms.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-02.ps.gz
DIMACS Home Page