IP地址散列調(diào)度均衡算法及其實(shí)現(xiàn)原理
來源：中國政府采購招標(biāo)網(wǎng) 時(shí)間：2008/9/22
作為網(wǎng)絡(luò)請求分配的控制者，負(fù)載均衡器起著至關(guān)重要的作用，考慮到在任何網(wǎng)絡(luò)請求中，都有一個(gè)源地址和目標(biāo)地址(源IP和目標(biāo)IP)，因此我們這里討論P(yáng)地址散列調(diào)度均衡算法。
在上一篇文章中，我們指出：網(wǎng)絡(luò)負(fù)載均衡本質(zhì)上是分布式業(yè)務(wù)中調(diào)度系統(tǒng)的一種實(shí)現(xiàn)。作為網(wǎng)絡(luò)請求分配的控制者，負(fù)載均衡器起著至關(guān)重要的作用。考慮到在任何一個(gè)網(wǎng)絡(luò)請求中，都有一個(gè)源地址和目標(biāo)地址(源IP和目標(biāo)IP)。這樣，在負(fù)載均衡器中，我們就可以利用這兩個(gè)IP，通過一種散列算法把請求分配到不同的服務(wù)器上。這種算法就是目標(biāo)散列調(diào)度(利用目標(biāo)IP)和源地址散列調(diào)度(利用源IP)。這兩種算法為靜態(tài)算法。
下面我們分別簡要講述一下。
目標(biāo)地址散列調(diào)度(Destination Hashing Scheduling)算法
目標(biāo)地址散列調(diào)度(Destination Hashing Scheduling)算法的基本原理是：此算法根據(jù)請求的目標(biāo)IP地址，作為散列鍵(Hash Key)從靜態(tài)分配的散列表找出對應(yīng)的服務(wù)器，若該服務(wù)器是可用的且未超載的，則將請求發(fā)送到該服務(wù)器，否則返回空。這里我們設(shè)定某個(gè)服務(wù)器的連接數(shù)目大于2倍的權(quán)值，則表示此服務(wù)器已超載。
目標(biāo)地址散列算法流程
假設(shè)有一組服務(wù)器S = {S0, S1, ..., Sn-1}，W(i)表示服務(wù)器Si的權(quán)值，C(i)表示服務(wù)器Si的當(dāng)前連接數(shù)。ServerNode[]是一個(gè)Hash表。此表大小就是服務(wù)器的數(shù)目，也可根據(jù)算法模塊中的具體條件修改。
算法的初始化是將所有服務(wù)器順序、循環(huán)地放置到ServerNode表中。
n = ServerNode[hashkey(dest_ip)];
if ( (n is dead) OR (W(n) == 0) OR (C(n) > 2*W(n))) then
return NULL;
return n; // 如果一切OK
上面的算法中，hashkey()為散列函數(shù)。在實(shí)現(xiàn)時(shí)，一般采用素?cái)?shù)乘法Hash函數(shù)，通過乘以素?cái)?shù)使得散列鍵值盡可能地達(dá)到較均勻的分布。
Hashkey實(shí)現(xiàn)如下：
static inline unsigned hashkey(unsigned int dest_ip)
{
return (dest_ip* 2654435761UL) & HASH_TAB_MASK;
}
其中，2654435761UL是2到2^32 (4294967296)間接近于黃金分割的素?cái)?shù)，
(sqrt(5) - 1) / 2 = 0.618033989
2654435761 / 4294967296 = 0.618033987
源地址散列調(diào)度(Source Hashing Scheduling)算法
源地址散列調(diào)度(Source Hashing Scheduling)算法的基本原理是：此算法根據(jù)請求的源IP地址，作為散列鍵(Hash Key)從靜態(tài)分配的散列表找出對應(yīng)的服務(wù)器，若該服務(wù)器是可用的且未超載的，則將請求發(fā)送到該服務(wù)器，否則返回空。這里我們設(shè)定某個(gè)服務(wù)器的連接數(shù)目大于2倍的權(quán)值，則表示此服務(wù)器已超載。、
可以看出，這種方式和目標(biāo)地址散列調(diào)度方法是類似的，唯一的區(qū)別是以源地址作為散列鍵。
源地址散列算法流程
源地址散列算法流程和目標(biāo)地址散列算法流程類似，采用的散列函數(shù)也一樣。唯一不同的是，需要將請求的目標(biāo)IP地址換成請求的源IP地址，所以這里不再贅述。
總結(jié)
源地址散列調(diào)度和目標(biāo)散列調(diào)度屬于兩種靜態(tài)的調(diào)度算法，在實(shí)際應(yīng)用中，這兩種調(diào)度算法可以結(jié)合使用在防火墻集群中，它們可以保證整個(gè)系統(tǒng)的唯一出入口。