【正文】 ancing, however, makes use of the natural redundancy in the work topology. The paths for load balancing, for example, equalcost multipaths, are discovered dynamically by routing protocols, such as OSPF [8], rather than through configuration. Second, in order to maintain synchronization and perflow FIFO packet ordering in inverse . . multiplexing, it is necessary to add extra packet headers with sequence numbers or to keep state at both ends of the channel. But, implementing these additional mechanisms for work load balancing requires a new work protocol. In parison, the hashingbased schemes can maintain perflow packet ordering and can be implemented without requiring any additional protocol support. Hashing has been widely used in indexing and searching [9].In the working context, hashingbased algorithms for address lookup [10], ?ow identi?cation [11] and packet demultiplexing [12] have been proposed in the past. The use of hashing for work load balancing is not new. Some mercial router products have implemented simple hashing over the IP destination address to distribute traf?c [13]. In the OSPF Optimized Multipath protocol (OSPFOMP) [14], a number of possible approaches for load balancing over multiple paths are mentioned , including perpacket round robin, dividing destination pre?xes among available next hops in the forwarding table, and dividing traf?c according to a hash function applied to the source and destination pair. However, the proposed schemes are not evaluated with simulation or real work measurement. In the study of load balancing with OSPFOMP, perfect hashing is assumed[15]. A traf?c splitting scheme using random numbers is proposed in [16]. It applies the namebased mappings approach to load balancing [17]. In this scheme, each nexthop is assigned with a weight based on a simple pseudorandom number function seeded with the ?ow identi?er and the nexthop identi?er. When a packet arrives, the weights are generated, and the nexthop receiving the highest weight is used for forwarding. The scheme is approximately times as expensive as a hashingbased scheme, where is the number of outgoing links. Again, no performance study on the proposed scheme is presented. It is clear that although hashingbased schemes for traf?c splitting have been proposed in the past, and some simple schemes have even been implemented in mercial products, the performance of such schemes has not been adequately evaluated .This paper presents the ?rst prehensive performance study on a wide range of hashingbased schemes, using real packet traces from backbone works. III. FRAMEWORK . . In this section, we describe the behavior of an ideal traf?c splitter, explain the requirements for a practical system, and de?ne the performance metrics for assessing various schemes. A. Reference Model A load balancing system typically prises a traf?c splitter and multiple outgoing links as shown in Figure 1. In such a system, the traf?c splitter receives an ining packet from a higherspeed link and forwards it to one of the lowerspeed outgoing links. A good load balancing system should be able to split the traf?c to the multiple outgoing links evenly or by some prede?ned proportion. In [7], it has been observed that there is a close relationship between fair queuing and load balancing. We now extend their observation to a mathematical model to obtain the constraints for ideal traf?c splitting. Let us ?rst look at an ideal ?uid model where the traf?c isin?nitely divisible. Suppose that there are out going links in the load balancing system, and the capacity of link I is ui . Let Si(T,t) be the amount of traf?c forwarded to link I during the period[T,t]. The ideal load balancing system should perform as well as the corresponding system with a single outgoing link of capacity ∑ui . Therefore, the ideal system should satisfy the following for any period [T,t]: The traf?c load is essentially split in proportion to the rates of the outgoing links. At any time instance, the traf?c load is perfectly balanced。我們研究分布在多個(gè) 鏈路層 幾個(gè)哈希方案的執(zhí)行情況 ， 同時(shí)保留流量數(shù)據(jù)包的通信順序。此外，基于 哈希表的 負(fù)載自適應(yīng)使用 源目 IP 地址 使用異或位移的 達(dá)到媲美 CRC16 的性能 。 引言 負(fù)載均衡（也稱為負(fù)載分擔(dān)）是改善互聯(lián)網(wǎng)的性能和可擴(kuò)展性的關(guān)鍵技術(shù)。 當(dāng)復(fù)前途密集波分復(fù)用（ DWDM）技術(shù)的部署在未來的 骨干 互聯(lián)網(wǎng) ，并行的主干鏈路 可能變得更加無處不在。同樣的技術(shù)也可以用來在擴(kuò)展的 網(wǎng)頁 服務(wù)器。 在本文中，我們提出 和評(píng)估 了一 系列 基于哈希的維護(hù)每個(gè)流的包的順序分流算法。我們發(fā)現(xiàn)， 在兩條主干網(wǎng)上 直接 哈希 目標(biāo) IP 地址會(huì)導(dǎo)致顯著的不平衡。 以表為基礎(chǔ)的哈希具有另外的優(yōu)點(diǎn)，它可以根據(jù)不相等的權(quán)重分散負(fù)載。第三部分描述了一個(gè)理想的流量分配行為，解釋一個(gè)實(shí)際的系統(tǒng)的要求，并且定義了將要使用到評(píng)估各種基于 哈希模式 的 方法 ， 并且定 義了各種基于哈希的模式 的性能 開銷 。 二 ． 相關(guān)工作 負(fù)載均衡已被用于在電信網(wǎng)絡(luò)中的逆復(fù)用 [4]。首先，逆復(fù)用的設(shè)計(jì) 是在點(diǎn)對(duì)點(diǎn)連接上使用 ，其技術(shù)通常不適用 于 網(wǎng)絡(luò)層 的 負(fù)載均衡。但是，實(shí)施這些額外網(wǎng)絡(luò)負(fù)載均衡機(jī)制，需要一個(gè)新的網(wǎng)絡(luò)協(xié)議。網(wǎng)絡(luò)負(fù)載均衡使用哈希 已不新奇 。 在 OSPFOMP 負(fù)載均衡的研究， 都 假定 有 完美的 哈希 [15]。 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)， 權(quán)重產(chǎn)生 ， 下一跳接收最高的權(quán)重?cái)?shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā) 。本文第一次廣泛的全面介紹了基于 哈希方案的 性能研究，使用骨干網(wǎng)真實(shí)的數(shù)據(jù)包。一個(gè)好的負(fù)載均衡系統(tǒng)應(yīng)該能夠 將流量分配到多個(gè) 比例均勻 的 或 預(yù)先定義的出口鏈路 。假設(shè)有N 個(gè)導(dǎo)出鏈接中的負(fù)載平衡系統(tǒng)中，鏈路 i的容量為 Ni。在任何時(shí)候，流量負(fù)荷是完美的平衡，所有 出口 鏈接忙碌或閑置在同一時(shí)間。 一個(gè)基本的轉(zhuǎn)發(fā)數(shù)據(jù)包單元時(shí)間是哈希模式下的幾倍 ，分組的負(fù)載均衡系統(tǒng) 工作 不再是出口鏈路的數(shù)量 。 數(shù)據(jù)包被轉(zhuǎn)發(fā)到兩個(gè)輸出鏈路 其中 之一。 在一個(gè)分組的系統(tǒng)， 最壞的考慮 是當(dāng)所有出口鏈路處于閑置，當(dāng)時(shí)間 T時(shí)，一個(gè)最大尺寸為 Pmax的數(shù)據(jù)包到達(dá)且沒有更多的數(shù)據(jù)包。 分流方案對(duì)于互聯(lián)網(wǎng)的負(fù)載均衡應(yīng)滿足一 些基本要求 ： 低開銷。 流量分布欠佳會(huì)導(dǎo)致不均勻的鏈路利用率和帶寬損失。因此這是一個(gè)基本的要求分流算法維護(hù)每個(gè)流的數(shù)據(jù)包順序。開銷成本 低通常是接近最優(yōu)的性能。. . 更好的是，如果哈希函數(shù)使用任意的五元組作為輸入的組合，每個(gè)流的順序可以保存 [1]。 我們現(xiàn)在討論評(píng)估 互聯(lián)網(wǎng)流量分配 的負(fù)載均衡算法基本性能指標(biāo)。 隊(duì)列長度。 隊(duì)列長度度量考慮到用戶的實(shí)際負(fù)荷 分布在在輕負(fù)荷期間遠(yuǎn)遠(yuǎn)低于重負(fù)載期間的差異，一個(gè)良好的流量分配算法不一定每個(gè)時(shí)間段都要有完美的負(fù)載分布，但它應(yīng)該是能夠保持小的隊(duì)列和平衡。空閑時(shí)間度量捕獲系統(tǒng)： 更大的非工作狀態(tài)空閑時(shí)間 ， 越有工作狀態(tài)的傾向 ， 所以這是 效率較低的負(fù)載均衡。 并使用哈希值，選擇輸出鏈路。 它可以表示為： 在這個(gè)方案中，如果 N= 2k是 我們有效地利用目的地址的最后 k 位作為出站鏈接的索引。此哈希函數(shù)可以表示為： 目的地址數(shù)組中的 Di的第 i個(gè)地址段 。 在本文中，我們 實(shí)驗(yàn)其流量分配的性能，我們把五元組當(dāng)做 16 位的英特網(wǎng)校驗(yàn)和 。然而，它并不總是希望分發(fā)的流量負(fù)荷均勻?；诒淼墓７椒ǎ旅嫖覀儗⒂懻摻鉀Q通過分離分流和負(fù)載分配這兩個(gè)問題。通常情況下， M是大于 N的一個(gè)或兩個(gè)數(shù)量級(jí)，從而可以分 割加載在一個(gè)相當(dāng)精細(xì)的粒度。 用 M個(gè) 關(guān)鍵字來劃分成 N 個(gè)分區(qū)， 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)，流量分配器計(jì)算哈希和對(duì) N1個(gè)關(guān)鍵字的哈希值進(jìn)行比較，以確定即將 使用 的 出口 鏈接。如果哈希值是大于 M / 3，該數(shù)據(jù)包被發(fā)送到第 一 條鏈路 ，否則第二 條鏈路。 基于引索的方式更加的靈活，因?yàn)?M個(gè)鍵（哈希值）被獨(dú)立的分配給了N 個(gè)出口鏈路，這樣可以當(dāng)流量調(diào)整，建立新連接或關(guān)機(jī)時(shí)最小化對(duì)現(xiàn)存流量負(fù)載的干擾。