On minimum congestion routing in rearrangeable multihop lightwave networks |
| |
Authors: | Jadranka Skorin-Kapov Jean-François Labourdette |
| |
Institution: | (1) W.A. Harriman School for Management and Policy, State University of New York at Stony Brook, 11794-3775 Stony Brook, NY;(2) AT&T Bell Laboratories, 07733 Holmdel, NJ |
| |
Abstract: | In this article we consider the problem of minimizing the congestion in logically rearrangeable multihop lightwave networks.
Namely, we consider a network in which each node is equipped with a small number of transmitters and receivers, and tuning
a transmitter at nodei and a receiver at nodej to the same wavelength creates a logical link (i, j) through which traffic could be sent. For a given traffic matrix-the matrix of flows between nodes—the objective is to find
the best connectivity diagram and the corresponding flow assignment so that the maximal flow on any link is minimized. We
develop a tabu search heuristic that yields a suboptimal connectivity diagram and an optimal flow assignment on it. Computational
experiments are conducted on some benchmark data sets, on a real-world traffic matrix, and on some randomly generated problems
of larger dimension. The results are compared with known results from the literature and with a known greedy approach. The
results suggest that a tabu search—based heuristic is a promising approach for handling this NP-hard combinatorial problem.
In addition, we discuss the performance of the method in view of different patterns of input data. |
| |
Keywords: | logically rearrangeable networks multihop optical networks tabu search |
本文献已被 SpringerLink 等数据库收录! |
|