ECMP在Linux内核的实现

ECMP(Equal Cost Multi Path),中文名叫等价多路径,是路由里的一项技术,作用是,在IP交换网络中存在到达同一目的地址的多条不同的路径,而且每条路径消耗的资源(Cost)一样的情况下,启用了ECMP功能的路由器就会根据配置策略,将它认定的“等价的IP报文”通过不同的路径均衡地转发出去,使转发达到负载均衡的目的。

ECMP在不同版本的Linux内核实现方式不一样,总体上可分为4个阶段。

内核版本

ECMP功能

< Pre kernel v2.2

无ECMP。

>= Pre kernel v2.2< kernel v3.6

有ECMP(Per-flow)

>= kernel v3.6< kernel v4.4

有ECMP(Per-packet) 可以通过iptables、ip-route等相关工具实现Per-flow参考:https://serverfault.com/questions/696675/multipath-routing-in-post-3-6-kernels

>= kernel v4.4

有ECMP(Per-flow)

说明Per-flow,每种“等价的IP报文”始终走同一条路径,它解决了IP报文对转发线路亲和性的问题。Per-packet,每个IP报文做独立的负载均衡,通常它对转发线路利用率更高。

选ECMP实现变更的大版本的最新版本进行分析,涉及版本:3.5.7、3.6.11、4.4.163。

为聚焦IP报文路由路径分析,选取TCP协议的“tcp_prot.recvmsg”指向的“tcp_recvmsg()”和“tcp_prot.sendmsg”指向的“tcp_sendmsg()”,将这两个函数分别作为入口和出口进行分析。

kernel 3.5.7

图1是内核里L3(网络层)核心流程框架,展示了接收IP报文的、发送IP报文、选取IP报文转发的下一跳和转发IP报文的流程。

图1

ECMP特性是通过选取IP报文转发的下一跳实现的。

先看关键函数“ip_route_input_common()”。它首先在代表Route Cache的哈希表“rt_hash_table”中获取是否有和当前IP报文匹配的路由缓存,如果有则直接设置IP报文转发的下一跳;如果没有则通过fib_lookup()生成下一跳信息,设置IP报文转发的下一跳,并将下一跳信息保存到Route Cache中,即设置了rt_hash_table。

下面结合代码来分析上述两种情况下的ECMP实现。

有路由缓存时,使用“rt_hash()”函数将源地址、目的地址等生成一个哈希值,再遍历哈希值获取到的哈希桶,找到和当前IP报文匹配的路由缓存。对于“同一类IP报文”,能够获取到同一个路由缓存,因此转发下一跳具有亲和性,ECMP是Per-flow类型的。需要注意的是,路由缓存是会过期的,过期时限内没有“同一类IP报文”刷新过期时间或者手动清空路由缓存,之后“同一类IP报文”可能会走不同的下一跳。

控制路由缓存超时的proc文件是:“/proc/sys/net/ipv4/route/gc_timeout”。在内核中该变量是:“ip_rt_gc_timeout”。

```

int ip_route_input_common(struct sk_buff *skb, __be32 daddr, __be32 saddr,

u8 tos, struct net_device *dev, bool noref)

{

...

hash = rt_hash(daddr, saddr, iif, rt_genid(net));

for (rth = rcu_dereference(rt_hash_table[hash].chain); rth;

rth = rcu_dereference(rth->dst.rt_next)) {

if ((((__force u32)rth->rt_key_dst ^ (__force u32)daddr) |

((__force u32)rth->rt_key_src ^ (__force u32)saddr) |

(rth->rt_route_iif ^ iif) |

(rth->rt_key_tos ^ tos)) == 0 &&

rth->rt_mark == skb->mark &&

net_eq(dev_net(rth->dst.dev), net) &&

!rt_is_expired(rth)) {

ipv4_validate_peer(rth);

if (noref) {

dst_use_noref(&rth->dst, jiffies);

skb_dst_set_noref(skb, &rth->dst);

} else {

dst_use(&rth->dst, jiffies);

skb_dst_set(skb, &rth->dst);

}

RT_CACHE_STAT_INC(in_hit);

rcu_read_unlock();

return 0;

}

RT_CACHE_STAT_INC(in_hlist_search);

}

...

}

```

没有路由缓存时,“ip_mkroute_input()”函数中会调用“fib_select_multipath()”函数,它根据随机数和不同路径的权重选择下一跳,具有随机性,对于多个“同一类IP报文”有良好的负载均衡作用,但它不能根据“同一类IP报文”的流量动态调整不同路径的权重。

