Hello,

I’ve been stuck on the question on poisoned reverse in homework 6. I have gone over the correction and made sure I understood the worked example from the course but I still don’t understand what is happening in figure 5 in the correction.

Could you please maybe just explain the first few steps?

Thank you,

Luka

Hi, we'll try to first make sure we understand the use of every element in this figure.

- Recall first the initial situation: we have an algorithm of least cost path routing that converged and every router knows where to go to reach A as fast as possible. This is the initial step, everyone is happy and every router knows which their neighbours to go to reach A as fast/least costly as possible (to retrieve it you can run the algorithm in your head to find the least cost paths to A, this is a very small graph) -> that what's written in line 0.
- Then, we learn that link A-B breaks, that's when troubles start, the algorithm will start being updated (you can imagine a packet tried to reack A after link breaks but never reached it, then the network decided to start rerunning a routing algorithm)
- In step 1, there are the announcements first: what messages are sent on the network. In first column, we see that C tells B "hey, if you wanna reach A through me, it'll cost you ∞". Why is that ? This is the essence of poisoned reverse: has C knows it decided to go to A by B, it tells B not to send packet with destination A to C. As you reviewed the slides of the course, I think you understood that but let me know if you want clarifications on that. This announcement is then labeled (pr) on the correction because it is part of the poisoned reverse protocol.
- After that, the table is updated for each router following "do I have a neighbour that will help me to reach A faster than through the neighbour I'm currently using?"
- And so on, every router receives updated costs from their neighbours

Don't forget the note above fig.4: in this kind of graph, poisoned reverse does not help the algorithm to converge (it's a special case).

Are there still things in this table that you do not understand? If no, are there still things you do not understand in the correction?

Great! thank you very much. I went through every step again using this and understand it now.