OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: O. Gerstel and P. Iannone
  • Vol. 6, Iss. 8 — Aug. 1, 2014
  • pp: 754–763

Spectrum Assignment in Optical Networks: A Multiprocessor Scheduling Perspective

Sahar Talebi, Evripidis Bampis, Giorgio Lucarelli, Iyad Katib, and George N. Rouskas  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 6, Issue 8, pp. 754-763 (2014)
http://dx.doi.org/10.1364/JOCN.6.000754


View Full Text Article

Enhanced HTML    Acrobat PDF (556 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

The routing and spectrum assignment problem has emerged as the key design and control problem in elastic optical networks. In this work, we show that the spectrum assignment (SA) problem in mesh networks transforms to the problem of scheduling multiprocessor tasks on dedicated processors. Based on this new perspective, we show that the SA problem in chain (linear) networks is NP-hard for four or more links, but is solvable in polynomial time for three links. We also develop new constant-ratio approximation algorithms for the SA problem in chains when the number of links is fixed. Finally, we present several list scheduling algorithms that are computationally efficient and simple to implement, yet produce solutions that, on average, are within 1%–5% of the lower bound.

© 2014 Optical Society of America

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4254) Fiber optics and optical communications : Networks, combinatorial network design
(060.4256) Fiber optics and optical communications : Networks, network optimization

ToC Category:
Research Papers

History
Original Manuscript: April 10, 2014
Revised Manuscript: June 18, 2014
Manuscript Accepted: June 29, 2014
Published: July 31, 2014

Citation
Sahar Talebi, Evripidis Bampis, Giorgio Lucarelli, Iyad Katib, and George N. Rouskas, "Spectrum Assignment in Optical Networks: A Multiprocessor Scheduling Perspective," J. Opt. Commun. Netw. 6, 754-763 (2014)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-6-8-754


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. O. Gerstel, M. Jinno, A. Lord, and S. J. B. Yoo, “Elastic optical networking: A new dawn for the optical layer?” IEEE Commun. Mag., vol.  50, no. 2, pp. s12–s20, 2012. [CrossRef]
  2. M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka, “Spectrum-efficient and scalable elastic optical path network: Architecture, benefits, and enabling technologies,” IEEE Commun. Mag., vol.  47, no. 11, pp. 66–73, 2009. [CrossRef]
  3. W. Shieh, “OFDM for flexible high-speed optical networks,” J. Lightwave Technol., vol.  29, no. 10, pp. 1560–1577, May2011. [CrossRef]
  4. S. Frisken, G. Baxter, D. Abakoumov, H. Zhou, I. Clarke, and S. Poole, “Flexible and grid-less wavelength selective switch using LCOS technology,” in Proc. OFC/NFOEC, 2011, paper OTuM3.
  5. R. Ryf, Y. Su, L. Moller, S. Chandrasekhar, X. Liu, D. T. Nelson, and C. R. Giles, “Wavelength blocking filter with flexible data rates and channel spacing,” J. Lightwave Technol., vol.  23, no. 1, pp. 54–61, Jan. 2005. [CrossRef]
  6. G. Zhang, M. De Leenheer, A. Morea, and B. Mukherjee, “A survey on OFDM-based elastic core optical networking,” IEEE Commun. Surv. Tutorials, vol.  15, no. 1, pp. 65–87, 2013. [CrossRef]
  7. M. Klinkowski and K. Walkowiak, “Routing and spectrum assignment in spectrum sliced elastic optical path network,” IEEE Commun. Lett., vol.  15, no. 8, pp. 884–886, 2011. [CrossRef]
  8. Y. Wang, X. Cao, and Y. Pan, “A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks,” in Proc. IEEE INFOCOM, 2011, pp. 1503–1511.
  9. K. Christodoulopoulos, I. Tomkos, and E. A. Varvarigos, “Elastic bandwidth allocation in flexible OFDM–based optical networks,” J. Lightwave Technol., vol.  29, no. 9, pp. 1354–1366, 2011. [CrossRef]
  10. Y. Zhang, X. Zheng, Q. Li, N. Hua, Y. Li, and H. Zhang, “Traffic grooming in spectrum-elastic optical path networks,” in Proc. of Optical Fiber Communication Conf. and the National Fiber Optic Engineers Conf. (OFC/NFOEC), Mar. 2011, paper OTuI1.
  11. Y. Wei, G. Shen, and S. You, “Span restoration for CO-OFDM-based elastic optical networks under spectrum conversion,” in Proc. of Asia Communications and Photonics Conf. (ACP), Nov. 2012, paper AF3E.7.
  12. G. N. Rouskas, “Routing and wavelength assignment in optical WDM networks,” in Wiley Encyclopedia of Telecommunications, J. Proakis, Ed. Wiley, 2001.
  13. Z. Liu and G. N. Rouskas, “A fast path-based ILP formulation for offline RWA in mesh optical networks,” in Proc. IEEE GLOBECOM, Anaheim, CA, Dec. 2012, pp. 2990–2995.
  14. S. Talebi, F. Alam, I. Katib, M. Khamis, R. Khalifah, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: A survey,” Opt. Switching Netw., vol.  13, pp. 34–48, July 2014.
  15. S. Shirazipourazad, C. Zhou, Z. Derakhshandeh, and A. Sen, “On routing and spectrum allocation in spectrum-sliced optical networks,” in Proc. IEEE INFOCOM, Apr. 2013, pp. 385–389.
  16. E. Bampis, M. Caramia, J. Fiala, A. Fishkin, and A. Iovanella, “Scheduling of independent dedicated multiprocessor tasks,” in Proc. of the 13th Annu. Int. Symp. on Algorithms and Computation, vol. 2518, Lecture Notes in Computer Science, 2002, pp. 391–402.
  17. J. A. Hoogeveen, S. L. Van de Velde, and B. Veltman, “Complexity of scheduling multiprocessor tasks with prespecified processor allocations,” Discrete Appl. Math., vol.  55, pp. 259–272, 1994. [CrossRef]
  18. S. Talebi, F. Alam, I. Katib, and G. N. Rouskas, “Spectrum assignment in rings with shortest path routing: Complexity and approximation algorithms,” to be presented at Proc. ICNC, Anaheim, CA.
  19. Y. Zhu, G. N. Rouskas, and H. G. Perros, “A path decomposition approach for computing blocking probabilities in wavelength routing networks,” IEEE/ACM Trans. Netw., vol.  8, pp. 747–762, Dec. 2000. [CrossRef]
  20. E. Bampis and A. Kononov, “On the approximability of scheduling multiprocessor tasks with time dependent processing and processor requirements,” in Proc. of the 15th Int. Parallel and Distributed Processing Symp., San Francisco, CA, 2001.
  21. M. R. Garey and D. S. Johnson, Computers and Intractability. New York: W. H. Freeman, 1979.
  22. J. Huang, J. Chen, S. Chen, and J. Wang, “A simple linear time approximation algorithm for multi-processor job scheduling on four processors,” J. Comb. Opt., vol.  13, pp. 33–45, 2007.
  23. M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag., vol.  48, no. 8, pp. 138–145, 2010. [CrossRef]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article

OSA is a member of CrossRef.

CrossCheck Deposited