1 of 115

1

CS 168, Spring 2026 @ UC Berkeley

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

Distance-Vector Protocols

Lecture 6 (Routing 2)

2 of 115

Some Announcements

Instructor Office Hours are cancelled this week (I am away)

Office hours will be as per usual next week.

Reminder: I will be travelling until next Thursday.

Will post recordings for both Tuesday and Thursday.

3 of 115

Recall: Routing Principles

Routing allows us to find paths through the network.

Have to handle constant change, a non-global view, and best-effort links

The Internet uses destination-based forwarding.

Each router keeps a table, mapping destinations to next hops.

We need a valid directed delivery tree with no dead ends and no loops!

R1

R7

R5

C

R6

D

R2

R3

R4

R8

B

A

R3's Table (Conceptual)
Destination	Next Hop
A	R2
B	R4
C	R7
D	R4

Static or direct routes can be hard coded!

4 of 115

Distance-Vector Algorithm Sketch

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

5 of 115

Distance-Vector Algorithm Sketch

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

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

A is 1 away from me. I should tell my neighbors.

A this way

so let's Jump Right In so before we talk about any rules let me just give

29:41

you a one slide one sentence version of this algorithm so all you have to do is

29:47

that if you hear about a path to a destination tell all your neighbors that's the oneliner version of this

29:54

algorithm we're then going to spend a lot of time making it good but at a high level this is what it looks like so what

30:00

does that mean let's say R1 wakes up one day and it sees that it has a hardcoded route to a so remember we said that

30:08

static routes are the ones that are hardcoded if you're directly connected to a host then we will hardcode an entry

30:15

into r1's table saying that your next top to a is direct so R1 wakes up one

30:21

day with this hardcoded entry and says I know a way to get to a so you know what I should do I should spread the love I

30:27

should tell all of my neighbors that if they want to reach a they should come through me so R1 thinks I can reach a so

30:35

let me go tell all of my neighbors so that if they want to reach a they can come through me as well so that's what

6 of 115

Distance-Vector Algorithm Sketch

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

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

A this way

A is 1 away from me.

7 of 115

Distance-Vector Algorithm Sketch

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

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

A this way

We just found a way to reach A. We should tell our neighbors.

A this way

8 of 115

Distance-Vector Algorithm Sketch

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

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

A this way

A is 2 away from me.

A is 2 away.

A this way

9 of 115

Distance-Vector Algorithm Sketch

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

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

A this way

We just found a way to reach A. We should tell our neighbors.

A this way

10 of 115

Distance-Vector Algorithm Sketch

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

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

A this way

A is 3 away.

11 of 115

Distance-Vector Algorithm Sketch

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

R2

A

R3

R1

R5

R4

R6

R7

R8

R9

R10

R11

R12

R13

R14

R15

A this way

We did it! Everybody knows the next-hop to A now.

12 of 115

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.

remember there is a critical difference between routing and

34:36

forwarding and remember routing is the process of all the routers talking to each other to form uh valid forwarding

34:45

tables and forwarding is the process of receiving a packet from a user and using

34:50

the table to forward packets so routing is building the tables forwarding is using the tables that you just built

34:58

and something you'll notice if you look at the demo is that the direction of packets being sent in routing and

35:04

forwarding are opposites and this always trips people up so notice that when

35:09

everyone was sharing information with their friends about the fact that they can reach a that information propagated

35:16

outwards so it started at a and R1 at first these were the only two people who knew about a but slowly that information

35:24

radiated outwards and from a going F further and further and further away from a from the left side of your screen

35:31

to the right side of your screen propagating outwards from a until everyone knew the information by

35:37

contrast when you are forwarding when you actually have the tables filled in and you're ready to use the tables when

35:44

someone sends you a packet and says please forward this packet toward a then the packets travel inwards toward a

13 of 115

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.

14 of 115

Rule 1: Bellman-Ford Updates

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

15 of 115

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

38:40

in the picture we showed you earlier everything was nice there was only a single path so when you heard about the

38:46

way to reach a you just pointed your forwarding table in the direction toward a but that might not always be the case

38:54

sometimes there are multiple paths to reach a destination so in this example as before R1 is the only one that knows

39:01

about a at the very beginning so it tells all its friends it tells R2 and R4

39:06

and then R2 tells R3 and then R3 tells R5 and then R4 tells R5 so what happened

39:13

here is R3 and R4 both have a way to reach a so R5 is going to hear two

39:20

different paths R3 is going to say I can reach a if you send packets to me I'll get to a but R4 will also say if you

39:28

send packets to me I will also re J so R5 now has a choice it can either

39:33

program its forwarding table to go via R3 or to go via R4 the next top to a

39:39

could either be R3 or R4 there's a choice and remember we said that both of these would be valid paths they would

39:46

send packets to a but one of them is better than the other in other words the cost is less and ultimately we want the

39:53

least cost path so what R5 should really do is prefer the path with less cost

16 of 115

Multiple Paths Advertised

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

Accept the shorter path.

R5

R3

R4

R2

R1

A

17 of 115

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

one more problem is that you

42:05

might actually not hear about both of the paths at the same time so in the picture we had before everything was

42:10

nice R5 heard about two different paths and it got to pick the best one but that

42:16

might not always happen what if the costs come in at different times for example you your R5 and you hear about

42:23

the advertisement from R3 so R3 says I can reach a I'm 308 so what should R5 do

42:30

at this point because R5 hasn't heard the second path yet it only knows about

42:35

a single path to a so what R5 has to do for now is say well is this the best I

42:41

don't know but it's what I have right now so I'm going to go ahead and use this one for now and if I hear a better

42:47

one later I can change my mind so routers are allowed to change their mind if they hear about something better and

42:53

what that means is because routers have to be able to change their minds when they hear better routes they should also

43:00

keep track of the routes so so far our forwarding tables just said a destination and a Next Top we are now

43:07

going to add a third column that used to not be there and the third column helps us keep track of the best known cost to

43:15

the destination so before this little packet came in R5 had no idea where a

43:21

was or even that a existed but then it heard a message from R3 and R3 said I am

43:26

r three if you want to send packets to a send them through me I am cost three

43:32

away and R5 thinks well that's great if you're three away I must be four away so

43:39

I will write down that I can pass packets to R3 and they will reach a and

43:44

I'll also leave a note to myself that this best known path has cost four and

43:50

maybe I'll get a better one later who knows but for now at least I have a path to a I don't know if it's the best one

43:56

maybe maybe better ones will come along maybe no other paths will come along but that's what I have right now and later

18 of 115

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.

44:03

you might hear a different path so now later down the line R4 sends a message to R5 and says I'm R4 I can reach a and

44:12

if you send it to me I am two away from a so R5 now thinks and realizes actually

44:17

you know what the old path that I had which was cost four is not the best one

44:22

this one is better R4 is 2 away so I must be three away so so actually this

44:27

one has cost three that's better than four three is better than four so what

44:32

R5 can now do is R5 can change its mind it says actually I don't need that path

44:38

via R3 anymore with cost 4 I really want the path via R4 with cost three that's

44:45

better so R5 says I like the new one better and it's okay to change your mind and abandon old ones so this is what you

44:52

have to do because of the fact that there are multiple paths and they might not all be revealed to you at the same

44:58

time

19 of 115

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.

20 of 115

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

21 of 115

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.

22 of 115

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.

23 of 115

Distributed Bellman-Ford Algorithm

Some of you 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.

24 of 115

Bellman-Ford Algorithm

The centralized Bellman-Ford algorithm for a single destination:

def bellman_ford(dst, routers, links):

� distance = {}; nexthop = {}

� for r in routers:� distance[r] = INFINITY� nexthop[r] = None� distance[dst] = 0� � for _ in range(len(routers)-1):� for (r1, r2, linkcost) in links:

� if distance[r1] + linkcost < distance[r2]:� distance[r2] = distance[r1] + linkcost� nexthop[r2] = r1

� return distance, nexthop

Everyone starts infinity away from the destination, except for the destination itself (0 away).

The relaxation operation.

Bellman-Ford loops through nodes and relaxes repeatedly.

In distance-vector, each router relaxes in parallel, with both directions as links between routers.

Here is the centralized bellman-ford algorithm in pseudo code. Let’s step through each component and then we’ll talk about how it’s distributed.

In the distributed version have to take out this for loop. Routers can’t get in line or have a guarantee all will do this in order.

ow the difference with our version is that our version is distributed so we

58:35

don't have a list of all the routers we don't have a list of all the links no one is telling us that stuff so instead

58:42

we're still going to do the same thing but we're going to do it in a distributed way so this blue section it

58:47

still exists but instead of initializing these dictionaries the way they did in their centralized version we'll just

58:53

have every router initialize their forwarding tables to for example empty

25 of 115

Bellman-Ford Demo

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

26 of 115

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)

Then, advertise to all your neighbors.

Terminology note:

Sending "I'm R1, and I can reach A with cost 5" is called announcing or advertising a route.

27 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:

28 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:

Static routing: Someone hard-codes R1's table to say it can reach A.

29 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:

I found a way to reach A!

Time to tell all my neighbors.

30 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:

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

New advertisement!

I don't have a way to reach A yet, so I'll accept.

R2's Table
To:	Via:	Cost:
A	R1	1+1=2

1 (link cost to R1), plus�1 (advertised cost).

31 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R3's Table
To:	Via:	Cost:

Time to tell everyone about my shiny new path to A.

R2's Table
To:	Via:	Cost:
A	R1	2

32 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R3's Table
To:	Via:	Cost:

R2's Table
To:	Via:	Cost:
A	R1	2

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

Notice: R2's announcement doesn't include the next-hop.�Nobody else cares how R2 reaches A, just that R2 can reach A.

33 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R3's Table
To:	Via:	Cost:

R2's Table
To:	Via:	Cost:
A	R1	2

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

New advertisement?!

This new path costs 1+2=3.

I already have a cost 1 path.

No thanks.

34 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R3's Table
To:	Via:	Cost:

R2's Table
To:	Via:	Cost:
A	R1	2

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

New advertisement?!?

I don't have a path to A yet, so I'll accept.

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

R3's Table
To:	Via:	Cost:
A	R2	1+2=3

1 (link cost to R2), plus�1 (advertised cost).

35 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:
A	R1	2

Time to advertise my exciting new path to A.

R3's Table
To:	Via:	Cost:
A	R2	3

36 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:
A	R1	2

R3's Table
To:	Via:	Cost:
A	R2	3

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

New advertisement?!??!?!!!?

This new path costs 1+3=4.

I already have a cost 2 path.

No thanks.

37 of 115

Bellman-Ford Demo

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:
A	R1	2

R3's Table
To:	Via:	Cost:
A	R2	3

We did it! Everybody has a way to reach A now.

A this way

38 of 115

Rule 2: Updates from Next-Hop

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

39 of 115

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.

R3

R1

R2

R3's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:
A	R2	1+3 = 4

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

A wasn't in my table. Accept!

1:12:28

actually the topology might have changed maybe like a link went down or an operator changed the cost of one of the

1:12:35

links so I know I said it's three earlier but I've actually changed my mind the graph itself has changed so I

1:12:42

have changed my mind and a should really be eight away so when you see a message

1:12:47

like this you're tempted to see it and say oh was a and nine that's worse than four reject but actually R2 might be

1:12:54

trying to tell you something it's trying to tell you hey the path has actually

1:12:59

changed because the network topology itself changed so you should really

