Uniform multi-hop all-to-all optical routings in rings

AbstractWe consider all-to-all routing problem in an optical ring network that uses the wavelength-division multiplexing (WDM). Since 1-hop, all-to-all optical routing in a WDM optical ring of n nodes needs ⌈12⌊n2/4⌋⌉ wavelengths (see Efficient Collective Communication in Optical Networks, Lecture Notes in Computer Science, Vol. 1099, Springer, Berlin, 1996, pp. 574–585), which can be too large even for moderate values of n, we consider in this paper j-hop implementations of all-to-all routing in a WDM optical ring, j⩾2. From among the possible routings we focus our attention on uniform routings, in which each node of the ring uses the same communication pattern and the communication load is distributed evenly among the nodes. We show that there exists a uniform 2-hop implementation of all-to-all routing that needs at most (n/4)(n3+3) wavelengths. This value is within multiplicative constants of a lower bound. We then give a uniform 3-hop, 4-hop implementation of all-to-all routing that needs at most (n/2)(n/167+3), (n/2)(n/215+6) wavelengths, respectively