Abstract

Many future Internet applications supported over optical networks may require large amounts of guaranteed bandwidth between two remote end hosts, but this bandwidth may not necessarily be needed immediately. To ensure a deterministic service, Internet customers may prefer to reserve network resources, e.g., lightpaths, in advance and may indicate an approximate time window in the future during which the bandwidth should be reserved for a certain period of time; however, the exact start time of the reservation is not specified, but can slide in the predefined time window. This type of user traffic is called “sliding scheduled traffic.” Optical network design for provisioning sliding scheduled traffic is a highly complex task that has been dealt with in the literature by two-step approaches, which first schedule user demands in time and then perform their routing and wavelength assignment (RWA). We propose a scalable integrated design for the sliding scheduling provisioning problem (SSPP), based on the Lagrangean relaxation (LR) approach, which can jointly perform the scheduling and RWA of the demands. We first develop a new mathematical model for SSPP, to which it is suitable to apply the relaxation of some of the model’s constraints. We use an integrated heuristic called IPSR (integrated provisioning of sliding requests), which is next enhanced with a cost assignment based on Lagrangean multiplier information, to serve as the primal algorithm for our LR approach (named IPSR-LR). We compare our approaches with an existing two-step heuristic algorithm for SSPP and show that both IPSR and IPSR-LR are able to outperform it. In addition, our numerical results show that IPSR-LR improves over IPSR under all typical experimental cases that we considered. Furthermore, we compare our approaches with the solutions provided by an integer linear program for the SSPP, which is, however, less scalable for large problem sizes compared with our algorithms.

© 2009 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. 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 2007. ICC ’07, Glasgow, Scotland, June 24–28, 2007, pp. 2412–2417.
  2. 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, 2005. BroadNets 2005, Boston, MA, Oct. 3–7, 2005, vol. 1, pp. 13–22.
  3. H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.
  4. B. Mukherjee, Optical WDM Networks, New York, NY: Springer Science+Business Media, Jan. 13, 2006.
  5. 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]
  6. L.-O. Burchard, H.-U. Heiss, C. De Rose, “Performance issues of bandwidth reservation for grid computing,” in Proc. 15th Symp. Computer Architecture and High Performance Computing 2003, Nov. 10–12, 2003, pp. 82–90.
  7. European Organization for Nuclear Research (CERN), www.cern.ch/.
  8. OptIPuter, http://www.optiputer.net/, 2008.
  9. R. Ahuja, T. Magnanti, J. Orlin, Network Flows—Theory, Algorithms, and Applications, Upper Saddle River, NJ: Prentice Hall, 1993.
  10. A. Jaekel, Y. Chen, “Demand allocation without wavelength conversion under a sliding scheduled traffic model,” in 4th Int. Conf. on Broadband Communications, Networks and Systems, 2007. BROADNETS 2007, Raleigh, NC, Sept. 10–14, 2007, pp. 495–503.
  11. C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Conf. on Optical Fiber Communication and Nat. Fiber Optic Engineers Conf., 2007. OFC/NFOEC 2007, Anaheim, CA, March 25–29, 2007, pp. 1–3.
  12. D. Andrei, M. Tornatore, D. Ghosal, C. Martel, B. Mukherjee, “On-demand provisioning of data-aggregation requests over WDM mesh networks,” in IEEE Global Telecommunications Conf., 2008. IEEE GLOBECOM 2008, New Orleans, LA, Nov. 30–Dec. 4, 2008, pp. 1–5.
  13. R. A. Guerin, A. Orda, “Networks with advance reservations: the routing perspective,” in Proc. IEEE INFOCOM 2000. 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Tel Aviv, Israel, March 26–30, 2000, vol. 1, pp. 118–127.
  14. J. Zheng, H. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications, ICC 2002, Apr. 28–May 2, 2002, vol. 5, pp. 2722–2726.
  15. C. V. Saradhi, M. Gurusamy, R. Piesiewicz, “Routing fault-tolerant sliding scheduled traffic in WDM optical mesh networks,” in 5th Int. Conf. on Broadband Communications, Networks and Systems, 2008. BROADNETS 2008, London, Sept. 8–11, 2008, pp. 197–202.
    [CrossRef]
  16. A. Jaekel, “Lightpath scheduling and allocation under a flexible scheduled traffic model,” in IEEE Global Telecommunications Conf., 2006. GLOBECOM '06, San Francisco, CA, Nov. 27–Dec. 1, 2006, pp. 1–5.
  17. W. Su, G. Sasaki, C.-F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, pp. 158–172, Dec. 2006.
    [CrossRef]
  18. H. H. Yen, F. Y. Lin, “Near-optimal tree-based access network design,” Comput. Commun., vol. 28, pp. 236–245, Feb. 2005.
    [CrossRef]
  19. J. Yen, “Finding the K shortest loopless paths in a network,” Manage. Sci., vol. 17, no. 11, pp. 712–716, July 1971.
    [CrossRef]
  20. ILOG CPLEX version 9.0, http://www.ilog.com/products/cplex/.
  21. D. Andrei, H. H. Yen, M. Tornatore, “Integrated design for sliding scheduled traffic in WDM networks,” in Optical Fiber Communication Conf., OSA Technical Digest (CD), San Diego, CA, March 22–26, 2009, Washington, DC: Optical Society of America, 2009, paper OThO5.

