Die Struktur von Telekommunikationsnetzen ändert sich momentan dramatisch. Immer mehr Anwendungen (e-mail, Video, Telefon und Mobilfunk,...) werden über ein IP/MLPS-Netz geführt, das wiederum auf einem optisches Transportnetz aufsetzt. Netzbetreiber stehen vor der Herausforderung, ihre Netze so zu planen, dass alle Benutzeranforderungen zu vernünftigen Kosten in hoher Qualität erfüllt werden können.

Die Planung eines Zwei-Layer-Netzes umfasst u.a. die Planung einer Topologie für beide Layer, die Dimensionierung von Hardware (Router, Multiplexer,...) und Linkkapazitäten, sowie die Bestimmung eines Routings für gegebene Kommunikationsbedarfe. Auch Ausfallsicherheitsbedingungen müssen in der Planung berücksichtigt werden, um im Falle eines durchtrennten Kabels oder eines Hardware-Ausfalls den betroffenen Verkehr umrouten zu können. Mangels besserer Planungsmethoden wurden die beiden Schichten bislang meistens einzeln geplant, obwohl es starke Abhängigkeiten zwischen ihnen gibt. Die existierenden mathematischen Modelle für eine integrierte Planung beider Schichten sind mit konventionellen Ansätzen sehr schwer zu lösen. In einer ersten Phase (damals mit Siemens) was das Ziel des Projektes die Erweiterung existierender Modelle und Algorithmen um Multi-layer-Aspekte, um die Lösungszeiten zu verringern. Dies wurde unter anderem durch verbessertes Preprocessing und durch Anpassung bewährter Schnittebenen aus der Single-layer-Planung an den Multi-layer-Kontext erreicht. In einer zweiten Phase (nun mit Nokia Siemens Networks) ging es um die Erweiterung dieser Lösungsmethoden auf große ausfallsichere Zwei-Layer-Netze, bei denen die Berechnung guter Netzkonfigurationen und dualer Schranken nach wie vor eine große Herausforderung darstellt. Wegen der auftretenden großen linearen Programme und der enormen Rechenzeiten ist das Problem mit einem Standard-Branch-and-Cut-Löser nicht einmal annähernd lösbar. Wir haben eine Reihe von problemspezifischen Erweiterungen für einen Branch-and-Cut-and-Price-Algorithmus entwickelt. Mit ihrer Hilfe können wir gute Netzkonfigurationen mit Qualitätsgarantien selbst für große Netze berechnen.

• Nokia Siemens Networks GmbH & Co. KG
• Arie Koster, University of Warwick, UK