Project

General

Profile

Intro to Routing

User documentation
09/13/2017

  • Last Updated: 07/25/2021

Basic Concepts

At an abstract level, routing is building maps and giving directions to incoming packets. We do this by directing different packets to different locations based on 2 criteria: destination and netmask. These packets are then forwarded on to a "next hop" location. This is called classic or destination based forwarding and is supported by all routers and most hosts.

These three elements (destination, netmask, and next hop) are what make up the basics of routing. The destination is the IP address of wherever the client has requested to go. The netmask (also called prefix length) of the route is a set of bits that the router looks at.

An ipv4 address has 32 bits. A route will look like this:

192.0.192.0/24 or 192.0.192.0 255.255.255.0

The /24 is saying that the router should match ONLY the first 24 bits of the route against a packet when determining whether to use the route for that packet.

Each piece (what is between the dots) of an ipv4 address is 8 bits long.
So the first 24 bits of this route are: 192.0.192

In binary [base2] the bits look like this:

[must match.........................][not used]
11000000.00000000.11000000.00000000

So any ipv4 destination that matches 192.0.192.x will use that route:
Example: 192.0.192.3 is:
11000000 00000000 11000000 00000011

and since the first 24 bits match, the route can be used.

IPv6 works in a similar fashion but the notation is different. Instead of using base10 notation with bytes separated by dots like ipv4, ipv6 uses a hex digit for each half byte (4 bits) with leading zeroes suppressed inside each group. Colons separate each group of 2 bytes:

Examples:

ipv6 address: 2620:a8:c000:999::21/64

ipv6 route: 2620:a8:c000:999::/64
[must match..............][not used..................]
2620:00a8:c000:0999:0000:0000:0000:0000

Users sometimes think of routes as having a subnet and a subnet mask but this is technically incorrect. For example a supernet route can represent many subnets with a single entry in a router.

For example a company may have 4 subnets on their network:
192.168.10.0/24 HR
192.168.20.0/24 Sales
192.168.30.0/24 Engineering
192.168.40.0/24 R&D LAB

A VPN tunnel that is established does not have to have 4 routes to provide connectivity for all 4 subnets.

Instead a single route destination 192.168.0.0/16 could be added to the VPN router to push traffic destined for any 192.168.* network.

This is why its important to combine the destination and route length into a prefix while remembering the route itself has 2 subcomponents.

If you try to represent a route or prefix incorrectly many operating systems will refuse to accept the route or cisco will autocorrect the route for you.

For example if you enter a route for:

192.168.1.230/24 next hop of 10.10.1.1 into a Cisco it will convert the route for you into 192.168.1.0 255.255.255.0 (192.168.1.0/24).

The reason for this is that all of the bits in the not-used section must be zeroed out.

Some common prefix lengths you will see:

/30 (used on point to point links)
/29 (used by broadband ISPs for a chunk of 5 usable public IPs)
/24 (common ipv4 LAN subnet)
/22 (used on large wireless LANs)
/16 (supernet routes for large chunks of space)
/0 (default route - also 0/0)

All next hop addresses must be directly accessible (using ARP) from an interface unless you have recursive routing enabled.

Types of Routes

Connected

A connected route is a route where two devices can communicate directly. Connected routes only exist for devices that share a LAN. No routing is done because the packets simply travel through the router's LAN interface. For example, if you have two computers connected to the same LAN, their route to one another is connected.

Static

Static routing is the most basic form of routing. It is programmed in by the user and does not change unless the user changes it.

The most precise static route will always be chosen before the most general one. For example, if you have these two routes:
0.0.0.0/0 via 172.30.100.1
192.168.1.0/24 via 172.30.100.10

The router will choose 172.30.100.10 for any queries in the 192.168.1.0/24 network because the 24 prefix is more precise than the 0 prefix. For any other routes, it has no choice but to choose 0.0.0.0/0 (also called a default route).

Static routes can also have a next hop of an interface instead of an IP address. This is for direct connections. These direct connections will use ARP for finding directly connected IPs.
Example:

192.168.1.0/24 dev eno1 proto kernel scope link src 192.168.1.130

Here, the routing table is telling the router to use the interface eno1 for all connections for 192.168.1.0/24.

Dynamic

Dynamic routing works much the same way static routing does with route selection and route criteria, but it differs in one big way: routes can change without user input.

In dynamic routing, routes are learned from a protocol (OSPF, BGP, RIP, etc.). Routes are "advertised" by other routers, and your router chooses which ones to add to its kernel based on acceptance criteria. These acceptance criteria make sure no malicious routes are declared like one overriding access to your LAN.

Policy

Policy routing is used to override static or dynamic routing policies based on more criteria than destination and netmask. Some of these criteria are source address, size of packet, protocol, or any other information.

Policy routing can be useful in some scenarios. For instance, it can be used if you have two fiber lines: one that is cheaper at night and one that is cheaper during the day. You can use a policy route to use one line for most of the traffic during the day and the other at night.

Now that sounds great, but it can cause some real problems. If you are trying to remotely access a server on your network, for instance, you will have to remember that the public IP will change with the day and night. Complications like this serve as a reminder that while policy routing may sometimes seem like a great solution, it can be problematic if not taken into careful consideration.

RIB vs FIB

The RIB (Routing Information Base) and FIB (Forwarding Information Base) are two distinctly different tables. A novice user inputting routes into a machine would assume that when forwarding packets, the router simply looks at the configuration file and reads the "ip route" statements, but
this is not the case.

RIB

The RIB is the list of all routes inputted whether it be by dynamic or static protocols. It can be thought of as the control plane level of routing. When a route is entered, it goes straight into the RIB. While routes are inputted into the RIB, they ARE NOT read off of it. Instead, the RIB is analyzed by the OS when new routes are entered, and the most efficient routes are entered into the FIB as well as the appropriate next hops.

FIB

The FIB is what is used to determine next hops for incoming packets. The FIB holds a definitive list of routes that know exactly where to send incoming packets. In the RIB, there may be multiple routes with the same prefix, but this will not be the case in the FIB. When the routes are put into the FIB, the most efficient one will be determined and be entered.

Now the obvious question is: Why not enter routes directly into the FIB? This whole RIB things seems unnecessary.

There are two main issues with entering directly into the FIB: capacity and recursive routes. In routers, the FIB has to be read at incredibly fast speeds in order to make quick decisions and route traffic quickly. In order to do this, the FIB is stored on DRAM. This is incredibly quick to access, but it is also very small. This means that often an entire RIB cannot be stored, so it must be consolidated into a smaller FIB to fit on DRAM. The second problem is with recursive routes. Typically, a next hop always must be an IP directly connected via ARP. If it is not, the router must break down that route into multiple other routes to create a set of routes that are all connected via ARP.

ARP

ARP has been mentioned multiple times, but we haven't really defined it yet. ARP (Address Resolution Protocol) is used for mapping directly connected devices' network addresses.

ARP first does this by sending out a request. ARP broadcasts its IP and MAC address as well as the desired destination address. If any of the hosts receiving the broadcast have the desired IP, they send back a response with their MAC address. When the first host receives this packet, it will update its ARP cache with the MAC address of the other host. Now, these two hosts can talk to each other because each has the MAC address of the other.

Files