[發明專利]一種基于動態路徑的負載遷移方法

有效

• 申請號: 201910364170.0
• 申請日: 2019-04-30
• 公開（公告）號: CN110138670B
• 公開（公告）日: 2022-06-07
• 發明（設計）人: 楊武
• 申請（專利權）人: 哈爾濱英賽克信息技術有限公司
• 主分類號: H04L47/125
• 分類號: H04L47/125;H04L47/10;H04L45/12;H04L45/745;H04L67/1001;H04L67/1042
• 代理公司: 哈爾濱龍科專利代理有限公司 23206
• 代理人: 高媛

1.一種基于動態路徑的負載遷移方法，其特征在于所述方法包括如下步驟：

步驟一、將負載均衡節點以無向圖的形式輸入，使用Floyd算法對無向圖整體進行分析，得出最短距離矩陣D和最短路徑矩陣R；

步驟二、通過最短距離矩陣D和最短路徑矩陣R構建一條聯通所有點的路徑；

步驟三、基于對R求在兩個端點v_i到v_j的所有等價最短路徑，選擇兩個末端節點作為發送源，將自身負載均衡狀態進行傳遞，并在途徑節點時，在節點上更新單方向的負載均衡狀態，復數更新流途經時，按照最晚到達的內容為準；

步驟四、節點k使用最短路徑矩陣R記錄距離自身i距離的節點，其中i為max(k-first,last-k)，即獲取路徑上所有節點的狀態，并使用hello報文對節點進行保活探測，當出現節點無響應時視為物理結構變化，則對最短距離矩陣和最短路徑矩陣進行更新，并重新對路徑進行生成，返回步驟二；

步驟五、當節點j出現數據流異常時，即數據量超過閾值，將導致設備過載，于是查詢鄰接節點狀態表內容，將過多的流量遷移到鄰接節點處理；若沒有出現流量超過閾值的情況則不執行任何操作；

步驟六、重復步驟二至五，直至流量發送結束。

2.根據權利要求1所述的基于動態路徑的負載遷移方法，其特征在于所述步驟一中，無向圖G＝[V,W]，其中V＝{v₁,v₂,...,v_n}為頂點集合，W＝(w_ij)_n*n為G的鄰接矩陣，w_ij表示邊(v_i,v_j)的權值，即兩個端點v_i與v_j之間的傳輸代價，其中，n為節點的個數；i、j大于等于1小于等于n；v_i與v_j表示第i個和第j個頂點。

3.根據權利要求1所述的基于動態路徑的負載遷移方法，其特征在于所述步驟一中，最短距離矩陣和最短路徑矩陣的計算方法如下：

設定初值：

其中，

對任意v_k∈V，更新

表示從v_i到v_j之間僅允許v₁,v₂,...,v_n作為中間點的路徑中最短長度，r_ij表示從v_i到v_j的等價最短路徑所經過的點集；

更新計算如下：

最終得到最短距離矩陣與最短路徑矩陣：

4.根據權利要求1所述的基于動態路徑的負載遷移方法，其特征在于所述步驟三的具體步驟如下：

(1)初始化路徑：

分解R(x,y)＝r_xy；MidP＝r_xy，nmu＝||MidP||，NumSet＝[1,num]，PathSet＝{}；

初始化路徑的中間節點集PathSet：

其中，MidP＝r_xy為v_x到v_y最短路徑的點集；nmu為中間點集的個數；

(2)對PathSet中每條路徑Pathk進行向后搜索：

將Pathk分解成num個集合：

更新PathSet:PathSet＝(PathSet/{Pathk})∪MidSet，直到

同時傳遞x到y方向負載均衡設備狀態，并更新x到當前節點k之間的節點狀態；

(3)對PathSet中每條路徑Pathk進行向前搜索：

將Pathk分解成num個集合：

更新PathSet:PathSet＝(PathSet/{Pathk})∪MidSet,直到

同時傳遞y到x方向負載均衡設備狀態，并更新y到當前節點k之間的節點狀態。

5.根據權利要求1所述的基于動態路徑的負載遷移方法，其特征在于所述步驟五的具體步驟如下：

當節點j出現數據流超過閾值時，節點j將判定為過載，啟動遷移調度算法，對于接受到的流量e，節點j處理時間為t_d，等待時間為t_w，將流量發送至距離節點j的距離為l的節點k上，所需時間為t_s，節點k的內存占用為σ_k，節點k的總內存上限為σ_total，判定是否進行遷移的參數Q為：

其中，Y為要遷移的流量大小，S_j為節點j的鄰接節點狀態表；若不存在任何一個鄰接節點空閑或預計傳輸代價大于直接處理的代價時，放棄將流量遷移，否則選擇一個適合的節點進行流量轉發。