Skip to content

ipv4: Hash-based multipath routing

Peter Nørlund netdev 5 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v5 Latest2 patches 1 replyIn review
  2. v42 patches 13 repliesSuperseded
  3. v32 patches 4 repliesSuperseded
Earlier versions · 2
VersionPostedPatchesRepliesStatus
v21 of 3 patches8 repliesSuperseded
v12 of 3 patches2 repliesSuperseded

Changes in v5 from the cover letter

- Fixed compilation error

Patches in v5 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2ipv4: L3 hash-based multipathinclude/net/ip_fib.h net/ipv4/fib_semantics.c net/ipv4/route.c+98 -720 replies
2/2ipv4: ICMP packet inspection for multipathinclude/net/route.h net/ipv4/icmp.c net/ipv4/route.c+80 -90 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v5 yet.

Read the v5 thread

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(-)