Alternative route search algorithm for robust and balanced traffic in telecommunication network
ADVA Optical Networking
E-mail: miwiktor@o2.pl
Received:
Received: 10 July 2018; revised: 29 January 2019; accepted: 04 February 2019; published online: 31 March 2019
DOI: 10.12921/cmst.2018.0000038
Abstract:
This paper discusses routing policy in optical transport networks. Dijkstra’s shortest path algorithm is compared to a new path computation technique based on heuristics originated from human behavior combined with spectral graph embedding. The two-step procedure allows one to separate the computationally expensive and computationally cheap parts for efficient implementation in network infrastructure.
Key words:
optical transport networks, path computation, spectral graph embedding
References:
[1] J. de Santi, A. Drummond, N. de Fonesca, X. Chen, A. Jukan, Leveraging Multipath Routing and Traffic Grooming for and Efficient Load Balancing in Optical Networks, IEEE Trans on Optical Networks and Systems, 2989–2993 (2012).
[2] A. Rahman, N.M. Sheikh, Modified Bidirectional Reservation on Burst drop with Dynamic Load Balance in Optical Burst Switching, 11th Int Conference on Telecommunications – ConTel 2011, Graz Austria.
[3] J. Zhang, S. Wang, K. Zhu, L. Sone, D. Datta, Y. Kim, B. Mukherjee, Optimized Routing for Fault Management in Optical Burst-Switched WDM Networks, IEEE Journal of Selected Areas in Communication 25(6), 111–120 (2007).
[4] M. Chamania, A. Jukan, A Survey of Inter-Domain Peering and Provisioning Solutions for the Next Generation Optical Networks, IEEE Communication Surveys and Tutorials, 11(1), 33–51 (2009).
[5] P. Idziaszek et al, Visualisation of Relational Database Structure by Graph Database, CMST 22(4), 217–224 (2016).
[6] C.D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM 2000.
[7] B. Luo, R. Wilson, E.R. Hancock, Spectral embedding of graphs, Pattern Recognition, 36(10), 2213–2230 (2003).
[8] S. Hardy, Romtelecom taps ADVA FSP 3000 for multiple networks, Lightwave, June 2011, https://www.lightwaveonline.com/articles/2011/06/romtelecom-taps-adva-fsp-3000-formultiple-networks-123097013.html, (access 20.11.2018)
[9] T. Eilam-Tzoreff, The disjoint shortest paths problem, Discrete Applied Mathematics, 8(2), 113–138 (1998).
[10] L, Guo, Y. Deng, K. Liao, Q. He, T. Sellis, Z. Hu, A Fast Algorithm for Optimally Finding Partially Disjoint Shortest Paths, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18).
[11] Ultra low latency networks. Application Note, ADVA Optical networking 2012 (available online, www.advaoptical.com).
[12] OSPF Version 2, protocol specification, RFC 2328.
[13] R. Dechter, J. Pearl, Generalized best-first search strategies and the optimality of A*, Journal of the ACM 32(3), 505–536 (1985).
This paper discusses routing policy in optical transport networks. Dijkstra’s shortest path algorithm is compared to a new path computation technique based on heuristics originated from human behavior combined with spectral graph embedding. The two-step procedure allows one to separate the computationally expensive and computationally cheap parts for efficient implementation in network infrastructure.
Key words:
optical transport networks, path computation, spectral graph embedding
References:
[1] J. de Santi, A. Drummond, N. de Fonesca, X. Chen, A. Jukan, Leveraging Multipath Routing and Traffic Grooming for and Efficient Load Balancing in Optical Networks, IEEE Trans on Optical Networks and Systems, 2989–2993 (2012).
[2] A. Rahman, N.M. Sheikh, Modified Bidirectional Reservation on Burst drop with Dynamic Load Balance in Optical Burst Switching, 11th Int Conference on Telecommunications – ConTel 2011, Graz Austria.
[3] J. Zhang, S. Wang, K. Zhu, L. Sone, D. Datta, Y. Kim, B. Mukherjee, Optimized Routing for Fault Management in Optical Burst-Switched WDM Networks, IEEE Journal of Selected Areas in Communication 25(6), 111–120 (2007).
[4] M. Chamania, A. Jukan, A Survey of Inter-Domain Peering and Provisioning Solutions for the Next Generation Optical Networks, IEEE Communication Surveys and Tutorials, 11(1), 33–51 (2009).
[5] P. Idziaszek et al, Visualisation of Relational Database Structure by Graph Database, CMST 22(4), 217–224 (2016).
[6] C.D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM 2000.
[7] B. Luo, R. Wilson, E.R. Hancock, Spectral embedding of graphs, Pattern Recognition, 36(10), 2213–2230 (2003).
[8] S. Hardy, Romtelecom taps ADVA FSP 3000 for multiple networks, Lightwave, June 2011, https://www.lightwaveonline.com/articles/2011/06/romtelecom-taps-adva-fsp-3000-formultiple-networks-123097013.html, (access 20.11.2018)
[9] T. Eilam-Tzoreff, The disjoint shortest paths problem, Discrete Applied Mathematics, 8(2), 113–138 (1998).
[10] L, Guo, Y. Deng, K. Liao, Q. He, T. Sellis, Z. Hu, A Fast Algorithm for Optimally Finding Partially Disjoint Shortest Paths, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18).
[11] Ultra low latency networks. Application Note, ADVA Optical networking 2012 (available online, www.advaoptical.com).
[12] OSPF Version 2, protocol specification, RFC 2328.
[13] R. Dechter, J. Pearl, Generalized best-first search strategies and the optimality of A*, Journal of the ACM 32(3), 505–536 (1985).