```

static int ip_mkroute_input(struct sk_buff *skb,

struct fib_result *res,

const struct flowi4 *fl4,

struct in_device *in_dev,

__be32 daddr, __be32 saddr, u32 tos)

{

...

#ifdef CONFIG_IP_ROUTE_MULTIPATH

if (res->fi && res->fi->fib_nhs > 1)

fib_select_multipath(res);

#endif

...

}

void fib_select_multipath(struct fib_result *res)

{

struct fib_info *fi = res->fi;

int w;

spin_lock_bh(&fib_multipath_lock);

if (fi->fib_power <= 0) {

int power = 0;

change_nexthops(fi) {

if (!(nexthop_nh->nh_flags & RTNH_F_DEAD)) {

power += nexthop_nh->nh_weight;

nexthop_nh->nh_power = nexthop_nh->nh_weight;

}

} endfor_nexthops(fi);

fi->fib_power = power;

if (power <= 0) {

spin_unlock_bh(&fib_multipath_lock);

/* Race condition: route has just become dead. */

res->nh_sel = 0;

return;

}

}

/* w should be random number [0..fi->fib_power-1],

* it is pretty bad approximation.

*/

w = jiffies % fi->fib_power;

change_nexthops(fi) {

if (!(nexthop_nh->nh_flags & RTNH_F_DEAD) &&

nexthop_nh->nh_power) {

w -= nexthop_nh->nh_power;

if (w <= 0) {

nexthop_nh->nh_power--;

fi->fib_power--;

res->nh_sel = nhsel;

spin_unlock_bh(&fib_multipath_lock);

return;

}

}

} endfor_nexthops(fi);

/* Race condition: route has just become dead. */

res->nh_sel = 0;

spin_unlock_bh(&fib_multipath_lock);

}

```

kernel 3.6.11

图2是内核里L3(网络层)核心流程框架,展示了接收IP报文的、发送IP报文、选取IP报文转发的下一跳和转发IP报文的流程。

条件2

3.6.11的路由选择流程大体上与3.5.7的类似,主要是去掉了Route Cache,同时“fib_select_multipath()”函数实现保持不变。因此ECMP变成了Per-packet类型的。

这个变更破坏了ECMP在历史版本的默认行为,因此遭到了社区的反对,在4.4版本中Per-flow类型的ECMP又回来了,下一节我们再分析。

那3.6到4.4之间的版本就不能实现Per-packet类型的ECMP吗?也不是不可能,使用iptables对“同一类IP报文”打上mark,配合ip-route的标签功能也能实现。参考:https://serverfault.com/questions/696675/multipath-routing-in-post-3-6-kernels

kerne 4.4.163

图3是内核里L3(网络层)核心流程框架,展示了接收IP报文的、发送IP报文、选取IP报文转发的下一跳和转发IP报文的流程。

图3

4.4.163的路由选择流程大体上与3.6.11的一致,前面说了,在4.4版本中Per-flow类型的ECMP又回来了,是如何实现的呢?我们来看看“fib_rebalance()”函数、“ip_mkroute_input()”函数和“fib_select_multipath()”函数实现。

“fib_rebalance()”函数的作用是,将不同比重的多条转发路径分配哈希值区间段,哈希值落在某条转发路径范围内时,就使用该转发路径。

“ip_mkroute_input()”函数首先使用源地址、目的地址生成生成一个哈希值,再调用“fib_select_multipath()”函数选取转发路径,由于哈希值是根据源地址、目的地址生成的,是一个稳定的值,“同一类IP报文”对转发下一跳具有亲和性,所以Per-flow类型的ECMP又回来了。相对于3.6之前的版本,对于多个“同一类IP报文”有良好的负载均衡作用可能会弱一些,因为它不能自动地调整多转发路径的权重。

