Autor(es):
Gomes, Teresa 
; Soares, Miguel ; Craveirinha, José ; Melo, Paulo ; Jorge, Luísa ; Mirones, Vítor ; Brizído, André
Data: 2012
Identificador Persistente: http://hdl.handle.net/10198/10643
Origem: Biblioteca Digital do IPB
Assunto(s): Protection; SRLG-disjoint; Min-sum
Descrição
Ensuring the resilience of telecommunications networks is an ongoing concern of telecommunications operators. In a Generalized Multiprotocol Label Switching (GMPLS) [4], network information about sets of links that share risks of failure, called Shared Risk Link Groups (SRLG), can be distributed [3]. This information allows Path Computation Elements (PCE) [1] to determine protected routes, i.e. compute a pair (or set) of SRLG-disjoint paths. A PCE must respond quickly to requests without requiring too many resources. This shows the importance of developing efficient algorithms for determining the SRLG disjoint paths.
Firstly, a new version of Conflicting SRLG-Exclusion Min Sum (CoSE-MS) heuristic [2,5] which seeks to determine a pair of SRLG-disjoint paths with minimum additive cost, adequate for dedicated global protection in GMPLS networks, will be described. The new version, designated CoSE-MScd, uses an improved version (designated MSHd) of the Modified Suurballe's Heuristic (MSH) proposed in [6] and modifies the process of selection of the
conflicting SRLGs used in [2]. The Iterative Modified Suurballes's Heuristic (IMSH) [6] and the new variant IMSHd, which results from the replacement of MSH by MSHd in IMSH, will also be presented. Secondly, the heuristics kCoSE-MScd and kIMSHd are proposed. To the best of our knowledge these procedures are a first proposal for seeking a set of k (k > 2) node and SRLG disjoint paths of minimal additive cost; these heuristics use a generalization of MSH for obtaining a set of k node and SRLG disjoint paths, which we designate as kMSH.
The two heuristics have a similar structure, but the first uses CoSE-MScd to collect a set of node and SRLG disjoint path pairs and the second uses IMSHd for that same purpose.
The network used for evaluating the heuristics' performance was the largest biconnected component of an image of a real network with 231 nodes and 471 edges. Ten different random seeds where used to generate different distributions of SRLGs for that component, resulting in 10 different networks (with the same topology). The accuracy of the solutions obtained by the heuristics was evaluated solving an ILP formulation of the problem, using CPLEX 12.3 on a Desktop.
Experimental results in an embedded system (core clock 330MHz, 128 MB RAM), showed that CoSE-MScd is more efficient than CoSE-MS, without compromising its accuracy. IMSHd is more accurate than IMSH (for the same number of iterations) at the cost of more CPU time. The experimental results obtained using kIMSH and kCoSE-MScd show that although both heuristics are quite effective in calculating a set of k = 3; 4 node and SRLG disjoint paths, however only 55%-59% of the sets of size k = 3 have optimal cost, and this value decreases for k = 4. The relative error of the total cost of the sub-optimal paths sets is about 7.5% for k = 3 and close to 15% for k = 4. Nevertheless given the great difficulty in obtaining optimal sets of node and SRLG disjoint paths, these proposals and results seem relevant in this area.
