【正文】 基于引索的方式更加的靈活，因?yàn)?M個(gè)鍵（哈希值）被獨(dú)立的分配給了N 個(gè)出口鏈路，這樣可以當(dāng)流量調(diào)整，建立新連接或關(guān)機(jī)時(shí)最小化對(duì)現(xiàn)存流量負(fù)載的干擾。 用 M個(gè) 關(guān)鍵字來(lái)劃分成 N 個(gè)分區(qū)， 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)，流量分配器計(jì)算哈希和對(duì) N1個(gè)關(guān)鍵字的哈希值進(jìn)行比較，以確定即將 使用 的 出口 鏈接?；诒淼墓７椒?，下面我們將討論解決通過(guò)分離分流和負(fù)載分配這兩個(gè)問(wèn)題。 在本文中，我們 實(shí)驗(yàn)其流量分配的性能，我們把五元組當(dāng)做 16 位的英特網(wǎng)校驗(yàn)和 。 它可以表示為： 在這個(gè)方案中，如果 N= 2k是 我們有效地利用目的地址的最后 k 位作為出站鏈接的索引?？臻e時(shí)間度量捕獲系統(tǒng)： 更大的非工作狀態(tài)空閑時(shí)間 ， 越有工作狀態(tài)的傾向 ， 所以這是 效率較低的負(fù)載均衡。 隊(duì)列長(zhǎng)度。. . 更好的是，如果哈希函數(shù)使用任意的五元組作為輸入的組合，每個(gè)流的順序可以保存 [1]。因此這是一個(gè)基本的要求分流算法維護(hù)每個(gè)流的數(shù)據(jù)包順序。 分流方案對(duì)于互聯(lián)網(wǎng)的負(fù)載均衡應(yīng)滿足一 些基本要求 ： 低開(kāi)銷。 數(shù)據(jù)包被轉(zhuǎn)發(fā)到兩個(gè)輸出鏈路 其中 之一。在任何時(shí)候，流量負(fù)荷是完美的平衡，所有 出口 鏈接忙碌或閑置在同一時(shí)間。一個(gè)好的負(fù)載均衡系統(tǒng)應(yīng)該能夠 將流量分配到多個(gè) 比例均勻 的 或 預(yù)先定義的出口鏈路 。 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)， 權(quán)重產(chǎn)生 ， 下一跳接收最高的權(quán)重?cái)?shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā) 。網(wǎng)絡(luò)負(fù)載均衡使用哈希 已不新奇 。首先，逆復(fù)用的設(shè)計(jì) 是在點(diǎn)對(duì)點(diǎn)連接上使用 ，其技術(shù)通常不適用 于 網(wǎng)絡(luò)層 的 負(fù)載均衡。第三部分描述了一個(gè)理想的流量分配行為，解釋一個(gè)實(shí)際的系統(tǒng)的要求，并且定義了將要使用到評(píng)估各種基于 哈希模式 的 方法 ， 并且定 義了各種基于哈希的模式 的性能 開(kāi)銷 。我們發(fā)現(xiàn)， 在兩條主干網(wǎng)上 直接 哈希 目標(biāo) IP 地址會(huì)導(dǎo)致顯著的不平衡。同樣的技術(shù)也可以用來(lái)在擴(kuò)展的 網(wǎng)頁(yè) 服務(wù)器。 引言 負(fù)載均衡（也稱為負(fù)載分擔(dān)）是改善互聯(lián)網(wǎng)的性能和可擴(kuò)展性的關(guān)鍵技術(shù)。我們研究分布在多個(gè) 鏈路層 幾個(gè)哈希方案的執(zhí)行情況 ， 同時(shí)保留流量數(shù)據(jù)包的通信順序。 all outgoing links are busy . . or idle at the same time. Such a system is workconserving?；诒淼?哈希還可以 根據(jù)不同權(quán)重分配流量負(fù)載 。 DWDM 通信中繼線的容量擴(kuò)展，允許更大數(shù)量的信道在一個(gè)單一的光纖通過(guò)。我們認(rèn)為 五元組是最直接的方法 ， 通過(guò) 哈希函數(shù)生成一個(gè) 關(guān)鍵 值，范圍 為 0， ...， N1， N為外部鏈接的數(shù)目， 我們也考慮基于表的 映射 ， 包括 M個(gè)哈希值 ，然后分配 M個(gè)值對(duì)應(yīng)的 N個(gè) 出站 鏈路 。 此外，這個(gè) 模式 基于索引的版本可以改變 權(quán)重 分布，以最小的中斷 退出流。 逆復(fù)用使 得 服務(wù)提供商能. . 夠提供結(jié)合多個(gè)窄帶寬帶通道 56 kbps 和 64 kbps 的 鏈路 [5]。相比之下，基于 哈希 的 模式 可以維護(hù)每個(gè)流的包的順序，并可以實(shí)現(xiàn)，而不需要任何額外的協(xié)議支持。 [16]提出了一個(gè)利用隨機(jī)數(shù) 的流量分配模式 。 III. 框 架 在本節(jié)中，我們描述 的是 理想流量分配行為， 理解為實(shí)際的系統(tǒng)要求 ，并 定義了 評(píng)估各種方案的 各種 性能指標(biāo)。讓 Si（ T， t）的流量，轉(zhuǎn)發(fā)給 i鏈接期間 [T， t]。再次， 沒(méi)有性能的保證 。假設(shè)數(shù)據(jù)包服務(wù)期間通過(guò)鏈路 i進(jìn)行轉(zhuǎn)發(fā)期間，不再有公式 1，因?yàn)? ，其中 C是期間一直服務(wù)的數(shù)據(jù)包的一小部分。流量分配器應(yīng)該盡量將流量分配接近參考模型。 然而，每個(gè)流的順序不能保證，除非額外的機(jī)制，如添加序列號(hào)或狀態(tài)保存。 負(fù)載分配。 非工作 狀態(tài) 空閑時(shí)間。 這是非常簡(jiǎn)單的實(shí)現(xiàn)，不需要額外 的開(kāi)銷保持狀態(tài) 。這種方法選擇利用 在選擇 連接鏈路中 使用了 更多位的目的地址。例如， 一個(gè)組織可能有兩個(gè)連接到互聯(lián)網(wǎng)骨干網(wǎng)而其中一個(gè)鏈路是另外 一個(gè)鏈路的速度的兩倍。注意：基于表 的 哈希當(dāng) M = N，一 對(duì) 一映射 時(shí)變?yōu)橹苯庸！? 更靈活的方法接近是聯(lián)系 M個(gè)鍵中的每個(gè)出口鏈路的引索，這種接近于引索的方式比基于 級(jí)別 的方法（ M指標(biāo)與 N1的 級(jí)別 ）需要更多的內(nèi)存。假設(shè)負(fù)載是均衡的，一半的流量將會(huì)被重新分配到不同鏈路上而引索方式只有三分之一的流量受到影響，鏈路的重新分配將會(huì)對(duì)顯著增加流內(nèi)的錯(cuò)誤序列。對(duì)于每個(gè)到達(dá)的數(shù)據(jù)包，我們計(jì)算哈希值，然后與關(guān)鍵字進(jìn)行比較。人們也可以通過(guò)調(diào)整分配表調(diào)整流量 分配 的性能 ， M和 N的比值確定的粒度的調(diào)整。 首先，直接哈希只能 分配 等量流量 給 多個(gè)傳出路徑。 [10]我們提出了一個(gè) 異或折疊 目的 IP地址的哈希函數(shù)。 在直接哈希法中，流量分配根據(jù)五元組的字段通過(guò)哈希函數(shù)得到哈希值。 在我們的分析中，隊(duì)列長(zhǎng)度作為另一個(gè)性能指標(biāo)。 因?yàn)樵谙嗤?TCP 流的所有數(shù)據(jù)包具有相同的五元組 是真實(shí) 的 ， 因此相同 五元組 的哈希 函數(shù)輸入應(yīng)始終 具有 相同的輸出。 以數(shù)據(jù)包的數(shù)據(jù)包輪循或 某種形式的公平排隊(duì)為例。 高效性。在實(shí)際系統(tǒng)中，流量分配器可以發(fā)送多個(gè)數(shù)據(jù)包在一 隊(duì)列中給同一個(gè)出口鏈 路 ， 然而這增加了帶寬的損失 。 在一 個(gè)真正的網(wǎng)絡(luò)系統(tǒng) 中 理想 的 負(fù)載均衡顯然是不切實(shí)際的。 讓我們先來(lái)看看一個(gè)理想流 體模型，這里的交通是無(wú)限可分的。 很明確的是 基于 哈希模式的流量分配 雖然已在過(guò)去 就 提出的，甚至一些簡(jiǎn)單的 方案 已在商業(yè)產(chǎn)品中實(shí)現(xiàn)， 而且這些方案 的 性能 已經(jīng)得到充分的評(píng)估。然而，提出的方案 不論是在模擬環(huán)境的 評(píng)估或真實(shí)的網(wǎng)絡(luò)測(cè)量。 其次 ，為了保持在 逆 復(fù)用 中 基于每個(gè)流的 FIFO 數(shù)據(jù)包的順序 的同步 ，有必要添加額外的 有 序列號(hào) 的 數(shù)據(jù)包報(bào)頭，或保持在信道的兩端的狀態(tài)。我們的 總結(jié)和今后的工作展望在第六部分。使用 基于表的哈希適應(yīng)可以達(dá)到同樣良好的負(fù)載均衡， 比 CRC 需要較少的計(jì)算，但需要監(jiān)控鏈路負(fù)載和存儲(chǔ)（調(diào)整）的映射表 鍵 的鏈接。此外，由于在互聯(lián)網(wǎng)上的大部分的流量是基于 TCP 的分流方案 [1]，以避免數(shù)據(jù)包內(nèi) 錯(cuò)誤順序 的 TCP 流，這可能錯(cuò)誤地觸發(fā)擁塞控制機(jī)制，并導(dǎo)致不必要的吞吐量降低 [2][3]。通 常情況下，這些 并行 的 主鏈路 被配置為等價(jià)路徑負(fù)載均衡 進(jìn)行負(fù)載 。我們發(fā) 現(xiàn) 使用五元組的 CRC16 哈希 算法具有 優(yōu)秀 的負(fù)載均衡 性能。. . 中文 5790 字 畢業(yè)設(shè)計(jì) 外文翻譯 專 業(yè) 網(wǎng) 絡(luò) 工 程 班 級(jí) 學(xué) 生姓名 xx 學(xué) 號(hào) xx 指 導(dǎo)教師 . . 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) technology is deployed in the future Inter backbone. DWDM expands the capacity of munication trunks by allowing a greater number of channels to be carried on a single optical fiber. With potentially tens or even hundreds of DWDM channels between major points, load balancing is essential in best utilizing the multiple parallel channels. Parallel architectures have been used for packet processing for coping with exponential growth in Inter traffic, Instead of one processing engine, packets are dispatched to multiple parallel engines inside a router to increase the overall processing throughput. The same technique is also used in scaling web servers. Popular web servers often operate a farm of machines and the routers connected to them split the HTTP requests to different machines. For all of these exampl