On the Complexity of Virtual Topology Design for Multicasting in WDM Trees With Tap-and-Continue and Multicast-Capable Switches
Document Type
Article
Department
Computer Science (HMC)
Publication Date
2004
Abstract
This paper investigates the problem of finding optimal multicast virtual topologies, with respect to minimizing the maximum hop distance, in wavelength-division multiplexing 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 lightpath 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.
Rights Information
© 2004 IEEE Communications Society
DOI
10.1109/JSAC.2004.833853
Recommended Citation
E. Miller, R. Libeskind-Hadas, D. Barnard, W. Chang, K. Dresner, W. 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 Jour- nal on Selected Areas in Communications, Optical Communications and Networking Series, Vol. 22, No. 9, November 2004, pp. 1601-1612. DOI: 10.1109/JSAC.2004.833853
