Abstract

Various static resource allocation algorithms have been used in WDM networks to allocate resources such as wavelength channels, transmitters, receivers, and wavelength converters to a given set of static lightpath demands. However, although optimized resource allocations can be obtained, it remains an open issue how to determine which resources are the bottlenecks in achieving better performance. Existing static resource allocation algorithms do not explicitly measure the impact of changes of network resources or lightpath demands on the design objective. We propose such a measurement based on the Lagrangian relaxation framework. We use the optimized values of Lagrange multipliers as a direct measurement of the criticality of resources. Such a quantitative measurement can be naturally acquired along with the optimization process to obtain the optimal solution (or a near-optimal solution) to the static routing and wavelength assignment problem. We investigate three practical applications of the resource criticality (RC) analysis in WDM network planning. In the first application, we use our proposed measurement to identify critical resources and thus to decide the best way to add or reallocate resources. In the second application, we estimate the impact of the addition or removal of lightpath demands on the design objective. This kind of estimation helps to set a proper price for lightpath demands. In the third application, the results of the RC analysis are used to speed up the convergence of the optimization process for different network scenarios.

© 2009 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. H. Zang, J. P. Jue, B. Mukherjee, “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.
  2. R. Dutta, G. N. Rouskas, “Survey of virtual topology design algorithm for wavelength-routed optical networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 73–89, Jan. 2000.
  3. 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]
  4. T. F. Noronha, C. C. Ribeiro, “Routing and wavelength assignment by partition colouring,” Concr. Library Int., vol. 171, no. 3, pp. 797–810, June 2006.
  5. N. Skorin-Kapov, “Routing and wavelength assignment in optical networks using bin packing based algorithms,” Concr. Library Int., vol. 177, no. 2, pp. 1167–1179, March 2007.
  6. H. Choo, V. V. Shakhov, B. Mukherjee, “Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths,” Photonic Network Commun., vol. 12, no. 2, pp. 145–152, Sept. 2006.
    [CrossRef]
  7. Y. Wang, T. H. Cheng, M. H. Lim, “A Tabu search algorithm for static routing and wavelength assignment problem,” IEEE Commun. Lett., vol. 9, no. 9, pp. 841–843, Sept. 2005.
    [CrossRef]
  8. L. D. Belgacem, N. Puech, “Solving large size instances of the RWA problem using graph partitioning,” in Int. Conf. on Optical Network Design and Modeling 2008. ONDM 2008, Vilanova ila Geltrú, Spain, March 12–14, 2008, pp. 1–6.
  9. S. Antonakopoulos, L. Zhang, “Heuristics for fiber installation in optical network optimization,” in IEEE Global Telecommunications Conf., 2000. GLOBECOM ’07, Washington, DC, Nov. 26–30, 2007, pp. 2342–2347.
  10. M. A. Ezzahdi, S. A. Zahr, M. Koubàa, N. Puech, M. Gagnaire, “LERP: a quality of transmission dependent heuristic for routing and wavelength assignment in hybrid WDM networks,” 15th Int. Conf. Computer Communications and Networks, 2006. ICCCN 2006, Proceedings, Arlington, VA, Oct. 9–11, 2006, pp. 125–136.
  11. B. Jaumard, C. Meyer, B. Thiongane, “Comparison of ILP formulations for the RWA problem,” Opt. Switching Networking, vol. 4, nos. 3–4, pp. 157–172, Nov. 2007.
    [CrossRef]
  12. A. Jukan, G. Franzl, “Path selection methods with multiple constraints in service-guaranteed WDM networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 59–72, Feb. 2004.
    [CrossRef]
  13. S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, no. 1, pp. 39–48, Jan. 2006.
    [CrossRef]
  14. A. Elwalid, D. Mitra, I. Saniee, I. Widjaja, “Routing and protection in GMPLS networks: from shortest paths to optimized designs,” J. Lightwave Technol., vol. 21, no. 11, pp. 2828–2838, Nov. 2003.
    [CrossRef]
  15. A. E. Ozdaglar, D. P. Bertsakas, “Routing and wavelength assignment in optical networks,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 259–272, Apr. 2003.
    [CrossRef]
  16. A. Zapata-Beghelli, P. Bayvel, “Dynamic versus static wavelength-routed optical networks,” J. Lightwave Technol., vol. 26, no. 20, pp. 3403–3415, Oct. 2008.
    [CrossRef]
  17. X. Chu, B. Li, “Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 704–715, June 2005.
    [CrossRef]
  18. T. Matsumoto, T. Takenaka, “Overlap degree aware routing in all-optical routing networks,” IEICE Trans. Commun., vol. E91-B, no. 1, pp. 212–220, Jan. 2008.
    [CrossRef]
  19. S. Kim, X. J. Zhang, S. S. Lumetta, “Rapid and efficient protection for all-optical WDM mesh networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, Suppl., pp. 68–82, Dec. 2007.
    [CrossRef]
  20. M. Gagnaire, M. Koubàa, N. Puech, “Network dimensioning under scheduled and random lightpath demands in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, Suppl., pp. 58–67, Dec. 2007.
    [CrossRef]
  21. G. Shen, W. D. Grover, “Dynamic path-protected service provisioning in optical transport networks with a limited number of add/drop ports and transmitter tenability,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, Suppl., pp. 121–134, Aug. 2007.
    [CrossRef]
  22. M. Kodialam, T. V. Lakshman, “Minimum interference routing with applications to MPLS traffic engineering,” in IEEE INFOCOM 2000, 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Tel Aviv, Israel, March 26–30, 2000, vol. 2, pp. 884–893.
  23. M. Kodialam, T. V. Lakshman, “Integrated dynamic IP and wavelength routing in IP over WDM networks,” in IEEE INFOCOM 2001, 20th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Anchorage, AK, Apr. 22–26, 2001, vol. 1, pp. 358–366.
  24. P. H. Ho, H. T. Mouftah, “A novel distributed control protocol in dynamic wavelength-routed optical networks,” IEEE Commun. Mag., vol. 40, no. 11, pp. 38–45, Nov. 2002.
    [CrossRef]
  25. F. Palmieri, U. Fiore, S. Ricciardi, “A minimum cut interference-based integrated RWA algorithm for multi-constrained optical transport networks,” J. Network Syst. Manage., vol. 16, no. 4, pp. 421–448, Dec. 2008.
    [CrossRef]
  26. J. S. Kim, D. C. Lee, H. Sridhar, “Route-metric-based dynamic routing and wavelength assignment for multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 12, Suppl., pp. 56–68, Dec. 2006.
    [CrossRef]
  27. K. Mosharaf, J. Talim, I. Lambadaris, “Optimal resource allocation and fairness control in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1496–1507, Aug. 2005.
    [CrossRef]
  28. S. S. W. Lee, M. C. Yuang, P. L. Tien, “A Lagrangean relaxation approach to routing and wavelength assignment for multi-granularity optical WDM networks,” in IEEE Global Telecommunications Conference 2004. GLOBECOM ’04, Dallas, TX, Nov. 29–Dec. 3, 2004, vol. 3, pp. 1936–1942.
  29. P. B. Luh, D. J. Hoitomt, E. Max, K. R. Pattipati, “Schedule generation and reconfiguration for parallel machines,” IEEE Trans. Rob. Autom., vol. 6, no. 6, pp. 687–696, Dec. 1990.
    [CrossRef]
  30. A. Lucena, “Lagrangian relax-and-cut algorithms,” in Handbook of Optimization in Telecommunications, M. G. C. Resende and P. M. Pardalos, eds., New York, NY: Springer Science and Business Media, 2006, pp. 129–146.
    [CrossRef]
  31. D. G. Luenberger, Y. Ye, Linear and Nonlinear Programming, 3rd ed., New York, NY: Springer, 2008.
  32. J. Y. Zhang, J. Wu, G. Bochmann, M. Savoie, “Grade-of-service differentiated static resource allocation schemes in WDM networks,” Opt. Switching Networking, vol. 5, nos. 2/3, pp. 107–122, June 2008.
    [CrossRef]
  33. D. P. Bertsekas, Nonlinear Programming, 2nd ed., Belmont, MA: Athena Scientific, 1999.
  34. 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]
  35. J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “A proof of wavelength conversion not improving the Lagrangian bound of the static RWA problem,” IEEE Commun. Lett., vol. 13, no. 5, pp. 345–347, May 2009.
    [CrossRef]
  36. E. Bouillet, J. F. Labourdette, R. Ramamurthy, S. Chaudhuri, “Lightpath re-optimization in mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 437–447, Apr. 2005.
    [CrossRef]
  37. R. M. Krishnaswamy, N. Sivarajan, “Algorithms for routing and wavelength assignment based on solutions of LP-relaxations,” IEEE Commun. Lett., vol. 5, no. 10, pp. 435–437, Oct. 2001.
    [CrossRef]
  38. M. D. Swaminathan, K. N. Sivarajan, “Practical routing and wavelength assignment algorithms for all optical networks with limited wavelength conversion,” in IEEE Int. Conf. on Communications, 2002. ICC 2002, New York, NY, Apr. 2–May 2002, vol. 5, pp. 2750–2755.

