Abstract

In this paper we investigate techniques for provisioning advance reservation (AR) multicast requests in multicast-incapable (MI) networks, which lack the ability to split an incoming signal to multiple output ports, without performing an O-E-O conversion. AR traffic consists of connection requests that arrive and reserve network resources at some time before they need them to ensure better quality of service than on-demand requests would receive. The traditional approach of providing multicast support in MI networks is to use an overlay approach in which a set of lightpaths is established from the source to each multicast destination member independently. This approach is wasteful of wavelength resources, particularly as the multicast destination set grows. We propose two alternative overlay approaches that take advantage of multiple-hop overlay-tree structures to limit the consumption of wavelengths in the network. We investigate static traffic scenarios on various network topologies and develop integer linear programs (ILPs) to optimally solve all three of the overlay-tree problems presented in this work with the goal of minimizing the total number of wavelengths required to service a multicast request set. We also present efficient heuristics that build and select overlay-trees that lower dynamic connection blocking and wavelength consumption. We compare the heuristics to the optimal ILPs on a small-scale network, and then further evaluate the heuristics on several large-scale topologies. In all scenarios, we are able to conclude that by sacrificing a minimization of O-E-O conversions, our more flexible overlay approaches, called drop at member node (MI-DMN) and drop at any node (MI-DAN), are superior in terms of resource usage when compared with the traditional naïve approach. Further dynamic traffic evaluations reveal that blocking may be lowered over the naïve approach by more than two orders of magnitude at low to medium traffic loads.

© 2014 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. Worldwide LHC Computing Grid, 2013 [Online]. Available: http://lcg.web.cern.ch/lcg/ .
  2. H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Netw. Mag., vol.  1, no. 1, pp. 47–60, Oct. 2000.
  3. N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol.  24, no. 8, pp. 2–15, Aug. 2006.
  4. X. Luo and B. Wang, “Service provisioning under a scheduled traffic model using light-trails in WDM optical networks,” in Proc. IEEE BROADNETS, Sept. 2007, pp. 385–393.
  5. S. Lee, A. Chen, and M. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photon. Netw. Commun., vol.  19, no. 1, pp. 103–109, 2010.
  6. D. Andrei, H.-H. Yen, M. Tornatore, C. U. Martel, and B. Mukherjee, “Integrated provisioning of sliding scheduled services over WDM optical networks [Invited],” J. Opt. Commun. Netw., vol.  1, no. 2, pp. A94–A105, July 2009.
    [CrossRef]
  7. W. E. Johnston, ESnet4: Networking for the future of DOE science, 2008 [Online]. Available: http://www.es.net/assets/Uploads/ESnet4-Networking-for-the-Future-of-Science-2008-05-05.NP.v1.pdf .
  8. R. Malli, X. Zhang, and C. Qiao, “Benefit of multicasting in all-optical networks,” Proc. SPIE, vol. 3531, pp. 209–220, Nov. 1998.
  9. 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.
  10. R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., The IBM Research Symposia Series. New York: Plenum, 1972, pp. 85–103.
  11. A. Gadkar, J. Plante, and V. M. Vokkarane, “Multicast overlay for high-bandwidth applications over optical WDM networks,” J. Opt. Commun. Netw., vol.  4, no. 8, pp. 571–585, Aug. 2012.
    [CrossRef]
  12. J. Zheng and H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in Proc. IEEE Int. Conf. on Communications (ICC), Apr. 2002, pp. 2722–2726.
  13. T. Schöndienst, J. M. Plante, D. A. P. Davis, and V. M. Vokkarane, “Energy source-aware manycast overlay in WDM networks,” in Proc. IEEE Globecom, Atlanta, GA, Dec. 2013.
  14. N. Charbonneau and V. M. Vokkarane, “Static routing and wavelength assignment for multicast advance reservation in all-optical wavelength-routed WDM networks,” IEEE/ACM Trans. Netw., vol.  20, no. 1, pp. 1–14, 2012.
    [CrossRef]
  15. U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, “Efficient algorithms for interval graphs and circular-arc graphs,” Networks, vol.  12, no. 4, pp. 459–467, 1982.
    [CrossRef]
  16. T. Entel, A. Gadkar, and V. M. Vokkarane, “Scheduled multicast overlay for bandwidth-intensive applications,” in Proc. Int. Conf. on Optical Networking Design and Modeling (ONDM), Colchester, UK, 2012, pp. 1–6.
  17. T. Entel, A. Gadkar, and V. M. Vokkarane, “Dynamic advance reservation multicast overlay for slotted optical WDM networks,” in Proc. IEEE Globecom, Anaheim, CA, 2012, pp. 3007–3012.

