A Universal Spectrum Symmetry-Free Algorithm for Routing and Spectrum Assignment (RSA)

We present the first spectrum symmetry-free model for the routing and spectrum assignment (RSA) problem. This model allows for the design of more efficient algorithms as it eliminates from consideration an exponential number of equivalent symmetric solutions. By sidestepping symmetry, the RSA solution space is naturally and optimally decomposed into a routing space and a connection permutation space. Building upon this property, we introduce a two-parameter, symmetry-free algorithm that is universal in that it can be used to tackle any RSA variant in a uniform manner. The algorithm is amenable to multi-threaded execution to speed up the search process and the value of the parameters can be adjusted to strike a balance between running time and solution quality. Our evaluation provides insight into the relative benefits of path diversity (which determines the size of the routing space) and connection diversity (which determines the size of the permutation space).