vault

IP Routing Decision and Forwarding

17 min read

IP Routing Decision and Forwarding

Every IPv4 packet the kernel touches must answer one question before it can move: where does this go next? The routing decision is the act of consulting the Forwarding Information Base (FIB) for a given packet and producing a verdict — deliver it locally, forward it to a next-hop, or drop it — bundled into a struct rtable (a routing-table cache entry wrapping a generic struct dst_entry) that is then attached to the packet’s struct sk_buff. On the receive side this is ip_route_input_noref() → ip_route_input_slow(); on the transmit side it is ip_route_output_flow() → ip_route_output_key_hash_rcu(). Both ultimately call fib_lookup() and then build a dst whose input/output function pointers are the decision: ip_local_deliver, ip_forward, or ip_error. Since Linux 3.6 there is no global route cache — the lookup runs essentially per-packet against the FIB trie, with only a thin per-next-hop dst cache softening the cost (DaveM, netdev 2012-07-01). Verified against net/ipv4/route.c at the v6.12 LTS tag.

Mental Model

Think of the routing decision as a function that maps a flow key (mostly the destination IP, plus a handful of secondary fields) to a behaviour (a pair of function pointers and a device). The FIB is the read-mostly lookup table; the dst_entry is the compiled answer the packet carries so that downstream code (dst_input(skb) / dst_output(net, sk, skb)) does not re-derive it. The crucial structural fact is that the decision is encoded as code, not data: rth->dst.input = ip_local_deliver means “this packet is for us,” ip_forward means “route it onward,” ip_error means “send an ICMP unreachable.” The stack just calls skb_dst(skb)->input(skb) and the right thing happens.

flowchart TB
  RX["Frame arrives<br/>ip_rcv → ip_rcv_finish_core"] --> HASDST{"skb already<br/>has a dst?<br/>(early demux / hint)"}
  HASDST -->|"yes"| USE["use cached dst"]
  HASDST -->|"no"| IRIN["ip_route_input_noref()<br/>build flowi4 key:<br/>daddr/saddr/tos/iif/mark"]
  IRIN --> FIB["fib_lookup()<br/>longest-prefix match<br/>in the FIB trie"]
  FIB --> TYPE{"res.type?"}
  TYPE -->|"RTN_LOCAL"| LOCAL["dst.input = ip_local_deliver<br/>→ up to TCP/UDP"]
  TYPE -->|"RTN_UNICAST<br/>+ ip_forward=1"| FWD["dst.input = ip_forward<br/>→ decrement TTL, re-emit"]
  TYPE -->|"unreachable /<br/>forwarding off"| ERR["dst.input = ip_error<br/>→ ICMP unreachable / drop"]
  LOCAL --> DSTIN["dst_input(skb)<br/>calls skb_dst(skb)->input(skb)"]
  FWD --> DSTIN
  ERR --> DSTIN

The receive-side routing decision. What it shows: after ip_rcv validates the header, ip_rcv_finish_core() either reuses a dst (from TCP/UDP early-demux or a batched lookup hint) or calls ip_route_input_noref(), which performs the FIB lookup and selects a dst whose input pointer encodes the fate of the packet. The insight to take: the three classic outcomes — local-deliver, forward, drop — are not if/else branches scattered through the stack; they are three different dst.input function pointers chosen once at routing time, after which dst_input(skb) dispatches uniformly. (Code path verified against net/ipv4/ip_input.c and net/ipv4/route.c, v6.12.)

The Routing Key — struct flowi4

A route lookup is not “look up the destination IP.” Linux routes on a flow key, struct flowi4, assembled fresh for each lookup. In ip_route_input_slow() the key is built field-by-field (net/ipv4/route.c, v6.12):

fl4.flowi4_l3mdev = 0;
fl4.flowi4_oif    = 0;            /* output interface: 0 = let routing pick */
fl4.flowi4_iif    = dev->ifindex; /* input interface */
fl4.flowi4_mark   = skb->mark;    /* firewall/conntrack mark for policy routing */
fl4.flowi4_tos    = tos;          /* Type-of-Service / DSCP bits */
fl4.flowi4_scope  = RT_SCOPE_UNIVERSE;
fl4.daddr = daddr;                /* destination — the primary match key */
fl4.saddr = saddr;                /* source — used for source validation / rules */

