[發(fā)明專(zhuān)利]覆蓋網(wǎng)備用路徑生成方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200910085466.5
• 申請(qǐng)日: 2009-05-26
• 公開(kāi)（公告）號(hào): CN101562568A
• 公開(kāi)（公告）日: 2009-10-21
• 發(fā)明（設(shè)計(jì)）人: 楊清峰;李彥君;張國(guó)清
• 申請(qǐng)（專(zhuān)利權(quán)）人: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所
• 主分類(lèi)號(hào): H04L12/56
• 分類(lèi)號(hào): H04L12/56;H04L29/06
• 代理公司: 北京泛華偉業(yè)知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 王 勇

1.一種覆蓋網(wǎng)備用路徑生成方法，用于在包括接入服務(wù)器節(jié)點(diǎn)、標(biāo)志服務(wù)器節(jié)點(diǎn)、轉(zhuǎn)發(fā)節(jié)點(diǎn)和用戶(hù)節(jié)點(diǎn)的覆蓋網(wǎng)上為源用戶(hù)節(jié)點(diǎn)選取合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)以構(gòu)建從源用戶(hù)節(jié)點(diǎn)到目的用戶(hù)節(jié)點(diǎn)的備用路徑，該方法包括：

步驟1)、利用所述覆蓋網(wǎng)中的標(biāo)志服務(wù)器節(jié)點(diǎn)對(duì)所述轉(zhuǎn)發(fā)節(jié)點(diǎn)做網(wǎng)絡(luò)測(cè)距，根據(jù)網(wǎng)絡(luò)測(cè)距結(jié)果計(jì)算任意兩個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)間的綜合性能相似度，由所述綜合性能相似度為具有相近性能的轉(zhuǎn)發(fā)節(jié)點(diǎn)構(gòu)建邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)；其中，在所述覆蓋網(wǎng)的一個(gè)自由域內(nèi)屬于同一邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)節(jié)點(diǎn)擁有同一個(gè)入口轉(zhuǎn)發(fā)節(jié)點(diǎn)；

步驟2)、所述接入服務(wù)器節(jié)點(diǎn)根據(jù)所述源用戶(hù)節(jié)點(diǎn)的請(qǐng)求轉(zhuǎn)發(fā)節(jié)點(diǎn)消息在所述源用戶(hù)節(jié)點(diǎn)所在的自由域中選擇邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)，然后通過(guò)所述邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)的入口轉(zhuǎn)發(fā)節(jié)點(diǎn)找到與所述入口轉(zhuǎn)發(fā)節(jié)點(diǎn)在同一自由域且同一邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)的轉(zhuǎn)發(fā)節(jié)點(diǎn)作為服務(wù)轉(zhuǎn)發(fā)節(jié)點(diǎn)；所述服務(wù)轉(zhuǎn)發(fā)節(jié)點(diǎn)在所在的邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)上運(yùn)行BFBB算法，根據(jù)該算法的運(yùn)行結(jié)果選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)作為一次候選轉(zhuǎn)發(fā)節(jié)點(diǎn)；其中，

所述的BFBB算法在計(jì)算網(wǎng)絡(luò)拓?fù)鋱D中每個(gè)節(jié)點(diǎn)的度和核度后，在當(dāng)前節(jié)點(diǎn)上通過(guò)廣度優(yōu)先算法在所述網(wǎng)絡(luò)拓?fù)鋱D上選取核度值大于當(dāng)前節(jié)點(diǎn)的核度值，且度與核度的商大于當(dāng)前節(jié)點(diǎn)的度與核度的商的節(jié)點(diǎn)；若所能找到的節(jié)點(diǎn)的數(shù)目無(wú)法滿(mǎn)足要求，則將當(dāng)前節(jié)點(diǎn)的度與核度的商的值遞減后，重新在當(dāng)前節(jié)點(diǎn)上利用廣度優(yōu)先算法選取核度值大于當(dāng)前節(jié)點(diǎn)的核度值，且度與核度的商大于當(dāng)前節(jié)點(diǎn)的度與核度的商的節(jié)點(diǎn)，直到滿(mǎn)足對(duì)所選取節(jié)點(diǎn)的數(shù)目要求；

步驟3)、對(duì)候選轉(zhuǎn)發(fā)節(jié)點(diǎn)所能形成的路徑做性能檢測(cè)，保留通過(guò)性能檢測(cè)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，在所述用戶(hù)節(jié)點(diǎn)間進(jìn)行業(yè)務(wù)通信時(shí)，根據(jù)業(yè)務(wù)從所保留的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)中選擇合適的轉(zhuǎn)發(fā)節(jié)點(diǎn)以構(gòu)建備用路徑。

2.根據(jù)權(quán)利要求1所述的覆蓋網(wǎng)備用路徑生成方法，其特征在于，在所述步驟2)中所得到的一次候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)目小于用戶(hù)的需求時(shí)，在所述的步驟2)和所述的步驟3)之間還包括選取二次候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的步驟，該步驟包括：

在所述覆蓋網(wǎng)的網(wǎng)絡(luò)拓?fù)鋱D上運(yùn)行BFBB算法；

根據(jù)所述BFBB算法的計(jì)算結(jié)果，從所述覆蓋網(wǎng)中選取一個(gè)自由域，在該自由域內(nèi)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)作為二次候選轉(zhuǎn)發(fā)節(jié)點(diǎn)；所選取的轉(zhuǎn)發(fā)節(jié)點(diǎn)盡量不屬于所述源用戶(hù)節(jié)點(diǎn)所在自由域內(nèi)的邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)。

3.根據(jù)權(quán)利要求1或2所述的覆蓋網(wǎng)備用路徑生成方法，其特征在于，所述的步驟1)包括：

步驟1-1)、所述覆蓋網(wǎng)中的所有轉(zhuǎn)發(fā)節(jié)點(diǎn)對(duì)所述覆蓋網(wǎng)中的所有標(biāo)志服務(wù)器節(jié)點(diǎn)做網(wǎng)絡(luò)測(cè)距，得到關(guān)于延遲、丟包率和瓶頸帶寬的指標(biāo)；

步驟1-2)、根據(jù)所述指標(biāo)計(jì)算任意兩個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)間的綜合性能相似度；

步驟1-3)、對(duì)所有的綜合性能相似度結(jié)果做排序，然后為所述排序結(jié)果分段，將具有相近綜合性能的轉(zhuǎn)發(fā)節(jié)點(diǎn)分配到同一個(gè)邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)。

4.根據(jù)權(quán)利要求3所述的覆蓋網(wǎng)備用路徑生成方法，其特征在于，所述的步驟1)還包括：

步驟1-4)、由所述邏輯轉(zhuǎn)發(fā)網(wǎng)絡(luò)的入口轉(zhuǎn)發(fā)節(jié)點(diǎn)向鄰居域的入口轉(zhuǎn)發(fā)節(jié)點(diǎn)做鏈路性能探測(cè)；所述鏈路性能包括路徑的延遲、丟包率和瓶頸帶寬；

步驟1-5)、所述鏈路性能探測(cè)的結(jié)果保存到入口轉(zhuǎn)發(fā)節(jié)點(diǎn)的鏈路狀態(tài)表中，所述鏈路狀態(tài)表的信息定時(shí)向鄰居域的入口轉(zhuǎn)發(fā)節(jié)點(diǎn)更新。