第7章自適應、無死鎖和容錯路由

第7章自適應、無死鎖和容錯路由自適應、無死鎖和容錯路由網(wǎng)絡通信中，消息在占有資源（緩沖區(qū)、信道）的情況下再申請資源，就可能會發(fā)生死鎖。在自適應路由環(huán)境下，死鎖更容易發(fā)生。M1M5M3等待圖M2M4*在等待圖中形成一個循環(huán)。（自適應路由中，這種循環(huán)更有可能會形成?。?表現(xiàn)在路由中，即：路由中形成了一個回路?！斗植际较到y(tǒng)》(七)08-042自適應、無死鎖和容錯路由本章主要討論：如何通過對網(wǎng)絡邏輯上的改造或對自適應路由一定的限制，避免自適應路由中死鎖的發(fā)生。節(jié)點或鏈路發(fā)生錯誤時，如何實現(xiàn)路由（容錯路由）?！斗植际较到y(tǒng)》(七)08-043虛信道和虛網(wǎng)絡在死鎖的4個條件（互斥、占有并等待、不可剝奪、循環(huán)等待）中，避免路由死鎖主要通過避免循環(huán)等待來實現(xiàn)。網(wǎng)絡通信中的鏈路（信道）是雙向的，路由時容易產(chǎn)生回路。如果避免網(wǎng)絡通信中產(chǎn)生回路，那么就不會形成循環(huán)等待，路由也就不會發(fā)生死鎖?！斗植际较到y(tǒng)》(七)08-044123456789虛信道和虛網(wǎng)絡一種辦法是通過劃分子網(wǎng)，每個子網(wǎng)中沒有回路。不同方向的網(wǎng)絡通信在不同子網(wǎng)中進行，從而避免死鎖。例：1234567891234567893×3網(wǎng)格雙Y信道網(wǎng)正網(wǎng)絡負網(wǎng)絡sdsd（2座橋：不同方向的車輛使用不同的橋。）《分布式系統(tǒng)》(七)08-045虛信道和虛網(wǎng)絡當物理上不存在雙（多）信道時，可以使用虛信道來實現(xiàn)。虛信道多個虛信道對一個物理信道進行復用，每個虛信道都有自己的緩沖器。當物理信道被其它虛信道使用時，就用這個緩沖器保存信息。如果虛信道之間沒有循環(huán)等待，那么就可以避免死鎖。

虛信道同時也可以提高對物理信道的利用率?！斗植际较到y(tǒng)》(七)08-046虛信道和虛網(wǎng)絡虛信道上更高一級的虛擬化是虛網(wǎng)絡。虛網(wǎng)絡一個給定的物理網(wǎng)絡可被分成幾個虛網(wǎng)絡。每個虛網(wǎng)絡包括一系列的虛信道。在虛網(wǎng)絡中相鄰的節(jié)點被映射到物理網(wǎng)絡中的時候也要相鄰。虛信道和虛網(wǎng)絡一個是信道層次上的虛擬化，一個是網(wǎng)絡層次上的虛擬化。必須合理安排虛信道，以避免因為虛信道間的依賴性而產(chǎn)生死鎖；虛網(wǎng)絡通常設計成沒有回路的，其中通信不會產(chǎn)生死鎖。《分布式系統(tǒng)》(七)08-047虛信道和虛網(wǎng)絡例：4個節(jié)點的單向環(huán)。如果同時有幾個路由進程啟動，就會發(fā)生死鎖。為每個鏈路設計2個虛信道來避免死鎖。P1P3P2P0P1P3P2P0Ch0Ch1Ch2Ch3Cl0Cl1Cl2Cl3高虛信道：Ch0、Ch1、Ch2、Ch3

低虛信道：Cl0、Cl1、Cl2、Cl3《分布式系統(tǒng)》(七)08-048虛信道和虛網(wǎng)絡虛信道安排：如果源地址大于目的地址，可以從任何一個信道開始；但一旦使用一個高（低）信道，那么以后也要使用同一信道。如果源地址小于目的地址，首先使用高信道，經(jīng)過P3節(jié)點后，高虛信道切換為低虛信道。 這樣，相應的信道依賴圖如下：P1P3P2P0Ch0Ch1Ch2Ch3Cl0Cl1Cl2Cl3*虛信道Cl0不被使用P1P3P2P0Ch1Ch2Ch3Cl1Cl2Cl3P3P2P1P0Ch0

