【導(dǎo)讀】ow.Althoughhashing-basedload. Keywords—Loadsharing,hashing.gured

　　

【正文】 IP 地址會(huì)導(dǎo)致顯著的不平衡。使用互聯(lián)網(wǎng)校驗(yàn)或獨(dú) 自異或 源 IP 地址和目的 IP 地址，大大提高了性能，雖然適度的不平衡仍然存在。更復(fù)雜的 16位 CRC 計(jì)算 的五元組（源地址，目的地址，源端口，目的端口，協(xié)議號(hào)） 得到了 優(yōu)秀的負(fù)載均衡性能，保持兩個(gè) 鏈路 非常相似的負(fù)載和隊(duì)列長度。使用 基于表的哈希適應(yīng)可以達(dá)到同樣良好的負(fù)載均衡， 比 CRC 需要較少的計(jì)算，但需要監(jiān)控鏈路負(fù)載和存儲(chǔ)（調(diào)整）的映射表 鍵 的鏈接。 以表為基礎(chǔ)的哈希具有另外的優(yōu)點(diǎn)，它可以根據(jù)不相等的權(quán)重分散負(fù)載。 此外，這個(gè) 模式 基于索引的版本可以改變 權(quán)重 分布，以最小的中斷 退出流。我們的研究結(jié)果證實(shí)， 當(dāng)自適應(yīng)時(shí) 基于索引的哈?？梢詼?zhǔn)確地實(shí)現(xiàn)了加權(quán)分配。 本文的其余部分安排如下：在第二部分中，我們討論了分流和負(fù)載均衡相關(guān)工作。第三部分描述了一個(gè)理想的流量分配行為，解釋一個(gè)實(shí)際的系統(tǒng)的要求，并且定義了將要使用到評估各種基于 哈希模式 的 方法 ， 并且定 義了各種基于哈希的模式 的性能 開銷 。 哈希模式的描述在第四部分 。 我們的研究成果則在第五部分 ，包括分析跟蹤數(shù)據(jù)（ VA 部分 ）的隨機(jī)性。我們的 總結(jié)和今后的工作展望在第六部分。 二 ． 相關(guān)工作 負(fù)載均衡已被用于在電信網(wǎng)絡(luò)中的逆復(fù)用 [4]。 逆復(fù)用使 得 服務(wù)提供商能. . 夠提供結(jié)合多個(gè)窄帶寬帶通道 56 kbps 和 64 kbps 的 鏈路 [5]。逆復(fù)用的負(fù)載均衡通常是基于輪循分布的數(shù)據(jù)包或字節(jié)數(shù) [6][7]。 我們的工作在兩個(gè)重要方面不同于 逆 復(fù)用。首先，逆復(fù)用的設(shè)計(jì) 是在點(diǎn)對點(diǎn)連接上使用 ，其技術(shù)通常不適用 于 網(wǎng)絡(luò)層 的 負(fù)載均衡。然而，互聯(lián)網(wǎng) 的負(fù)載均衡使得在網(wǎng)絡(luò)拓?fù)渲凶匀?的存在 冗余。 像 負(fù)載均衡的路徑，例如，等價(jià)多路徑，動(dòng)態(tài)發(fā)現(xiàn)的路由協(xié)議，如 OSPF [8]，而不是通過配置。 其次 ，為了保持在 逆 復(fù)用 中 基于每個(gè)流的 FIFO 數(shù)據(jù)包的順序 的同步 ，有必要添加額外的 有 序列號(hào) 的 數(shù)據(jù)包報(bào)頭，或保持在信道的兩端的狀態(tài)。但是，實(shí)施這些額外網(wǎng)絡(luò)負(fù)載均衡機(jī)制，需要一個(gè)新的網(wǎng)絡(luò)協(xié)議。相比之下，基于 哈希 的 模式 可以維護(hù)每個(gè)流的包的順序，并可以實(shí)現(xiàn)，而不需要任何額外的協(xié)議支持。 哈希方法 已廣泛用于索引和搜索 [9]。 在網(wǎng)絡(luò)環(huán)境中，基于 哈希的地址查找 [10]，流識(shí)別 [11]和數(shù)據(jù)包 的 解復(fù)用 [12]在過去已經(jīng)提出了。網(wǎng)絡(luò)負(fù)載均衡使用哈希 已不新奇 。一些商業(yè)路由器產(chǎn)品已經(jīng)實(shí)現(xiàn)簡單的通過 IP目的地址的哈希流量分配 [13]。在 OSPF 優(yōu)化的多路徑協(xié)議（ OSPFOMP） [14]， 一系列 通過多條路徑的負(fù)載均衡方法 已 被提及，包括循環(huán) 的使用 每個(gè) 數(shù)據(jù)包 除以在轉(zhuǎn)發(fā)表中可用的下一跳的目標(biāo) 地址 的前綴，再除以流量 得到的 哈希函數(shù)應(yīng)用到 一對源目 端上 。然而，提出的方案 不論是在模擬環(huán)境的 評估或真實(shí)的網(wǎng)絡(luò)測量。 在 OSPFOMP 負(fù)載均衡的研究， 都 假定 有 完美的 哈希 [15]。 [16]提出了一個(gè)利用隨機(jī)數(shù) 的流量分配模式 。 它適用于基于域名的映射 達(dá)到 負(fù)載均衡 [17]。在這個(gè)方案中，每個(gè)下一跳 被設(shè)計(jì)了根據(jù)一個(gè)簡單的偽隨機(jī)數(shù)函數(shù)分配了帶有流標(biāo)識(shí)符和下一跳標(biāo)識(shí)的權(quán)重 。 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)， 權(quán)重產(chǎn)生 ， 下一跳接收最高的權(quán)重?cái)?shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā) 。 這種模式的外部鏈接數(shù)量大約是基于哈希的方案的幾倍 。 而且 ，沒有對 這種方案的性能研究 。 很明確的是 基于 哈希模式的流量分配 雖然已在過去 就 提出的，甚至一些簡單的 方案 已在商業(yè)產(chǎn)品中實(shí)現(xiàn)， 而且這些方案 的 性能 已經(jīng)得到充分的評估。本文第一次廣泛的全面介紹了基于 哈希方案的 性能研究，使用骨干網(wǎng)真實(shí)的數(shù)據(jù)包。 III. 框 架 在本節(jié)中，我們描述 的是 理想流量分配行為， 理解為實(shí)際的系統(tǒng)要求 ，并 定義了 評估各種方案的 各種 性能指標(biāo)。 . . 圖 1中展示的是一個(gè)典型的包括了流量分配和多出口鏈路的例子 。 在這樣一個(gè)系統(tǒng)中，流量分離器從一個(gè)高速鏈路中接收到傳入的數(shù)據(jù)包，并將其轉(zhuǎn)發(fā)到的一個(gè)速度較低的出 口 鏈 接 。一個(gè)好的負(fù)載均衡系統(tǒng)應(yīng)該能夠 將流量分配到多個(gè) 比例均勻 的 或 預(yù)先定義的出口鏈路 。 在 [7]中， 已經(jīng) 證實(shí)的 到公平 隊(duì)列 和負(fù)載均衡 之間 存在著密切的關(guān)系。 我們現(xiàn)在就是要把他們的成果擴(kuò)展到獲取一個(gè)理想的流分配約束 。 讓我們先來看看一個(gè)理想流 體模型，這里的交通是無限可分的。假設(shè)有N 個(gè)導(dǎo)出鏈接中的負(fù)載平衡系統(tǒng)中，鏈路 i的容量為 Ni。讓 Si（ T， t）的流量，轉(zhuǎn)發(fā)給 i鏈接期間 [T， t]。理想的負(fù)載平衡系統(tǒng)以及相應(yīng)的系統(tǒng)應(yīng)該執(zhí)行一個(gè)單一的輸出鏈路的容量∑ Ui。因此，理想的系統(tǒng)應(yīng)該滿足以下任何期間 [T， t]： 轉(zhuǎn)發(fā)出口鏈路 效 率的比例基本上是 分配 的流量負(fù)載。在任何時(shí)候，流量負(fù)荷是完美的平衡，所有 出口 鏈接忙碌或閑置在同一時(shí)間。這樣的系統(tǒng)是 高效的 ，因?yàn)樨?fù)載均衡 沒有帶寬的損失 。 保證了工作效率 ，我們的意思是， 當(dāng)?shù)却龜?shù)據(jù)轉(zhuǎn)發(fā)的 時(shí)候 沒有一個(gè)傳出連接處于閑置狀態(tài)。 在一 個(gè)真正的網(wǎng)絡(luò)系統(tǒng) 中 理想 的 負(fù)載均衡顯然是不切實(shí)際的。 一個(gè)基本的轉(zhuǎn)發(fā)數(shù)據(jù)包單元時(shí)間是哈希模式下的幾倍 ，分組的負(fù)載均衡系統(tǒng) 工作 不再是出口鏈路的數(shù)量 。再次， 沒有性能的保證 。例如，假設(shè)一個(gè)負(fù)載均衡系統(tǒng)有兩個(gè)相同容量的 出口鏈路 。假定系統(tǒng)最初是空閑的， 當(dāng) 一個(gè)數(shù)據(jù)包到達(dá)。 數(shù)據(jù)包被轉(zhuǎn)發(fā)到兩個(gè)輸出鏈路 其中 之一。請注意，該數(shù)據(jù)包 使用的是可用帶. . 寬的一般 ，因此，它會(huì) 比理想的系統(tǒng)花費(fèi)兩倍的時(shí)間 來傳輸。在此期間， 兩個(gè)出口鏈路中一個(gè)忙于數(shù)據(jù)包的服務(wù)，而另外一個(gè)則 保持空閑。在實(shí)際系統(tǒng)中，流量分配器可以發(fā)送多個(gè)數(shù)據(jù)包在一 隊(duì)列中給同一個(gè)出口鏈 路 ， 然而這增加了帶寬的損失 。 在一個(gè)分組的系統(tǒng)， 最壞的考慮 是當(dāng)所有出口鏈路處于閑置，當(dāng)時(shí)間 T時(shí)，一個(gè)最大尺寸為 Pmax的數(shù)據(jù)包到達(dá)且沒有更多的數(shù)據(jù)包。假設(shè)數(shù)據(jù)包服務(wù)期間通過鏈路 i進(jìn)行轉(zhuǎn)發(fā)期間，不再有公式 1，因?yàn)? ，其中 C是期間一直服務(wù)的數(shù)據(jù)包的一小部分。因此，在分組系統(tǒng)中，理想的負(fù)載平衡，應(yīng)滿足下面的條件： 在任何時(shí)間間隔 [T,t]中 ， Pmax 是 其中最大包 的 大小。 在 不同 鏈路 中的時(shí)間 之間的差別，繁忙鏈路 的 時(shí) 間不應(yīng)該超過 在較慢的鏈路 上轉(zhuǎn)發(fā) 最大數(shù)據(jù)包的時(shí)間。 分流方案對于互聯(lián)網(wǎng)的負(fù)載均衡應(yīng)滿足一 些基本要求 ： 低開銷。 流量分配是對每個(gè)轉(zhuǎn)發(fā)數(shù)據(jù)包路徑執(zhí)行，因此每個(gè)數(shù)據(jù)包的開銷是一個(gè)大問題。流量拆分算法，應(yīng)該是很簡單的，最好保持狀態(tài)沒有或很少。 高效性。 流量分布欠佳會(huì)導(dǎo)致不均勻的鏈路利用率和帶寬損失。流量分配器應(yīng)該盡量將流量分配接近參考模型。 每個(gè)流的排序。 一個(gè) TCP 流內(nèi)錯(cuò)誤的數(shù)據(jù)包順序，可以產(chǎn)生錯(cuò)誤的擁塞信號(hào)，并導(dǎo)致不必要的吞吐量降低 [2][3]。因此這是一個(gè)基本的要求分流算法維護(hù)每個(gè)流的數(shù)據(jù)包順序。實(shí)現(xiàn)它而不需要一個(gè)新的協(xié)議層。 讓我們現(xiàn)在應(yīng)用一些接近上述要求的流量分配方法 。 以數(shù)據(jù)包的數(shù)據(jù)包輪循或 某種形式的公平排隊(duì)為例。開銷成本 低通常是接近最優(yōu)的性能。 然而，每個(gè)流的順序不能保證，除非額外的機(jī)制，如添加序列號(hào)或狀態(tài)保存。 這種額外的機(jī)制，將極大地增加了開銷，并且在許多情況下，只 能 工作在點(diǎn)至點(diǎn) 鏈路 。 基于 哈希 處理的分流算法是無狀態(tài)的 易于 計(jì)算的， 特別與硬件的協(xié)作。. . 更好的是，如果哈希函數(shù)使用任意的五元組作為輸入的組合，每個(gè)流的順序可以保存 [1]。正如本文后面所寫到的，許多基于哈希的模式執(zhí)行的很好?？偟膩碚f，基于哈希的模式符合上述要求并提供最佳的權(quán)衡。 因?yàn)樵谙嗤?TCP 流的所有數(shù)據(jù)包具有相同的五元組 是真實(shí) 的 ， 因此相同 五元組 的哈希 函數(shù)輸入應(yīng)始終 具有 相同的輸出。 我們現(xiàn)在討論評估 互聯(lián)網(wǎng)流量分配 的負(fù)載均衡算法基本性能指標(biāo)。 負(fù)載分配。 從負(fù)載均衡的角度來看，最重要的性能指標(biāo)是隨著時(shí)間的產(chǎn)生的多個(gè)出站鏈路的字節(jié)分布。正如我們在本節(jié)開始時(shí)已經(jīng)討論的，在一個(gè)理想的系統(tǒng)，流量負(fù)載應(yīng)該按出口鏈接率分配。 隊(duì)列長度。 在任何實(shí)際系統(tǒng)中，通常的負(fù)載分布曲線隨時(shí)間變動(dòng)。 這種負(fù)載波動(dòng)通過緩沖，從而免除外向 鏈路 隊(duì)列長度反映負(fù)載均衡的累積效應(yīng)。 在我們的分析中，隊(duì)列長度作為另一個(gè)性能指標(biāo)。 隊(duì)列長度度量考慮到用戶的實(shí)際負(fù)荷 分布在在輕負(fù)荷期間遠(yuǎn)遠(yuǎn)低于重負(fù)載期間的差異，一個(gè)良好的流量分配算法不一定每個(gè)時(shí)間段都要有完美的負(fù)載分布，但它應(yīng)該是能夠保持小的隊(duì)列和平衡。 非工作 狀態(tài) 空閑時(shí)間。 正如我們已經(jīng)討論過， 數(shù)據(jù)包 的負(fù)載均衡系統(tǒng)是非工作 狀態(tài)的 。 我們定義過工作狀態(tài)空閑時(shí)間是當(dāng)其他鏈路忙時(shí)至少有一條鏈路空閑的時(shí)間長度 ?？臻e時(shí)間度量捕獲系統(tǒng)： 更大的非工作狀態(tài)空閑時(shí)間 ， 越有工作狀態(tài)的傾向 ， 所以這是 效率較低的負(fù)載均衡。 四 ．基于哈希的方法 在本節(jié)中，我們描述了基于哈希的負(fù)載均衡方案，在下一節(jié)中，我們將評估。 直接哈希是一個(gè) 簡單的 流量分配模式 。 在直接哈希法中，流量分配根據(jù)五元組的字段通過哈希函數(shù)得到哈希值。 并使用哈希值，選擇輸出鏈路。 這是非常簡單的實(shí)現(xiàn)，不需要額外 的開銷保持狀態(tài) 。在本文中，我們考慮以下五個(gè)直接哈希 方法 。 目標(biāo)地址哈希 . . 最簡單的方案是哈希的 IP 目的地址模 塊 傳出鏈接的數(shù)量 N。 它可以表示為： 在這個(gè)方案中，如果 N= 2k是 我們有效地利用目的地址的最后 k 位作為出站鏈接的索引。 而很多 路由器廠商已經(jīng)實(shí)際應(yīng)用了這個(gè)哈希函數(shù) 。 使用異或目標(biāo)地址 處理的哈希函數(shù) 異或 已經(jīng)用在許多的哈希函數(shù) 中 ， 并且在其他程序中表現(xiàn)出了 良好的性能 。 [10]我們提出了一個(gè) 異或折疊 目的 IP地址的哈希函數(shù)。此哈希函數(shù)可以表示為： 目的地址數(shù)組中的 Di的第 i個(gè)地址段 。這種方法選擇利用 在選擇 連接鏈路中 使用了 更多位的目的地址。 使用異或折疊源目地址的哈希處理 地址 簡單的修改以前的哈希函數(shù)，把源地址也包括在計(jì)算之中，異或折疊源目地址，哈希功能可以描述如以下： 其中和是八位的源目 IP地址。 互聯(lián)網(wǎng)校驗(yàn) 網(wǎng)際校驗(yàn)和算法 RFC791[18]提出的是相對簡單的計(jì)算，也是一個(gè)不錯(cuò)的哈希函數(shù)。 在本文中，我們 實(shí)驗(yàn)其流量分配的性能，我們把五元組當(dāng)做 16 位的英特網(wǎng)校驗(yàn)和 。 出口鏈路的索引可以用如下為 N的校驗(yàn)和計(jì)算結(jié)果表示： 哈希函數(shù)功能如下： CRC16 16 位的 CRC16 算法 [19]被提議為候選的負(fù)載均衡算法。雖然與上述討論的哈希函數(shù)相比更加復(fù)雜，但是 CRC16 已經(jīng)被成功的應(yīng)用于高速網(wǎng)絡(luò)之中，CRC16 方案中，使用五元組分配流量，應(yīng) CRC16，得到獲取出口鏈路的模型，哈希函數(shù)可以描述如下： . . 的哈希 直接哈希雖然很簡單，它也有一定的局限性。 首先，直接哈希只能 分配 等量流量 給 多個(gè)傳出路徑。然而，它并不總是希望分發(fā)的流量負(fù)荷均勻。例如， 一個(gè)組織可能有兩個(gè)連接到互聯(lián)網(wǎng)骨干網(wǎng)而其中一個(gè)鏈路是另外 一個(gè)鏈路的速度的兩倍。 這個(gè)機(jī)構(gòu)可能希望按 2： 1的比例分配流量。 其次，直接哈希調(diào)整負(fù)荷分布這幾乎是不可能的。基于表的哈希方法，下面我們將討論解決通過分離分流和負(fù)載分配這兩個(gè)問題。首先，基于表的哈希方案 將流 量流分割成 M鍵，然后 與出口鏈路 映射到分配表（見圖 2）上。通過改變 出口鏈路對應(yīng)的鍵的分布 ，人們可以在一個(gè)預(yù)先定義的比例分配流量。人們也可以通過調(diào)整分配表調(diào)整流量 分配 的性能 ， M和 N的比值確定的粒度的調(diào)整。通常情況下， M是大于 N的一個(gè)或兩個(gè)數(shù)量級，從而可以分 割加載在一個(gè)相當(dāng)精細(xì)的粒度。注意：基于表 的 哈希當(dāng) M = N，一 對 一映射 時(shí)變?yōu)橹苯庸！? 有兩種基本 的 基于表的 實(shí)施方案 。一種 方案 需要 N1 個(gè)關(guān)鍵字來保持，每個(gè) 用于每個(gè)輸出鏈路（參見圖 3）。 用 M個(gè) 關(guān)鍵字來劃分成 N 個(gè)分區(qū)， 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)，流量分配器計(jì)算哈希和對 N1個(gè)關(guān)鍵字的哈希值進(jìn)行比較，以確定即將 使用 的 出口 鏈接。例如，假設(shè)我們要 分配在兩條鏈路 負(fù)荷超過 2:1的 流量 。我們可以簡單地設(shè)定關(guān)鍵字 為 M / 3。對于每個(gè)到達(dá)的數(shù)據(jù)包，我們計(jì)算哈希值，然后與關(guān)鍵字進(jìn)行比較。如果哈希值是大于 M / 3，該數(shù)據(jù)包被發(fā)送到第 一 條鏈路 ，否則第二 條鏈路。 更靈活的方法接近是聯(lián)系 M個(gè)鍵中的每個(gè)出口鏈路的引索，這種接近于引索的方式比基于 級別 的方法（ M指標(biāo)與 N1的 級別 ）需要更多的內(nèi)存。另一方面，使用引索的方式哈希值與出口鏈路的映射關(guān)系更加的簡單了。在直接哈希查找的計(jì)算與接近 N1級別 的比較中，就是上述的情況。 基于引索的方式更加的靈活，因?yàn)?M個(gè)鍵（哈希值）被獨(dú)立的分配給了N 個(gè)出口鏈路，這樣可以當(dāng)流量調(diào)整，建立新連接或關(guān)機(jī)時(shí)最小化對現(xiàn)存流量負(fù)載的干擾。與此相反，基于級別的方法在出口鏈路會(huì)引起顯著的流變化。. . 例如，假設(shè)一條新鏈接被添加到 已存在的兩條負(fù)載均衡鏈路上。假設(shè)負(fù)載是均衡的，一半的流量將會(huì)被重新分配到不同鏈路上而引索方式只有三分之一的流量受到影響，鏈路的重新分配將會(huì)對顯著增加流內(nèi)的錯(cuò)誤序列。