2006

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

2005

H. H. Yen, F. Y. Lin, “Near-optimal tree-based access network design,” Comput. Commun., vol. 28, pp. 236–245, Feb. 2005.
[CrossRef]

2003

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]

2000

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

1971

J. Yen, “Finding the K shortest loopless paths in a network,” Manage. Sci., vol. 17, no. 11, pp. 712–716, July 1971.
[CrossRef]

Ahuja, R.

R. Ahuja, T. Magnanti, J. Orlin, Network Flows—Theory, Algorithms, and Applications, Upper Saddle River, NJ: Prentice Hall, 1993.

Andrei, D.

D. Andrei, M. Tornatore, D. Ghosal, C. Martel, B. Mukherjee, “On-demand provisioning of data-aggregation requests over WDM mesh networks,” in IEEE Global Telecommunications Conf., 2008. IEEE GLOBECOM 2008, New Orleans, LA, Nov. 30–Dec. 4, 2008, pp. 1–5.

D. Andrei, H. H. Yen, M. Tornatore, “Integrated design for sliding scheduled traffic in WDM networks,” in Optical Fiber Communication Conf., OSA Technical Digest (CD), San Diego, CA, March 22–26, 2009, Washington, DC: Optical Society of America, 2009, paper OThO5.

Balasubramanian, A.

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

Burchard, L.-O.

L.-O. Burchard, H.-U. Heiss, C. De Rose, “Performance issues of bandwidth reservation for grid computing,” in Proc. 15th Symp. Computer Architecture and High Performance Computing 2003, Nov. 10–12, 2003, pp. 82–90.

Chen, Y.

A. Jaekel, Y. Chen, “Demand allocation without wavelength conversion under a sliding scheduled traffic model,” in 4th Int. Conf. on Broadband Communications, Networks and Systems, 2007. BROADNETS 2007, Raleigh, NC, Sept. 10–14, 2007, pp. 495–503.

De Rose, C.

L.-O. Burchard, H.-U. Heiss, C. De Rose, “Performance issues of bandwidth reservation for grid computing,” in Proc. 15th Symp. Computer Architecture and High Performance Computing 2003, Nov. 10–12, 2003, pp. 82–90.

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]

Fan, Y.

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, 2005. BroadNets 2005, Boston, MA, Oct. 3–7, 2005, vol. 1, pp. 13–22.

Gagnaire, M.

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]

Ghosal, D.

D. Andrei, M. Tornatore, D. Ghosal, C. Martel, B. Mukherjee, “On-demand provisioning of data-aggregation requests over WDM mesh networks,” in IEEE Global Telecommunications Conf., 2008. IEEE GLOBECOM 2008, New Orleans, LA, Nov. 30–Dec. 4, 2008, pp. 1–5.

Guerin, R. A.

R. A. Guerin, A. Orda, “Networks with advance reservations: the routing perspective,” in Proc. IEEE INFOCOM 2000. 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Tel Aviv, Israel, March 26–30, 2000, vol. 1, pp. 118–127.

Gurusamy, M.

C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Conf. on Optical Fiber Communication and Nat. Fiber Optic Engineers Conf., 2007. OFC/NFOEC 2007, Anaheim, CA, March 25–29, 2007, pp. 1–3.

C. V. Saradhi, M. Gurusamy, R. Piesiewicz, “Routing fault-tolerant sliding scheduled traffic in WDM optical mesh networks,” in 5th Int. Conf. on Broadband Communications, Networks and Systems, 2008. BROADNETS 2008, London, Sept. 8–11, 2008, pp. 197–202.
[CrossRef]

Heiss, H.-U.

