Optical routing of uniform instances in tori .
F. Comellas (*), M. Mitjana (o), L. Narayanan (#)
and J. Opatrny (#)
(*) Departament de Matemàtica Aplicada i Telemàtica;
Universitat Politècnica de Catalunya, Barcelona, Catalonia, Spain
(o) Departament de Matemàtica Aplicada I;
Universitat Politècnica de Catalunya, Barcelona, Catalonia, Spain
(#) Department of Computer Science, Concordia University, Montreal, Quebec,
Canada
Mathematical Foundations of Computer Science 2000 ,
Lecture Notes in Computer Science, vol. 1893, pp. 285-294.
M. Nielsen and B. Rovan (Eds.).
ISBN 3-540-67901-4.
Springer Verlag, 2000.
We consider the problem of routing uniform communication
instances in switched optical tori that use the
wavelength division multiplexing (or WDM) approach.
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}.
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 $ relative to n for the wavelength index to be
equal to the load. When k>= 2, we show
that for any set S, there exists an n0, such that
for all n > n0,
there is an optimal wavelength assignment
for the communication instance specified by
S on the torus T n x n.
We also show an approximation for the wavelength index for any S and
n .
Finally, we give some results for rectangular tori.
Load a preprint version of the paper: