Scalable node-disjoint and edge-disjoint multiwavelength routing

Yi-Zhi Xu, Ho Fai Po, Chi Ho Yeung, David Saad

Research output: Contribution to journalArticlepeer-review


Probabilistic message-passing algorithms are developed for routing transmissions in multiwavelength optical communication networks, under node- and edge-disjoint routing constraints and for various objective functions. Global routing optimization is a hard computational task on its own but is made much more difficult under the node- and edge-disjoint constraints and in the presence of multiple wavelengths, a problem which dominates routing efficiency in real optical communication networks that carry most of the world's internet traffic. The scalable principled method we have developed is exact on trees but provides good approximate solutions on locally treelike graphs. It accommodates a variety of objective functions that correspond to low latency, load balancing, and consolidation of routes and can be easily extended to include heterogeneous signal-to-noise values on edges and a restriction on the available wavelengths per edge. It can be used for routing and managing transmissions on existing topologies as well as for designing and modifying optical communication networks. Additionally, it provides the tool for settling an open and much-debated question on the merit of wavelength-switching nodes and the added capabilities they provide. The methods have been tested on generated networks such as random-regular, Erdős Rényi, and power-law graphs, as well as on optical communication networks in the United Kingdom and United States. They show excellent performance with respect to existing methodology on small networks and have been scaled up to network sizes that are beyond the reach of most existing algorithms.
Original languageEnglish
Article number044316
Number of pages20
JournalPhysical Review E
Issue number4
Publication statusPublished - 21 Apr 2022

Bibliographical note

©2022 American Physical Society. Scalable node-disjoint and edge-disjoint multiwavelength routing. Yi-Zhi Xu, Ho Fai Po, Chi Ho Yeung, and David Saad. Phys. Rev. E 105, 044316 – Published 21 April 2022

Funding Information:
D.S. and Y.Z.X. acknowledge support from the Engineering and Physical Sciences Research Council (EPSRC) Programme Grant TRANSNET (Grant No. EP/R035342/1) and thank Caterina De Bacco for pointing us to her code available on GitHub. The work by C.H.Y. and H.F.P. is supported by the Research Grants Council of the Hong Kong Special Administrative Region, China (Projects No. EdUHK GRF 18304316, No. GRF 18301217, and No. GRF 18301119), the Dean's Research Fund of the Faculty of Liberal Arts and Social Sciences (Projects No. FLASS/DRF 04418, No. FLASS/ROP 04396, and No. FLASS/DRF 04624), and the Internal Research Grant (Project No. RG67 2018-2019R R4015 and No. RG31 2020-2021R R4152), The Education University of Hong Kong, Hong Kong Special Administrative Region, China. D.S. and Y.Z.X. thank Ruijie Luo, Robin Matzner, and Polina Bayvel for insightful comments on practical routing in optical communication systems.


Dive into the research topics of 'Scalable node-disjoint and edge-disjoint multiwavelength routing'. Together they form a unique fingerprint.

Cite this