OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and V. Chan
  • Vol. 2, Iss. 7 — Jul. 1, 2010
  • pp: 442–455

Routing and Wavelength Assignment of Static Manycast Demands Over All-Optical Wavelength-Routed WDM Networks

Neal Charbonneau and Vinod M. Vokkarane  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 2, Issue 7, pp. 442-455 (2010)
http://dx.doi.org/10.1364/JOCN.2.000442


View Full Text Article

Acrobat PDF (319 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

In this paper we present the static manycast routing and wavelength assignment (MA-RWA) problem along with heuristics and an integer linear program (ILP) to solve it. Manycast is a point-to-multipoint communication paradigm with applications in e-Science, Grid, and cloud computing. A manycast request specifies a candidate set of destinations, of which a subset must be reached. To solve MA-RWA, a light-tree must be assigned to each manycast request in a static set such that the number of wavelengths required is minimized. We present two heuristics, the shortest path heuristic (SPT) and the lambda path heuristic (LPH), a tabu search meta-heuristic (TS), and an ILP formulation. We show that TS provides results close to the optimal solution (from the ILP) for small networks. We then show that TS provides a 10% improvement over LPH and a 30%–40% improvement over SPT for various realistic networks.

© 2010 Optical Society of America

OCIS Codes
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4253) Fiber optics and optical communications : Networks, circuit-switched

ToC Category:
Research Papers

History
Original Manuscript: February 18, 2010
Revised Manuscript: May 2, 2010
Manuscript Accepted: May 16, 2010
Published: June 25, 2010

Citation
Neal Charbonneau and Vinod M. Vokkarane, "Routing and Wavelength Assignment of Static Manycast Demands Over All-Optical Wavelength-Routed WDM Networks," J. Opt. Commun. Netw. 2, 442-455 (2010)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-2-7-442


Sort:  Author  |  Year  |  Journal  |  Reset

