Change Details

=== Overview === Switch //route// caching to //nexthop// caching, based on the nexthop objects provided by D24232 . Reasoning of the change and the high-level architecture is provided in D24141 . Quick recap: 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. Splitting the LPM code and the attached data solves multiple long-standing problems in the routing layer, drastically reduces the coupling with outher parts of the stack and allows to transparently introduce faster lookup algorithms. === Techical details === Route caching was (re)introduced to avoid (slow) routing lookups, allowing to better scale . It works by acquiring `rtentry` reference, which is protected by per-rtentry mutex. When the routing table is changed (checked by comparing the rtable generation id) or link goes down, cache record gets withdrawn, In terms of locking/performance typical datapath scenario looks like the following: (`rtalloc_ign()` logic) * RIB_RLOCK() * RT_LOCK() * ++rt ref * RIB_RUNLOCK() * RT_UNLOCK() This change merely replaces `rtentry` with the actual forwarding `nextop` as a cached object, the change is straight-forwarded. With the nexthop-based approach, rt lock/unlock part is changed to nhop `refcount_acquire()`: * RIB_RLOCK() * refcount_acquire_if_not_zero() * RIB_RUNLOCK() The rest of the mechanics such as cache cleanup on the route table change remains the same. === Worst-case scenario === The best use case for the route caching is the scenario with long-lived TCP sessions and rarely changing route table. When the condition starts to be suboptimal (short TCP connections, routing table churn), cache adds a penalty of locking/unlocking relevant rtentries. As nexthop are shared across many routes, in the scenarios with large number of short-lived connections the contention on the particular nexthop may introduce higher penalty. To be more specific, let's look at the example: Suppose node have customers behind prefixes A (50% TCP sessions) and B (50% TCP sessions). Suppose the routing table looks like the following: A/24 -> gateway1 (nhop1) B/24 -> gateway1 (nhop1) With the current code, each 50% of TCP connections will reference rte from A and 50% from B. In the proposed change, all 100% TCP connections will reference nhop1. With the high connection rate ratio (100k+/sec) this may result in lower performance due to the cacheline contention on the nhop1 refcounter. The are multiple ways (and even combination of ways) of dealing with it: 1) pcpu refcounts (`percpu_ref` in Linux) (OS-wide optimisation) 2) nexthop "sharding", similar to current trick of splitting route prefix into multiple to reduce contention (routing subsystem hack) 3) introducing faster lookup algorithms such as DXR, reducing the need of route caching. (route subsystem next steps) 4) introducing heuristics potentially backed by a socket option on avoding using route caching for short-lived connections. Depending on the importance of this particular scenario and the actual impact, one or more steps from the list above can be taken to address it.

