loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2001 International Conference on Parallel Processing Workshops (ICPPW'01)
Multi-hop All-to-All Broadcast on WDM Optical Networks
Valencia, Spain
September 03-September 07
ISBN: 0-7695-1260-7
Qian-Ping Gu, University of Aizu
Shietung Peng, Hosei University
Abstract: It is known that the minimum number of wavelengths for realizing all-to-all broadcast (gossiping) in one-hop of optical routing on the ring (resp. the 2-dimensional torus) of N nodes is \lceil\lfloorN^2/4\rfloor/2\rceil (resp. cN^{1+1/2}, c\approx 1/8). These numbers can be too large even for moderate values of N. One approach to reduce the number of wavelengths is to realize gossiping in multi-hops of routing. We prove that gossiping can be realized in k-hops by c_kN^{1+1/k} (ck\approx 1/2^{2+1.k}) wavelengths on the ring, c^{\prime} N^{1+1/(2k)} (c^{\prime}\approx 1/4) wavelengths on the 2-dimensional torus, and c^{\prime} N^{1+1/(3k)} wavelengths on the 3-dimensional torus on the simple model: in the (j + 1)st hop each node just forwards each message received in the jth hop to its next destinations. We also give the upperbounds on the numbers of wavelengths for gossiping in two-hops and three-hops for the ring, 2-dimensional torus, and 3- dimensional torus on the merge model: in the (j +1)st hop each node can merge different messages received in the jth hop into one and sends the merged message to its next destinations.
Index Terms:
All-to-all communication, WDM optical networks, torus.
Citation:
Qian-Ping Gu, Shietung Peng, "Multi-hop All-to-All Broadcast on WDM Optical Networks," icppw, pp.0291, 2001 International Conference on Parallel Processing Workshops (ICPPW'01), 2001
Usage of this product signifies your acceptance of the Terms of Use.