Reconfiguration algorithms for rearrangeable lightwave networks

The authors propose a minimally disruptive approach that transitions the network through a sequence of branch exchange operations, so that only two links are disrupted at any given time. It is shown that the problem of finding the shortest sequence, so as to minimize the duration of the reconfiguration phase, is equivalent to the problem of finding a decomposition of an auxiliary graph into the largest number of vertex-disjoint cycles. The authors then propose and compare three different polynomial-time greedy algorithms, on the basis of performance and time complexity. Noticing that the length of a sequence increases at most linearly with the size of the network, the authors derived the average rate of growth from simulation results