Spare capacity allocation using partially disjoint paths for dual link failure protection

Author

Liu, V.Y. ; Tipper, David

Author_Institution

Network Adv. Res., Huawei Technol., Santa Clara, CA, USA

fYear

2013

fDate

4-7 March 2013

Firstpage

171

Lastpage

178

Abstract

A shared backup path protection (SBPP) scheme can be used to protect dual link failures by pre-planning each traffic flow with mutually disjoint working and two backup paths while minimizing the network overbuild. However, many existing backbone networks are bi-connected without three fully disjoint paths between all node pairs. Hence in practice partially disjoint paths (PDP) have been used for backup paths instead of fully disjoint ones. This paper studies the minimum spare capacity allocation (SCA) problem using PDP within an optimization framework. This is an extension of the spare provision matrix (SPM) method for PDP. The integer linear programming (ILP) model is formulated and an approximation algorithm, Successive Survivable Routing (SSR), is extended and used in the numerical study.

Keywords

approximation theory; computer network security; integer programming; sparse matrices; telecommunication network routing; ILP model; PDP; SBPP scheme; SCA; SPM method; SSR; approximation algorithm; backbone networks; dual link failure protection; integer linear programming; optimization framework; partially disjoint paths; shared backup path protection; spare capacity allocation; spare provision matrix; successive survivable routing; traffic flow; Bandwidth; Equations; Indexes; Optimization; Resource management; Routing; Vectors; dual failure protection; partially disjoint path; resilient traffic engineering; shared backup path protection (SBPP); spare capacity allocation (SCA); survivable network design;

fLanguage

English

Publisher

ieee

Conference_Titel

Design of Reliable Communication Networks (DRCN), 2013 9th International Conference on the

Conference_Location

Budapest

Print_ISBN

978-1-4799-0049-7

Type

conf

Filename

6529857