DIMACS TR: 97-02
Demand Routing and Slotting on Ring Networks
Authors: Tamra Carpenter, Steven Cosares, and Iraj Saniee
ABSTRACT
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