Technical Report CS-2011-07

Title: Optimizing Regenerator Cost in Traffic Grooming
Authors: Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom and Shmuel Zaks
Abstract: In optical networks regenerators have to be placed on lightpaths every d nodes in order to regenerate the signal. In addition, grooming enables the use of the same regenerator by several lightpaths. Up to g (the grooming factor) lightpaths can use the same regenerator. In this work we consider the problem of minimizing the number of regenerators used in traffic grooming in optical networks. Starting from the 4-approximation algorithm of[10] for d = 1 and a path topology, we provide an approximation algorithm with the same approximation ratio for d = 1 and the ring and tree topologies. We present also a technique based on matching that leads to the same approximation ratio in tree topology and can be used to obtain approximation algorithms in other topologies. We provide an approximation algorithm for general topology that uses this technique. Finally, all the results are extended to the case of general d.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2011
To the main CS technical reports page

Computer science department, Technion