Chapter 9 · Routing ProtocolsThe student-friendly guide + hands-on Kali labs

Chapter 9 · The student-friendly guide

Routing Algorithms
& Protocols

How does a packet find its way across the planet? Routers build maps of the network and pick the least-cost path — using two families of algorithms and a handful of protocols: RIP, OSPF & BGP.

Forwarding vs routingLink-state (Dijkstra) Distance-vectorRIP · OSPF · BGP

Use ← → arrow keys, the dots below, or the ☰ menu to navigate. Switch to the Lab Guide up top.

The big picture

Three questions this chapter answers

🗺️
1

How do routers decide?

Routing algorithms find the least-cost path — link-state vs distance-vector.

🏛️
2

How does it scale?

The Internet is split into Autonomous Systems — intra-AS vs inter-AS routing.

📡
3

Which protocols?

RIP & OSPF & EIGRP inside an AS; BGP between them.

Part 1 · Foundations

Two network-layer jobs

Forwarding

The local action: move a packet from a router’s input port to the correct output port, using the forwarding table.

Routing

The network-wide process: determine the end-to-end route packets take from source to destination.

💡
Think of it like… a road trip. Routing = planning the whole journey on the map. Forwarding = making the correct individual turn at each junction.

Part 1 · Foundations

Static vs dynamic routing

StaticDynamic
Who sets routesConfigured by handLearned automatically by a protocol
Reacts to changeSlowly — admin edits itQuickly — periodic updates & on link changes
OverheadNone on the wireUpdate traffic between routers
Best forSmall / stub networksLarge, changing networks
📌
Your NSSA-241 capstone used a static default route to the ISP — simple and perfect for one edge. Dynamic protocols shine when there are many routers and paths.

Part 1 · Foundations

Two families of routing algorithm

Global — “Link-State”

Every router knows the complete topology and all link costs (via a link-state broadcast). Each computes paths itself. → OSPF

Decentralized — “Distance-Vector”

A router knows only its directly-connected neighbours and the cost to them. It learns the rest by exchanging info iteratively. → RIP

🧠
Memory hook: Link-State = everyone has the whole map. Distance-Vector = everyone only knows signposts from their neighbours (“dest X is 3 hops that way”).

Part 2 · Link-State

The network as a graph

Nodes, links, costs

Model the network as a graph G = (N, E): routers are nodes, links are edges, each with a cost c(x,y).

Cost can be 1 per hop, or inversely related to bandwidth or congestion.

Cost of a path

cost(x₁…xₚ) =
 c(x₁,x₂)+c(x₂,x₃)+…

A routing algorithm finds the least-cost path between two nodes.

Part 2 · Link-State

Dijkstra’s algorithm

The idea

With the full topology known, compute the least-cost path from a source to every other node — iteratively. After k steps, the k nearest destinations are finalised.

Notation

D(v) current least cost to v
p(v) predecessor node on that path
N' nodes whose cost is now final

🔁
Each loop: pick the not-yet-final node with the smallest D, add it to N', then relax its neighbours: D(v) = min( D(v), D(w)+c(w,v) ).

Part 2 · Link-State

From tree to forwarding table

The result of Dijkstra at source u is a shortest-path tree. Reading the first hop toward each destination gives u’s forwarding table:

DestinationOutgoing link (first hop)
v(u, v)
x(u, x)
y(u, x)
w(u, x)
z(u, x)
💡
Key insight: a router doesn’t store the whole path — only the next hop. Forwarding just needs “which door do I push this packet out of?”

Self-Test #1

Foundations & link-state

Tap a green answer to reveal it.

Q Which is the local action and which is network-wide: forwarding or routing?
A Forwarding = local (input→output port); routing = network-wide (plan the whole path).
Q A link-state router knows what about the network?
A The complete topology and all link costs — then runs Dijkstra itself.
Q What does Dijkstra produce for a source node?
A A shortest-path tree → a forwarding table of (destination, first-hop link).

Part 3 · Distance-Vector

Distance-vector & Bellman-Ford

The idea

Each node periodically tells its neighbours its own distance vector (its best-known cost to every destination). Neighbours fold that in.

Bellman-Ford update

