OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and V. Chan
  • Vol. 2, Iss. 10 — Oct. 1, 2010
  • pp: 803–819

Lightpath Scheduling and Routing for Traffic Adaptation in WDM Networks

James Yiming Zhang, Hussein Mouftah, Jing Wu, and Michel Savoie  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 2, Issue 10, pp. 803-819 (2010)
http://dx.doi.org/10.1364/JOCN.2.000803


View Full Text Article

Acrobat PDF (1545 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

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

ToC Category:
Research Papers

History
Original Manuscript: April 13, 2010
Revised Manuscript: August 2, 2010
Manuscript Accepted: August 11, 2010
Published: September 29, 2010

Citation
James Yiming Zhang, Hussein Mouftah, Jing Wu, and Michel Savoie, "Lightpath Scheduling and Routing for Traffic Adaptation in WDM Networks," J. Opt. Commun. Netw. 2, 803-819 (2010)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-2-10-803


Sort:  Author  |  Year  |  Journal  |  Reset

References

  1. A. Gencata and 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, and 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, and 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, and 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, and 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, and 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 and 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 and 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, and 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 and 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 and 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, and 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 and 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, and 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 and 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, and 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, and 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, and 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 and 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, and 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, and 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, and 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, and 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, and 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, and 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, and 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, and 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, and 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, and 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 and 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 and 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, and 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 and 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 and 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, and 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, and 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 and R. Dutta, “Spare capacity provisioning for quasi-static traffic,” Comput. Netw. , vol. 51, no. 18, pp. 5011–5035, Dec. 2007. [CrossRef]
  40. I. Chlamtac and 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, and 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, and 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, and 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, and 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.
  45. B. Jin, P. B. Luh, and 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, and 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 and 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, and 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, and 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, and 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 and 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 and 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, Jr., and 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.

Cited By

Alert me when this paper is cited

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

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited