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

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

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

信道依賴圖中沒有回路，路由不會(huì)死鎖！《分布式系統(tǒng)》(七)08-049虛信道和虛網(wǎng)絡(luò)DCDL形式化描述： /*最大節(jié)點(diǎn)*/ 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)絡(luò) /*其他節(jié)點(diǎn)*/ 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)絡(luò)來實(shí)現(xiàn)，而且具有更好的適應(yīng)性（不一定在最大節(jié)點(diǎn)處切換信道）。（P136，圖7-2b)、c)）《分布式系統(tǒng)》(七)08-0411完全自適應(yīng)和無死鎖路由適應(yīng)性和無死鎖是兩個(gè)互相矛盾的要求。一個(gè)決定性路由可以確保無死鎖，但網(wǎng)絡(luò)組件（鏈接或節(jié)點(diǎn)）錯(cuò)誤時(shí)，無法適應(yīng)，路由只好失效。

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

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

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

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

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

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

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

由于源和目標(biāo)的位置的不同，轉(zhuǎn)彎模型可能有適應(yīng)性，也可能沒有。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

空余維度：那些沒有在首選維度中出現(xiàn)的維度。算法中以空余維度標(biāo)記記錄那些可用的空余維度。如上面的空余維度是[2,4]，其標(biāo)記是0101。超立方中的容錯(cuò)單播－基于局部信息的模型《分布式系統(tǒng)》(七)08-0438算法如下：為了表示一個(gè)消息的目標(biāo)，等位序列要和消息一起傳送。空余維度標(biāo)記（源節(jié)點(diǎn)發(fā)起時(shí)，設(shè)為全0）也要一起傳送，以便用這些維度來繞過出錯(cuò)組件。因此，消息表示為（k,[d1,d2,…,dk](等位序列),消息,標(biāo)記(空余維度)）。其中k是剩余路徑的長(zhǎng)度，當(dāng)k=0時(shí)，消息到達(dá)目標(biāo)。等位序列和空余維度標(biāo)記在路由過程中隨著當(dāng)前節(jié)點(diǎn)的變化也將不斷更新。當(dāng)節(jié)點(diǎn)收到一個(gè)消息時(shí)，節(jié)點(diǎn)檢查k的值以便知道本節(jié)點(diǎn)是否是目標(biāo)。如果不是，節(jié)點(diǎn)將嘗試按照剩下的等位序列中指定的維度發(fā)送消息，以努力沿著最短路徑傳送。然而，如果通往最短路徑的維度的那個(gè)鏈接出錯(cuò)，這個(gè)節(jié)點(diǎn)將使用空余維度通過另外的路徑發(fā)送消息。超立方中的容錯(cuò)單播－基于局部信息的模型《分布式系統(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 ] ]超立方中的容錯(cuò)單播－基于局部信息的模型《分布式系統(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) ] ]超立方中的容錯(cuò)單播－基于局部信息的模型《分布式系統(tǒng)》(七)08-0441例：假設(shè)消息m從u=0110路由到w=1001。在u=0110處的最初消息是(4,[1,2,3,4],m,0000)。節(jié)點(diǎn)0110將(3,[2,3,4],m,0000)發(fā)送給01101＝0111，隨后節(jié)點(diǎn)0111將(2,[3,4],m,0000)發(fā)送給0101。由于0101的第3維鏈接出現(xiàn)錯(cuò)誤，節(jié)點(diǎn)0101將發(fā)送(1,[3],m,0000)到1101。然而，由于1101的第3維的鏈接出現(xiàn)錯(cuò)誤，節(jié)點(diǎn)1101將使用第1維（此時(shí)空余維度標(biāo)記=0100〕發(fā)送消息(2,[3,1],m,0101)到1100。1100發(fā)送(1,[1],m,0101)到1000。但節(jié)點(diǎn)1000的第1維鏈接又出現(xiàn)錯(cuò)誤，這時(shí)使用第2維（此時(shí)空余維度標(biāo)記=0101〕發(fā)送(2,[1,2],m,0111)到1010。之后，消息將經(jīng)過1011到達(dá)目標(biāo)1001。超立方中的容錯(cuò)單播－基于局部信息的模型w11101100111111011010100010111001u01100100011101010010000000110001×××路徑長(zhǎng)度＝8，顯然不是最優(yōu)路由?！斗植际较到y(tǒng)》(七)08-0442超立方中的容錯(cuò)單播－基于有限全局信息的模型：安全等級(jí)安全等級(jí)是有限全局信息，它實(shí)際上就是每個(gè)節(jié)點(diǎn)周圍鄰居中失效節(jié)點(diǎn)的大致數(shù)目。定義：設(shè)S(a)=k是節(jié)點(diǎn)a的安全等級(jí)，這里k被稱為安全等級(jí)，a被稱為是k-安全的。一個(gè)失效節(jié)點(diǎn)是0-安全的，即最低的安全等級(jí)；而n-安全的節(jié)點(diǎn)是安全級(jí)別最高的，也叫安全節(jié)點(diǎn)；如果k≠n，那么一個(gè)k-安全的節(jié)點(diǎn)就是不安全的。設(shè)(S0,S1,S2,…Sn-1)，0≦Si≦n，是n維立方中節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)的安全等級(jí)的非遞減安全狀態(tài)序列，即S0≦Si≦Si+1≦Sn-1。節(jié)點(diǎn)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?！斗植际较到y(tǒng)》(七)08-0443超立方中的容錯(cuò)單播－基于有限全局信息的模型：安全等級(jí)如下圖的出錯(cuò)超立方中，節(jié)點(diǎn)1000，1010，1100，1110，1101和1111是安全的（4-安全的）；出錯(cuò)節(jié)點(diǎn)0011，0100，0110和1001是0-安全的；節(jié)點(diǎn)0001，0010，0111和1011是1-安全的，因?yàn)樗鼈兠總€(gè)都有2個(gè)出錯(cuò)鄰居節(jié)點(diǎn)，安全狀態(tài)序列是（0,0,x,x）；節(jié)點(diǎn)0000和0101是2-安全的。44444401111011001111110110101000101110010021211001100100011101010010000000110001《分布式系統(tǒng)》(七)08-0444超立方中的容錯(cuò)單播－基于有限全局信息的模型：安全等級(jí)使用下面的算法，可以得到每個(gè)節(jié)點(diǎn)的安全等級(jí)。其中每個(gè)節(jié)點(diǎn)a(i)都保存了一個(gè)鄰居節(jié)點(diǎn)的非遞減狀態(tài)序列。開始時(shí)，所有非出錯(cuò)節(jié)點(diǎn)都是n-安全的，所有出錯(cuò)節(jié)點(diǎn)都是0-安全的。算法需要n-1次重復(fù)達(dá)到穩(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安全等級(jí)有以下性質(zhì)：如果一個(gè)節(jié)點(diǎn)的安全等級(jí)是k（0<k≦n），那么在k海明距離內(nèi)，至少存在一個(gè)從該節(jié)點(diǎn)到任意節(jié)點(diǎn)的海明距離路徑。也就是說，當(dāng)源的安全等級(jí)大于或等于源和目標(biāo)之間的海明距離的時(shí)候，就可以保證最優(yōu)路由。實(shí)際上，可以在每一步通過選擇具有最高安全等級(jí)的鄰居（相同時(shí)，隨機(jī)選擇一個(gè)）來產(chǎn)生最優(yōu)路徑。一個(gè)引導(dǎo)向量（定義為當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的按位異或）被附加在路由消息上面。

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

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

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

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

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

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

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