【正文】 folding has been used in many hash functions, and has been shown to provide good performance in other applications [10]. We propose a hash function with XOR folding of the destination IP address. This hash function can be expressed as: Where is Di the ith octet of the destination IP address .This approach utilizes more bits of the destination address in selecting the link. Hashing Using XOR Folding of Source and Destination Addresses A simple modification to the previous hash function is to include the source address in the putation, ., XOR folding with both the destination IP address and the source IP address .This hash function can be expressed as: where Si and are the ith octets of the source and destination IP addresses respectively. Inter Checksum The Inter Checksum algorithm proposed in RFC791 [18] is relatively simple to pute and is also a good hash function. In this paper, we examine its performance for traffic splitting. We feed the ?vetuple as input to the 16bit Inter checksum putation. The index of the outgoing link is calculated from the checksum result modulo by N. This hash function can be expressed as: CRC16 The 16bit CRC (Cyclic Redundant Checksum) algorithm [19] has been . . proposed as a possible candidate for load balancing. Although more plex pared with the other hash functions discussed above, CRC16 has been successfully implemented in highspeed systems. In the CRC16 scheme, the traffic splitter takes the ?vetuple, applies CRC16, and takes modulo by to obtain the outgoing link. The hash function can be expressed as: B. TableBased Hashing Although direct hashing is simple, it also has some limitations. First, direct hashing can only split traffic into equal amounts to multiple outgoing paths. However, it is not always desirable to distribute the traffic load evenly. For example, an anization may have two links to Inter backbones with one link twice the speed of the other. The anization may wish to distribute the traffic with a 2:1 ratio. Secondly, with direct hashing, it is almost impossible to tune the load distribution. The tablebased hashing approach we discuss below addresses both issues by separating traffic splitting and load allocation. A tablebased hashing scheme first splits a traffic stream into M bins. The M bins are then mapped to N outgoing links based on an allocation table (see Figure 2). By changing the allocation of the bins to the outgoing links, one can distribute traffic in a predefined ratio. One can also tune the performance of traffic splitting by adjusting the allocation table. The ratio of M and N determines the granularity of adjustment. Typically, M is one or two orders of magnitude larger than N, thus one can split the load at a fairly fine granularity. Note that tablebased hashing bees direct hashing When M=N and we have onetoone mapping. There are two basic approaches for implementing a table based scheme. One . . approach requires N1 thresholds to be maintained, one for each outgoing link (see Figure 3). The thresholds are used to divide the M bins into N partitions. When a packet arrives, the traffic splitter putes the hashing and pares the hash value against the N1 thresholds to determine the outgoing link. For example, suppose we want to split load over two outgoing links with a 2:1 ratio. We can simply set the threshold to M/3. For each arriving packet, we pute the hash value, and then pare with the threshold. If the hash value is greater than M/3, the packet is sent to the first link, otherwise to the second link. A more flexible approach is to associate the outgoing link index with each of the M bins(see Figure4).This indexbased approach requires more memory than the thresholdbased approach(M indexes versus N1 thresholds).On the other hand ,the mapping from the hash value to the outgoing link is simpler with the indexbased approach. It can be done with a direct table look up where as with the thresholdbased approach , the hash value has to be pared with the N1 thresholds. The indexbased approach is more flexible since each of the M bins can be assigned to N outgoing links independently. This can be used to minimize disruption to the existing traffic when load splitting is adjusted, or new links are added or shutdown. In contrast, the thresholdbased approach may cause a significant amount of flows to change their outgoing links. For example suppose that a new link is added to the existing two load balance links. If the load is to be evenly distributed, 1/2 of the traffic flows are reassigned to different outgoing links while only 1/3 of flows are affected if the indexbased approach is used. The outgoing link reassignment may potentially cause significant transient packet misordering to the affected flows. . . 基于哈希模式的負載均衡性能研究 亞特蘭大佐治亞理工學(xué)院計算機學(xué)院， GA303320280 貝爾實驗室，朗訊科技，霍爾姆德爾， NJ 07733 摘要 負載均衡 是一種提高互聯(lián)網(wǎng)性能的關(guān)鍵技術(shù)。有效利用負載均衡 的需要良好的 流量 分配方案。 關(guān)鍵字 — — 負載分享 ，哈希。 為應(yīng)對互聯(lián)網(wǎng)流量的指數(shù)級增長， 并行處理數(shù)據(jù)包的技術(shù)被復(fù)制到了包分析程序，代替了單一的處理引擎 。 我們的研究結(jié)果是通過使用取自一個主要的互聯(lián)網(wǎng)骨干網(wǎng)提供商 的 兩個 主鏈路 的數(shù)據(jù)包 記錄，通過 以下方式獲得模擬的流量分配器的性能。 本文的其余部分安排如下：在第二部分中，我們討論了分流和負載均衡相關(guān)工作。 我們的工作在兩個重要方面不同于 逆 復(fù)用。 在網(wǎng)絡(luò)環(huán)境中，基于 哈希的地址查找 [10]，流識別 [11]和數(shù)據(jù)包 的 解復(fù)用 [12]在過去已經(jīng)提出了。在這個方案中，每個下一跳 被設(shè)計了根據(jù)一個簡單的偽隨機數(shù)函數(shù)分配了帶有流標識符和下一跳標識的權(quán)重 。 在這樣一個系統(tǒng)中，流量分離器從一個高速鏈路中接收到傳入的數(shù)據(jù)包，并將其轉(zhuǎn)發(fā)到的一個速度較低的出 口 鏈 接 。因此，理想的系統(tǒng)應(yīng)該滿足以下任何期間 [T， t]： 轉(zhuǎn)發(fā)出口鏈路 效 率的比例基本上是 分配 的流量負載。假定系統(tǒng)最初是空閑的， 當 一個數(shù)據(jù)包到達。 在 不同 鏈路 中的時間 之間的差別，繁忙鏈路 的 時 間不應(yīng)該超過 在較慢的鏈路 上轉(zhuǎn)發(fā) 最大數(shù)據(jù)包的時間。 一個 TCP 流內(nèi)錯誤的數(shù)據(jù)包順序，可以產(chǎn)生錯誤的擁塞信號，并導(dǎo)致不必要的吞吐量降低 [2][3]。 基于 哈希 處理的分流算法是無狀態(tài)的 易于 計算的， 特別與硬件的協(xié)作。正如我們在本節(jié)開始時已經(jīng)討論的，在一個理想的系統(tǒng)，流量負載應(yīng)該按出口鏈接率分配。 我們定義過工作狀態(tài)空閑時間是當其他鏈路忙時至少有一條鏈路空閑的時間長度 。 目標地址哈希 . . 最簡單的方案是哈希的 IP 目的地址模 塊 傳出鏈接的數(shù)量 N。 互聯(lián)網(wǎng)校驗 網(wǎng)際校驗和算法 RFC791[18]提出的是相對簡單的計算，也是一個不錯的哈希函數(shù)。 其次，直接哈希調(diào)整負荷分布這幾乎是不可能的。一種 方案 需要 N1 個關(guān)鍵字來保持，每個 用于每個輸出鏈路（參見圖 3）。在直接哈希查找的計算與接近 N1