Abstract

Survivable traffic grooming (STG) is a promising approach to provide reliable and resource-efficient multigranularity connection services in wavelength-division-multiplexing (WDM) optical networks. In this paper, we study the STG problem in WDM mesh optical networks employing path protection at the connection level. Both dedicated-protection and shared-protection schemes are considered. Given network resources, the objective of the STG problem is to maximize network throughput. To enable survivability under various kinds of single failures, such as fiber cut and duct cut, we consider the general shared-risk-link-group (SRLG) diverse routing constraints. We first resort to the integer-linear-programming (ILP) approach to obtain optimal solutions. To address its high computational complexity, we then propose three efficient heuristics, namely separated survivable grooming algorithm (SSGA), integrated survivable grooming algorithm (ISGA), and tabu-search survivable grooming algorithm (TSGA). While SSGA and ISGA correspond to an overlay network model and a peer network model, respectively, TSGA further improves the grooming results from SSGA and ISGA by incorporating the effective tabu-search (TS) method. Numerical results show that the heuristics achieve comparable solutions to the ILP approach, which uses significantly longer running times than the heuristics.

© 2005 IEEE

PDF Article

References

  • View by:
  • |

  1. K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network", IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122-133, Jan. 2002.
  2. S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks-Part I: Protection", in Proc. IEEE Information Communications (INFOCOM), New York, Mar. 1999, pp. 744-751.
  3. Y. Xiong, D. Xu and C. Qiao, "Achieving fast and bandwidth-efficient shared-path protection", J. Lightw. Technol., vol. 21, no. 2, pp. 2683-2693, Feb. 2003.
  4. S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks-Part II: Restoration", in Proc. IEEE Integrated Circuits Conf., Vancouver, Canada,Jun. 1999, pp. 2023-2030.
  5. C. Ou, K. Zhu and B. Mukherjee, "Traffic grooming for survivable WDM networks-shared protection", IEEE J. Sel. Areas Commun., vol. 21, no. 9, pp. 1367-1383, Nov. 2003.
  6. G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri and K. Bala, "Routing and restoration architectures in mesh optical networks", Opt. Netw. Mag., vol. 4, no. 1, pp. 91-106, Jan./Feb. 2003.
  7. J. Hu, "Diverse routing in optical mesh networks", IEEE Trans. Commun., vol. 51, no. 3, pp. 489-494, Mar. 2003.
  8. H. Zang, C. Ou and B. Mukherjee, "Path-protection routing and wavelength assignment (RWA) in WDM mesh networks under duct-layer constraints", IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 248-258, Apr. 2003.
  9. L. Shen, X. Yang and B. Ramamurthy, "Shared Risk Link Group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks", IEEE/ACM Trans. Netw., vol. 13, no. 4, pp. 918-931, Aug. 2005.
  10. S. Thiagarajan and A. Somani, "Traffic grooming for survivable WDM mesh networks", Opt. Netw. Mag., vol. 3, no. 3, pp. 88-98, May/Jun. 2002.
  11. J. Fang and A. K. Somani, "Enabling subwavelength level traffic grooming in survivable WDM optical network design", in Proc. IEEE Global Telecommunications (GLOBECOM), vol. 5, San Francisco, CA, Dec. 2003, pp. 2761-2766.
  12. R. Ramaswami and K. N. Sivarajan, "Design of logical topologies for wavelength-routed optical networks", IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 840-851, Jun. 1996.
  13. R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical topologies: A linear formulation for wavelength-routed optical networks with no wavelength changers", IEEE/ACM Trans. Netw., vol. 9, no. 2, pp. 186-198, Apr. 2001.
  14. D. Banerjee and B. Mukherjee, "Wavelength-routed optical networks: Linear formulation, resource budgeting tradeoffs and a reconfiguration study", IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 598-607, Apr. 2000.
  15. R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks", Opt. Netw. Mag., vol. 1, no. 1, pp. 73-89, Jan. 2000.
  16. J. W. Suurballe, "Disjoint paths in a network", Networks, vol. 4, pp. 125-145, 1974.
  17. G. Li, B. Doverspike and C. Kalmanek, "Fiber span failure protection in mesh optical networks", in Proc. SPIE Optical Networking and Communications (OptiComm), Denver, CO, Aug. 2001, pp. 130-141.
  18. C. Xin, Y. Ye, S. Dixit and C. Qiao, "A joint lightpath routing approach in survivable optical networks", Opt. Netw. Mag., vol. 3, no. 3, pp. 23-32, May/Jun. 2002.
  19. P. H. Ho, J. Tapolcai and H. T. Mouftah, "Diverse routing for shared protection in survivable optical networks", in Proc. IEEE Global Telecommunications (GLOBECOM), vol. 5, San Francisco, CA, Dec. 2003, pp. 2519-2523.
  20. F. Glover and M. Laguna, Tabu Search, Boston, MA: Kluwer, Jul. 1997.
  21. W. Yao and B. Ramamurthy, "A link bundled auxiliary graph model for constrained dynamic traffic grooming in optical WDM mesh networks", IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1542-1555, Aug. 2005.
  22. ILOG CPLEX. ILOG, Inc., Mountain View, CA, Available [Online] http://www.ilog.com/products/cplex/
  23. W. Yao and B. Ramamurthy, "Survivable traffic grooming in WDM mesh networks under SRLG constraints", in Proc. IEEE Int. Conf. Communications (ICC), Seoul, Korea,May 2005, pp. 1751-1755.
  24. W. Yao, "Traffic grooming in next-generation optical WDM mesh networks", Ph.D. dissertation, Dept. CSE, Univ. Nebraska, Lincoln, 2005.

