Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 79 ยท Routing

Routing and Forwarding

Understand how routers forward packets: control plane vs data plane, routing table lookups, longest prefix match, default and static routes, and route selection.

A router has one basic job: take a packet that arrives on one interface and send it out of another, closer to its destination. Doing that for billions of packets a second needs two separate activities that are easy to mix up. Forwarding is the fast, local act of moving one packet. Routing is the slower, network-wide work of figuring out which way each destination lies.

This lesson explains the routing table that links the two, how a router chooses among overlapping entries, and how routes get into the table. The routing algorithms that fill it automatically (link state, distance vector, BGP) are the topic of the lessons that follow.

Control plane and data plane

Routers are described in two layers:

  • The data plane handles each packet: read the destination address, look it up in the forwarding table, decrement the TTL, update the checksum, and send the packet out of the right interface. This happens in specialized hardware, in nanoseconds to microseconds.
  • The control plane decides what is in the forwarding table. It runs routing protocols, talks to neighboring routers, computes paths and installs the results. It can take seconds, because it runs in software and reacts to changes (a link failing, a new network appearing).

Think of a road network. Forwarding is the driver at a junction following the signs; routing is the planning office that decides what the signs should say. A router that is busy computing routes should still forward packets at full speed, which is why the two planes are separated.

The routing table

