ฝัง
- เผยแพร่เมื่อ 7 มิ.ย. 2024
- Video presentation: Computer Networks and the Internet.
5.2 Routing algorithms: distance vector routing. Bellman-Ford distance-vector routing algorithm. An elegant, distributed 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.
When I was a wee lil boye back in tallahasee I really just wanted to learn what the internet was like a city boy. Jimbo my man you are making that come true. As my gran pappy used to say, you're one of them people who've went and gotten dem selves a heart the size o' Texas.
This was amazing! I feel like my mind has been expanded.
magnifique!
grats on 11k subs!
Dear professor, shouldn't it be {9, infinity, 2} @10:50, for calculating Db(d)? I am a bit confused by why it's {9, 2, infinity}. Thank you for your time and effort for all of these greate videos!
You are right but it is probably a set so it does not have to be ordered, it is bad for explanation though
yeah, i'm glad I'm not the only one that saw it... it was confusing me. It should really by (9, infinity, 2) like you suggested
I noticed the same thing
Why does z care about path to x via y when x direct is the min.
Dear professor, why are the components in Bellman's formula differently assigned? For example the first element in parentheses -> cost is signed with c and the other cost with D? Thank you
Becasue the cost using "c" is the local value (a variable), and the D is a function, because it is received from another desination, maybe a bit like a recursive call.
9:32 To be in the right order shouldn't Db(d)=min{Cb,a +Da(d), Cb,c + Dc(d), Cb,e + De(d)} = min{9,2,~}=2 ?
~= inf.
OOPS LOOKS LIKE SOMEBODY ALREADY NOTED THIS😮
I think there might be an error at the slide on 17:50; seems like 50 should be 5 and the 60 should be 6 despite being spoken as 60?
The slides also have small errors - bullet point 3 should be y computes new cost to x via "z" (instead of y)
Yeah when did x,z go from 5 to 50. The book I have is the same way.
Also, do packets get sent before and during all the routing cost settlement?
@@goedeck1 we should consider the path from z to y to x which is 1+4. As we not only focus on the direct path.
idk if this is too late, but each node only knows of it's neighbors. It can't see the full graph.
So;
Y has it's direct link to X set to 60. Y sees that and asks its neighbors what their link costs are.
- Neighbor X says its cost is 60
- Neighbor Z says its cost is 5. That 5 comes from the path of (Z->Y->X). Remember, the neighbors don't say what the path is, just that it's cost is lowest. Y doesn't know that itself is in that shortest path from Z.
Y now sees cost of 5 from Z, so it uses that and adds 1 to it for it's own cost. Y->X is now 6 and it alerts its neighbors.
Z receives an alert from Y that is has a new lowest cost. That cost is 6. Z checks its neighbors link costs:
- Neighbor X says its cost is 50.
Z now sees cost of 6 from Y, so it uses that and adds 1 to it for it's own cost. X->Z is now 7 and it alerts its neighbors.
Z then alerts Y and X of its new lowest cost and the cycle repeats.
This process will rebound back and forth with Z and Y alerting each other back to back until the link cost hits 51, where the new path from node Z->X will choose the direct link to X instead of through Y (which is now 51)
@@torvasdh That makes sense. So there's no typos, actually?
0:39 - "Bellman-Ford computes the least cost path as a centralized algorithm..." er, you mean "decentralized".
🧠