Abstract

We present the generic Dijkstra shortest-path algorithm: an efficient algorithm for finding a shortest path in an optical network, in both a wavelength-division multiplexed network and an elastic optical network (EON). The proposed algorithm is an enabler of real-time softwarized control of large-scale networks and is not limited to optical networks. The Dijkstra algorithm is a generalization of the breadth-first search, and we generalize the Dijkstra algorithm further to resolve the continuity and contiguity constraints of the frequency slot units required in EONs. 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 use 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 free, reliable, and generic implementation using the Boost Graph Library. We carried out 85,000 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 three other competing optimal algorithms that are frequently used.

© 2019 Optical Society of America

Full Article  |  PDF Article
OSA Recommended Articles
Dynamic Routing and Spectrum Allocation in Elastic Optical Networks With Mixed Line Rates

Xiong Wang, Kaixuan Kuang, Sheng Wang, Shizhong Xu, Hong Liu, and Gordon Ning Liu
J. Opt. Commun. Netw. 6(12) 1115-1127 (2014)

Routing, Modulation, and Spectrum Assignment in Programmable Networks Based on Optical White Boxes

Vahid Abedifar, Marija Furdek, Ajmal Muhammad, Mohammad Eshghi, and Lena Wosinska
J. Opt. Commun. Netw. 10(9) 723-735 (2018)

Graph-Model-Based Dynamic Routing and Spectrum Assignment in Elastic Optical Networks

Ching-Fang Hsu, Yuan-Chih Chang, and Siou-Ci Sie
J. Opt. Commun. Netw. 8(7) 507-520 (2016)

References

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Figures (4)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Tables (6)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription

Equations (4)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access OSA Member Subscription