彈性下一跳組

彈性組是一種下一跳組，旨在最大程度地減少在組構成和組成下一跳權重發生變化時，流路由中斷。

彈性雜湊組背後的思想最好透過與傳統多路徑下一跳組的對比來解釋，傳統多路徑下一跳組使用 RFC 2992 中描述的雜湊閾值演算法。

為了選擇下一跳，雜湊閾值演算法首先為組中的每個下一跳分配一個雜湊範圍，然後透過比較 SKB 雜湊與各個範圍來選擇下一跳。當一個下一跳從組中移除時，範圍會被重新計算，這導致雜湊空間的一部分從一個下一跳重新分配給另一個下一跳。RFC 2992 如此說明

+-------+-------+-------+-------+-------+
|   1   |   2   |   3   |   4   |   5   |
+-------+-+-----+---+---+-----+-+-------+
|    1    |    2    |    4    |    5    |
+---------+---------+---------+---------+

 Before and after deletion of next hop 3
 under the hash-threshold algorithm.

請注意，下一跳 2 如何將部分雜湊空間讓給下一跳 1，以及下一跳 4 讓給下一跳 5。雖然舊的和新的分配通常會有一些重疊，但一些流量流會改變它們解析到的下一跳。

如果多路徑組用於多個伺服器之間的負載均衡，這種雜湊空間重新分配會導致一個問題，即來自單個流的資料包突然到達一個不期望它們的伺服器。這可能導致 TCP 連線被重置。

如果多路徑組用於負載均衡到同一伺服器的可用路徑之間，問題在於沿途不同的延遲和亂序會導致資料包以錯誤的順序到達，從而導致應用程式效能下降。

為了緩解上述流重定向，彈性下一跳組在雜湊空間及其組成下一跳之間插入了另一層間接：一個雜湊表。選擇演算法使用 SKB 雜湊來選擇一個雜湊表桶，然後讀取該桶包含的下一跳，並將流量轉發到那裡。

這種間接帶來了重要特性。在雜湊閾值演算法中，與下一跳關聯的雜湊範圍必須是連續的。有了雜湊表，雜湊表桶和各個下一跳之間的對映是任意的。因此，當一個下一跳被刪除時，包含它的桶會被簡單地重新分配給其他下一跳

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|3|3|3|3|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                 v v v v
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|1|2|4|5|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Before and after deletion of next hop 3
under the resilient hashing algorithm.

當組中下一跳的權重改變時，可以選擇一部分當前未用於轉發流量的桶，並利用這些桶來滿足新的下一跳分配需求，同時保持“忙碌”的桶不變。這樣，已建立的流理想情況下會繼續透過與下一跳組更改前相同的路徑轉發到相同的端點。

演算法

簡而言之，該演算法的工作原理如下。根據其權重和雜湊表中桶的數量，每個下一跳都應分配一定數量的桶。根據原始碼，我們將此數量稱為下一跳的“需求計數”。如果發生可能導致桶分配更改的事件，將更新各個下一跳的需求計數。

桶數量少於其需求計數的下一跳被稱為“欠重”。桶數量多於其需求計數的下一跳被稱為“過重”。如果組中沒有過重（因此也沒有欠重）的下一跳，則稱該組為“平衡”。

每個桶都維護一個上次使用計時器。每當資料包透過一個桶轉發時，該計時器都會更新為當前的 jiffies 值。彈性組的一個屬性是“空閒計時器”，它是指一個桶在不被流量擊中多長時間後才會被認為是“空閒”的。不空閒的桶是忙碌的。

在為下一跳分配需求計數後，會執行一個“維護”演算法。對於桶

  1. 未分配下一跳，或

  2. 其下一跳已被移除，或

  3. 空閒且其下一跳過重，

維護會將桶引用的下一跳更改為某個欠重的下一跳。如果在以這種方式考慮所有桶後，仍然存在欠重的下一跳，則會安排另一次維護執行在未來的時間。