2012 (2)

N. Charbonneau and V. M. Vokkarane, “Static routing and wavelength assignment for multicast advance reservation in all-optical wavelength-routed WDM networks,” IEEE/ACM Trans. Netw., vol.  20, no. 1, pp. 1–14, 2012.
[CrossRef]

A. Gadkar, J. Plante, and V. M. Vokkarane, “Multicast overlay for high-bandwidth applications over optical WDM networks,” J. Opt. Commun. Netw., vol.  4, no. 8, pp. 571–585, Aug. 2012.
[CrossRef]

2010 (1)

S. Lee, A. Chen, and M. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photon. Netw. Commun., vol.  19, no. 1, pp. 103–109, 2010.

2009 (1)

2006 (1)

N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol.  24, no. 8, pp. 2–15, Aug. 2006.

2000 (1)

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

1999 (1)

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.

1998 (1)

R. Malli, X. Zhang, and C. Qiao, “Benefit of multicasting in all-optical networks,” Proc. SPIE, vol. 3531, pp. 209–220, Nov. 1998.

1982 (1)

U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, “Efficient algorithms for interval graphs and circular-arc graphs,” Networks, vol.  12, no. 4, pp. 459–467, 1982.
[CrossRef]

Andrei, D.

Charbonneau, N.

N. Charbonneau and V. M. Vokkarane, “Static routing and wavelength assignment for multicast advance reservation in all-optical wavelength-routed WDM networks,” IEEE/ACM Trans. Netw., vol.  20, no. 1, pp. 1–14, 2012.
[CrossRef]

Chen, A.

S. Lee, A. Chen, and M. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photon. Netw. Commun., vol.  19, no. 1, pp. 103–109, 2010.

Davis, D. A. P.

T. Schöndienst, J. M. Plante, D. A. P. Davis, and V. M. Vokkarane, “Energy source-aware manycast overlay in WDM networks,” in Proc. IEEE Globecom, Atlanta, GA, Dec. 2013.

Entel, T.

T. Entel, A. Gadkar, and V. M. Vokkarane, “Scheduled multicast overlay for bandwidth-intensive applications,” in Proc. Int. Conf. on Optical Networking Design and Modeling (ONDM), Colchester, UK, 2012, pp. 1–6.

T. Entel, A. Gadkar, and V. M. Vokkarane, “Dynamic advance reservation multicast overlay for slotted optical WDM networks,” in Proc. IEEE Globecom, Anaheim, CA, 2012, pp. 3007–3012.

Gadkar, A.

A. Gadkar, J. Plante, and V. M. Vokkarane, “Multicast overlay for high-bandwidth applications over optical WDM networks,” J. Opt. Commun. Netw., vol.  4, no. 8, pp. 571–585, Aug. 2012.
[CrossRef]

T. Entel, A. Gadkar, and V. M. Vokkarane, “Dynamic advance reservation multicast overlay for slotted optical WDM networks,” in Proc. IEEE Globecom, Anaheim, CA, 2012, pp. 3007–3012.

T. Entel, A. Gadkar, and V. M. Vokkarane, “Scheduled multicast overlay for bandwidth-intensive applications,” in Proc. Int. Conf. on Optical Networking Design and Modeling (ONDM), Colchester, UK, 2012, pp. 1–6.

Gupta, U. I.

U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, “Efficient algorithms for interval graphs and circular-arc graphs,” Networks, vol.  12, no. 4, pp. 459–467, 1982.
[CrossRef]

