[發(fā)明專利]基于鏈路擁塞強(qiáng)度分布的網(wǎng)絡(luò)擁塞鏈路診斷方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201910362446.1
• 申請(qǐng)日: 2019-04-30
• 公開（公告）號(hào): CN110149277B
• 公開（公告）日: 2020-11-27
• 發(fā)明（設(shè)計(jì)）人: 潘勝利;曾德澤;李沖
• 申請(qǐng)（專利權(quán)）人: 中國(guó)地質(zhì)大學(xué)（武漢）
• 主分類號(hào): H04L12/801
• 分類號(hào): H04L12/801;H04L12/24
• 代理公司: 武漢知產(chǎn)時(shí)代知識(shí)產(chǎn)權(quán)代理有限公司 42238
• 代理人: 孫麗麗

1.基于鏈路擁塞強(qiáng)度分布的網(wǎng)絡(luò)擁塞鏈路診斷方法，其特征在于，包括：

S1、對(duì)待測(cè)IP網(wǎng)絡(luò)中端到端路徑進(jìn)行t時(shí)刻快照，獲得t時(shí)刻待測(cè)IP網(wǎng)絡(luò)中各端到端路徑性能及拓?fù)浣Y(jié)構(gòu)的探測(cè)結(jié)果，使用快照獲得待測(cè)IP網(wǎng)絡(luò)鏈路的初始概率，初始概率包括鏈路的初始擁塞概率以及鏈路的初始擁塞強(qiáng)度概率；

S2、根據(jù)t時(shí)刻快照所得到的初始概率使用EM算法模型計(jì)算得到待測(cè)IP網(wǎng)絡(luò)的先驗(yàn)概率，先驗(yàn)概率包括先驗(yàn)擁塞概率和鏈路的先驗(yàn)擁塞強(qiáng)度概率；

所述步驟S2計(jì)算先驗(yàn)概率包括：

a、根據(jù)所述探測(cè)結(jié)果，獲得某一時(shí)刻t對(duì)應(yīng)的鏈路的擁塞概率向量p和鏈路的擁塞強(qiáng)度概率分布D^t；

b、根據(jù)t時(shí)刻得到的初始概率以及IP網(wǎng)絡(luò)路徑狀態(tài)Z，計(jì)算對(duì)數(shù)似然LL(D|Z，X)關(guān)于X的期望，得到最可能發(fā)生的鏈路狀態(tài)X；

c、根據(jù)鏈路狀態(tài)X，重新計(jì)算每條鏈路的擁塞強(qiáng)度概率分布，得到新的D^t+1；

d、當(dāng)?shù)揭欢ù螖?shù)，或者算法收斂到一定精度，結(jié)束算法，得到所述待測(cè)IP網(wǎng)絡(luò)中的先驗(yàn)鏈路擁塞強(qiáng)度概率分布；否則，回到步驟b；

S3、建立待測(cè)IP網(wǎng)絡(luò)中各鏈路的先驗(yàn)擁塞概率求解的線性方程組；

建立所述線性方程組包括：

A、在所述待測(cè)IP網(wǎng)絡(luò)中，將各端到端與其路徑的各鏈路之間的關(guān)系使用布爾代數(shù)模型表示為：

n_c為各端到端路徑經(jīng)過的鏈路總和，Z_i為第i條路徑的狀態(tài)變量，x_j為第j條鏈路的狀態(tài)變量；當(dāng)Z_i≥1時(shí)，表示第i條路徑為擁塞狀態(tài)，當(dāng)Z_i＝0時(shí)，表示第i條路徑為正常狀態(tài)；當(dāng)x_j＝1時(shí)，表示第j條鏈路為擁塞狀態(tài)，當(dāng)x_j＝0時(shí)，表示第j條鏈路為正常狀態(tài)；D_ij為路徑和鏈路的關(guān)系變量，當(dāng)D_ij＝1時(shí)，表示第i條路徑經(jīng)過第j條鏈路，當(dāng)D_ij＝0時(shí)，表示第i條路徑不經(jīng)過第j條鏈路；

