基于可編程數據平面的DLB算法實現

劉熙

（銳捷網絡股份有限公司 福建省福州市 350002）

1 引言

近年來，數據平面可編程技術的發展，為網絡領域的發展注入了新的活力。在高性能轉發領域，支持協議無關的交換架構PISA（Protocol Independent Switch Architecture）的可編程轉發芯片，結合P4（Programming Protocol-Independent Packet Processors）這樣的高級語言，使得網絡擁有者、工程師、架構師及管理員可以自上而下地定義數據包的完整處理流程[1]。程序員通過編程，可以將交換機變為一個架頂交換機(Top-Of-Rack,TOR)、一道防火墻或一個負載平衡器，或者支持新的自動診斷功能和新的擁塞控制算法等[1]。

PISA 架構（如圖1）主要由可編程的報文解析器(PARSER)、可編程的匹配動作單元模塊（MATCH-ACTION UNIT，簡稱MAU）和報文組裝模塊（DEPARSER）構成[1,2,3]。在流水線入口，可編程的報文解析器負責對數據包進行預處理和解析。可編程的匹配動作單元模塊主要用于各種查找表操作，芯片內部包含多級匹配動作單元并以流水線的方式組合而成。每級匹配動作單元內都包含一定數量的哈希資源、SRAM 資源、TCAM 資源和ALU 資源等。哈希資源可以用于實現各自查找表算法，SRAM 資源可以用來實現精確匹配表的存儲與查找，TCAM 資源則可以用來實現模糊匹配表的存儲與查找，ALU 資源可以實現內部的相關控制，具備邏輯與或的運算能力和加減的運算能力，從而實計數(Counter)、流量計(Meter)以及寄存器(Register)的功能。報文組裝模塊則將查表結果作用于報文之上，增加一些新的報文頭部，或刪除一些報文頭部，或修改已有報文頭部中的一些字段，并將處理完成的報文提交給緩存管理模塊入隊，調度模塊則根據選擇的調度算法將報文調度出隊，經過下行流水線處理最終由出口端口轉發給下一跳設備。

圖1：PISA 架構

2 概述

2.1 網絡負載均衡

負載均衡(Load Balance，簡稱LB)，是指將負載（工作任務）進行平衡、分攤到多個操作單元上進行運行，從而協同完成工作任務，達到提高系統的吞吐量、減小響應時間、優化系統資源的效果。而網絡的負載均衡是指對網絡上的負載情況進行平衡分配的一種處理方法。通過采用某些負載均衡算法實現多路徑的選擇，使得各路徑的負載分配均等，從而提高網絡的資源的利用率。

網絡技術中，通常采用等價多鏈路(Equal Cost Multi Path,ECMP)或鏈路聚合(Link Aggregation,LAG)實現負荷分擔和鏈路備份。其中，ECMP 的原理是，為一個目的地址配置多條相同開銷的物理鏈路組成ECMP，發往該目的地址的報文可以通過該ECMP包含的多條物理鏈路進行轉發，若某條物理鏈路出現故障，則可以使用其它物理鏈路代替出現故障的物理鏈路完成報文的轉發；LAG的原理是，將連接到同一網絡設備的多條物理鏈路匯聚成LAG，發往該網絡設備的報文可以通過該LAG 包含的多條物理鏈路進行轉發，若某條物理鏈路出現故障，則可以使用其它物理鏈路代替出現故障的物理鏈路完成報文的轉發。

從ECMP 或LAG 包含的多條物理鏈路中選取一條物理鏈路轉發報文的過程即為負載均衡。目前常用的負載均衡方法是，接收到報文后，基于該報文的目的地址確定該報文的出口為ECMP 或LAG 時，基于該報文的IP 五元組信息（IP 源地址、IP 目的地址、IP 協議號，四層協議源端口、四層協議目的端口）計算該報文的哈希值，將該報文的哈希值與該報文的出口包含的物理出口總數進行取模運算，最后根據取模運算結果，從該報文的出口包含的所有物理出口中選取一個物理出口轉發該報文。