可能沒有足夠的“空閒”桶來滿足所有下一跳的更新需求計數。彈性組的另一個屬性是“不平衡計時器”。此計時器可以設定為 0，在這種情況下，表將保持不平衡狀態，直到出現空閒桶為止，可能永遠不會。如果設定為非零值，該值表示允許表保持不平衡狀態的時間段。

考慮到這一點，我們將上述條件列表更新為再增加一項。因此，桶

  1. 如果其下一跳過重，並且表處於不平衡狀態的時間量超過了不平衡計時器（如果該計時器非零），

... 也會被遷移。

解除安裝和驅動程式反饋

解除安裝彈性組時，在下一跳之間分配桶的演算法仍然在軟體中。驅動程式透過以下三種方式接收下一跳組的更新通知

  • 型別為 NH_NOTIFIER_INFO_TYPE_RES_TABLE 的完整組通知。這僅在首次建立組並填充桶後使用。

  • 型別為 NH_NOTIFIER_INFO_TYPE_RES_BUCKET 的單桶通知，用於通知已建立組內的單個遷移。

  • 預替換通知，NEXTHOP_EVENT_RES_TABLE_PRE_REPLACE。這在替換組之前傳送，是驅動程式在將任何內容提交到硬體之前否決組的一種方式。

一些單桶通知是強制的，如通知中的“force”標誌所示。這些用於例如與桶關聯的下一跳已被移除，並且桶確實必須遷移的情況。

驅動程式可以透過返回錯誤程式碼來覆蓋非強制通知。這樣做的用例是，驅動程式通知硬體應該遷移桶，但硬體發現桶實際上已被流量擊中。

硬體報告桶忙碌的第二種方式是透過 nexthop_res_grp_activity_update() API。以這種方式識別為忙碌的桶被視為已被流量擊中。

解除安裝的桶應標記為“offload”或“trap”。這是透過 nexthop_bucket_set_hw_flags() API 完成的。

用法

為了說明用法，請考慮以下命令

# ip nexthop add id 1 via 192.0.2.2 dev eth0
# ip nexthop add id 2 via 192.0.2.3 dev eth0
# ip nexthop add id 10 group 1/2 type resilient \
        buckets 8 idle_timer 60 unbalanced_timer 300

最後一條命令建立了一個彈性下一跳組。它將有 8 個桶（這是一個異常低的數字，此處僅用於演示目的），每個桶在沒有流量命中它至少 60 秒後將被認為是空閒的，如果表保持不平衡狀態 300 秒，它將被強制恢復平衡。

更改下一跳權重會導致桶分配發生變化

# ip nexthop replace id 10 group 1,3/2 type resilient

這可以透過檢視單個桶來確認

# ip nexthop bucket show id 10
id 10 index 0 idle_time 5.59 nhid 1
id 10 index 1 idle_time 5.59 nhid 1
id 10 index 2 idle_time 8.74 nhid 2
id 10 index 3 idle_time 8.74 nhid 2
id 10 index 4 idle_time 8.74 nhid 1
id 10 index 5 idle_time 8.74 nhid 1
id 10 index 6 idle_time 8.74 nhid 1
id 10 index 7 idle_time 8.74 nhid 1

注意兩個空閒時間較短的桶。這些是在下一跳替換命令後遷移的桶，以滿足下一跳 1 需要分配 6 個桶而不是 4 個的新需求。

Netdevsim

netdevsim 驅動程式實現了彈性組的模擬解除安裝，並暴露了 debugfs 介面，允許將單個桶標記為忙碌。例如，以下命令將下一跳組 10 中的桶 23 標記為活動狀態

# echo 10 23 > /sys/kernel/debug/netdevsim/netdevsim10/fib/nexthop_bucket_activity

此外，另一個 debugfs 介面可用於配置下一次遷移桶的嘗試應失敗

# echo 1 > /sys/kernel/debug/netdevsim/netdevsim10/fib/fail_nexthop_bucket_replace

除了作為示例之外，netdevsim 暴露的介面在自動化測試中很有用，tools/testing/selftests/drivers/net/netdevsim/nexthop.sh 利用它們來測試演算法。