Research On Wavelength Assignment And Network Embedding Based On WDM Double Loop Networks

The traditional communication technology has been difficult to satisfy the growth of information capacity. Then many new communication technologies disappeared. All-optical communication is one of those technologies, and the WDM (Wavelength Division Multiplexing) technology has been widely studied and selected as the key technology for the next generation network, because of its advantages such as high bandwidth and low delay.Because of the technical limitation, the wavelengths become the most precious resources of all-optical networks. With the development of WDM technology, we can take full advantages 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 networks. Thus, the parallel network topologies can be considerably simplified. Wavelength assignment is a key topic in optical WDM 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. The network embedding is also a key topic of interconnection networks. Highly effective embeddings can improve the operating efficiency of parallel programs.DLN(Double-Loop Network) is an important interconnection network topology, which has many advantages such as simplicity, symmetry, extension. And it has better fault-tolerance and few average communication time.In this paper, we discussed the wavelength assignments of embedding several parallel communication patterns on the double-loop network, including the problem of parallel Matrix Multiplication for numerical analysis domain, Fast Fourier Transform for the digital signal processing and image processing, BP algorithm and Hopfield algorithm in artificial neural networks. The network embedding is also discussed in the last chapter of this paper, including embedding double-loop network onto RP(k) and embedding mesh onto double-loop network.The main achievements of this thesis can be summarized as follows: (1) Based on the WDM double-loop network, the ddd algorithm of parallel Matrix Multiplication is analyzed. The algorithm MRDR is designed and the wavelength assignment of realizing this communication pattern on WDM double-loop network is discussed. And the minimum number of wavelengths required realizing this communication pattern on WDM double-loop network is 2.(2) An recursive mapping algorithm FFT-DLN is given, and based on generative mapping, folio mapping, sequential mapping and reversal mapping, wavelength assignments of realizing parallel FFT communication patterns on WDM double-loop network are discussed and the wavelength numbers required is N/8. And through analysis, we find that folio mapping and reversal mapping have few performing time with the same network scale.(3) Based on WDM double-loop network, wavelength assignments of realizing Hopfield network on WDM double-loop network are discussed. The communication pattern of parallel Hopfield Cn is introduced. By embedding the complete graph Cn into the optical WDM double-loop network, the wavelength assignment algorithms are designed and the numbers of wavelengths required realizing Hopfield network on WDM double-loop network are given.(4) Based on the WDM double-loop network, the wavelength assignment of realizing parallel BP algorithm in WDM double-loop network 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 double-loop network, a routing and wavelength assignment algorithm is proposed, and the results are analyzed via simulation.(5) The structure of double-loop network is designed. An algorithm of embeddings of mesh onto double-loop network is proposed, and the values of four parameters (expansion, load factor, dilation, congestion) is given, that is 1, 1, 1, 1, which is optimal.(6) The architecture of the 10*k double-loop network is designed, and the algorithm DLN-RP(k) about the embeddings of double-loop network into RP(k) is proposed. The values of four parameters (expansion, load factor, dilation, congestion) is given, that is 1, 1, 2, 2, and proven to be optimal.