The fields that actually steer the decision are:

  • daddr — the destination address. This is the only field the basic FIB trie matches on (longest-prefix). Everything else is a filter or a policy-rule selector.
  • saddr — the source. The plain main-table lookup ignores it for the route, but it drives reverse-path validation (below) and policy rules (from selectors, see Policy Routing and Multiple Tables).
  • flowi4_tos — the Type-of-Service / DSCP byte. A route added with tos/dscp only matches packets carrying that value, so TOS can split traffic across routes.
  • flowi4_oif — output interface. On output lookups a nonzero oif constrains the route to that device; on input it is 0.
  • flowi4_mark — the skb->mark (a 32-bit tag set by netfilter, tc, or sockets). It is meaningless to the FIB trie itself but is a first-class selector for policy routing rules (ip rule add fwmark ... lookup ...), which is how fwmark-based routing works.

Uncertain

Verify: the precise set of flowi4 fields that participate in the plain main-table FIB-trie match versus those used only by rules (fib4_rules). Reason: fib_table_lookup() matches on daddr (longest prefix) and filters on tos/dscp and scope; saddr/mark/oif enter mainly through __fib_lookup() → fib_rules_lookup() when CONFIG_IP_MULTIPLE_TABLES and custom rules exist. The boundary is config- and rule-dependent. To resolve: trace fib_table_lookup() in net/ipv4/fib_trie.c (matches flp->daddr, flp->flowi4_tos/fa_dscp, flowi4_scope) against fib4_rule_match() in net/ipv4/fib_rules.c. uncertain

Mechanical Walk-through — The Input Path

When a frame is determined to be IPv4, ip_rcv() runs sanity checks (version, header length, checksum, total length) in ip_rcv_core(), then hands the packet to ip_rcv_finish() via the NF_INET_PRE_ROUTING netfilter hook. ip_rcv_finish() calls ip_rcv_finish_core() (net/ipv4/ip_input.c, v6.12), which is where the routing decision lives.

Step 1 — can we skip the lookup? Two shortcuts can pre-populate skb’s dst so no FIB lookup is needed. The first is the lookup hint (ip_can_use_hint() / ip_route_use_hint()): when a list of packets is processed together (ip_list_rcv), a packet with the same destination as its predecessor reuses the predecessor’s route. The second is early demux: for TCP and UDP, if sysctl_ip_early_demux is on and the packet is not a fragment, tcp_v4_early_demux() / udp_v4_early_demux() try to find the owning struct sock directly and borrow its cached dst, skipping routing entirely for established connections. Both are pure optimizations; if neither fires, skb_valid_dst(skb) is false and the real lookup runs.

Step 2 — ip_route_input_noref(). This masks the TOS to the DSCP bits, takes the RCU read lock, and calls ip_route_input_rcu(). Multicast destinations are split off to ip_route_input_mc(); everything else falls through to ip_route_input_slow() — the heart of the decision (net/ipv4/route.c, v6.12).

Step 3 — martian and special-address checks. Before any FIB lookup, ip_route_input_slow() rejects “martian” sources (multicast or limited-broadcast source addresses, zeronet sources) and martian destinations (zeronet destination, loopback addresses arriving on a non-loopback device unless route_localnet is set). Limited broadcast (255.255.255.255) and the all-zeros pair short-circuit to brd_input. These are RFC 1812 sanity rules that the FIB trie cannot easily express.

Step 4 — fib_lookup(). The flow key is passed to fib_lookup(net, &fl4, res, 0). This is the longest-prefix-match against the FIB trie, returning a struct fib_result whose type field is the verdict — RTN_LOCAL, RTN_UNICAST, RTN_BROADCAST, RTN_UNREACHABLE, etc. If fib_lookup() returns nonzero (no route) and forwarding is off, the error becomes -EHOSTUNREACH; otherwise it jumps to no_route, which sets res.type = RTN_UNREACHABLE and falls into the local-input path so an ICMP error can be generated. The mechanics of how fib_lookup() walks the trie and chooses a next-hop are owned by The Routing Subsystem and FIB.

Step 5 — branch on res.type.

  • RTN_LOCAL → call fib_validate_source() (reverse-path check, below); on success goto local_input, which allocates an rtable with dst.input = ip_local_deliver so the packet climbs to the transport layer. The host is the destination.
  • RTN_UNICAST with IN_DEV_FORWARD(in_dev) true → goto make_route → ip_mkroute_input(), which (possibly after ECMP next-hop selection) allocates an rtable with dst.input = ip_forward. The packet is not for us; we are a router for it.
  • Forwarding disabled (!IN_DEV_FORWARD) → err = -EHOSTUNREACH, goto no_route. The packet is dropped (and an ICMP unreachable may be sent). This is exactly why a host with ip_forward=0 silently swallows transit traffic.
  • Non-unicast, non-local (e.g. an address the FIB calls unreachable) → goto martian_destination.

