Abstract

We study the benefits and trade-offs of using scheduled lightpaths for traffic adaptation. We propose a network planning model that allows lightpaths to slide within their desired timing windows with no penalty on the optimization objective and to slide beyond their desired timing windows with a decreasing tolerance level. Our model quantitatively measures the timing satisfactions or violations. We apply the Lagrangian relaxation and subgradient methods to the formulated optimization problem, with which great computational efficiency is demonstrated when compared with other existing algorithms. Our simulation results show how timing flexibility improves network resource utilization and reduces rejections.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
    [CrossRef]
  2. K. Thompson, G. J. Miller, R. Wilder, “Wide-area Internet traffic patterns and characteristics,” IEEE Network, vol. 11, no. 6, pp. 10–23, Nov./Dec. 1997.
    [CrossRef]
  3. J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
    [CrossRef]
  4. M. Gagnaire, M. Koubaa, N. Puech, “Network dimensioning under scheduled and random lightpath demands in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 58–67, Dec. 2007.
    [CrossRef]
  5. J. Kuri, N. Puech, M. Gagnaire, “Diverse routing of scheduled lightpath demands in an optical transport network,” in 4th Int. Workshop on Design of Reliable Communication Networks (DCRN 2003), Banff, Alberta, Canada, 2003, pp. 69–76.
  6. C. V. Saradhi, L. K. Wei, M. Gurusamy, “Provisioning fault-tolerant scheduled lightpath demands in WDM mesh networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004, pp. 150–159.
  7. T. Li, B. Wang, “Path-protection-based routing and wavelength assignment in wavelength-division multiplexing optical networks under a scheduled traffic model,” J. Opt. Netw., vol. 5, no. 7, pp. 575–588, July 2006.
    [CrossRef]
  8. B. Wang, T. Li, “Survivable scheduled service provisioning in WDM optical networks with iterative routing,” Opt. Switching Networking, vol. 7, no. 1, pp. 28–38, Jan. 2010.
    [CrossRef]
  9. T. Li, B. Wang, C. Xin, X. Zhang, “On survivable service provisioning in WDM optical networks under a scheduled traffic model,” IEEE Global Telecommunications Conf. (GLOBECOM 2005), vol. 4, St. Louis, MO, 2005, pp. 1904–1908.
  10. N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 2–15, Aug. 2006.
  11. A. Jaekel, Y. Chen, “Routing and wavelength assignment for prioritized demands under a scheduled traffic model,” in 3rd Int. Conf. on Broadband Communications, Networks and Systems (BROADNETS 2006), San Jose, CA, 2006, pp. 1–7.
  12. C. Saradhi, M. Gurusamy, “Graph theoretic approaches for routing and wavelength assignment of scheduled lightpath demands in WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 2, pp. 1291–1299.
  13. S. Park, J. S. Yang, Y. C. Bang, “On RWA algorithms for scheduled lightpath demands in wavelength division multiplexing networks,” Int. J. Comput. Sci. Network Secur., vol. 7, no. 3, pp. 144–150, Mar. 2007.
  14. A. Chen, S. S. W. Lee, “A near-optimal heuristic algorithm for advance lightpath reservation in WDM networks,” in 34th European Conf. on Optical Communication (ECOC 2008), Brussels, Belgium, 2008, paper We.2.B.5.
  15. S. S. W. Lee, A. Chen, M. C. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photonic Network Commun., vol. 19, no. 1, pp. 103–109, Feb. 2010.
    [CrossRef]
  16. A. Jaekel, Y. Chen, “Resource provisioning for survivable WDM networks under a sliding scheduled traffic model,” Opt. Switching Networking, vol. 6, no. 1, pp. 44–54, Jan. 2009.
    [CrossRef]
  17. A. Jaekel, “Lightpath scheduling and allocation under a flexible scheduled traffic model,” in IEEE Global Telecommunications Conf. (GLOBECOM 2006), San Francisco, CA, 2006.
  18. B. Wang, T. Li, X. Luo, Y. Fan, C. Xin, “On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 1, pp. 13–22.
  19. B. Wang, T. Li, X. Luo, Y. Fan, “Traffic grooming under a sliding scheduled traffic model in WDM optical networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004.
  20. W. Su, G. Sasaki, C. F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, no. 3–4, pp. 158–172, Dec. 2006.
    [CrossRef]
  21. C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC 2007), Anaheim, CA, 2007, paper OWR7.
  22. H. H. Nguyen, M. Gurusamy, L. Zhou, “Scheduling network and computing resources for sliding demands in optical grids,” J. Lightwave Technol., vol. 27, no. 12, pp. 1827–1836, June 2009.
    [CrossRef]
  23. Y. Wang, Y. Jin, W. Guo, W. Sun, W. Hu, “Joint scheduling for optical grid applications,” J. Opt. Netw., vol. 6, no. 3, pp. 304–318, Mar. 2007.
    [CrossRef]
  24. X. Liu, C. Qiao, W. Wei, X. Yu, T. Wang, W. Hu, W. Guo, M. Y. Wu, “Task scheduling and lightpath establishment in optical grids,” J. Lightwave Technol., vol. 27, no. 12, pp. 1796–1805, June 2009.
    [CrossRef]
  25. X. Yang, L. Shen, A. Todimala, B. Ramamurthy, T. Lehman, “An efficient scheduling scheme for on-demand lightpath reservations in reconfigurable WDM optical networks,” in Optical Fiber Communication Conf. (OFC 2006), San Diego, CA, 2006, paper OTuN2.
  26. L. Shen, X. Yang, A. Todimala, B. Ramamurthy, “A two-phase approach for dynamic lightpath scheduling in WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2007), Glasgow, UK, 2007, pp. 2412–2417.
  27. S. Tanwir, L. Battestilli, H. Perros, G. Karmous-Edwards, “Dynamic scheduling of network resources with advance reservations in optical grids,” Int. J. Network Manage., vol. 18, no. 2, pp. 79–105, Mar. 2008.
    [CrossRef]
  28. M. Tornatore, C. Ou, J. Zhang, A. Pattavina, B. Mukherjee, “PHOTO: an efficient shared-path-protection strategy based on connection-holding-time awareness,” J. Lightwave Technol., vol. 23, no. 10, pp. 3138–3146, Oct. 2005.
    [CrossRef]
  29. D. Lucerna, M. Tornatore, B. Mukherjee, A. Pattavina, “Dynamic routing of connections with known duration in WDM networks,” in IEEE Global Communications Conf. (GLOBECOM 2009), Honolulu, HI, 2009.
  30. D. Lucerna, A. Baruffaldi, M. Tornatore, A. Pattavina, “On the efficiency of dynamic routing of connections with known duration,” in IEEE Int. Conf. on Communications (ICC 2009), Dresden, Germany, 2009.
  31. H. Miyagi, M. Hayashitani, D. Ishii, Y. Arakawa, N. Yamanaka, “Advanced wavelength reservation method based on deadline-aware scheduling for lambda grid networks,” J. Lightwave Technol., vol. 25, no. 10, pp. 2904–2910, Oct. 2007.
    [CrossRef]
  32. B. Wang, A. Deshmukh, “An all hops optimal algorithm for dynamic routing of sliding scheduled traffic demands,” IEEE Commun. Lett., vol. 9, no. 10, pp. 936–938, Oct. 2005.
    [CrossRef]
  33. J. Zheng, H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2002), New York, NY, 2002, vol. 5, pp. 2722–2726.
  34. J. Zheng, B. Zhou, H. T. Mouftah, “Toward automated provisioning of advance reservation service in next-generation optical Internet,” IEEE Commun. Mag., vol. 44, no. 12, pp. 68–74, Dec. 2006.
    [CrossRef]
  35. A. Narula-Tam, E. Modiano, “Dynamic load balancing in WDM packet networks with and without wavelength constraints,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1972–1979, Oct. 2000.
    [CrossRef]
  36. P. N. Tran, U. Killat, “Dynamic reconfiguration of logical topology for WDM networks under traffic changes,” in IEEE Network Operations and Management Symp. (NOMS 2008), Salvador, Bahia, Brazil, 2008, pp. 279–286.
  37. K. Lee, L. Zhang, C. H. Youn, “An adaptive virtual topology reconfiguration policy in multi-wavelength optical Internet,” Eur. Trans Telecommun. Relat. Technol., vol. 14, no. 5, pp. 417–422, Dec. 2003.
  38. F. Ricciato, S. Salsano, A. Belmonte, M. Listanti, “Off-line configuration of a MPLS over WDM network under time-varying offered traffic,” in 21st Annu. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, 2000, vol. 1, pp. 57–65.
  39. S. Huang, R. Dutta, “Spare capacity provisioning for quasi-static traffic,” Comput. Netw., vol. 51, no. 18, pp. 5011–5035, Dec. 2007.
    [CrossRef]
  40. I. Chlamtac, A. Ganz, “Lightnets: topologies for high-speed optical networks,” J. Lightwave Technol., vol. 11, no. 5/6, pp. 951–961, May/June 1993.
    [CrossRef]
  41. J. Y. Zhang, O. Yang, J. Wu, M. Savoie, “Connection routing optimization in a semi-dynamic reconfigurable WDM network,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 3–17, Dec. 2007.
    [CrossRef]
  42. I. Chlamtac, A. Farago, T. Zhang, “Lightpath (wavelength) routing in large WDM networks,” IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 909–913, June 1996.
    [CrossRef]
  43. Y. Zhang, J. Wu, O. Yang, M. Savoie, “A Lagrangian-relaxation based network profit optimization for mesh SONET-over-WDM networks,” Photonic Network Commun., vol. 10, no. 2, pp. 155–178, Sept. 2005.
    [CrossRef]
  44. J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, no. 2–3, pp. 107–122, June 2008.
    [CrossRef]
  45. B. Jin, P. B. Luh, L. S. Thakur, “An effective optimization-based algorithm for job shop scheduling with fixed-size transfer lots,” J. Manuf. Syst., vol. 18, no. 4, pp. 284–300, Aug. 1999.
    [CrossRef]
  46. Y. Zhang, O. Yang, H. Liu, “A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1752–1765, Nov. 2004.
    [CrossRef]
  47. M. Saad, Z. Luo, “On the routing and wavelength assignment in multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1708–1717, Nov. 2004.
    [CrossRef]
  48. S. S. W. Lee, M. C. Yuang, P. Tien, S. H. Lin, “A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1741–1751, Nov. 2004.
    [CrossRef]
  49. X. Guan, S. Guo, Q. Zhai, W. Gong, C. Qiao, “A new method for solving routing and wavelength assignment problems in optical networks,” J. Lightwave Technol., vol. 25, no. 8, pp. 1895–1909, Aug. 2007.
    [CrossRef]
  50. H. H. Yen, S. S. W. Lee, B. Mukherjee, “Traffic grooming and delay constrained multicast routing in IP over WDM networks,” in IEEE Int. Conf. on Communications (ICC 2008), Beijing, China, 2008, pp 5246–5251.
  51. C. S. Sung, S. H. Song, “Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network,” J. Oper. Res. Soc., vol. 54, no. 1, pp. 72–82, Jan. 2003.
    [CrossRef]
  52. K. Holmberg, J. Hellstrand, “Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound,” Oper. Res., vol. 46, no. 2, pp. 247–259, Mar.–Apr. 1998.
    [CrossRef]
  53. Z. K. G. Patrocinio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf. (GLOBECOM 2003), San Francisco, CA, 2003, vol. 5, pp. 2767–2771.
  54. D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.

