Routing and Capacity Optimization for IP networks

Please always quote using this URN: urn:nbn:de:0297-zib-10323
  • This article describes the main concepts and techniques that have been developed during the last year at ZIB to solve dimensioning and routing optimization problems for IP networks. We discuss the problem of deciding if a given path set corresponds to an unsplittable shortest path routing, the fundamental properties of such path sets, and the computational complexity of some basic network planning problems for this routing type. Then we describe an integer-linear programming approach to solve such problems in practice. This approach has been used successfully in the planning of the German national education and research network for several years.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Bley
Document Type:ZIB-Report
Tag:Approximationsalgorithmen; gemischt-ganzzahlige Programmierung; kombinatorische Optimierung; kürzeste-Wege Routing
approximation algorithms; combinatorial optimization; mixed-integer programming; shortest path routing
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-02 Research exposition (monographs, survey articles)
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] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
Date of first Publication:2007/11/09
Series (Serial Number):ZIB-Report (07-33)
ISSN:1438-0064
ZIB-Reportnumber:07-33
Published in:Appeared in: Operations Research Proceedings 2007. J. Kalcsics, S. Nickel (eds.) Springer 2008, pp. 9-16