這種基于IP 五元組的哈希值的負載均衡方法，也叫逐流均衡。這種均衡方法，對于同一個流，所有報文都走相同的物理端口，因此數據包的傳輸是保序的，對于TCP 這樣要求嚴格保序的通信協議來說非常適合。但是，可能存在多個數據流的報文的哈希值相同或者多個數據流的報文的哈希值不同但基于哈希值選擇的物理出口相同的問題，從而導致該多個數據流的報文通過同一個物理出口進行轉發處理，進而造成局部物理出口的負載過重。

還有一種符合均衡方法，叫逐包均衡。指采用輪詢方式，將報文在所有等價路徑上輪流發送。這種均衡方式的優點很明顯，所有等價路徑的網絡負載可以實現均等。但是缺點也很明顯，即：不同路徑的網絡時延可能不同，最終可能造成報文序列的亂序，這對像TCP 這樣要求強序傳輸的協議來說是致命的。

如何在報文傳輸保序和網絡負載均衡之間找到一個平衡支點，這就是動態負載均衡（Dynamic Load Balance，簡稱DLB)要解決的問題。

2.2 Flowlet原理

網絡通信中，大多數流量是TCP 流量。TCP 通信采用滑動窗口方式發送，為了性能考慮，報文會根據窗口大小以批量方式發送，因此TCP 報文實際上是以Burst 方式發送出來的。對于每個TCP 流，每次burst 之間存在時間間隙。當這種間隙足夠大的時候，可以進行TCP 流的底層鏈路的切換。此時，舊鏈路上的packet 均已經離開了鏈路或者至少將要離開鏈路，因此切換鏈路將不會造成亂序，不會破壞TCP 的強序要求[4,5]。而這種Burst 發送的多個報文，業界稱之為Flowlet[4,5,6]，意為微小的流。

由于存在burst 和對應的間隙，一個TCP Flow 可以切割為若干個TCP Flowlet，屬于同一個Flowlet 的報文必須選擇相同的鏈路，屬于不同Flowlet 的報文可以選擇走不同的鏈路。如圖2所示。

圖2：Flowlet 示意圖

2.3 DLB均衡算法實現

DLB 技術是一種在滿足TCP 保序傳輸要求的前提下提高網絡負載均衡效果的技術。基于可編程芯片實現的DLB算法，包括兩大模塊：

（1）均衡模塊：利用Flowlet 原理對流量的負載進行動態調整，選擇最優路徑調度新的Flowlet；

（2）監控模塊：在轉發面對鏈路進行負載監控，實時更新最優路徑信息。

DLB算法原理圖如圖3所示，DLB算法的整體處理流程如下：

圖3：DLB算法原理圖

均衡模塊（在報文入口方向）：

（1）DLB 分組：根據報文的源口信息、目的信息（LAG 或者ECMP）等信息進行匹配查找，獲取報文對應的DLB 分組信息，DLB 分組信息包括：

①分組標識(DLB_ID)：分組標識采用數值來表示，比如自然數1,2,3,4 等。不同分組的標識不同。

②分組掩碼(MASK)：包括高位掩碼(HI_MASK)和低位掩碼(LO_MASK)，這兩個掩碼和生成FlowID 有關。高位掩碼用于設定FlowID 的區間，低位掩碼用于設定FlowID 的區間偏移量。不同分組的分組掩碼是不同的。

③Flowlet 老化時間(IDLE_Timeout)：老化時間是一個相對時間戳，可以根據轉發場景需要設置此老化時間的大小。比如100μ 秒。

（2）計算FLOW_ID：

①計算報文的HASH 值。對于IP 報文，一般根據報文的五元組信息，計算出對應的哈希值；對于非IP報文，可以根據其他信息（比如MPLS 報文可以根據MPLS 標簽）計算報文的哈希值。

②根據公式 FLOW_ID = HI_MASK | (HASH & LO_MASK)，先將Hash 值和分組低位掩碼進行按位與運算，然后再和分組高位掩碼進行按位或運算，最終得到報文的FLOW_ID。

（3）Flowlet 老化判斷：

①獲取報文當前的的時間戳Cur_Timestamp；

②使用報文的FLOW_ID 作為索引，從寄存器數組Flowlet_TSTAMP 獲取記錄的上一次轉發報文的時間戳LAST_Timestamp。

③判斷不等式Cur_Timestamp>LAST_Timestamp + IDLE_Timeout 是否成立，如果成立則說明Flowlet 已老化（當前的報文視為新的Flowlet），反之則說明Flowlet 沒有老化（當前的報文視為舊的Flowlet）。

