Resilient Next-hop Groups

연속 hash range 방식의 문제와 bucket 간접층

Resilient next-hop group은 구성원 next hop이나 가중치가 바뀔 때 기존 flow routing의 중단을 최소화하는 multipath group입니다. 기존 그룹은 RFC 2992의 hash-threshold 알고리즘을 사용합니다.

Hash-threshold 방식은 각 next hop에 연속된 hash 범위를 배정하고 SKB hash가 들어가는 범위로 대상을 선택합니다. next hop 3을 제거하면 모든 범위를 다시 계산하므로 next hop 2가 일부 공간을 1에, 4가 일부 공간을 5에 넘기는 식으로 삭제 대상과 무관한 flow까지 다른 next hop으로 이동할 수 있습니다.

여러 서버에 load balancing하는 경우 한 flow의 패킷이 갑자기 상태를 모르는 서버로 가서 TCP connection이 reset될 수 있습니다. 같은 서버로 가는 여러 경로를 고르는 경우에도 latency 차이와 reordering 때문에 패킷 순서가 바뀌어 application 성능이 떨어집니다.

Resilient group은 hash 공간과 next hop 사이에 hash table bucket 층을 둡니다. SKB hash로 bucket을 고른 뒤 그 bucket이 가리키는 next hop으로 보냅니다. Bucket과 next hop의 대응은 임의적이므로 next hop을 지울 때 그 next hop을 담은 bucket만 다른 대상으로 재배정합니다.

가중치가 바뀔 때도 현재 traffic을 전달하지 않는 bucket만 골라 새 분포를 만족할 수 있습니다. busy bucket을 그대로 두면 이미 성립한 flow가 그룹 변경 전과 같은 endpoint와 path를 계속 사용할 가능성이 높아집니다.

.. SPDX-License-Identifier: GPL-2.0

=========================
Resilient Next-hop Groups
=========================

Resilient groups are a type of next-hop group that is aimed at minimizing
disruption in flow routing across changes to the group composition and
weights of constituent next hops.

The idea behind resilient hashing groups is best explained in contrast to
the legacy multipath next-hop group, which uses the hash-threshold
algorithm, described in RFC 2992.

To select a next hop, hash-threshold algorithm first assigns a range of
hashes to each next hop in the group, and then selects the next hop by
comparing the SKB hash with the individual ranges. When a next hop is
removed from the group, the ranges are recomputed, which leads to
reassignment of parts of hash space from one next hop to another. RFC 2992
illustrates it thus::

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

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

Note how next hop 2 gave up part of the hash space in favor of next hop 1,
and 4 in favor of 5. While there will usually be some overlap between the
previous and the new distribution, some traffic flows change the next hop
that they resolve to.

If a multipath group is used for load-balancing between multiple servers,
this hash space reassignment causes an issue that packets from a single
flow suddenly end up arriving at a server that does not expect them. This
can result in TCP connections being reset.

If a multipath group is used for load-balancing among available paths to
the same server, the issue is that different latencies and reordering along
the way causes the packets to arrive in the wrong order, resulting in
degraded application performance.

To mitigate the above-mentioned flow redirection, resilient next-hop groups
insert another layer of indirection between the hash space and its
constituent next hops: a hash table. The selection algorithm uses SKB hash
to choose a hash table bucket, then reads the next hop that this bucket
contains, and forwards traffic there.

This indirection brings an important feature. In the hash-threshold
algorithm, the range of hashes associated with a next hop must be
continuous. With a hash table, mapping between the hash table buckets and
the individual next hops is arbitrary. Therefore when a next hop is deleted
the buckets that held it are simply reassigned to other next hops::

            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |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.

When weights of next hops in a group are altered, it may be possible to
choose a subset of buckets that are currently not used for forwarding
traffic, and use those to satisfy the new next-hop distribution demands,
keeping the "busy" buckets intact. This way, established flows are ideally
kept being forwarded to the same endpoints through the same paths as before
the next-hop group change.

Algorithm

wants count, idle과 unbalanced timer

각 next hop은 가중치와 전체 hash table bucket 수에 따라 받을 bucket 수를 가집니다. 소스 코드 용어로 이를 `wants count`라고 하며, bucket 배정을 바꿀 수 있는 사건이 생기면 각 next hop의 wants count를 갱신합니다.

현재 bucket 수가 wants count보다 적으면 underweight, 많으면 overweight입니다. Overweight와 underweight가 모두 없으면 그룹이 balanced 상태입니다.