=== Overview === Switch //route// caching to //nexthop// caching, based on the nexthop objects provided by D24232 . Reasoning of the change and the high-level architecture is provided in D24141 . Quick recap: 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. Splitting the LPM code and the attached data solves multiple long-standing problems in the routing layer, drastically reduces the coupling with outher parts of the stack and allows to transparently introduce faster lookup algorithms. === Techical details === Route caching was (re)introduced to avoid (slow) routing lookups, allowing to better scale . It works by acquiring `rtentry` reference, which is protected by per-rtentry mutex. When the routing table is changed (checked by comparing the rtable generation id) or link goes down, cache record gets withdrawn, In terms of locking/performance typical datapath scenario looks like the following: (`rtalloc_ign()` logic) * RIB_RLOCK() * RT_LOCK() * ++rt ref * RIB_RUNLOCK() * RT_UNLOCK() This change merely replaces `rtentry` with the actual forwarding `nextop` as a cached object, the change is straight-forwarded. With the nexthop-based approach, rt lock/unlock part is changed to nhop `refcount_acquire()`: * RIB_RLOCK() * refcount_acquire_if_not_zero() * RIB_RUNLOCK() The rest of the mechanics such as cache cleanup on the route table change remains the same. === Worst-case scenario === The best use case for the route caching is the scenario with long-lived TCP sessions and rarely changing route table. When the condition starts to be suboptimal (short TCP connections, routing table churn), cache adds a penalty of locking/unlocking relevant rtentries. As nexthop are shared across many routes, in the scenarios with large number of short-lived connections the contention on the particular nexthop may introduce higher penalty. To be more specific, let's look at the example: Suppose node have customers behind prefixes A (50% TCP sessions) and B (50% TCP sessions). Suppose the routing table looks like the following: A/24 -> gateway1 (nhop1) B/24 -> gateway1 (nhop1) With the current code, each 50% of TCP connections will reference rte from A and 50% from B. In the proposed change, all 100% TCP connections will reference nhop1. With the high connection rate ratio (100k+/sec) this may result in lower performance due to the cacheline contention on the nhop1 refcounter. The are multiple ways (and even combination of ways) of dealing with it: 1) pcpu refcounts (`percpu_ref` in Linux) (OS-wide optimisation) 2) nexthop "sharding", similar to current trick of splitting route prefix into multiple to reduce contention (routing subsystem hack) 3) introducing faster lookup algorithms such as DXR, reducing the need of route caching. (route subsystem next steps) 4) introducing heuristics potentially backed by a socket option on avoding using route caching for short-lived connections. Depending on the importance of this particular scenario and the actual impact, one or more steps from the list above can be taken to address it.

=== Overview === Switch //route// caching to //nexthop// caching, based on the nexthop objects provided by D24232 . Reasoning of the change and the high-level architecture is provided in D24141 . Quick recap: 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. Splitting the LPM code and the attached data solves multiple long-standing problems in the routing layer, drastically reduces the coupling with outher parts of the stack and allows to transparently introduce faster lookup algorithms. === Techical details === Route caching was (re)introduced to avoid (slow) routing lookups, allowing to better scale . It works by acquiring `rtentry` reference, which is protected by per-rtentry mutex. When the routing table is changed (checked by comparing the rtable generation id) or link goes down, cache record gets withdrawn, In terms of locking/performance typical datapath scenario looks like the following: (`rtalloc_ign()` logic) * RIB_RLOCK() * RT_LOCK() * ++rt ref * RIB_RUNLOCK() * RT_UNLOCK() This change merely replaces `rtentry` with the actual forwarding `nextop` as a cached object, the change is straight-forwarded. With the nexthop-based approach, rt lock/unlock part is changed to nhop `refcount_acquire()`: * RIB_RLOCK() * refcount_acquire_if_not_zero() * RIB_RUNLOCK() The rest of the mechanics such as cache cleanup on the route table change remains the same. === Worst-case scenario === The best use case for the route caching is the scenario with long-lived TCP sessions and rarely changing route table. When the condition starts to be suboptimal (short TCP connections, routing table churn), cache adds a penalty of locking/unlocking relevant rtentries. As nexthop are shared across many routes, in the scenarios with large number of short-lived connections the contention on the particular nexthop may introduce higher penalty. To be more specific, let's look at the example: Suppose node have customers behind prefixes A (50% TCP sessions) and B (50% TCP sessions). Suppose the routing table looks like the following: A/24 -> gateway1 (nhop1) B/24 -> gateway1 (nhop1) With the current code, each 50% of TCP connections will reference rte from A and 50% from B. In the proposed change, all 100% TCP connections will reference nhop1. With the high connection rate ratio (100k+/sec) this may result in lower performance due to the cacheline contention on the nhop1 refcounter. The are multiple ways (and even combination of ways) of dealing with it: 1) pcpu refcounts (`percpu_ref` in Linux) (OS-wide optimisation) 2) nexthop "sharding", similar to current trick of splitting route prefix into multiple to reduce contention (routing subsystem hack) 3) introducing faster lookup algorithms such as DXR, reducing the need of route caching. (route subsystem next steps) 4) introducing heuristics potentially backed by a socket option on avoding using route caching for short-lived connections. Depending on the importance of this particular scenario and the actual impact, one or more steps from the list above can be taken to address it.