1:13:04

listen to me because I'm trying to tell you new information so we need to change our rule to not just reject all things

1:13:11

that are worse but we need to accept in a case like this so R3 really should say

1:13:19

well I currently am going via R2 but R2 has just come along and told me that

1:13:24

they changed their mind so this really shouldn't say four anymore what should it say this should

1:13:29

really say nine so I'm still forwarding via R2 to a but the new cost is nine

40 of 115

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.

R3

R1

R2

R3's Table
To:	Via:	Cost:
A	R2	4

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

1+8=9 is worse than 4.

Reject!

41 of 115

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.

R3

R1

R2

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

R2 is the next-hop. Accept!

R3's Table
To:	Via:	Cost:
A	R2	4

R3's Table
To:	Via:	Cost:
A	R2	1+8=9

Hi, it's R2 again. I know I said A is 3 away from me earlier, but that's changed. Now A is 8 away.

What R2 is really saying:

42 of 115

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.

43 of 115

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.

44 of 115

Rule 3: Resending

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

45 of 115

Ensuring Reliability

Recall our routing challenges: Packets can get dropped.

Solution: Resend advertisements every X seconds.

X is the "advertisement interval."
This should work eventually, assuming the link is functional (>0% delivery rate).

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:

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

Huh? Did someone say something?

Dropped!

46 of 115

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)

47 of 115

Rule 4: Expiring

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

48 of 115

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.

R3

R2

Didn't have a path to A. Accept!

R3's Table
To:	Via:	Cost:	TTL:

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

R3's Table
To:	Via:	Cost:	TTL:
A	R2	6	11

t = 0

Need another confirmation of this route in the next 11 seconds.

A

49 of 115

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.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	6	10

t = 1

t = 2

9

t = 3

8

t = 4

7

R3

R2

A

50 of 115

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.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	6	11

t = 5

We got a confirmation!�Reset TTL back to 11.

I'm still R2, and A is still 5 away from me.

R3

R2

A

51 of 115

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.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	6	10

t = 6

9

t = 7

8

t = 8

7

t = 9

Link goes down!

6

t = 10

5

t = 11

4

t = 12

3

t = 13

2

t = 14

1

t = 15

R3

R2

A

52 of 115

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.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	6	0

t = 16

Timeout! Delete expired entry.

Link goes down!

R3

R2

A

53 of 115

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.

