Online scheduling of periodic lightpath request with flexibility

Abstract

Lightpath scheduling algorithms are the algorithms that assign wavelengths and time periods to lightpaths [4] [5]. There are two types of scheduling algorithms: online scheduling algorithms and offline scheduling algorithms. For online scheduling algorithms, lightpath requests arrive one at a time. The algorithms assign the arriving lightpath requests as they arrive without changing the existing 1ightpaths. For offline scheduling algorithms, lightpath requests arrive as a batch. The offline algorithms know all the lightpath requests in advance, and schedule all the lightpaths together. This leads to better performance than online algorithms. But online scheduling algorithms are more practical, since in many cases traffic arrives in some sequence over time. In addition, service providers may be reluctant to change lightpaths of existing customers, since they are concerned about violating service level agreements. In [5], the concept of time flexibility was considered, and several offline heuristic scheduling algorithms were proposed. In this thesis we follow the work done in [5]. Note that in [5], a special system case was considered: one WDM fiber link connecting two end nodes. In this special case, routing is not a consideration, only scheduling. In this thesis we use the same system model and scheduled traffic model with time flexibility in [5]. We proposed several online algorithms to solve the problem of scheduling scheduled lightpaths with time flexibility. The performances of the algorithms are evaluated according to the number of wavelengths used, assuming no traffic is blocked. The result of the simulations under different traffic circumstances shows that the online algorithms have comparable performance with the offline algorithms.