L.-O. Burchard, H.-U. Heiss, C. De Rose, “Performance issues of bandwidth reservation for grid computing,” in Proc. 15th Symp. Computer Architecture and High Performance Computing 2003, Nov. 10–12, 2003, pp. 82–90.

Jaekel, A.

A. Jaekel, Y. Chen, “Demand allocation without wavelength conversion under a sliding scheduled traffic model,” in 4th Int. Conf. on Broadband Communications, Networks and Systems, 2007. BROADNETS 2007, Raleigh, NC, Sept. 10–14, 2007, pp. 495–503.

A. Jaekel, “Lightpath scheduling and allocation under a flexible scheduled traffic model,” in IEEE Global Telecommunications Conf., 2006. GLOBECOM '06, San Francisco, CA, Nov. 27–Dec. 1, 2006, pp. 1–5.

Jue, J.

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

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]

Li, T.

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, 2005. BroadNets 2005, Boston, MA, Oct. 3–7, 2005, vol. 1, pp. 13–22.

Lin, F. Y.

H. H. Yen, F. Y. Lin, “Near-optimal tree-based access network design,” Comput. Commun., vol. 28, pp. 236–245, Feb. 2005.
[CrossRef]

Luo, X.

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, 2005. BroadNets 2005, Boston, MA, Oct. 3–7, 2005, vol. 1, pp. 13–22.

Magnanti, T.

R. Ahuja, T. Magnanti, J. Orlin, Network Flows—Theory, Algorithms, and Applications, Upper Saddle River, NJ: Prentice Hall, 1993.

Martel, C.

D. Andrei, M. Tornatore, D. Ghosal, C. Martel, B. Mukherjee, “On-demand provisioning of data-aggregation requests over WDM mesh networks,” in IEEE Global Telecommunications Conf., 2008. IEEE GLOBECOM 2008, New Orleans, LA, Nov. 30–Dec. 4, 2008, pp. 1–5.

Mouftah, H.

J. Zheng, H. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications, ICC 2002, Apr. 28–May 2, 2002, vol. 5, pp. 2722–2726.

Mukherjee, B.

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

D. Andrei, M. Tornatore, D. Ghosal, C. Martel, B. Mukherjee, “On-demand provisioning of data-aggregation requests over WDM mesh networks,” in IEEE Global Telecommunications Conf., 2008. IEEE GLOBECOM 2008, New Orleans, LA, Nov. 30–Dec. 4, 2008, pp. 1–5.

B. Mukherjee, Optical WDM Networks, New York, NY: Springer Science+Business Media, Jan. 13, 2006.

Orda, A.

R. A. Guerin, A. Orda, “Networks with advance reservations: the routing perspective,” in Proc. IEEE INFOCOM 2000. 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Tel Aviv, Israel, March 26–30, 2000, vol. 1, pp. 118–127.

Orlin, J.

R. Ahuja, T. Magnanti, J. Orlin, Network Flows—Theory, Algorithms, and Applications, Upper Saddle River, NJ: Prentice Hall, 1993.

Piesiewicz, R.

C. V. Saradhi, M. Gurusamy, R. Piesiewicz, “Routing fault-tolerant sliding scheduled traffic in WDM optical mesh networks,” in 5th Int. Conf. on Broadband Communications, Networks and Systems, 2008. BROADNETS 2008, London, Sept. 8–11, 2008, pp. 197–202.
[CrossRef]

Puech, N.

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]

Ramamurthy, B.

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 2007. ICC ’07, Glasgow, Scotland, June 24–28, 2007, pp. 2412–2417.

Saradhi, C. V.

C. V. Saradhi, M. Gurusamy, R. Piesiewicz, “Routing fault-tolerant sliding scheduled traffic in WDM optical mesh networks,” in 5th Int. Conf. on Broadband Communications, Networks and Systems, 2008. BROADNETS 2008, London, Sept. 8–11, 2008, pp. 197–202.
[CrossRef]

C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Conf. on Optical Fiber Communication and Nat. Fiber Optic Engineers Conf., 2007. OFC/NFOEC 2007, Anaheim, CA, March 25–29, 2007, pp. 1–3.

Sasaki, G.