각 bucket은 마지막 사용 시각을 jiffies로 기록합니다. Group의 `idle timer` 동안 traffic이 닿지 않은 bucket은 idle, 그렇지 않은 bucket은 busy입니다.

Wants count를 계산한 뒤 upkeep이 실행됩니다. next hop이 배정되지 않은 bucket, 가리키던 next hop이 제거된 bucket, idle이면서 overweight next hop을 가리키는 bucket을 underweight next hop으로 옮깁니다. 모든 bucket을 검사한 뒤에도 underweight가 남으면 다음 upkeep을 예약합니다.

새 분포를 만족할 idle bucket이 부족할 수 있습니다. `unbalanced timer`가 0이면 idle bucket이 생길 때까지, 경우에 따라 영원히 불균형 상태로 둡니다. 0이 아니면 table이 불균형으로 남아 있어도 되는 최대 시간입니다. 이 시간이 지나면 busy이더라도 overweight next hop의 bucket을 옮겨 강제로 균형을 맞춥니다.

---------

In a nutshell, the algorithm works as follows. Each next hop deserves a
certain number of buckets, according to its weight and the number of
buckets in the hash table. In accordance with the source code, we will call
this number a "wants count" of a next hop. In case of an event that might
cause bucket allocation change, the wants counts for individual next hops
are updated.

Next hops that have fewer buckets than their wants count, are called
"underweight". Those that have more are "overweight". If there are no
overweight (and therefore no underweight) next hops in the group, it is
said to be "balanced".

Each bucket maintains a last-used timer. Every time a packet is forwarded
through a bucket, this timer is updated to current jiffies value. One
attribute of a resilient group is then the "idle timer", which is the
amount of time that a bucket must not be hit by traffic in order for it to
be considered "idle". Buckets that are not idle are busy.

After assigning wants counts to next hops, an "upkeep" algorithm runs. For
buckets:

1) that have no assigned next hop, or
2) whose next hop has been removed, or
3) that are idle and their next hop is overweight,

upkeep changes the next hop that the bucket references to one of the
underweight next hops. If, after considering all buckets in this manner,
there are still underweight next hops, another upkeep run is scheduled to a
future time.

There may not be enough "idle" buckets to satisfy the updated wants counts
of all next hops. Another attribute of a resilient group is the "unbalanced
timer". This timer can be set to 0, in which case the table will stay out
of balance until idle buckets do appear, possibly never. If set to a
non-zero value, the value represents the period of time that the table is
permitted to stay out of balance.

With this in mind, we update the above list of conditions with one more
item. Thus buckets:

4) whose next hop is overweight, and the amount of time that the table has
   been out of balance exceeds the unbalanced timer, if that is non-zero,

\... are migrated as well.

Offloading & Driver Feedback

하드웨어 offload와 driver feedback

Resilient group을 하드웨어에 offload해도 bucket 분배 알고리즘은 소프트웨어에서 실행됩니다. 그룹 생성 직후 첫 분포는 `NH_NOTIFIER_INFO_TYPE_RES_TABLE` 전체 그룹 알림으로, 이미 만들어진 그룹의 개별 이동은 `NH_NOTIFIER_INFO_TYPE_RES_BUCKET` 단일 bucket 알림으로 전달됩니다.

그룹 교체 전에 `NEXTHOP_EVENT_RES_TABLE_PRE_REPLACE`를 보내 드라이버가 하드웨어 반영 전에 그룹을 거부할 수 있게 합니다. Next hop이 제거되어 반드시 이동해야 하는 경우처럼 일부 단일 bucket 알림에는 `force` flag가 붙습니다.

강제가 아닌 알림은 드라이버가 오류를 반환하여 취소할 수 있습니다. 예를 들어 소프트웨어가 이동을 요청했지만 하드웨어가 해당 bucket에 최근 traffic이 있었다고 발견한 경우입니다. 하드웨어는 `nexthop_res_grp_activity_update()`로 busy bucket을 보고할 수도 있으며, 이 bucket은 실제 traffic이 닿은 것처럼 처리됩니다.

Offload한 bucket은 `nexthop_bucket_set_hw_flags()`를 사용해 `offload` 또는 `trap` flag를 표시해야 합니다.

----------------------------

When offloading resilient groups, the algorithm that distributes buckets
among next hops is still the one in SW. Drivers are notified of updates to
next hop groups in the following three ways:

- Full group notification with the type
  ``NH_NOTIFIER_INFO_TYPE_RES_TABLE``. This is used just after the group is
  created and buckets populated for the first time.

- Single-bucket notifications of the type
  ``NH_NOTIFIER_INFO_TYPE_RES_BUCKET``, which is used for notifications of
  individual migrations within an already-established group.