2010

S. S. W. Lee, A. Chen, M. C. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photonic Network Commun., vol. 19, no. 1, pp. 103–109, Feb. 2010.
[CrossRef]

B. Wang, T. Li, “Survivable scheduled service provisioning in WDM optical networks with iterative routing,” Opt. Switching Networking, vol. 7, no. 1, pp. 28–38, Jan. 2010.
[CrossRef]

2009

2008

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, no. 2–3, pp. 107–122, June 2008.
[CrossRef]

S. Tanwir, L. Battestilli, H. Perros, G. Karmous-Edwards, “Dynamic scheduling of network resources with advance reservations in optical grids,” Int. J. Network Manage., vol. 18, no. 2, pp. 79–105, Mar. 2008.
[CrossRef]

2007

J. Y. Zhang, O. Yang, J. Wu, M. Savoie, “Connection routing optimization in a semi-dynamic reconfigurable WDM network,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 3–17, Dec. 2007.
[CrossRef]

Y. Wang, Y. Jin, W. Guo, W. Sun, W. Hu, “Joint scheduling for optical grid applications,” J. Opt. Netw., vol. 6, no. 3, pp. 304–318, Mar. 2007.
[CrossRef]

X. Guan, S. Guo, Q. Zhai, W. Gong, C. Qiao, “A new method for solving routing and wavelength assignment problems in optical networks,” J. Lightwave Technol., vol. 25, no. 8, pp. 1895–1909, Aug. 2007.
[CrossRef]

H. Miyagi, M. Hayashitani, D. Ishii, Y. Arakawa, N. Yamanaka, “Advanced wavelength reservation method based on deadline-aware scheduling for lambda grid networks,” J. Lightwave Technol., vol. 25, no. 10, pp. 2904–2910, Oct. 2007.
[CrossRef]

M. Gagnaire, M. Koubaa, N. Puech, “Network dimensioning under scheduled and random lightpath demands in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 58–67, Dec. 2007.
[CrossRef]

S. Park, J. S. Yang, Y. C. Bang, “On RWA algorithms for scheduled lightpath demands in wavelength division multiplexing networks,” Int. J. Comput. Sci. Network Secur., vol. 7, no. 3, pp. 144–150, Mar. 2007.

S. Huang, R. Dutta, “Spare capacity provisioning for quasi-static traffic,” Comput. Netw., vol. 51, no. 18, pp. 5011–5035, Dec. 2007.
[CrossRef]

2006

N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 2–15, Aug. 2006.

J. Zheng, B. Zhou, H. T. Mouftah, “Toward automated provisioning of advance reservation service in next-generation optical Internet,” IEEE Commun. Mag., vol. 44, no. 12, pp. 68–74, Dec. 2006.
[CrossRef]

W. Su, G. Sasaki, C. F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, no. 3–4, pp. 158–172, Dec. 2006.
[CrossRef]

T. Li, B. Wang, “Path-protection-based routing and wavelength assignment in wavelength-division multiplexing optical networks under a scheduled traffic model,” J. Opt. Netw., vol. 5, no. 7, pp. 575–588, July 2006.
[CrossRef]

2005

Y. Zhang, J. Wu, O. Yang, M. Savoie, “A Lagrangian-relaxation based network profit optimization for mesh SONET-over-WDM networks,” Photonic Network Commun., vol. 10, no. 2, pp. 155–178, Sept. 2005.
[CrossRef]

M. Tornatore, C. Ou, J. Zhang, A. Pattavina, B. Mukherjee, “PHOTO: an efficient shared-path-protection strategy based on connection-holding-time awareness,” J. Lightwave Technol., vol. 23, no. 10, pp. 3138–3146, Oct. 2005.
[CrossRef]

B. Wang, A. Deshmukh, “An all hops optimal algorithm for dynamic routing of sliding scheduled traffic demands,” IEEE Commun. Lett., vol. 9, no. 10, pp. 936–938, Oct. 2005.
[CrossRef]

2004

Y. Zhang, O. Yang, H. Liu, “A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1752–1765, Nov. 2004.
[CrossRef]

M. Saad, Z. Luo, “On the routing and wavelength assignment in multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1708–1717, Nov. 2004.
[CrossRef]

S. S. W. Lee, M. C. Yuang, P. Tien, S. H. Lin, “A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1741–1751, Nov. 2004.
[CrossRef]

2003

C. S. Sung, S. H. Song, “Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network,” J. Oper. Res. Soc., vol. 54, no. 1, pp. 72–82, Jan. 2003.
[CrossRef]

J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
[CrossRef]

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

K. Lee, L. Zhang, C. H. Youn, “An adaptive virtual topology reconfiguration policy in multi-wavelength optical Internet,” Eur. Trans Telecommun. Relat. Technol., vol. 14, no. 5, pp. 417–422, Dec. 2003.

