ipv4: Hash-based multipath routing
Subsystems (4)
v2 cover 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 seeks to extend the multipath system to support both L3 and L4-based multipath while still supporting per-packet multipath.
The multipath algorithm is set as a per-route attribute (RTA_MP_ALGO) with some degree of binary compatibility with the old implementation (2.6.12 - 2.6.22), but without source level compatibility since attributes have different names:
RT_MP_ALG_L3_HASH:
L3 hash-based distribution. This was IP_MP_ALG_NONE, which with the route cached behaved somewhat like L3-based distribution. This is the new default.
RT_MP_ALG_PER_PACKET:
Per-packet distribution. Was IP_MP_ALG_RR. Uses round-robin.
RT_MP_ALG_DRR, RT_MP_ALG_RANDOM, RT_MP_ALG_WRANDOM:
Unsupported values, but reserved because they existed in 2.6.12 - 2.6.22.
RT_MP_ALG_L4_HASH:
L4 hash-based distribution. This is new.
The traditional modulo approach is replaced by a threshold-based approach, described in RFC 2992. This reduces disruption in case of link failures or route changes.
To better support anycast environments where PMTU usually breaks with multipath, certain ICMP packets are hashed using the IP addresses within the ICMP payload when using L3 hashing. This ensures that ICMP packets are routed over the same path as the flow they belong to. It is not enabled with L4 hashing, since we can only consistently rely on L4 information, when PMTU is used, and PMTU may be used in one direction while not being used in the other.
As a side effect, the multipath spinlock was removed and the code got faster. I measured ip_mkroute_input (excl. __mkroute_input) on a Xeon X3350 (4 cores, 2.66GHz) with two paths:
Old per-packet: ~393.9 cycles(tsc) New per-packet: ~75.2 cycles(tsc) New L3: ~107.9 cycles(tsc) New L4: ~129.1 cycles(tsc)
The timings are approximately the same with a single core, except for the old per-packet which gets faster (~199.8 cycles) most likely because there is no contention on the spinlock.
If this patch is accepted, a follow-up patch to iproute2 will also be submitted.
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 (3):
ipv4: Lock-less per-packet multipath
ipv4: L3 and L4 hash-based multipath routing
ipv4: ICMP packet inspection for L3 multipath
include/net/ip_fib.h | 26 ++++++- include/net/route.h | 12 ++- include/uapi/linux/rtnetlink.h | 14 +++- net/ipv4/Kconfig | 1 + net/ipv4/fib_frontend.c | 4 + net/ipv4/fib_semantics.c | 168 ++++++++++++++++++++++++++--------------- net/ipv4/icmp.c | 34 ++++++++- net/ipv4/route.c | 112 +++++++++++++++++++++++++-- 8 files changed, 298 insertions(+), 73 deletions(-)
A message that is not in the archive (sent off-list or not yet received): 1440792050-2109-1-git-send-email-pch-chEQUL3jiZBWk0Htik3J/[email protected]
PATCH v2 1/3 ipv4: Lock-less per-packet multipath
From: Peter Nørlund <pch-chEQUL3jiZBWk0Htik3J/[email protected]>
The current multipath attempted to be quasi random, but in most cases it behaved just like a round robin balancing. This patch refactors the algorithm to be exactly that and in doing so, avoids the spin lock.
The new design paves the way for hash-based multipath, replacing the modulo with thresholds, minimizing disruption in case of failing paths or route replacements.
--- include/net/ip_fib.h | 4 +- net/ipv4/Kconfig | 1 + net/ipv4/fib_semantics.c | 129 ++++++++++++++++++++++++++--------------------- 3 files changed, 74 insertions(+), 60 deletions(-)
include/net/ip_fib.h +2 -2
@@ -79,7 +79,7 @@ struct fib_nh {unsigned char nh_scope;#ifdef CONFIG_IP_ROUTE_MULTIPATH int nh_weight; -int nh_power; +atomic_t nh_upper_bound;#endif #ifdef CONFIG_IP_ROUTE_CLASSID __u32 nh_tclassid;
@@ -118,7 +118,7 @@ struct fib_info {#define fib_advmss fib_metrics[RTAX_ADVMSS-1]int fib_nhs;#ifdef CONFIG_IP_ROUTE_MULTIPATH -int fib_power; +int fib_weight;#endif struct rcu_head rcu;struct fib_nh fib_nh[0 ];
net/ipv4/Kconfig +1 -0
@@ -81,6 +81,7 @@ config IP_MULTIPLE_TABLES config IP_ROUTE_MULTIPATH bool "IP: equal cost multipath" depends on IP_ADVANCED_ROUTER + select BITREVERSE help Normally, the routing tables specify a single action to be taken in a deterministic manner for a given packet. If you say Y here
net/ipv4/fib_semantics.c +71 -58
191 lines not on this page · raw message
Signature · 1 line
2.1.4
PATCH v2 2/3 ipv4: L3 and L4 hash-based multipath routing
In reply to a message not in the archiveFrom: Peter Nørlund <pch-chEQUL3jiZBWk0Htik3J/[email protected]>
This patch adds L3 and L4 hash-based multipath routing, selectable on a per-route basis with the reintroduced RTA_MP_ALGO attribute. The default is now RT_MP_ALG_L3_HASH.
--- include/net/ip_fib.h | 22 ++++++++++++++++- include/uapi/linux/rtnetlink.h | 14 ++++++++++- net/ipv4/fib_frontend.c | 4 +++ net/ipv4/fib_semantics.c | 43 +++++++++++++++++++++++++++----- net/ipv4/route.c | 56 ++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 129 insertions(+), 10 deletions(-)
include/net/ip_fib.h +21 -1
@@ -37,6 +37,7 @@ struct fib_config {u32 fc_flags;u32 fc_priority;__be32 fc_prefsrc; +int fc_mp_alg;struct nlattr *fc_mx;struct rtnexthop *fc_mp;int fc_mx_len;
@@ -119,6 +120,7 @@ struct fib_info {int fib_nhs;#ifdef CONFIG_IP_ROUTE_MULTIPATH int fib_weight; +int fib_mp_alg;#endif struct rcu_head rcu;struct fib_nh fib_nh[0 ];
@@ -312,7 +314,25 @@ int ip_fib_check_default(__be32 gw, struct net_device *dev);int fib_sync_down_dev (struct net_device *dev,unsigned long event);int fib_sync_down_addr (struct net *net,__be32 local);int fib_sync_up (struct net_device *dev,unsigned int nh_flags); -void fib_select_multipath (struct fib_result *res); + +struct multipath_flow4 { +__be32 saddr; +__be32 daddr; +union { +__be32 ports; +struct { +__be16 sport; +__be16 dport; + }; + }; +}; + +typedef void (*multipath_flow4_func_t )(struct multipath_flow4 *flow, +void *ctx); + +void fib_select_multipath (struct fib_result *res, +multipath_flow4_func_t flow_func, +void *ctx);/* Exported by fib_trie.c */ void fib_trie_init (void );
include/uapi/linux/rtnetlink.h +13 -1
@@ -271,6 +271,18 @@ enum rt_scope_t {#define RTM_F_EQUALIZE 0x400/* Multipath equalizer: NI */ #define RTM_F_PREFIX 0x800/* Prefix addresses */ +/* Multipath algorithms */ + +enum rt_mp_alg_t { +RT_MP_ALG_L3_HASH ,/* Was IP_MP_ALG_NONE */ +RT_MP_ALG_PER_PACKET ,/* Was IP_MP_ALG_RR */ +RT_MP_ALG_DRR ,/* not used */ +RT_MP_ALG_RANDOM ,/* not used */ +RT_MP_ALG_WRANDOM ,/* not used */ +RT_MP_ALG_L4_HASH , + __RT_MP_ALG_MAX +}; +/* Reserved table identifiers */ enum rt_class_t {
@@ -301,7 +313,7 @@ enum rtattr_type_t {RTA_FLOW ,RTA_CACHEINFO ,RTA_SESSION ,/* no longer used */ -RTA_MP_ALGO ,/* no longer used */ +RTA_MP_ALGO ,RTA_TABLE ,RTA_MARK , RTA_MFC_STATS,
net/ipv4/fib_frontend.c +4 -0
@@ -622,6 +622,7 @@ const struct nla_policy rtm_ipv4_policy[RTA_MAX + 1] = { [RTA_PREFSRC] = { .type = NLA_U32 }, [RTA_METRICS] = { .type = NLA_NESTED }, [RTA_MULTIPATH] = { .len = sizeof(struct rtnexthop) }, + [RTA_MP_ALGO] = { .type = NLA_U32 }, [RTA_FLOW] = { .type = NLA_U32 }, [RTA_ENCAP_TYPE] = { .type = NLA_U16 }, [RTA_ENCAP] = { .type = NLA_NESTED },
@@ -684,6 +685,9 @@ static int rtm_to_fib_config(struct net *net, struct sk_buff *skb, cfg->fc_mp =nla_data (attr); cfg->fc_mp_len =nla_len (attr);break ; +case RTA_MP_ALGO : + cfg->fc_mp_alg =nla_get_u32 (attr); +break ;case RTA_FLOW : cfg->fc_flow =nla_get_u32 (attr);break ;
net/ipv4/fib_semantics.c +37 -6
71 lines not on this page · raw message
net/ipv4/route.c +54 -2
74 lines not on this page · raw message
Signature · 1 line
2.1.4
Re: [PATCH v2 net-next 2/3] ipv4: L3 and L4 hash-based multipath routing
Quoted 36 lines · On Fri, Aug 28, 2015 at 1:00 PM, <[email protected]> wrote:
From: Peter Nørlund <[email protected]>
This patch adds L3 and L4 hash-based multipath routing, selectable on a per-route basis with the reintroduced
RTA_MP_ALGOattribute. The default is nowRT_MP_ALG_L3_HASH.Signed-off-by Peter Nørlund <[email protected]>--- include/net/ip_fib.h | 22 ++++++++++++++++- include/uapi/linux/rtnetlink.h | 14 ++++++++++- net/ipv4/fib_frontend.c | 4 +++ net/ipv4/fib_semantics.c | 43 +++++++++++++++++++++++++++----- net/ipv4/route.c | 56 ++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 129 insertions(+), 10 deletions(-)include/net/ip_fib.h +2
-0@@ -37,6 +37,7 @@ struct fib_config {u32 fc_flags;u32 fc_priority;__be32 fc_prefsrc; +int fc_mp_alg;struct nlattr *fc_mx;struct rtnexthop *fc_mp;int fc_mx_len;@@ -119,6 +120,7 @@ struct fib_info {int fib_nhs;#ifdef CONFIG_IP_ROUTE_MULTIPATH int fib_weight; +int fib_mp_alg;#endif struct rcu_head rcu;struct fib_nh fib_nh[0 ];
include/net/ip_fib.h int ip_fib_check_default(__be32 gw, struct net_device *dev); · line 318
Quoted 6 lines
include/net/ip_fib.h +2
-1@@ -312,7 +314,25 @@ int ip_fib_check_default(__be32 gw, struct net_device *dev);int fib_sync_down_dev (struct net_device *dev,unsigned long event);int fib_sync_down_addr (struct net *net,__be32 local);int fib_sync_up (struct net_device *dev,unsigned int nh_flags); -void fib_select_multipath (struct fib_result *res); + +struct multipath_flow4 {
Please use flowi4 structure instead.
Quoted 120 lines
include/net/ip_fib.h +17
-0+__be32 saddr; +__be32 daddr; +union { +__be32 ports; +struct { +__be16 sport; +__be16 dport; + }; + }; +}; + +typedef void (*multipath_flow4_func_t )(struct multipath_flow4 *flow, +void *ctx); + +void fib_select_multipath (struct fib_result *res, +multipath_flow4_func_t flow_func, +void *ctx);/* Exported by fib_trie.c */ void fib_trie_init (void );include/uapi/linux/rtnetlink.h +13
-1@@ -271,6 +271,18 @@ enum rt_scope_t {#define RTM_F_EQUALIZE 0x400/* Multipath equalizer: NI */ #define RTM_F_PREFIX 0x800/* Prefix addresses */ +/* Multipath algorithms */ + +enum rt_mp_alg_t { +RT_MP_ALG_L3_HASH ,/* Was IP_MP_ALG_NONE */ +RT_MP_ALG_PER_PACKET ,/* Was IP_MP_ALG_RR */ +RT_MP_ALG_DRR ,/* not used */ +RT_MP_ALG_RANDOM ,/* not used */ +RT_MP_ALG_WRANDOM ,/* not used */ +RT_MP_ALG_L4_HASH , + __RT_MP_ALG_MAX +}; +/* Reserved table identifiers */ enum rt_class_t {@@ -301,7 +313,7 @@ enum rtattr_type_t {RTA_FLOW ,RTA_CACHEINFO ,RTA_SESSION ,/* no longer used */ -RTA_MP_ALGO ,/* no longer used */ +RTA_MP_ALGO ,RTA_TABLE ,RTA_MARK , RTA_MFC_STATS,net/ipv4/fib_frontend.c +4
-0@@ -622,6 +622,7 @@ const struct nla_policy rtm_ipv4_policy[RTA_MAX + 1] = { [RTA_PREFSRC] = { .type = NLA_U32 }, [RTA_METRICS] = { .type = NLA_NESTED }, [RTA_MULTIPATH] = { .len = sizeof(struct rtnexthop) }, + [RTA_MP_ALGO] = { .type = NLA_U32 }, [RTA_FLOW] = { .type = NLA_U32 }, [RTA_ENCAP_TYPE] = { .type = NLA_U16 }, [RTA_ENCAP] = { .type = NLA_NESTED },@@ -684,6 +685,9 @@ static int rtm_to_fib_config(struct net *net, struct sk_buff *skb, cfg->fc_mp =nla_data (attr); cfg->fc_mp_len =nla_len (attr);break ; +case RTA_MP_ALGO : + cfg->fc_mp_alg =nla_get_u32 (attr); +break ;case RTA_FLOW : cfg->fc_flow =nla_get_u32 (attr);break ;net/ipv4/fib_semantics.c +12
-5@@ -259,6 +259,11 @@ static inline int nh_comp(const struct fib_info *fi, const struct fib_info *ofi) {const struct fib_nh *onh = ofi->fib_nh; +#ifdef CONFIG_IP_ROUTE_MULTIPATH +if (fi->fib_mp_alg != ofi->fib_mp_alg) +return -1 ; +#endif +for_nexthops (fi) { if (nh->nh_oif != onh->nh_oif || nh->nh_gw != onh->nh_gw ||@@ -1028,6 +1033,7 @@ struct fib_info *fib_create_info(struct fib_config *cfg)if (cfg->fc_mp) {#ifdef CONFIG_IP_ROUTE_MULTIPATH + fi->fib_mp_alg = cfg->fc_mp_alg; err =fib_get_nhs (fi, cfg->fc_mp, cfg->fc_mp_len, cfg);if (err !=0 ) goto failure;@@ -1245,6 +1251,10 @@ int fib_dump_info(struct sk_buff *skb, u32 portid, u32 seq, int event,struct rtnexthop *rtnh;struct nlattr *mp; +if (fi->fib_mp_alg && +nla_put_u32 (skb,RTA_MP_ALGO , fi->fib_mp_alg)) + goto nla_put_failure; + mp =nla_nest_start (skb,RTA_MULTIPATH );if (!mp) goto nla_put_failure;@@ -1520,16 +1530,37 @@ int fib_sync_up(struct net_device *dev, unsigned int nh_flags)#ifdef CONFIG_IP_ROUTE_MULTIPATH -/* -* The algorithm is suboptimal, but it provides really -* fair weighted route distribution. -*/ -void fib_select_multipath (struct fib_result *res) +/* Compute multipath hash based on 3- or 5-tuple */ +static int fib_multipath_hash(const struct fib_result *res,
net/ipv4/fib_semantics.c int fib_sync_up(struct net_device *dev, unsigned int nh_flags) · line 1544
Quoted 10 lines
net/ipv4/fib_semantics.c +10
-0+ multipath_flow4_func_t flow_func, void *ctx) +{ + struct multipath_flow4 flow; + +flow_func (&flow, ctx); + +if (res->fi->fib_mp_alg ==RT_MP_ALG_L4_HASH ) +return jhash_3words (flow.saddr, flow.daddr, flow.ports,0 ) >>1 ; +else +return jhash_2words (flow.saddr, flow.daddr,0 ) >>1 ;
Please define/use general functions. As I pointed out an L4 hash may already be available via skb_get_hash or sk->tx_hash. For L3 we could add a function that does flow dissector to only get addresses and then hash over that. Also, jhash really should include a randomized key to avoid any concerns about DOS.
Quoted 28 lines
net/ipv4/fib_semantics.c +15
-1+} + +static int fib_multipath_perpacket (void ) +{ +return bitrev32 (this_cpu_inc_return (fib_multipath_rr_counter)) >>1 ; +} + +void fib_select_multipath (struct fib_result *res, +multipath_flow4_func_t flow_func, +void *ctx) {struct fib_info *fi = res->fi;int h; - h =bitrev32 (this_cpu_inc_return (fib_multipath_rr_counter)) >>1 ; +if (res->fi->fib_mp_alg ==RT_MP_ALG_PER_PACKET ) { + h =fib_multipath_perpacket (); + }else { + h =fib_multipath_hash (res, flow_func, ctx); + }for_nexthops (fi) {if (h >atomic_read (&nh->nh_upper_bound))net/ipv4/route.c +0
-0
net/ipv4/route.c out: · line 1649
Quoted 7 lines
net/ipv4/route.c +4
-0@@ -1643,6 +1643,58 @@ out:return err; } +#ifdef CONFIG_IP_ROUTE_MULTIPATH + +/* Fill multipath flow key data based on socket buffer */ +static void ip_multipath_flow_skb (struct multipath_flow4 *flow,void *ctx)
Please use flow_dissector for this, don't define a new dissection method.
Quoted 76 lines
net/ipv4/route.c +50
-3+{ +const struct sk_buff *skb = (const struct sk_buff *)ctx; +const struct iphdr *iph; + + iph =ip_hdr (skb); + + flow->saddr = iph->saddr; + flow->daddr = iph->daddr; + flow->ports =0 ; + +if (unlikely (!(iph->frag_off &htons (IP_DF )))) +return ; + +if (iph->protocol ==IPPROTO_TCP || + iph->protocol ==IPPROTO_UDP || + iph->protocol ==IPPROTO_SCTP ) { +__be16 _ports[2 ]; +const __be16 *ports; + + ports =skb_header_pointer (skb, iph->ihl *4 ,sizeof (_ports), + &_ports); +if (ports) { + flow->sport = ports[0 ]; + flow->dport = ports[1 ]; + } + } +} + +/* Fill multipath flow key data based on flowi4 */ +static void ip_multipath_flow_fl4 (struct multipath_flow4 *flow,void *ctx) +{ +const struct flowi4 *fl4 = (const struct flowi4 *)ctx; + + flow->saddr = fl4->saddr; + flow->daddr = fl4->daddr; + +if (fl4->flowi4_proto ==IPPROTO_TCP || + fl4->flowi4_proto ==IPPROTO_UDP || + fl4->flowi4_proto ==IPPROTO_SCTP ) { + flow->sport = fl4->fl4_sport; + flow->dport = fl4->fl4_dport; + }else { + flow->ports =0 ; + } +} + +#endif /* CONFIG_IP_ROUTE_MULTIPATH */ + static int ip_mkroute_input(struct sk_buff *skb, struct fib_result *res, const struct flowi4 *fl4,@@ -1651,7 +1703,7 @@ static int ip_mkroute_input(struct sk_buff *skb, {#ifdef CONFIG_IP_ROUTE_MULTIPATH if (res->fi && res->fi->fib_nhs >1 ) -fib_select_multipath (res); +fib_select_multipath (res, ip_multipath_flow_skb, skb);#endif /* create a routing cache entry */ @@ -2197,7 +2249,7 @@ struct rtable *__ip_route_output_key(struct net *net, struct flowi4 *fl4)#ifdef CONFIG_IP_ROUTE_MULTIPATH if (res.fi->fib_nhs >1 && fl4->flowi4_oif ==0 ) -fib_select_multipath (&res); +fib_select_multipath (&res, ip_multipath_flow_fl4, fl4); else#endif if (!res.prefixlen && --2.1.4
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
From: pch-chEQUL3jiZBWk0Htik3J/[email protected]
Date: Fri, 28 Aug 2015 22:00:47 +0200
Quoted 4 lines
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.
Don't even try to be fancy.
Simply kill the round-robin stuff off completely, and make hash based routing the one and only mode, no special configuration stuff necessary.
This puts ipv4 in line with ipv6, and nobody cares about the existing round robin behavior at all.
Thanks.
A message that is not in the archive (sent off-list or not yet received): 20150829.131429.360433621593751136.davem-fT/PcQaiUtIeIZ0/[email protected]
Quoted 9 lines · On Sat, 29 Aug 2015 13:14:29 -0700 (PDT) David Miller…
From: pch-chEQUL3jiZBWk0Htik3J/[email protected]
Date: Fri, 28 Aug 2015 22:00:47 +0200Quoted 5 lines
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.
Quoted 5 lines
Don't even try to be fancy.
Simply kill the round-robin stuff off completely, and make hash based routing the one and only mode, no special configuration stuff necessary.
I like the sound of that! Just to be clear - are you telling me to stick with L3 and skip the L4 part?
Quoted 5 lines
This puts ipv4 in line with ipv6, and nobody cares about the existing round robin behavior at all.
Thanks.
From: Peter Nørlund <pch-chEQUL3jiZBWk0Htik3J/[email protected]>
Date: Sat, 29 Aug 2015 22:31:15 +0200
Quoted 12 lines
Quoted 9 lines · On Sat, 29 Aug 2015 13:14:29 -0700 (PDT) David Miller…
From: pch-chEQUL3jiZBWk0Htik3J/[email protected]
Date: Fri, 28 Aug 2015 22:00:47 +0200Quoted 5 lines
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.
Quoted 8 lines
Quoted 5 lines
Don't even try to be fancy.
Simply kill the round-robin stuff off completely, and make hash based routing the one and only mode, no special configuration stuff necessary.
I like the sound of that! Just to be clear - are you telling me to stick with L3 and skip the L4 part?
For now it seems best to just do L3 and make ipv4 and ipv6 behave the same.
A message that is not in the archive (sent off-list or not yet received): 20150829.134628.1013990034021542524.davem-fT/PcQaiUtIeIZ0/[email protected]
Quoted 21 lines · David Miller
From: Peter Nørlund <pch-chEQUL3jiZBWk0Htik3J/[email protected]>
Date: Sat, 29 Aug 2015 22:31:15 +0200Quoted 18 lines
Quoted 14 lines · On Sat, 29 Aug 2015 13:14:29 -0700 (PDT) David Miller…
From: pch-chEQUL3jiZBWk0Htik3J/[email protected]
Date: Fri, 28 Aug 2015 22:00:47 +0200Quoted 5 lines
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.
Don't even try to be fancy.
Simply kill the round-robin stuff off completely, and make hash based routing the one and only mode, no special configuration stuff necessary.
Quoted 5 lines
Quoted 2 lines
I like the sound of that! Just to be clear - are you telling me to stick with L3 and skip the L4 part?
For now it seems best to just do L3 and make ipv4 and ipv6 behave the same.
That makes mapping the hash to offload hardware easier also.
Quoted 21 lines · David Miller
From: Peter Nørlund <pch-chEQUL3jiZBWk0Htik3J/[email protected]>
Date: Sat, 29 Aug 2015 22:31:15 +0200Quoted 18 lines
Quoted 14 lines · On Sat, 29 Aug 2015 13:14:29 -0700 (PDT) David Miller…
From: pch-chEQUL3jiZBWk0Htik3J/[email protected]
Date: Fri, 28 Aug 2015 22:00:47 +0200Quoted 5 lines
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.
Don't even try to be fancy.
Simply kill the round-robin stuff off completely, and make hash based routing the one and only mode, no special configuration stuff necessary.
Quoted 5 lines
Quoted 2 lines
I like the sound of that! Just to be clear - are you telling me to stick with L3 and skip the L4 part?
For now it seems best to just do L3 and make ipv4 and ipv6 behave the same.
This might be simpler if we just go directly to L4 which should be better load balancing and what most switches are doing anyway. The hash comes from:
1) If a lookup includes an skb, we just need to call skb_get_hash.
2) If we have a socket and sk->sk_txhash is nonzero then use that.
3) Else compute a hash frome flowi. We don't have the exact functions for this, but they can be easily derived from __skb_get_hash_flowi4 and __skb_get_hash_flowi6 (i.e. create general get_hash_flowi4 and get_hash_flowi6 and then call these from skb functions and multipath lookup).
Tom
Quoted 4 lines
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 33 lines · On Sat, 29 Aug 2015 13:59:08 -0700 Tom Herbert <[email protected]> wrote:
Quoted 21 lines · David Miller
From: Peter Nørlund <[email protected]>
Date: Sat, 29 Aug 2015 22:31:15 +0200Quoted 18 lines
Quoted 14 lines · On Sat, 29 Aug 2015 13:14:29 -0700 (PDT) David Miller <[email protected]>…
From: [email protected]
Date: Fri, 28 Aug 2015 22:00:47 +0200Quoted 5 lines
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.
Don't even try to be fancy.
Simply kill the round-robin stuff off completely, and make hash based routing the one and only mode, no special configuration stuff necessary.
Quoted 5 lines
Quoted 2 lines
I like the sound of that! Just to be clear - are you telling me to stick with L3 and skip the L4 part?
For now it seems best to just do L3 and make ipv4 and ipv6 behave the same.
This might be simpler if we just go directly to L4 which should be better load balancing and what most switches are doing anyway. The hash comes from:
Quoted 7 lines
1) If a lookup includes an skb, we just need to call
skb_get_hash.
2) If we have a socket andsk->sk_txhashis nonzero then use that.
3) Else compute a hash frome flowi. We don't have the exact functions for this, but they can be easily derived from__skb_get_hash_flowi4and__skb_get_hash_flowi6(i.e. create generalget_hash_flowi4andget_hash_flowi6and then call these from skb functions and multipath lookup).
It would definitely be simpler, and it would be nice to just fetch the hash directly from the NIC - and for link aggregation it would probably be fine. But with L4, we always need to consider fragmented packets, which might cause some packets of a flow to be routed differently - and with ECMP, the ramifications of suddenly choosing another path for a flow are worse than for link aggregation. The latency through the different paths may differ enough to cause out-or-order packets and bad TCP performance as a consequence. Both Cisco and Juniper routers defaults to L3 for ECMP - exactly for that reason, I believe. RFC 2991 also points out that ports probably shouldn't be used as part of the flow key with ECMP.
With anycast it is even worse. Depending on how anycast is used, changing path may destroy a TCP connection. And without special treatment of ICMP, ICMP packets may hit another anycast node, causing PMTU to fail. Cloudflare recognized this and solved it by letting a user space daemon (pmtud) route ICMP packets through all paths, ensuring that the anycast node receives the ICMP. But a more efficient solution is to handle the issue within the kernel.
It might be possible to do L4 on flows using PMTU, and while it is possible to extract addresses and ports from the ICMP payload, you can't rely the DF-bit in the ICMP payload, since it comes from the opposite flow (Flow A->B use PMTU while B->A doesn't). I guess you can technically reduce the number of possible paths to two, though.
I obviously prefer the default to be L3 with ICMP handling, since I specifically plan to use ECMP together with anycast (albeit anycasted load balancers which synchronizes states, although delayed), but I also recognizes that anycast is a special case. Question is, it is so much a special case that it belongs outside the vanilla kernel?
Regards,
Peter Nørlund
Quoted 7 lines
Tom
Quoted 4 lines
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 44 lines · Peter Nørlund
Quoted 33 lines · On Sat, 29 Aug 2015 13:59:08 -0700 Tom Herbert…
Quoted 21 lines · David Miller
From: Peter Nørlund <pch-chEQUL3jiZBWk0Htik3J/[email protected]>
Date: Sat, 29 Aug 2015 22:31:15 +0200Quoted 18 lines
Quoted 14 lines · On Sat, 29 Aug 2015 13:14:29 -0700 (PDT) David Miller…
From: pch-chEQUL3jiZBWk0Htik3J/[email protected]
Date: Fri, 28 Aug 2015 22:00:47 +0200Quoted 5 lines
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.
Don't even try to be fancy.
Simply kill the round-robin stuff off completely, and make hash based routing the one and only mode, no special configuration stuff necessary.
Quoted 5 lines
Quoted 2 lines
I like the sound of that! Just to be clear - are you telling me to stick with L3 and skip the L4 part?
For now it seems best to just do L3 and make ipv4 and ipv6 behave the same.
This might be simpler if we just go directly to L4 which should be better load balancing and what most switches are doing anyway. The hash comes from:
Quoted 7 lines
1) If a lookup includes an skb, we just need to call
skb_get_hash.
2) If we have a socket andsk->sk_txhashis nonzero then use that.
3) Else compute a hash frome flowi. We don't have the exact functions for this, but they can be easily derived from__skb_get_hash_flowi4and__skb_get_hash_flowi6(i.e. create generalget_hash_flowi4andget_hash_flowi6and then call these from skb functions and multipath lookup).
Quoted 12 lines
It would definitely be simpler, and it would be nice to just fetch the hash directly from the NIC - and for link aggregation it would probably be fine. But with L4, we always need to consider fragmented packets, which might cause some packets of a flow to be routed differently - and with ECMP, the ramifications of suddenly choosing another path for a flow are worse than for link aggregation. The latency through the different paths may differ enough to cause out-or-order packets and bad TCP performance as a consequence. Both Cisco and Juniper routers defaults to L3 for ECMP - exactly for that reason, I believe. RFC 2991 also points out that ports probably shouldn't be used as part of the flow key with ECMP.
That's more reason why we need vendors to use IPv6 flow label instead of ports to do ECMP :-). In any case, if we're fragmenting TCP packets then we're already in a bad place performance-wise-- we really don't need to optimize for that case. Albeit, it would be nice if fragments of packet followed same path, but the would require devices to not do L4 hash over ports when MF is set-- I don't know if anyone does that (I have been meaning to add that to stack).
Quoted 14 lines
With anycast it is even worse. Depending on how anycast is used, changing path may destroy a TCP connection. And without special treatment of ICMP, ICMP packets may hit another anycast node, causing PMTU to fail. Cloudflare recognized this and solved it by letting a user space daemon (pmtud) route ICMP packets through all paths, ensuring that the anycast node receives the ICMP. But a more efficient solution is to handle the issue within the kernel.
It might be possible to do L4 on flows using PMTU, and while it is possible to extract addresses and ports from the ICMP payload, you can't rely the DF-bit in the ICMP payload, since it comes from the opposite flow (Flow
A->Buse PMTU whileB->Adoesn't). I guess you can technically reduce the number of possible paths to two, though.
Quoted 6 lines
I obviously prefer the default to be L3 with ICMP handling, since I specifically plan to use ECMP together with anycast (albeit anycasted load balancers which synchronizes states, although delayed), but I also recognizes that anycast is a special case. Question is, it is so much a special case that it belongs outside the vanilla kernel?
OTOH, if the hash is always dependent on fixed fields of a connection (L3 or L4) then the path can never change during the lifetime of a connection, this is a bad thing if we want to try a different path when a connection is failing (via ipv4_negative_advice). This is why there is value is using sk->sk_txhash as a route selector.
It is stunning that anycast works at all given it's dependency on the network path being stack, but I suppose it is functionality we'll need to preserve.
Tom
Quoted 11 lines
Regards,
Peter NørlundQuoted 7 lines
Tom
Quoted 4 lines
--
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 13 lines · Tom Herbert
Quoted 12 lines · Peter N??rlund
It would definitely be simpler, and it would be nice to just fetch the hash directly from the NIC - and for link aggregation it would probably be fine. But with L4, we always need to consider fragmented packets, which might cause some packets of a flow to be routed differently - and with ECMP, the ramifications of suddenly choosing another path for a flow are worse than for link aggregation. The latency through the different paths may differ enough to cause out-or-order packets and bad TCP performance as a consequence. Both Cisco and Juniper routers defaults to L3 for ECMP - exactly for that reason, I believe. RFC 2991 also points out that ports probably shouldn't be used as part of the flow key with ECMP.
Quoted 7 lines
That's more reason why we need vendors to use IPv6 flow label instead of ports to do ECMP :-). In any case, if we're fragmenting TCP packets then we're already in a bad place performance-wise-- we really don't need to optimize for that case. Albeit, it would be nice if fragments of packet followed same path, but the would require devices to not do L4 hash over ports when MF is set-- I don't know if anyone does that (I have been meaning to add that to stack).
+1 for solving this at hash level. Being able to rely on the L4 HW hash for multipath routing is very desirable. A simple MF bit || FO > 0 check with fall back to flow dissector to generate an L3 hash in case the HW provided an L4 hash should be sufficient to address the fragmentation concern.
Since performance is gone anyway, I'm not sure it's worth offloading this behaviour to the HW.
PATCH v2 3/3 ipv4: ICMP packet inspection for L3 multipath
In reply to [email protected]From: Peter Nørlund <[email protected]>
When doing L3 based multipath, ICMP packets are inspected to let them route over the same path as the flow they relate to, allowing anycast environments to work with ECMP.
--- include/net/ip_fib.h | 2 +- include/net/route.h | 12 ++++++- net/ipv4/fib_semantics.c | 2 +- net/ipv4/icmp.c | 34 +++++++++++++++++++- net/ipv4/route.c | 82 ++++++++++++++++++++++++++++++++++++++---------- 5 files changed, 112 insertions(+), 20 deletions(-)
include/net/ip_fib.h +1 -1
@@ -328,7 +328,7 @@ struct multipath_flow4 { };typedef void (*multipath_flow4_func_t )(struct multipath_flow4 *flow, -void *ctx); +enum rt_mp_alg_t algo,void *ctx); void fib_select_multipath(struct fib_result *res, multipath_flow4_func_t flow_func,
include/net/route.h +11 -1
@@ -28,6 +28,7 @@#include <net/inetpeer.h> #include <net/flow.h> #include <net/inet_sock.h> +#include <net/ip_fib.h> #include <linux/in_route.h> #include <linux/rtnetlink.h> #include <linux/rcupdate.h>
@@ -110,7 +111,16 @@ struct in_device;int ip_rt_init (void );void rt_cache_flush (struct net *net);void rt_flush_dev (struct net_device *dev); -struct rtable *__ip_route_output_key (struct net *,struct flowi4 *flp); +struct rtable *__ip_route_output_key_flow (struct net *,struct flowi4 *flp, +multipath_flow4_func_t flow_func, +void *ctx); + +static inline struct rtable *__ip_route_output_key (struct net *net, +struct flowi4 *flp) +{ +return __ip_route_output_key_flow (net, flp,NULL ,NULL ); +} +struct rtable *ip_route_output_flow (struct net *,struct flowi4 *flp,struct sock *sk); struct dst_entry *ipv4_blackhole_route(struct net *net,
net/ipv4/fib_semantics.c +1 -1
@@ -1536,7 +1536,7 @@ static int fib_multipath_hash(const struct fib_result *res, {struct multipath_flow4 flow; -flow_func (&flow, ctx); +flow_func (&flow, res->fi->fib_mp_alg, ctx);if (res->fi->fib_mp_alg ==RT_MP_ALG_L4_HASH )return jhash_3words (flow.saddr, flow.daddr, flow.ports,0 ) >>1 ;
net/ipv4/icmp.c +33 -1
@@ -439,6 +439,38 @@ out_unlock:icmp_xmit_unlock (sk); } +/* Source and destination is swapped. See ip_multipath_flow_skb */ +static void icmp_multipath_flow (struct multipath_flow4 *flow, +enum rt_mp_alg_t algo,void *ctx) +{ +const struct sk_buff *skb = (const struct sk_buff *)ctx; +const struct iphdr *iph =ip_hdr (skb); + + flow->saddr = iph->daddr; + flow->daddr = iph->saddr; + flow->ports =0 ; + +if (algo ==RT_MP_ALG_L4_HASH ) +return ; + +if (unlikely (!(iph->frag_off &htons (IP_DF )))) +return ; + +if (iph->protocol ==IPPROTO_TCP || + iph->protocol ==IPPROTO_UDP || + iph->protocol ==IPPROTO_SCTP ) { +__be16 _ports[2 ]; +const __be16 *ports; + + ports =skb_header_pointer (skb, iph->ihl *4 ,sizeof (_ports), + &_ports); +if (ports) { + flow->sport = ports[1 ]; + flow->dport = ports[0 ]; + } + } +} + static struct rtable *icmp_route_lookup(struct net *net, struct flowi4 *fl4, struct sk_buff *skb_in,
@@ -463,7 +495,7 @@ static struct rtable *icmp_route_lookup(struct net *net, fl4->flowi4_oif =vrf_master_ifindex (skb_in->dev) ? : skb_in->dev->ifindex;security_skb_classify_flow (skb_in,flowi4_to_flowi (fl4)); - rt =__ip_route_output_key (net, fl4); + rt =__ip_route_output_key_flow (net, fl4, icmp_multipath_flow, skb_in);if (IS_ERR (rt))return rt;
net/ipv4/route.c +66 -16
119 lines not on this page · raw message
Signature · 1 line
2.1.4