波分复用光网络中的路由与波长分配问题研究

发布时间：2018-11-12 19:00

【摘要】：随着大规模并行计算系统中处理器数目的增加和处理速度的加快，整个系统的通信开销也在急剧增长，因而需要有效的通信网络来实现处理器之间的快速通信。传统的电互连由于带宽、时延、能耗等方面的缺陷，无法满足大规模并行计算机通信的需求。光互连由于具有极高的传输带宽、极低的传输时延以及极低的功耗等优良的特性，成为大规模并行计算机的新一代通信网络。波分复用（WDM）是光通信的关键技术之一，其核心思想，是将同一条光纤按照波长划分成多个信道，可以同时传输多个光信号。所谓将通信模式嵌入WDM光网络，就是将通信模式中的每个子任务映射到网络中的某个结点，并为每对需要直接通信的结点分配一条光路，使得经过同一条光纤的所有光路具有不同的波长。并行计算的一个重要课题，就是将各种典型通信模式有效地嵌入各种典型WDM光网络，，实现高效率通信。由于波长是极为宝贵的资源，这就要求我们寻找所需波长数最少的波长分配方案，这就是WDM光网络上的波长分配问题。超立方体、交叉立方体以及局部扭曲立方体都是典型通信模式，线性阵列则是典型的WDM网络拓扑。本文主要研究如何将上述通信模式嵌入线性阵列光网络，使得所需波长数最小。具体研究成果如下：（1）研究了如何将局部扭曲立方体静态地嵌入线性阵列。提出了一个具体的嵌入方案，运用最大导出子图技术证明了该方案的最优性，并且给出了相应的波长分配算法，使得所需波长数达到最小。（2）研究了如何将广义立方体静态地嵌入线性阵列。提出了自然嵌入方案，证明了该方案的最优性，并确定了阵列中每条边的拥塞度。在此基础上，研究了交叉立方体的半双工和全双工通信模式在线性阵列上的路由和波长分配问题，证明了自然嵌入方案在两种通信模式下均具有最小波长数，并且给出了相应的波长分配算法。（3）研究了如何将基于超立方体的双调排序动态地嵌入线性阵列。根据双调排序的特点提出了维嵌入的概念，由此提出了两个嵌入方案，并对其所需波长数进行了分析，结果表明，这两种波长分配方案所需波长数明显小于最优的静态波长分配方案。（4）研究了如何将双调排序算法嵌入片上光总线网络。针对双调归并操作的特点，提出了一个波长分配方案，进而提出了对n个元素的无序序列进行双调排序的波长分配方案，证明了该方案所需波长数是n2。最后，对本文工作进行了总结，并对后续研究进行了展望。
[Abstract]:With the increase of processor number and processing speed in large scale parallel computing system, the communication overhead of the whole system is also increasing rapidly. Therefore, effective communication network is needed to realize fast communication between processors. Because of the shortcomings of bandwidth, delay and energy consumption, traditional electrical interconnection can not meet the needs of large-scale parallel computer communication. Due to its excellent characteristics such as high transmission bandwidth, extremely low transmission delay and extremely low power consumption, optical interconnection has become the new generation communication network of large-scale parallel computers. Wavelength division multiplexing (WDM) is one of the key technologies in optical communication. Its core idea is to divide the same optical fiber into multiple channels according to wavelength and transmit multiple optical signals at the same time. Embedding communication mode into WDM optical network is to map each subtask of communication mode to a node in the network and assign an optical path to each pair of nodes that need direct communication. All optical paths passing through the same optical fiber have different wavelengths. An important task of parallel computing is to embed various typical communication modes into typical WDM optical networks to achieve efficient communication. Because wavelength is an extremely valuable resource, we need to find the least number of wavelength assignment scheme, which is the wavelength assignment problem in WDM optical networks. Hypercubes, cross cubes and locally distorted cubes are typical communication modes, while linear arrays are typical WDM network topologies. This paper focuses on how to embed the above communication modes into linear array optical networks to minimize the required wavelengths. The results are as follows: (1) We study how to embed the locally twisted cube into the linear array statically. In this paper, a specific embedding scheme is proposed, and the optimality of the scheme is proved by using the maximum derived subgraph technique, and the corresponding wavelength assignment algorithm is given to minimize the number of required wavelengths. (2) We study how to embed generalized cube into linear array statically. A natural embedding scheme is proposed, the optimality of the scheme is proved, and the congestion degree of each edge in the array is determined. On this basis, the routing and wavelength assignment problems of half-duplex and full-duplex communication modes on linear arrays of crossed cubes are studied. It is proved that the natural embedding schemes have the minimum number of wavelengths in both communication modes. The corresponding wavelength assignment algorithm is also given. (3) how to dynamically embed the hypercube-based bimonal ordering into a linear array is studied. The concept of dimension embedding is put forward according to the characteristics of double tone ordering, and two embedding schemes are put forward, and the number of wavelengths required is analyzed. The results show that, The number of wavelengths required by these two wavelength assignment schemes is obviously smaller than that of the optimal static wavelength assignment scheme. (4) how to embed the bimodal sorting algorithm into the on-chip optical bus network is studied. According to the characteristics of dual modulation merging, a wavelength assignment scheme is proposed, and then a wavelength assignment scheme is proposed for ordering the disordered sequence of n elements. It is proved that the number of wavelengths required in this scheme is N2. Finally, the work of this paper is summarized, and the future research is prospected.
【学位授予单位】：重庆大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TN929.1

【共引文献】