Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/48329
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 PEst-OE/EEI/UI308/2014 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 | URI: | https://hdl.handle.net/10316/48329 | ISSN: | 1064-7570 | DOI: | 10.1007/s10922-014-9332-6 | Rights: | openAccess |
Appears in Collections: | I&D INESCC - Artigos em Revistas Internacionais FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
gomes_et_al_R2_JONS_2015_EstudoGeral.pdf | 1.14 MB | Adobe PDF | View/Open |
SCOPUSTM
Citations
3
checked on Aug 5, 2024
WEB OF SCIENCETM
Citations
20
2
checked on Aug 2, 2024
Page view(s) 50
498
checked on Aug 6, 2024
Download(s) 50
464
checked on Aug 6, 2024
Google ScholarTM
Check
Altmetric
Altmetric
This item is licensed under a Creative Commons License