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.

КОМЕНТАРІ: 19

@mathieutulpinck3845 3 роки тому

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

@elcar5468 6 місяців тому

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

@ReadingKing1 Рік тому

Best clear lecture i've ever heard

@ianpatricklulu6179 2 роки тому

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 2 роки тому

thank you !!!

@varshashiremath1431 9 місяців тому

Thank u so much sir

@casperdewith 11 місяців тому

~ 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.

@usmanalibokhari Рік тому

GOAT

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