Fast reconfiguration algorithms for time, space, and wavelength dilated optical Benes networks

Abstract

Benes networks are rearrangeable nonblocking networks and are among the most efficient switching architectures in terms of the number of switching elements (SEs) used. In optical Benes networks, if two I/O connecting paths with the same (close) wavelength(s) share a common SE, crosstalk occurs. In order to reduce the crosstalk effect, three approaches, time, space and wavelength dilations have been proposed. In this paper, we present polylogarithmic-time reconfiguration algorithms for realizing any (partial) permutation in time, space and wavelength dilated optical Benes networks using a linear number of processors. Our algorithms are based on a logarithmic-time permutation decomposition algorithm and apply graph coloring techniques such as edge coloring, equitable coloring and vertex coloring.

Keywords:

• Optical switching
• Crosstalk
• Wavelength assignment
• Parallel algorithm
• Graph coloring
• Benes network

Keywords:

• 68W10 Parallel algorithms
• 94C10 Switching theory
• 05C85 Graph algorithms
• 05C15 Coloring of graphs and hypergraphs

Notes

^†In this paper, the crosstalk is referred to the first-order crosstalk [31].

^‡In this paper, all logarithms are in base 2.

^¶A graph is even (resp. odd) if it contains even (resp. odd) number of edges.