Please use this identifier to cite or link to this item:
Title: Two Heuristics for Calculating a Shared Risk Link Group Disjoint Set of Paths of Min-Sum Cost
Authors: Gomes, Teresa 
Soares, Miguel 
Craveirinha, José 
Melo, Paulo 
Jorge, Luísa 
Mirones, Vitor 
Brízido, André 
Keywords: diverse routing; SRLG-disjoint; node-disjoint; min-sum
Issue Date: 2015
Publisher: Springer
Project: QREN 23301 PANORAMA II 
PERGS (Portugal Telecom Inovação) 
Serial title, monograph or event: Journal of Network and Systems Management
Volume: 23
Issue: 4
Abstract: A Shared Risk Link Group (SRLG) is a set of links which share a common risk of failure. Routing protocols in Generalized MultiProtocol Label Switching (GMPLS), using distributed SRLG information, can calculate paths avoiding certain SRLGs. For single SRLG failure an end-to-end SRLG-disjoint path pair can be calculated, but to ensure connection in the event of multiple SRLG failures a set with more than two end-to-end SRLG-disjoint paths should be used. Two heuristic, the Conflicting SRLG-Exclusion Min Sum (CoSE-MS) and the Iterative Modified Suurballes's Heuristic (IMSH), for calculating node and SRLG-disjoint path pairs, which use the Modified Suurballes's Heuristic (MSH), are reviewed and new versions (CoSE-MScd and IMSHd) are proposed, which may improve the number of obtained optimal solutions. Moreover two new heuristics are proposed: kCoSE-MScd and kIMSHd, to calculate a set of k node and SRLG-disjoint paths, seeking to minimize its total cost. To the best of our knowledge these heuristics are a first proposal for seeking a set of k (k>2) node and SRLG-disjoint paths of minimal additive cost. The performance of the proposed heuristics is evaluated using a real network structure, where SRLGs were randomly defined. The number of solutions found, the percentage of optimal solutions and the relative error of the sub-optimal solutions are presented. Also the CPU time for solving the problem in a Path Computation Element (PCE) is reported.
Description: Two Heuristics for Calculating a Shared Risk Link Group Disjoint Set of Paths of Min-Sum Cost
ISSN: 1064-7570
DOI: 10.1007/s10922-014-9332-6
Rights: openAccess
Appears in Collections:FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais
I&D INESCC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
gomes_et_al_R2_JONS_2015_EstudoGeral.pdf1.14 MBAdobe PDFView/Open
Show full item record


checked on Feb 18, 2020

Page view(s) 50

checked on Nov 25, 2021

Download(s) 50

checked on Nov 25, 2021

Google ScholarTM




This item is licensed under a Creative Commons License Creative Commons