ECMP Hash 计算详解: fib_multipath_hash() 四种策略全解析

一、概述

fib_multipath_hash() 是 ECMP 选路的第一阶段，负责根据数据包信息计算一个 hash 值，供第二阶段 fib_select_multipath() 据此选择 nexthop。

本文基于 Linux v6.16 源码（net/ipv4/route.c），逐一解析 4 种 hash 策略的完整实现。

关于 ECMP 选路机制的整体架构，参见 ECMP选路: fib_select_multipath Hash 机制深度解析。

二、函数入口 — fib_multipath_hash()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* net/ipv4/route.c */
2066 int fib_multipath_hash(const struct net *net, const struct flowi4 *fl4,
2067                        const struct sk_buff *skb, struct flow_keys *flkeys)
2068 {
2069         u32 multipath_hash = fl4 ? fl4->flowi4_multipath_hash : 0;
2070         struct flow_keys hash_keys;
2071         u32 mhash = 0;
2072
2073         switch (READ_ONCE(net->ipv4.sysctl_fib_multipath_hash_policy)) {
2074         case 0: /* L3 hash */
2086         case 1: /* L4 hash */
2127         case 2: /* L3 inner (tunnel) */
2153         case 3: /* Custom hash */
2159         }
2160
2161         if (multipath_hash)
2162                 mhash = jhash_2words(mhash, multipath_hash, 0);
2163
2164         return mhash >> 1;  /* 右移1位，保证非负（最高位为0）*/
2165 }

关键点：

  • sysctl_fib_multipath_hash_policy 控制使用哪种策略（0/1/2/3）
  • flowi4_multipath_hash 允许上层预设 hash（非零时与计算结果做二次混合）
  • 最终 mhash >> 1 保证返回值为正整数（最高位置 0），因为 fib_select_multipath() 中的 upper_bound 使用 [0, 2^31-1] 区间

三、Policy 0：L3 Hash（默认）

仅用 源IP + 目的IP 做 hash。对 ICMP 错误报文特殊处理（用内层 IP）。

3.1 代码

1
2
3
4
5
6
7
8
9
10
11
12
/* net/ipv4/route.c */
2074         case 0:
2075                 memset(&hash_keys, 0, sizeof(hash_keys));
2076                 hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
2077                 if (skb) {
2078                         ip_multipath_l3_keys(skb, &hash_keys);
2079                 } else {
2080                         hash_keys.addrs.v4addrs.src = fl4->saddr;
2081                         hash_keys.addrs.v4addrs.dst = fl4->daddr;
2082                 }
2083                 mhash = fib_multipath_hash_from_keys(net, &hash_keys);
2084                 break;

逻辑分支：

  • 有 skb（转发路径）：调用 ip_multipath_l3_keys() 从报文中提取源/目的 IP
  • 无 skb（本地发包）：直接使用 flowi4 中的 saddr/daddr

3.2 ICMP 特殊处理 — ip_multipath_l3_keys()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/* net/ipv4/route.c */
1910 static void ip_multipath_l3_keys(const struct sk_buff *skb,
1911                                  struct flow_keys *hash_keys)
1912 {
1913         const struct iphdr *outer_iph = ip_hdr(skb);
1914         const struct iphdr *key_iph = outer_iph;
1915         const struct iphdr *inner_iph;
1916         const struct icmphdr *icmph;
1917         struct iphdr _inner_iph;
1918         struct icmphdr _icmph;
1919
1920         if (likely(outer_iph->protocol != IPPROTO_ICMP))
1921                 goto out;
1922
1923         if (unlikely((outer_iph->frag_off & htons(IP_OFFSET)) != 0))
1924                 goto out;
1925
1926         icmph = skb_header_pointer(skb, outer_iph->ihl * 4, sizeof(_icmph),
1927                                    &_icmph);
1928         if (!icmph)
1929                 goto out;
1930
1931         if (!icmp_is_err(icmph->type))
1932                 goto out;
1933
1934         inner_iph = skb_header_pointer(skb,
1935                                        outer_iph->ihl * 4 + sizeof(_icmph),
1936                                        sizeof(_inner_iph), &_inner_iph);
1937         if (!inner_iph)
1938                 goto out;
1939
1940         key_iph = inner_iph;
1941 out:
1942         hash_keys->addrs.v4addrs.src = key_iph->saddr;
1943         hash_keys->addrs.v4addrs.dst = key_iph->daddr;
1944 }

