Exploiting the diversity of shortest pairs of edge-disjoint paths

• Marina Girolimetto UFES
• Rodrigo S. Tessinari UFES
• Fabio O. Lima IFES
• Claunir Pavan UFFS
• Marcia H. M. Paiva UFES

DOI: https://doi.org/10.5753/sbrc.2018.2473

Resumo

In an optical network, given a pair of source and destination nodes, some algorithm can be used to find shortest pairs of edge-disjoint paths to be used as working and backup paths. The Suurballe and Tarjan's algorithm is a solution, but it can found different shortest pairs of pathways interconnecting the same pair of source and destination nodes. In this paper, two versions of the Suurballe and Tarjan's algorithm is proposed to deal with that diversity. For each node pair of a given network topology, these versions find the most balanced shortest pair of working and backup paths and the least balanced one. Both algorithms are tested and analyzed in a set of 40 2-edge-connected topologies of real-world optical telecommunication networks. A difference of up to 29% was found between the two strategies.

Referências

Berger, L., Bryskin, I., Farrel, A., and Papadimitriou, D. (2007). GMPLS segment recovery.

Grover, W. D. (2003). Mesh-based survivable transport networks: options and strategies for optical, MPLS, SONET and ATM networking. Prentice Hall PTR.

Korotky, S. K. (2004). Network global expectation model: A statistical formalism for quickly quantifying network needs and costs. Journal of Lightwave Technology, 22(3):703.

Labourdette, J.-F., Bouillet, E., Ramamurthy, R., and Akyamaç, A. A. (2005). Fast approximate dimensioning and performance analysis of mesh optical networks. IEEE/ACM Transactions on Networking (TON), 13(4):906–917.

Lang, J., Rekhter, Y., and Papadimitriou, D. (2007). RSVP-TE extensions in support of end-to-end generalized multi-protocol label switching (GMPLS) recovery. Technical report.

Manchester, J., Bonenfant, P., and Newton, C. (1999). The evolution of transport network survivability. IEEE Communications Magazine, 37(8):44–51.

Nykänen, M. and Ukkonen, E. (2002). The exact path length problem. Journal of Algorithms, 42(1):41–53.

Oliveira, J. M. S. d. S. (2010). Protecção maxima de redes de telecomunicações. Mestrado, Universidade de Aveiro.

Pavan, C., de Lima, L., Paiva, M., and Segatto, M. (2015). How reliable are the real-world Journal of Optical Communications and Networking, optical transport networks? 7(6):578–585.

Pinto, A. N. (2014). Reference networks. www.av.it.pt/anp/on/refnet2.html.

Ramaswami, R., Sivarajan, K., and Sasaki, G. (2009). Optical networks: a practical perspective. Morgan Kaufmann.

Routray, S. K., Morais, R. M., da Rocha, J. R. F., and Pinto, A. N. (2013). Statistical model for link lengths in optical transport networks. Journal of Optical Communications and Networking, 5(7):762–773.

Schrijver, A. (2003). Combinatorial optimization: polyhedra and efciency, volume 24. Springer Science & Business Media.

Shen, G., Guo, H., and Bose, S. K. (2016). Survivable elastic optical networks: survey and perspective. Photonic Network Communications, 31(1):71–87.

Suurballe, J. and Tarjan, R. E. (1984). A quick method for nding shortest pairs of disjoint paths. Networks, 14(2):325–336.

Tessinari, R. S., Puype, B., Colle, D., and Garcia, A. S. (2016). ElasticO++: An elastic optical network simulation framework for OMNeT++. Optical Switching and Networking, 22:95–104.

Whitney, H. (1932). Congruent graphs and the connectivity of graphs. American Journal of Mathematics, 54(1):150–168.

Williams, R. (2009). Finding paths of length k in O*(2k) time. Information Processing Letters, 109(6):315–318.

Yen, J. Y. (1970). An algorithm for nding shortest routes from all source nodes to a given destination in general networks. Quarterly of Applied Mathematics, 27(4):526–530.

Zang, H. (2012). WDM mesh networks: management and survivability. Springer Science & Business Media.