On preemptive multi-wavelength scheduling in hybrid WDM/TDM passive optical networks

Jingjing Zhang, Nirwan Ansari

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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)g/m, where 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.

Original languageEnglish (US)
Article number6171948
Pages (from-to)238-247
Number of pages10
JournalJournal of Optical Communications and Networking
Volume4
Issue number3
DOIs
StatePublished - Mar 2012

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Keywords

  • Approximation ratio
  • Delay
  • Fairness
  • Hybrid WDM/TDM PON
  • Wavelength scheduling

Fingerprint

Dive into the research topics of 'On preemptive multi-wavelength scheduling in hybrid WDM/TDM passive optical networks'. Together they form a unique fingerprint.

Cite this