ICMP 错误报文处理流程：

  1. 如果不是 ICMP 协议 → 直接用外层 IP 头的 saddr/daddr
  2. 如果是 ICMP 分片（非首片）→ 无法解析内层，用外层
  3. 检查是否为 ICMP 错误 报文（icmp_is_err()：Destination Unreachable / Time Exceeded / Redirect / Parameter Problem）
  4. 如果是错误报文 → 提取 ICMP payload 中 被包裹的原始 IP 头，使用其 saddr/daddr

为什么要这样做？ ICMP 错误报文的外层 saddr 是报告错误的路由器，daddr 是原始发送方。如果用外层地址做 hash，ICMP 错误可能走到与原始流量不同的路径上。用内层（原始数据包）的地址做 hash，保证 ICMP 错误走回原始流的相同路径。

四、Policy 1：L4 Hash（五元组）

用 源IP + 目的IP + 协议号 + 源端口 + 目的端口 做 hash，提供更细粒度的流量分散。

4.1 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* net/ipv4/route.c */
2086         case 1:
2087                 /* skb is currently provided only when forwarding */
2088                 if (skb) {
2089                         unsigned int flag = FLOW_DISSECTOR_F_STOP_AT_ENCAP;
2090                         struct flow_keys keys;
2091
2092                         /* short-circuit if we already have L4 hash present */
2093                         if (skb->l4_hash)
2094                                 return skb_get_hash_raw(skb) >> 1;
2095
2096                         memset(&hash_keys, 0, sizeof(hash_keys));
2097
2098                         if (!flkeys) {
2099                                 skb_flow_dissect_flow_keys(skb, &keys, flag);
2100                                 flkeys = &keys;
2101                         }
2102
2103                         hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
2104                         hash_keys.addrs.v4addrs.src = flkeys->addrs.v4addrs.src;
2105                         hash_keys.addrs.v4addrs.dst = flkeys->addrs.v4addrs.dst;
2106                         hash_keys.ports.src = flkeys->ports.src;
2107                         hash_keys.ports.dst = flkeys->ports.dst;
2108                         hash_keys.basic.ip_proto = flkeys->basic.ip_proto;
2109                 } else {
2110                         memset(&hash_keys, 0, sizeof(hash_keys));
2111                         hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
2112                         hash_keys.addrs.v4addrs.src = fl4->saddr;
2113                         hash_keys.addrs.v4addrs.dst = fl4->daddr;
2114                         if (fl4->flowi4_flags & FLOWI_FLAG_ANY_SPORT)
2115                                 hash_keys.ports.src = (__force __be16)get_random_u16();
2116                         else
2117                                 hash_keys.ports.src = fl4->fl4_sport;
2118                         hash_keys.ports.dst = fl4->fl4_dport;
2119                         hash_keys.basic.ip_proto = fl4->flowi4_proto;
2120                 }
2121                 mhash = fib_multipath_hash_from_keys(net, &hash_keys);
2122                 break;

4.2 转发路径（有 skb）逻辑

  1. 快速路径：如果 skb 已经有 L4 hash（skb->l4_hash 为真），直接返回 skb_get_hash_raw(skb) >> 1，避免重复解析
  2. 使用 FLOW_DISSECTOR_F_STOP_AT_ENCAP 标志 —— 只解析到封装层为止，不深入隧道内层
  3. 如果调用方已经传入了 flkeys（预解析的 flow keys），直接复用，不再重新解析

4.3 本地发包路径（无 skb）逻辑

  • 直接从 flowi4 中提取五元组
  • 关键细节：当 FLOWI_FLAG_ANY_SPORT 标志位被设置时，源端口用 get_random_u16() 随机化

FLOWI_FLAG_ANY_SPORT 的场景：tcp_v4_connect() 的第 1 次路由查询时，端口尚未分配（wildcard），此时设置该标志。随机化源端口使得同一目的的新连接能均匀分布到不同 nexthop，避免所有到同一 daddr 的连接走同一条路径。

五、Policy 2：Inner L3 Hash（隧道场景）

对 GRE/VXLAN 等封装流量，解析 内层 IP 头 做 hash，支持 IPv4/IPv6 inner。