Each entry in a routing table says: "to reach this destination network, go this way." A typical entry has these parts:

  • the destination prefix, such as 10.2.0.0/16 (see CIDR),
  • the next hop, the address of the neighboring router to hand the packet to (or "directly connected" if the destination network is on one of the router's own links),
  • the outgoing interface,
  • a metric (a cost; lower is better), and where the route came from (connected, static, or a routing protocol).

On a Linux router, the table looks like this (read-only sample):

TEXT
$ ip route
default via 192.168.1.1 dev eth0 proto dhcp metric 100
10.2.0.0/16 via 192.168.1.254 dev eth0 proto static metric 20
172.16.5.0/24 dev eth1 proto kernel scope link src 172.16.5.1
192.168.1.0/24 dev eth0 proto kernel scope link src 192.168.1.20

The proto kernel lines are connected routes: the operating system adds them automatically when an interface gets an address, since a network on a directly attached link needs no next hop. The packet is delivered by finding the destination host's MAC address with ARP. For all other routes the packet goes to the next hop's MAC address, while the IP destination stays unchanged. That is a key point: the IP addresses stay the same from end to end, and the link-layer addresses change at every hop.

Longest prefix match

Entries can overlap. The address 10.2.7.9 matches 10.0.0.0/8, 10.2.0.0/16 and the default route 0.0.0.0/0 all at once. The rule is: the most specific match wins, meaning the matching entry with the longest prefix. This is the longest prefix match (LPM). Here the answer is 10.2.0.0/16, a 16-bit match beats an 8-bit match, and /0 matches every address but with zero bits of certainty.

LPM is what makes route aggregation work. An ISP can announce one /16 for all of its customers and still carry a more specific /24 for one customer that moved elsewhere, and traffic for that customer follows the /24. Real routers do the lookup with specialized structures (tries and TCAM memory) so that it takes one memory access cycle, even with a table of a million entries.

Python Longest prefix match in a routing table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The default route

A router cannot hold an entry for every network in the world, and a small office certainly does not. The default route 0.0.0.0/0 (IPv6: ::/0) matches everything not matched by anything more specific. It points toward "the rest of the Internet", usually the ISP's router. A home router is the simplest case: one connected network on the inside and a default route to the outside.

If a router has no matching entry at all, including no default route, it drops the packet and sends an ICMP destination unreachable message to the source. Routers in the core of the Internet carry no default route; they keep the full table, close to a million IPv4 prefixes, and therefore know where everything goes.

A host also has a tiny routing table: its own subnet is connected, and everything else goes to the default gateway it learned from DHCP. To decide whether a destination is on its own subnet, the host ANDs the destination with its mask (see subnetting).

How routes get into the table

A route comes from one of three places:

  1. Connected routes. Created automatically for each interface that is up and has an address. Their administrative distance is the lowest, because the router is certain about them.
  2. Static routes. Typed in by an administrator, for example "send 10.2.0.0/16 to 192.168.1.254". They are simple, predictable and use no bandwidth, but they do not adapt: if the next hop fails, the route stays until a person changes it. They suit small networks, stub sites with one exit, and default routes.
  3. Dynamic routes. Learned from routing protocols. Routers exchange information with their neighbors and compute the best paths themselves, reacting to failures in seconds. Examples are OSPF, RIP and BGP.

The three can coexist. A router may learn the same prefix from several sources, so it has to choose.

Route selection

When several sources offer a route to the same prefix, the router picks the best by two rules, in this order:

  1. Administrative distance (AD) compares the trustworthiness of the source. Lower is better. Typical defaults on Cisco-style routers: connected 0, static 1, eBGP 20, OSPF 110, RIP 120. A static route therefore beats an OSPF route to the same prefix, which is how an administrator overrides a protocol. (Linux uses a similar idea with route "protocol" and metric values.)
  2. Metric compares the cost among routes from the same source. A protocol defines its own metric: hop count for RIP, link cost based on bandwidth for OSPF.

Remember the order of precedence overall: longest prefix first, then administrative distance, then metric. A less specific route with a better distance never beats a more specific route.

A static route with a high administrative distance, for example 200, is a floating static route: it stays inactive until the dynamic route disappears and then takes over as a backup.

Python Choosing between routes to the same prefix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Hop by hop forwarding in action

No router knows the whole path. Each router looks only at the destination address, picks the next hop, and trusts the next router to do the same. The result is hop-by-hop forwarding. As long as all routers agree about the topology, the packet arrives. If they disagree (a state that lasts for a short time after a change), the packet can loop between two routers, which is why the TTL exists.

flowchart LR
    H["Host A<br/>192.168.1.20"] --> R1["Router 1<br/>default via ISP"]
    R1 --> R2["Router 2<br/>10.2.0.0/16 via R3"]
    R2 --> R3["Router 3<br/>10.2.7.0/24 connected"]
    R3 --> D["Host B<br/>10.2.7.9"]

Each router matches the destination against its own table; the IP addresses never change, but the MAC addresses do on every link.

Python Forward a packet across three routers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last example shows a routing loop caused by inconsistent tables: R2 sends 10.2.8.1 to R3 (its /16 entry), but R3 has only a default route that points back to R2. Without TTL, those packets would circle forever.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the difference between routing and forwarding?

    Routing protocols compute and install routes, which can take seconds. Forwarding looks up the destination of every packet and sends it out of an interface, and must be very fast.
  2. 2. A router has entries for 10.0.0.0/8, 10.2.0.0/16 and 0.0.0.0/0. Where does a packet for 10.2.5.5 go?

    All three match. The longest prefix, /16, is the most specific, so it wins.
  3. 3. OSPF and a static route both offer a path to the same prefix. Which is installed by default?

    Administrative distance ranks the trustworthiness of the source, and lower is better. Setting a high distance on a static route makes it a floating backup instead.
  4. 4. As a packet crosses several routers, which addresses stay the same?

    IP addresses identify the end hosts. Each hop rewrites the Ethernet header with the MAC addresses of that link (the exception is NAT, which rewrites IP addresses on purpose).
  5. 5. What does a router do when no route, not even a default route, matches the destination?

    Routers do not flood IP packets. With no match, the packet is dropped, and the source is usually informed by ICMP.

Summary

  • Routing (control plane) computes paths and fills the forwarding table; forwarding (data plane) looks up each packet and sends it on, hop by hop.
  • A routing entry holds a prefix, next hop, interface, metric and source. IP addresses stay constant end to end, while MAC addresses change on each link.
  • The most specific matching entry wins (longest prefix match); the default route 0.0.0.0/0 catches the rest.
  • Routes are connected, static or dynamic. For the same prefix the lower administrative distance wins, then the lower metric.
  • Inconsistent tables can cause loops, which TTL and ICMP time-exceeded messages contain.

Next, see how routers compute shortest paths on their own: link-state routing and Dijkstra.