Understanding Linux Network Internals

Effects of Multipath on Next Hop Selection

In both ip_route_input_slow and ip_route_output_slow, fib_select_multipath is called only when:

• Multipath support is included in the kernel (CONFIG_IP_ROUTE_MULTIPATH).

• The routing lookup with fib_lookup returns a route with more than one next hop (fib_nhs> 1).

• The egress interface was not provided with the search key.

• The destination address is not a local, broadcast, or multicast address.

The following code shows how fib_select_multipath is called to select the next hop:

#ifdef CONFIG_IP_ROUTE_MULTIPATH
    if (res.fi->fib_nhs > 1 && fl.oif == 0)
        fib_select_multipath(&key, &res);
#endif

We already saw in the section "Next Hop Selection" in Chapter 31 how Linux selects the next hop to use when more than one is available. Let's see now how that algorithm is implemented.

We saw in the section "Organization of Routing Hash Tables" in Chapter 34 that a route is represented by the closely coupled data structures fib_node and fib_info, and that each fib_info includes an array of fib_nh data structures (one for each next hop specified in the route).

First, let's clarify which fields of the fib_info and fib_nh structures are used to decide whether a next hop must be chosen among a pool of available next hops, and if so, which one is chosen.

These are the fields used to store the multipath configuration:

fib_info->fib_nhs

Number of next hops defined by the route.

fib_info->fib_nh

Array of fib_nh structures. The size of the array is given by fib_info->fib_nhs ...