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={d₁,d₂,…,d_k}. 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 R_n. When k=2, we show that for any uniform instance specified by {d₁,d₂}, there is an optimal wavelength assignment on the ring R_n, if n>(d₁/q-2)d₁+(d₁/q-1)d₂, where q=GCD(d₁,d₂). For general k and n, we show a -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.