Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Design of Survivable Optical Networks by Mathematical Optimization

Please always quote using this URN: urn:nbn:de:0297-zib-10408
  • Abstract The cost-efficient design of survivable optical telecommunication networks is the topic of this thesis. In cooperation with network operators, we have developed suitable concepts and mathematical optimization methods to solve this comprehensive planning task in practice. Optical technology is more and more employed in modern telecommunication networks. Digital information is thereby transmitted as short light pulses through glass fibers. Moreover, the optical medium allows for simultaneous transmissions on a single fiber by use of different wavelengths. Recent optical switches enable a direct forwarding of optical channels in the network nodes without the previously required signal retransformation to electronics. Their integration creates ongoing optical connections,which are called lightpaths. We study the problem of finding cost-efficient configurations of optical networks which meet specified communication requirements. A configuration comprises the determination of all lightpaths to establish as well as the detailed allocation of all required devices and systems. We use a flexible modeling framework for a realistic representation of the networks and their composition. For different network architectures, we formulate integer linear programs which model the design task in detail. Moreover, network survivability is an important issue due to the immense bandwidths offered by optical technology. Operators therefore request for designs which perpetuate protected connections and guarantee for a defined minimum throughput in case of malfunctions. In order to achieve an effective realization of scalable protection, we present a novel survivability concept tailored to optical networks and integrate several variants into the models. Our solution approach is based on a suitable model decomposition into two subtasks which separates two individually hard subproblems and enables this way to compute cost-efficient designs with approved quality guarantee. The first subtask consists of routing the connections with corresponding dimensioning of capacities and constitutes a common core task in the area of network planning. Sophisticated methods for such problems have already been developed and are deployed by appropriate integration. The second subtask is characteristic for optical networks and seeks for a conflict-free assignment of available wavelengths to the lightpaths using a minimum number of involved wavelength converters. For this coloring-like task, we derive particular models and study methods to estimate the number of unavoidable conversions. As constructive approach, we develop heuristics and an exact branch-and-price algorithm. Finally, we carry out an extensive computational study on realistic data, provided by our industrial partners. As twofold purpose, we demonstrate the potential of our approach for computing good solutions with quality guarantee, and we exemplify its flexibility for application to network design and analysis.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Adrian Zymolka
Document Type:Doctoral Thesis
Tag:integer programming; mathematical optimization; network design; optical networks
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
Granting Institution:Technische Universität Berlin
Advisor:U. Pinkall, Martin Grötschel, Sven Krumke
Date of first Publication:2007/06/14
Published in:Ersch. als Buchveröffentlichung: Design of Survivable Optical Networks by Mathematical Optimization, (2007), Cuvillier, ISBN 978-3-86727-253-7.
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.