信道依賴圖中沒有回路，路由不會死鎖！《分布式系統(tǒng)》(七)08-049虛信道和虛網(wǎng)絡DCDL形式化描述： /*最大節(jié)點*/ P(n-1)::= *[initiatearouting [send(m,des)toCh(n-1)

send(m,des)toCl(n-1) ]

receive(m,des)fromCh0

[Pn-1=des

send(m)tolocalprocessor

Pn-1des

send(m,des)toCl(n-1) ] ]《分布式系統(tǒng)》(七)08-0410虛信道和虛網(wǎng)絡 /*其他節(jié)點*/ P(i:0..n-2)::= *[initiatearouting [true

send(m,des)toChi

i>dessend(m,des)toCli ] /*如果i>des，可以使用高信道或低信道；*/ /*如果i<des，則只能使用高信道。*/

receive(m,des)fromCh(i+1)

(orCl(i+1)) [Pi=des

send(m)tolocalprocessor

Pides

send(m,des)toChi

(orCli) ] ]也可以通過虛網(wǎng)絡來實現(xiàn)，而且具有更好的適應性（不一定在最大節(jié)點處切換信道）。（P136，圖7-2b)、c)）《分布式系統(tǒng)》(七)08-0411完全自適應和無死鎖路由適應性和無死鎖是兩個互相矛盾的要求。一個決定性路由可以確保無死鎖，但網(wǎng)絡組件（鏈接或節(jié)點）錯誤時，無法適應，路由只好失效。

另一方面，沒有限制的適應性路由很可能引發(fā)死鎖。

目標：在不引發(fā)死鎖的前提下，盡可能增加適應性?！斗植际较到y(tǒng)》(七)08-0412虛信道類為了做到完全自適應的無死鎖路由，需要引入足夠多的虛信道。當路由開始時，使用虛信道1(vc1)。在第i步使用虛信道i(vci)以及相應的鏈接。這樣，如果一個給定網(wǎng)絡的最長路徑（網(wǎng)絡直徑）是Dmax，就要用Dmax個虛信道。

為了減少虛信道的數(shù)量，可以通過將虛信道分類來實現(xiàn)。將給定網(wǎng)絡分成k個子集：S1,S2,…,Sk，每個子集都不會包含相鄰的節(jié)點。當一個消息從子集Si中的一個節(jié)點移動到子集Sj中的一個節(jié)點時（這里i<j），稱之為正移動；反之為負移動。當發(fā)生負移動時，虛信道標記加1（假定信道標記是從1開始的）。這樣，所需虛信道的個數(shù)就是一個路由路徑中負移動的個數(shù)。

選擇一個合適的k及子集劃分，可以使路由過程中的負移動個數(shù)最小（所需虛信道最少）。《分布式系統(tǒng)》(七)08-0413逃逸信道（Escapechannels）要實現(xiàn)完全自適應的無死鎖路由往往是困難的。通常使用混合路由。系統(tǒng)中包括2個路由，一個是使用標記為非等待的虛信道（不能阻塞）的完全適應性路由；另一個是限制性但無死鎖路由（如決定性路由），使用標記為等待的虛信道（稱為逃逸信道，可以阻塞）。開始時，使用完全適應路由，直到阻塞；然后切換到限制性路由。這樣，當信道不繁忙（不用等待）時，就使用完全適應路由，以滿足適應性要求；當信道繁忙或適應性路由出問題（如死鎖）時，就使用逃逸信道（盡管此時出現(xiàn)阻塞，需要等待），確保了不會死鎖。一個例子：k元n維立方的維度逆轉路由。（P139）《分布式系統(tǒng)》(七)08-0414部分自適應和無死鎖路由具備部分的適應性，且沒有死鎖。通常從決定性、無死鎖路由著手，進行擴展，在其中加入部分的適應性。 討論：2維網(wǎng)格的轉彎模型k元n維立方的平面自適應模型部分自適應的e-立方路由n維立方的轉彎模型部分自適應的XY-路由（基于起源的路由）《分布式系統(tǒng)》(七)08-0415部分自適應和無死鎖路由－2維網(wǎng)格的轉彎模型

2維網(wǎng)格的轉彎模型2維網(wǎng)格中會形成2種抽象回路： 其中包含8種轉彎。決定性的路由（如XY-路由）用到了4種轉彎（先X方向、再Y方向的轉彎）： 從而打破回路，不會產(chǎn)生死鎖。但其沒有適應能力?！斗植际较到y(tǒng)》(七)08-0416部分自適應和無死鎖路由－2維網(wǎng)格的轉彎模型