5.1 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* net/ipv4/route.c */
2127         case 2:
2128                 memset(&hash_keys, 0, sizeof(hash_keys));
2129                 /* skb is currently provided only when forwarding */
2130                 if (skb) {
2131                         struct flow_keys keys;
2132
2133                         skb_flow_dissect_flow_keys(skb, &keys, 0);
2134                         /* Inner can be v4 or v6 */
2135                         if (keys.control.addr_type == FLOW_DISSECTOR_KEY_IPV4_ADDRS) {
2136                                 hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
2137                                 hash_keys.addrs.v4addrs.src = keys.addrs.v4addrs.src;
2138                                 hash_keys.addrs.v4addrs.dst = keys.addrs.v4addrs.dst;
2139                         } else if (keys.control.addr_type == FLOW_DISSECTOR_KEY_IPV6_ADDRS) {
2140                                 hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
2141                                 hash_keys.addrs.v6addrs.src = keys.addrs.v6addrs.src;
2142                                 hash_keys.addrs.v6addrs.dst = keys.addrs.v6addrs.dst;
2143                                 hash_keys.tags.flow_label = keys.tags.flow_label;
2144                                 hash_keys.basic.ip_proto = keys.basic.ip_proto;
2145                         } else {
2146                                 /* Same as case 0 */
2147                                 hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
2148                                 ip_multipath_l3_keys(skb, &hash_keys);
2149                         }
2150                 } else {
2151                         /* Same as case 0 */
2152                         hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
2153                         hash_keys.addrs.v4addrs.src = fl4->saddr;
2154                         hash_keys.addrs.v4addrs.dst = fl4->daddr;
2155                 }
2156                 mhash = fib_multipath_hash_from_keys(net, &hash_keys);
2157                 break;

5.2 解析逻辑

有 skb（转发）：

  1. 使用 skb_flow_dissect_flow_keys(skb, &keys, 0) —— flag=0 表示 深入封装，解析到最内层
  2. 根据内层地址类型分发：
    • IPv4 内层：取 inner saddr + daddr
    • IPv6 内层：取 inner saddr + daddr + flow_label + ip_proto
    • 无封装：fallback 到 Policy 0 的逻辑（ip_multipath_l3_keys）
  3. IPv6 内层比 IPv4 多用了 flow_label 和 ip_proto，因为 IPv6 的 flow label 本身就设计用于标识流

无 skb（本地发包）：

  • 本地不可能产生需要按内层 hash 的隧道封装包，所以直接退化为 Policy 0（外层 L3）

5.3 适用场景

  • GRE / VXLAN / IPIP 等隧道的中转路由器
  • 外层 IP 头的 saddr/daddr 固定（隧道两端地址），如果用 Policy 0 所有隧道流量都会走同一条路径
  • Policy 2 解析内层用户流量做 hash，实现隧道内不同流的负载均衡

六、Policy 3：Custom Hash（自定义字段）

通过 sysctl net.ipv4.fib_multipath_hash_fields 位掩码自定义参与 hash 的字段组合，支持 outer + inner 字段。

6.1 主入口代码

1
2
3
4
5
6
7
/* net/ipv4/route.c */
2158         case 3:
2159                 if (skb)
2160                         mhash = fib_multipath_custom_hash_skb(net, skb);
2161                 else
2162                         mhash = fib_multipath_custom_hash_fl4(net, fl4);
2163                 break;

6.2 有 skb 路径 — fib_multipath_custom_hash_skb()

分为 outer 和 inner 两部分分别计算，最后合并：

1
2
3
4
5
6
7
8
9
10
11
12
/* net/ipv4/route.c */
static u32 fib_multipath_custom_hash_skb(const struct net *net,
                                         const struct sk_buff *skb)
{
        u32 mhash, mhash_inner;
        bool has_inner = true;

        mhash = fib_multipath_custom_hash_outer(net, skb, &has_inner);
        mhash_inner = fib_multipath_custom_hash_inner(net, skb, has_inner);

        return jhash_2words(mhash, mhash_inner, 0);
}

