31.1. Concepts Behind Policy Routing

We saw in the section "Special Routes" in Chapter 30 that the Linux kernel uses two routing tables by default, one for local routes and one configurable by the administrator. When the kernel is compiled with support for policy routing, you can have up to 255 distinct and independent routing tables. In this chapter, we will see what policy routing can be used for, and in Chapter 35 we will see its implications on the design of the routing subsystem.

The main idea behind policy routing is to allow the user to configure routing based on more parameters than just the destination IP addresses.

The Internet thrived for years with most routers configured just to route packets based on the destination IP address. (For the sake of simplicity, I'll leave out particular factors such as crossing ISP or country boundaries.) And basing the route on only the destination address can (with the help of some external configuration parameters) lead to pretty optimal routing tables for a surprisingly wide range of situations.

But the commercial world needs to take many other things into account, such as separating streams of traffic for security or accounting purposes, or sending real-time streaming traffic over a separate route. Here is where policy routing comes into play. Because there are such varied criteria for routing, for the purposes of this chapter I'll just say that any routing based on more than just the destination address is policy routing.

An example of the use of policy routing is for an ISP to route traffic based on the originating customer, or on Quality of Service (QoS) requirements. The customer can often be easily identified by the port on which the traffic arrives at the ISP's router, the source IP address, or a combination of the two. A router can also use a combination of source and destination addresses to identify a profile of traffic or an aggregate of traffic from a given source. The QoS requirements can be derived from the DiffServ Code Point (DSCP) field of the IP header and from a combination of the fields of the higher-layer headers (these identify the applications).

Since this book is about kernel internals, we want to know how those policies are passed to the kernel, see how they are embedded in the routing table, and find out how they affect the routing lookups. We will learn all of this, but let's start with an example, using the topology of Figure 31-1 as a reference.

Let's focus on the configuration of the router RT, which is used to connect Campus 1 and Campus 2 to both Campus 3 and the Internet (let's not bother about how the routers manage to translate the nonroutable addresses 10.0.x.x; this is just an example). Let's also suppose we want to enforce the following two policies:

• Traffic directed to Campus 3 will go through router RT1 when originated from Campus 1, and through RT2 when originated from Campus 2. One reason could be that the administrator of Campus 2 is willing to pay more and therefore is allowed the use of the faster network that connects RT to Campus 3.

• Traffic directed to the Internet (e.g., any destination except the three campuses) will go through DG1 (default gateway 1) for Campus 1, and through DG2 for Campus 2. This could be needed, perhaps, to enforce security or bandwidth policies.

This example is a simple one with just a few routes and only two policies. Of course, the advantage of providing independent routing tables appears only in much bigger and more complex scenarios. And even this example is incompletewe are ignoring, for instance, incoming routes from the Internet to the campuses.

There are two conceivable ways to configure routing on router RT, one of which (multiple tables) is the approach used by Linux.

Single table approach

Table 31-1 is a simplified version of the routing table configured on RT to enforce the two policies listed earlier. Note that because Campus 1 is the only network connected to RT's eth0, and Campus 2 is the only one connected to RT's eth1, the routes do not need to specify the source IP addresses. Instead of routing just on the destination addressbecause the same destination address can match multiple routesmultiple criteria are checked to choose a unique route. In this case, the incoming device is checked along with the destination address.

Figure 31-1. Example of topology that may require policy routing

Table 31-1. Single routing table example

Ingress device	Source IP	Destination IP	Next hop	Egress device
Routes to Campuses 2 and 3 for traffic originated in Campus 1
eth0	Not specified	10.0.3.0/24	10.0.0.10 (RT1)	eth2
eth0	Not specified	10.0.2.0/24	Not specified	eth1
Routes to Campuses 1 and 3 for traffic originated in Campus 2
eth1	Not specified	10.0.3.0/24	10.0.0.20 (RT2)	eth2
eth1	Not specified	10.0.1.0/24	Not specified	eth0
Default routes for Campus 1 and Campus 2
eth0	Not specified	0.0.0.0/0	10.0.0.11 (DG1)	eth2
eth1	Not specified	0.0.0.0/0	10.0.0.21 (DG2)	eth2