2009

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “A proof of wavelength conversion not improving the Lagrangian bound of the static RWA problem,” IEEE Commun. Lett., vol. 13, no. 5, pp. 345–347, May 2009.
[CrossRef]

2008

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

F. Palmieri, U. Fiore, S. Ricciardi, “A minimum cut interference-based integrated RWA algorithm for multi-constrained optical transport networks,” J. Network Syst. Manage., vol. 16, no. 4, pp. 421–448, Dec. 2008.
[CrossRef]

A. Zapata-Beghelli, P. Bayvel, “Dynamic versus static wavelength-routed optical networks,” J. Lightwave Technol., vol. 26, no. 20, pp. 3403–3415, Oct. 2008.
[CrossRef]

T. Matsumoto, T. Takenaka, “Overlap degree aware routing in all-optical routing networks,” IEICE Trans. Commun., vol. E91-B, no. 1, pp. 212–220, Jan. 2008.
[CrossRef]

2007

S. Kim, X. J. Zhang, S. S. Lumetta, “Rapid and efficient protection for all-optical WDM mesh networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, Suppl., pp. 68–82, Dec. 2007.
[CrossRef]

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

G. Shen, W. D. Grover, “Dynamic path-protected service provisioning in optical transport networks with a limited number of add/drop ports and transmitter tenability,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, Suppl., pp. 121–134, Aug. 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]

N. Skorin-Kapov, “Routing and wavelength assignment in optical networks using bin packing based algorithms,” Concr. Library Int., vol. 177, no. 2, pp. 1167–1179, March 2007.

B. Jaumard, C. Meyer, B. Thiongane, “Comparison of ILP formulations for the RWA problem,” Opt. Switching Networking, vol. 4, nos. 3–4, pp. 157–172, Nov. 2007.
[CrossRef]

2006

H. Choo, V. V. Shakhov, B. Mukherjee, “Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths,” Photonic Network Commun., vol. 12, no. 2, pp. 145–152, Sept. 2006.
[CrossRef]

T. F. Noronha, C. C. Ribeiro, “Routing and wavelength assignment by partition colouring,” Concr. Library Int., vol. 171, no. 3, pp. 797–810, June 2006.

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, no. 1, pp. 39–48, Jan. 2006.
[CrossRef]

