Open AccessExploiting the diversity of shortest pairs of edge-disjoint paths
Author(s) -
Marina Girolimetto,
Rodrigo Stange Tessinari,
Fábio O. Lima,
Claunir Pavan,
Marcia Helena Moreira Paiva
Publication year - 2018
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/sbrc.2018.2473
Subject(s) - backup , k shortest path routing , floyd–warshall algorithm , disjoint sets , computer science , network topology , shortest path problem , shortest path faster algorithm , yen's algorithm , node (physics) , topology (electrical circuits) , enhanced data rates for gsm evolution , algorithm , mathematics , combinatorics , discrete mathematics , theoretical computer science , computer network , dijkstra's algorithm , telecommunications , graph , structural engineering , database , engineering
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.