Date: Fri, 27 Mar 2020 07:48:13 +0000 From: Alexander V. Chernikov <melifaro@ipfw.ru> To: "current@FreeBSD.org" <current@freebsd.org>, net <net@freebsd.org> Subject: CFT: Next-hop objects and scalable multipath routing Message-ID: <1607511585294876@vla1-b2d94eaf2344.qloud-c.yandex.net>
next in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?1607511585294876>