事實上，可以去掉回路中的一個（轉彎）角來打破回路，同時具備部分適應性（有6個轉彎）：轉彎模型的基本思想就是通過禁止最少的轉彎來增加適應性，同時避免回路。

正向優(yōu)先路由（從負到正，即西到北、南到東的轉彎被禁止）負向優(yōu)先路由（從正到負，即東到南、北到西的轉彎被禁止）（上北下南、左西右東）《分布式系統(tǒng)》(七)08-0417部分自適應和無死鎖路由－2維網(wǎng)格的轉彎模型

由于源和目標的位置的不同，轉彎模型可能有適應性，也可能沒有。

如果目標位于源的東北或西南，那么正向優(yōu)先路由就是完全適應性的。如果目標位于源的東南或西北，那么正向路由就是決定性的。yxd(s)yxs(d)完全適應性的決定性的s(d)d(s)《分布式系統(tǒng)》(七)08-0418k元n維立方的平面自適應模型基本思想：k元n維立方中，在某一段時間將路由的自由度限制到幾個維度，從而既有一定的適應性，又不產(chǎn)生死鎖。如果每次只選2個維度，那么就是平面自適應模型：有A0,A1,…,An這些平面，其中Ai在維度di和di+1方向擴展。如三個平面的例子：A0（維度d0和d1），A1（維度d1和d2），和A2（維度d2和d3）。

部分自適應和無死鎖路由－平面自適應模型d0d1d2d3A0A1A2《分布式系統(tǒng)》(七)08-0419對每個平面Ai，引入3個虛信道，1個沿第i維，2個沿第(i+1)維。將第i維的虛信道分成2個單向信道，第(i+1)維的2個虛信道分開，從而形成這個平面（相當于2維網(wǎng)格）上的2個子網(wǎng)：一個正網(wǎng)絡、一個負網(wǎng)絡。Ai平面內部的適應性路由可以使用前述2維網(wǎng)格的正負網(wǎng)絡路由來實現(xiàn)：依據(jù)源和目標的位置不同而選用正網(wǎng)絡或者負網(wǎng)絡。如果目標的標識大于源標識，則選用正網(wǎng)絡；否則，選用負網(wǎng)絡。

相對于完全適應而言，平面適應方法犧牲了一些路由自由度（適應性），但大大降低了虛信道的數(shù)目。相對于決定性路由而言，平面適應方法在一個平面中路由時具有適應性。部分自適應和無死鎖路由－平面自適應模型《分布式系統(tǒng)》(七)08-0420對一個超立方中的任意回路，總能找出沿著某個維度（設為第i維）的2個鏈接，其中一個鏈接是從第i位為0的節(jié)點到第i位為1的節(jié)點（正向鏈接），另一個是從第i位為1的節(jié)點到第i位為0的節(jié)點（負向鏈接）。

為了打破一個回路，禁止從較高維度的正向鏈接向沿著維度i的負向鏈接轉換，除非這個轉換符合e-立方路由。從而擴展了e-立方路由的限制，增加了適應性。部分自適應和無死鎖路由－擴展e-立方路由《分布式系統(tǒng)》(七)08-0421部分自適應和無死鎖路由－擴展e-立方路由即：如果e-立方路由滿足維度遞增的順序，一個沿著維度dim(c1)的信道c1到一個沿著維度dim(c2)的信道c2的轉換是允許的當且僅當下述條件中的一個為真：dim(c1)<dim(c2)（滿足e-立方要求），或c2是正向的假定維度是從右向左編號的（最右邊的一位對應于維度1），那么變換：（10010，00010）→（00010，00000）是不允許的；變換（10010，10110）→（10110，11110）（滿足條件1和條件2）和變換（10010，10110）→（10110，00110）（滿足條件1）是允許的。