W. Su, G. Sasaki, C.-F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, pp. 158–172, Dec. 2006.
[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 2007. ICC ’07, Glasgow, Scotland, June 24–28, 2007, pp. 2412–2417.

Su, C.-F.

W. Su, G. Sasaki, C.-F. Su, A. Balasubramanian, “Scheduling of periodic connections with flexibility,” Opt. Switching Networking, vol. 3, 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, pp. 158–172, Dec. 2006.
[CrossRef]

Todimala, A.

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 2007. ICC ’07, Glasgow, Scotland, June 24–28, 2007, pp. 2412–2417.

Tornatore, M.

D. Andrei, H. H. Yen, M. Tornatore, “Integrated design for sliding scheduled traffic in WDM networks,” in Optical Fiber Communication Conf., OSA Technical Digest (CD), San Diego, CA, March 22–26, 2009, Washington, DC: Optical Society of America, 2009, paper OThO5.

D. Andrei, M. Tornatore, D. Ghosal, C. Martel, B. Mukherjee, “On-demand provisioning of data-aggregation requests over WDM mesh networks,” in IEEE Global Telecommunications Conf., 2008. IEEE GLOBECOM 2008, New Orleans, LA, Nov. 30–Dec. 4, 2008, pp. 1–5.

Wang, B.

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, 2005. BroadNets 2005, Boston, MA, Oct. 3–7, 2005, vol. 1, pp. 13–22.

Xin, C.

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, 2005. BroadNets 2005, Boston, MA, Oct. 3–7, 2005, vol. 1, pp. 13–22.

Yang, X.

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 2007. ICC ’07, Glasgow, Scotland, June 24–28, 2007, pp. 2412–2417.

Yen, H. H.

H. H. Yen, F. Y. Lin, “Near-optimal tree-based access network design,” Comput. Commun., vol. 28, pp. 236–245, Feb. 2005.
[CrossRef]

D. Andrei, H. H. Yen, M. Tornatore, “Integrated design for sliding scheduled traffic in WDM networks,” in Optical Fiber Communication Conf., OSA Technical Digest (CD), San Diego, CA, March 22–26, 2009, Washington, DC: Optical Society of America, 2009, paper OThO5.

Yen, J.

J. Yen, “Finding the K shortest loopless paths in a network,” Manage. Sci., vol. 17, no. 11, pp. 712–716, July 1971.
[CrossRef]

Zang, H.

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

Zheng, J.

J. Zheng, H. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications, ICC 2002, Apr. 28–May 2, 2002, vol. 5, pp. 2722–2726.

Comput. Commun.

H. H. Yen, F. Y. Lin, “Near-optimal tree-based access network design,” Comput. Commun., vol. 28, pp. 236–245, Feb. 2005.
[CrossRef]

IEEE J. Sel. Areas Commun.

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]

Manage. Sci.

J. Yen, “Finding the K shortest loopless paths in a network,” Manage. Sci., vol. 17, no. 11, pp. 712–716, July 1971.
[CrossRef]

Opt. Networks Mag.

H. Zang, J. Jue, B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 47–60, Jan. 2000.

Opt. Switching Networking

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

Other

B. Mukherjee, Optical WDM Networks, New York, NY: Springer Science+Business Media, Jan. 13, 2006.

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 2007. ICC ’07, Glasgow, Scotland, June 24–28, 2007, pp. 2412–2417.

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, 2005. BroadNets 2005, Boston, MA, Oct. 3–7, 2005, vol. 1, pp. 13–22.

ILOG CPLEX version 9.0, http://www.ilog.com/products/cplex/.

D. Andrei, H. H. Yen, M. Tornatore, “Integrated design for sliding scheduled traffic in WDM networks,” in Optical Fiber Communication Conf., OSA Technical Digest (CD), San Diego, CA, March 22–26, 2009, Washington, DC: Optical Society of America, 2009, paper OThO5.

L.-O. Burchard, H.-U. Heiss, C. De Rose, “Performance issues of bandwidth reservation for grid computing,” in Proc. 15th Symp. Computer Architecture and High Performance Computing 2003, Nov. 10–12, 2003, pp. 82–90.

European Organization for Nuclear Research (CERN), www.cern.ch/.

OptIPuter, http://www.optiputer.net/, 2008.

R. Ahuja, T. Magnanti, J. Orlin, Network Flows—Theory, Algorithms, and Applications, Upper Saddle River, NJ: Prentice Hall, 1993.

A. Jaekel, Y. Chen, “Demand allocation without wavelength conversion under a sliding scheduled traffic model,” in 4th Int. Conf. on Broadband Communications, Networks and Systems, 2007. BROADNETS 2007, Raleigh, NC, Sept. 10–14, 2007, pp. 495–503.

C. V. Saradhi, M. Gurusamy, “Scheduling and routing of sliding scheduled lightpath demands in WDM optical networks,” in Conf. on Optical Fiber Communication and Nat. Fiber Optic Engineers Conf., 2007. OFC/NFOEC 2007, Anaheim, CA, March 25–29, 2007, pp. 1–3.

