Research On Interconnection Networks And Optimization For Wavelength Assignment Based On Optical Interconnection Networks

Recently, the all-optical networks using the WDM (Wavelength Division Multiplexing) technology have been the research focus. Because of its advantages such as high bandwidth and low delay, it has been widely studied and selected as the key technology for the next generation network.With the development of WDM technology, we can take full advantage of the parallel transmission characteristic of optical networks, which support multiple lightpaths in the single fiber, to embed the complex parallel communication patterns into optical interconnection networks. Thus, the parallel network topologies can be considerably simplified. Wavelength assignment is a key topic in optical WDM interconnection networks. The purpose of wavelength assignment is to increase the utilization of wavelength and improve the network performance. Wavelength assignment problem which is known to be NP-hard is relational to the chromatic problem. Therefore, this kind of problem is of great value for the research on computer science.Optical communication becomes a promising networking choice for the interconnections of parallel architectures. Since different parallel algorithms have different communication patterns, how to realize these communication patterns on optical interconnections is a hot research field. In this paper, we discussed the wavelength assignments of embedding several parallel communication patterns on the optical interconnection networks including the problem of LU decomposition for solving the linear equations, Fast Fourier Transform for the digital signal processing and image processing, BP algorithm and Hopfield algorithm in artificial neural networks. Wavelength reservation protocol in the dynamic all-optical networks is also discussed in the last chapter of this paper.The main achievements of this thesis can be summarized as follows:(1) Based on the WDM ring interconnection network, a kind of parallel LU decomposition communication pattern is designed and the wavelength assignment of realizing this communication pattern on WDM ring is discussed. By embedding the communication pattern of a special bipartite graph into the WDM ring interconnection network, an algorithm to embed the parallel LU decomposition communication pattern into the WDM ring is designed, and the minimum number of wavelengths required to realize this communication pattern on WDM ring with n2 nodes is n2/4 when n is even and (n2-3)/4 when n is odd.(2) Based on sequential mapping and shift-reversal mapping, wavelength assignments of realizing parallel FFT communication pattern on a class of regular optical WDM networks are discussed. By sequential mapping, the numbers of wavelengths required to realize this communication pattern with 2" nodes on WDM linear array, ring, 2D mesh and 2D torus are 2n-1, 2n-1 2max(k,n-k)-1 and 2max(k,n-k)-1 respectively. By shift-reversal mapping, thenumbers of wavelengths required on the WDM interconnection networks mentioned above are max(3 x 2n-22) , 2n-2 max(3 x 2max(k,n-)k-1 2) and 2max(k,n-k)-2 respectively. These results show that shift-reversal mapping outperforms sequential mapping.(3) Based on the WDM ring interconnection network, the wavelength assignment of realizing parallel BP algorithm in WDM ring is discussed due to the parallel nature of the information processing in ANNs. By embedding the communication pattern of the complete bipartite graph Km,n into the WDM ring, the minimum number of wavelengths needed to realize parallel BP algorithm on WDM ring is given.(4) Based on WDM linear array and WDM ring, wavelength assignments of realizing Hopfield network on WDM linear array and WDM ring are discussed. The communication pattern of parallel Hopfield Cn is constructed. By embedding the complete graph Cn into the simple optical WDM interconnection networks, the wavelength assignment algorithms are designed and the numbers of wavelengths required realizing Hopfield network on WDM linear array and WDM ring are given.(5) The wavelength assignments of complete topology embedded in WDM interconnection networks of lin...