How a router forwards: the routing table

What a router really does

A router joins different IP networks. For every packet that arrives, it does the same three things: read the destination IP address, look for the best matching entry in its routing table, and send the packet out of the interface that entry names, towards the next hop. The next hop is the IP address of the next router on the way. The source address does not matter for normal forwarding.

The routing table is a list of networks the router knows about. Each entry says: this network, learnt from this source, reachable through this next hop or out of this interface. If no entry matches and there is no default route, the router drops the packet and sends back an ICMP "destination unreachable" message.

Where routes come from

Reading show ip route

R1# show ip route
Codes: L - local, C - connected, S - static, R - RIP, B - BGP
       D - EIGRP, O - OSPF, IA - OSPF inter area, * - candidate default
Gateway of last resort is 203.0.113.1 to network 0.0.0.0

S*    0.0.0.0/0 [1/0] via 203.0.113.1
      10.0.0.0/8 is variably subnetted, 5 subnets, 4 masks
C        10.1.12.0/30 is directly connected, GigabitEthernet0/1
L        10.1.12.1/32 is directly connected, GigabitEthernet0/1
O        10.2.0.0/16 [110/2] via 10.1.12.2, 00:05:12, GigabitEthernet0/1
S        10.2.5.0/24 [1/0] via 10.1.12.2
O        10.3.3.0/24 [110/3] via 10.1.12.2, 00:05:12, GigabitEthernet0/1

Read each line from left to right. The code says where the route came from. Then the prefix (network and prefix length). The numbers in square brackets are [administrative distance/metric]. "via" gives the next hop. For learnt routes you also see how long ago the route was learnt and the exit interface. "Gateway of last resort" tells you the default route is set.

Rule 1: longest prefix match

A destination often matches several entries. The router always picks the entry with the longest prefix, meaning the most network bits, because it is the most specific. Take these routes: 0.0.0.0/0 to the ISP, 10.0.0.0/8 to R2, 10.1.0.0/16 to R3, 10.1.1.0/24 to R4.

To check a match yourself, write the destination and the network in binary and compare only the first N bits, where N is the prefix length. 10.1.9.9 and 10.1.0.0 share the first 16 bits (10.1), so the /16 matches. They differ inside the first 24 bits (9 versus 1 in the third octet), so 10.1.1.0/24 does not match.

Rule 2: administrative distance

Administrative distance (AD) is how much the router trusts a source of routing information. Lower is more trusted. AD is used only when two different sources offer the exact same prefix with the same length, for example a static route and an OSPF route both for 10.2.0.0/16. Only the winner goes into the routing table.

Rule 3: the metric

A metric is how one routing protocol measures the length of a path. OSPF uses cost (based on bandwidth), RIP uses hop count, EIGRP uses a formula based mainly on bandwidth and delay. Lower is better. Metrics are compared only between routes from the same protocol: an OSPF cost of 20 and a RIP hop count of 2 cannot be compared. If two paths have the same best metric, the router installs both and shares traffic between them (equal-cost load balancing).

The whole decision, in order

1. Building the table: for each prefix, if several sources offer it, keep the lowest AD. Inside one protocol, keep the lowest metric.
2. Forwarding a packet: among the installed entries that match the destination, use the longest prefix.
3. No match and no default route: drop the packet.