Multi-hop all-to-all broadcast on WDM optical networks

摘要

It is known that the minimum number of wavelengths for realizingall-to-all broadcast (gossiping) in one-hop of optical routing on thering (resp. the 2-dimensional torus) of N nodes is [[N²/4]/2](resp. cN^1+1/2,c≈1/8). These numbers can be too large evenfor moderate values of N. One approach to reduce the number ofwavelengths is to realize gossiping in multi-hops of routing. We provethat gossiping can be realized in k-hops byc_kN¹⁺¹k/(c_k≈1/2²⁺¹k/)wavelengths on the ring, c'N¹⁺¹(2k)/(c'≈1/4) wavelengthson the 2-dimensional torus, and c'^N1+1(3k)/ wavelengths onthe 3-dimensional torus on the simple model: in the (j+1)st hop eachnode just forwards each message received in the jth hop to its nextdestinations. We also give the upper bounds on the numbers ofwavelengths 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 jthhop into one and sends the merged message to its next destinations