Generic Dijkstra for Optical Networks
share
We present the generic Dijkstra shortest path algorithm: an efficient algorithm for finding a shortest path in an optical network, both in a wavelength-division multiplexed network, and an elastic optical network. Our algorithm is an enabler of the real-time softwarized control of large-scale networks, and not only optical, we believe. The Dijkstra algorithm is a generalization of the depth-first search, and we generalize the Dijkstra algorithm further to resolve the continuity and contiguity constraints of the frequency slot units. Specifically, we generalize the notion of a label, change what we iterate with, and reformulate the edge relaxation so that vertices are revisited, loops avoided, and worse labels discarded. We also used the typical constriction during edge relaxation to take care of the signal modulation constraints. The algorithm can be used with various spectrum allocation policies. We motivate and discuss the algorithm design, and provide our libre, high-quality, and generic implementation using the Boost Graph Library. We carried out 85000 simulation runs for realistic and random networks (Gabriel graphs) of 75 vertices with about a billion shortest-path searches, and found that the proposed algorithm outperforms considerably other three competing optimal algorithms, which are frequently used in research.
READ FULL TEXT