（4）選擇最優路徑：對于新的Flowlet 情況，采用輪詢方式為報文選擇新的路徑。算法如下：

①使用報文的DLB_ID 作為索引，從寄存器數組PREF_PATH_SET 獲取優選路徑集合對應的端口位圖(PREF_PORTMAP)，位圖中非0 的bit 位表示對應的端口為可用物理端口。比如0b10101011，表示物理端口1、2、4、6、8 為可用端口。

②根據DLB_ID，從寄存器數組SN_GEN 獲取一個在一定范圍內遞增且超過范圍則重置的序列號SN。比如SN 可以取值1 ～127，則SN 值超過127 時重新置0。

③根據PREF_PORTMAP 和SN，選擇最優出口。比如，當PREF_PORTMAP 值為0b10101011，SN 值為1 時，選擇第一個物理口；當PREF_PORTMAP 值為0b10101011，SN 值為2 時，選擇第二個物理口。由于SN 值是遞增的，因此為新的Flowlet 分配到的優選出口是依次輪詢分配的。

④當最優路徑不存在時，即PREF_PORTMAP 值為全0，此時從候選路徑集合中基于SN 值選擇端口。候選路徑集合為所有可用的等價成員口集合。

（5）保存轉發路徑：

①對于新的Flowlet 情況，以FLOW_ID 作為索引，將選擇的出口信息更新到寄存器數組Flowlet Path 對應成員。

②對于舊的Flowlet 情況，以FLOW_ID 作為索引，從寄存器數組Flowlet Path 對應成員獲取保存的出口信息。

監控模塊1（在報文的出口方向）

（1）出口測速：

①利用計量器資源，為每個物理端口進行實時測速。比如，采用單桶令牌的計量器，當端口的報文速率超過配置的速率閾值時，計量器執行結果為紅色；當端口的報文速率低于配置的速率閾值時，計量器執行結果為綠色。

②為了使測速結果更穩定，還可以采用多次測量取平均顏色的做法。比如每輪累計統計1000 個報文的計量器顏色總量，當紅色總量(比如600 個）大于綠色總量（比如400 個）時判定平均顏色為紅色。

（2）權值計算和變化確認：

①根據端口的計量器顏色信息和端口的出口隊列深度（可選），調整端口的轉發優先級。比如發現端口的計量器顏色為紅色且出口隊列深度超過配置的閾值時，降低端口的轉發優先級，需要將它從優選路徑中移除。當發現端口的計量器顏色恢復為綠色且出口隊列深度低于配置的閾值時，提高端口的轉發優先級。

②用一組寄存器PORT_PRIORITY 保存端口上一次的權值信息。比較當前的權值信息與寄存器保存的上一次權值信息是否發生變化，如果有變化則更新權值信息，并返回權值變化確認(設置PRIORITY_ACK 為1)。

（3）鏡像反饋：當端口的權值發生變化時，觸發一個用于調整最優路徑的PREF 報文鏡像。

①獲取出端口的對應DLB 的物理成員口位圖，比如第一個物理成員口對應位圖可以表示為0b0000 0001，第二個物理成員口對應的位圖0b0000 0010。

②觸發一個指向回環口的鏡像報文。鏡像報文的頭部封裝這些信息：DLB ID、物理成員口位圖、端口權值。

監控模塊2（在報文的回環口入口方向）：

更新最優路徑：回環口收到PREF 報文鏡像后，從報文中提取DLB ID、物理成員口位圖、端口權值這些信息，更新PREF_PATH_SET 的最優路徑信息。將端口權值低于最優路徑權值的物理成員口對應位圖，從最優路徑的位圖中移除；將端口權值高于或等于最優路徑權值的物理成員口對應位圖，添加到最優路徑的位圖中。

3 結語

借助可編程芯片，我們在數據平面實現了DLB算法，通過均衡模塊和監控模塊的配合，在確保數據流中的報文不會出現亂序的情況下，有效地改善了負載均衡效果，提高了網絡轉發性能。可編程交換芯片作為一種新的技術，為未來網絡的發展注入了新的活力，很多傳統交換芯片無法實現或難以實現的功能和應用可通過可編程交換芯片快速得到實現，極大提升了轉發面功能的迭代更新，加速網絡領域的創新。