2000

A. Narula-Tam, E. Modiano, “Dynamic load balancing in WDM packet networks with and without wavelength constraints,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1972–1979, Oct. 2000.
[CrossRef]

1999

B. Jin, P. B. Luh, L. S. Thakur, “An effective optimization-based algorithm for job shop scheduling with fixed-size transfer lots,” J. Manuf. Syst., vol. 18, no. 4, pp. 284–300, Aug. 1999.
[CrossRef]

1998

K. Holmberg, J. Hellstrand, “Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound,” Oper. Res., vol. 46, no. 2, pp. 247–259, Mar.–Apr. 1998.
[CrossRef]

1997

K. Thompson, G. J. Miller, R. Wilder, “Wide-area Internet traffic patterns and characteristics,” IEEE Network, vol. 11, no. 6, pp. 10–23, Nov./Dec. 1997.
[CrossRef]

1996

I. Chlamtac, A. Farago, T. Zhang, “Lightpath (wavelength) routing in large WDM networks,” IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 909–913, June 1996.
[CrossRef]

1993

I. Chlamtac, A. Ganz, “Lightnets: topologies for high-speed optical networks,” J. Lightwave Technol., vol. 11, no. 5/6, pp. 951–961, May/June 1993.
[CrossRef]

Arakawa, Y.

Balasubramanian, A.

W. Su, G. Sasaki, C. F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, no. 3–4, pp. 158–172, Dec. 2006.
[CrossRef]

Bang, Y. C.

S. Park, J. S. Yang, Y. C. Bang, “On RWA algorithms for scheduled lightpath demands in wavelength division multiplexing networks,” Int. J. Comput. Sci. Network Secur., vol. 7, no. 3, pp. 144–150, Mar. 2007.

Baruffaldi, A.

D. Lucerna, A. Baruffaldi, M. Tornatore, A. Pattavina, “On the efficiency of dynamic routing of connections with known duration,” in IEEE Int. Conf. on Communications (ICC 2009), Dresden, Germany, 2009.

Battestilli, L.

S. Tanwir, L. Battestilli, H. Perros, G. Karmous-Edwards, “Dynamic scheduling of network resources with advance reservations in optical grids,” Int. J. Network Manage., vol. 18, no. 2, pp. 79–105, Mar. 2008.
[CrossRef]

Belmonte, A.

F. Ricciato, S. Salsano, A. Belmonte, M. Listanti, “Off-line configuration of a MPLS over WDM network under time-varying offered traffic,” in 21st Annu. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, 2000, vol. 1, pp. 57–65.

Bertsekas, D. P.

D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.

Bochmann, G. V.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, no. 2–3, pp. 107–122, June 2008.
[CrossRef]

Chen, A.

S. S. W. Lee, A. Chen, M. C. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photonic Network Commun., vol. 19, no. 1, pp. 103–109, Feb. 2010.
[CrossRef]

A. Chen, S. S. W. Lee, “A near-optimal heuristic algorithm for advance lightpath reservation in WDM networks,” in 34th European Conf. on Optical Communication (ECOC 2008), Brussels, Belgium, 2008, paper We.2.B.5.

Chen, Y.

A. Jaekel, Y. Chen, “Resource provisioning for survivable WDM networks under a sliding scheduled traffic model,” Opt. Switching Networking, vol. 6, no. 1, pp. 44–54, Jan. 2009.
[CrossRef]

A. Jaekel, Y. Chen, “Routing and wavelength assignment for prioritized demands under a scheduled traffic model,” in 3rd Int. Conf. on Broadband Communications, Networks and Systems (BROADNETS 2006), San Jose, CA, 2006, pp. 1–7.

Chlamtac, I.

I. Chlamtac, A. Farago, T. Zhang, “Lightpath (wavelength) routing in large WDM networks,” IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 909–913, June 1996.
[CrossRef]

I. Chlamtac, A. Ganz, “Lightnets: topologies for high-speed optical networks,” J. Lightwave Technol., vol. 11, no. 5/6, pp. 951–961, May/June 1993.
[CrossRef]

Deshmukh, A.

B. Wang, A. Deshmukh, “An all hops optimal algorithm for dynamic routing of sliding scheduled traffic demands,” IEEE Commun. Lett., vol. 9, no. 10, pp. 936–938, Oct. 2005.
[CrossRef]

Dotaro, E.

J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
[CrossRef]

Douville, R.

J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
[CrossRef]

Dutta, R.

S. Huang, R. Dutta, “Spare capacity provisioning for quasi-static traffic,” Comput. Netw., vol. 51, no. 18, pp. 5011–5035, Dec. 2007.
[CrossRef]

Fan, Y.

B. Wang, T. Li, X. Luo, Y. Fan, “Traffic grooming under a sliding scheduled traffic model in WDM optical networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004.

B. Wang, T. Li, X. Luo, Y. Fan, C. Xin, “On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 1, pp. 13–22.

Farago, A.

I. Chlamtac, A. Farago, T. Zhang, “Lightpath (wavelength) routing in large WDM networks,” IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 909–913, June 1996.
[CrossRef]

Gagnaire, M.

M. Gagnaire, M. Koubaa, N. Puech, “Network dimensioning under scheduled and random lightpath demands in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 58–67, Dec. 2007.
[CrossRef]

J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
[CrossRef]

J. Kuri, N. Puech, M. Gagnaire, “Diverse routing of scheduled lightpath demands in an optical transport network,” in 4th Int. Workshop on Design of Reliable Communication Networks (DCRN 2003), Banff, Alberta, Canada, 2003, pp. 69–76.

Ganz, A.

I. Chlamtac, A. Ganz, “Lightnets: topologies for high-speed optical networks,” J. Lightwave Technol., vol. 11, no. 5/6, pp. 951–961, May/June 1993.
[CrossRef]

Gencata, A.

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

Gong, W.

Guan, X.

Guo, S.

Guo, W.

Gurusamy, M.

H. H. Nguyen, M. Gurusamy, L. Zhou, “Scheduling network and computing resources for sliding demands in optical grids,” J. Lightwave Technol., vol. 27, no. 12, pp. 1827–1836, June 2009.
[CrossRef]

C. Saradhi, M. Gurusamy, “Graph theoretic approaches for routing and wavelength assignment of scheduled lightpath demands in WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 2, pp. 1291–1299.

C. V. Saradhi, L. K. Wei, M. Gurusamy, “Provisioning fault-tolerant scheduled lightpath demands in WDM mesh networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004, pp. 150–159.

C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC 2007), Anaheim, CA, 2007, paper OWR7.

Hayashitani, M.

Hellstrand, J.

K. Holmberg, J. Hellstrand, “Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound,” Oper. Res., vol. 46, no. 2, pp. 247–259, Mar.–Apr. 1998.
[CrossRef]

Holmberg, K.

K. Holmberg, J. Hellstrand, “Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound,” Oper. Res., vol. 46, no. 2, pp. 247–259, Mar.–Apr. 1998.
[CrossRef]

Hu, W.

Huang, S.

S. Huang, R. Dutta, “Spare capacity provisioning for quasi-static traffic,” Comput. Netw., vol. 51, no. 18, pp. 5011–5035, Dec. 2007.
[CrossRef]

Ishii, D.

Jaekel, A.

A. Jaekel, Y. Chen, “Resource provisioning for survivable WDM networks under a sliding scheduled traffic model,” Opt. Switching Networking, vol. 6, no. 1, pp. 44–54, Jan. 2009.
[CrossRef]

A. Jaekel, “Lightpath scheduling and allocation under a flexible scheduled traffic model,” in IEEE Global Telecommunications Conf. (GLOBECOM 2006), San Francisco, CA, 2006.

A. Jaekel, Y. Chen, “Routing and wavelength assignment for prioritized demands under a scheduled traffic model,” in 3rd Int. Conf. on Broadband Communications, Networks and Systems (BROADNETS 2006), San Jose, CA, 2006, pp. 1–7.

Jin, B.

B. Jin, P. B. Luh, L. S. Thakur, “An effective optimization-based algorithm for job shop scheduling with fixed-size transfer lots,” J. Manuf. Syst., vol. 18, no. 4, pp. 284–300, Aug. 1999.
[CrossRef]

