A Lagrangian Approach for Integrated Network Design and Routing in IP Networks

Please always quote using this URN: urn:nbn:de:0297-zib-7515

We consider the problem of designing a network that employs a non-bifurcated shortest path routing protocol. The network's nodes and the set of potential links are given together with a set of forecasted end-to-end traffic demands. All relevant hardware components installable at links or nodes are considered. The goal is to simultaneously choose the network's topology, to decide which hardware components to install on which links and nodes, and to find appropriate routing weights such that the overall network cost is minimized. In this paper, we present a mathematical optimization model for this problem and an algorithmic solution approach based on a Lagrangian relaxation. Computational results achieved with this approach for several real-world network planning problems are reported.

Metadaten
Author:	Andreas Bley
Document Type:	ZIB-Report
Tag:	IP Routing; Lagrangian relaxation; Network Planning; Routing
MSC-Classification:	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05]
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
	90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
Date of first Publication:	2003/09/10
Series (Serial Number):	ZIB-Report (03-29)
ZIB-Reportnumber:	03-29
Published in:	Appeared in: Proceedings of International Network Optimization Conference 2003, Oct. 27-29, Evry/Paris, France, pp. 107-113

Open Access