Routes and Rules

Additional, related information may be found in the following articles:

• Routers, Routes, Subnets, and Netmasks
• A Brief History of Linux Networking
• iproute and Routing Tables
• Route and Netstat

Familiarity with Linux network routing principles is recommended, including route and iproute2.

Routing Prefixes

What is a routing prefix? Applicable to IPv4 networking, and defined under RFC 3222,[1] the routing prefix - also known as the network prefix - is a binary string up to 32-bits in length that describes the network address range of a route to the router. There are a few different ways you can think of it. All of these statements describe the routing prefix:

1. The network address range, after applying the netmask to the destination address
2. The number of bits identified by the Slash Notation of the router address indicates the number of bits comprising the routing prefix, after the netmask has been applied.
3. The lower boundary of an IPv4 route's address range
4. The starting address of an IPv4 route's address range, calculated after applying the netmask to determine the route's size (range)

All of those statements say the same thing. They are just worded differently.

Why are Routing Prefixes Important?

Routers use routing prefixes to improve their efficiency. Routers work with the binary number system. By narrowing their focus to the smallest number of significant bits when evaluating routes, it improves their speed, especially when sorting through large routing tables. It allows packets to be first screened against the prefix. If the prefix matches, then the route is examined further to determine if the packet matches the route's characteristics. It basically allows the router to handle more traffic, more quickly.

Linux Network Route Prioritization Logic

Routers choose the appropriate route for outgoing packets based on algorithms that vary with the routing software. This article delves into IPv4 routing prefixes and how they are applied within the context of the Linux iproute2 process (incorporated into most Linux kernels).

iproute2 uses the longest prefix match method to identify the highest priority route in a routing table. If more than one matching route is the same length, the route with the highest bit will be chosen. If a tie still exists, other logic gates are applied.

Let's walk through an example to understand how the routing logic process works. Presume you have a packet with a destination IPv4 address of 192.168.10.1 on the eth0 interface, and your routing table rules were entered like this:

ip route add default via 10.10.0.3
ip route add 192.168.10.0/24 via 10.10.0.4
ip route add 192.168.10.0/25 via 10.10.0.5
ip route add 192.168.10.1/32 via 10.10.0.6

The route command may be used to examine your main routing table, which could look like this:

Destination	Gateway	Genmask	Flags	Metric	Ref	Use	Iface
default	10.10.10.3	0.0.0.0	UG	0	0	0	eth0
10.10.0.0	0.0.0.0	255.255.255.0	U	0	0	0	eth0
192.168.10.0	10.10.0.4	255.255.255.0	U	0	0	0	eth0
192.168.10.0	10.10.0.5	255.255.255.128	U	0	0	0	eth0
192.168.10.1	10.10.0.6	255.255.255.255	U	0	0	0	eth0

It seems our packet matches all the rules. Which rule will apply to the packet? Where will the packet be routed?

The terms "Genmask" and "Netmask" are interchangeable. Netmask is an industry-standard nomenclature, while Genmask only appears in output from certain iproute/iproute2 tools, such as route and netstat.

The Genmask (Netmask) 255.255.255.255 rule applies, because its routing prefix (the combination of that route's IPv4 address and netmask) has the highest matching bit.

When iproute2 compares the possible routes in binary form, this is what it's comparing:

The longest matching route will be chosen. But, take a look above at the ip route commands again, and you will see there is a problem. Notice all of the routes below the default route are the same length. Remember, "length" here is the length of the route as written into the routing table. Therefore, in this example, the longest matching route test will result in a tie. What happens when there is a tie?

The next test is whether a single route more specifically matches the destination when compared with all other routes in the current table, based on the routing prefix. And in this case, yes there is a route that is more specific than the others. That is the route that will ultimately be chosen. This is where you may allow your intuition to take over, because it will now be correct.

As you can see, the most specific route by highest routing prefix bit order (to the right) is the one on the bottom. And therefore, it will be the route chosen for this packet.

This also happens to be the most specific IPv4 address, and in this case there is a route that matches our IPv4 address exactly. However, that is not why this route was chosen. This is an important distinction. Although the net effect is the same, the routing decision process is different than one might intuit.

The selection becomes easier to identify when using slash notation to represent the destination IPv4 address to the router.

Now, we can instantly see there are 32 significant bits in the routing prefix (the slash notation value). Right away, we know this route is more specific to the destination address than any other route with fewer significant bits (32).

iproute2 Filtering Priority

Why does iproute behave this way?

Allowing the longest rule to take precedence allows anecdotal but relevant information to apply in the filtering process. For example, outgoing interface may be specified. So, you could have two different possible routes for a packet, depending on which interface it's travelling on. This is a very basic example, and the nuances available can get quite complex very quickly, but the point is you cannot rely on the combination of matching IPv4 address and mask or the position of a rule in a table. Those are factors in which route is chosen, but they are not the most important factor. For more information on the routing prioritization process, you may wish to read Route Priority Processing.

Interestingly, this example sheds a sliver of light on iproute's ability to affect multiple layers of the OSI networking architecture model.

More details on rule filtering logic are discussed in my guide on ip rules and its traffic management capabilities. ip rule has a similar prioritzation schema behind its logic gates.

It's worth noting the default route must exist. As its name implies, the default route will be the match when no other route applies to a packet. Thus, it is a critical component of any routing schema (even if the default route is to drop packets).

Endnotes