printlogo
ETH Zuerich - Homepage
Computer Engineering and Networks Laboratory (TIK)
 

Publication Details for Inproceedings "Limited Bandwidth in Multiple-Fiber All-Optical Caterpillars: a Minimization Problem"

 

 Back

 New Search

 

Authors: Thomas Erlebach, Aris Pagourtzis, Katerina Potika, Stamatis Stefanakos
Group: Theory of Communication Networks
Type: Inproceedings
Title: Limited Bandwidth in Multiple-Fiber All-Optical Caterpillars: a Minimization Problem
Year: 2003
Month: November
Pub-Key: EPPS03bci
Book Titel: Proceedings of the 1st Balkan Conference on Informatics (BCI 2003)
Pages: 133-146
Abstract: In multiple-fiber WDM networks it is important to minimize the number of active fiber links that need to be allocated in order to satisfy a given communication demand. Minimizing this number results in reduced network cost. Equivalently, one wants to minimize the number of wavelength collisions on each link of the network. This is modeled as the Minimum Collisions Path Multicoloring problem, which differs from the classical path coloring problems in that using the same colors for overlapping paths is now allowed.

More formally, we are given a graph G=(V,E), a set of communication requests (pairs of nodes) and a number of available colors. Requests can be undirected or directed, corresponding to full-duplex or one-way communication respectively. Each request must be assigned a path and a color, and the multiplicity of fibers per edge is determined by the maximum number of paths colored with the same color among paths that use this edge. The goal is to minimize the sum of fiber multiplicities over the network. The caterpillar topology is of particular interest because it often describes real networks or parts of a real network. In this paper we present an efficient approximation algorithm for caterpillar networks with undirected requests; the algorithm achieves approximation ratio 1+5|E*|/OPT (<= 6 in the worst case), where E* is the set of edges used by at least one communication path. By appropriate adaptation of our algorithm we obtain an approximation ratio 1+4|E*|/OPT$ for the case of directed requests. These ratios get closer to 1 as the network traffic increases.

Location: Thessaloniki, Greece
Resources: [BibTeX]

 

 Back

 New Search