REARRANGEABLE MULTIHOP LIGHTWAVE NETWORKS - CONGESTION MINIMIZATION ON REGULAR TOPOLOGIES

We address the design of rearrangeable multihop lightwave networks hav ing regular connectivity topology (such as Perfect Shuffle CPS), de Br uijn (dB) graph, GEneralized shuffle-exchange Multihop NETwork (GEMNET ) and Manhattan Street Network (MSN)). We propose a new formulation of the combined station assignment/flow routing problem with the congest ion minimization objective. The formulation is applicable to any regul ar topology. We then develop a heuristic solution strategy based on ta bu search. Given our objective, we want to assess the merit of a regul ar versus an arbitrary topology, as well as compare different regular topologies across several data instances. In terms of achieving small congestion las obtained heuristically), the results suggest that with increased problem sizes, regular topologies become more attractive. In such cases the benefit of having less restricted arbitrary network to pology might not be fully utilized. Equivalently,having regular topolo gy for larger instances will still provide a large enough search space to (heuristically) obtain good throughput (i.e., small congestion). M oreover, such design will implicitly offer benefits associated with ma nagement and operations of regular topologies.