Folks,
It came to my attention that the solution to the poisoned-reverse problem is somewhat obscure. So, let me try to clarify it a bit.
The problem shows you a network graph, tells you that a particular link goes down, and asks you to show the route (path) from each router to router A during the first 6 steps of the Bellman-Ford algorithm. The answer is shown in Figure 4.
Figure 5 is an auxiliary table that is supposed to help understand what's going on, but it's hard to read. Let's look at it step by step:
In general, X-> Y indicates an announcement sent from router X to its neighbor Y.
Step 0: It shows the route from each router to router A before the link went down:
- Router B goes to A through their direct link, which has cost 1.
- Router C goes to A through B, with cost 1 (from C to B) + 1 (from B to A) = 2.
- Etc.
Step 1: It shows the last set of announcements that each router receives from every one of its neighbors before the link went down:
- Router B receives two announcements, from C (indicated as C->B) and from E (indicated as E->B). C tells B that its best route to A has cost infinity (this is indicated as C->B : infinity). That's because C routes to A through B. Similarly, E tells B that its best route to A has cost infinity (this is indicated as E->B : infinity). That's because E also routes to A through B.
- Router C receives two announcements, from B (indicated as B->C) and from D (indicated as D->C). B tells C that its best route to A has cost 1 (this is indicated as B->C :1). D tells C that its best route to A has cost infinity (indicated as D->C : infinity). This is because D routes to A through C.
- Etc.
Step 2: It shows the first set of announcements that each router receives from its neighbors after the link went down:
- Router B receives two announcements, from C and E, which are the same as the ones it receives before. That's because C and E do not have any new information to share.
- Router C receives two announcements, from B and D. B tells C that its best route to A has cost infinity (indicated as B->C : infinity). That's because the link from B to A went down. D tells C that its best route to A has cost infinity (indicated as D->C : infinity). That's because D routes to A through C.
- Etc.
Step 3: It shows the next set of announcements.
- Router B receives 2 announcements. from C and E. C tells B that its best route to A has cost infinity. That's because C used to route to A through B and, in step 2, it learned that B's cost to A is now infinity. E tells B that its best route to A has cost 4. That's because, in step 2, E learned that B's cost to A is now infinity, so it switched to routing to A through D (without knowing yet that that route also goes through B).
- Etc.
I hope the solution makes a bit more sense now. Please don't hesitate to ask at the Q&A Moodle forum on Discord if it's still confusing.
