【正文】 假設(shè)負載是均衡的，一半的流量將會被重新分配到不同鏈路上而引索方式只有三分之一的流量受到影響，鏈路的重新分配將會對顯著增加流內(nèi)的錯誤序列。與此相反，基于級別的方法在出口鏈路會引起顯著的流變化。在直接哈希查找的計算與接近 N1級別 的比較中，就是上述的情況。 更靈活的方法接近是聯(lián)系 M個鍵中的每個出口鏈路的引索，這種接近于引索的方式比基于 級別 的方法（ M指標與 N1的 級別 ）需要更多的內(nèi)存。對于每個到達的數(shù)據(jù)包，我們計算哈希值，然后與關(guān)鍵字進行比較。例如，假設(shè)我們要 分配在兩條鏈路 負荷超過 2:1的 流量 。一種 方案 需要 N1 個關(guān)鍵字來保持，每個 用于每個輸出鏈路（參見圖 3）。注意：基于表 的 哈希當 M = N，一 對 一映射 時變?yōu)橹苯庸！Ｈ藗円部梢酝ㄟ^調(diào)整分配表調(diào)整流量 分配 的性能 ， M和 N的比值確定的粒度的調(diào)整。首先，基于表的哈希方案 將流 量流分割成 M鍵，然后 與出口鏈路 映射到分配表（見圖 2）上。 其次，直接哈希調(diào)整負荷分布這幾乎是不可能的。例如， 一個組織可能有兩個連接到互聯(lián)網(wǎng)骨干網(wǎng)而其中一個鏈路是另外 一個鏈路的速度的兩倍。 首先，直接哈希只能 分配 等量流量 給 多個傳出路徑。 出口鏈路的索引可以用如下為 N的校驗和計算結(jié)果表示： 哈希函數(shù)功能如下： CRC16 16 位的 CRC16 算法 [19]被提議為候選的負載均衡算法。 互聯(lián)網(wǎng)校驗 網(wǎng)際校驗和算法 RFC791[18]提出的是相對簡單的計算，也是一個不錯的哈希函數(shù)。這種方法選擇利用 在選擇 連接鏈路中 使用了 更多位的目的地址。 [10]我們提出了一個 異或折疊 目的 IP地址的哈希函數(shù)。 而很多 路由器廠商已經(jīng)實際應(yīng)用了這個哈希函數(shù) 。 目標地址哈希 . . 最簡單的方案是哈希的 IP 目的地址模 塊 傳出鏈接的數(shù)量 N。 這是非常簡單的實現(xiàn)，不需要額外 的開銷保持狀態(tài) 。 在直接哈希法中，流量分配根據(jù)五元組的字段通過哈希函數(shù)得到哈希值。 四 ．基于哈希的方法 在本節(jié)中，我們描述了基于哈希的負載均衡方案，在下一節(jié)中，我們將評估。 我們定義過工作狀態(tài)空閑時間是當其他鏈路忙時至少有一條鏈路空閑的時間長度 。 非工作 狀態(tài) 空閑時間。 在我們的分析中，隊列長度作為另一個性能指標。 在任何實際系統(tǒng)中，通常的負載分布曲線隨時間變動。正如我們在本節(jié)開始時已經(jīng)討論的，在一個理想的系統(tǒng)，流量負載應(yīng)該按出口鏈接率分配。 負載分配。 因為在相同的 TCP 流的所有數(shù)據(jù)包具有相同的五元組 是真實 的 ， 因此相同 五元組 的哈希 函數(shù)輸入應(yīng)始終 具有 相同的輸出。正如本文后面所寫到的，許多基于哈希的模式執(zhí)行的很好。 基于 哈希 處理的分流算法是無狀態(tài)的 易于 計算的， 特別與硬件的協(xié)作。 然而，每個流的順序不能保證，除非額外的機制，如添加序列號或狀態(tài)保存。 以數(shù)據(jù)包的數(shù)據(jù)包輪循或 某種形式的公平排隊為例。實現(xiàn)它而不需要一個新的協(xié)議層。 一個 TCP 流內(nèi)錯誤的數(shù)據(jù)包順序，可以產(chǎn)生錯誤的擁塞信號，并導致不必要的吞吐量降低 [2][3]。流量分配器應(yīng)該盡量將流量分配接近參考模型。 高效性。 流量分配是對每個轉(zhuǎn)發(fā)數(shù)據(jù)包路徑執(zhí)行，因此每個數(shù)據(jù)包的開銷是一個大問題。 在 不同 鏈路 中的時間 之間的差別，繁忙鏈路 的 時 間不應(yīng)該超過 在較慢的鏈路 上轉(zhuǎn)發(fā) 最大數(shù)據(jù)包的時間。假設(shè)數(shù)據(jù)包服務(wù)期間通過鏈路 i進行轉(zhuǎn)發(fā)期間，不再有公式 1，因為 ，其中 C是期間一直服務(wù)的數(shù)據(jù)包的一小部分。在實際系統(tǒng)中，流量分配器可以發(fā)送多個數(shù)據(jù)包在一 隊列中給同一個出口鏈 路 ， 然而這增加了帶寬的損失 。請注意，該數(shù)據(jù)包 使用的是可用帶. . 寬的一般 ，因此，它會 比理想的系統(tǒng)花費兩倍的時間 來傳輸。假定系統(tǒng)最初是空閑的， 當 一個數(shù)據(jù)包到達。再次， 沒有性能的保證 。 在一 個真正的網(wǎng)絡(luò)系統(tǒng) 中 理想 的 負載均衡顯然是不切實際的。這樣的系統(tǒng)是 高效的 ，因為負載均衡 沒有帶寬的損失 。因此，理想的系統(tǒng)應(yīng)該滿足以下任何期間 [T， t]： 轉(zhuǎn)發(fā)出口鏈路 效 率的比例基本上是 分配 的流量負載。讓 Si（ T， t）的流量，轉(zhuǎn)發(fā)給 i鏈接期間 [T， t]。 讓我們先來看看一個理想流 體模型，這里的交通是無限可分的。 在 [7]中， 已經(jīng) 證實的 到公平 隊列 和負載均衡 之間 存在著密切的關(guān)系。 在這樣一個系統(tǒng)中，流量分離器從一個高速鏈路中接收到傳入的數(shù)據(jù)包，并將其轉(zhuǎn)發(fā)到的一個速度較低的出 口 鏈 接 。 III. 框 架 在本節(jié)中，我們描述 的是 理想流量分配行為， 理解為實際的系統(tǒng)要求 ，并 定義了 評估各種方案的 各種 性能指標。 很明確的是 基于 哈希模式的流量分配 雖然已在過去 就 提出的，甚至一些簡單的 方案 已在商業(yè)產(chǎn)品中實現(xiàn)， 而且這些方案 的 性能 已經(jīng)得到充分的評估。 這種模式的外部鏈接數(shù)量大約是基于哈希的方案的幾倍 。在這個方案中，每個下一跳 被設(shè)計了根據(jù)一個簡單的偽隨機數(shù)函數(shù)分配了帶有流標識符和下一跳標識的權(quán)重 。 [16]提出了一個利用隨機數(shù) 的流量分配模式 。然而，提出的方案 不論是在模擬環(huán)境的 評估或真實的網(wǎng)絡(luò)測量。一些商業(yè)路由器產(chǎn)品已經(jīng)實現(xiàn)簡單的通過 IP目的地址的哈希流量分配 [13]。 在網(wǎng)絡(luò)環(huán)境中，基于 哈希的地址查找 [10]，流識別 [11]和數(shù)據(jù)包 的 解復用 [12]在過去已經(jīng)提出了。相比之下，基于 哈希 的 模式 可以維護每個流的包的順序，并可以實現(xiàn)，而不需要任何額外的協(xié)議支持。 其次 ，為了保持在 逆 復用 中 基于每個流的 FIFO 數(shù)據(jù)包的順序 的同步 ，有必要添加額外的 有 序列號 的 數(shù)據(jù)包報頭，或保持在信道的兩端的狀態(tài)。然而，互聯(lián)網(wǎng) 的負載均衡使得在網(wǎng)絡(luò)拓撲中自然 的存在 冗余。 我們的工作在兩個重要方面不同于 逆 復用。 逆復用使 得 服務(wù)提供商能. . 夠提供結(jié)合多個窄帶寬帶通道 56 kbps 和 64 kbps 的 鏈路 [5]。我們的 總結(jié)和今后的工作展望在第六部分。 哈希模式的描述在第四部分 。 本文的其余部分安排如下：在第二部分中，我們討論了分流和負載均衡相關(guān)工作。 此外，這個 模式 基于索引的版本可以改變 權(quán)重 分布，以最小的中斷 退出流。使用 基于表的哈希適應(yīng)可以達到同樣良好的負載均衡， 比 CRC 需要較少的計算，但需要監(jiān)控鏈路負載和存儲（調(diào)整）的映射表 鍵 的鏈接。使用互聯(lián)網(wǎng)校驗或獨 自異或 源 IP 地址和目的 IP 地址，大大提高了性能，雖然適度的不平衡仍然存在。 我們的研究結(jié)果是通過使用取自一個主要的互聯(lián)網(wǎng)骨干網(wǎng)提供商 的 兩個 主鏈路 的數(shù)據(jù)包 記錄，通過 以下方式獲得模擬的流量分配器的性能。我們認為 五元組是最直接的方法 ， 通過 哈希函數(shù)生成一個 關(guān)鍵 值，范圍 為 0， ...， N1， N為外部鏈接的數(shù)目， 我們也考慮基于表的 映射 ， 包括 M個哈希值 ，然后分配 M個值對應(yīng)的 N個 出站 鏈路 。此外，由于在互聯(lián)網(wǎng)上的大部分的流量是基于 TCP 的分流方案 [1]，以避免數(shù)據(jù)包內(nèi) 錯誤順序 的 TCP 流，這可能錯誤地觸發(fā)擁塞控制機制，并導致不必要的吞吐量降低 [2][3]。流行的 Web 服務(wù)器往往 連接了很多的機器和路由器還要分別處理不同機 器的 HTTP 請求 。 為應(yīng)對互聯(lián)網(wǎng)流量的指數(shù)級增長， 并行處理數(shù)據(jù)包的技術(shù)被復制到了包分析程序，代替了單一的處理引擎 。 DWDM 通信中繼線的容量擴展，允許更大數(shù)量的信道在一個單一的光纖通過。通 常情況下，這些 并行 的 主鏈路 被配置為等價路徑負載均衡 進行負載 。 例如，許多大型企業(yè)網(wǎng)絡(luò)連接到多個互聯(lián)網(wǎng)服務(wù)提供商（ ISP），以實現(xiàn)冗余連接和分配流量負載。 關(guān)鍵字 — — 負載分享 ，哈希?；诒淼?哈希還可以 根據(jù)不同權(quán)重分配流量負載 。我們發(fā) 現(xiàn) 使用五元組的 CRC16 哈希 算法具有 優(yōu)秀 的負載均衡 性能。雖然在過去已提出 過 基于哈希的 負載均衡 方案， 但 這是首次使用實際 流量記錄 的 結(jié)果的 全面研究 分析 。有效利用負載均衡 的需要良好的 流量 分配方案。 all outgoing links are busy . . or idle at the same time. Such a system is workconserving。. . 中文 5790 字 畢業(yè)設(shè)計 外文翻譯 專 業(yè) 網(wǎng) 絡(luò) 工 程 班 級 學 生姓名 xx 學 號 xx 指 導教師 . . Performance of HashingBased Schemes for Inter Load Balancing Zhiruo Cao ,Zheng Wang ,Ellen Zegura College of Computing Geia Institute of Technology Atlanta, GA 303320280 Bell Labs Lucent Technologies Holmdel , NJ 07733 Abstract—Load balancing is a key technique for improving Inter performance. Effective use of load balancing requires good traffic distribution schemes. We study the performance of several hashing schemes for distributing traffic over multiple links while preserving the order of packets within a ?ow. Although hashingbased load balancing schemes have been proposed in the past, this is the first prehensive study of their performance using real traffic traces. We evaluate five direct hashing methods and one tablebased hashing method. We find that hashing using a 16bit CRC over the Five tuple gives excellent load balancing performance. Further, loadadaptive tablebased hashing using the exclusive OR of the source and destination IP addresses achieves parable performance to the 16bit CRC. Tablebased hashing can also distribute traffic load according to unequal weights. We also report on four other schemes with poor to moderate performance. Keywords—Load sharing, hashing. I. INTRODUCTION Load balancing (also known as load sharing) is a key technique for improving the performance and scalability of the Inter. For example, many large enterprise works are connected to multiple Inter Service Providers (ISPs) to achieve redundant connectivity and to distribute traffic loading. Inside the Inter, the backbones are often engineered to have multiple parallel trunks between major Points of Presence to ensure high availability. Typically, these parallel trunks are con?gured as equalcost paths and allow load balancing over them. . . The parallel trunks may bee even more ubiquitous when the promising Dense Wavelength Division Multiplexing (DWDM