[發(fā)明專利]IP網(wǎng)絡(luò)中基于K-Shell算法的主動(dòng)式故障快速重路由方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201810564787.2
• 申請(qǐng)日: 2018-06-04
• 公開（公告）號(hào): CN108768847A
• 公開（公告）日: 2018-11-06
• 發(fā)明（設(shè)計(jì)）人: 李培巒;張治學(xué);李沛諭;陳曦;范志輝;王輝;劉新源
• 申請(qǐng)（專利權(quán)）人: 河南科技大學(xué)
• 主分類號(hào): H04L12/707
• 分類號(hào): H04L12/707;H04L12/703;H04L12/721;H04L12/751
• 代理公司: 洛陽公信知識(shí)產(chǎn)權(quán)事務(wù)所(普通合伙) 41120
• 代理人: 宋晨煒

1.IP網(wǎng)絡(luò)中基于K-Shell算法的主動(dòng)式故障快速重路由方法，所述IP網(wǎng)絡(luò)中包括若干個(gè)互相關(guān)聯(lián)的節(jié)點(diǎn)，其特征在于：所述方法包括如下步驟：

S1、利用K-Shell算法對(duì)所有節(jié)點(diǎn)進(jìn)行分解，得到多層核心節(jié)點(diǎn)，每層核心節(jié)點(diǎn)的數(shù)量為若干個(gè)；

S2、根據(jù)節(jié)點(diǎn)間的關(guān)聯(lián)性計(jì)算每個(gè)核心節(jié)點(diǎn)所有的鄰居節(jié)點(diǎn)對(duì)其的貢獻(xiàn)度；

S3、根據(jù)所有節(jié)點(diǎn)的貢獻(xiàn)度計(jì)算每個(gè)核心節(jié)點(diǎn)的重要度；

S4、按照重要度從大到小的順序?qū)λ泻诵墓?jié)點(diǎn)進(jìn)行排列，得到核心節(jié)點(diǎn)序列；

S5、從核心節(jié)點(diǎn)序列中選取若干個(gè)作為關(guān)鍵節(jié)點(diǎn)；

S6、創(chuàng)建備份拓?fù)?，備份拓?fù)渲忻總€(gè)關(guān)鍵節(jié)點(diǎn)都鄰接有多個(gè)受保護(hù)鏈路；

S7、使用MRC算法對(duì)除關(guān)鍵節(jié)點(diǎn)之外的普通節(jié)點(diǎn)進(jìn)行鏈路保護(hù)。

2.如權(quán)利要求1所述的IP網(wǎng)絡(luò)中基于K-Shell算法的主動(dòng)式故障快速重路由方法，其特征在于：還包括如下步驟：

S8、判斷備份拓?fù)涫欠駶M足MRC算法的備份拓?fù)渖梢?guī)則，如果滿足則方法結(jié)束，如果不滿足則返回S5并增加關(guān)鍵節(jié)點(diǎn)數(shù)量。

3.如權(quán)利要求1所述的IP網(wǎng)絡(luò)中基于K-Shell算法的主動(dòng)式故障快速重路由方法，其特征在于：S2中，貢獻(xiàn)度的計(jì)算方法為：

其中n_ij表示節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的貢獻(xiàn)度，l_i表示節(jié)點(diǎn)i在K-Shell算法中的度，l_j表示節(jié)點(diǎn)j在K-Shell算法中的度。

4.如權(quán)利要求1所述的IP網(wǎng)絡(luò)中基于K-Shell算法的主動(dòng)式故障快速重路由方法，其特征在于：S3中，計(jì)算核心節(jié)點(diǎn)重要度的方法包括如下步驟：

S31、構(gòu)建節(jié)點(diǎn)重要度貢獻(xiàn)矩陣

其中，δij是IP網(wǎng)絡(luò)中相鄰接的節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的鄰接系數(shù)，當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連邊時(shí)δij＝1，當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間不存在連邊時(shí)δij＝0；ks(n)表示K-Shell算法中的殼值；δijnijks(i)用來表示節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的重要度貢獻(xiàn)值；

S32、計(jì)算核心節(jié)點(diǎn)的貢獻(xiàn)度

5.如權(quán)利要求1所述的IP網(wǎng)絡(luò)中基于K-Shell算法的主動(dòng)式故障快速重路由方法，其特征在于：將與關(guān)鍵節(jié)點(diǎn)相連的受保護(hù)鏈路的數(shù)量記為m，關(guān)鍵節(jié)點(diǎn)的最大出入度記為D，IP網(wǎng)絡(luò)中的全部節(jié)點(diǎn)數(shù)記為N，則滿足m≤[ceil(D/N)+1]。