- Pre-replace notification, ``NEXTHOP_EVENT_RES_TABLE_PRE_REPLACE``. This
  is sent before the group is replaced, and is a way for the driver to veto
  the group before committing anything to the HW.

Some single-bucket notifications are forced, as indicated by the "force"
flag in the notification. Those are used for the cases where e.g. the next
hop associated with the bucket was removed, and the bucket really must be
migrated.

Non-forced notifications can be overridden by the driver by returning an
error code. The use case for this is that the driver notifies the HW that a
bucket should be migrated, but the HW discovers that the bucket has in fact
been hit by traffic.

A second way for the HW to report that a bucket is busy is through the
``nexthop_res_grp_activity_update()`` API. The buckets identified this way
as busy are treated as if traffic hit them.

Offloaded buckets should be flagged as either "offload" or "trap". This is
done through the ``nexthop_bucket_set_hw_flags()`` API.

Netlink UAPI

Netlink UAPI 개요

Resilient group과 bucket은 기존 next-hop netlink message에 resilient 전용 중첩 속성을 더해 구성·조회합니다. 다음 절은 group 교체, group 조회, 단일 bucket 조회와 dump의 메시지 및 필터를 구분합니다.

------------

Resilient Group Replacement

Resilient group 생성과 교체

다른 multipath group과 마찬가지로 `RTM_NEWNEXTHOP`으로 구성합니다. `NHA_GROUP_TYPE`은 `NEXTHOP_GRP_TYPE_RES`여야 하고 `NHA_RES_GROUP` 중첩 속성에 resilient 전용 값을 넣습니다.

`NHA_RES_GROUP_BUCKETS`는 hash table의 bucket 수, `NHA_RES_GROUP_IDLE_TIMER`는 `clock_t` 단위 idle timer, `NHA_RES_GROUP_UNBALANCED_TIMER`는 `clock_t` 단위 unbalanced timer입니다.

^^^^^^^^^^^^^^^^^^^^^^^^^^^

Resilient groups are configured using the ``RTM_NEWNEXTHOP`` message in the
same manner as other multipath groups. The following changes apply to the
attributes passed in the netlink message:

  =================== =========================================================
  ``NHA_GROUP_TYPE``  Should be ``NEXTHOP_GRP_TYPE_RES`` for resilient group.
  ``NHA_RES_GROUP``   A nest that contains attributes specific to resilient
                      groups.
  =================== =========================================================

``NHA_RES_GROUP`` payload:

  =================================== =========================================
  ``NHA_RES_GROUP_BUCKETS``           Number of buckets in the hash table.
  ``NHA_RES_GROUP_IDLE_TIMER``        Idle timer in units of clock_t.
  ``NHA_RES_GROUP_UNBALANCED_TIMER``  Unbalanced timer in units of clock_t.
  =================================== =========================================

Next Hop Get

Next-hop group 조회

Resilient next-hop group 조회는 다른 next hop과 동일하게 `RTM_GETNEXTHOP`을 사용합니다. 응답 속성도 교체 속성과 같지만 `NHA_RES_GROUP` payload에 `NHA_RES_GROUP_UNBALANCED_TIME`이 추가되어 group이 얼마나 오래 불균형이었는지 `clock_t` 단위로 알려 줍니다.

^^^^^^^^^^^^

Requests to get resilient next-hop groups use the ``RTM_GETNEXTHOP``
message in exactly the same way as other next hop get requests. The
response attributes match the replacement attributes cited above, except
``NHA_RES_GROUP`` payload will include the following attribute:

  =================================== =========================================
  ``NHA_RES_GROUP_UNBALANCED_TIME``   How long has the resilient group been out
                                      of balance, in units of clock_t.
  =================================== =========================================

Bucket Get

단일 bucket 조회

`NLM_F_DUMP` 없이 `RTM_GETNEXTHOPBUCKET`을 보내면 하나의 bucket을 요청합니다. `NHA_ID`는 bucket이 속한 next-hop group ID이고 `NHA_RES_BUCKET`은 bucket 전용 속성의 중첩 영역입니다. 그 안의 `NHA_RES_BUCKET_INDEX`로 resilient table의 bucket index를 지정합니다.

^^^^^^^^^^

The message ``RTM_GETNEXTHOPBUCKET`` without the ``NLM_F_DUMP`` flag is
used to request a single bucket. The attributes recognized at get requests
are:

  =================== =========================================================
  ``NHA_ID``          ID of the next-hop group that the bucket belongs to.
  ``NHA_RES_BUCKET``  A nest that contains attributes specific to bucket.
  =================== =========================================================

