Integer programming approaches to access and backbone IP-network planning

Please always quote using this URN: urn:nbn:de:0297-zib-7081
  • In this article we study the problem of designing a nation-wide communication network. Such networks usually consist of an access layer, a backbone layer, and maybe several intermediate layers. The nodes of each layer must be connected to those of the next layer in a tree-like fashion. The backbone layer has to satisfy certain survivability and routing constraints. Given the node locations, the demands between them, the possible connections and hardware configurations, and various other technical and administrational constraints, the goal is to decide, which node is assigned to which network level, how the nodes are connected, what hardware must be installed, and how traffic is routed in the backbone. Mixed integer linear programming models and solution methods are presented for both the access and the backbone network design problem. The focus is on the design of IP-over-SDH networks, but the access network design model and large parts of the backbone network design models are general and also applicable for other types of communication networks. Results obtained with these methods in the planning of the German research network are presented.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Bley, Thorsten Koch
Document Type:ZIB-Report
Tag:Internet routing ; Mixed-integer programming; Network design ; Traffic enineering
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:2002/11/18
Series (Serial Number):ZIB-Report (02-41)
Published in:A slightly modified vers. appeared in: Modeling, Simulation and Optimization of Complex Processes: Proceedings of the 3rd International Conference on High Performance Scientific Computing, Hanoi, Vietnam, Springer 2006, pp. 87-110

$Rev: 13581 $