【正文】 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. . . 基于哈希模式的負載均衡性能研究 亞特蘭大佐治亞理工學院計算機學院， GA303320280 貝爾實驗室，朗訊科技，霍爾姆德爾， NJ 07733 摘要 負載均衡 是一種提高互聯(lián)網性能的關鍵技術。有效利用負載均衡 的需要良好的 流量 分配方案。我們研究分布在多個 鏈路層 幾個哈希方案的執(zhí)行情況 ， 同時保留流量數(shù)據包的通信順序。雖然在過去已提出 過 基于哈希的 負載均衡 方案， 但 這是首次使用實際 流量記錄 的 結果的 全面研究 分析 。 我們評估 了 五個直接 哈希 方法和一個基于表的哈希方法。我們發(fā) 現(xiàn) 使用五元組的 CRC16 哈希 算法具有 優(yōu)秀 的負載均衡 性能。此外，基于 哈希表的 負載自適應使用 源目 IP 地址 使用異或位移的 達到媲美 CRC16 的性能 ?；诒淼?哈希還可以 根據不同權重分配流量負載 。我們 得出了其他四個方案性能在較差到中等的結論。 關鍵字 — — 負載分享 ，哈希。 引言 負載均衡（也稱為負載分擔）是改善互聯(lián)網的性能和可擴展性的關鍵技術。 例如，許多大型企業(yè)網絡連接到多個互聯(lián)網服務提供商（ ISP），以實現(xiàn)冗余連接和分配流量負載。 在 互聯(lián)網 內部 ，內部骨干往往設計有多個并行的 主鏈路 在 于主要節(jié)點之間 ，以確保高 效 性。通 常情況下，這些 并行 的 主鏈路 被配置為等價路徑負載均衡 進行負載 。 當復前途密集波分復用（ DWDM）技術的部署在未來的 骨干 互聯(lián)網 ，并行的主干鏈路 可能變得更加無處不在。 DWDM 通信中繼線的容量擴展，允許更大數(shù)量的信道在一個單一的光纖通過。 在主要節(jié)點之間的 幾十甚至上百 DWDM通道，負載均衡是利用多個并行 信道的 最好的 要素 。 為應對互聯(lián)網流量的指數(shù)級增長， 并行處理數(shù)據包的技術被復制到了包分析程序，代替了單一的處理引擎 。同樣的技術也可以用來在擴展的 網頁 服務器。流行的 Web 服務器往往 連接了很多的機器和路由器還要分別處理不同機 器的 HTTP 請求 。 對于所有這些例子中， 負載均衡的使用效率取決于在高速多層鏈路下的. . 模式 。此外，由于在互聯(lián)網上的大部分的流量是基于 TCP 的分流方案 [1]，以避免數(shù)據包內 錯誤順序 的 TCP 流，這可能錯誤地觸發(fā)擁塞控制機制，并導致不必要的吞吐量降低 [2][3]。 在本文中，我們提出 和評估 了一 系列 基于哈希的維護每個流的包的順序分流算法。我們認為 五元組是最直接的方法 ， 通過 哈希函數(shù)生成一個 關鍵 值，范圍 為 0， ...， N1， N為外部鏈接的數(shù)目， 我們也考慮基于表的 映射 ， 包括 M個哈希值 ，然后分配 M個值對應的 N個 出站 鏈路 。 基于表 的哈希 比直接哈希表需要更多的狀態(tài) 表示 ，但具有很大的靈活性來支持負荷分布不均和動態(tài)適應。 我們的研究結果是通過使用取自一個主要的互聯(lián)網骨干網提供商 的 兩個 主鏈路 的數(shù)據包 記錄，通過 以下方式獲得模擬的流量分配器的性能。我們發(fā)現(xiàn)， 在兩條主干網上 直接 哈希 目標