专栏首页lakezhong的专栏ECMP在Linux内核的实现
原创

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 条评论
登录 后参与评论

相关文章

  • 腾讯云TKE“无损业务”升级TKE节点的方法

    2. 驱逐节点下的非DaemonSet类型的pod。部分pod驱逐失败时,手工结束不能正常结束的pod;

    lakezhong
  • 一个简化的可横向扩容的高可用的四层接入网关的原理说明——ECMP

    图1是一个简化的可横向扩容的高可用的四层接入网关的组网图,主要由入口路由(Ingress Router)、负载均衡服务器(Load Direct...

    lakezhong
  • MySQL崩溃后的数据一致性

    谁也不能保证计算机系统能够永远无故障的执行下去。网络波动、磁盘损坏等现网高频故障,机房掉电、服务器硬件失效等低频却又致命的故障,时刻考验着我们的系统。

    lakezhong
  • iOS常见问题

    首先解释ARC: automatic reference counting自动引用计数。 ARC几个要点: 在对象被创建时 retain count +1,在对...

    剑行者
  • 听说你ping用得很6?给我图解一下ping的工作原理!

    在日常生活或工作中,我们在判断与对方网络是否畅通,使用的最多的莫过于 ping 命令了。

    黄泽杰
  • 听说你 ping 用的很 6 ?给我图解一下 ping 的工作原理!

    在日常生活或工作中,我们在判断与对方网络是否畅通,使用的最多的莫过于 ping 命令了。

    小林coding
  • 对标苹果M1、芯片面积增加,高通骁龙新一代PC端处理器SC8280曝光

    2020 年 11 月,苹果推出了首款基于 ARM 架构的自研处理器 M1,并发布了三款搭载 M1 芯片的 Mac 笔记本电脑。在 M1 芯片发布之后的各种测评...

    机器之心
  • 协议森林06 瑞士军刀 (ICMP协议)

    到现在为止,我们讲解了网络层中最重要的IP协议(参考协议森林)。IP协议的一个重要补充是是ICMP协议。 ICMP协议 ICMP(Internet Contro...

    Vamei
  • 【大数据成神之路】第一版更新完毕

    截止目前为止收获3500+Star,1200+Fork。这个仓库建立的初衷的是小编个人学习和面试过程中的一个笔记本,最初的时候简单到只有几个txt,在某一天突然...

    大数据技术与架构
  • FreeRTOS——基本简介

    【背景】:项目应用中需要添加的功能变多,而裸奔程序不足以应对后期产品的发展变化,所以需要在现有软件中加入实时操作系统。而目前在研的该系列产品并非高大上的产品,M...

    Winter_world

扫码关注云+社区

领取腾讯云代金券