Dₓ(y) = minv{ c(x,v) + Dᵥ(y) }

“My cost to y = the cheapest (cost to a neighbour + that neighbour’s cost to y).”

📌
Iterative, asynchronous, distributed: a node recomputes when a local link cost changes or a neighbour’s update arrives — and only tells its neighbours when its own vector changes.

Part 3 · Distance-Vector

“Good news fast, bad news slow”

The count-to-infinity problem

When a link goes down, distance-vector routers can believe each other’s stale routes and slowly count the cost upward in a loop — a routing ping-pong.

Poison reverse

The fix: a router advertising a now-dead route sends the metric as infinity so neighbours immediately stop using the bad path — no loop.

☠️
In RIP: the maximum path is 15 hops, so 16 = infinity = unreachable. Poison reverse advertises 16 to kill a dead route fast.

Part 3 · comparison

Link-state vs distance-vector

Link-State (OSPF)Distance-Vector (RIP)
KnowsThe whole mapOnly neighbours & their vectors
Computes withDijkstra, locallyBellman-Ford, exchanged
ConvergenceFastSlower; loop risks
Message sizeSmall updates, flooded to allFull vectors, only to neighbours
💡
Trade-off: link-state converges fast but every router does more work & storage; distance-vector is simpler but can loop and converge slowly.

Self-Test #2

Distance-vector

Tap a green answer to reveal it.

Q In distance-vector, what does a router send its neighbours, and how often (RIP)?
A Its distance vector (costs to all dests), every 30 seconds.
Q What value means “unreachable” in RIP, and why that number?
A 16 — because RIP’s max valid path is 15 hops, so 16 = infinity.
Q What problem does poison reverse prevent?
A Routing loops / count-to-infinity, by advertising a dead route with infinite metric.

Part 4 · Scaling

Why routing is hierarchical

A flat network of 200 million destinations is impossible — so we group routers into regions:

📈

Scale

Can’t store every destination in one table, and full updates would swamp the links.

🏛️

Autonomy

Each organisation wants to control routing inside its own network. The Internet is a network of networks.

🧠
The answer: group routers into Autonomous Systems (AS). Routers in one AS run the same intra-AS protocol; gateway routers link ASes together.

Part 4 · Scaling

Intra-AS vs inter-AS routing

AS 1
intra-AS: OSPF/RIP
gateway ↔ gateway
inter-AS: BGP
AS 2
intra-AS: OSPF/RIP

Intra-AS (IGP)

Routing within one AS — reachability to internal subnets. Performance-focused. RIP, OSPF, EIGRP.

Inter-AS (EGP)

Routing between ASes — which destinations are reachable through which neighbour AS. Policy-focused. BGP.

Part 4 · Scaling

Hot-potato routing

The rule

If a destination is reachable via two gateways, send the packet toward the gateway with the smallest intra-AS cost — get it out of your own network as fast as possible.

🥔
Think of it like… a hot potato: whichever exit is closest, toss it out there. It’s cheap for you — even if it’s not globally optimal.

Part 5 · Protocols

The routing protocols in this course

Interior (IGP) — inside an AS

RIP — distance-vector, hop count
OSPF — link-state, Dijkstra
EIGRP — Cisco advanced distance-vector

Exterior (EGP) — between ASes

BGP — the de-facto standard that glues the whole Internet together, using reachability + policy.

Part 5 · Protocols · IGP

RIP — Routing Information Protocol

🧭

Distance-vector

Metric = hop count. Max 15; 16 = ∞.

📢

Advertises

Full vector every 30 s, up to 25 nets per message.

⏱️

Dead timer

No update in 180 s → neighbour declared dead.

📨

Transport

Runs over UDP via the routed daemon.

📌
RIP uses poison reverse (advertise 16) to kill dead routes fast. Simple & classic — but the 15-hop limit means it doesn’t scale to large networks. This is the protocol your enterprise capstone can use.

Part 5 · Protocols · IGP

OSPF — Open Shortest Path First

How it works

“Open” = publicly available. Uses the link-state algorithm: each router floods link-state advertisements, builds a full topology map, and runs Dijkstra. Carried directly over IP (not TCP/UDP).

Advanced features (vs RIP)

Authenticated messages · equal-cost multipath · per-TOS metrics · integrated multicast (MOSPF) · hierarchical areas for big domains.

🧠
OSPF = the map-maker. Every router has the same topology database and computes its own shortest paths — fast convergence, no 15-hop limit.

Part 5 · Protocols

EIGRP & BGP

EIGRP · Cisco

An advanced distance-vector protocol (often called “hybrid”). Fast convergence, supports VLSM, sends partial updates only when a metric changes, and stores neighbours’ tables for quick failover.

BGP · inter-AS

The de-facto standard between ASes. Each AS learns which subnets are reachable via its neighbours, propagates that inside, and picks routes by reachability + policy. It’s how a network says “I am here” to the world.

Part 5 · Protocols

Why intra- and inter-AS differ

📜

Policy

Inter-AS: admins control who routes through their network. Intra-AS: one admin, no policy needed.

📐

Scale

Hierarchy shrinks table size and update traffic.

Performance

Intra-AS optimises for speed; inter-AS lets policy win over pure performance.

Self-Test #3

Protocols

Tap a green answer to reveal it.

Q Classify RIP and OSPF as link-state or distance-vector.
A RIP = distance-vector (hop count); OSPF = link-state (Dijkstra).
Q Which protocol routes between Autonomous Systems?
A BGP (the inter-AS / exterior gateway protocol).
Q OSPF is carried over what — TCP, UDP, or IP directly?
A Directly over IP. (RIP uses UDP.)
Q Name one OSPF feature RIP lacks.
A Any of: authentication, equal-cost multipath, per-TOS metrics, hierarchical areas.

One-page cheat sheet

Chapter 9 in a single glance

Two jobs

  • Routing = plan whole path
  • Forwarding = one hop, local
  • Static vs dynamic

Link-state

  • Knows whole map
  • Dijkstra → shortest-path tree
  • → OSPF

Distance-vector

  • Knows neighbours only
  • Bellman-Ford, exchanged
  • Poison reverse (16 = ∞) → RIP

Hierarchy

  • Autonomous Systems (AS)
  • Intra-AS (IGP) vs inter-AS (EGP)
  • Hot-potato routing

IGPs

  • RIP: DV, 15 hops, UDP, 30 s
  • OSPF: LS, Dijkstra, over IP
  • EIGRP: Cisco advanced DV

EGP

  • BGP between ASes
  • Reachability + policy
  • “I am here” to the Internet

Every packet, guided home.

Routers build the map (link-state) or trade signposts (distance-vector), group into Autonomous Systems for scale, and speak RIP/OSPF/EIGRP inside and BGP between. Revise with the cheat sheet, test yourself with the quizzes — and you’re ready.

Next up → Chapter 10 · IPv6

Ready to make it real? Switch to the 🧪 Lab Guide up top and run these concepts on Kali Linux.

1 / 24

Chapter 9 · Hands-on labs

Routing, live on Kali Linux

Six short labs that turn the slides into commands you actually run — read and edit your own forwarding table, watch a packet get routed hop-by-hop across the real Internet, cross Autonomous-System boundaries, and even run a routing daemon with FRRouting. Each maps to a Chapter 9 topic.

SET-UP  ·  Open the Kali Terminal. Tools: iproute2 (ip), traceroute, mtr, whois, and (Lab 5) frr. Install missing ones: sudo apt install -y traceroute mtr-tiny whois frr. The is just the prompt — Copy grabs only the command.
USE RESPONSIBLY  ·  Only trace to hosts you’re allowed to reach, and only change routing on machines you own. The FRR lab runs entirely on your own box with dummy interfaces.
1 · Forwarding table2 · Static route3 · Trace the path 4 · Cross ASes5 · Run FRR6 · Metrics✓ Answers
1

Read Your Forwarding Table

Maps to Ch.9:Forwarding — the local table that maps a destination to an output link; longest-prefix match. You’ll learn:See your own routing table and work out which route a given destination will use. Tools:ip route, ip -6 route
1

Your forwarding table — every destination the kernel knows:

ip route
Representative
default via 192.168.1.1 dev eth0
192.168.1.0/24 dev eth0 proto kernel scope link src 192.168.1.23

The default route is the “gateway of last resort”; the /24 is the directly-connected LAN. That’s a forwarding table — destination → next hop / link.

2

Ask the kernel which route a destination uses (longest-prefix match in action):

ip route get 8.8.8.8
ip route get 192.168.1.50
Representative
8.8.8.8 via 192.168.1.1 dev eth0 ...      <- uses default
192.168.1.50 dev eth0 src 192.168.1.23 ... <- uses the local /24
Why it works  ·  ip route get runs the same forwarding decision a router makes: pick the most specific matching route. Local traffic stays on the LAN; everything else follows the default.
Your turn  ·  If your table had both 10.0.0.0/8 and 10.5.0.0/16, which would ip route get 10.5.0.1 choose, and why? (answer below)
2

Add a Static Route

Maps to Ch.9:Static routing — routes configured by hand rather than learned by a protocol. You’ll learn:Add and remove a static route and watch the forwarding table change — safely, to a black-hole. Tools:sudo ip route add / del
1

Add a static route for a test network (blackhole = safely discard, changes nothing real):

sudo ip route add blackhole 203.0.113.0/24
ip route | grep 203.0.113
Your static route now appears
blackhole 203.0.113.0/24
2

Confirm the kernel would use it:

ip route get 203.0.113.5
3

Clean up — remove your static route:

sudo ip route del blackhole 203.0.113.0/24
Why it works  ·  You just did what an admin does for static routing: hand-place an entry in the forwarding table. No protocol learned it — you configured it, and it vanished the moment you deleted it.
Your turn  ·  Static routes don’t react to failures. Name one situation where static is the right choice, and one where dynamic wins. (answer below)
3

Watch a Packet Get Routed

Maps to Ch.9:Routing across the network — the end-to-end path a packet takes, hop by hop. You’ll learn:See the actual sequence of routers your traffic crosses to reach a distant host. Tools:traceroute, mtr
1

Trace the route to a distant site — each line is one router (hop):

traceroute -n 8.8.8.8
Representative — your hops will differ
1  192.168.1.1     1.0 ms   <- your gateway
2  100.64.0.1      8.4 ms   <- ISP edge
3  72.14.215.85    12.1 ms  <- upstream
...
7  8.8.8.8         14.0 ms  <- destination

This is routing made visible: each hop is a router that made an independent forwarding decision to push your packet one step closer.

2

Live view of the same path with per-hop loss & latency (press q to quit):

mtr -n 8.8.8.8
Why it works  ·  No single router knew the whole path — each just forwarded to its next hop. Chained together, those hops are the route the network computed.
Your turn  ·  Trace to two very different sites. Where do the paths diverge, and what does the shared early portion tell you? (answer below)
4

Cross Autonomous-System Boundaries

Maps to Ch.9:Hierarchical routing — Autonomous Systems, intra-AS vs inter-AS (BGP). You’ll learn:See the AS numbers your traffic passes through — the inter-AS structure BGP glues together. Tools:traceroute -A, whois
1

Trace with AS numbers — each [ASxxxx] is a different Autonomous System:

traceroute -A -n 8.8.8.8
Representative
2  100.64.0.1   [AS12345]  <- your ISP's AS
5  72.14.x.x    [AS15169]  <- Google's AS
8  8.8.8.8      [AS15169]
2

Who owns an AS / IP? Look up a hop:

whois 8.8.8.8 | grep -iE "OrgName|origin|netname|route"

When the AS number changes between hops, your packet has crossed an AS boundary — a place where BGP (inter-AS routing) decided the handoff.

Why it works  ·  The Internet really is a “network of networks.” Each AS runs its own intra-AS protocol; BGP stitches them together, and you just watched your packet hop from one AS to the next.
Your turn  ·  How many different ASes did your trace cross to reach the destination? Which one is your ISP’s? (answer below)
5

Run a Routing Daemon (FRR)

Maps to Ch.9:Dynamic routing protocols — the routed/OSPF/RIP daemons that actually run the algorithms. You’ll learn:Start a real routing suite (FRRouting), enable OSPF/RIP, and use its Cisco-style CLI — all on one box. Tools:frr, vtysh

FRRouting is the open-source descendant of Quagga/zebra — the same daemons the slides mention. You’ll run it on your own machine to meet the tooling (a full multi-router lab belongs in Packet Tracer / GNS3).

1

Install & enable the RIP and OSPF daemons:

sudo apt install -y frr
sudo sed -i 's/^ripd=no/ripd=yes/; s/^ospfd=no/ospfd=yes/' /etc/frr/daemons
sudo systemctl restart frr
2

Enter the router CLI (looks just like Cisco IOS):

sudo vtysh
You get an IOS-style prompt
Hello, this is FRRouting (version ...).
kali# show ip route
kali# configure terminal
kali(config)# router ospf
kali(config-router)# network 192.168.1.0/24 area 0
3

Inspect the routing state from inside vtysh:

show ip route
show ip ospf
show ip rip
Why it works  ·  These are the real distance-vector (ripd) and link-state (ospfd) daemons from the slides. On one box you won’t form neighbours, but you’re driving the exact protocol engines — with the same commands you’d use on a router.
Your turn  ·  In show ip ospf, is OSPF using the link-state or distance-vector algorithm? What single word in the name tells you? (answer below)
6

Metrics & Least-Cost Choices

Maps to Ch.9:Least-cost paths & metrics — how a router breaks ties and prefers one route over another. You’ll learn:Give two routes different metrics and watch the kernel pick the cheaper one. Tools:sudo ip route add ... metric
1

Add two blackhole routes to the same test net with different metrics (lower = preferred):

sudo ip route add blackhole 198.51.100.0/24 metric 100
sudo ip route add blackhole 198.51.100.0/24 metric 50
2

Which one wins? Ask the kernel:

ip route show 198.51.100.0/24
ip route get 198.51.100.9
The lower-metric route is chosen
blackhole 198.51.100.0/24 metric 50
blackhole 198.51.100.0/24 metric 100
198.51.100.9 dev lo ... (via the metric-50 route)
3

Clean up:

sudo ip route del blackhole 198.51.100.0/24 metric 50
sudo ip route del blackhole 198.51.100.0/24 metric 100
Why it works  ·  The metric is a cost, exactly like link cost in the graph model. Faced with two paths to the same destination, the router picks the least-cost one — the heart of every routing algorithm.
Your turn  ·  In RIP the metric is hop count; in OSPF it’s based on bandwidth. Why might OSPF pick a longer (more-hops) path than RIP would? (answer below)

Answer Key & Where Next

Lab 1. It chooses 10.5.0.0/16longest-prefix match: the most specific (longest mask) route that contains the destination always wins.

Lab 2. Static is right for a small stub network or a single edge link (like your capstone’s default route to the ISP). Dynamic wins when there are many routers/paths that change, so routes must be re-learned automatically.

Lab 3. Paths usually share the first few hops (your gateway + ISP) then diverge once traffic reaches the wider Internet and heads toward each destination’s network. The shared portion is your own ISP’s path out.

Lab 4. Count the distinct [ASxxxx] tags — typically 2–4. Your ISP’s AS is the first non-private one after your gateway.

Lab 5. OSPF uses the link-state algorithm — the words “Shortest Path First” refer to Dijkstra’s shortest-path-first computation over a full topology map.

Lab 6. OSPF costs are bandwidth-based, so a path with more hops but faster links can have a lower total cost than a shorter path over slow links — RIP, counting only hops, can’t see that difference.

This lab’s toolConnects to…
ip route / static routes (Labs 1–2)Chapter 4 & the NSSA-241 capstone — configuring routes on a router
traceroute / TTL (Lab 3)Chapter 5 — how traceroute abuses the IP TTL field
AS numbers / BGP (Lab 4)Inter-AS routing — the global routing table
FRR ospfd/ripd (Lab 5)The distance-vector & link-state algorithms, running for real
Nice work  ·  You’ve now seen every part of Chapter 9 at the terminal — the forwarding table, static routes, routed paths, AS boundaries, and real routing daemons.
Chapter 9 — Routing Algorithms & Protocols · Slides + Hands-On Kali Labs