超立方体网络的3路结构连通度及子结构连通度

来源:用户上传      作者:

　　摘 要：针对以超立方体网络为蓝本的多处理机系统的可靠性和容错能力的精准度量问题，结合多处理机系统遭受计算机病毒攻击时常常发生结构性故障的特点，研究了n维超立方体网络的结构连通性和子结构连通性评价问题。首先，使用构造n维超立方体网络的3路结构割的方法得到其3路结构连通度的一个上界;然后，使用構造n维超立方体网络的3路子结构集的等价变换或约简变换的方法，得到其3路结构子连通度的一个下界;最后，利用任意网络的3路结构连通度不小于3路子结构连通度的性质，证实了超立方体网络的3路结构连通度和子结构连通度均为该超立方体网络维数的一半。这一结果表明，在3路结构故障模型下，破坏敌方以超立方体网络为底层拓扑的多处理系统至少需要攻击该系统中维数一半的3路结构或子结构。
　　关键词：多处理机系统;超立方体网络;容错;可靠性;结构连通度
　　Abstract： In order to evaluate the reliability and fault-tolerant ability of multi-processor system which takes hypercubes as underlying networks， combining the fact that structural faults often occur when the system is invaded by computer viruses， 3-length-path structure connectivity and substructure connectivity of the n-dimensional hypercube network were investigated. Firstly， by using the 3-length-path structure-cut of the n-dimensional hypercube network， an upper bound of 3-length-path structure connectivity of the network was obtained. Secondly， by using an equivalent transformation or a reductive transformation of the 3-length-path substructure-set of the n-dimensional hypercube network， a lower bound of 3-length-path substructure connectivity of the network was obtained. Finally， combining with the property that 3-length-path structure connectivity of a network is not less than its 3-length-path substructure connectivity， it was proved that both 3-length-path structure connectivity and substructure connectivity of the n-dimensional hypercube network were half of n. The results show that to disconnect the enemys multi-processor system which take the n-dimensional hypercubes as underlying networks under the 3-length-path structure fault model， at least half of n 3-length-path structures or substructures of the system should be attacked.
　　In order to evaluate the reliability and fault-tolerant ability of multi-processor system which takes hypercubes as underlying networks， combining the fact that structural faults often occur when the system is invaded by computer viruses， three-length-path structure connectivity and substructure connectivity of the n-cube network were investigated. Firstly， by using the three-length-path structure-cut of the n-cube network， an upper bound of three-length-path structure connectivity of the network was obtained. Secondly， by using an equivalent transformation or a reductive transformation of the three-length-path substructure-set of the n-cube network， a lower bound of three-length-path substructure connectivity of the network was obtained. Finally， combining with the property that three-length-path structure connectivity of a network is not less than its three-length-path substructure connectivity， it was proved that both three-length-path structure connectivity and substructure connectivity of a n-cube network were half of n. The results show that to destroy the enemys multi-processor system which take the n-cubes as underlying networks under three-length-path structure fault model， at least half of n three-length-path structures or substructures of the system should be attacked. 　　Key words： multi-processor system; hypercube network; fault tolerance; reliability; structure connectivity
　　0 引言
　　多处理系统，尤其是超级并行计算机系统通常以某个拓扑性质优秀的图作为底层网络的蓝本。在诸多底层网络中，超立方体网络以其正则性[1-2]、对称性[3]、递归性[4]等拓扑特性脱颖而出，成为搭建超级并行计算机系统最常用的底层网络，诸如iWarp、J-machine、Cray T3D、Cray T3E等超级并行计算机系统均以超立方体网络为底层网络。
　　在实际系统中，处理器和通信线路故障在所难免，反映到底层网络中就是网络节点和连线难免发生故障。在网络发生故障时，用户希望网络中任意两个节点之间依然连通，因此，网络的连通度可以在一定程度上度量网络的可靠性。然而，在等概故障模型下与系统的同一节点相邻的其余节点同时发生故障是一个小概率事件[5]，因此在等概故障模型下，传统连通度严重低估了系统的可靠性[6]。在此背景下，各种条件连通度被相继提出并得到广泛的关注与深入的研究。其中，近几年被提出的条件连通度有嵌入限制连通度[7-9]、分支连通度[10]、结构连通度和子结构连通度[11-14]等。其中，2016年，Lin等[11-12]考虑到多处理系统度遭受计算机病毒入侵时往往发生结构性故障的实际特征，联合提出了两个系统可靠性度量的新参数——结构连通度和子结构连通度，确定了超立方体网络的星型和4圈结构连通度及子结构连通度。2018年，Mane[13]研究了超立方体网络中故障结构为低维子网及圈的结构连通度问题，并得到了一些上界。同年，Sabir等[14]得到了H为长度小于n的路、长度不超过2n的偶圈及4星时，n维超立方体网络的H结构连通度及子结构连通度，但其结论依赖于Yang等[2]关于超立方体网络的g超结构连通度的结论。本文提出超立方体网络的H结构集及子结构集的等价变换和约简变换的概念，在故障结构或故障子结构有公共节点或公共边的情形下，通过构造超立方体网络的P3子结构集的等价变换（或约简变换）这一新的方法，确定超立方体网络的P3结构连通度和P3子结构连通度，为以超立方体网络为底层拓扑的超级计算机系统的安全防护提供参考。
　　4 结语
　　网络的结构连通度和子结构连通度的计算对攻击敌方系统以及防护我方系统均具有指导性的意义。当确定这两个参数后，便可得知攻击敌方系统所需要攻击的最少结构的数目，若是攻击敌方系统，可据此设计攻击算法，若是保护我方系统，可据此完善防御策略。譬如：由“n维超立方体网络的3路结构连通度和子结构连通度均为「n/2”可知，当攻击敌方以n维超立方体为底层拓扑构建的系统时，至少需要破坏敌方「n/2个3路（子）结构才可使得敌方系统不再连通;而当敌方攻击我方系统时，我方应设法保护所有可能受攻击的3路（子）结构。
　　结构连通度和子结构连通度的计算往往通过构造相等的上下界的方法来确定。在确定下界时，需要证明当该网络中删除任一元素个数小于该下界的结构集（或子结构集）后，网络依旧连通。若已知该网络的g超连通度，网络连通性不难证明。然而对于g超连通度未知的网络，则需选择恰当的方式将高维网络划分为若干个不相交的子网，使得该结构集（或子结构集）中的边尽可能少地占据横跨边。即便如此，由于结构集（或子结构集）的多个元素有可能共用某条横跨边，这使得落在子网中子结构集的元素个数陡增，从而影响使用归纳前提。针对上述问题，本文提出了网络的结构集（或子结构集）的等价变换和约简变换的概念，并以超立方体网络中的3路子结构集为例，给出了构造结构集和子结构集的等价变换（或约简变换）的方法，通过该方法构造的等价变换和约简变换使得构造出的新的结构集和子结构集中只有一个元素包含某一横跨边，排除了解决网络结构连通度和子结构连通度度量问题的瓶颈。
　　使用文中的方法求解其他网络的结构连通度和子结构连通度也是值得进一步研究的问题。
　　参考文献：
　　[1] XU J M， ZHU Q， HOU X M， ZHU T. On restricted connectivity and extra connectivity of hypercubes and folded hypercubes [J]. Journal of Shanghai Jiaotong University （Science）， 2005， E-10（2）： 203-207. 上海交通大学学报（英文版）
　　[2] YANG W， MENG J. Extraconnectivity of hypercubes [J]. Applied Mathematics Letters， 2009， 22（6）： 887-891.
　　[3] MORRISION N， NOEL J A. Extremal bounds for bootstrap percolation in the hypercube [J]. Journal of Combinatorial Theorey， Series A， 2018， 156： 61-84.
　　[4] WANG F， ZHANG H. Hamiltonian laceability in hypercubes with faulty edges[J].Discrete Applied Mathematics，2018，236：438-445.
　　[5] 邱亞娜，杨玉星.增广泡型网络的边连通性和限制边连通性[J]. 计算机应用，2016，36（11）：3006-3009. （QIU Y N， YANG Y X. Link connectivity and restricted link connectivity of augmented bubble-sort networks [J]. Journal of Computer Applications， 2016， 36（11）： 3006-3009.） 　　[6] 李際超，吴俊，谭跃进，等.基于有向自然连通度的作战网络抗毁性研究[J].复杂系统与复杂性科学，2015，12（4）：25-31. （LI J C， WU J， TAN Y J， et al. Robustness of combat networks based on directed natural connectivity [J]. Complex Systems and Complexity Science， 2015， 12（4）： 25-31.）
　　[7] YANG Y， WANG S. Conditional connectivity of star graph networks under embedding restriction [J]. Information Sciences， 2012， 199： 187-192.
　　[8] YANG Y， WANG S， LI J. Conditional connectivity of recursive interconnection networks respect to embedding restriction [J]. Information Sciences， 2014， 279： 273-279.
　　[9] LI X-J， DONG Q-Q， YAN Z， et al. Embedded connectivity of recursive networks [J]. Theoretical Computer Science， 2016， 653： 79-86.
　　[10] ZHAO S， YANG W， ZHANG S. Component connectivity of hypercubes [J]. Theoretical Computer Science， 2016， 640： 115-118.
　　[11] LIN C-K， ZHANG L， FAN J， et al. Structure connectivity and substructure connectivity of hypercubes [J]. Theoretical Computer Science， 2016， 634： 97-107.
　　[12] LYU Y， FAN J， HSU D F， et al. Structure connectivity and substructure connectivity of k-ary n-cube networks [J]. Information Sciences， 2018， 433/434： 115-124.
　　[13] MANE S A. Structure connectivity of hypercubes[J].AKCE International Journal of Graphs and Combinatorics，2018，15（1）：49-52.
　　[14] SABIR E， MENG J. Structure fault tolerance of hypercubes and folded hypercubes [J]. Theoretical Computer Science， 2018， 711： 44-55.
　　[15] BONDY J A， MURTY U S R. Graph Theory [M]. New York： Springer， 2008： 633-641.
转载注明来源:https://www.xzbu.com/8/view-14941826.htm