【作者】 陈亚文；

【导师】 刘方爱；

【作者基本信息】 山东师范大学 ， 管理科学与工程， 2004， 硕士

【摘要】 随着光通信技术的发展，基于波分复用（Wavelength Division Multiplexing，简称WDM）技术的全光网络已成为了通信网络研究的重要方向，由于这种网络具有高带宽、低延迟等优点，被认为是下一代网络的关键技术，所以它得到了广泛的研究。 随着波分复用技术的发展，如果能够充分利用单根光纤中可以同时传输多路波长信号的特性，把较为复杂的通信模式嵌入在简单的光互连网络中，可以通过优化设计大大简化互连网络的结构。波长分配是光网络设计的基本问题，这类问题的目的是为了提高光网络中波长的利用率和改善整个网络的性能，该问题在大多数网络结构中都是NP难的，并且与图的着色问题有着很强的关系，所以对于这类问题的研究在理论计算机科学的研究方面具有重要的价值。 光互连网络作为并行体系结构的通信网络将是必然的趋势。不同的并行算法具有不同的通信模式，如何在光互连网上实现这些通信模式，是当前一个颇受关注的研究领域。本文就几个重要并行算法的通信模式嵌入在光网络上的波长分配问题作了初步的讨论，其中包括科学和工程领域求解线性方程组的LU分解问题、在数字信号处理及图像处理等领域中广泛应用的快速傅里叶变换FFT、人工神经网络中的BP算法和Hopfield算法。本文的最后一章对动态路由全光网络中的波长预留协议给出了一些改进的策略。 本文做的主要研究工作如下：① 基于WDM环网络，针对矩阵的并行LU分解，构造了一种并行LU分解的通信模式，讨论了将该通信模式嵌入在环形光网络中的波长分配问题。在解决该问题的过程中，得到了将一种特殊的二分图结构的通信模式嵌入在环网中的波长分配算法。通过分析和证明得出结论：在有n²个节点的WDM环网上，实现该并行LU分解通信模式所需的最小波长数为n²/4（n为偶数）或（n²-3）/4（n为奇数）。② 基于顺序映射和移位逆序映射两种不同的嵌入方式，分析了在一组规则WDM光网络上实现并行FFT的通信模式所需的波长数。按照顺序映射方式，在有2ⁿ个节点的线性阵列、环、二维mesh和二维torus光网络上实现并行FFT的通信模式所需的波长数分别为2^n-1、2^n-1、2^{max（k,n-k）-1}和2^{max（k,n-k）-1}；按照移位逆序映射方式，在上述光网络上实现该通信模式所需的波长数分别为max(3×2^n-3，2)、2^n-2、max(3×2^{max（k，n-k）-3}，2)和2^{max（k，n-k）-2}。结论表明：将并行FFT的通信模式嵌入在上述规则WDM光网络上，采用移位逆序映射方式比采用顺序映射方式所需的波长数少。③ 基于WDM环网络，讨论了在其上实现并行BP算法的波长分配问题，设计了将完全二分图结构K_m，n通信模式嵌入环网的方案，给出了在WDM环网络上实现并行BP算法所需的最小波长数。④ 将并行Hopfield算法的通信模式抽象为C_n通信模式，给出了在线性阵列和环形WDM光互连网络及基于光互连的波长分配优化研究网络上实现Cn通信模式所需波长数的下限值，分别设计了将Cn通信模式嵌入在线性和环形WDM光网络上的波长分配方案并给出了在该方案下实现H叩field网络所需的波长数。⑤讨论了将全互连网络嵌入在线性阵列、环、二维mesh和二维torus光网络中的波长分配 问题，设计了将全互连网络嵌入在上述WDM光网络中的波长分配方案并分别给出了所 需的波长数。⑥采用分布式波长预留协议建立光路连接可以提高wDM光网络的可靠性。分析和比较了 现有的分布式波长预留协议，指出了其中存在的问题，在此基础上提出改进的策略。通 过在NSFNET上进行计算机仿真试验，对不同的分布式波长预留协议和改进的方案进行 了比较，试验结果表明，改进的波长预留协议可以降低阻塞率。关键词:并行计算;光互连网络;波分复用;波长分配;网络嵌入分类号:仰393更多还原

【Abstract】 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更多还原