Multiple table approach

Because so many criteria could potentially be involved in every route lookup, it's faster and easier for a host to maintain independent routing tables and choose the right one from particular criteria. For instance, the source IP address or the ingress device could be used to choose a routing table, and that table could contain more criteria to help make the final route selection.

Thus, when multiple routing tables are used, the kernel has to select the right routing table before it can do a lookupthe choice of a routing table is where policies come into effect. Thus, the rules for router RT in our example could be determined by the following rules, in conjunction with Tables 31-2 and 31-3:

• Traffic coming in on eth0 is checked against Routing Table 1 (Table 31-2).

• Traffic coming in on eth1 is checked against Routing Table 2 (Table 31-3).

Table 31-2. RT1 used to route traffic from Campus 1

Destination IP	Next hop	Egress device
10.0.2.0/24	None	eth1
10.0.3.0/24	10.0.0.10 (RT1)	eth2
0.0.0.0/0	10.0.0.11 (DG1)	eth2

Table 31-3. RT2 used to route traffic from Campus 2

Destination IP	Next hop	Egress device
10.0.1.0/24	None	eth0
10.0.3.0/24	10.0.0.20 (RT2)	eth2
0.0.0.0/0	10.0.0.21 (DG2)	eth2

The first entry in Tables 31-2 and 31-3 does not need to be explicitly configured because the kernel derives it from the configuration of interfaces eth0 and eth1, respectively. We will see how this is achieved in Chapter 32.

As we will see in Chapter 33, Linux maintains only one routing cache that is updated by all the routing tables. These tables also share the memory pools used to allocate the building blocks of the tables. Linux does not enforce any fairness mechanism to share these common resources equitably among the various routing tables. In addition to simplifying the implementation, this actually maximizes overall routing throughput, because more system resources are allocated to the routing tables with higher needs. However, it may have an externally detectable effect: that is, when one Linux host using different routing tables manages traffic from different sources, the overall experience from a customer perspective may be different from the experience provided by independent routers or even by a single host that stringently separates the resources used by routes.

31.1.1. Lookup with Policy Routing

When policy routing is in use, a lookup for a destination consists of two steps:

Of course, before taking these two steps, the kernel always tries the routing cache.

Policies can be assigned an administrative type, like routes (see the section "Route Types and Actions" in Chapter 30). This allows the kernel to make a quick decision based on a type assigned to an entire policy, without waiting to look up the route. For example, the kernel generates an ICMP HOST UNREACHABLE message when the matching policy is configured with an UNREACHABLE type, instead of waiting and finding a matching route configured with an UNREACHABLE type.

Figure 31-2 is a revised version of Figure 30-9 in Chapter 30, with added support for policy routing and details about the optional policy types.

31.1.2. Routing Table Selection

The policies that let the kernel select the routing table to use can be based on the following parameters:

Source and/or destination IP address

It is possible to specify both the source IP address and the destination IP address, each with a netmask.

Ingress device

Depending on the context, the receiving device can be a more appropriate criterion for routing policy than the source IP address. There are cases where a packet with one source IP address could arrive on more than one interface, but we would like the configuration to be based on the receiving devicefor instance, if traffic on one device was considered real time and higher priority. In that case, the source IP address would not be of much help. The use of the device rather than of the source IP address could be preferable in these cases as well:

Figure 31-2. Policy routing lookup

• When multiple, discontinuous ranges of source IP addresses are on the same device that we want to associate with the same routing table. In this case, instead of adding a rule for each distinct range of IP addresses, you can simplify the configuration by using a single rule based on the device.

• When the selection of the routing table has more to do with the physical network topology than with the source of the traffic.

TOS

The use of this parameter can help in classifying the type of traffic (e.g., bulk data, interactive, etc.), as opposed to the parameters based on the source and destination of the traffic.

Fwmark

This is one of the features that shows the power of Linux firewalling. Policy routing rules can be defined in terms of firewall classification. Of course, for this to be possible, the firewall has to classify traffic before routing comes into the picture. See the section "Policy Routing and Firewall-Based Classifier."

Any combination of the preceding parameters also represents a valid way to determine the policy.