【正文】 es, effective use of load balancing requires good schemes for splitting traffic over multiple links. In addition, since the majority of the traffic on the Inter is TCPbased [1], traffic splitting schemes need to avoid packet misordering within a TCP ?ow, which can falsely trigger congestion control mechanisms and cause unnecessary throughput degradation [2], [3]. In this paper, we propose and evaluate a class of hashing based traffic splitting algorithms which preserve per?ow packet ordering. We consider five hash functions that are “direct,”meaning that the hash function produces a value in the range of 0...N1, where N is the number of outgoing links. We also consider a tablebased generalization that involves hashing to M bins, then assigning the M bins to the N outgoing links. Table based hashing requires more state than direct hashing, but has the flexibility to support unequal load distribution and dynamic adaptation. Our results are obtained by simulating the performance of a traf?c splitter, using packet traces taken from two trunks of a major Inter backbone provider. We ?nd that direct hashing with the destination IP address causes signi?cant imbalance across two links. Using the Inter checksum or the exclusive OR of both the source IP address and destination IP address improves the performance considerably, though moderate imbalance persists. The more putationally plex 16bit CRC of the ?vetuple (source address, destination address, source port,destination port and . . protocol id) gives excellent load balancing performance, keeping the load and queue lengths very similar on two links. Equally good load balancing can be achieved using tablebased hashing with adaptation, which requires less putation than the CRC but necessitates monitoring the link loads and storing (and adjusting) the mapping from table bins to links. Tablebased hashing has the additional advantage that it can distribute the load according to unequal weights. Further, an indexbased version of this scheme can alter the weight distribution with minimal disruption to existing ?ows . Our results con?rm that the indexbased hashing can accurately achieve a weighted distribution when adaptation is also used. The rest of this paper is anized as follows. In Section II we discuss related work in traf?c splitting and load balancing. Section III describes the behavior of an ideal traf?c splitter, explains the requirements for a practical system, and de?nes the performance metrics that will be used to assess various hashingbased schemes. The set of schemes that we consider are described in Section IV. The results of our study are described in Section V, and include analysis of the randomness inherent in the trace data (Section VA). We conclude and mention areas for future work in Section VI. II. RELATED WORK Load balancing has been used in telemunication works in the form of inverse multiplexing [4]. Inverse multiplexing allows service providers to offer wideband channels by bining multiple narrowband 56 kbps and 64 kbps trunks [5]. The load balancing in inverse multiplexing is typically based on round robin distribution of packets or bytes [6], [7]. Our work differs from inverse multiplexing in two important dimensions. First, inverse multiplexing is designed for use over pointtopoint links。 我們?cè)u(píng)估 了 五個(gè)直接 哈希 方法和一個(gè)基于表的哈希方法。 在 互聯(lián)網(wǎng) 內(nèi)部 ，內(nèi)部骨干往往設(shè)計(jì)有多個(gè)并行的 主鏈路 在 于主要節(jié)點(diǎn)之間 ，以確保高 效 性。 對(duì)于所有這些例子中， 負(fù)載均衡的使用效率取決于在高速多層鏈路下的. . 模式 。更復(fù)雜的 16位 CRC 計(jì)算 的五元組（源地址，目的地址，源端口，目的端口，協(xié)議號(hào)） 得到了 優(yōu)秀的負(fù)載均衡性能，保持兩個(gè) 鏈路 非常相似的負(fù)載和隊(duì)列長(zhǎng)度。 我們的研究成果則在第五部分 ，包括分析跟蹤數(shù)據(jù)（ VA 部分 ）的隨機(jī)性。 像 負(fù)載均衡的路徑，例如，等價(jià)多路徑，動(dòng)態(tài)發(fā)現(xiàn)的路由協(xié)議，如 OSPF [8]，而不是通過(guò)配置。在 OSPF 優(yōu)化的多路徑協(xié)議（ OSPFOMP） [14]， 一系列 通過(guò)多條路徑的負(fù)載均衡方法 已 被提及，包括循環(huán) 的使用 每個(gè) 數(shù)據(jù)包 除以在轉(zhuǎn)發(fā)表中可用的下一跳的目標(biāo) 地址 的前綴，再除以流量 得到的 哈希函數(shù)應(yīng)用到 一對(duì)源目 端上 。 而且 ，沒(méi)有對(duì) 這種方案的性能研究 。 我們現(xiàn)在就是要把他們的成果擴(kuò)展到獲取一個(gè)理想的流分配約束 。 保證了工作效率 ，我們的意思是， 當(dāng)?shù)却龜?shù)據(jù)轉(zhuǎn)發(fā)的 時(shí)候 沒(méi)有一個(gè)傳出連接處于閑置狀態(tài)。在此期間， 兩個(gè)出口鏈路中一個(gè)忙于數(shù)據(jù)包的服務(wù)，而另外一個(gè)則 保持空閑。流量拆分算法，應(yīng)該是很簡(jiǎn)單的，最好保持狀態(tài)沒(méi)有或很少。 讓我們現(xiàn)在應(yīng)用一些接近上述要求的流量分配方法 ?？偟膩?lái)說(shuō)，基于哈希的模式符合上述要求并提供最佳的權(quán)衡。 這種負(fù)載波動(dòng)通過(guò)緩沖，從而免除外向 鏈路 隊(duì)列長(zhǎng)度反映負(fù)載均衡的累積效應(yīng)。 直接哈希是一個(gè) 簡(jiǎn)單的 流量分配模式 。 使用異或目標(biāo)地址 處理的哈希函數(shù) 異或 已經(jīng)用在許多的哈希函數(shù) 中 ， 并且在其他程序中表現(xiàn)出了 良好的性能 。雖然與上述討論的哈希函數(shù)相比更加復(fù)雜，但是 CRC16 已經(jīng)被成功的應(yīng)用于高速網(wǎng)絡(luò)之中，CRC16 方案中，使用五元組分配流量，應(yīng) CRC16，得到獲取出口鏈路的模型，哈希函數(shù)可以描述如下： . . 的哈希 直接哈希雖然很簡(jiǎn)單，它也有一定的局限性。通過(guò)改變 出口鏈路對(duì)應(yīng)的鍵的分布 ，人們可以在一個(gè)預(yù)先定義的比例分配流量。我們可以簡(jiǎn)單地設(shè)定關(guān)鍵字 為 M / 3。. . 例如，假設(shè)一條新鏈接被添加到 已存在的兩條負(fù)載均衡鏈路上。另一方面，使用引索的方式哈希值與出口鏈路的映射關(guān)系更加的簡(jiǎn)單了。 有兩種基本 的 基于表的 實(shí)施方案 。 這個(gè)機(jī)構(gòu)可能希望按 2： 1的比例分配流量。 使用異或折疊源目地址的哈希處理 地址 簡(jiǎn)單的修改以前的哈希函數(shù)，把源地址也包括在計(jì)算之中，異或折疊源目地址，哈希功能可以描述如以下： 其中和是八位的源目 IP地址。在本文中，我們考慮以下五個(gè)直接哈希 方法 。 正如我們已經(jīng)討論過(guò)， 數(shù)據(jù)包 的負(fù)載均衡系統(tǒng)是非工作 狀態(tài)的 。 從負(fù)載均衡的角度來(lái)看，最重要的性能指標(biāo)是隨著時(shí)間的產(chǎn)生的多個(gè)出站鏈路的字節(jié)分布。 這種額外的機(jī)制，將極大地增加了開(kāi)銷，并且在許多情況下，只 能 工作在點(diǎn)至點(diǎn) 鏈路 。 每個(gè)流的排序。因此，在分組系統(tǒng)中，理想的負(fù)載平衡，應(yīng)滿足下面的條件： 在任何時(shí)間間隔 [T,t]中 ， Pmax 是 其中最大包 的 大小。例如，假設(shè)一個(gè)負(fù)載均衡系統(tǒng)有兩個(gè)相同容量的 出口鏈路 。理想的負(fù)載平衡系統(tǒng)以及相應(yīng)的系統(tǒng)應(yīng)該執(zhí)行一個(gè)單一的輸出鏈路的容量∑ Ui。 . . 圖 1中展示的是一個(gè)典型的包括了流量分配和多出口鏈路的例子 。 它適用于基于域名的映射 達(dá)到 負(fù)載均衡 [17]。 哈希方法 已廣泛用于索引和搜索 [9]。逆復(fù)用的負(fù)載均衡通常是基于輪循分布的數(shù)據(jù)包或字節(jié)數(shù) [6][7]。我們的研究結(jié)果證實(shí)， 當(dāng)自適應(yīng)時(shí) 基于索引的哈?？梢詼?zhǔn)確地實(shí)現(xiàn)了加權(quán)分配。 基于表 的哈希 比直接哈希表需要更多的狀態(tài) 表示 ，但具有很大的靈活性來(lái)支持負(fù)荷分布不均和動(dòng)態(tài)適應(yīng)。 在主要節(jié)點(diǎn)之間的 幾十甚至上百 DWDM通道，負(fù)載均衡是利用多個(gè)并行 信道的 最好的 要素 。我們 得出了其他四個(gè)方案性能在較差到中等的結(jié)論。 there is no bandwidth lost because of load balancing. By workconserving, we mean no one outgoing link is idle while there is data waiting to be forwarded. Ideal load balancing is obviously impractical in a real work system. As the basic unit of forwarding is at least a single approximately times as expensive as a hashingbased scheme packet, a packetized load balancing system is no longer work where is the number of outgoing links. Again , no performance conserving. For example, suppose that a load balancing systems has two outgoing links of the same capacity. Assume that the system is initially idle, then a single packet arrives. The packet is forwarded to one of the two outgoing link. Note that the packet is