B、在所述待測(cè)IP網(wǎng)絡(luò)中，將各端到端與其路徑的各鏈路之間的擁塞強(qiáng)度的關(guān)系使用線性代數(shù)模型表示為：

n_c為各端到端路徑經(jīng)過的鏈路總和，M_i為第i條路徑的狀態(tài)變量，x_j為第j條鏈路的狀態(tài)變量；當(dāng)M_i≥1時(shí)，表示第i條路徑為擁塞狀態(tài)，當(dāng)M_i＝0時(shí)，表示第i條路徑為正常狀態(tài)；當(dāng)x_j≥1時(shí)，表示第j條鏈路為擁塞狀態(tài)，當(dāng)x_j＝0時(shí)，表示第j條鏈路為正常狀態(tài)；D_ij為路徑和鏈路的關(guān)系變量，當(dāng)D_ij＝1時(shí)，表示第i條路徑經(jīng)過第j條鏈路，當(dāng)D_ij＝0時(shí)，表示第i條路徑不經(jīng)過第j條鏈路；

C、對(duì)所述A步驟中的布爾代數(shù)模型，找到向量x＝[x₁ x₂…x_n]，使得如下條件概率公式得到最大化：

其中z＝[z1 z2 … zm]表示快照得到的待測(cè)IP網(wǎng)絡(luò)的狀態(tài)，n表示待測(cè)IP網(wǎng)絡(luò)中鏈路的個(gè)數(shù)，m表示待測(cè)IP網(wǎng)絡(luò)中路徑的個(gè)數(shù)，

ρ_G為測(cè)量標(biāo)記為正常鏈路的集合，ρ_C為測(cè)量標(biāo)記為擁塞鏈路的集合，P_i表示路徑i；最大化概率公式化簡(jiǎn)為：

其中，ε_R表示去除所有經(jīng)過正常路徑的鏈路以及確定為正常鏈路之后所得到的路由矩陣，表示判斷的擁塞鏈路集合，p_k表示鏈路k的擁塞概率；

S4、根據(jù)步驟S2得到待測(cè)IP網(wǎng)絡(luò)的先驗(yàn)概率，結(jié)合步驟S3得到的線性方程組，計(jì)算推斷待測(cè)IP網(wǎng)絡(luò)中最有可能發(fā)生擁塞的鏈路集合；

所述步驟S4具體包括：

在當(dāng)前推斷時(shí)刻擁塞路徑鏈路集合中查找權(quán)值最高的鏈路的判斷公式如下：

其中，D_k表示鏈路k經(jīng)過的路徑的集合，|D_k|即為鏈路k經(jīng)過的路徑的個(gè)數(shù)；

根據(jù)所述判斷公式，對(duì)未判斷的鏈路集合∈_A進(jìn)行查找，對(duì)滿足所述判斷公式的鏈路e_k，將鏈路e_k標(biāo)記到推斷出的擁塞鏈路集合χ中；根據(jù)擁塞強(qiáng)度概率，將鏈路e_k的擁塞強(qiáng)度標(biāo)記為擁塞強(qiáng)度概率最大所對(duì)應(yīng)的擁塞強(qiáng)度Y_k；

根據(jù)步驟S3中得到的鏈路和路徑的擁塞強(qiáng)度的線性關(guān)系，對(duì)鏈路e_k所經(jīng)過的所有路徑的擁塞強(qiáng)度進(jìn)行更新，更新后的擁塞強(qiáng)度為M_k-Y_k，此后，將鏈路e_k從未判斷的鏈路集合∈_A中剔除；

重復(fù)所述查找過程，直到未判斷的鏈路集合∈_A為空，輸出得到的擁塞鏈路集合χ。

2.基于鏈路擁塞強(qiáng)度分布的網(wǎng)絡(luò)擁塞鏈路診斷系統(tǒng)，其特征在于，包括：處理器及存儲(chǔ)設(shè)備；所述處理器加載并執(zhí)行所述存儲(chǔ)設(shè)備中的指令及數(shù)據(jù)用于實(shí)現(xiàn)權(quán)利要求1所述的基于鏈路擁塞強(qiáng)度分布的網(wǎng)絡(luò)擁塞鏈路診斷方法。