CFT: Next-hop objects and scalable multipath routing

Alexander V. Chernikov melifaro at
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 [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
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 -weight 100
route add -net default -weight 200

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

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


More information about the freebsd-current mailing list