```

static void fib_rebalance(struct fib_info *fi)

{

int total;

int w;

struct in_device *in_dev;

if (fi->fib_nhs < 2)

return;

total = 0;

for_nexthops(fi) {

if (nh->nh_flags & RTNH_F_DEAD)

continue;

in_dev = __in_dev_get_rtnl(nh->nh_dev);

if (in_dev &&

IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev) &&

nh->nh_flags & RTNH_F_LINKDOWN)

continue;

total += nh->nh_weight;

} endfor_nexthops(fi);

w = 0;

change_nexthops(fi) {

int upper_bound;

in_dev = __in_dev_get_rtnl(nexthop_nh->nh_dev);

if (nexthop_nh->nh_flags & RTNH_F_DEAD) {

upper_bound = -1;

} else if (in_dev &&

IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev) &&

nexthop_nh->nh_flags & RTNH_F_LINKDOWN) {

upper_bound = -1;

} else {

w += nexthop_nh->nh_weight;

upper_bound = DIV_ROUND_CLOSEST_ULL((u64)w << 31,

total) - 1;

}

atomic_set(&nexthop_nh->nh_upper_bound, upper_bound);

} endfor_nexthops(fi);

net_get_random_once(&fib_multipath_secret,

sizeof(fib_multipath_secret));

}

static int ip_mkroute_input(struct sk_buff *skb,

struct fib_result *res,

const struct flowi4 *fl4,

struct in_device *in_dev,

__be32 daddr, __be32 saddr, u32 tos)

{

#ifdef CONFIG_IP_ROUTE_MULTIPATH

if (res->fi && res->fi->fib_nhs > 1) {

int h;

if (unlikely(ip_hdr(skb)->protocol == IPPROTO_ICMP))

h = ip_multipath_icmp_hash(skb);

else

h = fib_multipath_hash(saddr, daddr);

fib_select_multipath(res, h);

}

#endif

...

}

void fib_select_multipath(struct fib_result *res, int hash)

{

struct fib_info *fi = res->fi;

for_nexthops(fi) {

if (hash > atomic_read(&nh->nh_upper_bound))

continue;

res->nh_sel = nhsel;

return;

} endfor_nexthops(fi);

/* Race condition: route has just become dead. */

res->nh_sel = 0;

}

```

ECMP在Linux内核的实现的关键变更历史。

时间:1997.11

版本:Pre kernel v2.2

事件:“IPV4 ECMP”实现被加入内核。

ECMP形式:L3 Per-packet + route cache -> L3 Per-flow

相关信息:-

时间:2007

版本:2.6.23

事件:“IPV4 multipath cached”实现被移除。

ECMP形式:L3 Per-packet + route cache -> L3 Per-flow

相关信息:

https://lwn.net/Articles/241465/

IPV4 multipath cached routing support has been dropped; this code never did work very well, and never got out of the experimental state.

https://lists.openwall.net/netdev/2007/03/12/76

I'm going to FIX IT by saying that if nobody steps up to the plate to

fix the multipath cached code by 2.6.23 IT IS GONE forver.

And there is absolutely no negotiations about this, I've held back on

this for nearly 2 years, and nothing has happened, this code is not

maintained, nobody cares enough to fix the bugs, and even no

distributions enable it because it causes crashes.

时间:2012.9

版本:kernel v3.6 commit 5e9965c15ba8

事件:IPV4路由寻找下一条算法“IPV4 route cache”实现被移除。

ECMP形式:L3 Per-packet -> L3 Per-packet

相关信息:-

时间:2015.9/10

版本:kernel v4.4 commit 0e884c78ee19 and 9920e48b830a

事件:“IPV4 multipath特性重新被加回,但只支持三层

ECMP形式:L3 Per-packet + L3 hash -> L3 Per-flow

相关链接:

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=07355737a8badd951e6b72aa8609a2d6eed0a7e7

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.

时间:2016.4

版本:kernel v4.7 commit a6db4494d218

事件:IPV4路由寻找下一条算法增加下一跳邻居健康检查。参考net.ipv4.fib_multipath_use_neigh。

ECMP形式:L3 Per-packet + L3 hash -> L3 Per-flow

相关信息:-

时间:2017.3

版本:kernel v4.12 commit bf4e0a3db97e

事件:IPV4路由寻找下一条算法实现L4 hash。参考net.ipv4.fib_multipath_hash_policy。

ECMP形式:L3 Per-packet + L3/L4 hash -> L3/L4 Per-flow

相关信息:-

参考链接:

  1. https://lwn.net/Articles/241465/
  2. https://lists.openwall.net/netdev/2007/03/12/76
  3. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=07355737a8badd951e6b72aa8609a2d6eed0a7e7
  4. https://serverfault.com/questions/696675/multipath-routing-in-post-3-6-kernels
  5. https://serverfault.com/questions/820269/how-to-achieve-per-packet-multipath-routing-on-linux
  6. https://cumulusnetworks.com/blog/celebrating-ecmp-part-two/
  7. http://vger.kernel.org/~davem/tcp_output.html
  8. https://blog.csdn.net/mrpre/article/details/32183695
  9. http://simohayha.iteye.com/blog/532450
  10. https://blog.csdn.net/mrpre/article/details/32183695
  11. https://blog.csdn.net/qq_22990635/article/details/78828629
  12. https://blog.csdn.net/mrpre/article/details/33347221

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券