Library

Description: In der vorliegenden Dissertation untersuchen wir die Optimierung von ausfallsicheren Telekommunikationsnetzwerken. Wir präsentieren unterschiedliche gemischt-ganzzahlige Modelle für die diskrete Kapazitätsttruktu,, sowie für die Sicherung des Netzes gegen den Ausfall einzelner Komponenten. Die Modelle wurden in einer Kooperation mit der E-Plus Mobilfunk GmbH verwendet. Die theoretischen Resultate wurden in Algorithmen umgesetzt und in das von uns entiickllte Netzwerksoptimierungswerkzeug Discnet (Dimensioning Survivable Capaiitated NETworks) integriert, welches seit mehreren Jahren in der Planung bei E-Plus eingesetzt wird. Wir betrachten das Transportnetzllanungsproblem eines Telekommunikationsanbieters. Dieses Problem setzt auf logischen Kommunikattonsanforerrungen zwischen den Standorten (Knoten) des zu planenden Netzes und potentiell inslallirrbaren Verbindungen (Kanten) zwischen derselben Knotenmenge auf. Ein Kapazitätsmodell stellt die Information bereit, welche Kapazitäten auf den potentiellen Kanten verfügbar sind. Wir betrachten zwei Modelle. Entweder ist eine explizite Liste der verfügbaren Kapazittten gegeben oder eine Menge von sogenannten Basiskapazitäten, die auf jeder Kante indiviuelll kombiniert werden können. Die Basiskapazitäten müßen paarweise ganzzahlige Vielfache voneinander sein. Man beachte, daß diese Eigenschaft von den internationalen Standards PDH und SDH erfüllt wiid. Ein Ausfallsicherheitsmodell stellt die Information bereit, wie das zu planende Netz gegen den Ausfall einzelner Netzkomponenten geschützt werden soll. Wir betrachten sinnvolle Kombinationen der Modelle Diversification, Reservation und Path Restoration. Das erste Modell garantiert Ausfallsicherheit durch kommunikationsbedarfsabhängige Beschränkung des Prozentsatzes, der durch einzelne Netzkomponenten geroutet werden darf. Bei den beiden anderen Modelle können Kommunikationsbedarfe bei Ausfall einer Netzkomponente auf unterschiedliche Weise neu geroutet werden. Ziel der Planung ist eine ktstenminimlle Kapatitätsentscheidung, die eine Routenllanung aller Kommunikationsbedarfe gemäß den Ausfallsicherheitsanforderungen ermöglicht. Wir entwickeln ein Schnittebenenverfahren zur Lösung der betrachteten Optimiergngsrrobleme. Zu diesem Zweck untersuchen wir Polyeder, die mit den verschiedenen Problemen assoziiert sind. Wir präsentieren neue Klassen von Ungleichungen, entwickeln Separationsalgorithmen und Heuristiken. Mit dem Schnittebenenverfahren werden untere und obere Schranken für den Wert von Oitimallösungen berechnet, und daher ist es möglich, Qualitätsgarantien für die berechneten Löungen anzugeben. Parallel zur Beschreibung der implementierten Algorithmen präsentieren wir umfangreiche Tests mit praktisch relevanten Daten, die zu Problemen mit mehr als 2 Billionen Variablen führen.