J. S. Kim, D. C. Lee, H. Sridhar, “Route-metric-based dynamic routing and wavelength assignment for multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 12, Suppl., pp. 56–68, Dec. 2006.
[CrossRef]

2005

K. Mosharaf, J. Talim, I. Lambadaris, “Optimal resource allocation and fairness control in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1496–1507, Aug. 2005.
[CrossRef]

E. Bouillet, J. F. Labourdette, R. Ramamurthy, S. Chaudhuri, “Lightpath re-optimization in mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 437–447, Apr. 2005.
[CrossRef]

X. Chu, B. Li, “Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 704–715, June 2005.
[CrossRef]

Y. Wang, T. H. Cheng, M. H. Lim, “A Tabu search algorithm for static routing and wavelength assignment problem,” IEEE Commun. Lett., vol. 9, no. 9, pp. 841–843, Sept. 2005.
[CrossRef]

2004

A. Jukan, G. Franzl, “Path selection methods with multiple constraints in service-guaranteed WDM networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 59–72, Feb. 2004.
[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]

2003

A. Elwalid, D. Mitra, I. Saniee, I. Widjaja, “Routing and protection in GMPLS networks: from shortest paths to optimized designs,” J. Lightwave Technol., vol. 21, no. 11, pp. 2828–2838, Nov. 2003.
[CrossRef]

A. E. Ozdaglar, D. P. Bertsakas, “Routing and wavelength assignment in optical networks,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 259–272, Apr. 2003.
[CrossRef]

2002

P. H. Ho, H. T. Mouftah, “A novel distributed control protocol in dynamic wavelength-routed optical networks,” IEEE Commun. Mag., vol. 40, no. 11, pp. 38–45, Nov. 2002.
[CrossRef]

2001

R. M. Krishnaswamy, N. Sivarajan, “Algorithms for routing and wavelength assignment based on solutions of LP-relaxations,” IEEE Commun. Lett., vol. 5, no. 10, pp. 435–437, Oct. 2001.
[CrossRef]

2000

H. Zang, J. P. Jue, B. Mukherjee, “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.

R. Dutta, G. N. Rouskas, “Survey of virtual topology design algorithm for wavelength-routed optical networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 73–89, Jan. 2000.

1990

P. B. Luh, D. J. Hoitomt, E. Max, K. R. Pattipati, “Schedule generation and reconfiguration for parallel machines,” IEEE Trans. Rob. Autom., vol. 6, no. 6, pp. 687–696, Dec. 1990.
[CrossRef]

Antonakopoulos, S.

S. Antonakopoulos, L. Zhang, “Heuristics for fiber installation in optical network optimization,” in IEEE Global Telecommunications Conf., 2000. GLOBECOM ’07, Washington, DC, Nov. 26–30, 2007, pp. 2342–2347.

Bayvel, P.

Belgacem, L. D.

L. D. Belgacem, N. Puech, “Solving large size instances of the RWA problem using graph partitioning,” in Int. Conf. on Optical Network Design and Modeling 2008. ONDM 2008, Vilanova ila Geltrú, Spain, March 12–14, 2008, pp. 1–6.

Bertsakas, D. P.

A. E. Ozdaglar, D. P. Bertsakas, “Routing and wavelength assignment in optical networks,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 259–272, Apr. 2003.
[CrossRef]

Bertsekas, D. P.

D. P. Bertsekas, Nonlinear Programming, 2nd ed., Belmont, MA: Athena Scientific, 1999.

Bochmann, G.

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

Bochmann, G. V.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “A proof of wavelength conversion not improving the Lagrangian bound of the static RWA problem,” IEEE Commun. Lett., vol. 13, no. 5, pp. 345–347, May 2009.
[CrossRef]

Bouillet, E.

E. Bouillet, J. F. Labourdette, R. Ramamurthy, S. Chaudhuri, “Lightpath re-optimization in mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 437–447, Apr. 2005.
[CrossRef]

Chaudhuri, S.

E. Bouillet, J. F. Labourdette, R. Ramamurthy, S. Chaudhuri, “Lightpath re-optimization in mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 437–447, Apr. 2005.
[CrossRef]

Cheng, T. H.

Y. Wang, T. H. Cheng, M. H. Lim, “A Tabu search algorithm for static routing and wavelength assignment problem,” IEEE Commun. Lett., vol. 9, no. 9, pp. 841–843, Sept. 2005.
[CrossRef]

Choo, H.

H. Choo, V. V. Shakhov, B. Mukherjee, “Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths,” Photonic Network Commun., vol. 12, no. 2, pp. 145–152, Sept. 2006.
[CrossRef]

Chu, X.

X. Chu, B. Li, “Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 704–715, June 2005.
[CrossRef]

Dutta, R.

R. Dutta, G. N. Rouskas, “Survey of virtual topology design algorithm for wavelength-routed optical networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 73–89, Jan. 2000.

Elwalid, A.

Ezzahdi, M. A.

M. A. Ezzahdi, S. A. Zahr, M. Koubàa, N. Puech, M. Gagnaire, “LERP: a quality of transmission dependent heuristic for routing and wavelength assignment in hybrid WDM networks,” 15th Int. Conf. Computer Communications and Networks, 2006. ICCCN 2006, Proceedings, Arlington, VA, Oct. 9–11, 2006, pp. 125–136.

Fiore, U.

F. Palmieri, U. Fiore, S. Ricciardi, “A minimum cut interference-based integrated RWA algorithm for multi-constrained optical transport networks,” J. Network Syst. Manage., vol. 16, no. 4, pp. 421–448, Dec. 2008.
[CrossRef]

