一種覆蓋網(wǎng)絡(luò)環(huán)境下的多播路由樹前向式重構(gòu)恢復(fù)方法

(19)中民國家知識(shí)

(10)公告號(hào) (21)(22)(73)專利權(quán)人大地址430072省市武昌區(qū)珞珈(72)發(fā)明人萍曹雪松(74)專利機(jī)構(gòu)知識(shí)事務(wù)

員人H04L12/56(2006.01)H04L12/24(2006.01)H04L12/18(2006.01)H04L1/16(2006.01)權(quán)利要求書2權(quán)利要求書2說明書6附圖3B備份節(jié)點(diǎn)之間的備份有效性的檢測方法，限BB權(quán)利要求1/2驟：PPLR③節(jié)點(diǎn)N向RT中所有可用度＞1的節(jié)點(diǎn)發(fā)送消息這些節(jié)點(diǎn)接到消息后將返回ACK消息N根據(jù)ACK中返回出節(jié)點(diǎn)N到每個(gè)可用度＞1的節(jié)點(diǎn)的RTT值；④N選擇其點(diǎn)P為其多播樹上的父節(jié)點(diǎn)其中RTT(NP與根節(jié)點(diǎn)到節(jié)點(diǎn)P的分發(fā)T(P)ACK⑥節(jié)點(diǎn)N向PPL表中所有可用備選父節(jié)點(diǎn)發(fā)送消息，這些節(jié)點(diǎn)接到消息后將返回ACKN根據(jù)ACK中返回的時(shí)戳信算出節(jié)點(diǎn)N到每個(gè)可用備選父節(jié)點(diǎn)的RTT值；⑧設(shè)N選擇了節(jié)點(diǎn)V為備份父節(jié)點(diǎn)，則在PPL表點(diǎn)V的備份可用度BD(V)③節(jié)點(diǎn)N向PPL表中所有可用備選父節(jié)點(diǎn)發(fā)送消息，這些節(jié)點(diǎn)接到消息后將返回ACKN根據(jù)ACK中返回的時(shí)戳信算出節(jié)點(diǎn)N到每個(gè)可用備選父節(jié)點(diǎn)的RTT值；⑥V接到check消息后向其父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息N接到check消息則檢測未通V與N存在依V不能N的備份父N沒有接到check消息，則沿組播路徑繼續(xù)向上級(jí)父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息，并檢測N是否接受到check消⑦V接到check消息后還要向V的備份父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息，如N接到check消Rcheck⑨節(jié)點(diǎn)N選擇RTT值最且檢測通過的節(jié)點(diǎn)為節(jié)點(diǎn)N新的備份父節(jié)新的備份父節(jié)PPL表中的備份可用度BD1如果新的備份父節(jié)點(diǎn)的備份可用度BD0PPLB權(quán)利要求2/2一種覆蓋網(wǎng)絡(luò)環(huán)境下的多播路由樹前向式重構(gòu)恢復(fù)方 [0002]多播(Multicast，又稱為組播)技術(shù)是一種可控制的單點(diǎn)對(duì)多點(diǎn)的數(shù)據(jù)路由傳輸技 端系統(tǒng)(主機(jī))而不是路由器來實(shí)現(xiàn)通信的所有功能。與IP網(wǎng)絡(luò)相比其最大的優(yōu)勢在 [0005]端主機(jī)由于業(yè)務(wù)的需要或故障突發(fā)隨時(shí)可能退出群組，如果退出的節(jié)點(diǎn)是參與分[0006]覆蓋多播樹重構(gòu)算法主要研究多播樹在發(fā)生服務(wù)通信中斷的情況下，如何通過路構(gòu)(參見文獻(xiàn)1)是在樹異常發(fā)生之前就進(jìn)行預(yù)并提前制定備份路由策在發(fā)生之[0007]2)快速恢復(fù)樹路由。但是目前的備份節(jié)點(diǎn)選擇模型(參見文獻(xiàn)3)未考慮備份父節(jié)點(diǎn)EE1KusumotoTKunichikaYKattoJOkuboS“Tree-layermulticastusingproactiveroutemaintenanceanditsimplementation”，InProceedingsoftheACMP2PMMSSingapore2005pp.49-58. 文獻(xiàn)2ZongminFei，andMengkunYangProactiveTreeRecoveryVol.15，No.1，F(xiàn)ebruary2007173186.3JinJeonSeung-SonJi-NamOverlayrecoveryschemeusingaproactiveapproach”，ComputerCommunications，Vol.31，2008pp.3163-3168.[0015]②根節(jié)點(diǎn)RNRTPPLRT[0016]③節(jié)點(diǎn)N向RT中所有可用度＞1的節(jié)點(diǎn)發(fā)送消息這些節(jié)點(diǎn)接到消息后將返回ACKN根據(jù)ACK中返回的時(shí)戳信計(jì)算出節(jié)點(diǎn)N到每個(gè)可用度＞1的節(jié)點(diǎn)的RTT值；總和為所有返回ACK消息節(jié)點(diǎn)中的最小值；[0018]RTD(P)＝D(P)-[0019]⑥節(jié)點(diǎn)N向PPL表中所有可用備選父節(jié)點(diǎn)發(fā)送消息，這些節(jié)點(diǎn)接到消息后將返A(chǔ)CK消息NACK中返回的時(shí)戳信計(jì)算N到每個(gè)可用備選父節(jié)點(diǎn)的RTT值；[0020]RTTPRTT[0021]NVPPLBD(V)＝BD(V)-1[0025]③節(jié)點(diǎn)N向PPL表中所有可用備選父節(jié)點(diǎn)發(fā)送消息，這些節(jié)點(diǎn)接到消息后將返A(chǔ)CK消息NACK中返回的時(shí)戳信計(jì)算N到每個(gè)可用備選父節(jié)點(diǎn)的RTT值； ⑥V接到check消息后向其父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息如果N接到check消息則檢測未通過表明V與N存在依賴關(guān)系V不能成為N的備份父節(jié)點(diǎn)回到步驟④如果N沒有接到check消息則沿組播路徑繼續(xù)向上級(jí)父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息并檢測N是否接受到check消息如果收到則檢測不通過回到步驟④否則直到根節(jié)點(diǎn)R收到check消息； ⑦V接到check消息后還要向V的備份父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息如果N接到check消息則表明V與N存在依賴關(guān)系，V不能成為N的備份父節(jié)點(diǎn)回到步驟④；續(xù)向上級(jí)父節(jié)點(diǎn)轉(zhuǎn)發(fā)checkN是否接受到check果收到則檢測不通過， 3)異常情況下多播路由樹快速恢復(fù)過程步驟該步驟進(jìn)一步包括以下子步驟： 作； ②子節(jié)點(diǎn)ci向其備份父節(jié)點(diǎn)vi發(fā)送掛載請(qǐng)求connect消息； ③如果vi同意其掛載請(qǐng)求則回復(fù)ok消息否則發(fā)送refuse消息； ④收到ok消息的子節(jié)點(diǎn)vi則開始建立多播會(huì)話結(jié)束重建過程 網(wǎng)絡(luò)服務(wù)應(yīng)用中的容災(zāi)恢復(fù)問題； [0045]本發(fā)明提供的覆蓋網(wǎng)絡(luò)環(huán)境下的多播路由樹前向式重構(gòu)恢復(fù)方法，將有助于多媒[0047]本發(fā)明提供的前向式重構(gòu)恢復(fù)方法能夠預(yù)先為每個(gè)下游接入點(diǎn)提供預(yù)留備份接入[0048][0049]1 Node Node [0058]2)RNRT(RoutingTablePPL(PotentialParentList備份父節(jié)點(diǎn)RT記錄了任意樹節(jié)點(diǎn)I，I∈T的狀態(tài)信息(地址A(I可用度D(IR到該節(jié)點(diǎn)的分發(fā)延時(shí)T(I)PP表記錄了所有可用備選父節(jié)點(diǎn)KK∈T的信息(地A(KBD(K))；[0059]3)節(jié)點(diǎn)N向RT中所有可用度＞1的節(jié)點(diǎn)發(fā)送消息這些節(jié)點(diǎn)接到消息后將返回ACKN根據(jù)ACK中返回的時(shí)戳信計(jì)算出節(jié)點(diǎn)N到每個(gè)可用度＞1的節(jié)點(diǎn)的RTT(RoundTripTime)總和為所有返回ACK消息節(jié)點(diǎn)中的最小值；[0061]5)RTD(P)＝D(P)-[0062]6)節(jié)點(diǎn)N向PPL表中所有可用備選父節(jié)點(diǎn)發(fā)送消息，這些節(jié)點(diǎn)接到消息后將返A(chǔ)CK消息NACK中返回的時(shí)戳信計(jì)算N到每個(gè)可用備選父節(jié)點(diǎn)的RTT(RoundTripTime)[0063]7)RTTP果是則按照RTT[0064]8)NVPPLBD(V)＝BD(V)-1 1)設(shè)節(jié)點(diǎn)N重新計(jì)算其備份父節(jié)點(diǎn)首先向多播樹的根節(jié)點(diǎn)R發(fā)送request請(qǐng)求； 2)根節(jié)點(diǎn)R會(huì)向節(jié)點(diǎn)N返回PPL(PotentialParentList備份父節(jié)點(diǎn)列表)； 3)節(jié)點(diǎn)N向PPL表中所有可用備選父節(jié)點(diǎn)發(fā)送消息這些節(jié)點(diǎn)接到消息后將返回ACK消息節(jié)點(diǎn)N根據(jù)ACK中返回的時(shí)戳信息計(jì)算出節(jié)點(diǎn)N到每個(gè)可用備選父節(jié)點(diǎn)的RTT(RoundTripTime)值； 6)V接到check消息后向其父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息如果N接到check消息則檢接到check消息則沿組播路徑繼續(xù)向上級(jí)父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息并檢測N是否接受到check消息如果收到則檢測不通過回到步驟4否則直到根節(jié)點(diǎn)R收到check消息； 7)V接到check消息后還要向V的備份父節(jié)點(diǎn)轉(zhuǎn)發(fā)check消息如果N接到check消息則表明V與N存在依賴關(guān)系，V不能成為N的