評估交換超立方體網絡可靠性的一種新方法

梁家榮白 楊王新陽

①(廣西大學計算機與電子信息學院 南寧 530004)

②(華南理工大學計算機科學與工程學院 廣州 510006)

評估交換超立方體網絡可靠性的一種新方法

梁家榮*①白 楊①王新陽②

①(廣西大學計算機與電子信息學院 南寧 530004)

②(華南理工大學計算機科學與工程學院 廣州 510006)

交換超立方體互連網絡(EH(s,t))作為大規模處理器系統網絡模型的重要候選之一，其可靠性問題一直為人們所關注。該文利用額外連通度作為評價可靠性的重要度量，對交換超立方體互連網絡的可靠性進行分析，得到了交換超立方體網絡的2-額外點連通度(k2(EH(s,t)))和2-額外邊連通度(λ2(EH(s,t )))，證明了當t≥s≥2時，k2(EH(s,t))=3s-2；當t≥s≥3時，λ2(EH(s,t))=3s-1。分析說明了對交換超立方體互連網絡的可靠性評價時，2-額外連通度較之傳統連通度更具有優勢性。

互連網絡；交換超立方體；可靠性；額外連通度

1 引言

互連網絡的可靠性主要是指在網絡的部分節點、部分鏈路出現故障時，剩余子網是否仍能保持正常通信的能力。隨著網絡規模的不斷擴大，網絡中出現故障節點、故障鏈路的情況不可避免，因此網絡的可靠性問題就成為不可回避的研究課題。其中，點連通度和邊連通度是衡量網絡可靠性的兩個重要參數，它們表明了一個網絡能容忍同時故障的最大節點數和最大鏈路數。但點連通度和邊連通度在衡量網絡可靠性方面也存在不足的地方：它們都默認一個節點或一條鏈路的所有鄰居節點(或鄰居鏈路)可能同時出現故障，而這種情況在實際的網絡中幾乎不可能存在，例如在一個具有2n個節點的正則度為n的規則互連網絡中，一個節點的所有鄰居點同時故障的概率是2n/＜10-6(當n≥6時)，這種概率的事件幾乎不可能發生，因此用點連通度和邊連通度研究互連網絡的可靠性不切實際。

為了解決這一問題，Haray在傳統連通度的基礎上加入一些限制條件，提出了條件連通度[1]的概念。后來，Fabrega和Fiol將這一限制條件進一步細化提出了額外連通度的概念[2,3]。額外連通度一經提出便引起眾多學者的高度關注，并獲得眾多研究成果[4-10]。文獻[4]研究了超立方體[11]的2-額外連通度；文獻[5]將超立方體的額外連通度精確到了h階，這極大提升了超立方體網絡的可靠性精度；文獻[6]從網絡中不存在孤立節點、孤立鏈路的角度分別研究了折疊超立方體網絡[12]的2-額外點連通度和2-額外邊連通度；文獻[9]研究了一類特殊正則網絡的2-額外連通度；文獻[10]則將該類特殊正則網絡的可靠性精度提升到h階，證明了當0≤h≤n-4時，n維一一對應連接(Bijection Connected,BC)網絡[13]的h-額外連通度是n(h+1)-(h(h+3))/2，這為進一步研究更大規模的具有失效節點的BC互連網絡的可靠性提供了支持。

