CFT: Next-hop objects and scalable multipath routing

From: Alexander V. Chernikov <melifaro_at_ipfw.ru>
Date: Fri, 27 Mar 2020 07:48:13 +0000
I would like to introduce an implementation of scalable multipath routing.

Previous implementation (RADIX_MPATH) focused on a simpler case like having 2 defaults, with performance falling linearly proportional to the number of paths. That implementation was also tightly coupled lookup algorithm details with the routing details, making it hard to hack both.

The proposed one allows O(1) lookup and is more cache-efficient with the large amount of routes.  Furthermore, multipath functionality is based on the number of internal changes, modernizing the old routing code.

Most of the changes revolves around introducing the concept of _nexthops_.
Nexthops are separate datastructures, containing all necessary information to perform packet forwarding such as gateway, interface and mtu. Nexthops are shared among the routes, providing more pre-computed cache-efficient data while requiring less memory.
Multipath implementation adds _nexthop groups_ which are basically collection of nexthops weights, compiled into an array, to allow direct nexthop selection.
More detailed technical description is available at [1].
Any comments/suggestions are welcome!

Presentation of the similar functionality in the other OS: [2]
Next-hop objects support was implemented in FRR in 2019 [3].

Next steps:
As these changes decouples routing code details from algorithm details and abstracts callers, it is much easier to introduce a number of other relevant features.
The most important proposed features are: nexthop-based route installation and  custom per-address-family route lookup algorithms.
The former targets improving convergence times for the large-fib boxes, while the latter may improve dataplane performance, especially for IPv6.

How to test:
fetch the patch from  https://reviews.freebsd.org/D24141
rebuild kernel with ROUTE_MPATH option (already added to amd64 GENERIC)
Optionally, rebuild world to get netstat nexthops/multipath groups reporting.

Use route(8) to add multiple routes for the same destination, optionally specifying weight.
Example: add 2:1 load balancing for the default route:

route add -net default 192.168.53.1 -weight 100
route add -net default 192.168.53.2 -weight 200

netstat -4rnW
..
Destination        Gateway            Flags   Nhop#    Mtu      Netif Expire
default            192.168.53.1       UGS         4   1500        em0
default            192.168.53.2       UGS         5   1500        em0

netstat -4onW
Nexthop data
Idx   Type         IFA                Gateway             Flags      Use Mtu         Netif     Addrif Refcnt Prepend
..
4            v4/gw 192.168.53.128     192.168.53.1       GS            0   1500        em0               2
5            v4/gw 192.168.53.128     192.168.53.2       GS            0   1500        em0               1
Nexthop groups data
MpIdx NHIdx Weigh Slots            Gateway Netif      Refcnt
1      ---- ---- ----              ----      ----    1
          4   100     1       192.168.53.1       em0
          5   200     2       192.168.53.2       em0

[1] https://reviews.freebsd.org/D24141
[2] https://linuxplumbersconf.org/event/4/contributions/434/attachments/251/436/nexthop-objects-talk.pdf
[3] https://github.com/FRRouting/frr/commit/d9f5b2f50f53d625986dbd47cd12778c9f841f0c
Received on Fri Mar 27 2020 - 06:49:05 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:41:23 UTC