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
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.
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.