Step 6 — build and cache the dst. The local_input/make_route paths call rt_dst_alloc() to allocate the rtable, set its input/output pointers, and — if the next-hop and result are cacheable (do_cache) — store it in the next-hop’s per-CPU/per-nexthop dst slot via rt_cache_route() (see caching, below). Finally skb_dst_set(skb, &rth->dst) attaches the answer to the packet. Back in ip_rcv_finish(), dst_input(skb) calls skb_dst(skb)->input(skb) — ip_local_deliver, ip_forward, or ip_error — and the packet continues.

The Output Path — ip_route_output_flow()

A locally generated packet (a send()/connect(), an ICMP reply, a SYN from this host) routes through the output side. The entry point most callers use is ip_route_output_flow(net, flp4, sk), which wraps __ip_route_output_key() → ip_route_output_key_hash() → ip_route_output_key_hash_rcu() (net/ipv4/route.c, v6.12). The structure mirrors input but the constraints differ:

  • If the caller supplied a source address (fl4->saddr), it is validated to be a local address (__ip_dev_find()), unless FLOWI_FLAG_ANYSRC is set. You cannot normally send from an address you do not own.
  • If the caller supplied an output interface (fl4->flowi4_oif), the device is looked up and must be IFF_UP; multicast/broadcast/IGMP destinations can shortcut to make_route with an auto-selected source via inet_select_addr().
  • If there is no destination (!fl4->daddr), the route is forced to loopback (INADDR_LOOPBACK, RTN_LOCAL) — this is how connect() to a local address or 0.0.0.0 resolves.
  • Otherwise fib_lookup() runs. RTN_LOCAL results route via the loopback device (the packet never hits the wire); unicast results call fib_select_path() to pick a next-hop (and an ECMP member if the route is multipath, see The Routing Subsystem and FIB). Then __mkroute_output() builds the rtable with dst.output set appropriately (ip_output for the normal egress path).

The output dst is what TCP caches on the socket (sk->sk_dst_cache) so that a long-lived connection does not re-route every segment — the socket-level equivalent of the old route cache.

Forwarding — ip_forward() in Detail

When the route says dst.input = ip_forward, transit packets land in ip_forward() (net/ipv4/ip_forward.c, v6.12). The sequence:

  1. Sanity drops. Drop if pkt_type != PACKET_HOST (the frame was not addressed to our MAC), if skb->sk is set (a forwarded packet should not be socket-owned), or if it failed XFRM/IPsec forward policy.
  2. TTL check (the hop limit). if (ip_hdr(skb)->ttl <= 1) goto too_many_hops; — a packet arriving with TTL 1 cannot be forwarded; the router emits ICMP_TIME_EXCEEDED/ICMP_EXC_TTL and drops it. This is the mechanism that makes traceroute work: each hop decrements TTL and the hop that hits zero reports itself.
  3. MTU / fragmentation-needed. ip_exceeds_mtu() checks the outgoing route’s MTU. If the packet is larger and has the Don’t-Fragment bit set, the router sends ICMP_DEST_UNREACH/ICMP_FRAG_NEEDED carrying the MTU — the signal that drives Path MTU Discovery — and drops it.
  4. Copy-on-write + TTL decrement. skb_cow() ensures the header is writable (the buffer may be shared/cloned), then ip_decrease_ttl(iph) decrements TTL and incrementally updates the IP header checksum (TTL is a header field, so the checksum must change). The decrement happens after the COW so we never mutate a shared buffer.
  5. ICMP redirect. If IPSKB_DOREDIRECT is set (the packet is being sent back out the interface it came in on, toward a better gateway on the same subnet), ip_rt_send_redirect() emits an ICMP_REDIRECT advising the sender of the better next-hop.
  6. The FORWARD hook and transmit. Finally NF_HOOK(NFPROTO_IPV4, NF_INET_FORWARD, ...) runs the netfilter FORWARD chain; if accepted, ip_forward_finish() → dst_output() sends the packet out the chosen interface. The next-hop’s MAC is resolved by the neighbour subsystem (ARP) at transmit time.

The master switch is net.ipv4.ip_forward, which gates IN_DEV_FORWARD. Per the kernel docs it is “special, its change resets all configuration parameters to their default state” and defaults to 0 (ip-sysctl.html). Without it, RTN_UNICAST transit packets are dropped at step 5 of the input walk-through, never reaching ip_forward() at all.