Jin, Y.

Karmous-Edwards, G.

S. Tanwir, L. Battestilli, H. Perros, G. Karmous-Edwards, “Dynamic scheduling of network resources with advance reservations in optical grids,” Int. J. Network Manage., vol. 18, no. 2, pp. 79–105, Mar. 2008.
[CrossRef]

Killat, U.

P. N. Tran, U. Killat, “Dynamic reconfiguration of logical topology for WDM networks under traffic changes,” in IEEE Network Operations and Management Symp. (NOMS 2008), Salvador, Bahia, Brazil, 2008, pp. 279–286.

Koubaa, M.

M. Gagnaire, M. Koubaa, N. Puech, “Network dimensioning under scheduled and random lightpath demands in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 58–67, Dec. 2007.
[CrossRef]

Kuri, J.

J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
[CrossRef]

J. Kuri, N. Puech, M. Gagnaire, “Diverse routing of scheduled lightpath demands in an optical transport network,” in 4th Int. Workshop on Design of Reliable Communication Networks (DCRN 2003), Banff, Alberta, Canada, 2003, pp. 69–76.

Lee, K.

K. Lee, L. Zhang, C. H. Youn, “An adaptive virtual topology reconfiguration policy in multi-wavelength optical Internet,” Eur. Trans Telecommun. Relat. Technol., vol. 14, no. 5, pp. 417–422, Dec. 2003.

Lee, S. S. W.

S. S. W. Lee, A. Chen, M. C. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photonic Network Commun., vol. 19, no. 1, pp. 103–109, Feb. 2010.
[CrossRef]

S. S. W. Lee, M. C. Yuang, P. Tien, S. H. Lin, “A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1741–1751, Nov. 2004.
[CrossRef]

A. Chen, S. S. W. Lee, “A near-optimal heuristic algorithm for advance lightpath reservation in WDM networks,” in 34th European Conf. on Optical Communication (ECOC 2008), Brussels, Belgium, 2008, paper We.2.B.5.

H. H. Yen, S. S. W. Lee, B. Mukherjee, “Traffic grooming and delay constrained multicast routing in IP over WDM networks,” in IEEE Int. Conf. on Communications (ICC 2008), Beijing, China, 2008, pp 5246–5251.

Lehman, T.

X. Yang, L. Shen, A. Todimala, B. Ramamurthy, T. Lehman, “An efficient scheduling scheme for on-demand lightpath reservations in reconfigurable WDM optical networks,” in Optical Fiber Communication Conf. (OFC 2006), San Diego, CA, 2006, paper OTuN2.

Li, T.

B. Wang, T. Li, “Survivable scheduled service provisioning in WDM optical networks with iterative routing,” Opt. Switching Networking, vol. 7, no. 1, pp. 28–38, Jan. 2010.
[CrossRef]

T. Li, B. Wang, “Path-protection-based routing and wavelength assignment in wavelength-division multiplexing optical networks under a scheduled traffic model,” J. Opt. Netw., vol. 5, no. 7, pp. 575–588, July 2006.
[CrossRef]

T. Li, B. Wang, C. Xin, X. Zhang, “On survivable service provisioning in WDM optical networks under a scheduled traffic model,” IEEE Global Telecommunications Conf. (GLOBECOM 2005), vol. 4, St. Louis, MO, 2005, pp. 1904–1908.

B. Wang, T. Li, X. Luo, Y. Fan, C. Xin, “On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 1, pp. 13–22.

B. Wang, T. Li, X. Luo, Y. Fan, “Traffic grooming under a sliding scheduled traffic model in WDM optical networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004.

Lin, S. H.

S. S. W. Lee, M. C. Yuang, P. Tien, S. H. Lin, “A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1741–1751, Nov. 2004.
[CrossRef]

Listanti, M.

F. Ricciato, S. Salsano, A. Belmonte, M. Listanti, “Off-line configuration of a MPLS over WDM network under time-varying offered traffic,” in 21st Annu. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, 2000, vol. 1, pp. 57–65.

Liu, H.

Y. Zhang, O. Yang, H. Liu, “A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1752–1765, Nov. 2004.
[CrossRef]

Liu, X.

Lucerna, D.

D. Lucerna, A. Baruffaldi, M. Tornatore, A. Pattavina, “On the efficiency of dynamic routing of connections with known duration,” in IEEE Int. Conf. on Communications (ICC 2009), Dresden, Germany, 2009.

D. Lucerna, M. Tornatore, B. Mukherjee, A. Pattavina, “Dynamic routing of connections with known duration in WDM networks,” in IEEE Global Communications Conf. (GLOBECOM 2009), Honolulu, HI, 2009.

Luh, P. B.

B. Jin, P. B. Luh, L. S. Thakur, “An effective optimization-based algorithm for job shop scheduling with fixed-size transfer lots,” J. Manuf. Syst., vol. 18, no. 4, pp. 284–300, Aug. 1999.
[CrossRef]

Luo, X.

B. Wang, T. Li, X. Luo, Y. Fan, “Traffic grooming under a sliding scheduled traffic model in WDM optical networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004.

B. Wang, T. Li, X. Luo, Y. Fan, C. Xin, “On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 1, pp. 13–22.

Luo, Z.

M. Saad, Z. Luo, “On the routing and wavelength assignment in multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1708–1717, Nov. 2004.
[CrossRef]

Mateus, G. R.

Z. K. G. Patrocinio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf. (GLOBECOM 2003), San Francisco, CA, 2003, vol. 5, pp. 2767–2771.

Miller, G. J.

K. Thompson, G. J. Miller, R. Wilder, “Wide-area Internet traffic patterns and characteristics,” IEEE Network, vol. 11, no. 6, pp. 10–23, Nov./Dec. 1997.
[CrossRef]

Miyagi, H.

Modiano, E.

A. Narula-Tam, E. Modiano, “Dynamic load balancing in WDM packet networks with and without wavelength constraints,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1972–1979, Oct. 2000.
[CrossRef]

Mouftah, H. T.

J. Zheng, B. Zhou, H. T. Mouftah, “Toward automated provisioning of advance reservation service in next-generation optical Internet,” IEEE Commun. Mag., vol. 44, no. 12, pp. 68–74, Dec. 2006.
[CrossRef]

J. Zheng, H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2002), New York, NY, 2002, vol. 5, pp. 2722–2726.

Mukherjee, B.

M. Tornatore, C. Ou, J. Zhang, A. Pattavina, B. Mukherjee, “PHOTO: an efficient shared-path-protection strategy based on connection-holding-time awareness,” J. Lightwave Technol., vol. 23, no. 10, pp. 3138–3146, Oct. 2005.
[CrossRef]

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

H. H. Yen, S. S. W. Lee, B. Mukherjee, “Traffic grooming and delay constrained multicast routing in IP over WDM networks,” in IEEE Int. Conf. on Communications (ICC 2008), Beijing, China, 2008, pp 5246–5251.

D. Lucerna, M. Tornatore, B. Mukherjee, A. Pattavina, “Dynamic routing of connections with known duration in WDM networks,” in IEEE Global Communications Conf. (GLOBECOM 2009), Honolulu, HI, 2009.

Narula-Tam, A.

A. Narula-Tam, E. Modiano, “Dynamic load balancing in WDM packet networks with and without wavelength constraints,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1972–1979, Oct. 2000.
[CrossRef]

Nguyen, H. H.

Ou, C.

Park, S.

S. Park, J. S. Yang, Y. C. Bang, “On RWA algorithms for scheduled lightpath demands in wavelength division multiplexing networks,” Int. J. Comput. Sci. Network Secur., vol. 7, no. 3, pp. 144–150, Mar. 2007.

Patrocinio, Z. K. G.

Z. K. G. Patrocinio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf. (GLOBECOM 2003), San Francisco, CA, 2003, vol. 5, pp. 2767–2771.

Pattavina, A.

M. Tornatore, C. Ou, J. Zhang, A. Pattavina, B. Mukherjee, “PHOTO: an efficient shared-path-protection strategy based on connection-holding-time awareness,” J. Lightwave Technol., vol. 23, no. 10, pp. 3138–3146, Oct. 2005.
[CrossRef]

