楊玉星 李曉慧

摘 要：針對以超立方體網(wǎng)絡為藍本的多處理機系統(tǒng)的可靠性和容錯能力的精準度量問題，結合多處理機系統(tǒng)遭受計算機病毒攻擊時常常發(fā)生結構性故障的特點，研究了n維超立方體網(wǎng)絡的結構連通性和子結構連通性評價問題。首先，使用構造n維超立方體網(wǎng)絡的3路結構割的方法得到其3路結構連通度的一個上界;然后，使用構造n維超立方體網(wǎng)絡的3路子結構集的等價變換或約簡變換的方法，得到其3路結構子連通度的一個下界;最后，利用任意網(wǎng)絡的3路結構連通度不小于3路子結構連通度的性質(zhì)，證實了超立方體網(wǎng)絡的3路結構連通度和子結構連通度均為該超立方體網(wǎng)絡維數(shù)的一半。這一結果表明，在3路結構故障模型下，破壞敵方以超立方體網(wǎng)絡為底層拓撲的多處理系統(tǒng)至少需要攻擊該系統(tǒng)中維數(shù)一半的3路結構或子結構。

關鍵詞：多處理機系統(tǒng);超立方體網(wǎng)絡;容錯;可靠性;結構連通度

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 引言

多處理系統(tǒng)，尤其是超級并行計算機系統(tǒng)通常以某個拓撲性質(zhì)優(yōu)秀的圖作為底層網(wǎng)絡的藍本。在諸多底層網(wǎng)絡中，超立方體網(wǎng)絡以其正則性[1-2]、對稱性[3]、遞歸性[4]等拓撲特性脫穎而出，成為搭建超級并行計算機系統(tǒng)最常用的底層網(wǎng)絡，諸如iWarp、J-machine、Cray T3D、Cray T3E等超級并行計算機系統(tǒng)均以超立方體網(wǎng)絡為底層網(wǎng)絡。

在實際系統(tǒng)中，處理器和通信線路故障在所難免，反映到底層網(wǎng)絡中就是網(wǎng)絡節(jié)點和連線難免發(fā)生故障。在網(wǎng)絡發(fā)生故障時，用戶希望網(wǎng)絡中任意兩個節(jié)點之間依然連通，因此，網(wǎng)絡的連通度可以在一定程度上度量網(wǎng)絡的可靠性。然而，在等概故障模型下與系統(tǒng)的同一節(jié)點相鄰的其余節(jié)點同時發(fā)生故障是一個小概率事件[5]，因此在等概故障模型下，傳統(tǒng)連通度嚴重低估了系統(tǒng)的可靠性[6]。在此背景下，各種條件連通度被相繼提出并得到廣泛的關注與深入的研究。其中，近幾年被提出的條件連通度有嵌入限制連通度[7-9]、分支連通度[10]、結構連通度和子結構連通度[11-14]等。其中，2016年，Lin等[11-12]考慮到多處理系統(tǒng)度遭受計算機病毒入侵時往往發(fā)生結構性故障的實際特征，聯(lián)合提出了兩個系統(tǒng)可靠性度量的新參數(shù)——結構連通度和子結構連通度，確定了超立方體網(wǎng)絡的星型和4圈結構連通度及子結構連通度。2018年，Mane[13]研究了超立方體網(wǎng)絡中故障結構為低維子網(wǎng)及圈的結構連通度問題，并得到了一些上界。同年，Sabir等[14]得到了H為長度小于n的路、長度不超過2n的偶圈及4星時，n維超立方體網(wǎng)絡的H結構連通度及子結構連通度，但其結論依賴于Yang等[2]關于超立方體網(wǎng)絡的g超結構連通度的結論。本文提出超立方體網(wǎng)絡的H結構集及子結構集的等價變換和約簡變換的概念，在故障結構或故障子結構有公共節(jié)點或公共邊的情形下，通過構造超立方體網(wǎng)絡的P3子結構集的等價變換（或約簡變換）這一新的方法，確定超立方體網(wǎng)絡的P3結構連通度和P3子結構連通度，為以超立方體網(wǎng)絡為底層拓撲的超級計算機系統(tǒng)的安全防護提供參考。

4 結語

網(wǎng)絡的結構連通度和子結構連通度的計算對攻擊敵方系統(tǒng)以及防護我方系統(tǒng)均具有指導性的意義。當確定這兩個參數(shù)后，便可得知攻擊敵方系統(tǒng)所需要攻擊的最少結構的數(shù)目，若是攻擊敵方系統(tǒng)，可據(jù)此設計攻擊算法，若是保護我方系統(tǒng)，可據(jù)此完善防御策略。譬如：由“n維超立方體網(wǎng)絡的3路結構連通度和子結構連通度均為「n/2”可知，當攻擊敵方以n維超立方體為底層拓撲構建的系統(tǒng)時，至少需要破壞敵方「n/2個3路（子）結構才可使得敵方系統(tǒng)不再連通;而當敵方攻擊我方系統(tǒng)時，我方應設法保護所有可能受攻擊的3路（子）結構。

結構連通度和子結構連通度的計算往往通過構造相等的上下界的方法來確定。在確定下界時，需要證明當該網(wǎng)絡中刪除任一元素個數(shù)小于該下界的結構集（或子結構集）后，網(wǎng)絡依舊連通。若已知該網(wǎng)絡的g超連通度，網(wǎng)絡連通性不難證明。然而對于g超連通度未知的網(wǎng)絡，則需選擇恰當?shù)姆绞綄⒏呔S網(wǎng)絡劃分為若干個不相交的子網(wǎng)，使得該結構集（或子結構集）中的邊盡可能少地占據(jù)橫跨邊。即便如此，由于結構集（或子結構集）的多個元素有可能共用某條橫跨邊，這使得落在子網(wǎng)中子結構集的元素個數(shù)陡增，從而影響使用歸納前提。針對上述問題，本文提出了網(wǎng)絡的結構集（或子結構集）的等價變換和約簡變換的概念，并以超立方體網(wǎng)絡中的3路子結構集為例，給出了構造結構集和子結構集的等價變換（或約簡變換）的方法，通過該方法構造的等價變換和約簡變換使得構造出的新的結構集和子結構集中只有一個元素包含某一橫跨邊，排除了解決網(wǎng)絡結構連通度和子結構連通度度量問題的瓶頸。

使用文中的方法求解其他網(wǎng)絡的結構連通度和子結構連通度也是值得進一步研究的問題。

參考文獻：

[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] 邱亞娜，楊玉星.增廣泡型網(wǎng)絡的邊連通性和限制邊連通性[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] 李際超，吳俊，譚躍進，等.基于有向自然連通度的作戰(zhàn)網(wǎng)絡抗毀性研究[J].復雜系統(tǒng)與復雜性科學，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.