Resource allocation and performance analysis problems in optical networks
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2004-12-10
Major/Subject
Mcode
Degree programme
Language
en
Pages
106, [103]
Series
Report / Helsinki University of Technology, Networking Laboratory, 5/2004
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.Description
Keywords
optical networks, WDM, routing and wavelength assignment, Markov decision process, policy iteration, optical burst switching
Other note
Parts
- Esa Hyytiä, 2004. Heuristic algorithms for the generalized routing and wavelength assignment problem. In: Seventeenth Nordic Teletraffic Seminar (NTS-17). Fornebu, Norway, August 2004.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.