《分布式系統(tǒng)》(七)08-0422將轉彎模型擴展到n維立方中。n維立方中，假定s=snsn-1…s1和d=dndn-1…d1是源和目標節(jié)點。設S是s和d所不同的維度的集合。S被分為S1（正向轉換集合）和S2（負向轉換集合）。即，如果si=0且di=1則i∈S1，如果si=1且di=0則i∈S2。路由分成兩個階段：在第一階段，消息按照任意順序沿著集合S1中的維度路由；在第二階段，消息按照任意順序沿著集合S2中的維度路由。（兩階段期間都具有適應性，但都沒有回路！）部分自適應和無死鎖路由－n維立方的轉彎模型《分布式系統(tǒng)》(七)08-0423例：如果s=0101和d=1010，那么S1={2，4}、S2={1，3}。下面的路由路徑是合法的： 0101→1101→1111→1011→1010 0101→0111→1111→1011→1010 0101→1101→1111→1110→1010 0101→0111→1111→1110→1010適應性分析：n維立方中，一個完全適應性的路由算法中，有|S|!種不同的路由選擇。使用本擴展轉彎模型，這個數(shù)字是|S1|!×|S2|!。如：當s=0101和d=1010時，有|S|=4，|S1|=2，|S2|=2。使用完全適應性路由算法有|S|!=4!=24種路由選擇，而使用本模型有|S1|!×|S2|!=2!×2!=4種路由選擇。部分自適應和無死鎖路由－n維立方的轉彎模型《分布式系統(tǒng)》(七)08-0424基于起源的路由是2維網(wǎng)格XY-路由的一個擴展。在2維網(wǎng)格中預先選定一個起源節(jié)點o，網(wǎng)絡被分成2個子網(wǎng)：IN子網(wǎng)（包括所有指向起源節(jié)點o的單向信道）和OUT子網(wǎng)（包括所有離開起源節(jié)點o的單向信道）。以起源節(jié)點o和目標節(jié)點d為對角頂點的矩形建立一個outbox。部分自適應和無死鎖路由－基于起源的路由圖中僅僅顯示了IN子網(wǎng)?？梢酝ㄟ^將圖中的每個鏈接反向來得到OUT子網(wǎng)。sdooutboxoutbox包含了所有位于目標節(jié)點d和起源節(jié)點o之間的最短路徑上的節(jié)點。《分布式系統(tǒng)》(七)08-0425路由分成兩個階段。階段1是從源s到起源節(jié)點o，階段2是從起源節(jié)點o到目標節(jié)點d。路由的第一階段使用IN子網(wǎng)，第二階段使用OUT子網(wǎng)。（兩階段中都沒有回路！）確切地說，基于起源的路由使用IN子網(wǎng)將消息從源向目標區(qū)域靠近（以得到部分適應性）；一旦消息到達outbox邊界，就將切換為OUT子網(wǎng)向目標節(jié)點d轉發(fā)（也有部分適應性）。部分自適應和無死鎖路由－基于起源的路由《分布式系統(tǒng)》(七)08-0426容錯單播容錯單播：不增加空節(jié)點和/或鏈接，通過使用網(wǎng)絡中已有的冗余來達到容錯。具有一定的適應性，且保證無死鎖。容錯單播路由算法主要考慮：最短路徑或非最短路徑。錯誤類型：鏈接錯、節(jié)點錯或者二者都有。出錯的組件的個數(shù)是有限的還是無限的。對錯誤分布的了解：局部、全局和有限的全局。冗余或非冗余?；赝嘶蛘咔斑M?！斗植际较到y(tǒng)》(七)08-04272維網(wǎng)格和圓環(huán)中的容錯單播－基于局部信息的路由

在2維網(wǎng)絡中，如果源和目標都有四個鄰居，那么2維網(wǎng)的冗余路由可以至少經(jīng)受三個錯誤（鏈接和/或節(jié)點）。所以，2維網(wǎng)絡可以實現(xiàn)容錯路由。將2維網(wǎng)絡的錯誤節(jié)點框定在一個凸起的區(qū)域（稱為錯誤塊），以便路由時繞過錯誤塊，而方便實現(xiàn)2維網(wǎng)絡的容錯路由。錯誤塊框定目標：包含所有錯誤節(jié)點，且框進去的節(jié)點數(shù)盡量少。有2種方法：基本安全/非安全節(jié)點定義所有錯誤節(jié)點都是不安全的。所有非錯誤節(jié)點開始時都是安全的。如果一個非錯誤節(jié)點有兩個或兩個以上的非安全鄰居，那么它的狀態(tài)就變?yōu)榉前踩摹？梢宰C明，基本錯誤塊是分離的且它們間的距離最少是3。《分布式系統(tǒng)》(七)08-04282維網(wǎng)格和圓環(huán)中的容錯單播－基于局部信息的路由