D. Lucerna, M. Tornatore, B. Mukherjee, A. Pattavina, “Dynamic routing of connections with known duration in WDM networks,” in IEEE Global Communications Conf. (GLOBECOM 2009), Honolulu, HI, 2009.

D. Lucerna, A. Baruffaldi, M. Tornatore, A. Pattavina, “On the efficiency of dynamic routing of connections with known duration,” in IEEE Int. Conf. on Communications (ICC 2009), Dresden, Germany, 2009.

Perros, H.

S. Tanwir, L. Battestilli, H. Perros, G. Karmous-Edwards, “Dynamic scheduling of network resources with advance reservations in optical grids,” Int. J. Network Manage., vol. 18, no. 2, pp. 79–105, Mar. 2008.
[CrossRef]

Puech, N.

M. Gagnaire, M. Koubaa, N. Puech, “Network dimensioning under scheduled and random lightpath demands in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 58–67, Dec. 2007.
[CrossRef]

J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
[CrossRef]

J. Kuri, N. Puech, M. Gagnaire, “Diverse routing of scheduled lightpath demands in an optical transport network,” in 4th Int. Workshop on Design of Reliable Communication Networks (DCRN 2003), Banff, Alberta, Canada, 2003, pp. 69–76.

Qiao, C.

Ramamurthy, B.

X. Yang, L. Shen, A. Todimala, B. Ramamurthy, T. Lehman, “An efficient scheduling scheme for on-demand lightpath reservations in reconfigurable WDM optical networks,” in Optical Fiber Communication Conf. (OFC 2006), San Diego, CA, 2006, paper OTuN2.

L. Shen, X. Yang, A. Todimala, B. Ramamurthy, “A two-phase approach for dynamic lightpath scheduling in WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2007), Glasgow, UK, 2007, pp. 2412–2417.

Ricciato, F.

F. Ricciato, S. Salsano, A. Belmonte, M. Listanti, “Off-line configuration of a MPLS over WDM network under time-varying offered traffic,” in 21st Annu. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, 2000, vol. 1, pp. 57–65.

Saad, M.

M. Saad, Z. Luo, “On the routing and wavelength assignment in multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1708–1717, Nov. 2004.
[CrossRef]

Salsano, S.

F. Ricciato, S. Salsano, A. Belmonte, M. Listanti, “Off-line configuration of a MPLS over WDM network under time-varying offered traffic,” in 21st Annu. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, 2000, vol. 1, pp. 57–65.

Saradhi, C.

C. Saradhi, M. Gurusamy, “Graph theoretic approaches for routing and wavelength assignment of scheduled lightpath demands in WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 2, pp. 1291–1299.

Saradhi, C. V.

C. V. Saradhi, L. K. Wei, M. Gurusamy, “Provisioning fault-tolerant scheduled lightpath demands in WDM mesh networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004, pp. 150–159.

C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC 2007), Anaheim, CA, 2007, paper OWR7.

Sasaki, G.

W. Su, G. Sasaki, C. F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, no. 3–4, pp. 158–172, Dec. 2006.
[CrossRef]

Savoie, M.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, no. 2–3, pp. 107–122, June 2008.
[CrossRef]

J. Y. Zhang, O. Yang, J. Wu, M. Savoie, “Connection routing optimization in a semi-dynamic reconfigurable WDM network,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 3–17, Dec. 2007.
[CrossRef]

Y. Zhang, J. Wu, O. Yang, M. Savoie, “A Lagrangian-relaxation based network profit optimization for mesh SONET-over-WDM networks,” Photonic Network Commun., vol. 10, no. 2, pp. 155–178, Sept. 2005.
[CrossRef]

Shen, L.

L. Shen, X. Yang, A. Todimala, B. Ramamurthy, “A two-phase approach for dynamic lightpath scheduling in WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2007), Glasgow, UK, 2007, pp. 2412–2417.

X. Yang, L. Shen, A. Todimala, B. Ramamurthy, T. Lehman, “An efficient scheduling scheme for on-demand lightpath reservations in reconfigurable WDM optical networks,” in Optical Fiber Communication Conf. (OFC 2006), San Diego, CA, 2006, paper OTuN2.

Skorin-Kapov, N.

N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 2–15, Aug. 2006.

Song, S. H.

C. S. Sung, S. H. Song, “Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network,” J. Oper. Res. Soc., vol. 54, no. 1, pp. 72–82, Jan. 2003.
[CrossRef]

Su, C. F.

W. Su, G. Sasaki, C. F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, no. 3–4, pp. 158–172, Dec. 2006.
[CrossRef]

Su, W.

W. Su, G. Sasaki, C. F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, no. 3–4, pp. 158–172, Dec. 2006.
[CrossRef]

Sun, W.

Sung, C. S.

C. S. Sung, S. H. Song, “Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network,” J. Oper. Res. Soc., vol. 54, no. 1, pp. 72–82, Jan. 2003.
[CrossRef]

Tanwir, S.

S. Tanwir, L. Battestilli, H. Perros, G. Karmous-Edwards, “Dynamic scheduling of network resources with advance reservations in optical grids,” Int. J. Network Manage., vol. 18, no. 2, pp. 79–105, Mar. 2008.
[CrossRef]

Thakur, L. S.

B. Jin, P. B. Luh, L. S. Thakur, “An effective optimization-based algorithm for job shop scheduling with fixed-size transfer lots,” J. Manuf. Syst., vol. 18, no. 4, pp. 284–300, Aug. 1999.
[CrossRef]

Thompson, K.

K. Thompson, G. J. Miller, R. Wilder, “Wide-area Internet traffic patterns and characteristics,” IEEE Network, vol. 11, no. 6, pp. 10–23, Nov./Dec. 1997.
[CrossRef]

Tien, P.

S. S. W. Lee, M. C. Yuang, P. Tien, S. H. Lin, “A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1741–1751, Nov. 2004.
[CrossRef]

Todimala, A.

X. Yang, L. Shen, A. Todimala, B. Ramamurthy, T. Lehman, “An efficient scheduling scheme for on-demand lightpath reservations in reconfigurable WDM optical networks,” in Optical Fiber Communication Conf. (OFC 2006), San Diego, CA, 2006, paper OTuN2.

L. Shen, X. Yang, A. Todimala, B. Ramamurthy, “A two-phase approach for dynamic lightpath scheduling in WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2007), Glasgow, UK, 2007, pp. 2412–2417.

Tornatore, M.

M. Tornatore, C. Ou, J. Zhang, A. Pattavina, B. Mukherjee, “PHOTO: an efficient shared-path-protection strategy based on connection-holding-time awareness,” J. Lightwave Technol., vol. 23, no. 10, pp. 3138–3146, Oct. 2005.
[CrossRef]

D. Lucerna, M. Tornatore, B. Mukherjee, A. Pattavina, “Dynamic routing of connections with known duration in WDM networks,” in IEEE Global Communications Conf. (GLOBECOM 2009), Honolulu, HI, 2009.

D. Lucerna, A. Baruffaldi, M. Tornatore, A. Pattavina, “On the efficiency of dynamic routing of connections with known duration,” in IEEE Int. Conf. on Communications (ICC 2009), Dresden, Germany, 2009.

Tran, P. N.

P. N. Tran, U. Killat, “Dynamic reconfiguration of logical topology for WDM networks under traffic changes,” in IEEE Network Operations and Management Symp. (NOMS 2008), Salvador, Bahia, Brazil, 2008, pp. 279–286.

Wang, B.

B. Wang, T. Li, “Survivable scheduled service provisioning in WDM optical networks with iterative routing,” Opt. Switching Networking, vol. 7, no. 1, pp. 28–38, Jan. 2010.
[CrossRef]

T. Li, B. Wang, “Path-protection-based routing and wavelength assignment in wavelength-division multiplexing optical networks under a scheduled traffic model,” J. Opt. Netw., vol. 5, no. 7, pp. 575–588, July 2006.
[CrossRef]

B. Wang, A. Deshmukh, “An all hops optimal algorithm for dynamic routing of sliding scheduled traffic demands,” IEEE Commun. Lett., vol. 9, no. 10, pp. 936–938, Oct. 2005.
[CrossRef]

