Optimal Bandwidth Utilization of All-Optical Ring with a Converter of Degree 4

In many models of all-optical routing, a set of communication paths in a network is given, and a wavelength is to be assigned to each path so that paths sharing an edge receive different wavelengths. The goal is to assign as few wavelengths as possible, in order to use the optical bandwidth efficiently. If a node of a network contains a wavelength converter, any path that passes through this node may change its wavelength. Having converters at some of the nodes can reduce the number of wavelengths required for routing. This paper presents a wavelength converter with degree 4 and gives a routing algorithm which shows that any routing with loadL can be realized withL wavelengths when a node of an all-optical ring hosts such a wavelength converter. It is also proved that 4 is the minimum degree of the converter to reach the full utilization of the available wavelengths if only one node of an all-optical ring hosts a converter. Supported by the NKBRSF of China on the NP-Complete Problem and High Performance Software (Grant No.G1998030403). XU Yinlong was born in 1963. He received the B.S degree in mathematics from the Peking University in 1983, and the M.S. degree in computer science from the University of Science and Technology of China (USTC) in 1989. Now he is an associate professor in the Department of Computer Science at USTC. His current research interests include parallel computing and combinatorial optimization. CHEN Guoliang was born in 1938. Now he is a professor and Ph.D. supervisor in the Department of Computer Science at USTC. His current research interests include parallel computing, computer architecture and combinatorial optimization. HUANG Liusheng was born in 1957. He received the B.S. and M.S. degrees in computer software from Anhui University and USTC in 1982 and 1988 respectively. He is now a professor and director of the Department of Computer Science at USTC, a vice-director of the National High Performance Computing Center at Hefei. His main research interests include OODB, parallel and distributed computing and intelligent algorithms. WAN Yingyu was born in 1975. He received the B.S. degree in computer science from USTC in 1997. Now he is a. Ph.D. candidate in computer science at USTC. His current research interests include parallel computing and combinatorial optimization.