[發明專利]一種基于Q值法的負載均衡調度算法

有效

• 申請號: 201310011222.9
• 申請日: 2013-01-11
• 公開（公告）號: CN103078806A
• 公開（公告）日: 2013-05-01
• 發明（設計）人: 陳擁權;李梁;張羽
• 申請（專利權）人: 合肥寰景信息技術有限公司
• 主分類號: H04L12/803
• 分類號: H04L12/803
• 代理公司: 安徽合肥華信知識產權代理有限公司 34112
• 代理人: 方琦

技術領域

本發明屬于網絡集群服務器技術領域，具體為一種基于Q值法的負載均衡調度算法。

背景技術

負載均衡是集群服務器中的關鍵技術，它決定了集群分配器的請求分發策略，并且直接影響著服務器集群系統的整體性能。

集群負載均衡技術主要分靜態信息和動態信息算法。靜態算法主要適用于較小規模的、同構的、提供靜態網頁信息服務的系統；而動態算法適用于大規模的、異構的、提供動態網頁信息服務的系統。

早期的負載均衡算法有隨機(Random)算法和輪詢(Round-Robin)算法，特別是輪詢算法采用傳統的輪轉轉發分配方式，計算簡單、效率高，應用較廣。但這兩種算法不考慮后端服務器的差異，不能保證在不同的服務器間達到負載均衡，因此，不適合于異構的集群系統。另外還有基于服務器中當前活躍連接數(正在處理的請求連接)的最小連接數(Least?Connections?First)算法，選擇當前正在處理的請求個數最少的服務器作為轉發對象。但活躍請求連接個數并不能完全反映服務器處理負荷上的差異，如處理能力強的服務器在單位時間內可以處理更多的請求。此外，還可能在請求量少時將多個請求分配到同一臺服務器。

為了適應異構集群系統的需求，出現了加權輪詢(Weighted?Round-Robin)算法和加權最小連接數(Weighted?Least?Connections?First)算法，通過為不同的服務器配置不同的權值來平衡服務器間的差異，選取合適的轉發對象。但隨著動態、多媒體網絡信息的大量應用，靜態的權值信息不能表現動態的負載特征，隨著系統運行時間增長，將導致集群負載分布的不平衡。

為了克服靜態配置權值信息的缺點，提出了動態計算權值信息的方法。動態計算權值的負載均衡算法有基于輪詢的(如WRR_time、WRR_num)和基于活躍連接數的(如Round_Trip、XimtByte)。它們都是通過周期性地獲取服務器狀態信息，動態地計算出當前每臺服務器應具有的權值。權值的計算方法：第一種是用采樣周期內每臺服務器的平均響應產生時間(以請求轉發到達服務器至第一個響應的比特輸出為響應產生時間)來計算，如WRR_time(基于WRR)和Round-Trip(基于WLCF)；第二種是用采樣周期內每臺服務器的活躍連接數來計算，如WRR_num(基于WRR)；第三種是用采樣周期內輸出的字節流量來計算，如XimtByte(基于WLCF)。

由上可見，動態計算權值信息的方法，僅僅是對權值的動態計算以反映服務器的負載狀況。在動態得到權值信息后，調度算法仍與傳統算法類似，在調度算法層面上并沒有本質改進。

發明內容

針對上述問題，本發明提供一種基于Q值法的負載均衡調度算法。該算法可以結合靜態配置權值或動態配置權值的方法使用。

為了達到上述目的，本發明所采用的技術方案為：

一種基于Q值法的負載均衡調度算法，其特征在于：將網絡中的負載均衡問題與代表名額分配問題相類比，借鑒代表名額分配問題中的Q值法，結合靜態或動態權值配置方法以解決網絡中的負載均衡問題。

所述的一種基于Q值法的負載均衡調度算法，其特征在于：Q值法結合靜態權值配置方法時，按以下步驟進行：

(1)通過靜態測試，確定網絡中各服務器的負載特性；

(2)為利用Q值法，根據步驟(1)所測得的負載特性，計算出對應代表名額分配問題中的參數；

(3)步驟(2)中的參數保存在調度服務器上，當連接請求到達時，利用Q值法將連接請求分配到服務器。

所述的一種基于Q值法的負載均衡調度算法，其特征在于：Q值法結合動態權值配置方法時，按以下步驟進行：

(1)通過靜態測試，確定網絡中各服務器的負載特性；

(2)選擇一種動態權值配置方法，周期性對服務器負載狀況做采樣檢查；

(3)對步驟(2)的檢查結果做適當變換，計算出對應代表名額分配問題中的參數；

(4)利用步驟(3)中求得的參數，使用Q值法依采樣周期中新增連接到達次序，并將連接分配到服務器；重新啟動采樣周期。

所述的一種基于Q值法的負載均衡調度算法，其特征在于：所述Q值法是一種基于代表名額分配問題的通用方法。

本發明利用負載均衡問題與代表名額分配問題的相似性，利用Q值法解決負載均衡問題，與傳統的wRR、wLCF等簡單算法相比，提高了負載調度的均衡性。

具體實施方式