5.2 Routing algorithms: link state routing

Video presentation: Computer Networks and the Internet.
5.2 Routing algorithms: link state routing. Introduction to routing algorithms. Dijkstra's centralized link state routing algorithm.

Computer networks class.
Jim Kurose
Textbook reading: Section 5.2, Computer Networking: a Top-Down Approach (8th edition), J.F. Kurose, K.W. Ross, Pearson, 2020.

[eminkilicaslan]

This book is brilliant, and these lectures great for quick revise. Thank you Dr Kurose.

[luisdmaco]

you explained it better than my professor at uni, thanks!

[mathieutulpinck]

Slide at 13:43 contains typos. Correct version of update step:
D(w) = min ( D(w), D(y) + c y, w) = [...]
D(z) = min ( D(z), D(y) + c y, z) = [...]

[elcar]

Usually when a Youtube lecture is longer than 10 minutes I expect long tangents. However this was the best lecture I've seen today. Well done.

[ReadingKing]

Best clear lecture i've ever heard

[ianpatricklulu]

thank you so much for this! really helps supplement with my class

[onurcanisler]

Fun thing is that our Computer Networks professor is also teaching Analysis of Algorithms course in our faculty:P

[casperdewith]

~ 8:00 Can you not eliminate lines 4–5 and put them in the loop? It feels like the initialisation phase is already doing half of an iteration of the loop.

[solomontan]

I find it weird at 17:30 that the message complexity is O(n^2). I understand that the message complexity is O(nE) where E = the total number of links. We need to multiply E with n since the link state is sent to all n routers in the network. But E is not O(n). From graph theory, E should grow at a worst case scenario of O(n^2). So O(nE) should really be O(n^3) instead, no?

[BipinJethwani]

You have missed edge (u, w) in the slide