On the Complexity of Virtual Topology Design for Multicasting in WDM Trees With Tap-and-Continue and Multicast-Capable Switches

Student Co-author

HMC Undergraduate

Document Type



Computer Science (HMC)

Publication Date



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