胖樹網(wǎng)絡(luò)路由算法的研究

胖樹網(wǎng)絡(luò)路由算法的研究

1不同網(wǎng)絡(luò)鏈路算法的研究這是1985年提出的一個典型的多層面交換網(wǎng)絡(luò)（m）。胖樹結(jié)構(gòu)具有等分帶寬高、網(wǎng)絡(luò)直徑低、擴(kuò)展性好等優(yōu)點(diǎn),因此廣泛應(yīng)用于超級計算系統(tǒng)和數(shù)據(jù)中心的互連網(wǎng)絡(luò),例如中國國家超算天津中心(NSCC-TJ)的“天河一號(Tianhe-1A)”、美國洛斯阿拉莫斯國家實(shí)驗(yàn)室(LANL)的“走鵑(Roadrunner)”、德國于利希研究中心(FZJ)的“于利希藍(lán)色基因(Jugene)”和部署在中國國家超算廣州中心(NSCC-GZ)的“天河二號(Tianhe-2)”等。胖樹結(jié)構(gòu)通常采用最短路由,即報文先從源處理節(jié)點(diǎn)上行到源和目的處理節(jié)點(diǎn)的最近公共祖先交換器(Switch),然后再從公共祖先交換器下行到目的處理節(jié)點(diǎn)。胖樹結(jié)構(gòu)的路徑多樣性體現(xiàn)在任意的源和目的處理節(jié)點(diǎn)間可能存在多個最近公共祖先交換器。各種胖樹路由算法的差異主要體現(xiàn)于選擇最近公共祖先交換器的依據(jù)和方法不同?，F(xiàn)有胖樹路由缺乏良好的對稱性,即從任意處理節(jié)點(diǎn)A到B的路徑所包含的鏈路不一定等于從B到A的路徑所包含的鏈路。這不利于通過基于網(wǎng)絡(luò)應(yīng)用層的通信測試快速定位網(wǎng)絡(luò)鏈路故障,因此鏈路故障的可診斷性較差。為此,本文考慮到網(wǎng)絡(luò)鏈路故障的易診斷性需求,在不降低路由算法性能的前提下,針對胖樹結(jié)構(gòu)提出了一種新型路由算法BT-OSRM(Back-TrackObliviouSRoutingalgorithM)。2規(guī)定了運(yùn)動路由及其算法在胖樹拓?fù)浣Y(jié)構(gòu)研究方面,常用的胖樹拓?fù)淠Ｐ陀袃煞N,一種是k-aryn-tree模型,另一種是m-portn-tree模型。k-aryn-tree模型提出較早,其來源于k-aryn-flies多級交換網(wǎng)絡(luò),先前的大量胖樹方面的研究都是基于該模型的。與k-aryn-tree模型相比,m-portn-tree模型定義所有交換器相連端口數(shù)目相同,這更合乎胖樹結(jié)構(gòu)的實(shí)際應(yīng)用,因此最近在胖樹方面的研究越來越多地采用該模型。在胖樹確定性路由算法研究方面,MLID(MultipleLocalIDentifier)路由算法針對的是基于分布式查表路由的胖樹,其特點(diǎn)是為每個處理節(jié)點(diǎn)分配多個本地標(biāo)識LID(LocalIDentifier),具體算法由處理節(jié)點(diǎn)尋址、路徑選擇和轉(zhuǎn)發(fā)表賦值等機(jī)制組成。DESTRO算法根據(jù)目的處理節(jié)點(diǎn)編號從源和目的處理節(jié)點(diǎn)的多個最近公共祖先交換器進(jìn)行選擇,其作者認(rèn)為該算法比根據(jù)源處理節(jié)點(diǎn)編號選擇最近公共祖先交換器的算法性能更優(yōu)。OSRM(ObliviouSRoutingAlgorithM)算法綜合考慮源和目的處理節(jié)點(diǎn)編號選擇最近公共祖先交換器,已經(jīng)被證明是確定性能比率(ObliviousPerformanceRatio)最高的路由算法之一。在胖樹路由算法的實(shí)現(xiàn)方面,FIR對傳統(tǒng)的區(qū)間路由IR(IntervalRouting)進(jìn)行了擴(kuò)展,在交換器的每個端口除了設(shè)置IR的區(qū)間首寄存器(First-Interval-Register)和區(qū)間尾寄存器(Last-Interval-Register)外,還額外地設(shè)置掩碼寄存器(Mask-Register)和路由限制寄存器(Routing-Restrictions-Register),以避免路由死鎖。不同于傳統(tǒng)的源路由和分布式查表路由實(shí)現(xiàn)方法,FIR是一種較為新穎的胖樹路由實(shí)現(xiàn)方法。3問題描述3.1交換器端口c,n-2,b本文采用m-portn-tree模型描述胖樹結(jié)構(gòu),其描述方法與文獻(xiàn)[4,5,10]相似。定義1FT(m,n)胖樹模型可完整地描述為:(2)分級特點(diǎn):FT(m,n)胖樹共分為n級,分別編號為第0、1、…、n-1級。第0級包含的交換器數(shù)目為(m/2)n-1,其余各級包含的交換器數(shù)目均為2×(m/2)n-1。(3)交換器的標(biāo)記:交換器標(biāo)記為switch(cn-2,cn-3,…,c1,c0,l),其中l(wèi)∈{0,1,…,n-1},表示該交換器在胖樹中所在的級數(shù);如果l=0或i≠n-2,則ci∈{0,1,…,(m/2)-1},否則如果l∈{1,2,…,n-1}或i=n-2,則ci∈{0,1,…,m-1},其中i∈{0,1,…,n-3,n-2}。(4)交換器端口標(biāo)記:交換器switch(cn-2,cn-3,…,c1,c0,l)的第k個端口標(biāo)記為switch(cn-2,cn-3,…,c1,c0,l)k,其中k∈{0,1,…,m-1}。(5)處理節(jié)點(diǎn)的標(biāo)記:處理節(jié)點(diǎn)標(biāo)記為node(pn-1,pn-2,…,p1,p0),其中如果j=n-1,則pj∈{0,1,…,m-1},否則如果j∈{0,1,…,n-2},則pj∈{0,1,…,(m/2)-1}。(6)交換器間連接規(guī)則:交換器端口switch(cn-2,cn-3,…,c1,c0,l)k與switch(c′n-2,c′n-3,…,c′1,c′0,l′)k′相連,當(dāng)且僅當(dāng)如下等式同時成立:①l′=l-1;②?i(i≠n-l-1),則c′i=ci;③k′=cn-l-1;④k=c′n-l-1+m/2。(7)處理節(jié)點(diǎn)與交換器的連接規(guī)則:處理節(jié)點(diǎn)node(pn-1,pn-2,…,p1,p0)與交換器端口switch(cn-2,cn-3,…,c1,c0,l)k相連,當(dāng)且僅當(dāng)如下等式同時成立:①l=n-1;②?i(i∈{0,1,…,n-3,n-2}),則ci=pi+1;③k=p0。圖1所示為FT(4,3),即4-port3-tree胖樹拓?fù)?。其?圓形和正方形分別代表處理節(jié)點(diǎn)和交換器,其標(biāo)記只顯示了括號中的關(guān)鍵信息。3.2基于路由路徑的雙向路徑為了描述胖樹原路返回路由問題,需要基于FT(m,n)的定義(定義1)進(jìn)一步定義鏈路、路由路徑、反向路由路徑和原路返回路由。定義2(鏈路)處理節(jié)點(diǎn)與交換器的端口或者交換器端口之間的無向連接稱為鏈路,鏈路標(biāo)記為link〈nodei,switchportp〉或link〈switchports,switchportd〉,其中nodei表示處理節(jié)點(diǎn),switchportp、switchports和switchportd表示不同的交換器端口。注意,本文定義的鏈路是無方向的,即link〈nodei,switchportp〉與link〈switchportp,nodei〉,以及l(fā)ink〈switchports,switchportd〉與link〈switchportd,switchports〉對鏈路的標(biāo)記是等價的。定義3(路由路徑)處理節(jié)點(diǎn)間傳輸數(shù)據(jù)時報文(網(wǎng)絡(luò)層數(shù)據(jù)傳輸單元)所經(jīng)過的鏈路序列。假設(shè)路由算法為R,nodes向noded傳輸數(shù)據(jù)時報文共經(jīng)過n條鏈路,它們依次為link0、link1、…、linkn-1,則從nodes到noded的路由路徑標(biāo)記為path{R|nodes→noded},且path{R|nodes→noded}=link0→link1→…→linkn-1?？梢?雖然鏈路是沒有方向性的,但是路由路徑是具有方向性的。通常,稱路由路徑的起始節(jié)點(diǎn)為源處理節(jié)點(diǎn)或源節(jié)點(diǎn),路由路徑的終止節(jié)點(diǎn)為目的處理節(jié)點(diǎn)或目的節(jié)點(diǎn)。定義4(反向路由路徑)處理節(jié)點(diǎn)間反向傳輸數(shù)據(jù)時報文(網(wǎng)絡(luò)層數(shù)據(jù)傳輸單元)所經(jīng)過的鏈路序列。假設(shè)路由算法為R,從nodes到noded的路由路徑為path{R|nodes→noded},則從nodes到noded的反向路由路徑標(biāo)記為Reverse(path{R|nodes→noded}),且Reverse(path{R|nodes→noded})=path{R|noded→nodes}。定義5(路由路徑的反向)對路由路徑所包含的鏈路序列取逆序的操作稱為該路由路徑的反向。假設(shè)路由算法為R,則從nodes到noded的路由路徑path{R|nodes→noded}的反向標(biāo)記為BackTrack(path{R|nodes→noded})。定義6(原路返回路由路徑和算法)對于特定的拓?fù)浣Y(jié)構(gòu)T及其路由算法R而言,如果兩個處理節(jié)點(diǎn)間的反向路由路徑等于路由路徑的反向,則稱這兩個處理節(jié)點(diǎn)間的路由路徑是原路返回路由路徑。如果任意兩個處理節(jié)點(diǎn)間的路由路徑都是原路返回路由路徑,則稱該路由算法R為拓?fù)浣Y(jié)構(gòu)T的原路返回路由算法?？梢?對于特定的拓?fù)浣Y(jié)構(gòu)T中的兩個處理節(jié)點(diǎn)nodes和noded,其路由路徑由其路由算法R確定。如果Reverse(path{R|nodes→noded})=BackTrack(path{R|nodes→noded}),則nodes和noded間的路由路徑為原路返回路由路徑。如果T中的任意兩節(jié)點(diǎn)nodes和noded間的路由路徑都滿足Reverse(path{R|nodes→noded})=BackTrack(path{R|nodes→noded}),則稱R為T的原路返回路由算法。3.3原路返回路由算法定義7(胖樹原路返回路由問題)對于任意的胖樹FT(m,n),尋找其原路返回路由算法R。定義7所描述的問題就是本文算法所要解決的問題。本文沒有針對任意拓?fù)浣Y(jié)構(gòu)研究其原路返回路由算法,這是因?yàn)樵谀承┩負(fù)浣Y(jié)構(gòu)條件下,原路返回路由會造成死鎖。以二維Torus網(wǎng)絡(luò)為例,該拓?fù)浣Y(jié)構(gòu)通常采用維序路由DOR(DimensionOrderRouting)算法,而如果允許原路返回路由,則意味著網(wǎng)絡(luò)的通道依賴圖CGD(ChannelDependencyGraph)會出現(xiàn)環(huán),從而導(dǎo)致死鎖發(fā)生。4bt-osrm路由算法4.1b-osrm3算法的改進(jìn)針對FT(m,n)胖樹模型,文獻(xiàn)已經(jīng)提出了OSRM(包括OSRM2和OSRM3兩種)路由算法。同時,當(dāng)前主流交換器均采用高階實(shí)現(xiàn)技術(shù),其端口數(shù)通常為32、48或64。對于32端口的交換器而言,FT(32,2)和FT(32,3)最多可支持的處理節(jié)點(diǎn)數(shù)目分別為512和8192個;如果交換器的端口數(shù)為48,則FT(48,2)和FT(48,3)最多分別可支持1152和27648個處理節(jié)點(diǎn);對于64端口的交換器而言,FT(64,2)和FT(64,3)最多可支持處理節(jié)點(diǎn)數(shù)目分別達(dá)到2048和65536個;而當(dāng)前世界上運(yùn)算性能最高的超級計算系統(tǒng)“天河二號”由16000個處理節(jié)點(diǎn)構(gòu)成。所以,FT(m,2)和FT(m,3)幾乎可涵蓋所有實(shí)際應(yīng)用的胖樹結(jié)構(gòu)?；谏鲜龇治?本文對OSRM2和OSRM3算法進(jìn)行了改進(jìn),形成了支持原路返回路由的新型算法BT-OSRM(Back-TrackOSRM)。BT-OSRM算法在為兩處理節(jié)點(diǎn)確定路由路徑時,不僅要利用OSRM算法所產(chǎn)生的路由路徑,而且還需要比較處理節(jié)點(diǎn)間的大小關(guān)系。處理節(jié)點(diǎn)間的大小關(guān)系定義如下:4.2bt-osrm算法描述BT-OSRM路由算法就是依據(jù)源處理節(jié)點(diǎn)與目的處理節(jié)點(diǎn)大小關(guān)系選擇路由路徑,即如果源處理節(jié)點(diǎn)大于或等于目的處理節(jié)點(diǎn),則直接依據(jù)OS-RM路由算法計算從源到目的處理節(jié)點(diǎn)間的路由路徑;反之,首先依據(jù)OSRM路由算法計算從目的處理節(jié)點(diǎn)到源處理節(jié)點(diǎn)間的路由路徑,再對該路由路徑進(jìn)行反向,則獲得從源到目的處理節(jié)點(diǎn)間的路由路徑。BT-OSRM算法的另一種描述如下所示:算法1BT-OSRM路由算法此外,如果改變BT-OSRM中節(jié)點(diǎn)大小比較結(jié)果與路由路徑選擇的對應(yīng)關(guān)系,即如果源處理節(jié)點(diǎn)小于或等于目的處理節(jié)點(diǎn),則直接依據(jù)OSRM路由算法計算從源到目的處理節(jié)點(diǎn)間的路由路徑;反之,對依據(jù)OSRM路由算法計算從目的處理節(jié)點(diǎn)到源處理節(jié)點(diǎn)間的路由路徑進(jìn)行反向以獲得從源到目的處理節(jié)點(diǎn)間的路由路徑,該方法與BT-OSRM算法并無本質(zhì)區(qū)別,因此也可視為BT-OS-RM算法。4.3bt-osrm2路由算法描述FT(m,2)結(jié)構(gòu)共包含3×(m/2)個交換器和m2/2個處理節(jié)點(diǎn)。FT(m,2)中所有交換器和處理節(jié)點(diǎn)可分別標(biāo)記為switch(c0,l)和node(p1,p0),其中l(wèi)為交換器所在的級數(shù)。BT-OSRM2路由算法是BT-OSRM算法針對2級胖樹FT(m,2)結(jié)構(gòu)的具體化,其描述如下所示:算法2FT(m,2)的BT-OSRM2路由算法FT(m,3)結(jié)構(gòu)共包含5×(m/2)2個交換器和m2個處理節(jié)點(diǎn)。在FT(m,3)結(jié)構(gòu)中,FT(m,3)中所有交換器和處理節(jié)點(diǎn)可分別標(biāo)記為switch(c1,c0,l)和node(p2,p1,p0),其中l(wèi)為交換器所在的級數(shù)。BT-OSRM3路由算法是BT-OSRM算法針對3級胖樹FT(m,3)結(jié)構(gòu)的具體化,其描述如下所示:算法3FT(m,3)的BT-OSRM3路由算法5特征分析本節(jié)將理論分析BT-OSRM路由算法的一些特性,如原路返回、無死鎖、負(fù)載均衡和最優(yōu)化等。5.1b-osrm函數(shù)定理1BT-OSRM是FT(m,n)胖樹拓?fù)涞脑贩祷芈酚伤惴āＷC明假設(shè)nodei和nodej為FT(m,n)胖樹中任意兩個處理節(jié)點(diǎn),根據(jù)節(jié)點(diǎn)大小關(guān)系共分為三種情況討論:(1)如果,又因?yàn)?所以path{BT-OS-RM|nodej→nodei}=BackTrack(path{OSRM|nodei→nodej}),故Reverse(path{BT-OSRM|nodei→nodej})=BackTrack(path{OSRM|nodei→nodej})=BackTrack(path{BT-OSRM|nodei→nodej})成立。(2)如果nodei=nodej,此與的情況證明相同。(3)如果則,所以根據(jù)對情況(1)的證明結(jié)果,可知Reverse(path{BT-OSRM|nodej→nodei})=BackTrack(path{BT-OSRM|nodej→nodei})成立。所以,BackTrack(Reverse(path{BT-OSRM|nodej→nodei}))=BackTrack(BackTrack(path{BT-OSRM|nodej→nodei}))成立,即BackTrack(path{BT-OSRM|nodei→nodej})=path{BT-OSRM|nodej→nodei}=Reverse(path{BT-OSRM|nodei→nodej})成立。而且,由于nodei和nodej的任意性,所以根據(jù)本文定義6可知,BT-OSRM是FT(m,n)胖樹拓?fù)涞脑贩祷芈酚伤惴?。故定?得證,證畢。5.2b-osrm2路由算法對均勻流量模式的負(fù)載均衡定理2BT-OSRM路由算法是無死鎖的。證明已知OSRM采用的是最短路徑的UP-DOWN路由策略,即從源節(jié)點(diǎn)到目的節(jié)點(diǎn)通信時分為上行和下行兩個階段,在上行階段時,先將數(shù)據(jù)從源處理節(jié)點(diǎn)傳輸?shù)皆春湍康奶幚砉?jié)點(diǎn)的最近公共祖先交換器;在下行階段時,將數(shù)據(jù)從該最近公共祖先交換器傳輸?shù)侥康奶幚砉?jié)點(diǎn)。盡管BT-OSRM對SROM選擇最近公共祖先交換器的方法進(jìn)行了修改,但并沒有修改其TOP-DOWN路由策略,所以BT-OSRM路由算法是無死鎖的。故定理2得證,證畢。對于路由算法的負(fù)載均衡問題,文獻(xiàn)明確給出了多級交換網(wǎng)絡(luò)中路由算法負(fù)載均衡定義。其定義指出:對于給定的胖樹FT(m,n)及其路由算法R和流量模式F,如果胖樹中屬于同一級的各條單向鏈路承載的路由路徑數(shù)目相等,則稱路由算法R在流量模式F下是負(fù)載均衡的。定理3BT-OSRM2和BT-OSRM3路由算法對于均勻流量模式(UniformTrafficPattern)是負(fù)載均衡的。證明已知OSRM2和OSRM3路由算法對于均勻流量模式是負(fù)載均衡的,下面首先證明BT-OSRM2路由算法對于均勻流量模式是負(fù)載均衡的。假設(shè)nodei和nodej為FT(m,2)中的任意兩個處理節(jié)點(diǎn),則分析如下:(1)根據(jù)定理1可知,對于path{BT-OSRM|nodei→nodej}中的任意鏈路linkk,其一個方向承載了從nodei到nodej的路由路徑,另一方向承載了從nodej到nodei的路由路徑。所以,由nodei和nodej選取的任意性可知,FT(m,2)中任意鏈路的上行和下行方向所承載的路由路徑數(shù)目必相等。(2)根據(jù)OSRM2算法定義可知,為nodei選擇上行鏈路時只考慮了nodei和nodej在FT(m,2)中的位置信息,而與它們之間的編號的相對大小無任何關(guān)系。根據(jù)OSRM2路由算法是負(fù)載均衡的可知,BT-OSRM2路由算法在為任意nodei選擇到nodej的上行鏈路也是均勻的。所以,綜合(1)和(2)的分析可知,BT-OSRM2路由算法對于均勻流量模式是負(fù)載均衡的。同理,可以證明BT-OSRM3路由算法對于均勻流量模式是負(fù)載均衡的。故定理3得證,證畢。5.4生成n,n2-采用bt-osr2路由,a在特征交換器,有多個d確定性能比率反映了路由算法對不同流量模式的適應(yīng)能力,有關(guān)性能比率、確定性能比率、最優(yōu)化路由算法的定義詳見文獻(xiàn)。為方便起見,本文沿用文獻(xiàn)對確定性能比率的標(biāo)記方法,即路由算法R的確定性能比率為PRRF(R)。定理4如果為整數(shù),則;如果m/2為整數(shù),則PRRF(BT-OSRM3)=m/2。證明首先證明PRRF(BT-OSRM2)的相關(guān)結(jié)論。為此,需要對BT-OSRM2和OSRM2兩種路由算法進(jìn)行對比。令,則OSRM2路由算法將每個級數(shù)為1的交換器所連接的m/2個處理節(jié)點(diǎn)分為Z組(group)。具體而言,假設(shè)0≤i≤m-1且0≤j≤Z-1,則switch(i,1)的groupj包括的節(jié)點(diǎn)構(gòu)成的集合為{node(i,j*Z),node(i,j*Z+1),…,node(i,j*Z+Z-1)}。假設(shè)nodes和noded為FT(m,2)中的任意兩個處理節(jié)點(diǎn),可分兩種情況討論。(1)如果或者nodes=noded,則path{BT-OSRM2|nodes→noded}=path{OSRM2|nodes→noded},所以該情況下由OSRM2修改為BT-OSRM2路由方式并不影響其確定性能比率的計算。(2)如果,則path{BT-OSRM2|nodes→noded}=BackTrack(path{OSRM2|noded→nodes})。(2.1)如果從nodes到noded的路由路徑只經(jīng)過switch(i,1)一級交換,即nodes和noded連接同一交換器,則BackTrack(path{OSRM2|noded→nodes})=path{OSRM2|nodes→noded},該情況下由OSRM2修改為BT-OSRM2路由方式也并不影響其確定性能比率的計算。(2.2)如果從nodes到noded的路由路徑需要經(jīng)過switch(i,1)和switch(k,0)兩級交換(0≤k≤m/2-1),即nodes和noded連接在不同交換器,則假設(shè)nodes=node(i1,j1*Z+x)且noded=node(i2,j2*Z+y),其中0≤i1、i2≤m-1,0≤j1、j2≤Z-1,0≤x、y≤Z-1。(2.2.1)如果nodes和noded屬于相同分組,即j1=j2,則path{OSRM2|nodes→noded}和path{OSRM2|noded→nodes}經(jīng)過同一頂層交換器switch(j1,0),則path{BT-OSRM2|nodes→noded}=BackTrack(path{OSRM2|noded→nodes})=path{OSRM2|nodes→noded},該情況下由OSRM2修改為BT-OSRM2路由方式也并不影響其確定性能比率的計算。推論1BT-OSRM2和BT-OSRM3路由算法是最優(yōu)(Optimal)的。證明假設(shè)R2和R3分別是FT(m,2)和FT(m,3)拓?fù)浣Y(jié)構(gòu)的路由算法,且PRRF(R2)和PRRF(R3)分別是R2和R3的確定性能比率。根據(jù)文獻(xiàn)引理12(Lemma12)可知,路由算法R2和R3的確定性能比率取值范圍分別為和PRRF(R3)≥m/2。而定理4已經(jīng)證明了BT-OSRM2和BT-OSRM3路由算法的確定性能比率分別為和m/2,所以BT-OSRM2和BT-OSRM3路由算法是最優(yōu)的。故推論1得證,證畢。6研究工作展望BT-OSRM路由算法是對OSRM路由算法的改進(jìn)算法,該新型路由算法不僅繼承了OSRM算法性能最優(yōu)和負(fù)載均衡等優(yōu)點(diǎn),而且通過簡單的定義和利用處理節(jié)點(diǎn)間的大小關(guān)系,使得任意處理節(jié)點(diǎn)對間的往返路徑所包含的網(wǎng)絡(luò)鏈路相同,從而提高了網(wǎng)絡(luò)故障鏈路的易診斷性。BT-OSRM路由算法的實(shí)現(xiàn)也較為簡單———如果胖樹網(wǎng)絡(luò)采用源路由,則在靜態(tài)生成系統(tǒng)的路由表時直接實(shí)現(xiàn)即可;如果胖樹網(wǎng)絡(luò)實(shí)現(xiàn)采用分布式查表路由,則需要增加節(jié)點(diǎn)編號比較的機(jī)制并修改查表流程?；诒疚难芯炕A(chǔ),未來研究工作可在如下三個方面展開:(1)深入研究原路返回路由算法對網(wǎng)絡(luò)鏈路故障定位的影響;(2)進(jìn)一步為胖樹網(wǎng)絡(luò)提出更通用的原路返回路由算法;(3)考慮其它拓?fù)浣Y(jié)構(gòu)中的原路返回路由問題及其可解性。(1)基本構(gòu)成:FT(m,n)胖樹由(2n-1)×(m/2)n-1個m端口的交換器和m×(m/2)n-1個處理節(jié)點(diǎn)構(gòu)成?？梢?如果path{R|nodes→noded}=link0→link1→…→linkn-1,則BackTrack(path{R|nodes→noded})=linkn-1→linkn-2→…→link0。5.3節(jié)點(diǎn)面圖2所示為FT(8,2)胖樹結(jié)構(gòu),OSRM路由算法將其32個處理節(jié)點(diǎn)分為兩組,即group0和group1。頂層的四個交換器分別負(fù)責(zé)的路由路徑(表示從groupi中的處理節(jié)點(diǎn)到groupj中的處理節(jié)點(diǎn))。定理4證明過程中的各種情況可舉例如下:(1)path{BT-OSRM2|node(6,0)→node(1,0)}=path{OSRM2|node(6,0)→node(1,0)};(2.1)path{BT-OSRM2|node(1,0)→node(1,2)}=path{OSRM2|node(1,0)→node(1,2)};(2.2.1)path{BT-OSRM2|node(1,0)→node(6,1)}=path{OSRM2|node(1,0)→node(6,1)};(2.2.2)path{BT-OSRM2|node(1,0)→node(