References

  1. G. E. Keiser, “A review of WDM technology and applications,” Opt. Fiber Technol. , vol. 5, no. 1, pp. 3–39, 1999. [CrossRef]
  2. R. Ramaswami and K. N. Sivarajan, “Routing and wavelength assignment in all-optical networks,” IEEE/ACM Trans. Netw. , vol. 3, no. 5, pp. 489–500, 1995. [CrossRef]
  3. I. Chlamatac, A. Ganz, and G. Karmi, “Lightpath communications: an approach to high bandwidth optical WAN’s,” IEEE/ACM Trans. Netw. , vol. 40, no. 7, pp. 1171–1182, July 1992.
  4. H. Zang, J. P. Jue, and 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.
  5. S. Y. Cheung and A. Kumar, “Efficient quorumcast routing algorithms,” in Proc. IEEE INFOCOM, 1994, pp. 840–847.
  6. R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi, “Spanning trees short or small,” in Proc. ACM-SIAM Symp. on Discrete Algorithms, 1994, pp. 546–555.
  7. B. G. Bathula and V. M. Vokkarane, “QoS-based manycasting over optical burst-switched (OBS) networks,” IEEE/ACM Trans. Netw. , vol. 18, no. 1, pp. 271–283, Feb. 2010. [CrossRef]
  8. L. H. Sahasrabuddhe and B. Mukherjee, “Light trees: optical multicasting for improved performance in wavelength-routed networks,” IEEE Commun. Mag. , vol. 37, no. 2, pp. 67–73, Feb. 1999. [CrossRef]
  9. R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations. Springer, 1972, pp. 85–103.
  10. W. S. Hu and Q. J. Zeng, “Multicasting optical cross connects employing splitter-and-delivery switch,” IEEE Photon. Technol. Lett. , vol. 10, pp. 970–972, 1998. [CrossRef]
  11. J. Leuthold and C. H. Joyner, “Multimode interference couplers with tunable power splitting ratios,” J. Lightwave Technol. , vol. 19, no. 5, pp. 700–707, May 2001. [CrossRef]
  12. H. S. Chung, S. H. Chang, and K. Kim, “Experimental demonstration of layer-1 multicast for WDM networks using reconfigurable OADM,” Opt. Fiber Technol. , vol. 15, no. 5–6, pp. 431–437, 2009.
  13. R. Jain, “Internet 3.0: ten problems with current Internet architecture and solutions for the next generation,” in Proc. IEEE MILCOMM, 2006, pp. 1–9.
  14. “Large hadron collider (LHC) project,” http://lhc.web.cern.ch/lhc.
  15. R. Malli, X. Zhang, and C. Qiao, “Benefits of multicasting in all-optical networks,” in Proc. All-Optical Networking, 1998, pp. 209–220.
  16. G. Sahin and M. Azizoglu, “Multicast routing and wavelength assignment in wide-area networks,” Proc. SPIE , vol. 3531, pp. 196–208, 1998.
  17. M. Ali and J. S. Deogun, “Power-efficient design of multicast wavelength-routed networks,” IEEE J. Sel. Areas Commun. , vol. 18, no. 10, pp. 1852–1862, Oct. 2000. [CrossRef]
  18. J. Bermond, L. Gargano, S. Perennes, A. A. Rescigno, and U. Vaccaro, “Efficient collective communication in optical networks,” Theor. Comput. Sci. , vol. 233, no. 1–2, pp. 165–189, 2000. [CrossRef]
  19. X. Zhang, J. Y. Wei, and C. Qiao, “Constrained multicast routing in WDM networks with sparse light splitting,” J. Lightwave Technol. , vol. 18, no. 12, pp. 1917–1927, Dec. 2000. [CrossRef]
  20. L. H. Sahasrabuddhe and B. Mukherjee, “Multicast routing algorithms and protocols: a tutorial,” IEEE Network , vol. 14, no. 1, pp. 90–102, Jan./Feb. 2000. [CrossRef]
  21. R. Libeskind-Hadas and R. Melhem, “Multicast routing and wavelength assignment in multihop optical networks,” IEEE/ACM Trans. Netw. , vol. 10, no. 5, pp. 621–629, 2002. [CrossRef]
  22. B. Chen and J. Wang, “Efficient routing and wavelength assignment for multicast in WDM networks,” IEEE J. Sel. Areas Commun. , vol. 20, no. 1, pp. 97–109, Jan. 2002. [CrossRef]
  23. S. Sankaranarayanan and S. Subramaniam, “Comprehensive performance modeling and analysis of multicasting in optical networks,” IEEE J. Sel. Areas Commun. , vol. 21, no. 9, pp. 1399–1413, Nov. 2003. [CrossRef]
  24. Y. Xin and G. N. Rouskas, “Multicast routing under optical layer constraints,” in Proc. IEEE INFOCOM, 2004, vol. 4, pp. 2731–2742.
  25. B. Du, J. Gu, D. H. K. Tsang, and W. Wang, “Quorumcast routing by multispace search,” in Proc. IEEE GLOBECOM, Nov. 1996, vol. 2, pp. 1069–1073.
  26. C. P. Low, “Optimal quorumcast routing,” in Proc. IEEE GLOBECOM, 1998, vol. 5, pp. 3013–3016.
  27. B. Wang and J. Hou, “An efficient QoS routing algorithm for quorumcast communication,” in Proc. IEEE ICNP, 2001, pp. 110–118.
  28. F. A. Chudak, T. Roughgarden, and D. P. Williamson, “Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation,” Math. Program. , vol. 100, no. 2, pp. 411–421, 2004. [CrossRef]
  29. X. Huang, Q. She, V. M. Vokkarane, and J. P. Jue, “Manycasting over optical burst-switched networks,” in Proc. IEEE ICC, 2007, pp. 2353–2358.
  30. Q. She, X. Huang, N. Kannasoot, Z. Qiong, and J. P. Jue, “Multiresource manycast over optical burst-switched networks,” in Proc. IEEE ICCCN, Aug. 2007, pp. 222–227.
  31. B. G. Bathula, V. M. Vokkarane, R. R. C. Bikram, and S. Talabathula, “Impairment-aware manycast algorithms over optical burst-switched networks,” in Proc. IEEE ICCCN, 2008.
  32. Q. She, N. Kannasoot, J. P. Jue, and Y.-C. Kim, “On finding minimum cost tree for multi-resource manycast in mesh networks,” Opt. Switching Networking , vol. 6, no. 1, pp. 29–36, Jan. 2009.
  33. D. Din, “A hybrid method for solving ARWA problem on WDM network,” Comput. Commun. , vol. 30, no. 2, pp. 385–395, 2007. [CrossRef]
  34. S. Azodolmolky, M. Klinkowski, E. Marin, D. Careglio, J. S. Pareta, and I. Tomkos, “A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks,” Comput. Netw. , vol. 53, no. 7, pp. 926–944, 2009. [CrossRef]
  35. J. P. Jue, “Lightpath establishment in wavelength-routed WDM optical networks,” in Optical Networks: Recent Advances. Springer, 2001, pp. 99–122.
  36. M. Andrews and L. Zhang, “Complexity of wavelength assignment in optical network optimization,” IEEE/ACM Trans. Netw. , vol. 17, no. 2, pp. 646–657, 2009. [CrossRef]
  37. H. Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica , vol. 24, no. 6, pp. 573–577, 1980.
  38. F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, 1997.
  39. J. Kuri, N. Puech, M. Gagnaire, and E. Dotaro, “Routing foreseeable lightpath demands using a tabu search meta-heuristic,” in Proc. IEEE GLOBECOM, 2002, vol. 3, pp. 2803–2807.
  40. 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]
  41. C. Dzongang, P. Galinier, and S. Pierre, “A tabu search heuristic for the routing and wavelength assignment problem in optical networks,” IEEE Commun. Lett. , vol. 9, no. 5, pp. 426–428, May 2005. [CrossRef]
  42. “NP science network requirements,” 2008, http://www.es.net/pub/esnet-doc/NP-Net-Req-Workshop-2008-Final-Report.pdf.
  43. V. M. Vokkarane and B. G. Bathula, “Manycast service in optical burst/packet switched (OBS/OPS) networks (Invited Paper),” in ICST/ACM GridNets, 2008, pp. 231–242
  44. B. G. Bathula, V. M. Vokkarane, and R. R. C. Bikram, “Impairment-aware manycasting over optical burst-switched networks,” in Proc. IEEE ICC, 2008, pp. 5234–5238.

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