Reverse-Path Filtering (rp_filter)

Both locally-destined and forwarded packets run fib_validate_source() → __fib_validate_source() (net/ipv4/fib_frontend.c, v6.12) to defend against source-address spoofing. For RTN_LOCAL/broadcast packets the call is made directly in ip_route_input_slow(); for transit unicast it happens inside __mkroute_input() (net/ipv4/route.c line ~1788, v6.12) — the function on the make_route → ip_mkroute_input() forward path. This matters: reverse-path filtering protects a router against spoofed transit traffic, not just a host against spoofed local-destined traffic. The idea (RFC 3704) is: if I reverse the lookup — route back toward the packet’s claimed source — does the answer point out the interface the packet actually arrived on? If not, the source is implausible and the packet is dropped with -EXDEV, which ip_rcv_finish_core() maps to SKB_DROP_REASON_IP_RPFILTER and counts in LINUX_MIB_IPRPFILTER.

The behaviour is controlled by the rp_filter sysctl, whose effective value is max(conf/all/rp_filter, conf/<iface>/rp_filter) (ip-sysctl.html):

  • 0 — no source validation.
  • 1 — strict mode (RFC 3704 Strict Reverse Path): the packet must arrive on the interface that is the best reverse route. In __fib_validate_source() this is the if (rpf == 1) goto e_rpf; branch — if the input device does not match the reverse-lookup’s device, it fails immediately.
  • 2 — loose mode (RFC 3704 Loose Reverse Path): the source need only be reachable via some interface, not necessarily the one it arrived on. The code retries the lookup with FIB_LOOKUP_IGNORE_LINKSTATE and only fails if no route to the source exists at all. Loose mode is the correct choice under asymmetric routing (the return path differs from the forward path), where strict mode would wrongly drop legitimate traffic.

The kernel default is 0, but most distributions ship rp_filter=1 or 2 via /etc/sysctl.d, so the “default” you observe depends on the distro, not the kernel.

Uncertain

Verify: that mainstream distributions still default rp_filter to a nonzero value as of 2026 (historically Fedora/RHEL set 1, Debian/Ubuntu vary; systemd has set strict mode in the past). Reason: this is a userspace/distro policy file, not a kernel constant, and it drifts. To resolve: read /proc/sys/net/ipv4/conf/all/rp_filter and the distro’s sysctl.d on the target system. uncertain

Why There Is No Route Cache Anymore (3.6)

Through Linux 3.5 the kernel kept a global, hashed route cache (rt_hash_table): every distinct flow that was routed got a cache entry keyed on the full flow tuple, so repeat lookups were O(1) hash hits. David S. Miller removed it in 3.6: the patch “ipv4: Delete routing cache” was posted 2012-07-01 (netdev — I read the patch text; it deletes ~1000 lines including rt_hash_table, rt_garbage_collect(), and rt_check_expire()) and he later presented the rationale in his 2013 “The Routing Cache is Dead, Now What?” netfilter-workshop slides (title/author/date confirmed from the PDF metadata; the slide body would not convert — see flag). The cache was a security and performance liability: it grew unboundedly under traffic, its garbage collector was complex and DoS-prone (per thermalcircle part 2, “you could easily fill the cache with entries basically by sending packets to random destinations”), and it required a global lock/genid scheme that hurt scaling on many cores. Removal became feasible once the FIB-trie lookup was optimized in 2.6.39 (thermalcircle part 2).

Uncertain

Verify: the finer rationale in DaveM’s “The Routing Cache is Dead, Now What?” slides. Reason: the PDF’s binary did not convert to text via fetch, so only its title/author/date metadata was confirmed; the 3.6-removal facts here rest on the openwall patch text and thermalcircle part 2, both of which I read in full. To resolve: open the PDF directly. uncertain

The replacement model is per-lookup against the FIB trie, which was already fast (longest-prefix in O(W) where W is the address width), made faster and SMP-friendly with RCU. What survives is a much smaller cache: each FIB next-hop (fib_nh_common) carries a per-CPU output dst (nhc_pcpu_rth_output) and a single input dst (nhc_rth_input). When ip_route_input_slow()/__mkroute_output() builds a dst, rt_cache_route() tries to store it in that slot with a cmpxchg; the next packet to the same next-hop reuses it if rt_cache_valid() (the genid still matches). This is a next-hop cache, not a flow cache — it has a tiny, bounded footprint and cannot be exhausted by a flood of distinct destination addresses, which is precisely why it replaced the old design (thermalcircle part 2). Sockets and TCP additionally cache their own output dst (sk_dst_cache), and IP-fragment/PMTU exceptions live in a separate per-next-hop nhc_exceptions hash.