Jue, J. P.

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

Karp, R. M.

R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., The IBM Research Symposia Series. New York: Plenum, 1972, pp. 85–103.

Lee, D. T.

U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, “Efficient algorithms for interval graphs and circular-arc graphs,” Networks, vol.  12, no. 4, pp. 459–467, 1982.
[CrossRef]

Lee, S.

S. Lee, A. Chen, and M. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photon. Netw. Commun., vol.  19, no. 1, pp. 103–109, 2010.

Leung, J. Y.-T.

U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, “Efficient algorithms for interval graphs and circular-arc graphs,” Networks, vol.  12, no. 4, pp. 459–467, 1982.
[CrossRef]

Luo, X.

X. Luo and B. Wang, “Service provisioning under a scheduled traffic model using light-trails in WDM optical networks,” in Proc. IEEE BROADNETS, Sept. 2007, pp. 385–393.

Malli, R.

R. Malli, X. Zhang, and C. Qiao, “Benefit of multicasting in all-optical networks,” Proc. SPIE, vol. 3531, pp. 209–220, Nov. 1998.

Martel, C. U.

Mouftah, H. T.

J. Zheng and H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in Proc. IEEE Int. Conf. on Communications (ICC), Apr. 2002, pp. 2722–2726.

Mukherjee, B.

D. Andrei, H.-H. Yen, M. Tornatore, C. U. Martel, and B. Mukherjee, “Integrated provisioning of sliding scheduled services over WDM optical networks [Invited],” J. Opt. Commun. Netw., vol.  1, no. 2, pp. A94–A105, July 2009.
[CrossRef]

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

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.

Plante, J.

Plante, J. M.

T. Schöndienst, J. M. Plante, D. A. P. Davis, and V. M. Vokkarane, “Energy source-aware manycast overlay in WDM networks,” in Proc. IEEE Globecom, Atlanta, GA, Dec. 2013.

Qiao, C.

R. Malli, X. Zhang, and C. Qiao, “Benefit of multicasting in all-optical networks,” Proc. SPIE, vol. 3531, pp. 209–220, Nov. 1998.

Sahasrabuddhe, L. H.

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.

Schöndienst, T.

T. Schöndienst, J. M. Plante, D. A. P. Davis, and V. M. Vokkarane, “Energy source-aware manycast overlay in WDM networks,” in Proc. IEEE Globecom, Atlanta, GA, Dec. 2013.

Skorin-Kapov, N.

N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol.  24, no. 8, pp. 2–15, Aug. 2006.

Tornatore, M.

Vokkarane, V. M.

A. Gadkar, J. Plante, and V. M. Vokkarane, “Multicast overlay for high-bandwidth applications over optical WDM networks,” J. Opt. Commun. Netw., vol.  4, no. 8, pp. 571–585, Aug. 2012.
[CrossRef]

N. Charbonneau and V. M. Vokkarane, “Static routing and wavelength assignment for multicast advance reservation in all-optical wavelength-routed WDM networks,” IEEE/ACM Trans. Netw., vol.  20, no. 1, pp. 1–14, 2012.
[CrossRef]

T. Schöndienst, J. M. Plante, D. A. P. Davis, and V. M. Vokkarane, “Energy source-aware manycast overlay in WDM networks,” in Proc. IEEE Globecom, Atlanta, GA, Dec. 2013.

T. Entel, A. Gadkar, and V. M. Vokkarane, “Dynamic advance reservation multicast overlay for slotted optical WDM networks,” in Proc. IEEE Globecom, Anaheim, CA, 2012, pp. 3007–3012.

T. Entel, A. Gadkar, and V. M. Vokkarane, “Scheduled multicast overlay for bandwidth-intensive applications,” in Proc. Int. Conf. on Optical Networking Design and Modeling (ONDM), Colchester, UK, 2012, pp. 1–6.

Wang, B.

X. Luo and B. Wang, “Service provisioning under a scheduled traffic model using light-trails in WDM optical networks,” in Proc. IEEE BROADNETS, Sept. 2007, pp. 385–393.

