Processing connection requests in a given all-optical network dynamically works as follows.

Upon release of a customer call, it must be decided immediately and without knowledge of future calls whether the call is accepted or not.
In the case of acceptance, the requested connection must be established by installing corresponding lightpaths in the optical network. In return, some profit is gained.

The goal is to accept suitable requests and route such lightpaths that the total gained profit is as large as possible. For the presented problem various online algorithms have been developed and evaluated in the project.

DynRoute

Routing in Optical Transport Networks: Optimization of Optical Transport Networks with Dynamical Routing

Processing connection requests in a given all-optical network dynamically works as follows.

  • Upon release of a customer call, it must be decided immediately and without knowledge of future calls whether the call is accepted or not.
  • In the case of acceptance, the requested connection must be established by installing corresponding lightpaths in the optical network. In return, some profit is gained.
The goal is to accept suitable requests and route such lightpaths that the total gained profit is as large as possible. For the presented problem various online algorithms have been developed and evaluated in the project.
teaser

Optical Networks

In today's 1st generation optical networks, high transmission rates are realized by virtue of Wavelength Division Multiplexing (WDM). WDM partitions the available wavelength spectrum of a fiber into distinct wavelengths, which can be used in parallel by different optical signals. When several fibers meet in a network node, the incoming signals are converted into electronic form to switch them, before they are sent on optically. This so-called o-e-o conversion limits transmission speed significantly.

In future 2nd generation optical networks, optical switches will supersede the electronic ones. A fully configurable optical switch can guide lightwaves from any ingoing to any outgoing fiber without applying o-e-o conversion. This results in faster connections, and it enables the network operator to offer services like video-on-demand, remote medical imaging and distributed supercomputing. Optical switches are announced to be commercially available soon. In addition, wavelength converters are currently being developed that can change the wavelength of an optical signal.

From a mathematical point of view, 1st generation optical networks are similar to circuit-switched electronic networks. In contrast, 2nd generation telecommunication networks require different mathematical models and new algorithms, since an optical signal remains in optical form on its whole path from start to end node. Therefore, these networks are also all-optical. In an all-optical network without wavelength converters, the establishment of a new connection requires two decisions: which path in the network is to be used, and which wavelength is selected. The resulting pair that is composed of a path together with a wavelength is called a lightpath. The crucial condition that the same wavelength may only be used once per fiber is called wavelength conflict constraint.

Dynamic Configuration of Optical Networks

Moreover, all-optical networks allow to set up and take down connections on demand , since the configuration of an optical switch can be changed within milliseconds. This property gives rise to a typical online optimization problem, the dynamic configuration of all-optical networks, defined as follows. New connection requests occur over time, and lightpaths cease to exist as old connections end. Given the current network status, the network operator has to decide whether to accept or to reject a new connection request without knowing which connections will be asked for in the future. If a request is accepted, a valid routing must be established, that is, sufficiently many lightpaths must be installed without violating the wavelength conflict constraint. The objective of the operator is to make as much profit as Each connection request has an associated profit that may depend on various parameters such as the requested demand, the number of hops needed in a lightpath, the duration etc. The objective of the operator is to maximize the profit of accepted connections.

In the project Optimization of optical transport networks with dynamic routing we have studied the dynamic configuration problem. We have formulated an online optimization model for the problem that comprises many different requirements from practice, and that additionally allows to model failure situations. The focus of our work was the review, design, and implementation of algorithms for the dynamic routing of connection requests. We have also investigated distributed algorithms, that is, algorithms that work only with information gained at the network nodes without calling any centralized instance.

Results

Using a plausible traffic generation model and four realistic networks, we have evaluated various by means of simulation. We have compared several greedy algorithms, which choose a shortest one among a set of options by some (predefined or dynamically adapted) order on the wavelengths, to a number of more sophisticated algorithm that perform path and wavelength selection jointly.

One interesting result of our simulation experiments is that the choice of the tie-breaking rule substantially influences the performance of a greedy-algorithm, even if only globally shortest paths are considered. Moreover, our simulation experiments have shown that the best of the greedy algorithms is almost as good as the best among the more sophisticated algorithms. Yet, our simulation experiments have been carried out in a relatively homogeneous environment (unit prices/profits, arrival process with independent inter arrival times, et cetera). Experiences in other areas of optimization show that the performance of greedy algorithms might severely degrade on very irregular problem instances. Moreover, a major drawback of greedy algorithms is that that they neither take varying durations, profits, or different customer and service classes into account, nor can they handle start times that differ from the release times of calls.

The development and evaluation of well-funded, more sophisticated and yet fast algorithms is still in its infancy, and further research is needed in this area.

 

Poster (in german)

  • Online Call Control in Optischen Netzen (JPEG [528kB], PDF [160kB])

Publications

2004
Dynamical configuration of transparent optical telecommunication networks Operations Research Proceedings, Hein Fleuren, Dick den Hertog, Peter Kort (Eds.), pp. 25-32, 2004 Andreas Tuchscherer BibTeX
Routing in Optical Transport Networks
2003
Dynamic routing algorithms in transparent optical networks Proceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling (ONDM 2003), Tibor Cinkler, Tivadar Jakab, Jànos Tapolcai, Csaba Gàspàr (Eds.), pp. 293-312, 2003 (preprint available as ) Ralf Hülsermann, Monika Jäger, Diana Poensgen, Sven Krumke, Jörg Rambau, Andreas Tuchscherer BibTeX
Routing in Optical Transport Networks
2002
Online Call Admission in Optical Networks with Larger Wavelength Demands ZIB-Report 02-22 (Appeared in: Graph-Theoretic Concepts in Computer Science. 28 Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 333-344) Sven Krumke, Diana Poensgen PDF
BibTeX
URN
Routing in Optical Transport Networks