×

Optical routing of uniform instances in tori. (English) Zbl 0996.90017

Nielsen, Mogens (ed.) et al., Mathematical foundations of computer science 2000. 25th international symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1893, 285-294 (2000).
Summary: We consider the problem of routing uniform communication instances in switched optical tori that use the wavelength division multiplexing 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=\{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\times 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\geq 2\), we show that for any set \(S\), there exists an \(n_0\), such that for all \(n>n_0\), there is an optimal wavelength assignment for the communication instance specified by \(S\) on the torus \(T_{n\times n}\). We also show an approximation for the wavelength index for any \(S\) and \(n\). Finally, we give some results for rectangular tori.
For the entire collection see [Zbl 0944.00070].

MSC:

90B18 Communication networks in operations research
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite