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.