【正文】 r checksum or the exclusive OR of both the source IP address and destination IP address improves the performance considerably, though moderate imbalance persists. The more putationally plex 16bit CRC of the ?vetuple (source address, destination address, source port,destination port and . . protocol id) gives excellent load balancing performance, keeping the load and queue lengths very similar on two links. Equally good load balancing can be achieved using tablebased hashing with adaptation, which requires less putation than the CRC but necessitates monitoring the link loads and storing (and adjusting) the mapping from table bins to links. Tablebased hashing has the additional advantage that it can distribute the load according to unequal weights. Further, an indexbased version of this scheme can alter the weight distribution with minimal disruption to existing ?ows . Our results con?rm that the indexbased hashing can accurately achieve a weighted distribution when adaptation is also used. The rest of this paper is anized as follows. In Section II we discuss related work in traf?c splitting and load balancing. Section III describes the behavior of an ideal traf?c splitter, explains the requirements for a practical system, and de?nes the performance metrics that will be used to assess various hashingbased schemes. The set of schemes that we consider are described in Section IV. The results of our study are described in Section V, and include analysis of the randomness inherent in the trace data (Section VA). We conclude and mention areas for future work in Section VI. II. RELATED WORK Load balancing has been used in telemunication works in the form of inverse multiplexing [4]. Inverse multiplexing allows service providers to offer wideband channels by bining multiple narrowband 56 kbps and 64 kbps trunks [5]. The load balancing in inverse multiplexing is typically based on round robin distribution of packets or bytes [6], [7]. Our work differs from inverse multiplexing in two important dimensions. First, inverse multiplexing is designed for use over pointtopoint links。有效利用負(fù)載均衡 的需要良好的 流量 分配方案。我們發(fā) 現(xiàn) 使用五元組的 CRC16 哈希 算法具有 優(yōu)秀 的負(fù)載均衡 性能。 關(guān)鍵字 — — 負(fù)載分享 ，哈希。通 常情況下，這些 并行 的 主鏈路 被配置為等價(jià)路徑負(fù)載均衡 進(jìn)行負(fù)載 。 為應(yīng)對(duì)互聯(lián)網(wǎng)流量的指數(shù)級(jí)增長(zhǎng)， 并行處理數(shù)據(jù)包的技術(shù)被復(fù)制到了包分析程序，代替了單一的處理引擎 。此外，由于在互聯(lián)網(wǎng)上的大部分的流量是基于 TCP 的分流方案 [1]，以避免數(shù)據(jù)包內(nèi) 錯(cuò)誤順序 的 TCP 流，這可能錯(cuò)誤地觸發(fā)擁塞控制機(jī)制，并導(dǎo)致不必要的吞吐量降低 [2][3]。 我們的研究結(jié)果是通過(guò)使用取自一個(gè)主要的互聯(lián)網(wǎng)骨干網(wǎng)提供商 的 兩個(gè) 主鏈路 的數(shù)據(jù)包 記錄，通過(guò) 以下方式獲得模擬的流量分配器的性能。使用 基于表的哈希適應(yīng)可以達(dá)到同樣良好的負(fù)載均衡， 比 CRC 需要較少的計(jì)算，但需要監(jiān)控鏈路負(fù)載和存儲(chǔ)（調(diào)整）的映射表 鍵 的鏈接。 本文的其余部分安排如下：在第二部分中，我們討論了分流和負(fù)載均衡相關(guān)工作。我們的 總結(jié)和今后的工作展望在第六部分。 我們的工作在兩個(gè)重要方面不同于 逆 復(fù)用。 其次 ，為了保持在 逆 復(fù)用 中 基于每個(gè)流的 FIFO 數(shù)據(jù)包的順序 的同步 ，有必要添加額外的 有 序列號(hào) 的 數(shù)據(jù)包報(bào)頭，或保持在信道的兩端的狀態(tài)。 在網(wǎng)絡(luò)環(huán)境中，基于 哈希的地址查找 [10]，流識(shí)別 [11]和數(shù)據(jù)包 的 解復(fù)用 [12]在過(guò)去已經(jīng)提出了。然而，提出的方案 不論是在模擬環(huán)境的 評(píng)估或真實(shí)的網(wǎng)絡(luò)測(cè)量。在這個(gè)方案中，每個(gè)下一跳 被設(shè)計(jì)了根據(jù)一個(gè)簡(jiǎn)單的偽隨機(jī)數(shù)函數(shù)分配了帶有流標(biāo)識(shí)符和下一跳標(biāo)識(shí)的權(quán)重 。 很明確的是 基于 哈希模式的流量分配 雖然已在過(guò)去 就 提出的，甚至一些簡(jiǎn)單的 方案 已在商業(yè)產(chǎn)品中實(shí)現(xiàn)， 而且這些方案 的 性能 已經(jīng)得到充分的評(píng)估。 在這樣一個(gè)系統(tǒng)中，流量分離器從一個(gè)高速鏈路中接收到傳入的數(shù)據(jù)包，并將其轉(zhuǎn)發(fā)到的一個(gè)速度較低的出 口 鏈 接 。 讓我們先來(lái)看看一個(gè)理想流 體模型，這里的交通是無(wú)限可分的。因此，理想的系統(tǒng)應(yīng)該滿足以下任何期間 [T， t]： 轉(zhuǎn)發(fā)出口鏈路 效 率的比例基本上是 分配 的流量負(fù)載。 在一 個(gè)真正的網(wǎng)絡(luò)系統(tǒng) 中 理想 的 負(fù)載均衡顯然是不切實(shí)際的。假定系統(tǒng)最初是空閑的， 當(dāng) 一個(gè)數(shù)據(jù)包到達(dá)。在實(shí)際系統(tǒng)中，流量分配器可以發(fā)送多個(gè)數(shù)據(jù)包在一 隊(duì)列中給同一個(gè)出口鏈 路 ， 然而這增加了帶寬的損失 。 在 不同 鏈路 中的時(shí)間 之間的差別，繁忙鏈路 的 時(shí) 間不應(yīng)該超過(guò) 在較慢的鏈路 上轉(zhuǎn)發(fā) 最大數(shù)據(jù)包的時(shí)間。 高效性。 一個(gè) TCP 流內(nèi)錯(cuò)誤的數(shù)據(jù)包順序，可以產(chǎn)生錯(cuò)誤的擁塞信號(hào)，并導(dǎo)致不必要的吞吐量降低 [2][3]。 以數(shù)據(jù)包的數(shù)據(jù)包輪循或 某種形式的公平排隊(duì)為例。 基于 哈希 處理的分流算法是無(wú)狀態(tài)的 易于 計(jì)算的， 特別與硬件的協(xié)作。 因?yàn)樵谙嗤?TCP 流的所有數(shù)據(jù)包具有相同的五元組 是真實(shí) 的 ， 因此相同 五元組 的哈希 函數(shù)輸入應(yīng)始終 具有 相同的輸出。正如我們?cè)诒竟?jié)開(kāi)始時(shí)已經(jīng)討論的，在一個(gè)理想的系統(tǒng)，流量負(fù)載應(yīng)該按出口鏈接率分配。 在我們的分析中，隊(duì)列長(zhǎng)度作為另一個(gè)性能指標(biāo)。 我們定義過(guò)工作狀態(tài)空閑時(shí)間是當(dāng)其他鏈路忙時(shí)至少有一條鏈路空閑的時(shí)間長(zhǎng)度 。 在直接哈希法中，流量分配根據(jù)五元組的字段通過(guò)哈希函數(shù)得到哈希值。 目標(biāo)地址哈希 . . 最簡(jiǎn)單的方案是哈希的 IP 目的地址模 塊 傳出鏈接的數(shù)量 N。 [10]我們提出了一個(gè) 異或折疊 目的 IP地址的哈希函數(shù)。 互聯(lián)網(wǎng)校驗(yàn) 網(wǎng)際校驗(yàn)和算法 RFC791[18]提出的是相對(duì)簡(jiǎn)單的計(jì)算，也是一個(gè)不錯(cuò)的哈希函數(shù)。 首先，直接哈希只能 分配 等量流量 給 多個(gè)傳出路徑。 其次，直接哈希調(diào)整負(fù)荷分布這幾乎是不可能的。人們也可以通過(guò)調(diào)整分配表調(diào)整流量 分配 的性能 ， M和 N的比值確定的粒度的調(diào)整。一種 方案 需要 N1 個(gè)關(guān)鍵字來(lái)保持，每個(gè) 用于每個(gè)輸出鏈路（參見(jiàn)圖 3）。對(duì)于每個(gè)到達(dá)的數(shù)據(jù)包，我們計(jì)算哈希值，然后與關(guān)鍵字進(jìn)行比較。在直接哈希查找的計(jì)算與接近 N1級(jí)別 的比較中，就是上述的情況。假設(shè)負(fù)載是均衡的，一半的流量將會(huì)被重新分配到不同鏈路上而引索方式只有三分之一的流量受到影響，鏈路的重新分配將會(huì)對(duì)顯著增加流內(nèi)的錯(cuò)誤序列。與此相反，基于級(jí)別的方法在出口鏈路會(huì)引起顯著的流變化。 更靈活的方法接近是聯(lián)系 M個(gè)鍵中的每個(gè)出口鏈路的引索，這種接近于引索的方式比基于 級(jí)別 的方法（ M指標(biāo)與 N1的 級(jí)別 ）需要更多的內(nèi)存。例如，假設(shè)我們要 分配在兩條鏈路 負(fù)荷超過(guò) 2:1的 流量 。注意：基于表 的 哈希當(dāng) M = N，一 對(duì) 一映射 時(shí)變?yōu)橹苯庸?。首先，基于表的哈希方?將流 量流分割成 M鍵，然后 與出口鏈路 映射到分配表（見(jiàn)圖 2）上。例如， 一個(gè)組織可能有兩個(gè)連接到互聯(lián)網(wǎng)骨干網(wǎng)而其中一個(gè)鏈路是另外 一個(gè)鏈路的速度的兩倍。 出口鏈路的索引可以用如下為 N的校驗(yàn)和計(jì)算結(jié)果表示： 哈希函數(shù)功能如下： CRC16 16 位的 CRC16 算法 [19]被提議為候選的負(fù)載均衡算法。這種方法選擇利用 在選擇 連接鏈路中 使用了 更多位的目的地址。 而很多 路由器廠商已經(jīng)實(shí)際應(yīng)用了這個(gè)哈希函數(shù) 。 這是非常簡(jiǎn)單的實(shí)現(xiàn)，不需要額外 的開(kāi)銷保持狀態(tài) 。 四 ．基于哈希的方法 在本節(jié)中，我們描述了基于哈希的負(fù)載均衡方案，在下一節(jié)中，我們將評(píng)估。 非工作 狀態(tài) 空閑時(shí)間。 在任何實(shí)際系統(tǒng)中，通常的負(fù)載分布曲線隨時(shí)間變動(dòng)。 負(fù)載分配。正如本文后面所寫(xiě)到的，許多基于哈希的模式執(zhí)行的很好。 然而，每個(gè)流的順序不能保證，除非額外的機(jī)制，如添加序列號(hào)或狀態(tài)保存。實(shí)現(xiàn)它而不需要一個(gè)新的協(xié)議層。流量分配器應(yīng)該盡量將流量分配接近參考模型。 流量分配是對(duì)每個(gè)轉(zhuǎn)發(fā)數(shù)據(jù)包路徑執(zhí)行，因此每個(gè)數(shù)據(jù)包的開(kāi)銷是一個(gè)大問(wèn)題。假設(shè)數(shù)據(jù)包服務(wù)期間通過(guò)鏈路 i進(jìn)行轉(zhuǎn)發(fā)期間，不再有公式 1，因?yàn)? ，其中 C是期間一直服務(wù)的數(shù)據(jù)包的一小部分。請(qǐng)注意，該數(shù)據(jù)包 使用的是可用帶. . 寬的一般 ，因此，它會(huì) 比理想的系統(tǒng)花費(fèi)兩倍的時(shí)間 來(lái)傳輸。再次， 沒(méi)有性能的保證 。這樣的系統(tǒng)是 高效的 ，因?yàn)樨?fù)載均衡 沒(méi)有帶寬的損失 。讓 Si（ T， t）的流量，轉(zhuǎn)發(fā)給 i鏈接期間 [T， t]。 在 [7]中， 已經(jīng) 證實(shí)的 到公平 隊(duì)列 和負(fù)載均衡 之間 存在著密切的關(guān)系。 III. 框 架 在本節(jié)中，我們描述 的是 理想流量分配行為， 理解為實(shí)際的系統(tǒng)要求 ，并 定義了 評(píng)估各種方案的 各種 性能指標(biāo)。 這種模式的外部鏈接數(shù)量大約是基于哈希的方案的幾倍 。 [16]提出了一個(gè)利用隨機(jī)數(shù) 的流量分配模式 。一些商業(yè)路由器產(chǎn)品已經(jīng)實(shí)現(xiàn)簡(jiǎn)單的通過(guò) IP目的地址的哈希流量分配 [13]。相比之下，基于 哈希 的 模式 可以維護(hù)每個(gè)流的包的順序，并可以實(shí)現(xiàn)，而不需要任何額外的協(xié)議支持。然而，互聯(lián)網(wǎng) 的負(fù)載均衡使得在網(wǎng)絡(luò)拓?fù)渲凶匀?的存在 冗余。 逆復(fù)用使 得 服務(wù)提供商能. . 夠提供結(jié)合多個(gè)窄帶寬帶通道 56 kbps 和 64 kbps 的 鏈路 [5]。 哈希模式的描述在第四部分 。 此外，這個(gè) 模式 基于索引的版本可以改變 權(quán)重 分布，以最小的中斷 退出流。使用互聯(lián)網(wǎng)校驗(yàn)或獨(dú) 自異或 源 IP 地址和目的 IP 地址，大大提高了性能，雖然適度的不平衡仍然存在。我們認(rèn)為 五元組是最直接的方法 ， 通過(guò) 哈希函數(shù)生成一個(gè) 關(guān)鍵 值，范圍 為 0， ...， N1， N為外部鏈接的數(shù)目， 我們也考慮基于表的 映射 ， 包括 M個(gè)哈希值 ，然后分配 M個(gè)值對(duì)應(yīng)的 N個(gè) 出站 鏈路 。流行的 Web 服務(wù)器往往 連接了很多的機(jī)器和路由器還要分別處理不同機(jī) 器的 HTTP 請(qǐng)求 。 DWDM 通信中繼線的容量擴(kuò)展，允許更大數(shù)量的信道在一個(gè)單一的光纖通過(guò)。 例如，許多大型企業(yè)網(wǎng)絡(luò)連接到多個(gè)互聯(lián)網(wǎng)服務(wù)提供商（ ISP），以實(shí)現(xiàn)冗余連接和分配流量負(fù)載?；诒淼?哈希還可以 根據(jù)不同權(quán)重分配流量負(fù)載 。雖然在過(guò)去已提出 過(guò) 基于哈希的 負(fù)載均衡 方案， 但 這是首次使用實(shí)際 流量記錄 的 結(jié)果的 全面研究 分析 。 all outgoing links are busy . . or idle at the same time. Such a system is workconserving。 its techniques are not typically applicable for work layer load balancing. Inter load bal