超大规模计算机互连网络的可靠性研究

Network reliability analysis is one of the most important problems in performance analysis of large-scale interconnection networks. When the graph is used in representing the topological structure of interconnection networks, the connectivity of graph is an important parameter to measure network reliability. To compensate for the shortcoming of connectivity, several conditional connectivities have been proposed, such as super connectivity, h-restricted connectivity and h-super connectivity. These parameters can measure the reliabilities of the interconnection networks more precisely...This project will mainly do some work depending on three aspects of the researches of network reliability. (i) Consider the vertex persistence of super h-restricted connected network, which means the ability of super h-restricted connected network to persist its super h-restricted connectedness when the node is faulty in networks. This project will discuss the vertex persistence of super h-restricted connected permutation network, circulant permutation network and Cartesian product networks, and expect to get its exact value. (ii) Consider the structure parameters and h-restricted (edge-)connectivity of replacement product networks. (iii) Discuss h-super connectivity and h-super edge-connectivity of some traditional networks, such as bubble-sort networks and pancake networks, and expect to obtain the exact values or bounds of them in terms of h. Since h-restricted connectivity and h-super connectivity are generalizations of the connectivity, the research of this project will be helpful for the research and development of connectivity and provide references for the researches and applications of the interconnection networks.

网络可靠性分析是超大规模计算机互连网络性能分析中最重要的问题之一，当用图来表示互连网络的拓扑结构时，图的连通度是度量网络可靠性的重要参数。为了弥补连通度的缺陷，人们提出了超连通度、h-限制连通度和h-超连通度等多种条件连通度，这些参数能更准确地度量网络的可靠性。.本项目拟从网络可靠性研究的三个方面开展工作：（1）研究超h-限制连通网络的点持久度，即网络节点发生故障时，网络保持超h-限制连通性的能力，将探讨超h-限制连通的置换网络、循环置换网络和笛卡尔乘积网络的点持久度，以期得到其精确值。（2）研究替代乘积网络的结构参数和h-限制（边）连通度。（3）讨论一些经典网络的h-超连通度和h-超边连通度，如冒泡排序网络、煎饼网络等，以期得到与h有关的精确值或界。鉴于h-限制连通度和h-超连通度是连通度的推广，本项目的研究将对连通度的研究和发展起到一定的推动作用，为互连网络的研究和应用提供参考。

图的连通度、限制连通度和超连通度是度量网络可靠性的重要参数。本项目主要研究了图和互连网络可靠性中的若干重要问题，通过研究我们得到了如下一系列结果。（1）研究了替代乘积网络的边连通度和限制边连通度，证明了在特定的条件下两个Cayley图的替代乘积仍是Cayley图，并基于此解决了有关图的限制边连通度的一个猜想。（2）分别确定了局部交换扭立方体LeTQ(s,t)的h-超点连通度和h-超边连通度。（3）证明了当图的边数足够多时给定最小度的无向图是极大边连通的和超边连通的，并且证明了当有向图的弧数足够多时给定最小度的有向图是极大点连通的和超点连通的。（4）通过图的第二大邻接特征值、次小Laplace特征值和第二大无符号Laplace特征值刻画了给定围长或团数的图的点连通度和边连通度，所得结果极大地改进了以往的研究结果。在本项目的支持下，在Linear Algebra and its Application和Science China Mathematics等学术期刊上共发表学术论文6篇。