Article ID: | iaor19991536 |
Country: | United Kingdom |
Volume: | 25 |
Issue: | 7/8 |
Start Page Number: | 595 |
End Page Number: | 609 |
Publication Date: | Jul 1998 |
Journal: | Computers and Operations Research |
Authors: | Lee Chae Y., Koh Seok J. |
Keywords: | heuristics, networks |
We propose a design of self-healing ATM virtual path (VP) networks based on backup VP. The backup VP is a preassigned virtual path to restore the traffic after a network failure. It is known that the self-healing scheme based on the backup VP is simple, fast and easy to implement. Given a set of bandwidth requirements and original routes for target demands, the design is to find the backup route of each traffic demand such that the cost of total spare bandwidth, which is required for each physical link to restore the services, is minimized. The problem is formulated as an integer linear program. Based on the property that a common backup VP of any two distinct traffic demands saves the required bandwidth, an initial and two improvement heuristics are proposed. Computational experiments show that the proposed procedure provides solutions the gap of which is less than 11% compared to optimal solutions.