B. Wang, T. Li, X. Luo, Y. Fan, “Traffic grooming under a sliding scheduled traffic model in WDM optical networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004.

B. Wang, T. Li, X. Luo, Y. Fan, C. Xin, “On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 1, pp. 13–22.

T. Li, B. Wang, C. Xin, X. Zhang, “On survivable service provisioning in WDM optical networks under a scheduled traffic model,” IEEE Global Telecommunications Conf. (GLOBECOM 2005), vol. 4, St. Louis, MO, 2005, pp. 1904–1908.

Wang, T.

Wang, Y.

Wei, L. K.

C. V. Saradhi, L. K. Wei, M. Gurusamy, “Provisioning fault-tolerant scheduled lightpath demands in WDM mesh networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004, pp. 150–159.

Wei, W.

Wilder, R.

K. Thompson, G. J. Miller, R. Wilder, “Wide-area Internet traffic patterns and characteristics,” IEEE Network, vol. 11, no. 6, pp. 10–23, Nov./Dec. 1997.
[CrossRef]

Wu, J.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, no. 2–3, pp. 107–122, June 2008.
[CrossRef]

J. Y. Zhang, O. Yang, J. Wu, M. Savoie, “Connection routing optimization in a semi-dynamic reconfigurable WDM network,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 3–17, Dec. 2007.
[CrossRef]

Y. Zhang, J. Wu, O. Yang, M. Savoie, “A Lagrangian-relaxation based network profit optimization for mesh SONET-over-WDM networks,” Photonic Network Commun., vol. 10, no. 2, pp. 155–178, Sept. 2005.
[CrossRef]

Wu, M. Y.

Xin, C.

T. Li, B. Wang, C. Xin, X. Zhang, “On survivable service provisioning in WDM optical networks under a scheduled traffic model,” IEEE Global Telecommunications Conf. (GLOBECOM 2005), vol. 4, St. Louis, MO, 2005, pp. 1904–1908.

B. Wang, T. Li, X. Luo, Y. Fan, C. Xin, “On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 1, pp. 13–22.

Yamanaka, N.

Yang, J. S.

S. Park, J. S. Yang, Y. C. Bang, “On RWA algorithms for scheduled lightpath demands in wavelength division multiplexing networks,” Int. J. Comput. Sci. Network Secur., vol. 7, no. 3, pp. 144–150, Mar. 2007.

Yang, O.

J. Y. Zhang, O. Yang, J. Wu, M. Savoie, “Connection routing optimization in a semi-dynamic reconfigurable WDM network,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 3–17, Dec. 2007.
[CrossRef]

Y. Zhang, J. Wu, O. Yang, M. Savoie, “A Lagrangian-relaxation based network profit optimization for mesh SONET-over-WDM networks,” Photonic Network Commun., vol. 10, no. 2, pp. 155–178, Sept. 2005.
[CrossRef]

Y. Zhang, O. Yang, H. Liu, “A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1752–1765, Nov. 2004.
[CrossRef]

Yang, X.

X. Yang, L. Shen, A. Todimala, B. Ramamurthy, T. Lehman, “An efficient scheduling scheme for on-demand lightpath reservations in reconfigurable WDM optical networks,” in Optical Fiber Communication Conf. (OFC 2006), San Diego, CA, 2006, paper OTuN2.

L. Shen, X. Yang, A. Todimala, B. Ramamurthy, “A two-phase approach for dynamic lightpath scheduling in WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2007), Glasgow, UK, 2007, pp. 2412–2417.

Yen, H. H.

H. H. Yen, S. S. W. Lee, B. Mukherjee, “Traffic grooming and delay constrained multicast routing in IP over WDM networks,” in IEEE Int. Conf. on Communications (ICC 2008), Beijing, China, 2008, pp 5246–5251.

Youn, C. H.

K. Lee, L. Zhang, C. H. Youn, “An adaptive virtual topology reconfiguration policy in multi-wavelength optical Internet,” Eur. Trans Telecommun. Relat. Technol., vol. 14, no. 5, pp. 417–422, Dec. 2003.

Yu, X.

Yuang, M. C.

S. S. W. Lee, A. Chen, M. C. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photonic Network Commun., vol. 19, no. 1, pp. 103–109, Feb. 2010.
[CrossRef]

S. S. W. Lee, M. C. Yuang, P. Tien, S. H. Lin, “A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1741–1751, Nov. 2004.
[CrossRef]

Zhai, Q.

Zhang, J.

Zhang, J. Y.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, no. 2–3, pp. 107–122, June 2008.
[CrossRef]

J. Y. Zhang, O. Yang, J. Wu, M. Savoie, “Connection routing optimization in a semi-dynamic reconfigurable WDM network,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 3–17, Dec. 2007.
[CrossRef]

Zhang, L.

K. Lee, L. Zhang, C. H. Youn, “An adaptive virtual topology reconfiguration policy in multi-wavelength optical Internet,” Eur. Trans Telecommun. Relat. Technol., vol. 14, no. 5, pp. 417–422, Dec. 2003.

Zhang, T.

I. Chlamtac, A. Farago, T. Zhang, “Lightpath (wavelength) routing in large WDM networks,” IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 909–913, June 1996.
[CrossRef]

Zhang, X.

T. Li, B. Wang, C. Xin, X. Zhang, “On survivable service provisioning in WDM optical networks under a scheduled traffic model,” IEEE Global Telecommunications Conf. (GLOBECOM 2005), vol. 4, St. Louis, MO, 2005, pp. 1904–1908.

Zhang, Y.

Y. Zhang, J. Wu, O. Yang, M. Savoie, “A Lagrangian-relaxation based network profit optimization for mesh SONET-over-WDM networks,” Photonic Network Commun., vol. 10, no. 2, pp. 155–178, Sept. 2005.
[CrossRef]

Y. Zhang, O. Yang, H. Liu, “A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1752–1765, Nov. 2004.
[CrossRef]

Zheng, J.

J. Zheng, B. Zhou, H. T. Mouftah, “Toward automated provisioning of advance reservation service in next-generation optical Internet,” IEEE Commun. Mag., vol. 44, no. 12, pp. 68–74, Dec. 2006.
[CrossRef]

J. Zheng, H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2002), New York, NY, 2002, vol. 5, pp. 2722–2726.

Zhou, B.

J. Zheng, B. Zhou, H. T. Mouftah, “Toward automated provisioning of advance reservation service in next-generation optical Internet,” IEEE Commun. Mag., vol. 44, no. 12, pp. 68–74, Dec. 2006.
[CrossRef]

Zhou, L.

Comput. Netw.

S. Huang, R. Dutta, “Spare capacity provisioning for quasi-static traffic,” Comput. Netw., vol. 51, no. 18, pp. 5011–5035, Dec. 2007.
[CrossRef]

Eur. Trans Telecommun. Relat. Technol.

K. Lee, L. Zhang, C. H. Youn, “An adaptive virtual topology reconfiguration policy in multi-wavelength optical Internet,” Eur. Trans Telecommun. Relat. Technol., vol. 14, no. 5, pp. 417–422, Dec. 2003.

IEEE Commun. Lett.

B. Wang, A. Deshmukh, “An all hops optimal algorithm for dynamic routing of sliding scheduled traffic demands,” IEEE Commun. Lett., vol. 9, no. 10, pp. 936–938, Oct. 2005.
[CrossRef]

IEEE Commun. Mag.

J. Zheng, B. Zhou, H. T. Mouftah, “Toward automated provisioning of advance reservation service in next-generation optical Internet,” IEEE Commun. Mag., vol. 44, no. 12, pp. 68–74, Dec. 2006.
[CrossRef]

IEEE J. Sel. Areas Commun.

A. Narula-Tam, E. Modiano, “Dynamic load balancing in WDM packet networks with and without wavelength constraints,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1972–1979, Oct. 2000.
[CrossRef]

J. Y. Zhang, O. Yang, J. Wu, M. Savoie, “Connection routing optimization in a semi-dynamic reconfigurable WDM network,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 3–17, Dec. 2007.
[CrossRef]