在眾多互連網絡結構中，超立方體是最具吸引力的網絡之一，但它并非各方面性質最好的。針對超立方體的一些缺陷，不少學者提出了很多超立方體的變種[12,14-17]。作為其中最重要的網絡之一，交換超立方體[17]不僅保持了超立方體大量的優秀屬性，并且擁有比超立方體更好的屬性，如其邊數幾乎是超立方體邊數的一半。目前，關于交換超立方體互連網絡的研究已經有很多成果[18-21]，其中可靠性問題備受人們關注。文獻[18]證明了交換超立方體的點連通度和邊連通度均為1s+；在文獻[19]中，Ma等人從網絡中不存在孤立節點的角度證明了交換超立方體網絡的超點連通度和超邊連通度均為2s，這將交換超立方體網絡的可靠性的精度提升了近2倍。盡管如此，但上述參數仍有一定缺陷，例如當n很大時，交換超立方體的連通度1s+和超連通度2s與節點總數2s+t+1的比值均非常小，以至于失去了實際意義，而額外連通度在一定程度上克服了這一缺陷。因此用額外連通度來研究交換超立方體的可靠性具有較高的學術意義和應用價值。本文主要在傳統連通度和超連通度的基礎上，深入剖析了交換超立方體網絡的2-額外點連通度和2-額外邊連通度，證明了當t≥s≥2時，k2(EH(s,t))=3s-2；當t≥s≥3時，λ2(EH(s,t))=3s-1。最后，分析說明了在評價交換超立方體互連網絡的可靠性時，2-額外連通度比傳統連通度更精確、更符合實際情況。

2 預備知識

本文中沒有定義的理論術語與符號描述，本文將參照文獻[22]中的相關定義。在無向圖G中，V(G), E(G)分別表示圖G的頂點集和邊集。對于圖G中的任意的集合F，令G-F表示圖G在移除了F中所有元素之后所形成的子圖。|S|表示集合S的基。(u,v)∈E(G)表示G中任意一條邊。NG(u)和EG(u)分別表示頂點u的鄰居結點集和鄰居邊集，且NG(u)={v∈V(G)|?(u,v)∈E(G)}, EG(u)={(u,v)∈E(G)|?v∈V(G)}。NG(P)和EG(P)分別表示路徑P在圖G中的鄰居結點集和鄰居邊集，且NG(P)=(∪?u∈V(P)NG(u))-V(P),EG(P)=(∪u∈V(P)?EG(u))-E(P)。

定義1[17]交換超立方體被定義為一個無向圖EH(s,t)=(V,E)(s≥1,t≥1)。頂點集V={as-1…a0bt-1…b0c|ai,bj∈{0,1}且i∈[0,s),j∈[0,t)}。該類超立方體包含3種類型的邊E1, E2和E3，描述為

其中v[x:y]表示v的第y位與第x位之間的比特串，H(v1,v2)表示頂點v1,v2之間的海明距離。圖1示出了兩個交換超立方體EH(1,1)和EH(1,2)。

引理 1[17]EH(,)st同構于EH(,)ts。

引理 2[17]EH(,)st可分解為同構于EH(1,)st-或EH(,1)st-的兩個子圖。

根據引理1，本文只討論當st≤時EH(,)st的情況，為了研究需要，將EH(,)st分解成子圖L和R，其中

圖1 兩個交換超立方體EH(1,1)和EH(1,2)

由定義1可知，EH(,)st是在超立方體的基礎上通過系統地移除部分邊而得到。因此，它是超立方體的一個生成子圖，保留了其大量優越屬性。

引理 3 在EH(,)st中，任意兩個不相鄰頂點的公共鄰居最多是2。

定理 1 若P為EH(,)st中任意一條長度為2的路，則NEH(s,t)(P)≥3s-2。

證明 由定義1及引理3，很容易證明NEH(s,t)(P)≥3s-2。 證畢

定理 2 若P為EH(s,t)中任意一條長度為2的路，則EEH(s,t)(P)≥3s-1。

證明 由定義1中邊的特性，很容易證明EEH(s,t)(P)≥3s-1。 證畢

3 交換超立方網絡的額外連通度

3.1 刪除部分結點(邊)的stEH(,)的連通性

在交換超立方網絡的運行中，出現故障結點和失效鏈路是不可避免的，存在故障結點和失效鏈路的交換超立方網絡仍能保持通信是網絡分析中重要考慮的問題之一。下面本文考慮刪除部分結點(邊)后，交換超立方網絡的連通性問題。

定理 3 對于任意的F?V(EH(s,t ))且|F|≤3s-3，令Fl=F∩V(L), Fr=F∩V(R)。若在EH(s, t)-F中既無孤立頂點也無孤立邊，則R-Fr(或L-Fl)中每一個頂點均與L-Fl(或R-Fr)中一個頂點連接。

