Abstract

In this paper, we investigate the wavelength scheduling problem in hybrid wavelength division multiplexing/time division multiplexing passive optical networks (WDM/TDM PONs), which can be mapped into multiprocessor scheduling problems with wavelengths and optical network unit (ONU) requests being considered as machines and jobs, respectively. To achieve high bandwidth utilization, guarantee low delay, and ensure short-term fairness, we try to construct a schedule with the minimum latest job completion time. First, we investigate the non-preemptive scheduling problem, which was shown to be NP-hard, and hence requires heuristic algorithms to approximate the optimal solution. The approximation ratio of the best heuristic algorithm is as large as $2-1/m$, where m is the number of wavelengths. Motivated to achieve a smaller latest job completion time, we then investigate the preemptive scheduling problem. Preemption allows jobs to be scheduled more flexibly, and thus may yield a smaller makespan. However, with preemption, jobs may be split into subjobs and scheduled in discontinuous time durations at the expense of more guard time. We show that, with the consideration of guard time, the preemptive scheduling with the objective of minimizing the latest job completion time is NP-hard. To address the problem, we propose an approach by using linear programming with guard time supplement. It is shown that the proposed algorithm can ensure that the latest job completion time is no greater than the optimal value plus $(m-1)\mathfrak{g}/m$, where $\mathfrak{g}$ is the guard time between the scheduling of two ONUs. When the network is highly loaded, the approximation ratio is around 1.00061 and 1.002056 for hybrid WDM/TDM Ethernet PON (EPON) and Gigabit-capable PON (GPON), respectively.

©2012 Optical Society of America

Optimal Wavelength Scheduling for Hybrid WDM/TDM Passive Optical Networks

Chonggang Wang, Wei Wei, Weiyi Zhang, Hongbo Jiang, Chunming Qiao, and Ting Wang
J. Opt. Commun. Netw. 3(6) 522-532 (2011)

Code Division Multiple Access Enabled Dynamic Bandwidth Allocation (CDBA) Scheme for EPON

Elie Inaty, Robert Raad, Paul Fortier, and Martin Maier
J. Opt. Commun. Netw. 4(3) 271-281 (2012)

Dynamic Bandwidth Allocation Algorithm With Proper Guard Time Management Over Multi-OLT PON-Based Hybrid FTTH and Wireless Sensor Networks

Monir Hossen and Masanori Hanawa
J. Opt. Commun. Netw. 5(7) 802-812 (2013)

Design and performance evaluation of dynamic wavelength scheduled hybrid WDM/TDM PON for distributed computing applications

Min Zhu, Wei Guo, Shilin Xiao, Yi Dong, Weiqiang Sun, Yaohui Jin, and Weisheng Hu
Opt. Express 17(2) 1023-1032 (2009)

Design and Demonstration of REAM-Based WDM-PONs With Remote Amplification and Channel Fault Monitoring

Shu-Chuan Lin, San-Liang Lee, Cheng-Kuang Liu, Chun-Liang Yang, Sun-Chien Ko, Ty-Wang Liaw, and Gerd Keiser
J. Opt. Commun. Netw. 4(4) 336-343 (2012)