Yen, H.-H.

Yuang, M.

S. Lee, A. Chen, and M. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photon. Netw. Commun., vol.  19, no. 1, pp. 103–109, 2010.

Zang, H.

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

Zhang, X.

R. Malli, X. Zhang, and C. Qiao, “Benefit of multicasting in all-optical networks,” Proc. SPIE, vol. 3531, pp. 209–220, Nov. 1998.

Zheng, J.

J. Zheng and H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in Proc. IEEE Int. Conf. on Communications (ICC), Apr. 2002, pp. 2722–2726.

IEEE Commun. Mag. (1)

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.

IEEE J. Sel. Areas Commun. (1)

N. Skorin-Kapov, “Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,” IEEE J. Sel. Areas Commun., vol.  24, no. 8, pp. 2–15, Aug. 2006.

IEEE/ACM Trans. Netw. (1)

N. Charbonneau and V. M. Vokkarane, “Static routing and wavelength assignment for multicast advance reservation in all-optical wavelength-routed WDM networks,” IEEE/ACM Trans. Netw., vol.  20, no. 1, pp. 1–14, 2012.
[CrossRef]

J. Opt. Commun. Netw. (2)

Networks (1)

U. I. Gupta, D. T. Lee, and J. Y.-T. Leung, “Efficient algorithms for interval graphs and circular-arc graphs,” Networks, vol.  12, no. 4, pp. 459–467, 1982.
[CrossRef]

Opt. Netw. Mag. (1)

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

Photon. Netw. Commun. (1)

S. Lee, A. Chen, and M. Yuang, “A Lagrangean relaxation based near-optimal algorithm for advance lightpath reservation in WDM networks,” Photon. Netw. Commun., vol.  19, no. 1, pp. 103–109, 2010.

Proc. SPIE (1)

R. Malli, X. Zhang, and C. Qiao, “Benefit of multicasting in all-optical networks,” Proc. SPIE, vol. 3531, pp. 209–220, Nov. 1998.

Other (8)

W. E. Johnston, ESnet4: Networking for the future of DOE science, 2008 [Online]. Available: http://www.es.net/assets/Uploads/ESnet4-Networking-for-the-Future-of-Science-2008-05-05.NP.v1.pdf .

T. Entel, A. Gadkar, and V. M. Vokkarane, “Scheduled multicast overlay for bandwidth-intensive applications,” in Proc. Int. Conf. on Optical Networking Design and Modeling (ONDM), Colchester, UK, 2012, pp. 1–6.

T. Entel, A. Gadkar, and V. M. Vokkarane, “Dynamic advance reservation multicast overlay for slotted optical WDM networks,” in Proc. IEEE Globecom, Anaheim, CA, 2012, pp. 3007–3012.

Worldwide LHC Computing Grid, 2013 [Online]. Available: http://lcg.web.cern.ch/lcg/ .

X. Luo and B. Wang, “Service provisioning under a scheduled traffic model using light-trails in WDM optical networks,” in Proc. IEEE BROADNETS, Sept. 2007, pp. 385–393.

R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., The IBM Research Symposia Series. New York: Plenum, 1972, pp. 85–103.

J. Zheng and H. T. Mouftah, “Routing and wavelength assignment for advance reservation in wavelength-routed WDM optical networks,” in Proc. IEEE Int. Conf. on Communications (ICC), Apr. 2002, pp. 2722–2726.

T. Schöndienst, J. M. Plante, D. A. P. Davis, and V. M. Vokkarane, “Energy source-aware manycast overlay in WDM networks,” in Proc. IEEE Globecom, Atlanta, GA, Dec. 2013.

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

Fig. 1.
Fig. 1.

Illustration: number of wavelengths required to satisfy the scheduled multicast requests of Table I using (a) MVWU and (b) MI-DMN. The corresponding logical overlays are (c) MVWU and (d) MI-DMN.

Fig. 2.
Fig. 2.

Provisioning the multicast requests of Table II by MVWU: (a) physical layer routing at time instance I1 and (b) physical layer routing at time instance I2. The corresponding logical overlays: (c) time instance I1 and (d) time instance I2.