證明 對于任意的頂點ur∈V(R-Fr), ur= 1as-2…a0bt-1…b0c ，分以下兩種情形進行討論。

(1)令ur=1as-2…a0bt-1…b00。若ul=0as-2…a0bt-1…b00?F ，則定理得證。否則ul∈F。如果存在ur0=1as-2…a0bt-1…b01?F ,1as-2…a0bt-1…且，那么從ur出發總存在一條路徑使其連接至L-Fl，定理得證。否則ur0∈F。如果且uri(s+t)=0as-2，則定理得證。否則uri與 uri(s+t)(0≤i≤s -2)中至少一個頂點在F中，此時令A={uri,uri(s+t)|0≤i≤s-2}∩F ，則必有|A|≥s-1。

因為EH(s,t)-F中不存在孤立點，不妨令vr=，如此(ur,vr)∈E(R-Fr)。若，則定理得證。否則vl∈F。如果存在且b00?F，那么從ur出發經過vr，總存在一條路徑使其連接至L-Fl。 否則vr0∈F。如果vrj=1as-2…且，則定理得證。否則其中之一必在F中，此時令B={vrj,vrj(s+t)|0≤j≤s-2且j≠i}∩F，則|B|≥s-2。

令C={wrk,wrk(s+t)|0≤k≤s-2,k≠i,j }, D= {ul,vl,wl,ur0,vr0,wr0}，其中wl∈F, wr0∈F。由于而在C中有s-3對頂點使ur連接至L-Fl，因此至少存在一個常數k(k≠i,j)使u與L-Fl中一個頂點相連接，定理得證。

(2)令ur=1as-2…a0bt-1…b01。由于N(ur)∩V(L) =φ若，則存在一條路徑，使ur連通至L-Fl。否則u′∈F。令，若|A′|＜t，則必定存在某一i′使1as-2…a0bt-1…bi′…b01b00?F，如此ur連通至L-Fl。否則|A′|≥t。因為EH(,)stF-中不存在孤立點，不妨令，如此(ur,)∈E(EH(s,t)-F)。若，則ur連通至L-Fl。否則v′∈F。令j′≤t-1,j′≠i′}∩F ，若|B′|＜t-1，同理可得ur連通至L-Fl。否則，令|B′|≥t-1。

…bi′…bj′…b0；或w′→1a…ab…bi′…bj′

0

輕量級、大眾化 原生應用是專門針對某一類移動設備而開發的，下載并安裝到設備里進行使用；輕量級應用是指基于微信等應用軟件，以一定形式為用戶提供的應用服務，具有上手容易、發展迅速的特點[3]。教師采用輕量級形式的全民學習共享平臺，花費更多心思在教學設計上，深耕教學內容，打磨出高品質的智慧課堂。教師可以零成本地開發課程資源，對制作好的PPT添加語音講解，引入學生投票、提問、評論功能，促使學生更加專注。教師可以登錄微信完成課件的移動查閱、實時推送，可以通過雨課堂或微信群的形式建立立體交流、互動互助的共享空間，又能實現點對點的個人交流空間。

令C′={u′,v′}，由于|F-(A′∪B′∪C′)|≤(3s-3)-t-(t-1)-2≤s -4，而ur通過可構造t-1條路徑且t-1≥s-1＞s-4，如此至少存在一條路徑使ur與L-Fl中的一個頂點相連接，定理得證。

定理4 對于任意的F′?E(EH(s,t ))且|F′|≤3s -2，令=F′∩E(L),=F′∩E(R),=F′∩M0。若在EH(s,t)-F′中既無孤立頂點也無孤立邊，則中每一個頂點均與中一個頂點相連。

證明 設ur為R-F中任意一頂點，令ur= 1as-2…a0bt-1…b00，則有以下兩種情形。

