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.
See gaia.cs.umass.edu/kurose_ross for more open student resources.

[@elcar5468]

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

[@mathieutulpinck3845]

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) = [...]

[@ReadingKing1]

Best clear lecture i've ever heard

[@ianpatricklulu6179]

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

[@marie_12]

thank you !!!

[@usmanalibokhari]

GOAT

[@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.

[@varshashiremath1431]

Thank u so much sir

[@solomontan1524]

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?

[@assemblywizard8]

Broadcast allows to send one router link state to ALL nodes in O(N). You need to repeat this N times so each router can let any other router their link state. So if you are more or less synchronised you can do in O(N^2).

[@BipinJethwani]

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

[@kylemeade7349]

Why was v updated in step 2?

[@ezaldeen11]

May I have the PPT files please?

[@findmeifucan2719]

Yes ,you can have

[@devmahad]

done

[@vohu7640]

7:09

[@calvinsaxon5822]

b is never defined

[@Mimonsi]

b is defined as all nodes adjacent to a, the definitions is right behind the first use.