A Study Of Routing And Wavelength Assignment Problem On WDM Optical Networks

With the ever increasing number and speed of processors in massive parallelcomputing systems, the relevant communication overhead is also rising up rapidly. Asthus, an effective communication network is needed for realizing rapid data exchangebetween processors. Thus, high-speed and high-capacity interconnection network isrequired. Due to intrinsic limitations in bandwidth and power dissipation, electricalinterconnections cannot meet the above requirements. Due to appealing properties suchas extremely high bandwidth, extremely low power consumption and extremely lowtime delay, optical interconnections have been widely regarded as a promisingalternative to electrical interconnections in realizing the next generation communicationnetworks.Wavelength division multiplexing (WDM) is one of the key techniques forimplementing optical communications; its core idea is to divide the bandwidth of asingle optical fiber into multiple communication channels, each represented by aseparate wavelength, so that a multiplicity of data streams can be transmittedsimultaneously across a same optical fiber. The so-called embedding of acommunication pattern in a WDM network is (1) to map each subtask in thecommunication pattern onto a node in the WDM network, and (2) to assign a dedicatedlightpath for each pair of subtasks that need to exchange data directly. One importantissue in the area of parallel computing is to embed typical communication patterns intypical WDM networks so as to achieve a high communication efficiency. Aswavelengths are invaluable resources, it is desired that the number of wavelengthsrequired by an embedding scheme is minimized, and the corresponding problem isknown as the routing and wavelength assignment (RWA) problem.Hypercubes, generalized cubes, and locally twisted cubes are all typicalcommunications, and linear arrays are typical WDM network topologies. This thesisaddresses the issues of embedding these communication patterns into linear arrays ofthe same size. The major contributions are presented below.(1) The static embedding problem of locally twisted cubes in linear arrays isstudied. Specifically, an embedding scheme is proposed, and its optimality in thenumber of wavelengths is proved. The corresponding wavelength assignment strategy isalso described. (2) The static embedding problem of generalized cubes in linear arrays isinvestigated. Specifically, the optimality of the natural numbering scheme is shown, andthe resulting congestions on all optical fibers are determined. On this basis, theembedding problems of crossed cubes in linear arrays under half duplex and full duplexmodes are addressed. Specifically, two optimal embedding schemes, one for each mode,are presented, and the corresponding wavelength assignment strategies are formulated.(3) The dynamic realization problem of the hypercube-based bitonic sorting onlinear arrays. Specifically, the notions of dimension congestion and dimensionembedding are introduced, and two novel dimension embedding schemes of hypercubesin linear arrays are developed. Theoretical analysis shows that the number ofwavelengths consumed by either of the two schemes is much less than that required byan optimal static embedding scheme of the same description.(4) The problem of implementing bitonic sorting on Optical Bus Network-on-Chipis attacked. Specifically, based on a novel wavelength assignment scheme for bitonicmerging, a wavelength assignment scheme for bitonic sorting of n elements is suggested,and the total number of wavelengths required is shown to be n/2.Finally, this work is summarized, and an outlook for further study is presented.