``NHA_RES_BUCKET`` payload:

  ======================== ====================================================
  ``NHA_RES_BUCKET_INDEX`` Index of bucket in the resilient table.
  ======================== ====================================================

Bucket Dumps

Bucket dump 필터

`NLM_F_DUMP`를 붙인 `RTM_GETNEXTHOPBUCKET`은 조건에 맞는 bucket 전체를 dump합니다. `NHA_ID`는 특정 group ID, `NHA_OIF`는 특정 ifindex 장치를 쓰는 next hop, `NHA_MASTER`는 특정 ifindex VRF 안의 장치를 쓰는 next hop으로 제한합니다.

`NHA_RES_BUCKET` 중첩 payload의 `NHA_RES_BUCKET_NH_ID`를 지정하면 해당 ID의 next hop을 담은 bucket만 반환합니다.

^^^^^^^^^^^^

The message ``RTM_GETNEXTHOPBUCKET`` with the ``NLM_F_DUMP`` flag is used
to request a dump of matching buckets. The attributes recognized at dump
requests are:

  =================== =========================================================
  ``NHA_ID``          If specified, limits the dump to just the next-hop group
                      with this ID.
  ``NHA_OIF``         If specified, limits the dump to buckets that contain
                      next hops that use the device with this ifindex.
  ``NHA_MASTER``      If specified, limits the dump to buckets that contain
                      next hops that use a device in the VRF with this ifindex.
  ``NHA_RES_BUCKET``  A nest that contains attributes specific to bucket.
  =================== =========================================================

``NHA_RES_BUCKET`` payload:

  ======================== ====================================================
  ``NHA_RES_BUCKET_NH_ID`` If specified, limits the dump to just the buckets
                           that contain the next hop with this ID.
  ======================== ====================================================

Usage

iproute2 사용 예

예제는 `192.0.2.2`와 `192.0.2.3`을 next hop ID 1과 2로 만든 뒤 ID 10의 resilient group을 구성합니다. 설명을 위해 매우 작은 8개 bucket을 사용하고, 60초 동안 traffic이 없으면 idle, 300초 동안 불균형이면 강제로 균형을 맞추도록 설정합니다.

`ip nexthop replace id 10 group 1,3/2 type resilient`은 next hop 1의 가중치를 3으로 바꿉니다. `ip nexthop bucket show id 10`으로 확인하면 8개 중 6개가 next hop 1, 2개가 next hop 2를 가리킵니다.

출력에서 idle time이 더 짧은 두 bucket은 replace 뒤 새 요구량을 만족하려고 이동한 bucket입니다. 즉 next hop 1의 할당이 4개에서 6개로 늘어난 결과입니다.

-----

To illustrate the usage, consider the following commands::

        # 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

The last command creates a resilient next-hop group. It will have 8 buckets
(which is unusually low number, and used here for demonstration purposes
only), each bucket will be considered idle when no traffic hits it for at
least 60 seconds, and if the table remains out of balance for 300 seconds,
it will be forcefully brought into balance.

Changing next-hop weights leads to change in bucket allocation::

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

This can be confirmed by looking at individual buckets::

        # 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

Note the two buckets that have a shorter idle time. Those are the ones that
were migrated after the next-hop replace command to satisfy the new demand
that next hop 1 be given 6 buckets instead of 4.

Netdevsim

netdevsim 시험 인터페이스

`netdevsim` 드라이버는 resilient group의 모의 offload를 구현하고 debugfs에서 개별 bucket을 busy로 표시할 수 있게 합니다. 예제 명령은 group 10의 bucket 23을 active로 표시합니다.

다른 debugfs 파일에 `1`을 쓰면 다음 bucket 이동 시도를 실패하도록 만들 수 있습니다. 이 인터페이스는 구현 예제이자 자동 시험 수단이며 `tools/testing/selftests/drivers/net/netdevsim/nexthop.sh`가 알고리즘 검증에 사용합니다.

---------

The netdevsim driver implements a mock offload of resilient groups, and
exposes debugfs interface that allows marking individual buckets as busy.
For example, the following will mark bucket 23 in next-hop group 10 as
active::

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

In addition, another debugfs interface can be used to configure that the
next attempt to migrate a bucket should fail::

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

Besides serving as an example, the interfaces that netdevsim exposes are
useful in automated testing, and
``tools/testing/selftests/drivers/net/netdevsim/nexthop.sh`` makes use of
them to test the algorithm.