(1)令ur=1as-2…a0bt-1…b00。 若es+t(ur)= (ul,ur)?F′，則定理得證。否則es+t(ur)∈F′。若且?F′，則存在一條路徑使ur連通至L-，定理得證。否則e0(ur)∈F′。令A={ei(ur),es+t(uri)|0≤i≤s-2}∩F′，若|A|＜s-1，則必定存在某一i，使ei(ur)?F′且es+t(uri)?F′，如此ur必定與L-中某一頂點相連接，定理得證。否則|A|≥s-1。

由于EH(s,t)-F′中無孤立頂點，如此存在某一ei(ur)?F′使(ur,uri)∈E(EH(s,t)-F′)。若es+t(uri)?F′，則定理得證。否則es+t(uri)∈F′。若e0(uri)?F′，此時可以形成一條通向L-Fl′的路徑為：

如此定理可證。否則e0(uri)∈F′。令B={ej(uri), es+t(urij)|0≤j≤s-2,j≠i}∩F′，若|B|＜s-2，則必定存在某一j，使ej(uri)?F′,es+t(urij)?F′, ur可通過一條路徑連接至L-，定理可證。否則|B|≥s-2。

由于EH(s,t)-F′中不存在孤立邊，因此存在ej(uri)?F′且j≠i，如此ur經過urij至L-可構造如下路徑：

或ek(urij)→es+t(urijk)，其中0≤k≤s-2且 k≠i,j。

令C={es+t(ur),e0(ur),es+t(uri),e0(uri)}，因為|F′-A∪B∪C|=|F′|-|A|-|B|-|C|≤(3s -2) -(s-1)-(s-2)-4=s-3，而ur通過urij可構造(s-1)條通向L-的路徑，如此至少存在一條路徑使ur與L-中一個頂點相連，定理得證。

(2) 令ur=1as-2…a0bt-1…b01。 由于N(ur)∩V(L)=φ，若e0(ur)F′，則此時存在一條路徑ur→ur0→0as-2…a0bt-1…b00，定理得證。否則e0(ur)∈F′。令≤t-1}∩F′，若|A′|＜t，則同理可得存在某一i′，使，如此ur可連接至L-Fl′中一個頂點，定理可證。否則|A′|≥t。

，同理通過uri′j′可構造通向的路徑為：

uri′j′→，其中0≤k′≤t-1且k′≠i′,j′。

令C′={e0(ur),e0(uri′)}，由于|F′-A′∪B′∪C′|≤(3s-2)-t-(t-1)-2≤s -3,而ur通過uri′j′可構造(t-1)條通向L-的路徑，其中t≥s，因此至少存在一條路徑使ur與L-中一個頂點相連，定理得證。

3.2 stEH(,)的2-額外連通度

額外連通度是評價交換超立方網絡可靠性的重要度量，依靠于3.1節的結論，下面給出交換超立方網絡的2-額外連通度的相關結果。

引理 4[19]當s≤t時，k′(EH(s,t))=λ′(EH(s,t)) =2s。定理 5 k2(EH(s,t))=3s-2，其中t≥s≥2。證明 在EH(s,t)中任取一條長度為2的路徑P，由定理1有NEH(s,t)(P)≥3s-2。很容易驗證，EH(s,t)-NEH(s,t)(P)既不包含孤立頂點，也不包含孤立邊，如此NEH(s,t)(P)為一點割集且k2(EH(s,t))≤3s-2。若要證明定理5成立，只需證明k2(EH(s,t))≥3s-2，即證明對于任意的頂點集F?V(EH(s,t))，當|F|=3s-3且不存在孤立頂點也不存在孤立邊時，EH(s,t)-F是連通的。令Fl=F∩V(L), Fr=F∩V(R)，由定理3可知，R-Fr中任意一頂點與L-Fl中一頂點連通。如此，只需證明當|F|=3s-3且在EH(s,t)-F不存在孤立頂點也不存在孤立邊時，L-Fl是連通的即可。不失一般性，令|Fl|≤|Fr|，則|Fl|≤(3s-3) /2＜2s-2(s≥2)。

