弹性下一跳组

弹性组是一种下一跳组，旨在最大限度地减少在构成下一跳的组成部分和权重发生变化时，流量路由的中断。

弹性哈希组背后的思想最好通过与传统的、使用 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。以这种方式识别为繁忙的桶被视为流量命中了它们。

卸载的桶应标记为“卸载”或“陷阱”。这是通过 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 利用它们来测试该算法。