Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Journal of Information Science and Engineering, Vol.18 No.6, pp.1049-1058 (November 2002)


Multicasts on WDM All-Optical Butterfly Networks*

Xinchen Liu and Qian-Ping Gu+
Department of Computer Science and Engineering
The University of Aizu
Fukushima, 965-8580 Japan
+School of Computing Science
Simon Fraser University
Burnaby B.C. Canada V5A 1S6
E-mail: qgu@cs.sfu.ca

On the wavelength-division multiplexing (WDM) optical networks, when the number of wavelengths for realizing a set R of routing requests is beyond the number of wavelengths supported by an optical link, multiple rounds of routing for R are required. R = {(u, v)} is a set of multicasts if each source u sends a message to at least one destination v and each destination v receives a message from exactly one source u. In this paper, we propose routing algorithms for a set of multicasts on n-dimensional WDM all-optical butterfly networks. For a network with wavelength converters, we give algorithms which realize any set of multicasts by 2?(n-1)/(k+1)? wavelengths in k rounds of routing. For k = 1, the upper bound is tight to the lower bound.

Keywords: multicast, WDM all-optical networks, multi-hop routing, multistage interconnection networks, off-line routing algorithms

Full Text () Retrieve PDF document (200211_12.pdf)

Received July 31, 2001; accepted April 15, 2002.
Communicated by Jang-Ping Sheu, Makoto Takizawa and Myongsoon Park.
*The preliminary version of the paper appeared in the Proceedings of the 8th International Conference on Parallel and Distributed Systems (ICPADS '01).