若在L-Fl中無孤立點，而|Fl|＜2s-2= k′(L)，則L-Fl是連通的，定理得證。否則在L-Fl中有孤立點，假設有兩個孤立點，記為x,y。由于|NL(x)|,|NL(y)|≥(s-1)+1=s ，且在L中任意兩個不相鄰頂點之間的公共鄰居最多為2，故至少移出(2s-2)個頂點才能得到兩個孤立點，而|Fl|＜2s-2，如此在L中只存在一個孤立點，設為ul，即NL(ul)?Fl且|NL(ul)|≥s。下面證明當|F|=3s-3且在EH(s,t)-F不存在孤立頂點也不存在孤立邊時，ul與L-Fl∪{ul}是連通的。

若 ul=0as-2…a0bt-1…b01時，由于N(ul)∩V(R) =φ，則ul在EH(s,t)-F中為一孤立點，這與EH(s,t)-F不存在孤立頂點相矛盾，此時ul只能取下面的值，即 ul=0as-2…a0bt-1…b00。

因為在EH(s,t)-F中無孤立點，故存在ur= 1as-2…a0bt-1…b00?F ，如此(ul,ur)∈E(EH(s,t ) -F)。若ur0=1as-2…a0bt-1…b01?F , 1as-2…a0bt-10as-2…a0bt-1…bi′…b00?F ，則定理得證。否則且則定理得證。否則令A={uri,uri(s+t)|0≤i≤s-2}∩F，則|A|≥s-1。

因為在EH(s,t)-F中無孤立邊，如此存在一個uriF，使(ur,uri)∈E(EH(s,t)-F)，則ul通過uri構造通向L-ul的路徑為：

uri→，其中0≤j≤ s-2且j≠i。

由于|F-NL(ul)∪A∪{ur0}|≤(3s-3)-s-(s -1)-1=s-3且ul通過uri可構造(s-2)+1= s-1條通向L-ul的路徑，故至少存在一條路徑使ul與L-Fl∪{ul}連通，定理得證。

引理5[22]對任意的圖G，都有k(G)≤λ(G)≤δ(G)。

引理 6[18]當s≤t時，k(EH(s,t))=λ(EH(s,t)) =s +1。

定理 6 λ2(EH(s,t))=3s -1，其中t≥s≥3。