擴展安全/非安全節(jié)點的定義所有錯誤節(jié)點都是不安全的。所有非錯誤節(jié)點開始時都是安全的。如果一個非出錯節(jié)點在兩個維度上都有錯誤的或不安全的鄰居，那么它的狀態(tài)就變?yōu)榉前踩摹？梢宰C明，擴展錯誤塊是分離的且它們間的距離最少是2。例：擴展安全/非安全節(jié)點的定義所有錯誤節(jié)點都是不安全的。所有非錯誤節(jié)點開始時都是安全的。如果一個非出錯節(jié)點在兩個維度上都有錯誤的或不安全的鄰居，那么它的狀態(tài)就變?yōu)榉前踩摹？梢宰C明，擴展錯誤塊是分離的且它們間的距離最少是2。例：基本錯誤塊擴展錯誤塊（節(jié)點數(shù)少）非安全節(jié)點(形成錯誤塊)錯誤節(jié)點《分布式系統(tǒng)》(七)08-04292維網(wǎng)格和圓環(huán)中的容錯單播－基于局部信息的路由

框定錯誤塊后，在2維網(wǎng)絡上進行容錯路由：1.如果沒有因為錯誤塊阻塞，那么就按照無錯的情況進行路由。2.如果在X維（或Y維）阻塞，那么在Y維（或X維）路由。3.如果是在X維度受到阻塞，而Y維度的距離已經(jīng)接近零了，就有必要進行曲折路由。隨便選擇一個Y方向，開始曲折路由。首先試著從X維度到達目標。繼續(xù)沿著X方向，直到Y方向正確為止。就是說，沿著出錯塊的邊緣路由。（Y維情況類似）《分布式系統(tǒng)》(七)08-0430在掌握了有限全局信息的條件下，Wu提出了有錯誤塊的2維網(wǎng)格的最優(yōu)容錯路由算法。首先，可以證明：2維網(wǎng)格中，設節(jié)點(0,0)是源節(jié)點，節(jié)點(i,j)是目標節(jié)點。如果沒有錯誤塊通過X和Y軸，那么至少存在一個始于(0,0)的最優(yōu)路徑，長度為|i|+|j|。定義：如果這一結果對任意位置的目標節(jié)點，任何數(shù)目和分布的錯誤塊都是成立的，相應的源叫做安全的。擴展上述結果和定義，允許X和Y軸有出錯塊，只要它們到源的距離分別大于|i|和|j|就行。這樣的源節(jié)點叫做擴展安全的。（這里的安全節(jié)點的概念和在錯誤塊中使用的有所不同。）2維網(wǎng)格和圓環(huán)中的容錯單播－基于有限全局信息的路由

《分布式系統(tǒng)》(七)08-0431Wu有2個最優(yōu)和適應性容錯的路由算法：面向目標路由和面向源路由。為簡單起見，假定源節(jié)點是(0,0)，目標節(jié)點是(i,j)，且i,j0。就是說，路由永遠向東北方向。在面向目標路由中，引入最短路徑區(qū)域（regionofminimalpaths,RMP）：對于給定的目標和源，RMP包括了最短路徑的所有中間節(jié)點。

2維網(wǎng)格和圓環(huán)中的容錯單播－基于有限全局信息的路由

《分布式系統(tǒng)》(七)08-0432構建RMP：路徑A：做一條從目標節(jié)點(i,j)開始到Y軸結束的線，當遇到錯誤塊時，先向南繞過錯誤塊，然后繼續(xù)向西。路徑B：同樣，做一條從(i,j)開始向南到X軸截止的線，當遇到錯誤塊時，先向西繞過錯誤塊，然后繼續(xù)向南。2維網(wǎng)格和圓環(huán)中的容錯單播－基于有限全局信息的路由

(i,j)目標源(0,0)yxRMP路徑A路徑B《分布式系統(tǒng)》(七)08-0433當源是擴展安全時，使用面向目標路由：

源通過一個最優(yōu)或不是最優(yōu)的路徑向目標發(fā)送一個信號。接到信號后，目標發(fā)送2個信號：一個向西，一個向南。向西的信號建立RMP的路徑A，向南的信號建立RMP的路徑B。一旦源收到來自目標的2個信號，就意味著RMP已經(jīng)建立起來了。源節(jié)點就用任何一種適應性最小路由發(fā)送路由消息。遇到路徑A（或路徑B）的邊界時，剩下的路由就要沿著路徑A（路徑B）發(fā)往目標。2維網(wǎng)格和圓環(huán)中的容錯單播－基于有限全局信息的路由

《分布式系統(tǒng)》(七)08-0434Wu面向源路由。（P146～147，自學）2維網(wǎng)格和圓環(huán)中的容錯單播－基于有限全局信息的路由

《分布式系統(tǒng)》(七)08-04352維網(wǎng)格和圓環(huán)中的容錯單播－基于其他錯誤模型的路由

