On minimum congestion routing in rearrangeable multihop lightwave networks

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 node i and a receiver at node j 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.