Journal of Applied Mathematics and Decision Sciences 
Volume 2006 (2006), Article ID 72547, 18 pages
doi:10.1155/JAMDS/2006/72547

Maximizing residual capacity in connection-oriented networks

Krzysztof Walkowiak

 Chair of Systems and Computer Networks, Faculty of Electronics, Wroclaw University of Technology, Wybrzeze Wyspianskiego 27, Wroclaw 50-370, Poland
Received 5 October 2005; Revised 5 May 2006; Accepted 22 May 2006

Abstract

The following problem arises in the study of survivable connection-oriented networks. Given a demand matrix to be routed between nodes, we want to route all demands, so that the residual capacity given by the difference between link capacity and link flow is maximized. Each demand can use only one path. Therefore, the flow is modeled as nonbifurcated multicommodity flow. We call the considered problem nonbifurcated congestion (NBC) problem. Solving NBC problem enables robust restoration of failed connections in a case of network failure. We propose a new heuristic algorithm for NBC problem and compare its performance with existing algorithms.