PVD: An Efficient Routing Algorithm for Optical Networks with Instantaneous Demands

To overcome the wastage of resources on recalculation when instantaneous demands are ubiquitous in optical networks, it is of profound import for operators to engender a cost-effective algorithm. We characterize this new scenario as a mathematical problem with multiple constraints and multiple demands. To tackle this optimization problem, we propose a novel optimal routing algorithm based on Dijkstra's algorithm, which encompasses two subroutines: 1) construct a virtual graph; 2) search for the optimal optical link. A theoretical proof of the optimality of the algorithm and an analysis of its complexity are given. Furthermore, we release a new dataset for follow-up research. By conducting numerous simulations at different scales and settings, we demonstrate the improvement (62.5× speedup in the dataset and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1.3 \mathrm{x}-31.22 \mathrm{x}$</tex> speedup in simulation) of our proposed algorithm over the state-of-the-art for computational time and find that the algorithm still performs well on large-scale problems.