CFT: Next-hop objects and scalable multipath routing
Alexander V. Chernikov
melifaro at ipfw.ru
Fri Mar 27 07:49:05 UTC 2020
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 .
Any comments/suggestions are welcome!
Presentation of the similar functionality in the other OS: 
Next-hop objects support was implemented in FRR in 2019 .
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
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
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
More information about the freebsd-current