Cookies help us deliver our services. By using our services, you agree to our use of cookies.

Cuvillier Verlag

Publications, Dissertations, Habilitations & Brochures.
International Specialist Publishing House for Science and Economy

Cuvillier Verlag

De En Es
Routing and Capacity Optimization for IP Networks

Hard Copy
EUR 40.00 EUR 38.00

EUR 28.00

Routing and Capacity Optimization for IP Networks (English shop)

Andreas Bley (Author)


Table of Contents, Datei (42 KB)
Extract, Datei (150 KB)

ISBN-13 (Printausgabe) 3867272816
ISBN-13 (Hard Copy) 9783867272810
ISBN-13 (eBook) 9783736922815
Language English
Page Number 294
Edition 1
Volume 0
Publication Place Göttingen
Place of Dissertation Berlin
Publication Date 2007-07-04
General Categorization Dissertation
Departments Informatics
Keywords Shortest path routing, Internet routing,Network design, Traffic engineering,Integer programming,Combinatorial optimization, Approximation.

This thesis is concerned with dimensioning and routing optimization problems for communication networks that employ a shortest pathrouting protocol such as OSPF, IS-IS, or RIP. These protocols are widely used in the Internet. With these routing protocols, all end-to-end data streams are routed along shortest paths with respect to a metric of link lengths. The network administrator can configure the routing only by modifying this metric. In this thesis we consider the unsplittable shortest path routing variant, where each communication demand must be sent unsplit through the network. This requires that all shortest paths are uniquely determined.

The major difficulties in planning such networks are that the routing can be controlled only indirectly via the routing metric and that all
routing paths depend on the same routing metric. This leads to rather complicated and subtle interdependencies among the paths that comprise
a valid routing. In contrast to most other routing schemes, the paths for different communication demands cannot be configured independent
of each other.

Part I of the thesis is dedicated to the relation between path sets and routing metrics and to the combinatorial properties of those path
sets that comprise a valid unsplittable shortest path routing. Besides reviewing known approaches to find a compatible metric for a
given path set (or to prove that none exists) and discussing some properties of valid path sets, we show that the problem of finding a
compatible metric with integer lengths as small as possible and the problem of finding a smallest possible conflict in the given path set
are both NP-hard to approximate within a constant factor.

In Part II of the thesis we discuss the relation between unsplittable shortest path routing and several other routing schemes and we analyze
the computational complexity of three basic unsplittable shortest path routing problems. We show that the lowest congestion that can be
obtained with unsplittable shortest path routing may significantly exceed that achievable with other routing paradigms and we prove several non-approximability results for unsplittable shortest path routing problems that are stronger than those for the corresponding unsplittable flow problems. In addition, we derive various polynomial time approximation algorithms for general and special cases of these problems.

In Part III of the thesis we finally develop an integer linear programming approach to solve these and more realistic unsplittable shortest path routing problems to optimality. We present alternative formulations for these problems, discuss their strength and computational complexity, and show how to derive strong valid inequalities. Eventually, we describe our implementation of this solution approach and report on the numerical results obtained for
real-world problems that came up in the planning the German National Research and Education Networks G-WiN and X-WiN and for several benchmark instances.