I. Chlamtac, A. Farago, T. Zhang, “Lightpath (wavelength) routing in large WDM networks,” IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 909–913, June 1996.
[CrossRef]

N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 2–15, Aug. 2006.

J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, R. Douville, “Routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 1231–1240, Oct. 2003.
[CrossRef]

M. Gagnaire, M. Koubaa, N. Puech, “Network dimensioning under scheduled and random lightpath demands in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, pp. 58–67, Dec. 2007.
[CrossRef]

Y. Zhang, O. Yang, H. Liu, “A Lagrangean relaxation and subgradient framework for the routing and wavelength assignment problem in WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1752–1765, Nov. 2004.
[CrossRef]

M. Saad, Z. Luo, “On the routing and wavelength assignment in multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1708–1717, Nov. 2004.
[CrossRef]

S. S. W. Lee, M. C. Yuang, P. Tien, S. H. Lin, “A Lagrangean relaxation-based approach for routing and wavelength assignment in multigranularity optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1741–1751, Nov. 2004.
[CrossRef]

IEEE Network

K. Thompson, G. J. Miller, R. Wilder, “Wide-area Internet traffic patterns and characteristics,” IEEE Network, vol. 11, no. 6, pp. 10–23, Nov./Dec. 1997.
[CrossRef]

IEEE/ACM Trans. Netw.

A. Gencata, B. Mukherjee, “Virtual-topology adaptation for WDM mesh networks under dynamic traffic,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 236–247, Apr. 2003.
[CrossRef]

Int. J. Comput. Sci. Network Secur.

S. Park, J. S. Yang, Y. C. Bang, “On RWA algorithms for scheduled lightpath demands in wavelength division multiplexing networks,” Int. J. Comput. Sci. Network Secur., vol. 7, no. 3, pp. 144–150, Mar. 2007.

Int. J. Network Manage.

S. Tanwir, L. Battestilli, H. Perros, G. Karmous-Edwards, “Dynamic scheduling of network resources with advance reservations in optical grids,” Int. J. Network Manage., vol. 18, no. 2, pp. 79–105, Mar. 2008.
[CrossRef]

J. Lightwave Technol.

J. Manuf. Syst.

B. Jin, P. B. Luh, L. S. Thakur, “An effective optimization-based algorithm for job shop scheduling with fixed-size transfer lots,” J. Manuf. Syst., vol. 18, no. 4, pp. 284–300, Aug. 1999.
[CrossRef]

J. Oper. Res. Soc.

C. S. Sung, S. H. Song, “Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network,” J. Oper. Res. Soc., vol. 54, no. 1, pp. 72–82, Jan. 2003.
[CrossRef]

J. Opt. Netw.

Oper. Res.

K. Holmberg, J. Hellstrand, “Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound,” Oper. Res., vol. 46, no. 2, pp. 247–259, Mar.–Apr. 1998.
[CrossRef]

Opt. Switching Networking

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, no. 2–3, pp. 107–122, June 2008.
[CrossRef]

W. Su, G. Sasaki, C. F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, no. 3–4, pp. 158–172, Dec. 2006.
[CrossRef]

B. Wang, T. Li, “Survivable scheduled service provisioning in WDM optical networks with iterative routing,” Opt. Switching Networking, vol. 7, no. 1, pp. 28–38, Jan. 2010.
[CrossRef]

A. Jaekel, Y. Chen, “Resource provisioning for survivable WDM networks under a sliding scheduled traffic model,” Opt. Switching Networking, vol. 6, no. 1, pp. 44–54, Jan. 2009.
[CrossRef]

Photonic Network Commun.

Y. Zhang, J. Wu, O. Yang, M. Savoie, “A Lagrangian-relaxation based network profit optimization for mesh SONET-over-WDM networks,” Photonic Network Commun., vol. 10, no. 2, pp. 155–178, Sept. 2005.
[CrossRef]

S. S. W. Lee, A. Chen, M. C. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photonic Network Commun., vol. 19, no. 1, pp. 103–109, Feb. 2010.
[CrossRef]

Other

P. N. Tran, U. Killat, “Dynamic reconfiguration of logical topology for WDM networks under traffic changes,” in IEEE Network Operations and Management Symp. (NOMS 2008), Salvador, Bahia, Brazil, 2008, pp. 279–286.

J. Zheng, H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2002), New York, NY, 2002, vol. 5, pp. 2722–2726.

F. Ricciato, S. Salsano, A. Belmonte, M. Listanti, “Off-line configuration of a MPLS over WDM network under time-varying offered traffic,” in 21st Annu. Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2002), New York, NY, 2000, vol. 1, pp. 57–65.

A. Jaekel, “Lightpath scheduling and allocation under a flexible scheduled traffic model,” in IEEE Global Telecommunications Conf. (GLOBECOM 2006), San Francisco, CA, 2006.

B. Wang, T. Li, X. Luo, Y. Fan, C. Xin, “On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 1, pp. 13–22.

B. Wang, T. Li, X. Luo, Y. Fan, “Traffic grooming under a sliding scheduled traffic model in WDM optical networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004.

T. Li, B. Wang, C. Xin, X. Zhang, “On survivable service provisioning in WDM optical networks under a scheduled traffic model,” IEEE Global Telecommunications Conf. (GLOBECOM 2005), vol. 4, St. Louis, MO, 2005, pp. 1904–1908.

A. Jaekel, Y. Chen, “Routing and wavelength assignment for prioritized demands under a scheduled traffic model,” in 3rd Int. Conf. on Broadband Communications, Networks and Systems (BROADNETS 2006), San Jose, CA, 2006, pp. 1–7.

C. Saradhi, M. Gurusamy, “Graph theoretic approaches for routing and wavelength assignment of scheduled lightpath demands in WDM optical networks,” in 2nd Int. Conf. on Broadband Networks (BROADNETS 2005), Boston, MA, 2005, vol. 2, pp. 1291–1299.

C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Optical Fiber Communication Conf. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC 2007), Anaheim, CA, 2007, paper OWR7.

A. Chen, S. S. W. Lee, “A near-optimal heuristic algorithm for advance lightpath reservation in WDM networks,” in 34th European Conf. on Optical Communication (ECOC 2008), Brussels, Belgium, 2008, paper We.2.B.5.

J. Kuri, N. Puech, M. Gagnaire, “Diverse routing of scheduled lightpath demands in an optical transport network,” in 4th Int. Workshop on Design of Reliable Communication Networks (DCRN 2003), Banff, Alberta, Canada, 2003, pp. 69–76.

C. V. Saradhi, L. K. Wei, M. Gurusamy, “Provisioning fault-tolerant scheduled lightpath demands in WDM mesh networks,” in 1st Int. Conf. on Broadband Networks (BROADNETS 2004), San Jose, CA, 2004, pp. 150–159.

X. Yang, L. Shen, A. Todimala, B. Ramamurthy, T. Lehman, “An efficient scheduling scheme for on-demand lightpath reservations in reconfigurable WDM optical networks,” in Optical Fiber Communication Conf. (OFC 2006), San Diego, CA, 2006, paper OTuN2.

L. Shen, X. Yang, A. Todimala, B. Ramamurthy, “A two-phase approach for dynamic lightpath scheduling in WDM optical networks,” in IEEE Int. Conf. on Communications (ICC 2007), Glasgow, UK, 2007, pp. 2412–2417.

Z. K. G. Patrocinio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf. (GLOBECOM 2003), San Francisco, CA, 2003, vol. 5, pp. 2767–2771.

D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 1999.

D. Lucerna, M. Tornatore, B. Mukherjee, A. Pattavina, “Dynamic routing of connections with known duration in WDM networks,” in IEEE Global Communications Conf. (GLOBECOM 2009), Honolulu, HI, 2009.

D. Lucerna, A. Baruffaldi, M. Tornatore, A. Pattavina, “On the efficiency of dynamic routing of connections with known duration,” in IEEE Int. Conf. on Communications (ICC 2009), Dresden, Germany, 2009.

H. H. Yen, S. S. W. Lee, B. Mukherjee, “Traffic grooming and delay constrained multicast routing in IP over WDM networks,” in IEEE Int. Conf. on Communications (ICC 2008), Beijing, China, 2008, pp 5246–5251.

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 (14)

