【正文】 e 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. . . 基于哈希模式的負(fù)載均衡性能研究 亞特蘭大佐治亞理工學(xué)院計(jì)算機(jī)學(xué)院， GA303320280 貝爾實(shí)驗(yàn)室，朗訊科技，霍爾姆德爾， NJ 07733 摘要 負(fù)載均衡 是一種提高互聯(lián)網(wǎng)性能的關(guān)鍵技術(shù)。我們研究分布在多個(gè) 鏈路層 幾個(gè)哈希方案的執(zhí)行情況 ， 同時(shí)保留流量數(shù)據(jù)包的通信順序。 我們?cè)u(píng)估 了 五個(gè)直接 哈希 方法和一個(gè)基于表的哈希方法。此外，基于 哈希表的 負(fù)載自適應(yīng)使用 源目 IP 地址 使用異或位移的 達(dá)到媲美 CRC16 的性能 。我們 得出了其他四個(gè)方案性能在較差到中等的結(jié)論。 引言 負(fù)載均衡（也稱為負(fù)載分擔(dān)）是改善互聯(lián)網(wǎng)的性能和可擴(kuò)展性的關(guān)鍵技術(shù)。 在 互聯(lián)網(wǎng) 內(nèi)部 ，內(nèi)部骨干往往設(shè)計(jì)有多個(gè)并行的 主鏈路 在 于主要節(jié)點(diǎn)之間 ，以確保高 效 性。 當(dāng)復(fù)前途密集波分復(fù)用（ DWDM）技術(shù)的部署在未來的 骨干 互聯(lián)網(wǎng) ，并行的主干鏈路 可能變得更加無處不在。 在主要節(jié)點(diǎn)之間的 幾十甚至上百 DWDM通道，負(fù)載均衡是利用多個(gè)并行 信道的 最好的 要素 。同樣的技術(shù)也可以用來在擴(kuò)展的 網(wǎng)頁 服務(wù)器。 對(duì)于所有這些例子中， 負(fù)載均衡的使用效率取決于在高速多層鏈路下的. . 模式 。 在本文中，我們提出 和評(píng)估 了一 系列 基于哈希的維護(hù)每個(gè)流的包的順序分流算法。 基于表 的哈希 比直接哈希表需要更多的狀態(tài) 表示 ，但具有很大的靈活性來支持負(fù)荷分布不均和動(dòng)態(tài)適應(yīng)。我們發(fā)現(xiàn)， 在兩條主干網(wǎng)上 直接 哈希 目標(biāo) IP 地址會(huì)導(dǎo)致顯著的不平衡。更復(fù)雜的 16位 CRC 計(jì)算 的五元組（源地址，目的地址，源端口，目的端口，協(xié)議號(hào)） 得到了 優(yōu)秀的負(fù)載均衡性能，保持兩個(gè) 鏈路 非常相似的負(fù)載和隊(duì)列長(zhǎng)度。 以表為基礎(chǔ)的哈希具有另外的優(yōu)點(diǎn)，它可以根據(jù)不相等的權(quán)重分散負(fù)載。我們的研究結(jié)果證實(shí)， 當(dāng)自適應(yīng)時(shí) 基于索引的哈?？梢詼?zhǔn)確地實(shí)現(xiàn)了加權(quán)分配。第三部分描述了一個(gè)理想的流量分配行為，解釋一個(gè)實(shí)際的系統(tǒng)的要求，并且定義了將要使用到評(píng)估各種基于 哈希模式 的 方法 ， 并且定 義了各種基于哈希的模式 的性能 開銷 。 我們的研究成果則在第五部分 ，包括分析跟蹤數(shù)據(jù)（ VA 部分 ）的隨機(jī)性。 二 ． 相關(guān)工作 負(fù)載均衡已被用于在電信網(wǎng)絡(luò)中的逆復(fù)用 [4]。逆復(fù)用的負(fù)載均衡通常是基于輪循分布的數(shù)據(jù)包或字節(jié)數(shù) [6][7]。首先，逆復(fù)用的設(shè)計(jì) 是在點(diǎn)對(duì)點(diǎn)連接上使用 ，其技術(shù)通常不適用 于 網(wǎng)絡(luò)層 的 負(fù)載均衡。 像 負(fù)載均衡的路徑，例如，等價(jià)多路徑，動(dòng)態(tài)發(fā)現(xiàn)的路由協(xié)議，如 OSPF [8]，而不是通過配置。但是，實(shí)施這些額外網(wǎng)絡(luò)負(fù)載均衡機(jī)制，需要一個(gè)新的網(wǎng)絡(luò)協(xié)議。 哈希方法 已廣泛用于索引和搜索 [9]。網(wǎng)絡(luò)負(fù)載均衡使用哈希 已不新奇 。在 OSPF 優(yōu)化的多路徑協(xié)議（ OSPFOMP） [14]， 一系列 通過多條路徑的負(fù)載均衡方法 已 被提及，包括循環(huán) 的使用 每個(gè) 數(shù)據(jù)包 除以在轉(zhuǎn)發(fā)表中可用的下一跳的目標(biāo) 地址 的前綴，再除以流量 得到的 哈希函數(shù)應(yīng)用到 一對(duì)源目 端上 。 在 OSPFOMP 負(fù)載均衡的研究， 都 假定 有 完美的 哈希 [15]。 它適用于基于域名的映射 達(dá)到 負(fù)載均衡 [17]。 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)， 權(quán)重產(chǎn)生 ， 下一跳接收最高的權(quán)重?cái)?shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā) 。 而且 ，沒有對(duì) 這種方案的性能研究 。本文第一次廣泛的全面介紹了基于 哈希方案的 性能研究，使用骨干網(wǎng)真實(shí)的數(shù)據(jù)包。 . . 圖 1中展示的是一個(gè)典型的包括了流量分配和多出口鏈路的例子 。一個(gè)好的負(fù)載均衡系統(tǒng)應(yīng)該能夠 將流量分配到多個(gè) 比例均勻 的 或 預(yù)先定義的出口鏈路 。 我們現(xiàn)在就是要把他們的成果擴(kuò)展到獲取一個(gè)理想的流分配約束 。假設(shè)有N 個(gè)導(dǎo)出鏈接中的負(fù)載平衡系統(tǒng)中，鏈路 i的容量為 Ni。理想的負(fù)載平衡系統(tǒng)以及相應(yīng)的系統(tǒng)應(yīng)該執(zhí)行一個(gè)單一的輸出鏈路的容量∑ Ui。在任何時(shí)候，流量負(fù)荷是完美的平衡，所有 出口 鏈接忙碌或閑置在同一時(shí)間。 保證了工作效率 ，我們的意思是， 當(dāng)?shù)却龜?shù)據(jù)轉(zhuǎn)發(fā)的 時(shí)候 沒有一個(gè)傳出連接處于閑置狀態(tài)。 一個(gè)基本的轉(zhuǎn)發(fā)數(shù)據(jù)包單元時(shí)間是哈希模式下的幾倍 ，分組的負(fù)載均衡系統(tǒng) 工作 不再是出口鏈路的數(shù)量 。例如，假設(shè)一個(gè)負(fù)載均衡系統(tǒng)有兩個(gè)相同容量的 出口鏈路 。 數(shù)據(jù)包被轉(zhuǎn)發(fā)到兩個(gè)輸出鏈路 其中 之一。在此期間， 兩個(gè)出口鏈路中一個(gè)忙于數(shù)據(jù)包的服務(wù)，而另外一個(gè)則 保持空閑。 在一個(gè)分組的系統(tǒng)， 最壞的考慮 是當(dāng)所有出口鏈路處于閑置，當(dāng)時(shí)間 T時(shí)，一個(gè)最大尺寸為 Pmax的數(shù)據(jù)包到達(dá)且沒有更多的數(shù)據(jù)包。因此，在分組系統(tǒng)中，理想的負(fù)載平衡，應(yīng)滿足下面的條件： 在任何時(shí)間間隔 [T,t]中 ， Pmax 是 其中最大包 的 大小。 分流方案對(duì)于互聯(lián)網(wǎng)的負(fù)載均衡應(yīng)滿足一 些基本要求 ： 低開銷。流量拆分算法，應(yīng)該是很簡(jiǎn)單的，最好保持狀態(tài)沒有或很少。 流量分布欠佳會(huì)導(dǎo)致不均勻的鏈路利用率和帶寬損失。 每個(gè)流的排序。因此這是一個(gè)基本的要求分流算法維護(hù)每個(gè)流的數(shù)據(jù)包順序。 讓我們現(xiàn)在應(yīng)用一些接近上述要求的流量分配方法 。開銷成本 低通常是接近最優(yōu)的性能。 這種額外的機(jī)制，將極大地增加了開銷，并且在許多情況下，只 能 工作在點(diǎn)至點(diǎn) 鏈路 。. . 更好的是，如果哈希函數(shù)使用任意的五元組作為輸入的組合，每個(gè)流的順序可以保存 [1]。總的來說，基于哈希的模式符合上述要求并提供最佳的權(quán)衡。 我們現(xiàn)在討論評(píng)估 互聯(lián)網(wǎng)流量分配 的負(fù)載均衡算法基本性能指標(biāo)。 從負(fù)載均衡的角度來看，最重要的性能指標(biāo)是隨著時(shí)間的產(chǎn)生的多個(gè)出站鏈路的字節(jié)分布。 隊(duì)列長(zhǎng)度。 這種負(fù)載波動(dòng)通過緩沖，從而免除外向 鏈路 隊(duì)列長(zhǎng)度反映負(fù)載均衡的累積效應(yīng)。 隊(duì)列長(zhǎng)度度量考慮到用戶的實(shí)際負(fù)荷 分布在在輕負(fù)荷期間遠(yuǎn)遠(yuǎn)低于重負(fù)載期間的差異，一個(gè)良好的流量分配算法不一定每個(gè)時(shí)間段都要有完美的負(fù)載分布，但它應(yīng)該是能夠保持小的隊(duì)列和平衡。 正如我們已經(jīng)討論過， 數(shù)據(jù)包 的負(fù)載均衡系統(tǒng)是非工作 狀態(tài)的 。空閑時(shí)間度量捕獲系統(tǒng)： 更大的非工作狀態(tài)空閑時(shí)間 ， 越有工作狀態(tài)的傾向 ， 所以這是 效率較低的負(fù)載均衡。 直接哈希是一個(gè) 簡(jiǎn)單的 流量分配模式 。 并使用哈希值，選擇輸出鏈路。在本文中，我們考慮以下五個(gè)直接哈希 方法 。 它可以表示為： 在這個(gè)方案中，如果 N= 2k是 我們有效地利用目的地址的最后 k 位作為出站鏈接的索引。 使用異或目標(biāo)地址 處理的哈希函數(shù) 異或 已經(jīng)用在許多的哈希函數(shù) 中 ， 并且在其他程序中表現(xiàn)出了 良好的性能 。此哈希函數(shù)可以表示為： 目的地址數(shù)組中的 Di的第 i個(gè)地址段 。 使用異或折疊源目地址的哈希處理 地址 簡(jiǎn)單的修改以前的哈希函數(shù)，把源地址也包括在計(jì)算之中，異或折疊源目地址，哈希功能可以描述如以下： 其中和是八位的源目 IP地址。 在本文中，我們 實(shí)驗(yàn)其流量分配的性能，我們把五元組當(dāng)做 16 位的英特網(wǎng)校驗(yàn)和 。雖然與上述討論的哈希函數(shù)相比更加復(fù)雜，但是 CRC16 已經(jīng)被成功的應(yīng)用于高速網(wǎng)絡(luò)之中，CRC16 方案中，使用五元組分配流量，應(yīng) CRC16，得到獲取出口鏈路的模型，哈希函數(shù)可以描述如下： . . 的哈希 直接哈希雖然很簡(jiǎn)單，它也有一定的局限性。然而，它并不總是希望分發(fā)的流量負(fù)荷均勻。 這個(gè)機(jī)構(gòu)可能希望按 2： 1的比例分配流量?；诒淼墓７椒?，下面我們將討論解決通過分離分流和負(fù)載分配這兩個(gè)問題。通過改變 出口鏈路對(duì)應(yīng)的鍵的分布 ，人們可以在一個(gè)預(yù)先定義的比例分配流量。通常情況下， M是大于 N的一個(gè)或兩個(gè)數(shù)量級(jí)，從而可以分 割加載在一個(gè)相當(dāng)精細(xì)的粒度。 有兩種基本 的 基于表的 實(shí)施方案 。 用 M個(gè) 關(guān)鍵字來劃分成 N 個(gè)分區(qū)， 當(dāng)一個(gè)數(shù)據(jù)包到達(dá)時(shí)，流量分配器計(jì)算哈希和對(duì) N1個(gè)關(guān)鍵字的哈希值進(jìn)行比較，以確定即將 使用 的 出口 鏈接。我們可以簡(jiǎn)單地設(shè)定關(guān)鍵字 為 M / 3。如果哈希值是大于 M / 3，該數(shù)據(jù)包被發(fā)送到第 一 條鏈路 ，否則第二 條鏈路。另一方面，使用引索的方式哈希值與出口鏈路的映射關(guān)系更加的簡(jiǎn)單了。 基于引索的方式更加的靈活，因?yàn)?M個(gè)鍵（哈希值）被獨(dú)立的分配給了N 個(gè)出口鏈路，這樣可以當(dāng)流量調(diào)整，建立新連接或關(guān)機(jī)時(shí)最小化對(duì)現(xiàn)存流量負(fù)載的干擾。. . 例如，假設(shè)一條新鏈接被添加到 已存在的兩條負(fù)載均衡鏈路上。