超立方體網(wǎng)絡(luò)的3路結(jié)構(gòu)連通度及子結(jié)構(gòu)連通度

楊玉星 李曉慧

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

關(guān)鍵詞：多處理機(jī)系統(tǒng);超立方體網(wǎng)絡(luò);容錯(cuò);可靠性;結(jié)構(gòu)連通度

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)，尤其是超級并行計(jì)算機(jī)系統(tǒng)通常以某個(gè)拓?fù)湫再|(zhì)優(yōu)秀的圖作為底層網(wǎng)絡(luò)的藍(lán)本。在諸多底層網(wǎng)絡(luò)中，超立方體網(wǎng)絡(luò)以其正則性[1-2]、對稱性[3]、遞歸性[4]等拓?fù)涮匦悦摲f而出，成為搭建超級并行計(jì)算機(jī)系統(tǒng)最常用的底層網(wǎng)絡(luò)，諸如iWarp、J-machine、Cray T3D、Cray T3E等超級并行計(jì)算機(jī)系統(tǒng)均以超立方體網(wǎng)絡(luò)為底層網(wǎng)絡(luò)。

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

4 結(jié)語

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

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

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

參考文獻(xiàn)：

[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. 上海交通大學(xué)學(xué)報(bào)（英文版）

[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)絡(luò)的邊連通性和限制邊連通性[J]. 計(jì)算機(jī)應(yīng)用，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ìn)，等.基于有向自然連通度的作戰(zhàn)網(wǎng)絡(luò)抗毀性研究[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，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.