Other (24)

K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network", IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122-133, Jan. 2002.

S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks-Part I: Protection", in Proc. IEEE Information Communications (INFOCOM), New York, Mar. 1999, pp. 744-751.

Y. Xiong, D. Xu and C. Qiao, "Achieving fast and bandwidth-efficient shared-path protection", J. Lightw. Technol., vol. 21, no. 2, pp. 2683-2693, Feb. 2003.

S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks-Part II: Restoration", in Proc. IEEE Integrated Circuits Conf., Vancouver, Canada,Jun. 1999, pp. 2023-2030.

C. Ou, K. Zhu and B. Mukherjee, "Traffic grooming for survivable WDM networks-shared protection", IEEE J. Sel. Areas Commun., vol. 21, no. 9, pp. 1367-1383, Nov. 2003.

G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri and K. Bala, "Routing and restoration architectures in mesh optical networks", Opt. Netw. Mag., vol. 4, no. 1, pp. 91-106, Jan./Feb. 2003.

J. Hu, "Diverse routing in optical mesh networks", IEEE Trans. Commun., vol. 51, no. 3, pp. 489-494, Mar. 2003.

H. Zang, C. Ou and B. Mukherjee, "Path-protection routing and wavelength assignment (RWA) in WDM mesh networks under duct-layer constraints", IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 248-258, Apr. 2003.

L. Shen, X. Yang and B. Ramamurthy, "Shared Risk Link Group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks", IEEE/ACM Trans. Netw., vol. 13, no. 4, pp. 918-931, Aug. 2005.

S. Thiagarajan and A. Somani, "Traffic grooming for survivable WDM mesh networks", Opt. Netw. Mag., vol. 3, no. 3, pp. 88-98, May/Jun. 2002.

J. Fang and A. K. Somani, "Enabling subwavelength level traffic grooming in survivable WDM optical network design", in Proc. IEEE Global Telecommunications (GLOBECOM), vol. 5, San Francisco, CA, Dec. 2003, pp. 2761-2766.

R. Ramaswami and K. N. Sivarajan, "Design of logical topologies for wavelength-routed optical networks", IEEE J. Sel. Areas Commun., vol. 14, no. 5, pp. 840-851, Jun. 1996.

R. M. Krishnaswamy and K. N. Sivarajan, "Design of logical topologies: A linear formulation for wavelength-routed optical networks with no wavelength changers", IEEE/ACM Trans. Netw., vol. 9, no. 2, pp. 186-198, Apr. 2001.

D. Banerjee and B. Mukherjee, "Wavelength-routed optical networks: Linear formulation, resource budgeting tradeoffs and a reconfiguration study", IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 598-607, Apr. 2000.

R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks", Opt. Netw. Mag., vol. 1, no. 1, pp. 73-89, Jan. 2000.

J. W. Suurballe, "Disjoint paths in a network", Networks, vol. 4, pp. 125-145, 1974.

G. Li, B. Doverspike and C. Kalmanek, "Fiber span failure protection in mesh optical networks", in Proc. SPIE Optical Networking and Communications (OptiComm), Denver, CO, Aug. 2001, pp. 130-141.

C. Xin, Y. Ye, S. Dixit and C. Qiao, "A joint lightpath routing approach in survivable optical networks", Opt. Netw. Mag., vol. 3, no. 3, pp. 23-32, May/Jun. 2002.

P. H. Ho, J. Tapolcai and H. T. Mouftah, "Diverse routing for shared protection in survivable optical networks", in Proc. IEEE Global Telecommunications (GLOBECOM), vol. 5, San Francisco, CA, Dec. 2003, pp. 2519-2523.

F. Glover and M. Laguna, Tabu Search, Boston, MA: Kluwer, Jul. 1997.

W. Yao and B. Ramamurthy, "A link bundled auxiliary graph model for constrained dynamic traffic grooming in optical WDM mesh networks", IEEE J. Sel. Areas Commun., vol. 23, no. 8, pp. 1542-1555, Aug. 2005.

ILOG CPLEX. ILOG, Inc., Mountain View, CA, Available [Online] http://www.ilog.com/products/cplex/

W. Yao and B. Ramamurthy, "Survivable traffic grooming in WDM mesh networks under SRLG constraints", in Proc. IEEE Int. Conf. Communications (ICC), Seoul, Korea,May 2005, pp. 1751-1755.

W. Yao, "Traffic grooming in next-generation optical WDM mesh networks", Ph.D. dissertation, Dept. CSE, Univ. Nebraska, Lincoln, 2005.

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.