Abstract of Paper |

*Optical Routing of Uniform Instances in Tori*

by Francesc Comellas, Margarida Mitjana, Lata Narayanan, and Jaroslav Opatrny

**Abstract:**

We consider the problem of routing in switched optical tori that use the wavelength division multiplexing (or WDM) approach. Given a communication instance in a network, the optical routing problem is the assignment of routes to communication requests in the instance, as well as wavelengths to routes so that the assignment of wavelengths is conflict-free and the number of wavelengths used is minimal. We focus on uniform communication instances in tori, a widely studied and implemented class of networks. 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_1, d_2,\dots, d_k }$. We give bounds on the optimal load induced on an edge for any uniform instance in a torus $T_{n x n}$. When $k=1$, we prove necessary and sufficient conditions on the value in $S$ relative to $n$ for the wavelength index to be equal to the load. When $k=2$, we show that for any $d_1$, $d_2$, there exists an $n_0$, such that for all $n>n_0$, there is an optimal wavelength assignment for the communication instance specified by $\{ d_1, d_2 \}$ on the torus $T_{n\times n}$. For general $k$, we show a similar result, and also show an approximation for the wavelength index for any $S$ and $n$. Finally, we give some results for rectangular tori.