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报文的流程。
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报文的流程。
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报文的流程。
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
相关链接：
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
相关信息：-
参考链接：
- https://lwn.net/Articles/241465/
- https://lists.openwall.net/netdev/2007/03/12/76
- https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=07355737a8badd951e6b72aa8609a2d6eed0a7e7
- https://serverfault.com/questions/696675/multipath-routing-in-post-3-6-kernels
- https://serverfault.com/questions/820269/how-to-achieve-per-packet-multipath-routing-on-linux
- https://cumulusnetworks.com/blog/celebrating-ecmp-part-two/
- http://vger.kernel.org/~davem/tcp_output.html
- https://blog.csdn.net/mrpre/article/details/32183695
- http://simohayha.iteye.com/blog/532450
- https://blog.csdn.net/mrpre/article/details/32183695
- https://blog.csdn.net/qq_22990635/article/details/78828629
- https://blog.csdn.net/mrpre/article/details/33347221
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。