In computer networks, routing is about getting packets from A to B. Normally this will involve two hosts (maybe a client and a server) communicating, with series of intermediate hops (usually routers) in between them. Below, we will consider how both hosts and routers deal with IP version 4 routing.

How does host routing work?

If the IP address it wants to talk to is on the same subnet, it will send the packet directly to that host (using ARP and the Ethernet layer).

Hosts have a default gateway – this is where they send packets if they have no better ideas and the host isn't on the same subnet. This default gateway will usually be able to route packets on to other subnets and the internet.

It is possible to set up more complex routes – for example, if the host can reach multiple routers which are used for different things.

How do routers work?

Routers have a routing table. The routing table contains ‘routes’ which consist of

  • Network

  • Interface

  • Next Hop (in some cases)

When a router receives a packet, on a basic level it does this:

  1. Check the data-link frame (is it for this router and is the FCS correct).

  2. De-encapsulate the IP packet.

  3. Check the destination IP address against the routing table for the route which is the best match.

  4. Encapsulate the IP packet in a new data-link frame and send it out of the interface associated with the best match route.

The best match route is the most specific network which includes the destination IP address.

This process is repeated by each router in the path until our packet reaches its final destination.

Routing Protocols

To decide where to forward packets on to, routers need to know which router to send a packet to next (the next hop).

It is possible to specify the route entries in the routing table manually using 'static routes' which hard code values for the network, interface and next hop. However, this isn't scalable as networks often change and so the routing table quickly becomes out of date.

Instead, we use routing protocols to automatically share routes between the routers on a network (Interior Gateway Protocols - IGPs) or between different networks (Exterior Gateway Protocols).

We need routing protocols to

  • Keep our routing table up to date

  • Make sure we use the best route possible

  • Remove routes that are no longer valid and add replacements

  • Make sure packets don’t just go round in a loop

  • Do all of the above as quickly as possible

Regardless of the specific routing protocol being used, each router will add routes for subnets directly connected to its interfaces.

Each router then uses the routing protocol to tell connected routers (neighbours) which networks it is directly connected to and any routes that it has learned from others.

When it receives information from other routers these routes will be added to its routing table and the router it learned them from will be used as the ‘next hop’ address.

How do routing protocols work?

Routing protocols allow routers to learn information about subnets from other routers, to share information about subnets they are connected to (or know about) and to choose the best route if there are multiple ways of getting somewhere.

Routing protocols allow routers to share and understand the topology of a network.

Routing protocols can be categorized into interior gateway protocols (IGPs) and exterior gateway protocols (EGPs). IGPs are used within a given autonomous system (AS), where an AS can is a network or group of networks managed with a single administrator (such as a company or telecommunications provider). Examples of IGPs are RIP-2, Open Shortest Path First (OSPF) and Enhanced Interior Gateway Routing Protocol (EIGRP). EGPs exchange routing information between different autonomous systems and are typically used by large telecommunications providers. BGP is the most commonly used exterior gateway protocol and underpins a lot of the routing across the internet. Here we will be focusing on interior gateway protocols.

Information is exchanged using a defined protocol (such as RIP-2, OSPF or EIGRP) which is typically shared around the network using multicast addresses – for example RIP-2 uses 224.0.0.9. Different protocols have different metrics for assessing the ‘distance’ to a subnet and different algorithms for calculating the best route. A single network may use more than one routing protocol

Metrics are values assigned to routes to determine the best route to a given destination. A lower metric indicates a better route.

The Routing Information Protocol (version 1) was the original IP routing protocol. Later RIP-2 (version 2) added improvements and then RIPng (next generation) introduced support for IPv6. RIPng isn’t discussed here. RIP is an open standard but there are several other open and proprietary routing protocols in use.

Distance-Vector Routing

One way of calculating the optimal route through a network is to use a distance-vector method. Basic distance vector protocols share a distance (or metric) and a vector (the ‘next hop’) for each subnet. The next hop is simply the router to forward the packet on to (and therefore which interface to use) and the metric (such as how many hops it is to the destination) is used to decide on the best route if there are multiple options.

Split-Horizon

If a router shared all of the routes it knew through every interface then we could get stuck in a loop. This happens if a router shares routes through the same interface which it learnt about them on. Router A would learn about Router B’s routes and then Router A would share them back to Router B which would learn them as new routes (going via Router A) and share these new routes back to Router A and so on. Split-horizon is a common technique used with distance-vector protocols to stop this happening. It simply stops routes from being shared out of the interface which they were learned on. There are some cases where split-horizon can cause issues if using ATM or Frame Relay.

Route Poisoning and Poison Reverse

When a route is no longer valid (for example, an interface has been shut down), this information needs to be shared throughout the network so that routers no longer try to use it! This can be done with route poisoning. When a router needs to share that a network is no longer reachable, it will send an advertisement for that network but with a metric of infinity (or unreachable) so that other routers no longer use the route. This is known as poisoning the route and the poison update is also sent back to the originating router – this is poison reverse. Poison reverse goes against the idea of split-horizon, but helps ensure that invalid routes spread quickly through the network.

Other Related Skills

The traceroute command is useful tool installed on hosts and network devices for troubleshooting networking issues by tracing the route of a packet across a network.
RIP was one of the first routing protocols to be implemented. RIPv2 later added a number of improvements.