Franzl, G.

A. Jukan, G. Franzl, “Path selection methods with multiple constraints in service-guaranteed WDM networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 59–72, Feb. 2004.
[CrossRef]

Gagnaire, M.

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

M. A. Ezzahdi, S. A. Zahr, M. Koubàa, N. Puech, M. Gagnaire, “LERP: a quality of transmission dependent heuristic for routing and wavelength assignment in hybrid WDM networks,” 15th Int. Conf. Computer Communications and Networks, 2006. ICCCN 2006, Proceedings, Arlington, VA, Oct. 9–11, 2006, pp. 125–136.

Gong, W.

Grover, W. D.

G. Shen, W. D. Grover, “Dynamic path-protected service provisioning in optical transport networks with a limited number of add/drop ports and transmitter tenability,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, Suppl., pp. 121–134, Aug. 2007.
[CrossRef]

Guan, X.

Guo, S.

Ho, P. H.

P. H. Ho, H. T. Mouftah, “A novel distributed control protocol in dynamic wavelength-routed optical networks,” IEEE Commun. Mag., vol. 40, no. 11, pp. 38–45, Nov. 2002.
[CrossRef]

Hoitomt, D. J.

P. B. Luh, D. J. Hoitomt, E. Max, K. R. Pattipati, “Schedule generation and reconfiguration for parallel machines,” IEEE Trans. Rob. Autom., vol. 6, no. 6, pp. 687–696, Dec. 1990.
[CrossRef]

Horiguchi, S.

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, no. 1, pp. 39–48, Jan. 2006.
[CrossRef]

Jaumard, B.

B. Jaumard, C. Meyer, B. Thiongane, “Comparison of ILP formulations for the RWA problem,” Opt. Switching Networking, vol. 4, nos. 3–4, pp. 157–172, Nov. 2007.
[CrossRef]

Jiang, X.

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, no. 1, pp. 39–48, Jan. 2006.
[CrossRef]

Jue, J. P.

H. Zang, J. P. Jue, B. Mukherjee, “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.

Jukan, A.

A. Jukan, G. Franzl, “Path selection methods with multiple constraints in service-guaranteed WDM networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 59–72, Feb. 2004.
[CrossRef]

Kim, J. S.

J. S. Kim, D. C. Lee, H. Sridhar, “Route-metric-based dynamic routing and wavelength assignment for multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 12, Suppl., pp. 56–68, Dec. 2006.
[CrossRef]

Kim, S.

S. Kim, X. J. Zhang, S. S. Lumetta, “Rapid and efficient protection for all-optical WDM mesh networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, Suppl., pp. 68–82, Dec. 2007.
[CrossRef]

Kodialam, M.

M. Kodialam, T. V. Lakshman, “Minimum interference routing with applications to MPLS traffic engineering,” in IEEE INFOCOM 2000, 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Tel Aviv, Israel, March 26–30, 2000, vol. 2, pp. 884–893.

M. Kodialam, T. V. Lakshman, “Integrated dynamic IP and wavelength routing in IP over WDM networks,” in IEEE INFOCOM 2001, 20th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Anchorage, AK, Apr. 22–26, 2001, vol. 1, pp. 358–366.

Koubàa, M.

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

M. A. Ezzahdi, S. A. Zahr, M. Koubàa, N. Puech, M. Gagnaire, “LERP: a quality of transmission dependent heuristic for routing and wavelength assignment in hybrid WDM networks,” 15th Int. Conf. Computer Communications and Networks, 2006. ICCCN 2006, Proceedings, Arlington, VA, Oct. 9–11, 2006, pp. 125–136.

Krishnaswamy, R. M.

R. M. Krishnaswamy, N. Sivarajan, “Algorithms for routing and wavelength assignment based on solutions of LP-relaxations,” IEEE Commun. Lett., vol. 5, no. 10, pp. 435–437, Oct. 2001.
[CrossRef]

Labourdette, J. F.

E. Bouillet, J. F. Labourdette, R. Ramamurthy, S. Chaudhuri, “Lightpath re-optimization in mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 437–447, Apr. 2005.
[CrossRef]

Lakshman, T. V.

M. Kodialam, T. V. Lakshman, “Integrated dynamic IP and wavelength routing in IP over WDM networks,” in IEEE INFOCOM 2001, 20th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Anchorage, AK, Apr. 22–26, 2001, vol. 1, pp. 358–366.

M. Kodialam, T. V. Lakshman, “Minimum interference routing with applications to MPLS traffic engineering,” in IEEE INFOCOM 2000, 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Tel Aviv, Israel, March 26–30, 2000, vol. 2, pp. 884–893.

Lambadaris, I.

K. Mosharaf, J. Talim, I. Lambadaris, “Optimal resource allocation and fairness control in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1496–1507, Aug. 2005.
[CrossRef]

Lee, D. C.

J. S. Kim, D. C. Lee, H. Sridhar, “Route-metric-based dynamic routing and wavelength assignment for multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 12, Suppl., pp. 56–68, Dec. 2006.
[CrossRef]

Lee, S. S. W.

S. S. W. Lee, M. C. Yuang, P. L. Tien, “A Lagrangean relaxation approach to routing and wavelength assignment for multi-granularity optical WDM networks,” in IEEE Global Telecommunications Conference 2004. GLOBECOM ’04, Dallas, TX, Nov. 29–Dec. 3, 2004, vol. 3, pp. 1936–1942.

Li, B.

X. Chu, B. Li, “Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 704–715, June 2005.
[CrossRef]

Lim, M. H.

Y. Wang, T. H. Cheng, M. H. Lim, “A Tabu search algorithm for static routing and wavelength assignment problem,” IEEE Commun. Lett., vol. 9, no. 9, pp. 841–843, Sept. 2005.
[CrossRef]

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]

