[發明專利]一種網絡負載均衡的混合算法

無效

• 申請號: 201310429836.9
• 申請日: 2013-09-18
• 公開（公告）號: CN103491019A
• 公開（公告）日: 2014-01-01
• 發明（設計）人: 王雷;趙玉龍;王宇
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H04L12/803
• 分類號: H04L12/803
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及計算機網絡，具體為負載均衡算法。

背景技術

網絡負載均衡在計算機網絡中具有很重要的作用，負載均衡建立在現有網絡結構之上，它提供了一種廉價有效透明的方法擴展網絡設備和服務器的帶寬、增加吞吐量、加強網絡數據處理能力、提高網絡的靈活性和可用性。負載均衡包括調度和轉發兩部分，如圖1所示。調度是負載均衡的關鍵，轉發引擎負責根據目的IP將數據包發送至下一級設備。

最初的調度算法是簡單的Round-robin，按數據包的順序，依次發給不同編號的轉發引擎。因為Round-robin工作在數據包的層面，導致數據包到達目的設備時，會出現亂序現象，同時也破壞了網絡流的局部性。之后，一種基于flow（數據流）層面的Hash算法成為主流。Flow指擁有相同5元組的數據包，而5元組指的是源IP，目的IP，源端口，目的端口和協議類型。將5元組作為Hash函數的key，得到的結果就是要發送的轉發引擎。這種方法的弊端是，當一個flow中的數據包數量非常大時，就會造成某個轉發引擎負載過重。清華大學的時磊（音譯），劉斌（音譯）等人通過研究發現，網絡數據包中，即便是同一個flow中的數據包，也不是連續不斷的發送的。如果一個flow中的兩個數據包之間的時間間隔超過了一定的臨界值，就認為它們屬于不同的flow?slice，這時就應該將它們分配到不同的轉發引擎上，這就是基于flow-slice（FS）的負載均衡算法，如圖2所示。

發明內容

本發明提出了一種混合的負載均衡調度算法，這里混合的對象是Hash算法和flow-slice算法。核心思想是，在flow-slice算法的基礎上，引入一個大小可配置的flow-slice表（FS?table），用以存儲已經出現過的flow的5元組及上一條數據包的時間。

本發明與FS的不同之處在于：

1.FS調度中，用hash表存儲相應的flow信息，為保證盡可能多的保存數據，這個表很大。本發明中的FS?table是一個大小可調節的表，大小一般為500-1000。

2.FS調度中，新的flow-slice轉發引擎ID的確定是用全局的round-robin，本發明中使用hash算法。

3.FS調度中，同一flow的不同flow?slice的轉發引擎ID的確定使用全局round-robin，本發明對每個flow使用round-robin。

本發明的具體流程如圖3所示。

附圖說明

圖1負責均衡調度模型；

圖2FS調度算法流程；

圖3混合調度算法流程。

具體實施方式

第一步，獲取5元組和時間

從網絡數據包網絡層的IP報頭讀取源IP和目的IP，然后讀取傳輸層協議類型，根據傳輸層協議（tcp或者udp）類型讀取源端口和目的端口。這樣就得到一個完整的5元組。記錄數據包的到達時間。

第二步，確定數據包發往的轉發引擎

這個過程可描述為：

2.1判斷5元組是否在FS?table中，如果是，轉2.2步，否則轉2.5步。

2.2計算當前數據包與FS?table中記錄的時間之差，是否超過約定的時間間隔，若果是，轉2.3，否則轉2.4。

2.3按round-robin決定新的轉發引擎，修改轉發引擎和時間。

2.4向FS?table中記錄的轉發引擎發數據包。

2.5判斷FS?table是否已滿，如果沒有，轉2.6步，否則轉2.7步。

2.6對5元組使用Hash，確定其初始發往的轉發引擎。將5元組，時間和轉發引擎插入FS?table中。

2.7找出最久沒有使用的數據項a，計算當前數據包與a的時間之差，如果超過約定時間間隔，轉2.8，否則轉2.9

2.8對5元組使用Hash，確定其初始發往的轉發引擎。用5元組，時間和轉發引擎插替換a數據項。

2.9對5元組使用Hash，確定其發往的轉發引擎。