• Sorted by Date • Classified by Publication Type • Classified by Research Category •
E. Miller, R. Libeskind-Hadas, D. Barnard, W. Chang, K. Dresner, W. M. Turner, and J. R. Hartline. On The Complexity of Virtual Topology Design for Multicasting in WDM Trees With Tap-and-Continue and Multicast-Capable Switches. IEEE Journal on Selected Areas in Communications Special Series: Optical Communications and Networking, 22(9):1601–1612, 2004.
[PDF]309.5kB [gzipped postscript]501.5kB
This paper investigates the problem of finding optimal multicastvirtual topologies, with respect to minimizing the maximum hop distance,in WDM multicast trees. Although the problem of finding optimal multicasttrees is itself known to be NP-complete under many optimization metrics,high-quality approximation algorithms are known for this problem.We investigate the case that a multicast tree has been selected andseek to embed an optimal virtual topology in this multicast tree.We show that the problem can be solved in polynomial time when tap-and-continueswitches are employed which allow a light-path to be tapped by somenumber of intermediate nodes. However, the problem becomes NP-completewhen fully multicast-capable switches are employed. Our results suggestthat tap-and-continue switches can be used to obtain high qualitymulticast virtual topologies while heuristics will be required tofind good solutions in fully multicast-capable networks.
@ARTICLE{IEEE-JSAC-OCN-miller,
author = {E.\ Miller and R.\ Libeskind-Hadas and D.\ Barnard and W.\ Chang
and K.\ Dresner and W.\ M.\ Turner and J.\ R.\ Hartline},
title = {On The Complexity of Virtual Topology Design for Multicasting in
WDM Trees With Tap-and-Continue and Multicast-Capable Switches},
journal = {IEEE Journal on Selected Areas in Communications Special Series:
Optical Communications and Networking},
year = {2004},
volume = {22},
pages = {1601-1612},
number = {9},
abstract = {
This paper investigates the problem of finding optimal multicast
virtual topologies, with respect to minimizing the maximum hop distance,
in WDM multicast trees. Although the problem of finding optimal multicast
trees is itself known to be NP-complete under many optimization metrics,
high-quality approximation algorithms are known for this problem.
We investigate the case that a multicast tree has been selected and
seek to embed an optimal virtual topology in this multicast tree.
We show that the problem can be solved in polynomial time when tap-and-continue
switches are employed which allow a light-path to be tapped by some
number of intermediate nodes. However, the problem becomes NP-complete
when fully multicast-capable switches are employed. Our results suggest
that tap-and-continue switches can be used to obtain high quality
multicast virtual topologies while heuristics will be required to
find good solutions in fully multicast-capable networks.},
bib2html_rescat = {Optical Routing},
bib2html_pubtype = {Journal}
}
Generated by bib2html (written by Patrick Riley ) on Wed Jul 02, 2008 11:31:21