54 of 115

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. (#4)

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

55 of 115

Rule 5: Poison Expired Routes

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

56 of 115

Route Expiry is Slow

Waiting for routes to expire is slow. Let's watch the demo again.

R1 is offering a new path to A, but R3 has to wait for the old busted route to expire before accepting the new path.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	2	13

t = 3

12

R3

R2

R1

A

Assume that by t=3, R3 knows a route to A.

t = 4

11

t = 5

57 of 115

Route Expiry is Slow

Waiting for routes to expire is slow. Let's watch the demo again.

R1 is offering a new path to A, but R3 has to wait for the old busted route to expire before accepting the new path.

R3's Table
To:	Via:	Cost:	TTL:
R2	A	2	10

t = 6

Pause right here.

At this point, we know the path via R2 is busted.
But R3 won't know until the timeout 10s later.
If R3 knew now, it could accept the new path. Instead, R3 rejects the new path, thinking the busted path is still valid.

Link goes down!

No thanks, I already have a cost 2 path.

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

R3

R2

R1

A

58 of 115

Route Expiry is Slow

Waiting for routes to expire is slow. Let's watch the demo again.

R1 is offering a new path to A, but R3 has to wait for the old busted route to expire before accepting the new path.

R3's Table
To:	Via:	Cost:	TTL:
R2	A	2	9

8

7

6

t = 7

t = 8

t = 9

t = 10

R3

R2

R1

A

59 of 115

Route Expiry is Slow

Waiting for routes to expire is slow. Let's watch the demo again.

R1 is offering a new path to A, but R3 has to wait for the old busted route to expire before accepting the new path.

R3's Table
To:	Via:	Cost:	TTL:
R2	A	2	5

t = 11

Again, R3 is forced to reject this new path, because it's still waiting for the busted path to time out.

No thanks, I already have a cost 2 path.

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

R3

R2

R1

A

60 of 115

Route Expiry is Slow

Waiting for routes to expire is slow. Let's watch the demo again.

R1 is offering a new path to A, but R3 has to wait for the old busted route to expire before accepting the new path.

R3's Table
To:	Via:	Cost:	TTL:
R2	A	2	4

3

2

1

t = 12

t = 13

t = 14

t = 15

R3

R2

R1

A

61 of 115

Route Expiry is Slow

Waiting for routes to expire is slow. Let's watch the demo again.

R1 is offering a new path to A, but R3 has to wait for the old busted route to expire before accepting the new path.

R3's Table
To:	Via:	Cost:	TTL:
R2	A	2	0

t = 16

Timeout! Delete expired entry.

R3

R2

R1

A

Sure, I'll accept, my old path just expired.

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

Can we alert R3 of the failure sooner, so it can delete the old busted path earlier (and start accepting new paths)?

62 of 115

Poison for Fast Route Expiry

Waiting for routes to expire is slow.

You keep a busted path in the forwarding table for a long time.

Packets might get lost during this time.
You might advertise that busted route to other people.

You might reject new paths, thinking the busted path is still valid.

Could have converged on a better path earlier.

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!

63 of 115

Poison for Fast Route Expiry

Poison lets us detect busted routes faster. Let's watch the demo again.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	2	13

t = 3

12

R3

R2

R1

A

Assume that by t=3, R3 knows a route to A.

t = 4

11

t = 5

64 of 115

Poison for Fast Route Expiry

Poison lets us detect busted routes faster. Let's watch the demo again.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	2	10

t = 6

R3 updates the table to indicate the path is busted. TTL recharges, just like any other update.

Link goes down!

Looks like the path via R2 is busted.

R3

R2

R1

A

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

R3's Table
To:	Via:	Cost:	TTL:
A	R2	∞	16

65 of 115

Poison for Fast Route Expiry

Poison lets us detect busted routes faster. Let's watch the demo again.

R3's Table
To:	Via:	Cost:	TTL:
A	R2	∞	16

R3's Table
To:	Via:	Cost:	TTL:
A	R1	2	16

t = 6

R3 was able to accept the new route way earlier!

t=6 with poison, t=16 without poison.

Link goes down!

Sure, I'll accept, that's better than infinity.

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

R3

R2

R1

A

66 of 115

Accepting and Advertising Poison

Where does poison come from?

One of your routes times out.
You notice a local failure, e.g. one of your links goes down.

When one of those occurs:

Poison the entry: Set cost to infinity, reset TTL.
Advertise the poison to your neighbors.

67 of 115

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.

68 of 115

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. (#5)

Advertise to all your neighbors when the table updates, and periodically. (#3)
If a table entry expires, make the entry poison and advertise it. (#4, #5)

69 of 115

Rule 6A:�Split Horizon

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

70 of 115

Split Horizon – The Problem

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:
A	R1	2

R3's Table
To:	Via:	Cost:
A	R2	3

We ran the algorithm for some time, and we converged to this steady-state.

All subsequent advertisements will be rejected.

71 of 115

Split Horizon – The Problem

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:
A	R1	2

R3's Table
To:	Via:	Cost:
A	R2	3

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

Rejected. I have cost 2, and you're offering cost 1+3=4.

72 of 115

Split Horizon – The Problem

R2's Table
To:	Via:	Cost:
A	R1	2

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:
A	R2	3

A link goes down, and R2's entry expires (no more updates from R1).

What happens now?

73 of 115

Split Horizon – The Problem

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:
A	R2	3

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

My table's empty, so that sounds good to me.

R2's Table
To:	Via:	Cost:
A	R3	4

74 of 115

Split Horizon – The Problem

R2's Table
To:	Via:	Cost:
A	R3	4

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R3's Table
To:	Via:	Cost:
A	R2	3

A this way

We made a routing loop!

75 of 115

Split Horizon – The Problem

Problem ("me" = R2):

I gave R3 a path via me, and R3 accepted.
Then, R3 turned around and gave me that same path.
I'm being offered a path that goes through myself!
Normally, I would never accept, because a path with a loop is longer.
But if I lost my earlier route, I might accept and create a loop.

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:
A	R2	3

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

My table's empty, so that sounds good to me.

R2's Table
To:	Via:	Cost:
A	R3	4

76 of 115

Split Horizon – The Problem

The split horizon 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.

Solution: Don't advertise a path back to the person who gave it to you.

A advertises a route to B.
B can advertise that route to everybody except A.
More generally: Don't advertise paths back to the next-hop (the person who gave you the path).

77 of 115

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. (#5)

Advertise to all your neighbors when the table updates, and periodically. (#3)

But don't advertise back to the next-hop. (#6A)

If a table entry expires, make the entry poison and advertise it. (#4, #5)

78 of 115

Rule 6B:�Poison Reverse

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

79 of 115

Poison Reverse

Split horizon: If R1 gives me a route, don't advertise it to R1.

Don't tell R1 anything.

Poison reverse: If R1 gives me a route, advertise poison back to R1.

Explicitly tell R1: "Do not forward packets to me."

Poison reverse is an alternative way to avoid routing loops.

80 of 115

Poison Reverse vs. Split Horizon

R2

I can reach A.

Split Horizon:

I can reach A.

Poison Reverse:

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.

R1

81 of 115

Poison Reverse

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:
A	R1	2

R3's Table
To:	Via:	Cost:
A	R2	3

Let's watch the demo again, but with poison reverse this time.

As before, we first reach steady state.

82 of 115

Poison Reverse

R2's Table
To:	Via:	Cost:
A	R1	2

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:
A	R2	3

A link goes down, and R2's entry expires (no more updates from R1).

What happens now?

83 of 115

Poison Reverse

R2's table now explicitly says: Do not send packets to R3.

Because R3 would just send the packet back to R2.

R1

A

R2

R3

R1's Table
To:	Via:	Cost:
A	Direct	1

R2's Table
To:	Via:	Cost:

R3's Table
To:	Via:	Cost:
A	R2	3

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

My table's empty, so that sounds good to me.

R2's Table
To:	Via:	Cost:
A	R3	∞

84 of 115

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.

85 of 115

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.

86 of 115

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. (#5)

Advertise to all your neighbors when the table updates, and periodically. (#3)

But don't advertise back to the next-hop. (#6A)
...Or, advertise poison back to the next-hop. (#6B)

If a table entry expires, make the entry poison and advertise it. (#4, #5)

87 of 115

Rule 7: Count to Infinity

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

88 of 115

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.

89 of 115

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

90 of 115

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	∞

91 of 115

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	∞

92 of 115

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

93 of 115

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

94 of 115

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

95 of 115

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

96 of 115

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

97 of 115

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

98 of 115

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

99 of 115

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

100 of 115

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

101 of 115

Count to Infinity – The Problem

The problem, restated:

Poison wasn't propagated properly. A router had a busted path.
Busted path is advertised in a loop.

Split horizon won't save us.

We're never advertising a path back to the next-hop.

R1

R2

R3

2

5

8

3

6

9

10

7

4

102 of 115

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.

103 of 115

Count to Infinity – Solution

All numbers ≥ 16 are considered infinity.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	10

R1's Table
To:	Via:	Cost:
A	R3	11

R2's Table
To:	Via:	Cost:
A	R1	9

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

R2's Table
To:	Via:	Cost:
A	R1	12

104 of 115

Count to Infinity – Solution

All numbers ≥ 16 are considered infinity.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	10

R1's Table
To:	Via:	Cost:
A	R3	11

R2's Table
To:	Via:	Cost:
A	R1	12

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

R3's Table
To:	Via:	Cost:
A	R2	13

105 of 115

Count to Infinity – Solution

All numbers ≥ 16 are considered infinity.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	13

R1's Table
To:	Via:	Cost:
A	R3	11

R2's Table
To:	Via:	Cost:
A	R1	12

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

R1's Table
To:	Via:	Cost:
A	R3	14

106 of 115

Count to Infinity – Solution

All numbers ≥ 16 are considered infinity.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	13

R1's Table
To:	Via:	Cost:
A	R3	14

R2's Table
To:	Via:	Cost:
A	R1	12

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

R2's Table
To:	Via:	Cost:
A	R1	15

107 of 115

Count to Infinity – Solution

All numbers ≥ 16 are considered infinity.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	13

R1's Table
To:	Via:	Cost:
A	R3	14

R2's Table
To:	Via:	Cost:
A	R1	15

R3's Table
To:	Via:	Cost:
A	R2	16 ∞

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

108 of 115

Count to Infinity – Solution

All numbers ≥ 16 are considered infinity.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	∞

R1's Table
To:	Via:	Cost:
A	R3	14

R2's Table
To:	Via:	Cost:
A	R1	15

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

R1's Table
To:	Via:	Cost:
A	R3	∞

109 of 115

Count to Infinity – Solution

All numbers ≥ 16 are considered infinity.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	∞

R1's Table
To:	Via:	Cost:
A	R3	∞

R2's Table
To:	Via:	Cost:
A	R1	15

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

R2's Table
To:	Via:	Cost:
A	R1	∞

110 of 115

Count to Infinity – Solution

We've reached steady state!

Future advertisements won't change the tables.
Routes for A will soon expire.

Or, if another route to A appears, it'll replace the infinite-cost entry.

A

R1

R2

R3

R3's Table
To:	Via:	Cost:
A	R2	∞

R1's Table
To:	Via:	Cost:
A	R3	∞

R2's Table
To:	Via:	Cost:
A	R1	∞

111 of 115

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. (#5)

Advertise to all your neighbors when the table updates, and periodically. (#3)

But don't advertise back to the next-hop. (#6A)
...Or, advertise poison back to the next-hop. (#6B)
Any cost ≥ 16 is advertised as ∞. (#7)

If a table entry expires, make the entry poison and advertise it. (#4, #5)

112 of 115

Eventful Updates

Lecture 6, CS 168, Spring 2026

Distance-Vector Correctness

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

Distance-Vector Enhancements

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

113 of 115

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.)
When a table entry expires. (Poison routes and advertise poison.)

Periodically (once every "advertisement interval").

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.

114 of 115

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. (#5)

Advertise to all your neighbors when the table updates, and periodically. (#3)

But don't advertise back to the next-hop. (#6A)
...Or, advertise poison back to the next-hop. (#6B)
Any cost ≥ 16 is advertised as ∞. (#7)

If a table entry expires, make the entry poison and advertise it. (#3, #5)

115 of 115

Summary: Distance-Vector Rules

1. Bellman-Ford Updates: Accept if advertised cost + link cost to neighbor < best-known cost.

2. Updates From Next-Hop: Accept if advertisement is from next hop.

3. Resending: Advertise periodically.

4. Expiring: Expire an entry if TTL runs out.

5. Poison Expired Routes: Send poison if an entry expires.

6A. Split Horizon: Don't advertise path back to the person who gave it to you.

6B. Poison Reverse: Send poison back to the person who gave you the path.

7. Count To Infinity: Any cost ≥ 16 is advertised as ∞.

This is now a pretty good routing protocol!