Outer 部分 — fib_multipath_custom_hash_outer()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* net/ipv4/route.c */
static u32 fib_multipath_custom_hash_outer(const struct net *net,
                                           const struct sk_buff *skb,
                                           bool *p_has_inner)
{
        u32 hash_fields = READ_ONCE(net->ipv4.sysctl_fib_multipath_hash_fields);
        struct flow_keys keys, hash_keys;

        if (!(hash_fields & FIB_MULTIPATH_HASH_FIELD_OUTER_MASK))
                return 0;

        memset(&hash_keys, 0, sizeof(hash_keys));
        skb_flow_dissect_flow_keys(skb, &keys, FLOW_DISSECTOR_F_STOP_AT_ENCAP);

        hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_SRC_IP)
                hash_keys.addrs.v4addrs.src = keys.addrs.v4addrs.src;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_DST_IP)
                hash_keys.addrs.v4addrs.dst = keys.addrs.v4addrs.dst;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_IP_PROTO)
                hash_keys.basic.ip_proto = keys.basic.ip_proto;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_SRC_PORT)
                hash_keys.ports.src = keys.ports.src;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_DST_PORT)
                hash_keys.ports.dst = keys.ports.dst;

        *p_has_inner = !!(keys.control.flags & FLOW_DIS_ENCAPSULATION);
        return fib_multipath_hash_from_keys(net, &hash_keys);
}

按位掩码逐字段判断是否参与 hash，只提取 hash_fields 中启用的字段。

Inner 部分 — fib_multipath_custom_hash_inner()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/* net/ipv4/route.c */
static u32 fib_multipath_custom_hash_inner(const struct net *net,
                                           const struct sk_buff *skb,
                                           bool has_inner)
{
        u32 hash_fields = READ_ONCE(net->ipv4.sysctl_fib_multipath_hash_fields);
        struct flow_keys keys, hash_keys;

        if (!has_inner)
                return 0;

        if (!(hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_MASK))
                return 0;

        memset(&hash_keys, 0, sizeof(hash_keys));
        skb_flow_dissect_flow_keys(skb, &keys, 0);

        if (!(keys.control.flags & FLOW_DIS_ENCAPSULATION))
                return 0;

        if (keys.control.addr_type == FLOW_DISSECTOR_KEY_IPV4_ADDRS) {
                hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
                if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_SRC_IP)
                        hash_keys.addrs.v4addrs.src = keys.addrs.v4addrs.src;
                if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_DST_IP)
                        hash_keys.addrs.v4addrs.dst = keys.addrs.v4addrs.dst;
        } else if (keys.control.addr_type == FLOW_DISSECTOR_KEY_IPV6_ADDRS) {
                hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_SRC_IP)
                        hash_keys.addrs.v6addrs.src = keys.addrs.v6addrs.src;
                if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_DST_IP)
                        hash_keys.addrs.v6addrs.dst = keys.addrs.v6addrs.dst;
                if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_FLOWLABEL)
                        hash_keys.tags.flow_label = keys.tags.flow_label;
        }

        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_IP_PROTO)
                hash_keys.basic.ip_proto = keys.basic.ip_proto;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_SRC_PORT)
                hash_keys.ports.src = keys.ports.src;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_INNER_DST_PORT)
                hash_keys.ports.dst = keys.ports.dst;

        return fib_multipath_hash_from_keys(net, &hash_keys);
}

6.3 无 skb 路径 — fib_multipath_custom_hash_fl4()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* net/ipv4/route.c */
static u32 fib_multipath_custom_hash_fl4(const struct net *net,
                                         const struct flowi4 *fl4)
{
        u32 hash_fields = READ_ONCE(net->ipv4.sysctl_fib_multipath_hash_fields);
        struct flow_keys hash_keys;

        if (!(hash_fields & FIB_MULTIPATH_HASH_FIELD_OUTER_MASK))
                return 0;

        memset(&hash_keys, 0, sizeof(hash_keys));
        hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_SRC_IP)
                hash_keys.addrs.v4addrs.src = fl4->saddr;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_DST_IP)
                hash_keys.addrs.v4addrs.dst = fl4->daddr;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_IP_PROTO)
                hash_keys.basic.ip_proto = fl4->flowi4_proto;
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_SRC_PORT) {
                if (fl4->flowi4_flags & FLOWI_FLAG_ANY_SPORT)
                        hash_keys.ports.src = (__force __be16)get_random_u16();
                else
                        hash_keys.ports.src = fl4->fl4_sport;
        }
        if (hash_fields & FIB_MULTIPATH_HASH_FIELD_DST_PORT)
                hash_keys.ports.dst = fl4->fl4_dport;

        return fib_multipath_hash_from_keys(net, &hash_keys);
}

注意 FLOWI_FLAG_ANY_SPORT 的随机化逻辑与 Policy 1 一致。

6.4 可配置字段一览

net.ipv4.fib_multipath_hash_fields 是一个位掩码，可选字段包括：

