【正文】 . . 例如，假設(shè)一條新鏈接被添加到 已存在的兩條負(fù)載均衡鏈路上。另一方面，使用引索的方式哈希值與出口鏈路的映射關(guān)系更加的簡單了。我們可以簡單地設(shè)定關(guān)鍵字 為 M / 3。 有兩種基本 的 基于表的 實施方案 。通過改變 出口鏈路對應(yīng)的鍵的分布 ，人們可以在一個預(yù)先定義的比例分配流量。 這個機(jī)構(gòu)可能希望按 2： 1的比例分配流量。雖然與上述討論的哈希函數(shù)相比更加復(fù)雜，但是 CRC16 已經(jīng)被成功的應(yīng)用于高速網(wǎng)絡(luò)之中，CRC16 方案中，使用五元組分配流量，應(yīng) CRC16，得到獲取出口鏈路的模型，哈希函數(shù)可以描述如下： . . 的哈希 直接哈希雖然很簡單，它也有一定的局限性。 使用異或折疊源目地址的哈希處理 地址 簡單的修改以前的哈希函數(shù)，把源地址也包括在計算之中，異或折疊源目地址，哈希功能可以描述如以下： 其中和是八位的源目 IP地址。 使用異或目標(biāo)地址 處理的哈希函數(shù) 異或 已經(jīng)用在許多的哈希函數(shù) 中 ， 并且在其他程序中表現(xiàn)出了 良好的性能 。在本文中，我們考慮以下五個直接哈希 方法 。 直接哈希是一個 簡單的 流量分配模式 。 正如我們已經(jīng)討論過， 數(shù)據(jù)包 的負(fù)載均衡系統(tǒng)是非工作 狀態(tài)的 。 這種負(fù)載波動通過緩沖，從而免除外向 鏈路 隊列長度反映負(fù)載均衡的累積效應(yīng)。 從負(fù)載均衡的角度來看，最重要的性能指標(biāo)是隨著時間的產(chǎn)生的多個出站鏈路的字節(jié)分布?？偟膩碚f，基于哈希的模式符合上述要求并提供最佳的權(quán)衡。 這種額外的機(jī)制，將極大地增加了開銷，并且在許多情況下，只 能 工作在點至點 鏈路 。 讓我們現(xiàn)在應(yīng)用一些接近上述要求的流量分配方法 。 每個流的排序。流量拆分算法，應(yīng)該是很簡單的，最好保持狀態(tài)沒有或很少。因此，在分組系統(tǒng)中，理想的負(fù)載平衡，應(yīng)滿足下面的條件： 在任何時間間隔 [T,t]中 ， Pmax 是 其中最大包 的 大小。在此期間， 兩個出口鏈路中一個忙于數(shù)據(jù)包的服務(wù)，而另外一個則 保持空閑。例如，假設(shè)一個負(fù)載均衡系統(tǒng)有兩個相同容量的 出口鏈路 。 保證了工作效率 ，我們的意思是， 當(dāng)?shù)却龜?shù)據(jù)轉(zhuǎn)發(fā)的 時候 沒有一個傳出連接處于閑置狀態(tài)。理想的負(fù)載平衡系統(tǒng)以及相應(yīng)的系統(tǒng)應(yīng)該執(zhí)行一個單一的輸出鏈路的容量∑ Ui。 我們現(xiàn)在就是要把他們的成果擴(kuò)展到獲取一個理想的流分配約束 。 . . 圖 1中展示的是一個典型的包括了流量分配和多出口鏈路的例子 。 而且 ，沒有對 這種方案的性能研究 。 它適用于基于域名的映射 達(dá)到 負(fù)載均衡 [17]。在 OSPF 優(yōu)化的多路徑協(xié)議（ OSPFOMP） [14]， 一系列 通過多條路徑的負(fù)載均衡方法 已 被提及，包括循環(huán) 的使用 每個 數(shù)據(jù)包 除以在轉(zhuǎn)發(fā)表中可用的下一跳的目標(biāo) 地址 的前綴，再除以流量 得到的 哈希函數(shù)應(yīng)用到 一對源目 端上 。 哈希方法 已廣泛用于索引和搜索 [9]。 像 負(fù)載均衡的路徑，例如，等價多路徑，動態(tài)發(fā)現(xiàn)的路由協(xié)議，如 OSPF [8]，而不是通過配置。逆復(fù)用的負(fù)載均衡通常是基于輪循分布的數(shù)據(jù)包或字節(jié)數(shù) [6][7]。 我們的研究成果則在第五部分 ，包括分析跟蹤數(shù)據(jù)（ VA 部分 ）的隨機(jī)性。我們的研究結(jié)果證實， 當(dāng)自適應(yīng)時 基于索引的哈?？梢詼?zhǔn)確地實現(xiàn)了加權(quán)分配。更復(fù)雜的 16位 CRC 計算 的五元組（源地址，目的地址，源端口，目的端口，協(xié)議號） 得到了 優(yōu)秀的負(fù)載均衡性能，保持兩個 鏈路 非常相似的負(fù)載和隊列長度。 基于表 的哈希 比直接哈希表需要更多的狀態(tài) 表示 ，但具有很大的靈活性來支持負(fù)荷分布不均和動態(tài)適應(yīng)。 對于所有這些例子中， 負(fù)載均衡的使用效率取決于在高速多層鏈路下的. . 模式 。 在主要節(jié)點之間的 幾十甚至上百 DWDM通道，負(fù)載均衡是利用多個并行 信道的 最好的 要素 。 在 互聯(lián)網(wǎng) 內(nèi)部 ，內(nèi)部骨干往往設(shè)計有多個并行的 主鏈路 在 于主要節(jié)點之間 ，以確保高 效 性。我們 得出了其他四個方案性能在較差到中等的結(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 serviced with half of the total bandwidth available, thus it will take twice the amount of time to transmit pared with an ideal system. During this period, one of two outgoing links is busy servicing the packet while the other link remains idle. In a practical system, the traf?c splitter may send several packets in a row to the same outgoing link, and thus increase the loss of bandwidth. In a packetized system, consider the worst case that all out going links have been idle since time T when a packet of maximum size Pmax arrives and no more packets are ing until the packet is served. Assume the packet is forwarded onto link i. During the service period, Equation 1 no longer holds because , where C is a fraction of the packet that has been serviced during the period. Therefore, in a packetized system, the ideal load balancing should satisfy the following: over any interval [T,t] , where Pmax is the maximum size of packet. That is, the difference between the time link i is busy and the time link j is busy should be no more than the time to send a largest packet over the slower link. B. Requirements There are a number of basic requirements that traf?c splitting schemes should meet for Inter load balancing: Low Overhead . Traf?c splitting is executed for every packet in the packet forwarding path, thus the perpacket overhead it introduces is a major concern. Traf?c . . splitting algorithms should be very simple and preferably keep no or little state. High Ef?ciency. Poor traf?c distribution will result in uneven link utilization and loss of bandwidth. A traf?c splitter should try to distribute traf?c as close as possible to the reference model. High Ef?ciency. Poor traf?c distribution will result in uneven link utilization and loss of bandwidth. A traf?c splitter should try to distribute traf?c as close as possible to the reference model. PerFlow Ordering. Packet misordering within a TCP ?ow can produce false congestion signals and cause unnecessary throughput degradation [2], [3]. It is therefore an essential requirement that the traffic splitting algorithms maintain perflow packet ordering. This has to be achieved without requiring a new protocol layer. Let us now apply the above requirements to some of the possible traffic splitting approaches. Take packetbypacket round robin or some form of fair queuing for example. The overheads are low and the performance is typically close to optimal. However, per?ow ordering cannot be guaranteed unless additional mechanisms, such as sequence numbers or state keeping, are added. Such additional mechanisms would increase the overhead drastically, and in many cases, only work over pointtopoint links. Hashingbased traf?c splitting algorithms are stateless and fairly easy to pute, particularly with hardware assistance. What is more, if the hash functions use any bination of the ?vetuple as input, perflow ordering can be preserved 1. As we will show later in this paper, many of the hashingbased schemes perform well. Overall, hashingbased schemes meet the above requirements and offer the best tradeoff. This is true because all packets within the same TCP ?ow have the same ?vetuple, thus the output of the hash function with the ?vetuple as input should always be the same. C. Performance Metrics We now discuss t