利用矩形錯誤塊模型實現(xiàn)2維網(wǎng)絡的容錯路由很簡單。但矩形錯誤塊框進去較多的非出錯節(jié)點，這些非出錯節(jié)點在路由中不起作用，這損失了一些適應性。Wu將錯誤塊模型擴展為直角凸多邊形模型，進一步縮小了錯誤塊的范圍，將更多的非出錯節(jié)點加入到路由中。直角凸多邊形模型使用了活躍/不活躍節(jié)點的概念：所有出錯節(jié)點都是不活躍的，所有安全節(jié)點都是活躍的。一個非安全節(jié)點開始的時候是不活躍的，但如果它有兩個或兩個以上的活躍鄰居，那么它就是活躍的。因此，對于一個非出錯節(jié)點，有三種可能情況：1)安全且活躍；2)非安全但活躍；3)非安全且不活躍。所有不活躍的節(jié)點組成一個直角凸多邊形，作為錯誤塊?！斗植际较到y(tǒng)》(七)08-0436已經(jīng)證明，對n維立方中的任何2點u和w，如果H(u,w)=k，那么從u到w有n條點分離路徑。這些路徑中，有k條長度為k的路徑，有(n-k)條長度為k+2的路徑。如果出錯組件的數(shù)目L小于n，那么從u到w就至少存在1條可用路徑。也就是說，這時的容錯單播路由是可能的。超立方中的容錯單播－基于局部信息的模型《分布式系統(tǒng)》(七)08-0437Chen和Shin給出了4種基于局部信息的容錯單播算法：1)出錯組件小于n，不確保有最優(yōu)路徑；2)出錯組件小于n，確保有最優(yōu)路徑；3)出錯組件無限制，不確保有最優(yōu)路徑；4)出錯組件無限制，確保有最優(yōu)路徑；我們討論第1種算法。首先定義：等位序列[d1,d2,…,dk]（初始時也叫首選維度）列出了當前節(jié)點與目標節(jié)點不同的所有維度。如，0010和0111是當前節(jié)點（源節(jié)點）和目標節(jié)點，那么相應的等位序列（首選維度）就是[1,3]。

空余維度：那些沒有在首選維度中出現(xiàn)的維度。算法中以空余維度標記記錄那些可用的空余維度。如上面的空余維度是[2,4]，其標記是0101。超立方中的容錯單播－基于局部信息的模型《分布式系統(tǒng)》(七)08-0438算法如下：為了表示一個消息的目標，等位序列要和消息一起傳送?？沼嗑S度標記（源節(jié)點發(fā)起時，設為全0）也要一起傳送，以便用這些維度來繞過出錯組件。因此，消息表示為（k,[d1,d2,…,dk](等位序列),消息,標記(空余維度)）。其中k是剩余路徑的長度，當k=0時，消息到達目標。等位序列和空余維度標記在路由過程中隨著當前節(jié)點的變化也將不斷更新。當節(jié)點收到一個消息時，節(jié)點檢查k的值以便知道本節(jié)點是否是目標。如果不是，節(jié)點將嘗試按照剩下的等位序列中指定的維度發(fā)送消息，以努力沿著最短路徑傳送。然而，如果通往最短路徑的維度的那個鏈接出錯，這個節(jié)點將使用空余維度通過另外的路徑發(fā)送消息。超立方中的容錯單播－基于局部信息的模型《分布式系統(tǒng)》(七)08-0439算法正式的DCDL描述： P(u)::=[initiate-routing-process send(k,[d1,d2,…,dk],m,0)toP(u)

receive(k,[d1,d2,…,dk],message,tag)

[k=0save(message)

k0intermediate-node ] ]超立方中的容錯單播－基于局部信息的模型《分布式系統(tǒng)》(七)08-0440