Lucena, A.

A. Lucena, “Lagrangian relax-and-cut algorithms,” in Handbook of Optimization in Telecommunications, M. G. C. Resende and P. M. Pardalos, eds., New York, NY: Springer Science and Business Media, 2006, pp. 129–146.
[CrossRef]

Luenberger, D. G.

D. G. Luenberger, Y. Ye, Linear and Nonlinear Programming, 3rd ed., New York, NY: Springer, 2008.

Luh, P. B.

P. B. Luh, D. J. Hoitomt, E. Max, K. R. Pattipati, “Schedule generation and reconfiguration for parallel machines,” IEEE Trans. Rob. Autom., vol. 6, no. 6, pp. 687–696, Dec. 1990.
[CrossRef]

Lumetta, S. S.

S. Kim, X. J. Zhang, S. S. Lumetta, “Rapid and efficient protection for all-optical WDM mesh networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, Suppl., pp. 68–82, Dec. 2007.
[CrossRef]

Matsumoto, T.

T. Matsumoto, T. Takenaka, “Overlap degree aware routing in all-optical routing networks,” IEICE Trans. Commun., vol. E91-B, no. 1, pp. 212–220, Jan. 2008.
[CrossRef]

Max, E.

P. B. Luh, D. J. Hoitomt, E. Max, K. R. Pattipati, “Schedule generation and reconfiguration for parallel machines,” IEEE Trans. Rob. Autom., vol. 6, no. 6, pp. 687–696, Dec. 1990.
[CrossRef]

Meyer, C.

B. Jaumard, C. Meyer, B. Thiongane, “Comparison of ILP formulations for the RWA problem,” Opt. Switching Networking, vol. 4, nos. 3–4, pp. 157–172, Nov. 2007.
[CrossRef]

Mitra, D.

Mosharaf, K.

K. Mosharaf, J. Talim, I. Lambadaris, “Optimal resource allocation and fairness control in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1496–1507, Aug. 2005.
[CrossRef]

Mouftah, H. T.

P. H. Ho, H. T. Mouftah, “A novel distributed control protocol in dynamic wavelength-routed optical networks,” IEEE Commun. Mag., vol. 40, no. 11, pp. 38–45, Nov. 2002.
[CrossRef]

Mukherjee, B.

H. Choo, V. V. Shakhov, B. Mukherjee, “Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths,” Photonic Network Commun., vol. 12, no. 2, pp. 145–152, Sept. 2006.
[CrossRef]

H. Zang, J. P. Jue, B. Mukherjee, “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.

Ngo, S. H.

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, no. 1, pp. 39–48, Jan. 2006.
[CrossRef]

Noronha, T. F.

T. F. Noronha, C. C. Ribeiro, “Routing and wavelength assignment by partition colouring,” Concr. Library Int., vol. 171, no. 3, pp. 797–810, June 2006.

Ozdaglar, A. E.

A. E. Ozdaglar, D. P. Bertsakas, “Routing and wavelength assignment in optical networks,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 259–272, Apr. 2003.
[CrossRef]

Palmieri, F.

F. Palmieri, U. Fiore, S. Ricciardi, “A minimum cut interference-based integrated RWA algorithm for multi-constrained optical transport networks,” J. Network Syst. Manage., vol. 16, no. 4, pp. 421–448, Dec. 2008.
[CrossRef]

Pattipati, K. R.

P. B. Luh, D. J. Hoitomt, E. Max, K. R. Pattipati, “Schedule generation and reconfiguration for parallel machines,” IEEE Trans. Rob. Autom., vol. 6, no. 6, pp. 687–696, Dec. 1990.
[CrossRef]

Puech, N.

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

M. A. Ezzahdi, S. A. Zahr, M. Koubàa, N. Puech, M. Gagnaire, “LERP: a quality of transmission dependent heuristic for routing and wavelength assignment in hybrid WDM networks,” 15th Int. Conf. Computer Communications and Networks, 2006. ICCCN 2006, Proceedings, Arlington, VA, Oct. 9–11, 2006, pp. 125–136.

L. D. Belgacem, N. Puech, “Solving large size instances of the RWA problem using graph partitioning,” in Int. Conf. on Optical Network Design and Modeling 2008. ONDM 2008, Vilanova ila Geltrú, Spain, March 12–14, 2008, pp. 1–6.

Qiao, C.

Ramamurthy, R.

E. Bouillet, J. F. Labourdette, R. Ramamurthy, S. Chaudhuri, “Lightpath re-optimization in mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 437–447, Apr. 2005.
[CrossRef]

Ribeiro, C. C.

T. F. Noronha, C. C. Ribeiro, “Routing and wavelength assignment by partition colouring,” Concr. Library Int., vol. 171, no. 3, pp. 797–810, June 2006.

Ricciardi, S.

F. Palmieri, U. Fiore, S. Ricciardi, “A minimum cut interference-based integrated RWA algorithm for multi-constrained optical transport networks,” J. Network Syst. Manage., vol. 16, no. 4, pp. 421–448, Dec. 2008.
[CrossRef]

Rouskas, G. N.

R. Dutta, G. N. Rouskas, “Survey of virtual topology design algorithm for wavelength-routed optical networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 73–89, Jan. 2000.

Saniee, I.

Savoie, M.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “A proof of wavelength conversion not improving the Lagrangian bound of the static RWA problem,” IEEE Commun. Lett., vol. 13, no. 5, pp. 345–347, May 2009.
[CrossRef]

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

Shakhov, V. V.

