[發明專利]一種基于分組測試的擁塞鏈路定位方法

有效

• 申請號: 201611204022.5
• 申請日: 2016-12-23
• 公開（公告）號: CN106713035B
• 公開（公告）日: 2019-12-27
• 發明（設計）人: 齊小剛;王曉琳;劉立芳;胡紹林;楊國平;馮海林;牛紅曼
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/26;H04L12/703;H04L12/721;H04L12/801
• 代理公司: 61227 西安長和專利代理有限公司
• 代理人: 黃偉洪

1.一種基于分組測試的擁塞鏈路定位方法，其特征在于，所述基于分組測試的擁塞鏈路定位方法采用d分離矩陣模型作為二進制檢驗矩陣鑒別擁塞鏈路，定位網絡中的擁塞鏈路；通過隨機游走方法來構造矩陣的每一行去定位擁塞鏈路；一個測試為一個隨機游走，即探測信號從發送方出發，隨機選擇路徑進行隨機游走，直到到達接收方后停止；任務是識別擁塞鏈路；在給定的圖中，使用布爾向量編碼路由矩陣，編碼的過程是：布爾向量相應的位置表示圖中鏈路集合，每條探測路徑經過的鏈路，他們相應位置記為1，否則記為0；

所述d分離矩陣模型的構造方法包括：n個鏈路當中至多d條是擁塞的，即經由鏈路的數據包丟失；每一列相當于G中的每條鏈路，每一行相當于G上的一些鏈路形成的一條路徑；提出隨機游走的算法去設計一個保證沒有誤差地鑒別所有擁塞鏈路的行數m最小的m×n的二進制檢驗矩陣；m為探測路徑數；網絡中的總鏈路數為n。

2.如權利要求1所述的基于分組測試的擁塞鏈路定位方法，其特征在于，所述隨機游走方法包括：

輸入：無向圖G(V,E)，一個發送方u，一個接收方v，擁塞鏈路數d，初始擁塞鏈路集合為Ψ＝E；節點集V表示節點；邊集合E表示連接這些節點的鏈路；

輸出：擁塞鏈路集合Ψ，M的行數m；m×n的二進制測試矩陣M；

初始化每條鏈路上的計數器ρ(e)＝0；

獨立地構造M的每一行的過程如下：

讓u∈V為G中的任意一點，從u開始直到達到節點v，執行一個任意的隨機游走；

每次隨機游走結束后，對其所經過的鏈路上的計數器ρ(e)加1；

下一次隨機游走從u開始，選擇計數器數值小的鏈路進行游走，直到達到節點v；

讓M的每行為由每條游走訪問的鏈路的集合；

end

在每一條游走上發送數據包，如果某條游走上的時延低于閾值t，從Ψ中刪除這條游走經過的鏈路。

3.一種利用權利要求1～2任意一項所述基于分組測試的擁塞鏈路定位方法的網絡診斷系統。