Abstract of Paper

Optical Routing of Uniform Instances in Tori
by Francesc Comellas, Margarida Mitjana, Lata Narayanan, and Jaroslav Opatrny


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.