Fig. 3.
Fig. 3.

Provisioning the multicast requests of Table II by MI-DMN: (a) physical layer routing at time instance I1 and (b) physical layer routing at time instance I2. The corresponding logical overlays: (c) time instance I1 and (d) time instance I2.

Fig. 4.
Fig. 4.

SPO overlay-trees for the multicast request R1 of Table III. (a) Initial logical hop to node 1, (b) initial logical hop to node 3, (c) initial logical hop to node 5, and (d) reserved physical hops in network after R1 is provisioned, using minimum tree shown in (c).

Fig. 5.
Fig. 5.

SPO overlay-trees for the multicast request R2 of Table III. (a) Initial logical hop to node 1, (b) initial logical hop to node 3, (c) initial logical hop to node 4, and (d) reserved physical hops in network after R2 is provisioned, using minimum tree shown in (c).

Fig. 6.
Fig. 6.

SPO overlay-trees for the multicast request R3 of Table III. (a) Initial logical hop to node 3, (b) initial logical hop to node 4, (c) initial logical hop to node 5, and (d) reserved physical hops in network after R3 is provisioned, using maximum trees for all three requests.

Fig. 7.
Fig. 7.

Performance evaluations of ILPs and MOS+SPO for the proposed overlay models. K=3, γ(R¯)=0.7. (a) Wavelength consumption and (b) execution overhead.

Fig. 8.
Fig. 8.

Network topologies used for heuristic evaluation. (a) 14-node NSFnet and (b) 18-node Pan-European network.

Fig. 9.
Fig. 9.

Relative performance evaluation of MOS+SPO heuristics for all three overlay models. K=3, γ(R¯)=0.7. (a) NSFnet topololgy and (b) Pan-European topology.

Fig. 10.
Fig. 10.

Performance evaluation of SPO overlay approximations on the NSFnet topology. (a) Request blocking, (b) logical hop hunt, and (c) maximum logical hop hunt.

Fig. 11.
Fig. 11.

Blocking performance comparison of MI-DMN on the NSFnet topology using different tree-selection criteria.

Tables (6)

Tables Icon

Table I Example Set of Static Multicast AR Requests

Tables Icon

Table II Example Set of Dynamic Multicast AR Requests

Tables Icon

Algorithm 1 Multicast Overlay Scheduler

Tables Icon

Algorithm 2 Shortest Path Overlay

Tables Icon

Table III Example Set of Dynamic Multicast AR Requests

Tables Icon

Table IV Comparison of Average Number of Logical Hops

Equations (21)

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

minimize MaxIndex
MaxIndexLu,vr,w×wrR¯,u,vN¯,wW¯,
wLu,vr,w=Tu,vrrR¯,u,vN¯,
uvFu,v,i,jr1,w+Fu,v,i,jr2,w+Or1,r22r1,r2R¯,i,j,w,
Fu,v,i,jr,wAij×Lu,vr,wu,v,i,jN¯,wW¯,
iFu,v,i,jr,wkFu,v,j,kr,w={0ifju,vLu,vr,wifj=vLu,vr,wifj=u,
minimize:MaxIndex
MaxIndexCwr×wrR¯,wW¯,
wCwr1rR¯,
Lu,vr,wCwrrR¯,wW¯,u,vN¯,
wvLsr,vr,w1rR¯,
wvLv,ur,w=1rR¯,uDr,
wvLv,srr,w=0rR¯,
wvLu,vr,w=0rR¯,uDr,
wvLv,ur,w=0rR¯,uDr,u=sr,
XurXvr+|N|×Lu,vr,w|N|1rR¯,wW¯,u,vN¯.
uwLu,vr,w1rR¯,usr,
vwLu,vr,w|N|×vwLv,ur,w0rR¯,usr,
uwLu,vr,wuwLv,ur,w0rR¯,vDr.
f=Δ·w+(1Δ)·l.
γ(R¯)=rR¯c(r,R¯)|R¯|·(|R¯|1).