On the Complexity of Virtual Topology Design for Multicasting in WDM Trees With Tap-and-Continue and Multicast-Capable Switches
Computer Science (HMC)
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.
© 2004 IEEE Communications Society
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