Abstract
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.