The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Resource Allocation and Performance Analysis Problems in Optical Networks

Esa Hyytiä

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Electrical and Communications Engineering for public examination and debate in Auditorium S4 at Helsinki University of Technology (Espoo, Finland) on the 10th of December, 2004, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-7405-1)   [705 KB]
Dissertation is also available in print (ISBN 951-22-7398-5)

Abstract

Optical networks pose a rich variety of new design and performance analysis problems. Typically, the static design problems belong to the field of combinatorial optimisation, whereas decision-making and performance analysis problems are best treated using appropriate stochastic models. This dissertation focuses on certain issues in resource allocation and performance evaluation of backbone wavelength-routed (WR) networks and metropolitan area optical burst switching (OBS) networks.

The first two parts of the thesis consider heuristic algorithms for the static routing and wavelength assignment (RWA) and logical topology design (LTD) problems that arise in the context of WR networks. In a static RWA problem, one is asked to establish a given set of lightpaths (or light trees) in an optical WR network with given constraints, where the objective often is to minimise the number of wavelength channels required. In LTD problem, the number of wavelength channels is given and one is asked to decide on the set of lightpaths so that, for instance, the mean sojourn time of packets travelling at the logical layer is minimised. In the thesis, several heuristic algorithms for both the RWA and LTD problems are described and numerical results are presented.

The third part of the thesis studies the dynamic control problem where connection requests, i.e. lightpath requests, arrive according to a certain traffic pattern and the task is to establish one lightpath at a time in the WR optical network so that the expected revenue is maximised or the expected cost is minimised. Typically, the goal of optimisation is to minimise some infinite time horizon cost function, such as the blocking probability. In this thesis, the dynamic RWA problem is studied in the framework of Markov decision processes (MDP). An algorithmic approach is proposed by which any given heuristic algorithm can be improved by applying the so-called first policy iteration (FPI) step of the MDP theory. Relative costs of states needed in FPI are estimated by on-the-fly simulations. The computational burden of the approach is alleviated by introducing the importance sampling (IS) technique with FPI, for which an adaptive algorithm is proposed for adjusting the optimal IS parameters at the same time as data are collected for the decision-making analysis.

The last part of the thesis considers OBS networks, which represent an intermediate step towards full optical packet switching networks. In OBS networks, the data are transferred using optical bursts consisting of several IP packets going to the same destination. On the route of the burst, temporary reservations are made only for the time during which the burst is transmitted. This thesis focuses on fairness issues in OBS networks. It is demonstrated that fairness can be improved by using fibre delay lines together with Just-Enough-Time protocol (JET). Furthermore, by choosing the routes in an appropriate way one can also reach a satisfactory level of fairness and, at the same time, lower the overall blocking probability. Possible scheduling policies for metropolitan area OBS ring networks are also studied.

This thesis consists of an overview and of the following 9 publications:

  1. Esa Hyytiä, 2004. Heuristic algorithms for the generalized routing and wavelength assignment problem. In: Seventeenth Nordic Teletraffic Seminar (NTS-17). Fornebu, Norway, August 2004.
  2. Esa Hyytiä, 2003. Maximization of single hop traffic with greedy heuristics. In: Proceedings of the 3rd IASTED International Conference on Wireless and Optical Communications (WOC 2003). Banff, Alberta, Canada, July 2003, pages 289-294.
  3. Esa Hyytiä and Jorma Virtamo, 2000. Dynamic routing and wavelength assignment using first policy iteration. In: Proceedings of the Fifth IEEE Symposium on Computers and Communications (ISCC'2000). Antibes - Juan les Pins, France, July 2000, pages 146-151.
  4. Esa Hyytiä and Jorma Virtamo, 2000. Dynamic routing and wavelength assignment using first policy iteration, inhomogeneous traffic case. In: Proceedings of the International Conference on Performance and QoS of Next Generation Networking (P&QNet 2000). Nagoya, Japan, November 2000, pages 301-316.
  5. Esa Hyytiä and Jorma Virtamo, 2001. Optimal importance sampling in Markov process simulation. In: Proceedings of the IASTED International Conference on Applied Simulation and Modelling (ASM 2001). Marbella, Spain, September 2001, pages 67-72.
  6. Esa Hyytiä and Jorma Virtamo, 2002. Adaptive importance sampling in routing and wavelength assignment problem. European Transactions on Telecommunications (ETT): Special Issue on Rare Event Simulation 13, number 4, pages 331-339.
  7. Laura Nieminen and Esa Hyytiä, 2003. Performance of the JET protocol with optical delay lines. In: Proceedings of the 7th IFIP Working Conference on Optical Network Design and Modelling (ONDM 2003). Budapest, Hungary, February 2003, pages 769-784.
  8. Esa Hyytiä and Laura Nieminen, 2004. Linear program formulation for routing problem in OBS networks. In: Proceedings of the Ninth IEEE Symposium on Computers and Communications (ISCC'2004). Alexandria, Egypt, June 2004, pages 252-257.
  9. Esa Hyytiä and Laura Nieminen, 2004. Analytical loss models for MAC protocols in optical ring network operating under a static traffic load. In: Proceedings of the 2004 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2004). San Jose, California, USA, July 2004, pages 135-141.

Errata of publication 6

Keywords: optical networks, WDM, routing and wavelength assignment, Markov decision process, policy iteration, optical burst switching

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2004 Helsinki University of Technology

Last update 2011-05-26