[發明專利]一種HPC間接網絡環境下的鏈路故障檢測方法

有效

• 申請號: 201810256843.6
• 申請日: 2018-03-27
• 公開（公告）號: CN108650110B
• 公開（公告）日: 2021-01-08
• 發明（設計）人: 肖利民;劉成春;楊章;田泓蘊;閆柏成;王志昊
• 申請（專利權）人: 北京航空航天大學;北京應用物理與計算數學研究所
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/26
• 代理公司: 北京海虹嘉誠知識產權代理有限公司 11129
• 代理人: 吳小燦

1.一種HPC間接網絡環境下的鏈路故障檢測方法，其特征在于，包括以下步驟：

(a)查詢HPC互連網絡路由信息，獲得結點間通信路徑的鏈路組成；HPC間接網絡中包含n個結點，結點集合為N，以及m條鏈路，鏈路集合為M，那么n個結點之間共有n(n-1)/2條通信路徑，通過查詢網絡所提供的路由查詢接口，獲得組成任意一條通信路徑L_i的鏈路集合M_i，且有

(b)結合各通信路徑的鏈路組成，確定需要進行延遲測量的關鍵通信路徑集合；將各通信路徑的鏈路組成轉化為矩陣形式，然后對矩陣進行矩陣操作，去掉冗余通信路徑，確定最終需要進行延遲測量的關鍵通信路徑集合，根據這些關鍵路徑的延遲信息求解出網絡中所有鏈路的延遲信息；

(c)并行測量關鍵路徑的延遲信息，并據此信息求解出全網所有鏈路的延遲信息；

(d)根據鏈路延遲信息判斷鏈路是否發生故障；求解網絡中鏈路延遲的期望值，延遲與該值存在較大偏差的鏈路即為故障鏈路；

所述步驟(c)的具體過程為，

(c-1)結合圖論算法生成并行測量方案；以關鍵通信路徑集合中每條待測通信路徑的鏈路組成為結點，包含有相同鏈路的路徑所對應的結點間記為相連，否則記為不相連構造無向圖；基于圖染色算法將無向圖各結點進行染色，所有染相同顏色的結點之間可以并行進行延遲測量；

(c-2)測量各通信路徑的延遲信息；在測量數據經某一條通信路徑上傳輸的延遲信息時，采取多次測量取平均值的方式：首先，在發送結點之上發送延遲測量數據，記錄時間t_j,1；數據到達接收結點之后被返回，重新到達發送結點上的時間為t_j,2，則時間間隔t_j＝(t_j,2-t_j,1)/2即為此次測量的通路延遲信息；最后，重復上述過程x次取平均值

(c-3)根據各通信路徑的延遲信息，求解各鏈路延遲信息；構建關于網絡中各鏈路延遲信息的線性方程組，求解方程組得到HPC間接網絡中所有鏈路的延遲信息。

2.根據權利要求1所述的HPC間接網絡環境下的鏈路故障檢測方法，其特征在于，所述步驟(b)的具體過程為，

(b-1)根據所有結點之間通信路徑的鏈路組成確定鏈路延遲方程組的系數矩陣；一條通信路徑的延遲信息則可以表示為如下形式：

O(L_i)＝a_i,1·o(l₁)+a_i,2·o(l₂)+…+a_i,j·o(l_j)+…+a_i,m·o(l_m)

對于其中的a_i,j·o(l_j)，a_i,j取值為0或1，表示l_j是否包含于通信路徑L_i中，因此全網所有通信路徑的鏈路延遲方程組為：

方程組的系數矩陣為：

(b-2)利用高斯消元構建新的系數矩陣，以原系數矩陣的每一行作為行向量，則可得到行向量集合S＝{α₁,α₂,…,α_i,…,α_n(n-1)/2}，利用高斯消元求得該向量集合的極大無關組則新的系數矩陣為：

(b-3)根據新系數矩陣確定需要進行延遲測量的所有通信路徑；對于系數矩陣中的任意一行中的元素它的取值為1或0，分別表示的是通信路徑中是否包含鏈路l_j；因此根據中各元素的取值，便能確定具體對應于哪一條通信路徑；系數矩陣各行所對應通信路徑即為需要進行延遲測量的關鍵路徑。