Dimensioning Survivable Capacitated Networks
Roland Wessäly · 2000
In der vorliegenden Dissertation untersuchen wir die Optimierung von ausfallsicheren Telekommunikationsnetzwerken. Wir prasentieren unterschiedliche gemischt-ganzzahlige Modelle fur die diskrete Kapazitatsttruktu,, sowie fur 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 Kapazitatsmodell stellt die Information bereit, welche Kapazitaten auf den potentiellen Kanten verfugbar sind. Wir betrachten zwei Modelle. Entweder ist eine explizite Liste der verfugbaren Kapazittten gegeben oder eine Menge von sogenannten Basiskapazitaten, die auf jeder Kante indiviuelll kombiniert werden konnen. Die Basiskapazitaten musen paarweise ganzzahlige Vielfache voneinander sein. Man beachte, das diese Eigenschaft von den internationalen Standards PDH und SDH erfullt wiid. Ein Ausfallsicherheitsmodell stellt die Information bereit, wie das zu planende Netz gegen den Ausfall einzelner Netzkomponenten geschutzt werden soll. Wir betrachten sinnvolle Kombinationen der Modelle Diversification, Reservation und Path Restoration. Das erste Modell garantiert Ausfallsicherheit durch kommunikationsbedarfsabhangige Beschrankung des Prozentsatzes, der durch einzelne Netzkomponenten geroutet werden darf. Bei den beiden anderen Modelle konnen Kommunikationsbedarfe bei Ausfall einer Netzkomponente auf unterschiedliche Weise neu geroutet werden. Ziel der Planung ist eine ktstenminimlle Kapatitatsentscheidung, die eine Routenllanung aller Kommunikationsbedarfe gemas den Ausfallsicherheitsanforderungen ermoglicht. Wir entwickeln ein Schnittebenenverfahren zur Losung der betrachteten Optimiergngsrrobleme. Zu diesem Zweck untersuchen wir Polyeder, die mit den verschiedenen Problemen assoziiert sind. Wir prasentieren neue Klassen von Ungleichungen, entwickeln Separationsalgorithmen und Heuristiken. Mit dem Schnittebenenverfahren werden untere und obere Schranken fur den Wert von Oitimallosungen berechnet, und daher ist es moglich, Qualitatsgarantien fur die berechneten Loungen anzugeben. Parallel zur Beschreibung der implementierten Algorithmen prasentieren wir umfangreiche Tests mit praktisch relevanten Daten, die zu Problemen mit mehr als 2 Billionen Variablen fuhren.