Routes and Rules

A traditional router stores network route information in routing tables. A routing table is a map of a network. Linux uses a policy based routing system, aptly called a Routing Policy DataBase or RPDB. A Routing Policy DataBase (RPDB) is a collection of routing addresses, rules, and routes. The "policies" per se are defined by rules. Here's how it works.

A traditional routing table is two-dimensional. It is a single table that includes algorithms (rules) and pointers (routes) to every network connection the server is aware of. Routing a connection is simple. Apply any applicable rules and off you go. The advantage of a RPDB is two-fold: the separation of rules from routes, and the use of a master routing table index and a collection of tables with the real routing information. This combination allows more granular control over network traffic, such as pointing to a single route from multiple rules, or the opposite (multiple rules pointing to a single table). In short, it allows for improved granular control and segmentation of your network routes.

Another plus of a RPDB is real-time changes can be made to routing tables without interfering with the server's operation. With a traditional single-dimension routing table, you may need to interrupt the server's traffic or have to take it offline in order to modify the table. And if you inadvertently make a mistake while editing a router table, in a single-dimension routing table environment it's much easier to accidentally cripple your server's access. While in a RPDB configuration, isolating changes and creating failsafe traps is easier. In short, it's more foolproof.

The RPDB rule cache is loaded during the server boot-up process. When a routing decision is required, only the cache copy is referenced. What are the characteristics of the RPDB?

• Addresses (source and destination)
• Rules (what goes where?)
• Routes (where's it going?)

In Linux, the RPDB is composed of two databases: a table of rules and a table of routes. Taken together they determine the route assigned to a packet. At a high level, the rules work in conjunction with routing tables like this:

How is a route selected for any given packet?

Rules are examined sequentially, in order of priority. Rules contain a selector and an action predicate. If the current network packet matches the current rule selector, the action is executed. If the corresponding action is a reference to a routing table (a "look up"), it will point to the index number or name in the RPDB's routing table.

The combined process flow looks like this:

ip rule Analysis

1. Network packets are processed one at a time
2. The same rules process both incoming and outgoing packets
3. Packets are evaluated against a list of rules, in order of priority, beginning with rule 0
4. First rule matching the packet is executed
5. If the action is a table lookup and the lookup fails, evaluate the next rule
6. If no rule matches the packet, fail with an undeliverable packet error

iproute2 Analysis flow

1. The route with the longest matching prefix is chosen
2. If more than one match is the same length, the route with the best preference values is chosen
3. If more than one match exists, if ToS is specified, routes that don't match the ToS are dropped[1]
4. If more than one route still exists, then the first ordered matching route in the list is chosen
5. If no matching route is found, the kernel returns to the Rule table and moves onto the next rule

In this context "prefix" means the destination IP address, including the netmask (if present).

Let's move on to a discussion of how the main routing process functions and the philosophy behind it. Afterwards, I'll go over the packet mangling process (netfilter), and wrap it all together for you with a comprehensive explanation of how these pieces fit together to complete the puzzle.

The RPDB Triad: Addresses, Rules, and Routes

These are the building blocks of the RPDB system. Every server has an internal firewall and routing configuration that tells it where to send network packets. iptables manipulates packet filters, ip route controls routing paths, and ip rules controls routing policies on your server.

Before you begin modifying your RPDB, you should be clear on how ip rules, ip route, and iptables are inter-related and work together to manage network packet flow. You may recall the Packet Routing diagram found in the Linux Firewall Management Tools Overview demonstrates that while all three (3) modules are called at one point or another, which is called first depends on whether the packet is originating from the local device (i.e. new outgoing packet), an incoming packet, a forwarded packet, or an outgoing packet that's part of an established communication link.

Here’s a brief clarification of each portion of the Linux RPDB system.

Addresses

This is pretty straightforward. An address describes the location of a service on a network. Packets must have both source (origin) and destination addresses. A packet's addresses are the most important factor in how it is routed.

Rules

IP rules are pointers that define the location of routes. While their ability to scrutinize a network packet is limited, in combination with routing tables they create a powerful filtering combination.

Routing rules are managed with the ip rules command. They are the crux of the Routing Policy DataBase (RPDB) system. Routing rules control how and where traffic flows along routes to a destination address (if it moves forward). Routing rules are effectively filtering algorithms. Each rule contains a selector (match filter) and an action. They provide instructions to the kernel regarding what to do with the packet.

Selectors may examine one or more of the following parts of the current network packet:

1. Source address
2. Destination address
3. ToS (Type of Service)[1]
4. Incoming interface (that which the packet arrived from)
5. fwmark (firewall mark)

ip rules does not allow filtering based on protocols or transport ports, though that type of filtering is possible via iptables, which is discussed later in this guide. For our purposes (basic routing), we are not concerned with the ToS value.

The output of each rule is of the following action types:

• Jump to specified routing table
• Drop or reject packet
• Return an error
• Modify packet source address

Each rule contains a selector and an action. The selector is an algorithm or criteria. When the selector of the current rule matches the packet, that rule's action is executed. Each rule is preceded by an integer from 0-32767. The rule number is its priority. For every packet, the rule database is scanned from highest priority (rule 0) to lowest priority (rule 32767). Each packet is compared sequentially to every rule beginning with rule 0.

IP Rules are explained in more detail in Follow the Rules.

Type of Service (ToS)

The iproute2 documentation refers to Type of Service (or ToS), which relates to the priority of a network packet relative to other network traffic. ToS was subsequently replaced in 1998 with DSCP (Differentiated Services Code Point). Later on, ECN (Explicit Congestion Notification) was added.[1] However, the function of ToS in the context of iproute2 did not change. While it is now technically DSCP, literature referring to ToS may still be followed. When it comes to iproute2's treatment of ToS vs. DSCP, its behavior is the same. This issue is mostly a function of nomenclature (especially in regards to IPv4 header discussions).

ToS (now DSCP) is sometimes used in advanced networks to incorporate traffic priority into the datagram of the traffic itself (versus traffic prioritization by other means, such as port, protocol, source/destination address). Traffic shaping and priority manipulation by ToS is beyond the scope of this document.

Routes and Routing Tables

A “route” is a pathway to a destination. It defines the location of a service. A route instructs the kernel where on the network to send a network packet so that a packet so that it is one step closer to its destination address. The route may be the destination, or it may be a bridge, router, gateway, or the localhost. If the route leads to another device that is not the final destination, the route is called a hop.

A “route table” is a collection of routes. You can liken a routing table to a map, as they typically contain multiple routes, and it’s possible more than one route could lead to the packet’s destination. Likewise, a single route - a single basic instruction - is like a sign post. It advises the kernel of the next step in a packet’s path to its destination. Similar to rules, there may be times when more than one route is applicable to a particular packet. When this happens, the longest matching route wins. Practically speaking, the longest route should be the most specific route and it is generally safe to presume that will be the case.

Endnotes