H. Choo, V. V. Shakhov, B. Mukherjee, “Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths,” Photonic Network Commun., vol. 12, no. 2, pp. 145–152, Sept. 2006.
[CrossRef]

Shen, G.

G. Shen, W. D. Grover, “Dynamic path-protected service provisioning in optical transport networks with a limited number of add/drop ports and transmitter tenability,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, Suppl., pp. 121–134, Aug. 2007.
[CrossRef]

Sivarajan, K. N.

M. D. Swaminathan, K. N. Sivarajan, “Practical routing and wavelength assignment algorithms for all optical networks with limited wavelength conversion,” in IEEE Int. Conf. on Communications, 2002. ICC 2002, New York, NY, Apr. 2–May 2002, vol. 5, pp. 2750–2755.

Sivarajan, N.

R. M. Krishnaswamy, N. Sivarajan, “Algorithms for routing and wavelength assignment based on solutions of LP-relaxations,” IEEE Commun. Lett., vol. 5, no. 10, pp. 435–437, Oct. 2001.
[CrossRef]

Skorin-Kapov, N.

N. Skorin-Kapov, “Routing and wavelength assignment in optical networks using bin packing based algorithms,” Concr. Library Int., vol. 177, no. 2, pp. 1167–1179, March 2007.

Sridhar, H.

J. S. Kim, D. C. Lee, H. Sridhar, “Route-metric-based dynamic routing and wavelength assignment for multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 12, Suppl., pp. 56–68, Dec. 2006.
[CrossRef]

Swaminathan, M. D.

M. D. Swaminathan, K. N. Sivarajan, “Practical routing and wavelength assignment algorithms for all optical networks with limited wavelength conversion,” in IEEE Int. Conf. on Communications, 2002. ICC 2002, New York, NY, Apr. 2–May 2002, vol. 5, pp. 2750–2755.

Takenaka, T.

T. Matsumoto, T. Takenaka, “Overlap degree aware routing in all-optical routing networks,” IEICE Trans. Commun., vol. E91-B, no. 1, pp. 212–220, Jan. 2008.
[CrossRef]

Talim, J.

K. Mosharaf, J. Talim, I. Lambadaris, “Optimal resource allocation and fairness control in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1496–1507, Aug. 2005.
[CrossRef]

Thiongane, B.

B. Jaumard, C. Meyer, B. Thiongane, “Comparison of ILP formulations for the RWA problem,” Opt. Switching Networking, vol. 4, nos. 3–4, pp. 157–172, Nov. 2007.
[CrossRef]

Tien, P. L.

S. S. W. Lee, M. C. Yuang, P. L. Tien, “A Lagrangean relaxation approach to routing and wavelength assignment for multi-granularity optical WDM networks,” in IEEE Global Telecommunications Conference 2004. GLOBECOM ’04, Dallas, TX, Nov. 29–Dec. 3, 2004, vol. 3, pp. 1936–1942.

Wang, Y.

Y. Wang, T. H. Cheng, M. H. Lim, “A Tabu search algorithm for static routing and wavelength assignment problem,” IEEE Commun. Lett., vol. 9, no. 9, pp. 841–843, Sept. 2005.
[CrossRef]

Widjaja, I.

Wu, J.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “A proof of wavelength conversion not improving the Lagrangian bound of the static RWA problem,” IEEE Commun. Lett., vol. 13, no. 5, pp. 345–347, May 2009.
[CrossRef]

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

Yang, O.

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]

Ye, Y.

D. G. Luenberger, Y. Ye, Linear and Nonlinear Programming, 3rd ed., New York, NY: Springer, 2008.

Yuang, M. C.

S. S. W. Lee, M. C. Yuang, P. L. Tien, “A Lagrangean relaxation approach to routing and wavelength assignment for multi-granularity optical WDM networks,” in IEEE Global Telecommunications Conference 2004. GLOBECOM ’04, Dallas, TX, Nov. 29–Dec. 3, 2004, vol. 3, pp. 1936–1942.

Zahr, S. A.

M. A. Ezzahdi, S. A. Zahr, M. Koubàa, N. Puech, M. Gagnaire, “LERP: a quality of transmission dependent heuristic for routing and wavelength assignment in hybrid WDM networks,” 15th Int. Conf. Computer Communications and Networks, 2006. ICCCN 2006, Proceedings, Arlington, VA, Oct. 9–11, 2006, pp. 125–136.

Zang, H.

H. Zang, J. P. Jue, B. Mukherjee, “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.

Zapata-Beghelli, A.

Zhai, Q.

Zhang, J. Y.

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “A proof of wavelength conversion not improving the Lagrangian bound of the static RWA problem,” IEEE Commun. Lett., vol. 13, no. 5, pp. 345–347, May 2009.
[CrossRef]

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

Zhang, L.

S. Antonakopoulos, L. Zhang, “Heuristics for fiber installation in optical network optimization,” in IEEE Global Telecommunications Conf., 2000. GLOBECOM ’07, Washington, DC, Nov. 26–30, 2007, pp. 2342–2347.

Zhang, X. J.

S. Kim, X. J. Zhang, S. S. Lumetta, “Rapid and efficient protection for all-optical WDM mesh networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, Suppl., pp. 68–82, Dec. 2007.
[CrossRef]

Zhang, Y.

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]

Concr. Library Int.

T. F. Noronha, C. C. Ribeiro, “Routing and wavelength assignment by partition colouring,” Concr. Library Int., vol. 171, no. 3, pp. 797–810, June 2006.

N. Skorin-Kapov, “Routing and wavelength assignment in optical networks using bin packing based algorithms,” Concr. Library Int., vol. 177, no. 2, pp. 1167–1179, March 2007.

IEEE Commun. Lett.

