A new model and a computational study for Demand-wise Shared Protection
Please always quote using this URN: urn:nbn:de:0297-zib-8880
- This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15\% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15\% percent worse than shared path protection.
Author: | Claus G. Gruber, Arie M.C.A. Koster, Sebastian Orlowski, Roland Wessäly, Adrian Zymolka |
---|---|
Document Type: | ZIB-Report |
Tag: | demand-wise shared protection; integer linear programming; network design; resilience |
MSC-Classification: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Mxx Computer system organization / 68M10 Network design and communication [See also 68R10, 90B18] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05] | |
Date of first Publication: | 2005/12/14 |
Series (Serial Number): | ZIB-Report (05-55) |
ZIB-Reportnumber: | 05-55 |
Published in: | Partly appeared in: Proc. of INOC 2005, Int. Network Opt. Conf. March 20-23, 2005, Lissabopn, Portugal, pp. 100-105. Partly appeared in: Proc. of DRCN 2005, the 5th Int. Workshop on the Design of Reliable Communiction Networks, Oct. 16-19, 2005, Naples, Italy, pp. 421-428 |