2005 | OriginalPaper | Chapter
Approximating the Traffic Grooming Problem
Authors : Michele Flammini, Luca Moscardelli, Mordechai Shalom, Shmuel Zaks
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The problem of grooming is central in studies of optical networks. In graph-theoretic terms, this can be viewed as assigning colors to the lightpaths so that at most
g
of them (
g
being the
grooming factor
) can share one edge. The cost of a coloring is the number of optical switches (ADMs); each lightpath uses two ADM’s, one at each endpoint, and in case
g
lightpaths of the same wavelength enter through the same edge to one node, they can all use the same ADM (thus saving
g
– 1 ADMs). The goal is to minimize the total number of ADMs. This problem was shown to be NP-complete for
g
= 1 and for a general
g
. Exact solutions are known for some specific cases, and approximation algorithms for certain topologies exist for
g
= 1. We present an approximation algorithm for this problem. For every value of
g
the running time of the algorithm is polynomial in the input size, and its approximation ratio for a wide variety of network topologies – including the ring topology – is shown to be 2 ln
g
+
o
(ln
g
). This is the first approximation algorithm for the grooming problem with a general grooming factor
g
.