Y. Wang, T. H. Cheng, M. H. Lim, “A Tabu search algorithm for static routing and wavelength assignment problem,” IEEE Commun. Lett., vol. 9, no. 9, pp. 841–843, Sept. 2005.
[CrossRef]

J. Y. Zhang, J. Wu, G. V. Bochmann, M. Savoie, “A proof of wavelength conversion not improving the Lagrangian bound of the static RWA problem,” IEEE Commun. Lett., vol. 13, no. 5, pp. 345–347, May 2009.
[CrossRef]

R. M. Krishnaswamy, N. Sivarajan, “Algorithms for routing and wavelength assignment based on solutions of LP-relaxations,” IEEE Commun. Lett., vol. 5, no. 10, pp. 435–437, Oct. 2001.
[CrossRef]

IEEE Commun. Mag.

P. H. Ho, H. T. Mouftah, “A novel distributed control protocol in dynamic wavelength-routed optical networks,” IEEE Commun. Mag., vol. 40, no. 11, pp. 38–45, Nov. 2002.
[CrossRef]

IEEE J. Sel. Areas Commun.

J. S. Kim, D. C. Lee, H. Sridhar, “Route-metric-based dynamic routing and wavelength assignment for multifiber WDM networks,” IEEE J. Sel. Areas Commun., vol. 24, no. 12, Suppl., pp. 56–68, Dec. 2006.
[CrossRef]

K. Mosharaf, J. Talim, I. Lambadaris, “Optimal resource allocation and fairness control in all-optical WDM networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1496–1507, Aug. 2005.
[CrossRef]

S. Kim, X. J. Zhang, S. S. Lumetta, “Rapid and efficient protection for all-optical WDM mesh networks,” IEEE J. Sel. Areas Commun., vol. 25, no. 9, Suppl., pp. 68–82, Dec. 2007.
[CrossRef]

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

G. Shen, W. D. Grover, “Dynamic path-protected service provisioning in optical transport networks with a limited number of add/drop ports and transmitter tenability,” IEEE J. Sel. Areas Commun., vol. 25, no. 6, Suppl., pp. 121–134, Aug. 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]

IEEE Trans. Rob. Autom.

P. B. Luh, D. J. Hoitomt, E. Max, K. R. Pattipati, “Schedule generation and reconfiguration for parallel machines,” IEEE Trans. Rob. Autom., vol. 6, no. 6, pp. 687–696, Dec. 1990.
[CrossRef]

IEEE/ACM Trans. Netw.

E. Bouillet, J. F. Labourdette, R. Ramamurthy, S. Chaudhuri, “Lightpath re-optimization in mesh optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 437–447, Apr. 2005.
[CrossRef]

A. Jukan, G. Franzl, “Path selection methods with multiple constraints in service-guaranteed WDM networks,” IEEE/ACM Trans. Netw., vol. 12, no. 1, pp. 59–72, Feb. 2004.
[CrossRef]

A. E. Ozdaglar, D. P. Bertsakas, “Routing and wavelength assignment in optical networks,” IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 259–272, Apr. 2003.
[CrossRef]

X. Chu, B. Li, “Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,” IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 704–715, June 2005.
[CrossRef]

IEICE Trans. Commun.

T. Matsumoto, T. Takenaka, “Overlap degree aware routing in all-optical routing networks,” IEICE Trans. Commun., vol. E91-B, no. 1, pp. 212–220, Jan. 2008.
[CrossRef]

J. Lightwave Technol.

J. Network Syst. Manage.

F. Palmieri, U. Fiore, S. Ricciardi, “A minimum cut interference-based integrated RWA algorithm for multi-constrained optical transport networks,” J. Network Syst. Manage., vol. 16, no. 4, pp. 421–448, Dec. 2008.
[CrossRef]

Opt. Networks Mag.

H. Zang, J. P. Jue, B. Mukherjee, “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.

R. Dutta, G. N. Rouskas, “Survey of virtual topology design algorithm for wavelength-routed optical networks,” Opt. Networks Mag., vol. 1, no. 1, pp. 73–89, Jan. 2000.

Opt. Switching Networking

B. Jaumard, C. Meyer, B. Thiongane, “Comparison of ILP formulations for the RWA problem,” Opt. Switching Networking, vol. 4, nos. 3–4, pp. 157–172, Nov. 2007.
[CrossRef]

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

Photonic Network Commun.

S. H. Ngo, X. Jiang, S. Horiguchi, “An ant-based approach for dynamic RWA in optical WDM networks,” Photonic Network Commun., vol. 11, no. 1, pp. 39–48, Jan. 2006.
[CrossRef]

H. Choo, V. V. Shakhov, B. Mukherjee, “Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths,” Photonic Network Commun., vol. 12, no. 2, pp. 145–152, Sept. 2006.
[CrossRef]

Other

L. D. Belgacem, N. Puech, “Solving large size instances of the RWA problem using graph partitioning,” in Int. Conf. on Optical Network Design and Modeling 2008. ONDM 2008, Vilanova ila Geltrú, Spain, March 12–14, 2008, pp. 1–6.

S. Antonakopoulos, L. Zhang, “Heuristics for fiber installation in optical network optimization,” in IEEE Global Telecommunications Conf., 2000. GLOBECOM ’07, Washington, DC, Nov. 26–30, 2007, pp. 2342–2347.

M. A. Ezzahdi, S. A. Zahr, M. Koubàa, N. Puech, M. Gagnaire, “LERP: a quality of transmission dependent heuristic for routing and wavelength assignment in hybrid WDM networks,” 15th Int. Conf. Computer Communications and Networks, 2006. ICCCN 2006, Proceedings, Arlington, VA, Oct. 9–11, 2006, pp. 125–136.

