Efficient scheduling of periodic traffic for WDM networks

Abstract

Numerous papers have looked at the problem of scheduling [1] [2] [3] [4] [5] [6] [7]. The relationship that time flexibility shares with periodic scheduled lightpaths and the number of wavelengths used was first proposed and analyzed in [2]. The work in [2] focused on a single WDM fiber link connecting two nodes. Scheduling algorithms were proposed and analyzed by simulation. Performance was based on the number of wavelengths utilized assuming static traffic. To simplify analysis, for each simulation batch of lightpath requests, the flexibility values were identical. The results of [2] show that with a modest amount of time flexibility, wavelength usage is considerably diminished. In [3] a dynamic traffic model was used and five online algorithms where purposed and analyzed using the same topology and traffic distributions in [2]. It was shown through simulation that online algorithms displayed comparable performance to offline algorithms. In [4] routing and scheduling lightpaths through a ring topology was considered. The routes of the lightpaths were shortest-hop paths, and lightpaths for the same source-destination pairs use the same paths. Additionally in [4], their online algorithms were used to do offline scheduling. In particular, a preprocessing algorithm that sorts a batch of lightpath requests was presented. Then the online algorithms would schedule the requests in that order. It was shown that intelligent ordering improved the wavelength utilization. In this thesis we follow the work done in [3] [4] by analyzing algorithm performance using the same scheduled traffic model with flexibility. However, our contribution will be to analyze performance across a mesh topology whereas [3] and [4] were restricted to single links or rings. Additionally, a more realistic traffic simulation is conducted in which flexibility values for lightpath requests can vary within a simulation batch. This is different from the analysis in [2] [3] [4] where simulations were conducted using identical flexibility values for all lightpath requests in a given simulation batch. Finally, we propose a new scheduling algorithm to take into account traffic sets composed of varying flexibilities. We present simulations that show our algorithm performs significantly better than existing online algorithms. This thesis is organized as follows. In Chapter 2 we describe the WDM topologies and traffic model. In Chapter 3 we discuss the top four best-performing scheduling algorithms from [3] [4], as well as our newly proposed algorithm. Chapter 4 presents our simulation results and compares the algorithms' performance to one another across different traffic distributions. Additionally, we look at the effect the topology has on the algorithm's performance. Finally, in Chapter 5 conclusions will be made and a discussion of future work will be given.