Routing and Capacity Optimization for IP Networks

Vorschau

Inhaltsverzeichnis, Datei (42 KB)
Leseprobe, Datei (150 KB)

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.