Policy Routing: Keying the Lookup on More Than the Destination

Destination-based forwarding has one input. The router reads the destination address, searches one table, and forwards. That model is the reason a multi-homed network cannot balance inbound traffic, as noted in CIDR aggregation and its limits, and it is the reason a router cannot distinguish traffic from a guest network from traffic from an internal one when both arrive on the same interface. Policy routing generalises the model by allowing the lookup to be keyed on other fields and by allowing more than one table to exist.

The rule list and what it selects

The mechanism has two parts: a list of rules evaluated in order, and a set of tables. Each rule has a selector and an action. The selector describes which packets the rule applies to; the action says which table to search, or says to stop and discard. Evaluation walks the list from the lowest priority number upward, and the first rule whose selector matches the packet determines the table. The search in that table then produces a next hop, or fails, in which case evaluation continues with the next rule.

The default configuration is three rules. Priority 0 selects the local table, which holds the router’s own addresses and the broadcast entries, so a packet for the device itself is delivered rather than forwarded. Priority 32766 selects the main table, where ordinary routes are installed, and priority 32767 selects an empty table named default that serves as a fallback. Together they reproduce ordinary destination-based forwarding. Adding a rule in front of the catch-all changes the decision for the packets it matches, and leaves everything else alone. That structure is what makes the feature usable incrementally: a network can add one rule for one source prefix without rewriting its entire routing configuration.

# Route traffic from the guest prefix through the backup uplink.
ip rule add from 192.0.2.0/24 table 100 priority 1000
ip route add default via 198.51.100.1 dev eth1 table 100

# The pre-existing catch-all rule (priority 32766, lookup main) still
# handles every packet the guest rule does not match.

The priority numbers are the evaluation order, not a preference among equal matches. A rule at priority 1000 is consulted before one at 32766, and the first match wins. The spacing is convention rather than requirement; implementations allow insertion between existing rules, which is why the numbers are typically spread out.

Selectors that are available

The selector can match on source prefix, destination prefix, incoming interface, the firewall mark, and the address family. The mark is the most general of these and the least visible: it is a value that another part of the stack, usually a firewall rule, has attached to the packet, so a policy can be expressed as “packets classified as belonging to tenant 7 use table 7” without the routing table needing to know how the classification was done.

The source prefix selector is the one that solves multi-homing. An organisation with two uplinks can install two rules: traffic from the address range assigned to uplink A uses table A, and traffic from the range assigned to uplink B uses table B. Each table has a default route through its own uplink. Outbound traffic then leaves on the link that owns the source address, which is what makes provider ingress filtering survivable: the packet’s source is inside the prefix the provider expects from that link.

The incoming interface selector handles a different case. A router with two interfaces connected to networks that use overlapping address space cannot have both in one table, because the table would contain two routes for the same prefix. Giving each interface its own table resolves the ambiguity, since the lookup is keyed on where the packet arrived rather than only on where it is going. This is the mechanism behind virtual routing domains on a single device. In a provider network the same separation appears as one virtual routing and forwarding table per customer, the routing context RFC 4364 defines for VPNs, and each domain keeps its own routing information base in the sense described in route preference and the RIB.

The cost of the extra lookup

Each rule evaluation is a comparison, and the list is walked until a match. A router with a hundred rules pays for the average position of the matching rule, not for the table size. That is why long rule lists degrade forwarding in a way that large routing tables do not: the table lookup is a fixed-depth search, while the rule walk is linear in the number of rules.

Linux once hid that cost behind a route cache keyed on the packet’s addresses and other header fields, so the rule list was walked once per flow and the result reused. The cache was removed in the 3.6 kernel, and the rule list is now walked for every packet, which is why the length of the list matters directly instead of being amortised over flows. The usual mitigation is to keep the list short and do the classification once: a firewall rule sets a mark on the packet at ingress, and a single rule matching that mark selects the table. The mark is carried in the packet’s control block rather than in the header, so nothing on the wire reveals the classification.

A second cost is that each table is a separate FIB, so the memory and hardware entries multiply. A device with eight tables and a full internet table in each needs eight times the space, which is why policy routing on a full-table router is usually restricted to a small number of tables holding partial copies rather than complete ones.

Asymmetric paths become the normal case

When the outbound path is chosen by source and the inbound path by the destination announcement, the two directions can traverse different providers. The forward packet leaves through uplink A because its source is in A’s range; the reply arrives through uplink B because the destination prefix is announced there. Nothing in the routing system is inconsistent, but the stateful devices on the path see only one direction.

A firewall that tracks connections will drop the reply, because it never saw the opening packet. A NAT that rewrote the source on the way out will not see the reply’s destination match any translation. A tunnel endpoint that expects symmetric encapsulation will receive packets on an interface it did not send from. Each of these is a real consequence of a configuration that is correct at the routing layer.

The usual fix is to make the policy symmetric: the rule that selects the table for outbound traffic is paired with a rule that ensures the reply, if it arrives on the other link, is routed back out the same link rather than being forwarded by the main table. That second rule is a routing decision applied to traffic that has already been accepted, and it exists only to preserve the state that other devices built.

Policy routing is not traffic engineering

The mechanism selects a path per packet class. It does not measure the path, react to congestion, or rebalance. A rule that sends a prefix through a backup link keeps sending it there when the primary recovers, because nothing in the rule list observes link state. Making the selection dynamic requires an external process that adds and removes rules or changes table contents in response to measurements, and that process is a control loop with its own convergence time.

The distinction matters because policy routing is often described as if it provided load balancing. It provides selection, and selection plus an external controller can approximate balancing. The controller must handle the same problems any control loop has: hysteresis to avoid oscillation, damping to avoid reacting to noise, and a defined behaviour when the measurement is stale. None of that is in the routing table.

Failure modes specific to multiple tables

The first is a rule that matches more than intended. A selector written for one source prefix also matches traffic from a subnet added later inside that prefix, and that traffic is silently diverted to a table the rule was not written for. If that table has a default route the traffic leaves by a path nobody chose; if it has none, the packet falls through to a later rule and follows a third path. Either way the diversion is invisible in the packet’s addressing, because the source and destination are unchanged and only the exit differs.

The second is a table with no route for the packet’s destination. Most implementations treat that as a failed lookup and continue to the next rule rather than dropping, so the packet is forwarded by whatever the following rule selects. That is worse than a black hole in one respect: the packet leaves, so the policy appears to be in force while the traffic is actually following a path the rule list was written to avoid. A rule that must not fall through is written with an explicit action that discards instead of a table reference.

The third is the interaction with the reverse path check. A router that verifies a packet’s source address against the interface it arrived on will reject traffic that policy routing deliberately sends out a different interface than the one the source implies. The check is a security measure that assumes symmetric routing, and policy routing violates that assumption by design. Disabling the check restores function and removes the protection, which is a trade an operator must make explicitly.

The fourth is that policy routing operates on the forward direction only. A rule list on one router says nothing about how the next router will treat the packet, so a policy that depends on the whole path behaving consistently requires configuration at every hop. That is the same limitation that makes any per-hop decision hard to reason about, and it is why policy routing is usually confined to the edges of a network where the number of hops under one administrative control is small.