Fig. 1
Fig. 1

Shortage of effective service time caused by schedule earliness and tardiness.

Fig. 2
Fig. 2

Example of earliness and tardiness penalties reflecting a decreasing tolerance level as a scheduled lightpath moves away from its desired timing window.

Fig. 3
Fig. 3

Illustration of our solution framework and its relation to the mathematical model.

Fig. 4
Fig. 4

Application of the subgradient method in the dual space.

Fig. 5
Fig. 5

Updating the variables by using the subgradient method.

Fig. 6
Fig. 6

Flow chart of our heuristic algorithm to obtain a feasible scheduling and RWA solution.

Fig. 7
Fig. 7

Example network for performance evaluation (NSFNET with 14 nodes and 21 links).

Fig. 8
Fig. 8

Number of rejected SSLDs versus the earliness violations as y s d n varies.

Fig. 9
Fig. 9

Achieved optimization objective and its bound as y s d n varies.

Fig. 10
Fig. 10

Number of rejected SSLDs versus the tardiness violations as r s d n varies.

Fig. 11
Fig. 11

Achieved optimization objective and its bound as r s d n varies.

Fig. 12
Fig. 12

Impact of d i j on the average hop count.

Fig. 13
Fig. 13

Impact of d i j on the rejection of SSLDs.

Fig. 14
Fig. 14

Achieved optimization objective and its bound as d i j varies.

Tables (8)

Tables Icon

Table 1 Solution Methods for the Static Lightpath Scheduling Problems Where a Lightpath Must Start at its Specified Starting Time

Tables Icon

Table 2 Solution Methods for the Static Lightpath Scheduling Problems Where a Lightpath is Allowed to Slide Within Its Specified Time Window

Tables Icon

Table 3 Number of Constraints in Our Formulation

Tables Icon

Table 4 Computation Complexity for the Static Lightpath Scheduling Problems Where a Lightpath Must Start at Its Specified Starting Time

Tables Icon

Table 5 Number of SSLDs for All Node Pairs

Tables Icon

Table 6 Timing and Duration Requirements of SSLDs for All Node Pairs

Tables Icon

Table 7 Using Wavelength Conversion to Improve the Achieved Design Objective and to Reduce the Number of Rejected SSLDs

Tables Icon

Table 8 Computation Results Using Various Topologies and Traffic Matrices

Equations (35)

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

J l s d n L [ ( 1 α s d n ) P + α s d n ( C s d n + E s d n ) ] .
E s d n = { y s d n × ( b s d n β s d n ) 2 if β s d n < b s d n ( i.e. , earliness penalty ) 0 if b s d n β s d n b s d n ( i.e. , no penalty , since the lightpath starts within its desired starting time window ) r s d n × ( β s d n b s d n ) 2 if β s d n > b s d n ( i.e. , tardiness penalty ) } , l s d n L ,
C s d n = β s d n t < ( β s d n + t s d n ) ( d i j × e i j E 0 c < W δ i j c t s d n + o i × i V ϕ i t s d n ) , l s d n L .
j V 0 c < W δ i j c t s d n j V 0 c < W δ j i c t s d n = { α s d n if β s d n t < β s d n + t s d n , i = s α s d n if β s d n t < β s d n + t s d n , i = d 0 otherwise } ,
l s d n L , i V .
ϕ j t s d n = { 1 if ( m V , k V , b c ) , δ m j b t s d n = δ j k c t s d n = 1 0 otherwise } ,
l s d n L , j V , 0 t < Z .
l s d n L δ i j c t s d n 1 , e i j E , 0 c < W , 0 t < Z .
l s d n L ϕ j t s d n F j , j V , 0 t < Z .
δ i j c x s d n = δ i j c y s d n , l s d n L , e i j E , β s d n x < β s d n + t s d n , β s d n y < β s d n + t s d n
D s d n = min β s d n , Δ s d n , Φ s d n ( E s d n + e i j E 0 c < W β s d n t < β s d n + t s d n δ i j c t s d n ( ξ i j c t + d i j ) + i V β s d n t < β s d n + t s d n ϕ i t s d n ( π i t + o i ) ) ,
l s d n L .
l s d n L { min α s d n [ ( 1 α s d n ) P s d n + α s d n D s d n ] } ,
D s d n = min β s d n { E s d n + min Δ s d n , Φ s d n [ e i j E 0 c < W β s d n t < β s d n + t s d n δ i j c t s d n ( ξ i j c t + d i j ) + i V β s d n t < β s d n + t s d n ϕ i t s d n ( π i t + o i ) ] } l s d n L ,
min Δ s d n , Φ s d n [ e i j E 0 c < W β s d n t < β s d n + t s d n δ i j c t s d n ( ξ i j c t + d i j ) + i V β s d n t < β s d n + t s d n ϕ i t s d n ( π i t + o i ) ] .
ξ ̂ i j c β , T = β t < β + T ( ξ i j c , t + d i j ) , e i j E , 0 c < W ,
π ̂ i β , T = β t < β + T ( π i , t + o i ) , i V .
z ( h + 1 ) = z ( h ) + α ( h ) g ( z ( h ) ) ,
g ( ξ i j c t ) = l s d n L δ i j c t s d n 1 , e i j E , 0 c < W , 0 t < Z ,
g ( π i t ) = l s d n L ϕ i t s d n F i , j V , 0 t < Z .
α ( h ) = μ × q U q ( h ) g T ( z ( h ) ) g ( z ( h ) ) ,
δ ̂ i j c β , T = min β t < β + T ( 1 l s d n L δ i j c , t s d n ) , e i j E , 0 c < W ,
ϕ ̂ i β , T = min β t < β + T ( F i l s d n L ϕ i , t s d n ) , i V .
d ̂ i j β , T = β t < β + T d i j , e i j E .
o ̂ i β , T = β t < β + T o i , i V .
Sum of Earliness Violations ( SEV ) = l s d n L min { 0 , ( b s d n β s d n ) } ,
Sum of Tardiness Violations ( STV ) = l s d n L min { 0 , ( β s d n b s d n ) } .
max ξ , π 0 ( q ) = min A , B , Δ , Φ { l s d n L [ ( 1 α s d n ) P s d n + α s d n ( C s d n + E s d n ) ] + e i j E 0 c < W 0 t < Z ξ i j c t ( l s d n L δ i j c t s d n 1 ) + i V 0 t < Z π i t ( l s d n L ϕ i t s d n F i ) } ,
min A , B , Δ , Φ { l s d n L [ ( 1 α s d n ) P s d n + α s d n ( C s d n + E s d n ) + e i j E 0 c < W 0 t < Z δ i j c t s d n ξ i j c t + i V 0 t < Z π i t ϕ i t s d n ] e i j E 0 c < W 0 t < Z ξ i j c t i V 0 t < Z π i t F i } .
δ i j c t s d n = α s d n δ i j c t s d n , l s d n L , e i j E ,
0 c < W , 0 t < Z ,
ϕ i t s d n = α s d n ϕ i t s d n , l s d n L , j V , 0 t < Z .
min A , B , Δ , Φ { l s d n L [ ( 1 α s d n ) P s d n + α s d n ( C s d n + E s d n + e i j E 0 c < W 0 t < Z δ i j c t s d n ξ i j c t + i V 0 t < Z π i t ϕ i t s d n ) ] e i j E 0 c < W 0 t < Z ξ i j c t i V 0 t < Z π i t F i } .
min A , B , Δ , Φ { l s d n L [ ( 1 α s d n ) P s d n + α s d n ( C s d n + E s d n + e i j E 0 c < W 0 t < Z δ i j c t s d n ξ i j c t + i V 0 t < Z π i t ϕ i t s d n ) ] } ,
min A { l s d n L [ ( 1 α s d n ) P s d n + α s d n min β s d n , Δ s d n , Φ s d n ( E s d n + e i j E 0 c < W β s d n t < β s d n + t s d n δ i j c t s d n ( ξ i j c t + d i j ) + i V β s d n t < β s d n + t s d n ϕ i t s d n ( π i t + o i ) ) ] } .