D. P. Bertsekas, Nonlinear Programming, 2nd ed., Belmont, MA: Athena Scientific, 1999.

A. Lucena, “Lagrangian relax-and-cut algorithms,” in Handbook of Optimization in Telecommunications, M. G. C. Resende and P. M. Pardalos, eds., New York, NY: Springer Science and Business Media, 2006, pp. 129–146.
[CrossRef]

D. G. Luenberger, Y. Ye, Linear and Nonlinear Programming, 3rd ed., New York, NY: Springer, 2008.

S. S. W. Lee, M. C. Yuang, P. L. Tien, “A Lagrangean relaxation approach to routing and wavelength assignment for multi-granularity optical WDM networks,” in IEEE Global Telecommunications Conference 2004. GLOBECOM ’04, Dallas, TX, Nov. 29–Dec. 3, 2004, vol. 3, pp. 1936–1942.

M. Kodialam, T. V. Lakshman, “Minimum interference routing with applications to MPLS traffic engineering,” in IEEE INFOCOM 2000, 19th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Tel Aviv, Israel, March 26–30, 2000, vol. 2, pp. 884–893.

M. Kodialam, T. V. Lakshman, “Integrated dynamic IP and wavelength routing in IP over WDM networks,” in IEEE INFOCOM 2001, 20th Annu. Joint Conf. of the IEEE Computer and Communications Societies, Proceedings, Anchorage, AK, Apr. 22–26, 2001, vol. 1, pp. 358–366.

M. D. Swaminathan, K. N. Sivarajan, “Practical routing and wavelength assignment algorithms for all optical networks with limited wavelength conversion,” in IEEE Int. Conf. on Communications, 2002. ICC 2002, New York, NY, Apr. 2–May 2002, vol. 5, pp. 2750–2755.

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

Fig. 1
Fig. 1

Schematic depiction of the overall algorithm.

Fig. 2
Fig. 2

NSFNET (14 nodes, 21 links).

Fig. 3
Fig. 3

Achieved design objective values and the lower bounds when additional wavelength channels are added or existing wavelength channels are relocated.

Fig. 4
Fig. 4

Achieved design objective values and the lower bounds when additional transmitters and receivers are added or existing transmitters and receivers are relocated.

Fig. 5
Fig. 5

Achieved design objective values and the lower bounds when additional transmitters and receivers are incrementally deployed.

Fig. 6
Fig. 6

Achieved value and a lower bound of the design objective when additional lightpath demands are added.

Fig. 7
Fig. 7

Pan-European network with 28 nodes and 61 links.

Fig. 8
Fig. 8

Convergence speed comparison between different multiplier initialization schemes.

Tables (6)

Tables Icon

Table 1 Lightpath Demand Matrix

Tables Icon

Table 2 Average Optimized Lagrange Multipliers for All Links

Tables Icon

Table 3 Optimized Lagrange Multipliers for Transmitters and Receivers at All Nodes

Tables Icon

Table 4 Optimized Lagrange Multipliers for Wavelength Converters at All Nodes

Tables Icon

Table 5 Lightpath Demand Matrix in the Previous Session for the Multiplier Initialization

Tables Icon

Table 6 Current Lightpath Demand Matrix

Equations (23)

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

J = s sdn L [ ( 1 α sdn ) P sdn + α sdn C sdn ] .
C sdn = e i j E 0 < c W d i j δ i j c sdn + i V o i ϕ i sdn s sdn L ,
j V 0 < c W δ i j c sdn j V 0 < c W δ j i c sdn = { α sdn if i = s α sdn if i = d 0 otherwise } s sdn L .
s sdn L δ i j c sdn 1 e i j E , 0 < c W .
d V 0 < n N sd α sdn T s s V ,
s V 0 < n N sd α sdn R d d V ,
s sdn L ϕ i sdn F i i V .
ϕ j sdn = { 1 if m , k V and b a , δ m j a sdn = δ j k b sdn = 1 0 otherwise }
j V .
L ( V , M ) = J ( V ) + e i j E 0 < c W ξ i j c ( s sdn L δ i j c sdn 1 ) + s V π s ( d V 0 < n N sd α sdn T s ) + d V θ d ( s V 0 < n N sd α sdn R d ) + i V λ i ( s sdn L ϕ i sdn F i ) .
q ( M ) = min V [ L ( V , M ) ] .
q * ( M * ) = min V [ L ( V , M * ) ] min V [ J ( V ) ] .
M R * = d J * d R ,
M R * Δ J * Δ R .
q ( M ) = min V { s sdn L [ ( 1 α sdn ) P sdn + α sdn ( e i j E 0 < c W δ i j c sdn ( ξ i j c + d i j ) + i V ϕ i sdn ( λ i + o i ) + π s + θ d ) ] } .
q ( M ) = s sdn L min α sdn [ ( 1 α sdn ) P sdn + α sdn min Δ sdn , Φ sdn ( e i j E 0 < c W δ i j c sdn ( ξ i j c + d i j ) + i V ϕ i sdn ( λ i + o i ) + π s + θ d ) ] .
D sdn = min Δ sdn , Φ sdn { e i j E 0 < c W δ i j c sdn ( ξ i j c + d i j ) + i V ϕ i sdn ( λ i + o i ) } ,
min α sdn [ ( 1 α sdn ) P sdn + α sdn ( D sdn + π s + θ d ) ] .
M ( h + 1 ) = M ( h ) + α ( h ) g ( M ( h ) ) ,
g i j c ( ξ ) = s sdn L δ i j c sdn 1 ,
g s ( π ) = d V 0 < n N sd α sdn T s ,
g d ( θ ) = s V 0 < n N sd α sdn R d ,
g i ( λ ) = s sdn L ϕ i sdn F i .