The dst_entry / rtable Result

The product of a routing decision is a struct rtable (include/net/route.h, v6.12) whose first member is a generic struct dst_entry (include/net/dst.h). The fields that matter:

  • dst.input / dst.output — the function pointers that are the verdict (ip_local_deliver, ip_forward, ip_error; ip_output on egress).
  • dst.dev — the output network device.
  • dst.obsolete — DST_OBSOLETE_NONE/_DEAD/_FORCE_CHK; a nonzero value forces dst_ops->check() re-validation, the mechanism by which a cached dst is invalidated when routes change.
  • rt_type — RTN_UNICAST/RTN_LOCAL/RTN_BROADCAST/RTN_MULTICAST/RTN_UNREACHABLE.
  • rt_flags — RTCF_LOCAL, RTCF_BROADCAST, RTCF_DOREDIRECT, etc.
  • rt_is_input — 1 if this dst was built on the input path (selects nhc_rth_input vs the per-CPU output slot in rt_cache_route()).
  • rt_uses_gateway / rt_gw4 — whether the next-hop is a gateway (off-link router) and, if so, its IPv4 address. Strict-source-route forwarding (opt->is_strictroute && rt->rt_uses_gateway) fails here.
  • rt_genid — the routing generation id; bumping the per-namespace genid is how mass invalidation (“flush the routes”) is implemented without walking every dst.

The dst is reference-counted (__rcuref). skb_dst_set() takes a reference and attaches it; skb_dst_set_noref() attaches a borrowed reference valid only under RCU (used for the cheap cached-dst fast path).

Configuration and Inspection

# Turn this host into a router (the master forwarding switch).
sysctl -w net.ipv4.ip_forward=1
 
# Reverse-path filter: 1 = strict (RFC3704), 2 = loose (asymmetric-safe).
sysctl -w net.ipv4.conf.all.rp_filter=2
sysctl -w net.ipv4.conf.eth0.rp_filter=2   # effective = max(all, eth0)
 
# Ask the kernel to *show its routing decision* for a packet, without
# sending anything. This runs the real fib_lookup() machinery:
ip route get 8.8.8.8
#   8.8.8.8 via 192.168.1.1 dev eth0 src 192.168.1.50 uid 1000
#       cache
# 'via' = next-hop gateway, 'dev' = output interface (dst.dev),
# 'src' = chosen source address, 'cache' = a per-nexthop dst was used.
 
ip route get 8.8.8.8 from 10.0.0.1 iif eth1 mark 0x10
#   ^ exercises saddr / iif / fwmark as part of the flow key (policy routing)

ip route get is the single best diagnostic: it invokes inet_rtm_getroute() which calls the same ip_route_input_rcu()/ip_route_output_key_hash_rcu() paths as a real packet (net/ipv4/route.c), so its output is the actual decision, not a guess.

Failure Modes and Diagnosis

  • Transit packets vanish silently. Almost always ip_forward=0. The input walk-through drops RTN_UNICAST packets with -EHOSTUNREACH before ip_forward() runs, so no ICMP is even generated by default. Fix: sysctl net.ipv4.ip_forward=1.
  • Legitimate traffic dropped on a multi-homed host / asymmetric path. rp_filter=1 (strict) drops packets whose source’s best reverse route points out a different interface. Symptom: IPRPFILTER increments in nstat//proc/net/netstat, drop reason SKB_DROP_REASON_IP_RPFILTER. Fix: set rp_filter=2 (loose) or 0, or fix routing symmetry.
  • ip route get says unreachable. No matching FIB entry and forwarding context disallows it — check the route exists and the right table/rule selects it (Policy Routing and Multiple Tables).
  • Forwarding works but is slow / per-packet expensive. Without the old route cache, every packet does a trie lookup; on a busy router this is normal and expected. The mitigations are the per-next-hop dst cache (automatic), the netfilter flowtable offload, and hardware/XDP fast paths — not a return of the flow cache.
  • Martian source log spam. A packet arrived with an impossible source (e.g. a loopback or zeronet source on a real interface), logged by ip_handle_martian_source() when log_martians is on. Usually a misconfigured peer or spoofing.

See Also

Graph View

Backlinks