位掩码常量 含义
FIB_MULTIPATH_HASH_FIELD_SRC_IP 外层源 IP
FIB_MULTIPATH_HASH_FIELD_DST_IP 外层目的 IP
FIB_MULTIPATH_HASH_FIELD_IP_PROTO 外层协议号
FIB_MULTIPATH_HASH_FIELD_SRC_PORT 外层源端口
FIB_MULTIPATH_HASH_FIELD_DST_PORT 外层目的端口
FIB_MULTIPATH_HASH_FIELD_INNER_SRC_IP 内层源 IP
FIB_MULTIPATH_HASH_FIELD_INNER_DST_IP 内层目的 IP
FIB_MULTIPATH_HASH_FIELD_INNER_IP_PROTO 内层协议号
FIB_MULTIPATH_HASH_FIELD_INNER_SRC_PORT 内层源端口
FIB_MULTIPATH_HASH_FIELD_INNER_DST_PORT 内层目的端口
FIB_MULTIPATH_HASH_FIELD_INNER_FLOWLABEL 内层 IPv6 flow label

默认值 FIB_MULTIPATH_HASH_FIELD_DEFAULT_MASK = SRC_IP | DST_IP | IP_PROTO（即 L3 + 协议号）。

七、Hash 算法本身 — fib_multipath_hash_from_keys()

7.1 代码

定义在 include/net/ip_fib.h，根据是否配置了 CONFIG_IP_ROUTE_MULTIPATH 有两种实现：

有 seed 配置的版本（CONFIG_IP_ROUTE_MULTIPATH 启用时）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* include/net/ip_fib.h */
static void
fib_multipath_hash_construct_key(siphash_key_t *key, u32 mp_seed)
{
        u64 mp_seed_64 = mp_seed;

        key->key[0] = (mp_seed_64 << 32) | mp_seed_64;
        key->key[1] = key->key[0];
}

static inline u32 fib_multipath_hash_from_keys(const struct net *net,
                                               struct flow_keys *keys)
{
        siphash_aligned_key_t hash_key;
        u32 mp_seed;

        mp_seed = READ_ONCE(net->ipv4.sysctl_fib_multipath_hash_seed).mp_seed;
        fib_multipath_hash_construct_key(&hash_key, mp_seed);

        return flow_hash_from_keys_seed(keys, &hash_key);
}

无 seed 的版本（fallback）：

1
2
3
4
5
static inline u32 fib_multipath_hash_from_keys(const struct net *net,
                                               struct flow_keys *keys)
{
        return flow_hash_from_keys(keys);
}

7.2 算法选择

  • 有 seed：使用 SipHash 算法（flow_hash_from_keys_seed()），128-bit key 由 32-bit seed 扩展而来
  • 无 seed：使用 jhash2（Jenkins Hash），这是内核中广泛使用的通用 hash 函数

7.3 Seed 的作用 — 防极化

seed 可通过 net.ipv4.fib_multipath_hash_seed sysctl 配置。

极化问题（Polarization）：在多跳 ECMP 拓扑中，如果每一跳路由器使用相同的 hash 算法和 seed，对同一个五元组会计算出相同的 hash 值，导致：

  • 所有路由器对同一流量做出 相同的路径选择
  • 某些链路过载，其他链路空闲
  • ECMP 的负载均衡效果大打折扣

解决方案：为每一跳路由器配置不同的 seed，相同的流量在不同路由器上产生不同的 hash 值，从而选择不同的路径。

1
2
3
4
5
# 路由器 A
sysctl -w net.ipv4.fib_multipath_hash_seed=12345

# 路由器 B
sysctl -w net.ipv4.fib_multipath_hash_seed=67890

7.4 Seed 扩展方式

32-bit seed 扩展为 128-bit SipHash key 的方式很简单：

1
2
3
seed_64 = (seed << 32) | seed      // 32-bit → 64-bit: 高低各放一份
key[0] = seed_64                   // 128-bit key 的两个 64-bit 部分相同
key[1] = seed_64

八、四种策略对比总结

策略 sysctl 值 Hash 字段 适用场景 特点
L3 0 saddr + daddr 通用默认 简单，同源同目的走同一路径
L4 1 五元组 双 ISP / 数据中心 per-flow 分散，粒度最细
Inner L3 2 内层 saddr + daddr GRE/VXLAN 中转 解决隧道两端地址固定的问题
Custom 3 位掩码自定义 高级定制 最灵活，支持 outer + inner