intermediate-node::= [ Thedjth(1jk)linkandneighborarebothhealthy [send(k-1,[d1,d2,…,dj-1,dj+1,…,dk],

message,tag)tou(dj) ]

Nolinkandneighborarebothhealthy [1jk||tag(dj):=1;

tag(h):=1,whereh=min{i:tag(i)=0,1in}; send(k+1,[d1,d2,…,dk,h],message,tag)tou(h) ] ]超立方中的容錯單播－基于局部信息的模型《分布式系統(tǒng)》(七)08-0441例：假設消息m從u=0110路由到w=1001。在u=0110處的最初消息是(4,[1,2,3,4],m,0000)。節(jié)點0110將(3,[2,3,4],m,0000)發(fā)送給01101＝0111，隨后節(jié)點0111將(2,[3,4],m,0000)發(fā)送給0101。由于0101的第3維鏈接出現(xiàn)錯誤，節(jié)點0101將發(fā)送(1,[3],m,0000)到1101。然而，由于1101的第3維的鏈接出現(xiàn)錯誤，節(jié)點1101將使用第1維（此時空余維度標記=0100〕發(fā)送消息(2,[3,1],m,0101)到1100。1100發(fā)送(1,[1],m,0101)到1000。但節(jié)點1000的第1維鏈接又出現(xiàn)錯誤，這時使用第2維（此時空余維度標記=0101〕發(fā)送(2,[1,2],m,0111)到1010。之后，消息將經(jīng)過1011到達目標1001。超立方中的容錯單播－基于局部信息的模型w11101100111111011010100010111001u01100100011101010010000000110001×××路徑長度＝8，顯然不是最優(yōu)路由。《分布式系統(tǒng)》(七)08-0442超立方中的容錯單播－基于有限全局信息的模型：安全等級安全等級是有限全局信息，它實際上就是每個節(jié)點周圍鄰居中失效節(jié)點的大致數(shù)目。定義：設S(a)=k是節(jié)點a的安全等級，這里k被稱為安全等級，a被稱為是k-安全的。一個失效節(jié)點是0-安全的，即最低的安全等級；而n-安全的節(jié)點是安全級別最高的，也叫安全節(jié)點；如果k≠n，那么一個k-安全的節(jié)點就是不安全的。設(S0,S1,S2,…Sn-1)，0≦Si≦n，是n維立方中節(jié)點a的鄰居節(jié)點的安全等級的非遞減安全狀態(tài)序列，即S0≦Si≦Si+1≦Sn-1。節(jié)點a的安全狀態(tài)定義如下：如果(S0,S1,S2,…,Sn-1)≧(0,1,2,…,n-1)，那么S(a)=n；否則，如果(S0,S1,S2,…Sk-1)≧(0,1,2,…,k-1)∧(Sk=k-1)，那么S(a)＝k。《分布式系統(tǒng)》(七)08-0443超立方中的容錯單播－基于有限全局信息的模型：安全等級如下圖的出錯超立方中，節(jié)點1000，1010，1100，1110，1101和1111是安全的（4-安全的）；出錯節(jié)點0011，0100，0110和1001是0-安全的；節(jié)點0001，0010，0111和1011是1-安全的，因為它們每個都有2個出錯鄰居節(jié)點，安全狀態(tài)序列是（0,0,x,x）；節(jié)點0000和0101是2-安全的。44444401111011001111110110101000101110010021211001100100011101010010000000110001《分布式系統(tǒng)》(七)08-0444超立方中的容錯單播－基于有限全局信息的模型：安全等級使用下面的算法，可以得到每個節(jié)點的安全等級。其中每個節(jié)點a(i)都保存了一個鄰居節(jié)點的非遞減狀態(tài)序列。開始時，所有非出錯節(jié)點都是n-安全的，所有出錯節(jié)點都是0-安全的。算法需要n-1次重復達到穩(wěn)定狀態(tài)。 global-status::=(n-1)[P(0)||P(1)P(2)…P(2n-1)] P(i)::=determineanondecreasingstatussequence (S0,S1,S2,…Sn-1)ofneighboringnodes; [(S0,S1,S2,…Sn-1)≧(0,1,2,…,n-1)

S(a(i))=n

(S0,S1,S2,…Sk-1)≧(0,1,2,…,k-1)∧(Sk=k-1)

S(a(i))=k ]《分布式系統(tǒng)》(七)08-0445安全等級有以下性質：如果一個節(jié)點的安全等級是k（0<k≦n），那么在k海明距離內，至少存在一個從該節(jié)點到任意節(jié)點的海明距離路徑。也就是說，當源的安全等級大于或等于源和目標之間的海明距離的時候，就可以保證最優(yōu)路由。實際上，可以在每一步通過選擇具有最高安全等級的鄰居（相同時，隨機選擇一個）來產(chǎn)生最優(yōu)路徑。一個引導向量（定義為當前節(jié)點和目標節(jié)點的按位異或）被附加在路由消息上面。

