[發明專利]一種基于樸素貝葉斯分類的負載均衡算法

在審

• 申請號: 201310536971.3
• 申請日: 2013-11-05
• 公開（公告）號: CN104618406A
• 公開（公告）日: 2015-05-13
• 發明（設計）人: 不公告發明人
• 申請（專利權）人: 鎮江華揚信息科技有限公司
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本算法是涉及到計算機中涉及到一種算法領域。

背景技術

云計算是繼分布式處理、并行處理、網格計算之后的一種新的計算模式，其核心是將大型數據中心的計算資源進行虛擬化，并向用戶提供以計算資源為形式的服務。隨著互聯網中的數據量與日俱增，云計算環境（簡稱云環境）必須具備提供大量并發訪問服務的能力，如何將云環境中的總體處理負載“合理”分配到各個節點上，避免各節點的處理能力和I/O能力成為云環境提供服務的瓶頸，是云計算研究領域的熱點問題之一。目前，主要采用負載均衡技術，通過調整各個節點上的處理負載分配情況，進行節點間的負載平衡，從而最大限度地利用系統資源，以實現用戶服務和擴展性能的最大化在現有的負載均衡技術研究中，根據其實現負載均衡策略方式的不同，主要可以分為靜態負載均衡技術和動態負載均衡技術。靜態負載均衡利用現有任務信息，根據系統硬件等參數，通過調度算法來選擇合適的節點，分配、執行任務。動態負載均衡技術則根據系統當前狀態或最近狀態去決定如何給分布式系統的每個節點分配任務，若節點任務超載，超載任務將被轉移至其他節點執行，如基于蟻群算法的負載均衡算法，基于貪心算法的負載均衡算法^[5]等。另外，文獻[6]提出了一種基于虛擬機實時遷移的自適應負載均衡算法，通過當前數據和歷史數據，預測虛擬機遷移后對系統影響程度，從而選擇有效遷移策略。文獻[7]則將分布式系統中基于移動代理的負載均衡策略應用于云環境，利用agent輪詢機制收集節點信息，進行節點間負載遷移。由于每個任務占用資源難以預測，且各節點處理能力不同，動態負載均衡技術與靜態負載均衡技術相比，更能根據系統性能的變化，動態地調整各節點的負載分配情況，負載均衡效果較好。但在實現動態調度時，由于未對云環境中各節點的負載情況進行有效評估，使得任務的分配調度不合理，容易造成任務在各集群節點間的大范圍“抖動”情況，給系統造成大量額外開銷。本文將針對上述問題，結合云計算分布式并行的特點，提出了一種基于樸素貝葉斯分類的負載均衡技術。首先，對云環境中的心跳包信息進行定期收集，并采用樸素貝葉斯算法對各節點負載狀態進行劃分；然后，根節點根據劃分結果，實現任務和資源分配的合理調度，有效實現云環境中的各節點負載均衡，提高集群的性能。

發明內容

定義1?負載特征值：云環境中節點s的靜態負載特征和動態負載特征，用于反映節點運行時的總體負載狀況，記為WV(s)。

在計算各節點負載特征值時，我們設定節點的負載特征屬性主要包括CPU、內存、磁盤及網絡等四個方面。其中，CPU和內存屬性反映當前節點任務處理過程中的負載情況；磁盤屬性反映當前節點I/O負載情況；網絡屬性則反映了節點任務的接收及傳送情況。下面將給出各個負載特征值屬性的具體定義：

定義2??CPU負載特征值：設云環境中節點s的CPU的運行隊列中任務書為C₁、CPU上下文切換率為C₂、空閑CPU時間百分比為C₃，則其CPU負載特征值WV^c(s)為：

????其中，為一組權重系數，且，根據不同的應用和需求可動態調整權重。

定義3?內存負載特征值：設云環境中節點s的內存的物理內存大小R₁、虛擬內存大小R₂、空閑存儲器的大小R₃，則其內存負載特征值為WV^R(s)為：

????其中，為一組權重系數，且，根據不同的應用和需求可動態調整權重。

???????定義4?磁盤負載特征值：設云環境中節點s的磁盤利用率為D₁、磁盤訪問速度為D₂、磁盤隊列長度為D₃，則其磁盤負載特征值WV^D(s)為：

????其中，為一組權重系數，且，根據不同的應用和需求可動態調整權重。

???????定義5?網絡負載特征值：設云環境中節點s的網絡往返延時為N₁和網絡帶寬N₂，則其網絡負載特征值WV^N(s)為，則有：

????其中，為一組權重系數，且，根據不同的應用和需求動態可調整權重。

????另外，為了對節點s的負載情況進行貝葉斯分類，根據上述定義，訓練樣本的格式定義如下：