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

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  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]

2014 (1)

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.

2013 (1)

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]

2012 (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]

2011 (3)

2010 (1)

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]

2009 (1)

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]

2007 (1)

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.

2005 (1)

2000 (1)

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]

1994 (1)

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]

Abakoumov, D.

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.

Alam, F.

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.

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.

Bampis, E.

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.

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.

Baxter, G.

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.

Cao, X.

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.

Caramia, M.

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.

Chandrasekhar, S.

Chen, J.

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.

Chen, S.

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.

Christodoulopoulos, K.

Clarke, I.

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.

De Leenheer, M.

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]

Derakhshandeh, Z.

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.

Fiala, J.

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.

Fishkin, A.

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.

Frisken, S.

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.

Garey, M. R.

M. R. Garey and D. S. Johnson, Computers and Intractability. New York: W. H. Freeman, 1979.

Gerstel, O.

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]

Giles, C. R.

Hirano, A.

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]

Hoogeveen, J. A.

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]

Hua, N.

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.

Huang, J.

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.

Iovanella, A.

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.

Jinno, M.

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]

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]

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]

Johnson, D. S.

M. R. Garey and D. S. Johnson, Computers and Intractability. New York: W. H. Freeman, 1979.

Katib, I.

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.

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.

Khalifah, R.

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.

Khamis, M.

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.

Klinkowski, M.

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]

Kononov, A.

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.

Kozicki, B.

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]

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]

Li, Q.

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.

Li, Y.

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.

Liu, X.

Liu, Z.

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.

Lord, A.

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]

Matsuoka, S.

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]

Moller, L.

Morea, A.

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]

Mukherjee, B.

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]

Nelson, D. T.

Pan, Y.

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.

Perros, H. G.

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]

Poole, S.

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.

Rouskas, G. N.

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.

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]

G. N. Rouskas, “Routing and wavelength assignment in optical WDM networks,” in Wiley Encyclopedia of Telecommunications, J. Proakis, Ed. Wiley, 2001.

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.

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.

Ryf, R.

Sen, A.

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.

Shen, G.

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.

Shieh, W.

Shirazipourazad, S.

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.

Sone, Y.

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]

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]

Su, Y.

Takara, H.

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]

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]

Talebi, S.

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.

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.

Tanaka, T.

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]

Tomkos, I.

Tsukishima, Y.

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]

Van de Velde, S. L.

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]

Varvarigos, E. A.

Veltman, B.

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]

Walkowiak, K.

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]

Wang, J.

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.

Wang, Y.

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.

Watanabe, A.

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]

Wei, Y.

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.

Yoo, S. J. B.

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]

You, S.

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.

Zhang, G.

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]

Zhang, H.

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.

Zhang, Y.

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.

Zheng, X.

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.

Zhou, C.

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.

Zhou, H.

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.

Zhu, Y.

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]

Discrete Appl. Math. (1)

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]

IEEE Commun. Lett. (1)

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]

IEEE Commun. Mag. (3)

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]

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]

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]

IEEE Commun. Surv. Tutorials (1)

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]

IEEE/ACM Trans. Netw. (1)

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]

J. Comb. Opt. (1)

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.

J. Lightwave Technol. (3)

Opt. Switching Netw. (1)

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.

Other (11)

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.

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.

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.

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.

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.

G. N. Rouskas, “Routing and wavelength assignment in optical WDM networks,” in Wiley Encyclopedia of Telecommunications, J. Proakis, Ed. Wiley, 2001.

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.

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.

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.

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.

M. R. Garey and D. S. Johnson, Computers and Intractability. New York: W. H. Freeman, 1979.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (9)

Fig. 1.
Fig. 1.

(a) Instance of the offline RSA problem on a chain. (b) Optimal schedule for the corresponding P 3 | line j | C max problem.

Fig. 2.
Fig. 2.

Feasible schedule with C max = 4 B .

Fig. 3.
Fig. 3.

Two-approximation schedule for m = 9 processors.

Fig. 4.
Fig. 4.

Average ratio versus number of processors, discrete uniform distribution.

Fig. 5.
Fig. 5.

Average ratio versus number of processors, discrete high distribution.

Fig. 6.
Fig. 6.

Average ratio versus number of processors, discrete low distribution.

Fig. 7.
Fig. 7.

Average ratio versus number of processors, uniform distribution.

Fig. 8.
Fig. 8.

Average ratio versus number of processors, skewed high distribution.

Fig. 9.
Fig. 9.

Average ratio versus number of processors, skewed low distribution.

Tables (3)

Tables Icon

Algorithm 1 Two-Stage Approximation Algorithm for P | line j | C max , m 6

Tables Icon

Algorithm 2 Block-Based Scheduling Algorithm for P m | line j | C max

Tables Icon

Algorithm 3 Compact Scheduling Algorithm for P m | line j | C max

Equations (3)

Equations on this page are rendered with MathJax. Learn more.

T = [ 0 3 4 1 0 0 1 1 0 0 0 2 0 0 0 0 ] .
α = α mid + max { α l o , α h i } .
α ( m ) = { 1 m = 1 , 2 , 3 1.5 m = 4 , 5 min l = 1 , , m 2 { α ( l ) + α ( m l 2 ) } m 6 .