Journal of Applied Mathematics and Decision Sciences
Volume 2006 (2006), Article ID 72547, 18 pages

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

Copyright © 2006 Krzysztof Walkowiak. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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.