超立方中的容錯單播－基于有限全局信息的模型：安全等級《分布式系統(tǒng)》(七)08-0446超立方中的容錯單播－基于有限全局信息的模型：安全等級下圖例：源s=1110向d=0001單播。引導向量N=sd=1111，H(s,d)=4，源節(jié)點s的安全等級是4，可以使用最優(yōu)路由。在源節(jié)點的首選轉發(fā)節(jié)點中，1111作為3個具有最高安全等級的鄰居節(jié)點之一被隨機選中。引導向量N對應的該位置為無效(清0)后也和消息一起被發(fā)送。其后，1111根據(jù)引導向量有效位的指示和最高安全等級選擇原則，選擇鄰居節(jié)點1101轉發(fā)。同樣，1101選擇0101轉發(fā)，0101選擇0001轉發(fā)到目標。44444401111011001111110110101000101110010021211001100100011101010010000000110001sd《分布式系統(tǒng)》(七)08-0447超立方中的容錯單播－基于有限全局信息的模型：安全等級事實上，當源節(jié)點的安全等級比源s和目標d之間的海明距離H(s,d)=|sd|小的時候，根據(jù)引導向量有效位的指示，只要存在一個安全等級不小于H(s,d)-1的鄰居，仍然可以通過將消息轉發(fā)到這個節(jié)點來實現(xiàn)最優(yōu)路由。否則，如果存在一個安全等級不低于H(s,d)+1的空閑鄰居節(jié)點（引導向量無效位上的鄰居），也可以通過將消息轉發(fā)到這個節(jié)點實現(xiàn)次優(yōu)路由，結果路徑的長度是H(s,d)+2。例：44444401111011001111110110101000101110010021211001100100011101010010000000110001ds《分布式系統(tǒng)》(七)08-0448安全等級模型的擴展，討論安全等級為k的節(jié)點到達超過k海明距離節(jié)點的最優(yōu)路由問題。 （P151～152）

超立方中的容錯單播－基于有限全局信息的模型：安全向量《分布式系統(tǒng)》(七)08-0449容錯廣播根據(jù)下面幾個方面的特點分類：（1）每個目標節(jié)點接收消息的方法可以接收多個拷貝（冗余廣播）只能接收一個拷貝（非冗余廣播）（2）每個節(jié)點保存的信息局部有限全局全局（3）出錯組件的類型鏈接節(jié)點（4）出錯組件的數(shù)目有限無限容錯廣播《分布式系統(tǒng)》(七)08-0450容錯廣播－使用全局信息的廣播

Wu提出了n維立方中一個使用全局信息進行廣播的有效算法（廣播結構在源節(jié)點根據(jù)全局信息就可以確定）。算法前提：錯誤類型是鏈接錯誤，錯誤數(shù)目n-1。算法包含以下兩步：1）分離過程：在源節(jié)點s決定（分離出）等位序列（算法1）。2）容錯廣播過程：根據(jù)得到的等位序列進行廣播（算法2）。

《分布式系統(tǒng)》(七)08-0451容錯廣播－使用全局信息的廣播

算法1{分離過程}/*源節(jié)點s在Qn中，初始時m=1*/1.隨機選擇一個維度im，保證Qn-m+1中的第im維沒有出錯鏈接（如果初始錯誤數(shù)目n-1，這一點總是做得到）。Qn-m+1沿著第i維分成了（Qn-m,Qn-m'）。如果不存在這樣的維度，則返回“不可行”。2.如果Qn-m+1中的所有出錯鏈接都位于Qn-m（或Qn-m

‘）中，則停止并返回（Tnonop，imim-1…i1）（或者（Top，imim-1…i1）），這里imim-1…i1是通過第一步得到的維度序列。（注意imim-1…i1的順序和它們被選擇的順序是相反的。）否則，將m加1，對Qn-m（包含s）重復步驟1和2，直到m=n為止。通過算法1的過程，將分離出一個完全無錯的子立方?！斗植际较到y(tǒng)》(七)08-0452容錯廣播－使用全局信息的廣播

算法2{容錯廣播過程}/*（類型，imim-1…i1）是由算法1確定的，s在Qn-m中*/1.（最優(yōu)路由）如果類型=Top，Qn-m中沒有出錯鏈接，那么可以對Qn-m使用一般基于二分樹的廣播而沒有限制，在Qn-m外部的廣播，依據(jù)維度順序cs=imim-1…i1。2.（非最優(yōu)廣播）如果類型=Tnonop，則Qn-m'中沒有出錯鏈接，使用如下步驟：a)s沿著第im維將廣播數(shù)據(jù)發(fā)送給它的鄰居（記為s(im)）。b)在Qn-m'中使用基于一般二分樹的廣播，s(im)是源節(jié)點。c)