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