A Logical Topology and Discrete Capacity Assignment Algorithm for Reconfigurable Networks

Ming-Jeng Lee and James R. Yee
Additional contact information
Ming-Jeng Lee: IBM, Research Triangle Park, North Carolina
James R. Yee: University of Hawaii, Honolulu, Hawaii

Operations Research, 1995, vol. 43, issue 1, 102-116

Abstract: A reconfigurable network is a circuit-switched network where the effective topology and capacities can be dynamically adapted to changes in the traffic requirements or to changes in the structure of the network due to failures. The application of reconfigurable networks considered in this paper is data communications. We formulated the joint topology, capacity and routing problem in a reconfigurable network as a nonlinear, mixed integer programming problem. To solve this problem, we present a partial branch-and-bound algorithm. The reduced gradient method is used to solve the problem with the integrality constraints relaxed. Lagrangian relaxation is applied to obtain lower bounds. In the computational experiments, the algorithm found good solutions in a few minutes of CPU time. In addition, the reduction in the minimal delay due to the reconfiguration capability can be as large as 62%.

Keywords: communications; topology; capacity assignment routing; networks/graphs: multicommodity flow algorithms (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.1.102 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:1:p:102-116

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().