OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and V. Chan
  • Vol. 1, Iss. 4 — Sep. 1, 2009
  • pp: 294–306

Resource Criticality Analysis of Static Resource Allocations and Its Applications in WDM Network Planning

James Yiming Zhang, Jing Wu, Gregor v. Bochmann, and Michel Savoie  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 1, Issue 4, pp. 294-306 (2009)
http://dx.doi.org/10.1364/JOCN.1.000294


View Full Text Article

Acrobat PDF (384 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

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:
Regular Papers

History
Original Manuscript: March 11, 2009
Revised Manuscript: July 15, 2009
Manuscript Accepted: July 21, 2009
Published: August 20, 2009

Citation
James Yiming Zhang, Jing Wu, Gregor v. Bochmann, and Michel Savoie, "Resource Criticality Analysis of Static Resource Allocations and Its Applications in WDM Network Planning," J. Opt. Commun. Netw. 1, 294-306 (2009)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-1-4-294


Sort:  Author  |  Year  |  Journal  |  Reset

References

  1. H. Zang, J. P. Jue, and 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 and 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, 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]
  4. T. F. Noronha and 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, and 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, and 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 and 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 and 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, and 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, and 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 and 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, and 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, and 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 and 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 and 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 and 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 and 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, and 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, 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, Suppl., pp. 58-67, Dec. 2007. [CrossRef]
  21. G. Shen and 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 and 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 and 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 and 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.
  25. F. Palmieri, U. Fiore, and 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, and 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, and 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, and 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, and 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.
  31. D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd ed., New York, NY: Springer, 2008.
  32. J. Y. Zhang, J. Wu, G. Bochmann, and 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, 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]
  35. J. Y. Zhang, J. Wu, G. V. Bochmann, and 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, and 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 and 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 and 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

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