Title:

An Algorithm for Enumerating SRLG Diverse Path Pairs, Journal of Telecommunications and Information Technology, 2010, nr 3

Creator:

Craveirinha, Jose ; Gomes, Teresa

Subject and Keywords:

routing ; telecommunication networks ; SRLG disjoint shortest paths

Description:

Telecommunication networks are intrinsically multi-layered, a single failure at a lower level usually corresponds to a multi-failure scenario at an upper layer. In this context, the concept of shared risk link group (SRLG) allows an upper layer to select, for a given active path (AP), a backup path (BP), which avoids every SRLG that may involve the selected AP, in the event of a failure. That is a SRLG diverse path set maybe defined as a set of paths, between an origin and a destination, such that no pair of paths can be simultaneously affected by any given failure (or risk) in a single failure scenario. Firstly we present the formulation of the SRLG diverse path pair calculation problem in a directed network. An algorithm for enumerating SRLG diverse paths, by non decreasing cost of their total (additive) cost will be presented, which is based on an algorithm proposed for generating minimal cost node disjoint path pairs. The SRLG diverse path pairs may be node or arc disjoint, with or without length constraints. Computational results will be presented to show the efficiency of the proposed algorithm for obtaining node or arc disjoint SRLG diverse path pairs in undirected networks.

Publisher:

Instytut Łączności - Państwowy Instytut Badawczy, Warszawa

Date:

2010, nr 3

Resource Type:

artykuł

Format:

application/pdf

Resource Identifier:

ISSN 1509-4553, on-line: ISSN 1899-8852

Source:

Journal of Telecommunications and Information Technology

Language:

ang

Rights Management:

Biblioteka Naukowa Instytutu Łączności