證明 在EH(s,t)中任取一條長度為2的路徑P，根據定理2有|EEH(s,t)(P)|≥3s-1。由于EH(s,t)- EEH(s,t)(P)既不包含孤立頂點也不包含孤立邊，根據λ2的定義，有λ2(EH(s,t))≤3s-1。如此，只需證明λ2(EH(s,t))≥3s-1，即證明對于任意的邊集F′?E(EH(s,t ))，若|F′|=3s-2且既無孤立頂點也無孤立邊時，EH(s,t)-F′為連通的。令=F∩E(L),=F∩E(R),=F∩M0。由定理4可知，R-中每個頂點至少與L-中一個頂點相連接，故只需證明當|F′|=3s-2且EH(s,t)-F′既無孤立頂點也無孤立邊時，L-是連通的即可。由于|F′|=3s-2＜4(s -1)(s≥3)，故中至少兩個小于2(s-1)，不妨設||＜ 2(s-1)。若L-中無孤立點，且||＜2(s-1) =λ′(L) ，如此L-為連通的，定理得證。否則存在孤立點。同理定理5可得，L-中沒有兩個孤立點，只能有一個孤立點，記為ul，此時有EL(ul)?且|EL(ul)|≥s。由于λ(L-ul)≥k(L而＜s-2＜s -1，如此為連通的。下面只需證明當|F′|=3s-2且在EH(s,t)-F′中既不包含孤立點也不包含孤立邊時，ul與L-∪{ul}連通即可。

若ul=0as-2…a0bt-1…b01，由于ul在L-中為孤立點且N(ul)∩V(R)=φ，這與E(EH(s,t)-F′)中無孤立頂點相矛盾，如此ul只能為下面值，即ul=0as-2…a0bt-1…b00。

由于EH(s,t)-F′中無孤立點，如此es+t(ul)?F′，使(ul,ur)∈E(EH(s,t)-F′)，其中us+t=ur。若e0(ur)?F′，則ul可通過下面路徑連接至L-∪{ul}：

如此，則定理成立。否則e0(ur)∈F′，令A′= {ei(ur),es+t(uri)|0≤i≤s-2}∩F′，則|A′|≥s-1。

由于EH(s,t)-F′中無孤立邊，則存在某個i，使ei(ur)F′，如此(ur,uri)∈E(EH(s,t)-F′)，則從ul出發經過uri可構造通向L-ul的路徑為：

ul→ur→uri→或ul→ ur→其中0≤j≤s -2且j≠i。

由于|F′-A′∪EL(ul)∪{e0(ur)}|=|F′|-|A′| -|EL(ul)|-1≤s -2，而ul通過uri連接至L-ul的路徑有1s-條，故至少存在一條路徑使lu連接至

4 stEH(,)的2-額外連通度與傳統連通度比較

綜上所述，當t≥s≥2時，EH(s,t)的2-額外點連通度是3s-2；當t≥s≥3時，EH(s,t)的2-額外邊連通度是3s-1。而當t≥s時，EH(s,t)的傳統點連通度和傳統邊連通度均是s+1。由此可以看出，2-額外連通度幾乎是傳統連通度的3倍，這使得交換超立方體網絡可靠性的量度更加精確，因此2-額外連通度比傳統連通度更適合評價大規模交換超立方體網絡的可靠性。另一方面，傳統連通度假定交換超立方體網絡的任一節點或任一鏈路的所有鄰居節點(或鄰居鏈路)都可能同時故障，這種情況發生的概率是2n/＜10-6(當n≥6時)，不切實際。而2-額外連通度假定交換超立方體網絡的任一節點或任一鏈路的部分鄰居節點(或鄰居鏈路)不能同時故障，這更符合實際情況，因此在評價交換超立方體互連網絡的可靠性時，2-額外連通度比傳統連通度更具優勢性。

5 結束語

本文在交換超立方體網絡傳統連通度和超連通度的基礎上深入研究，進一步證明了2-額外點連通度和2-額外邊連通度：當t≥s≥2時，k2(EH(s,t))= 3s-2；當t≥s≥3時，λ2(EH(s,t))=3s -1。也就是說，當t≥s≥2(或t≥s≥3)時，交換超立方體至少刪除3s-2個頂點(或3s-1條邊)，才能得到既不包含孤立頂點也不包含孤立邊的非連通圖。該結果的得出進一步擴展了交換超立方體網絡的可靠性研究，同時對交換超立方體網絡的可靠性提供了更精確的量度。

[1] Harary F. Conditional connectivity[J]. Networks, 1983, 13(3): 347-357.

[2] Fàbrega J and Fiol M A. Extraconnectivity of graphs with large girth[J]. Discrete Mathematics, 1994, 127(1): 163-170.

[3] Fàbrega J and Fiol M A. On the extraconnectivity of graphs[J]. Discrete Mathematics, 1996, 155(1): 49-57.

[4] Xu J M and Zhu Q. On restricted connectivity and extra-connectivity of hypercubes and folded hypercubes[J]. Journal of Shanghai Jiaotong University, 2005, 10(2): 203-207.

[5] Yang W and Meng J. Extraconnectivity of hypercubes[J]. Applied Mathematics Letters, 2009, 22(6): 887-891.

[6] Zhu Q, Xu J M, Hou X, et al.. On reliability of the folded hypercubes[J]. Information Sciences, 2007, 177(8): 1782-1788.

[7] Hong W S and Hsieh S Y. Extra edge connectivity of hypercube-like networks[J]. International Journal of Parallel, Emergent and Distributed Systems, 2013, 28(2): 123-133.

[8] Li H and Yang W. Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes[J]. Discrete Applied Mathematics, 2013, 161(16/17): 2753-2757. [9] Xu J M, Zhu Q, and Xu M. Fault-tolerant analysis of a class of networks[J]. Information Processing Letters, 2007, 103(6): 222-226.

[10] Zhu Q, Wang X K, and Cheng G. Reliability evaluation of BC networks[J]. IEEE Transactions on Computers, 2013, 62(11): 2337-2340.

[11] Saad Y and Schultz M H. Topological properties of hypercubes[J]. IEEE Transactions on Computers, 1988, 37(7): 867-872.

[12] El-Amawy A and Latifi S. Properties and performance of folded hypercubes[J]. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(1): 31-42.

[13] Fan J X. BC interconnection networks and their properties[J]. Chinese Journal of Computers-Chinese Edition, 2003, 26(1): 84-90.

[14] Cheng B, Fan J, Jia X, et al.. Parallel construction of independent spanning trees and an application in diagnosis on M?bius cubes[J]. Journal of Supercomputing, 2013, 65(3): 1279-1301.

[15] Chen J C, Lai C J, Tsai C H, et al.. A lower bound on the number of Hamiltonian cycles through a prescribed edge in acrossed cube[J]. Applied Mathematics and Computation, 2013, 219(19): 9885-9892.

[16] Yang X F, Evans D J, and Megson G M. The locally twisted cubes[J]. International Journal of Computer Mathematics, 2005, 82(4): 401-413.

[17] Loh P K K, Hsu W J, and Pan Y. The exchanged hypercube[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(9): 866-874.

[18] Ma M J. The connectivity of exchanged hypercubes[J]. Discrete Mathematics, Algorithms and Applications, 2010, 2(2): 213-220.

[19] Ma M J and Zhu L Y. The super connectivity of exchanged hypercubes[J]. Information Processing Letters, 2011, 111(8): 360-364.

[20] Li X J and Xu J M. Generalized measures of fault tolerance in exchanged hypercubes[J]. Information Processing Letters, 2013, 113(14): 533-537.

[21] zar Klav∨S and Ma M J. The domination number of exchanged hypercubes[J]. Information Processing Letters, 2014, 114(4): 159-162.

[22] Bondy J A and Murty U S R. Graph Theory with Applications[M]. London: MacMillan, 1976: 10-24.

梁家榮： 男，1966年生，教授，博士，博士生導師，研究方向為網絡與并行計算、人工智能.

白 楊： 男，1987年生，碩士生，研究方向為網絡與并行計算.

王新陽： 男，1985年生，博士生，研究方向為網絡與并行計算、云計算、大數據.

A New Method Used for Evaluating Reliability of the Exchanged Hypercube Network

Liang Jia-rong①Bai Yang①Wang Xin-yang②

①(School of Computer and Electronic Information, Guangxi University, Nanning 530004, China)
②(School of Computer Science & Engineering, South China University of Technology, Guangzhou 510006, China)

Reliability problems on Exchanged Hypercube interconnection network(EH(s,t)) regard as one of important candidates of network models in large-scale processor systems are concerned by people. The extra connectivity, which is an important measure in evaluating the reliability, is utilized to analyze the reliability of exchanged hypercube interconnection network. Then the 2-extra vertex connectivity(k2(EH(s,t)))and 2-extra edge connectivity(λ2(EH(s,t )))of exchanged hypercube interconnection network are obtained. The conclusions are thatk2(EH(s,t))=3s-2 fort≥s≥2; andλ2(EH(s,t))=3s -1 fort≥s≥3. The analysis shows that the 2-extra connectivity is much superior to the traditional connectivity in evaluating the reliability of exchanged hypercube interconnection network.

Interconnection network; Exchanged hypercube; Reliability; Extra connectivity

TP393

A

1009-5896(2015)03-0693-07

10.11999/JEIT140557

2014-04-28收到，2014-07-14改回

國家自然科學基金(61363002)資助課題

*通信作者：梁家榮 gxuliangjr@163.com