Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Spare capacity allocation using shared backup path protection for dual link failures

Liu, VY and Tipper, D (2013) Spare capacity allocation using shared backup path protection for dual link failures. Computer Communications, 36 (6). 666 - 677. ISSN 0140-3664

[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)


This paper extends the spare capacity allocation (SCA) problem from single failures to dual link failures on mesh-like IP or WDM networks. The SCA problem pre-plans traffic flows with mutually disjoint one working and two backup paths using the shared backup path protection (SBPP) scheme. The spare provision matrix (SPM) method aggregates per-flow based information and computes the shared spare capacity for dual link failures. When compared to previous two-flow based methods, it has better scalability and flexibility. The SCA problem is formulated as a non-linear integer programming model and partitioned into two sequential linear sub-models: one finds all primary backup paths, and the other finds all secondary backup paths. We extend the terminologies in the 1+1 and 1:1 link protection for the backup path protection: using ":" to indicate backup paths with shared spare capacity; and using "+" to indicate backup paths with dedicated capacity. Numerical results from five networks show that the network redundancy of the 1+1+1 dedicated path protection is in the range of 313-400%. It drops to 96-180% in the 1:1:1 shared backup path protection without loss of dual-link resiliency, but with the trade-off of the highest complexity on spare capacity shared by all backup paths. The 1+1:1 hybrid path protection provides intermediate redundancy at 187-310% with the moderate complexity. It has dedicated primary backup paths and shared secondary backup paths. We also compare passive sharing with active sharing. They perform spare capacity sharing either after or during the backup path routing, i.e., the active sharing approach performs share spare capacity within the backup path routing, while the passive sharing does so only after all backup paths are found. The active sharing approaches always achieve lower redundancy values than the passive sharing. The reduction percentages are about 12% for 1+1:1 and 25% for 1:1:1 respectively. The extension of the Successive Survivable Routing (SSR) heuristic algorithm to the dual failure case is given and the numerical results show that SSR maintains a 4-11% gap from optimal on small or medium networks, and scales up well on large networks. © 2013 Elsevier B.V. All rights reserved.


Social Networking:
Share |


Item Type: Article
Status: Published
CreatorsEmailPitt UsernameORCID
Liu, VY
Tipper, Ddtipper@pitt.eduDTIPPER0000-0002-9429-6425
Date: 15 March 2013
Date Type: Publication
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Journal or Publication Title: Computer Communications
Volume: 36
Number: 6
Page Range: 666 - 677
DOI or Unique Handle: 10.1016/j.comcom.2012.09.007
Institution: University of Pittsburgh
Schools and Programs: School of Information Sciences > Telecommunications
Refereed: Yes
ISSN: 0140-3664
Date Deposited: 01 Jul 2013 22:27
Last Modified: 03 Jun 2019 14:55


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item