Wavelength routing of uniform instances in all-optical rings

We consider the problem of routing uniform communication instances in switched optical rings that use wavelength-division multiplexing technology. A communication instance is called uniform if it consists exactly of all pairs of nodes in the graph whose distance is equal to one from a specified set S={d1,d2,…,dk}. When k=1 or 2, we prove necessary and sufficient conditions on the values in S relative to n for the optimal wavelength index to be equal to the optimal load in the ring Rn. When k=2, we show that for any uniform instance specified by {d1,d2}, there is an optimal wavelength assignment on the ring Rn, if n>(d1/q-2)d1+(d1/q-1)d2, where q=GCD(d1,d2). For general k and n, we show a (32)-approximation for the optimal wavelength index; this is the best possible for arbitrary S. We also show that an optimal assignment can always be obtained provided n is large enough compared to the values in S.