OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and O. Gerstel
  • Vol. 4, Iss. 3 — Mar. 1, 2012
  • pp: 238–247

On Preemptive Multi-wavelength Scheduling in Hybrid WDM/TDM Passive Optical Networks

Jingjing Zhang and Nirwan Ansari  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 4, Issue 3, pp. 238-247 (2012)
http://dx.doi.org/10.1364/JOCN.4.000238


View Full Text Article

Enhanced HTML    Acrobat PDF (259 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
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.

© 2012 OSA

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4510) Fiber optics and optical communications : Optical communications

ToC Category:
Research Papers

History
Original Manuscript: July 22, 2011
Revised Manuscript: January 19, 2012
Manuscript Accepted: January 26, 2012
Published: February 22, 2012

Citation
Jingjing Zhang and Nirwan Ansari, "On Preemptive Multi-wavelength Scheduling in Hybrid WDM/TDM Passive Optical Networks," J. Opt. Commun. Netw. 4, 238-247 (2012)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-4-3-238

You do not have subscription access to this journal. Citation lists with outbound citation links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an OSA member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Log in to access OSA Member Subscription

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited