1 of 71

Discussion 3

1

CS 168, Summer 2025 @ UC Berkeley

Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao, Iuniana Oprescu

Routing I 🫂

2 of 71

Logistics

  • Project 1B: Traceroute Error Handling
    • Deadline: Thursday, July 3rd

​

​

  • Still somewhat far ahead: Midterm on July 22nd, 7-9pm (put it in your calendar)!

​

3 of 71

Distance-Vector Algorithm Sketch

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

4 of 71

Distance-Vector Algorithm Sketch – Routing vs. Forwarding

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

Routing announcements ("I can reach A") propagated outward, away from A.

When forwarding packets toward A, packets travel inward, toward A.

One-line algorithm: If you hear about a path to a destination, tell all your neighbors!

​

5 of 71

Distance-Vector Algorithm Sketch – Multiple Destinations

What if there are multiple destinations?

  • Run the same path propagation algorithm, once per destination.
  • Routers use forwarding tables to keep track of the next-hop of each destination.

​

We'll focus on a single destination for simplicity.

  • But the protocol can extend to multiple destinations.

6 of 71

Rule 1: Bellman-Ford Updates

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

7 of 71

Multiple Paths Advertised

What if you hear about multiple paths to a single destination?

  • Accept the shorter path.

R5

R3

R4

R2

R1

A

A is 3 away from me.

A is 2 away from me.

I prefer what R4 is offering.

A this way

8 of 71

Multiple Paths Advertised

You might not hear about both paths simultaneously.

  • In the forwarding table, record the best-known cost to a destination.
  • If your table doesn't have a path to a destination, accept any path you hear about.

​

R5

R3

R4

R2

R1

A

A is 3 away from me.

R5's Table

To:

Via:

Cost:

A

R3

4

9 of 71

Multiple Paths Advertised

You might not hear about both paths simultaneously.

  • In the forwarding table, record the best-known cost to a destination.
  • If your table doesn't have a path to a destination, accept any path you hear about.
  • If you hear about a better path later, update the table (next-hop and cost).

​

R5

R3

R4

R2

R1

A

R5's Table

To:

Via:

Cost:

A

R3�R4

4�3

A is 2 away from me.

I like this new path better. I'll abandon the old one.

10 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear about a path to that destination, update table if:
    • The destination isn't in the table.
    • The advertised cost is better than best-known cost.
  • Then, tell all your neighbors.

11 of 71

Unequal Costs

Not all link costs are 1.

  • When a neighbor advertises a path, the cost via that path is the sum of:
    • Link cost from you to the neighbor.
    • Cost from neighbor to destination (as advertised by neighbor).

R3

R1

R2

1

10

A is 5 away from me.

R3's Table

To:

Via:

Cost:

A

R1

1+5 = 6

12 of 71

Unequal Costs

Not all link costs are 1.

  • When a neighbor advertises a path, the cost via that path is the sum of:
    • Link cost from you to the neighbor.
    • Cost from neighbor to destination (as advertised by neighbor).

R3

R1

R2

1

10

R3's Table

To:

Via:

Cost:

A

R1

1+5 = 6

A is 3 away from me.

This path actually costs 10+3=13. I'll keep using the cost 6 path and reject this.

13 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear about a path to that destination, update table if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
  • Then, tell all your neighbors.

14 of 71

Distributed Bellman-Ford Algorithm

Careful viewers might have noticed this operation looks familiar.

  • "If cost to neighbor + cost from neighbor to destination < best-known cost,�accept update."
  • This is the relaxation operation in Dijkstra's shortest path algorithm!

Bellman-Ford is another relaxation-based shortest path algorithm.

  • Relax every edge repeatedly until we get shortest paths.
  • Unlike Dijkstra's, does not require relaxing the edges in any specific order.

Distance-vector algorithms are a distributed, asynchronous version of Bellman-Ford.

  • Distributed: Each router relaxes its own links. No global mastermind.
  • Asynchronous: Nobody is syncing when the routers do relaxations.

15 of 71

Rule 2: Updates from Next-Hop

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

16 of 71

Updates From the Current Next-Hop

Recall our routing challenges: Topology can change.

  • So far: We update if we get a better path (or if we didn't have a path before).
  • Fix: If our current next hop sends us an announcement, accept it,�even if the path is worse.
  • This lets the next-hop notify us if the topology changed.

17 of 71

Convergence

If the network never changes:

  • After running this protocol for some time, it will converge.
  • Everyone's forwarding table has the least-cost next hop.
  • All future announcements will be rejected.

If a change happens (e.g. a link goes down):

  • Some new announcements are sent.
  • Some forwarding tables are updated.
  • Eventually, we converge again to the new routing state.

The network topology is constantly changing, so routers run the protocol indefinitely.

  • Steady-state occurs when the network has converged.
  • In steady-state, everything stays the same until the next topology change.

18 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear an advertisement, update table if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
    • The advertisement is from current next-hop. (#2)
  • Then, advertise to all your neighbors.

19 of 71

Rule 3: Resending and Expiring

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

20 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear an advertisement, update table if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
    • The advertisement is from current next-hop. (#2)
  • Advertise to all your neighbors when the table updates, and periodically. (#3)

21 of 71

Handling Failures

Recall our routing challenges: Links and routers can fail.

Solution: Each route has a finite time to live (TTL).

  • Periodic advertisements help us confirm that a route still exists.
    • When we get an advertisement, reset ("recharge") the TTL.
  • If a link goes down, we stop getting periodic updates, and the TTL will expire.
    • If the TTL expires, delete the entry from the table.

22 of 71

Timers

Routers maintain multiple timers:

  • Advertisement interval: How long before we advertise routes to neighbors.
    • Usually one timer for all entries in the table.
  • TTL: How long before we expire a route.
    • Each table entry has its own TTL.

23 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear an advertisement, update table and reset TTL if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
    • The advertisement is from current next-hop. (#2)
  • Advertise to all your neighbors when the table updates, and periodically. (#3)
  • If a table entry expires, delete it. (#3)

​

This is a mostly-functional protocol now.�Let's add some optimizations for faster convergence.

24 of 71

Rule 4: Poison Expired Routes

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

25 of 71

Poison for Fast Route Expiry

Key problem: When something fails, nobody's reporting it.

​

Solution: Poison ☠️.

  • Explicitly advertise that a path is busted.
  • A path with cost infinity represents a busted path.
  • This path propagates just like any other path.
    • Routers accept the poison path to invalidate the route.
  • Can be much faster than waiting for timeouts!

​

26 of 71

Accepting and Advertising Poison

When you get a poison advertisement from the current next-hop:

  • Accept it, even if you have a better path.
    • Because the next-hop is telling you that the route no longer exists.
    • Similar to Rule #2: accept worse paths from current next-hop.

​

When you update the table with a poison route:

  • Reset the TTL, just like any other table update.
  • Advertise the poison to your neighbors, so they also know about the busted route.

​

Don't forward packets along a poisoned route.

To:

Via:

Cost:

A

R1

∞

Don't forward to R1.

27 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear an advertisement, update table and reset TTL if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
    • The advertisement is from current next-hop. (#2)�Includes poison advertisements. (#4)
  • Advertise to all your neighbors when the table updates, and periodically. (#3)
  • If a table entry expires, make the entry poison and advertise it. (#3, #4)

28 of 71

Rule 5A/5B:�Split Horizon / Poison Reverse

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

29 of 71

Split Horizon / Poison Reverse – The Problem

The problem: When I give someone a path, they advertise it back to me.

  • Path goes from me → them → me.
  • Path with extra loop is always longer, so I'd never accept.
  • But if I lost my earlier routes, I might accept.
  • I might not realize the path is going through me.

​

30 of 71

Poison Reverse vs. Split Horizon

R2

I can reach A.

Split Horizon:

I can reach A.

Poison Reverse:

R2

R2

I can reach A.

R2

I can reach A.

I cannot reach A.

Don't advertise anything back to R1.

Explicitly advertise poison back to R1 (infinity).

R1

R1

R1

R1

31 of 71

Poison Reverse vs. Split Horizon

Suppose we end up with a routing loop somehow.

Split horizon: No poison is sent.

  • Loop stays until the routes expire.

​

R2's Table

To:

Via:

Cost:

A

R3

4

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

3

I got this route from R3, so don't send it to R3.

I got this route from R2, so don't send it to R2.

32 of 71

Poison Reverse vs. Split Horizon

Suppose we end up with a routing loop somehow.

Poison reverse: R3 explicitly sends poison back to R2.

  • Loop is immediately eliminated!
  • Faster than split horizon.

R2's Table

To:

Via:

Cost:

A

R3

4

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

3

I'm R3, and A is ∞ away from me.

R3 is my next-hop, so I accept.

R2's Table

To:

Via:

Cost:

A

R3

∞

I got this route from R2, so send poison to R2.

33 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear an advertisement, update table and reset TTL if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
    • The advertisement is from current next-hop. (#2)�Includes poison advertisements. (#4)
  • Advertise to all your neighbors when the table updates, and periodically. (#3)
    • But don't advertise back to the next-hop. (#5A)
    • ...Or, advertise poison back to the next-hop. (#5B)
  • If a table entry expires, make the entry poison and advertise it. (#3, #4)

34 of 71

Rule 6: Count to Infinity

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

35 of 71

Count to Infinity – The Problem

Split horizon (or poison reverse) helps us avoid length-2 loops.

  • R1 forwards to R2.
  • R2 forwards to R1.

​

But we can still get routing loops with 3 or more routers.

36 of 71

Count to Infinity – The Problem

Suppose the tables reach steady-state.

A

R3's Table

To:

Via:

Cost:

A

Direct

1

R1's Table

To:

Via:

Cost:

A

R3

2

R2's Table

To:

Via:

Cost:

A

R3

2

R1

R2

R3

37 of 71

Count to Infinity – The Problem

Link goes down! A now unreachable.

R3 updates table and sends poison.

Poison reaches R2, but not R1!

I'm R3, and A is�∞ away from me.

R1

R2

R3

A

R3's Table

To:

Via:

Cost:

A

Direct

1

R1's Table

To:

Via:

Cost:

A

R3

2

R2's Table

To:

Via:

Cost:

A

R3

2

R3's Table

To:

Via:

Cost:

A

Direct

∞

I'm R3, and A is�∞ away from me.

Dropped!

R2's Table

To:

Via:

Cost:

A

R3

∞

38 of 71

Count to Infinity – The Problem

At this point, R3 and R2 know A is unreachable.

But R1 still thinks there's a path to A!

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

Direct

∞

R1's Table

To:

Via:

Cost:

A

R3

2

R2's Table

To:

Via:

Cost:

A

R3

∞

39 of 71

Count to Infinity – The Problem

R1 announces it can reach A.

Split horizon: R1's path came from R3, so don't tell R3.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

Direct

∞

R1's Table

To:

Via:

Cost:

A

R3

2

R2's Table

To:

Via:

Cost:

A

R3

∞

I'm R1, and A is�2 away from me.

R2's Table

To:

Via:

Cost:

A

R1

3

40 of 71

Count to Infinity – The Problem

R2 announces it can reach A.

Split horizon: R2's path came from R1, so don't tell R1.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

Direct

∞

R1's Table

To:

Via:

Cost:

A

R3

2

R2's Table

To:

Via:

Cost:

A

R1

3

I'm R2, and A is�3 away from me.

R3's Table

To:

Via:

Cost:

A

R2

4

41 of 71

Count to Infinity – The Problem

R3 announces it can reach A.

Split horizon: R3's path came from R2, so don't tell R2.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

4

R1's Table

To:

Via:

Cost:

A

R3

2

R2's Table

To:

Via:

Cost:

A

R1

3

I'm R3, and A is�4 away from me.

R1's Table

To:

Via:

Cost:

A

R3

5

42 of 71

Count to Infinity – The Problem

We keep advertising in a cycle, and costs keep increasing!

Split horizon can't save us.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

4

R1's Table

To:

Via:

Cost:

A

R3

5

R2's Table

To:

Via:

Cost:

A

R1

3

I'm R1, and A is�5 away from me.

R2's Table

To:

Via:

Cost:

A

R1

6

43 of 71

Count to Infinity – The Problem

We keep advertising in a cycle, and costs keep increasing!

Split horizon can't save us.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

4

R1's Table

To:

Via:

Cost:

A

R3

5

R2's Table

To:

Via:

Cost:

A

R1

6

I'm R2, and A is�6 away from me.

R3's Table

To:

Via:

Cost:

A

R2

7

44 of 71

Count to Infinity – The Problem

We keep advertising in a cycle, and costs keep increasing!

Split horizon can't save us.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

7

R1's Table

To:

Via:

Cost:

A

R3

5

R2's Table

To:

Via:

Cost:

A

R1

6

I'm R3, and A is�7 away from me.

R1's Table

To:

Via:

Cost:

A

R3

8

45 of 71

Count to Infinity – The Problem

We keep advertising in a cycle, and costs keep increasing!

Split horizon can't save us.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

7

R1's Table

To:

Via:

Cost:

A

R3

8

R2's Table

To:

Via:

Cost:

A

R1

6

I'm R1, and A is�8 away from me.

R2's Table

To:

Via:

Cost:

A

R1

9

46 of 71

Count to Infinity – The Problem

We keep advertising in a cycle, and costs keep increasing!

Split horizon can't save us.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

7

R1's Table

To:

Via:

Cost:

A

R3

8

R2's Table

To:

Via:

Cost:

A

R1

9

I'm R2, and A is�9 away from me.

R3's Table

To:

Via:

Cost:

A

R2

10

47 of 71

Count to Infinity – The Problem

We keep advertising in a cycle, and costs keep increasing!

Split horizon can't save us.

A

R1

R2

R3

R3's Table

To:

Via:

Cost:

A

R2

10

R1's Table

To:

Via:

Cost:

A

R3

8

R2's Table

To:

Via:

Cost:

A

R1

9

I'm R3, and A is�10 away from me.

R1's Table

To:

Via:

Cost:

A

R3

11

48 of 71

Count to Infinity – Solution

Solution: Enforce a maximum cost.

  • 15 is a common choice.
  • All numbers ≥ 16 are considered infinity.

​

Result:

  • Loop will stop when all costs reach 16.
  • Busted path will expire, or get replaced by another non-infinite-cost path.

49 of 71

The Distance-Vector Algorithm So Far

For each destination:

  • If you hear an advertisement, update table and reset TTL if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
    • The advertisement is from current next-hop. (#2)�Includes poison advertisements. (#4)
  • Advertise to all your neighbors when the table updates, and periodically. (#3)
    • But don't advertise back to the next-hop. (#5A)
    • ...Or, advertise poison back to the next-hop. (#5B)
    • Any cost ≥ 16 is advertised as ∞. (#6)
  • If a table entry expires, make the entry poison and advertise it. (#3, #4)

50 of 71

Eventful Updates

Distance-Vector Correctness

  • Algorithm Sketch
  • Rule 1: Bellman-Ford Updates
  • Rule 2: Updates From Next-Hop
  • Rule 3: Resending and Expiring

Distance-Vector Enhancements

  • Rule 4: Poison Expired Routes
  • Rule 5A: Split Horizon
  • Rule 5B: Poison Reverse
  • Rule 6: Count To Infinity
  • Eventful Updates

51 of 71

Eventful Updates

When do we send advertisements?

  • When the table changes (triggered updates).
    • When we accept a new advertisement.
    • When a new link is added. (Add static routes and advertise them.)
    • When a link goes down. (Poison routes and advertise poison.)
  • Periodically (once every "advertisement interval").
  • When a table entry expires.

​

Triggered updates are an optimization.

  • Instead of advertising when the table changes, we could just wait for the interval. Protocol is still correct.
  • Triggered updates help us converge faster.

52 of 71

Our Completed Distance-Vector Algorithm

For each destination:

  • If you hear an advertisement, update table and reset TTL if:
    • The destination isn't in the table.
    • Advertised cost + link cost to neighbor < best-known cost. (#1)
    • The advertisement is from current next-hop. (#2)�Includes poison advertisements. (#4)
  • Advertise to all your neighbors when the table updates, and periodically. (#3)
    • But don't advertise back to the next-hop. (#5A)
    • ...Or, advertise poison back to the next-hop. (#5B)
    • Any cost ≥ 16 is advertised as ∞. (#6)
  • If a table entry expires, make the entry poison and advertise it. (#3, #4)

53 of 71

Worksheet

  • Distance Vector
  • Split Horizon and Poison
  • Count to Infinity

54 of 71

Question 1: Distance Vector

55 of 71

Question 1: Distance Vector

56 of 71

Question 1: Distance Vector

57 of 71

Question 1: Distance Vector

58 of 71

Question 1: Distance Vector

59 of 71

Question 1: Distance Vector

60 of 71

Question 1: Distance Vector

61 of 71

Question 1: Distance Vector

62 of 71

Worksheet

  • Distance Vector
  • Split Horizon and Poison
  • Count to Infinity

63 of 71

Question 2: Split Horizon and Poison

64 of 71

Question 2: Split Horizon and Poison

65 of 71

Worksheet

  • Distance Vector
  • Split Horizon and Poison
  • Count to Infinity

66 of 71

Question 3: Count to Infinity

67 of 71

Question 3: Count to Infinity

68 of 71

Question 3: Count to Infinity

69 of 71

Question 3: Count to Infinity

70 of 71

Question 3: Count to Infinity

71 of 71

Questions?

Feedback Form: https://tinyurl.com/cs168-su25-disc-feedback