|
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] |