Routing- und Kapazitätsoptimierung für IP Netze

Die Arbeit befasst sich mit der Kapazitäts- und Routenplanung für Kommunikationsnetze, die ein kürzeste-Wege Routingprotokoll verwenden. Diese Art von Protokollen ist im Internet weit verbreitet. Bei diesen Routingverfahren wird für jede Verbindung im Netz ein Längenwert festgelegt, diese Längen formen die sogenannte Routingmetrik. Die Routingwege der Kommunikationsbedarfe sind dann die jeweiligen kürzesten Wege bezüglich dieser Metrik. Bei der in der Arbeit untersuchten Variante dieser Routingprotokolle wird zusätzlich verlangt, dass es je Kommunikationsbedarf genau einen eindeutigen kürzesten Weg gibt. Die Schwierigkeit bei der Planung solcher Netze besteht darin, dass sich die Routingwege einerseits nur indirekt über die Routingmetrik beeinflussen lassen, andererseits aber alle Routingwege von der gleichen Metrik abhängen. Dadurch können die Wege verschiedener Kommunikationsanforderungen nicht wie bei anderen Routingverfahren unabhängig voneinander gewählt werden. Im erstem Teil der Arbeit werden der Zusammenhang zwischen gegebenen Wegesystemen und kompatiblen Routingmetriken sowie die Beziehungen der Wege eines zulässigen eindeutige-kürzeste-Wege-Routings untereinander untersucht. Dabei wird unter Anderem gezeigt, dass es NP-schwer ist, eine kompatible Metrik mit kleinstmöglichen Routinglängen zu einem gegebenen Wegesystem zu finden. Es wird auch bewiesen, dass das Finden eines kleinstmöglichen Konfliktes in einem gegebenen Wegesystem, zu dem keine kompatible Metrik existiert, NP-schwer ist. Im zweiten Teil der Arbeit wird die Approximierbarkeit von drei grundlegenden Netz- und Routenplanungsproblemen mit eindeutige-kürzeste-Wege-Routing untersucht. Für diese Probleme werden stärkere Nichtapproximierbarkeitsresultate als für die entsprechenden Einwege-Routing Probleme bewiesen und es werden verschiedene polynomiale Approximationsverfahren für allgemeine und Spezialfälle entworfen. Ausserdem wird die Beziehung zwischen eindeutige-kürzeste-Wege-Routing und anderen Routingverfahren diskutiert. Im dritten und letzten Teil der Arbeit wird ein (gemischt-) ganzzahliger Lösungsansatz für Planungsprobleme mit eindeutige-kürzeste-Wege-Routing vorgestellt. Für die im zweiten Teil diskutierten grundlegenden Netz- und Routenplanungsprobleme werden verschiedene (gemischt-) ganzzahlige lineare Modelle vorgestellt und es wird deren Lösbarkeit und die Stärke ihrer LP Relaxierungen untersucht. Es wird auch gezeigt, wie sich starke gültig Ungleichungen aus den in diesen Modellen enthalten Substrukturen ableiten lassen. Schlielich werden am Ende der Arbeit die Software-Implementierung dieses Lösungsverfahrens für eine praxisrelevante Verallgemeinerung der Planungsprobleme sowie die damit erzielten numerischen Ergebnisse vorgestellt und diskutiert.This thesis is concerned with dimensioning and routing optimization problems for communication networks that employ a shortest path routing 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