ipv4: Hash-based multipath routing
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v5 Latest2 patches 1 replyIn review
- v42 patches 13 repliesSuperseded
- v32 patches 4 repliesSuperseded
Earlier versions · 2
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v2 | 1 of 3 patches | 8 replies | Superseded | |
| v1 | 2 of 3 patches | 2 replies | Superseded |
Changes in v5 from the cover letter
- Fixed compilation error
Patches in v5 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/2 | ipv4: L3 hash-based multipathinclude/ net/ net/ | +98 | 0 replies | |
| 2/2 | ipv4: ICMP packet inspection for multipathinclude/ net/ net/ | +80 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v5 yet.
Cover letter [PATCH v5 net-next 0/2] ipv4: Hash-based multipath routing
When the routing cache was removed in 3.6, the IPv4 multipath algorithm changed from more or less being destination-based into being quasi-random per-packet scheduling. This increases the risk of out-of-order packets and makes it impossible to use multipath together with anycast services.
This patch series replaces the old implementation with flow-based load balancing based on a hash over the source and destination addresses.
Distribution of the hash is done with thresholds as described in RFC 2992. This reduces the disruption when a path is added/remove when having more than two paths.
To futher the chance of successful usage in conjuction with anycast, ICMP error packets are hashed over the inner IP addresses. This ensures that PMTU will work together with anycast or load-balancers such as IPVS.
Port numbers are not considered since fragments could cause problems with anycast and IPVS. Relying on the DF-flag for TCP packets is also insufficient, since ICMP inspection effectively extracts information from the opposite flow which might have a different state of the DF-flag. This is also why the RSS hash is not used. These are typically based on the NDIS RSS spec which mandates TCP support.
Measurements of the additional overhead of a two-path multipath (p_mkroute_input excl. __mkroute_input) on a Xeon X3550 (4 cores, 2.66GHz):
Original per-packet: ~394 cycles/packet
L3 hash: ~76 cycles/packet
Changes in v5:
- Fixed compilation error
Changes in v4:
- Functions take hash directly instead of func ptr
- Added inline hash function
- Added dummy macros to minimize ifdefs
- Use upper 31 bits of hash instead of lower
Changes in v3:
- Multipath algorithm is no longer configurable (always L3)
- Added random seed to hash
- Moved ICMP inspection to isolated function
- Ignore source quench packets (deprecated as per RFC 6633)
Changes in v2:
- Replaced 8-bit xor hash with 31-bit jenkins hash
- Don't scale weights (since 31-bit)
- Avoided unnecesary renaming of variables
- Rely on DF-bit instead of fragment offset when checking for fragmentation
- upper_bound is now inclusive to avoid overflow
- Use a callback to postpone extracting flow information until necessary
- Skipped ICMP inspection entirely with L4 hashing
- Handle newly added sysctl ignore_routes_with_linkdown
Best Regards
Peter Nørlund
Peter Nørlund (2):
ipv4: L3 hash-based multipath
ipv4: ICMP packet inspection for multipath
include/net/ip_fib.h | 14 ++++- include/net/route.h | 11 +++- net/ipv4/fib_semantics.c | 140 ++++++++++++++++++++++-------------------- net/ipv4/icmp.c | 19 +++++- net/ipv4/route.c | 65 ++++++++++++++++++-- 5 files changed, 173 insertions(+), 76 deletions(-)