D. Andrei, M. Tornatore, D. Ghosal, C. Martel, B. Mukherjee, “On-demand provisioning of data-aggregation requests over WDM mesh networks,” in IEEE Global Telecommunications Conf., 2008. IEEE GLOBECOM 2008, New Orleans, LA, Nov. 30–Dec. 4, 2008, pp. 1–5.

R. A. Guerin, A. Orda, “Networks with advance reservations: the routing perspective,” in Proc. IEEE INFOCOM 2000. 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Tel Aviv, Israel, March 26–30, 2000, vol. 1, pp. 118–127.

J. Zheng, H. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in IEEE Int. Conf. on Communications, ICC 2002, Apr. 28–May 2, 2002, vol. 5, pp. 2722–2726.

C. V. Saradhi, M. Gurusamy, R. Piesiewicz, “Routing fault-tolerant sliding scheduled traffic in WDM optical mesh networks,” in 5th Int. Conf. on Broadband Communications, Networks and Systems, 2008. BROADNETS 2008, London, Sept. 8–11, 2008, pp. 197–202.
[CrossRef]

A. Jaekel, “Lightpath scheduling and allocation under a flexible scheduled traffic model,” in IEEE Global Telecommunications Conf., 2006. GLOBECOM '06, San Francisco, CA, Nov. 27–Dec. 1, 2006, pp. 1–5.

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

Fig. 1
Fig. 1

14-node U.S. nationwide topology.

Fig. 2
Fig. 2

24-node carrier topology.

Fig. 3
Fig. 3

Comparison between our approaches and SSLDP, for W = 8 .

Fig. 4
Fig. 4

Our approaches compared with SSLDP, for W = 16 .

Fig. 5
Fig. 5

Influence of the number of alternative paths K on the performance of IPSR and IPSR-LR.

Fig. 6
Fig. 6

Impact of the sorting policy on the number of SSRs provisioned by IPSR-LR.

Fig. 7
Fig. 7

Optimizing total provisioned bandwidth.

Fig. 8
Fig. 8

Performance of our approaches using topology in Fig. 2.

Fig. 9
Fig. 9

Nine-node reduced version of the network in Fig. 1.

Fig. 10
Fig. 10

Comparison between our planning approaches and ILP.

Tables (2)

Tables Icon

Table 1 Algorithm 1: Integrated Provisioning of Sliding Requests (IPSR) Algorithm

Tables Icon

Table 2 Algorithm 2: IPSR-LR Algorithm

Equations (29)

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

Z IP = Max i R A i = ( Min i R A i ) .
i R y i l j t i k 1 l L , j J , k K ,
p P i x p j δ p l y i l j i R , l L , j J ,
p P i p i j J x p j = 1 i R ,
A i p P i j J x p j i R ,
α i k θ i S i k = A i i R ,
α i k θ i 0 q < H i S i k t i k + q = A i H i i R ,
t i k = 0 k < α i , i R ,
t i k = 0 k > θ i , i R ,
y i l j = 0 1 i R , l L , j J ,
t i k = 0 1 i R , k K ,
x p j = 0 1 p P i , i R , j J ,
A i = 0 1 i R ,
S i k = 0 1 k K , i R .
Z LR ( μ ) = Min { i R A i + l L j J k K μ l j k 1 ( i R y i l j t i k 1 ) + i R l L j J μ i l j 2 ( p P i x p j δ p l y i l j ) + i R μ i 3 ( A i p P i j J x p j ) } ,
Subproblem 1: Min { i R p P i l L j J μ i l j 2 x p j δ p l i R p P i j J μ i 3 x p j } ,
Subproblem 2: Min { i R ( μ i 3 1 ) A i + l L j J k K i R μ l j k 1 y i l j t i k i R l L j J μ i l j 2 y i l j } ,
Subproblem 1.1: Min { p P i l L j J μ i l j 2 x p j δ p l p P i j J μ i 3 x p j } ,
p P i p i j j x p j = 1 and
x p j = 0 1 p P i , j j .
Subproblem 2.1: Min { ( μ i 3 1 ) A i + l L j J k K μ l j k 1 y i l j t i k l L j J μ i l j 2 y i l j } ,
α i k θ i S i k = A i ,
α i k θ i 0 q < H i S i k t i k + q = A i H i ,
t i k = 0 k < α i ,
t i k = 0 k > θ i ,
y i l j = 0 1 l L , j J ,
t i k = 0 1 k K ,
A i = 0 1 ,
S i k = 0 1 k K .