Distance Vector Algorithm (Bellman Ford) - Computerphile

[@BonJoviBeatlesLedZep]

We had a Computer Networks exam involving distance vector algorithms yesterday and NOW this video gets posted. Just my luck.

[@johanhendriks]

don't worry, you'll be on time for the second time you take the test

[@siddharthkapoor1056]

F

[@shlomiunger3518]

Haha me too I just learned about dynamic routing protocols on Jeremy's IT Lab's channel and how RIP and EIGRP use a Distance Vector Algorithm and then I see this. Awesome channel!

[@usafa1987]

Are you in my class?

[@talideon]

I had fun times with this stuff a two decades ago. In my college work placement, I had to get a bunch of MEMS talking to each other in a mostly reliable fashion, which meant figuring out mesh networking and what to do when you have very unreliable routes. That was a harder problem than my mentors (who were electronic engineers, not software engineers) realised... It was certainly a learning experience!

[@richardclegg8027]

Optical MEMs? They're pretty amazing. The first time I heard someone talk about that (late 90s) I honestly thought they were kidding me as it didn't seem possible.

[@davidgillies620]

Bellman-Ford not having been invented by Bellman and Ford is an example of Stigler's Law: no scientific or engineering discovery is named after its originator. Stigler himself credited Robert Merton as the original discoverer of the law in a nice bit of self-reference.

[@matheuscosta5330]

dijkstra

[@davidgillies620]

@@matheuscosta5330 Examples can be found practically without limit.

[@Enigmatt_eu]

University bells ringing 🔔 Thanks for refreshing my knowledge @Computerphile 🙏

[@TechyBen]

Overhead projectors in 1990: Blurred focus on the wall. Overhead projectors in 2020: Blurred low pixel count KZbin.

[@xenobob2773]

30 years of progress!

[@zwz.zdenek]

It's one of those things you need expensive equipment for and so much planning needs to go into making it work that only those at the top do it. A regional network, especially with damage and/or overloaded paths has to be managed by hand.

[@n00dle_king]

3 years on I think I've forgotten the details of every algorithm from my networking class :(

[@vipsylar6370]

You're not alone!

[@sasukesarutobi3862]

Can the algorithm account for directness? It seems from Dr Clegg's explanation that the count-to-infinity problem arises from nodes exchanging second-hand routing information back and forth, so weighting information by originality would help updates propagate quicker. (Unless that's one of the hacks he alludes to.)

[@noamlima9402]

So tyler what about maping glitches to instructions then injecting it on intel management engine ? Maybe we can install android that is kinda great

[@noamlima9402]

So its the ones thats is from that

[@donaldkjenstad1129]

Back in the '70's we were writing algorithms for minimal spanning trees ....

[@wylie500]

Great video. Cleared things up for me, very well explained.

[@joshroberts4076]

This video does a great job of showing a run of the algorithm, but doesn't explain as well the problems it solves

[@MasterHigure]

They refer back to earlier videos on Dijkstra and A*. Presumably they think the problem is explained well enough over there.

[@joshroberts4076]

@@MasterHigure I'm familiar with the video they refer to, but that one I feel too fails to effectively explain why you would use Bellman Ford over Dijkstra

[@MasterHigure]

@@joshroberts4076 That I think they do explain: That no router wants the responsibility of having a full map of the network, or even the full path to any other router. Just "If I want to send to red, the shortest seems to be to send to black and let them deal with it from there". They don't spend minutes exploring this issue, but it is explained at the outset.

[@joshroberts4076]

@@MasterHigure I don't they ever explicitly cover it at all in the video, you've just made a clever inference

[@MasterHigure]

@@joshroberts4076 Yes, they do. Have a look at 1:10.

[@victorcotu]

I'm glad to see that I'm not the only one to have stolen continuous form paper from the lab.

[@s_rox5042]

Please add subtitles. Great content

[@JoshNorris52]

I would give away my car to have an hour in the classroom with this guy

[@felineboy]

Aaaaaand then Black becomes overwhelmed and the whole networks becomes slower, and that reminds me of Braess' paradox.

[@AnaS-lp4mf]

Thank you so much this made sense of everything!

[@LaserFur]

I would think a better way to look at it is to leave the initial blocks and then have sub lists from each router. So it's a one blue followed by one red.

[@JmanNo42]

Immediately i must say fantastic idea of webcam

[@t71024]

My toilet is clogged. I guess I have to call the brown rooter.

[@daddlplays4060]

much more complicated explained that it is, hes a professor so that explains a lot.

[@isyt1]

Great video but one thing I’m not getting - how are the initial route numbers between nodes generated - like in this example, a cost of 1 or 2 or 3 - between nodes? Like when the network is turned on does each node ping everything and base that number on the ping time? And if so, do they routinely recalculate the ping at given intervals?

[@richardclegg8027]

So there's lot of ways you might choose to get those initial costs. You might choose simply to say everything is 1 (that's very common) but that makes a boring example. You might choose to say that a link is more expensive if it is near capacity so getting crowded. You might even say that a link is more expensive if it is literally more expensive (you pay some other company money for traffic on that link). In large scale systems these "link weight" parameters tend to be set by engineers. It's actually pretty complicated I am afraid so we didn't really have time to get into it here. Really that would be a full video on its own.

[@isyt1]

@@richardclegg8027 Great many thanks for that!

[@UpcycleElectronics]

Are the units directly coupled to physical time/distance, or do they include environmental factors and hardware limitations?

[@recklessroges]

They can be coupled to various things, (that you mention and other things such as including upstream costs.)

[@theinnerwaffle5887]

I'd watch a video on the Counter Infinity Problem.

[@arpitpachori3620]

Please make another video on Count to Infinity problem.

[@vinayak186f3]

Just finished watching Dijkstra algo 😀

[@TheRastaDan]

what about one router is manually configured to give wrong information? Be it just for disrupting a network or let traffic go through itself to spy on it? Is there anything in the algorithm to prevent that? And - not sure if it relates here - can you make a video on the 'byzantine general problem'?

[@kevincozens6837]

I like that mug. Where can you buy one of them?

[@richardclegg8027]

Ah... I'm afraid I had it since about 1980 so I doubt it is made any more. :-)

[@Engineer12798]

While this video explains how the algorithm is used to get the length of the shortest routes, it doesn't explain how to use that information to traverse to any particular node.

[@richardclegg8027]

Let us imagine you are router A and you want to get to router B. You receive from each of your neighbours their cost to get to B and you know your cost to get to that neighbour. You pick the smallest of these and send the traffic to that neighbour.

[@jsomhorst]

What I'm missing in this is how does a router on its own define what the cost is to a specific device?

[@richardclegg8027]

I've answered this in a few places in comments here. It's really a complex problem.

[@NilakshMalpotra]

0:52 I can imagine Moss from the IT Crowd saying that :'D

[@kinloo3778]

i thought link state protocol / distance vector protocol, Dijkstra Algorithm / DUAL Algorithm?

[@richardclegg8027]

DUAL is the algorithm used by EIGRP - I mention it just a little.

[@JanBebendorf]

And the funniest thing is that in reality you almost never use this to search for the shortest route but instead artificially increase the cost of routes to choose the financially cheapest route to send your traffic :D

[@richardclegg8027]

Yes. The numbers here are a generic "weight". I did not get into it here but it could be latency or financial cost or something related to bandwidth. At the highest level routing is an economic and political decision as much as an engineering one.

[@vishalcseiitghy]

@@richardclegg8027 Cisco makes routers have the option to choose which algorithm you want your packets to be sent. Either RIP or OSPF or EIGRP one more protocol developed by cisco only.

[@richardclegg8027]

@@vishalcseiitghy yup - I play with them virtually in Packet Tracer software which I teach to my students. :)

[@vishalcseiitghy]

@@richardclegg8027 I would gladly be a part of that. Are you taking students for internship at the moment. I need to do one internship based on the topic of my choice, and Computer networks fascinate me to my core. I am ready for a test for eligibility from your side, if this is what it takes to do that.

[@richardclegg8027]

@@vishalcseiitghy I'm afraid to say I don't have internship places right now but do feel free to drop me an email.

[@graywolf3354]

I have one of those mugs!

[@TheFool88888]

thanks

[@paulogsf76]

Isn't that Floyd-Warshall?

[@richardclegg8027]

Floyd-Warshall finds every shortest path for every pair of nodes assuming a single entity which knows the whole network. F-W is a centralised solution. B-F is a distributed solution. In B-F no router ever knows every link in the network. In F-W one entity knows every link.

[@paulogsf76]

@@richardclegg8027 Ok. This is not so important, it's just that, if I understood it right, the explained algrorithm computes shortest-paths between all pairs of nodes, and it does so by first considering direct paths with no intermediate nodes and then progressively considering intermediate nodes. This is pretty much like FW is usually presented (in algorithms textbooks, or wikipedia, for instance). The BF algorithm, otoh usually refers to a single-source shortest path algorithm (like Dijkstra, but allowing for negative edges) which uses dynamic programming to progressively relax the number of edges. I am not aware of the computer networks-specific literature, but just got a bit concerned that one could get confused when searching for further references on the topic. But anyway, thanks for your time and the nice explanation with the blocks :)

[@richardclegg8027]

@@paulogsf76 the confusion is reasonable. They both try to achieve the same thing in different ways. (Plus I am describing B-F in a short video here. In a lecture series it would get 30 minutes, a full problem definition and worked examples.)

[@alejandrodeharo9509]

ADD SUBTITLES PLEASE

[@kentw.england2305]

Great explain(er)

[@raygreen2134]

Never been so early.

[@pratek3d]

Me too!

[@raygreen2134]

@@pratek3d hello! you interested in computer science?

[@IcyMidnight]

Your sweater stripes keep making me think there's some sort of massive codec error going on 😂

[@richardclegg8027]

Haha... I can't unsee that now. Waistcoat encoding error.

[@ShubhamBhushanCC]

Dynamic Programming is basically just Magic

[@SimGunther]

Feels like magic, but it's just caching (pure) function results based on input parameters and programming for optimal substructures/overlapping subproblems

[@almatnarmatov]

my future self, hope you doing okay

[@sadashivshinde9150]

That mug has seperate fanbase

[@TheDudem122]

farid naisan

[@noamlima9402]

100

[@MikelNaUsaCom]

as a real world example from my experience... imagine of you have a bunch of distribution centers and trucks... now if you are selling alcohol, you want to plan out the best routes to take and distribute alcohol to all the bars in the area... well the ones that are your customers. Wala... a need for this al-gore-rhythm... I don't know if al gore can dance, but yeah... real world.

[@richardclegg8027]

This relates to one of the most famous algorithms in computer science "the travelling salesman problem". It is usually phrased as the cheapest/quickest way one person could visit every one of a set of locations. In your sense, one truck must drive to all of ten bars in some area using the least petrol. (You can make it more complex by adding more trucks or some bars only take some types of beer etc.)

[@BoxEnjoyer]

Rooter

[@iamundergrace]

First

[@photophone5574]

No one cares

[@G.T828]

@@photophone5574 I do as well

[@ShainAndrews]

Nobody cares.

[@theinnerwaffle5887]

@@ShainAndrews How original.

[@NathanTallack]

lol, "rooter". :P

[@diamondsmasher]

These rooters look a lot like my router

[@jackismname]

None of computerphiles videos are truly accessible to the average person who isn’t on a college course, as opposed to brady’s other series like 60 symbols, the periodic table and numberphile. This is the only channel where they will jump right into an algorithm, without any explanation of what RAM or pointers or libraries or stacks are... In short, the jargon used gates the content, and I think its a shame.

[@DigitalMonsters]

You don't need to know any of that stuff to appreciate an algorithm. Algorithms are entirely divorceable from the machine.

[@theinnerwaffle5887]

@@DigitalMonsters fax

[@jackismname]

​@@DigitalMonsters Go to around 7:30 in the video, when he his asked "Is this being used?", and I have no idea what any of the things listed in the next 40 seconds are, and how they themselves are implemented. I didn't know what a router was until I was 18 or so, and I'm more tech savvy than the average person. Simple words like "path", "protocol", "thread", "hash", are thrown up extensively, but not every one knows what they mean in the context of computer science. And the explanations of these on this channel I think are poor, and again feel like revision for someone who already knows the topic. I stand by what I say, there is a big layer of jargon and constructs that isn't broken down in every video, and in this case, I still don't really understand what a Dijkstra algorithm is, what is so special about this particular algorithm, which some one who has tried to implement such a procedure knows intuitively, and probably under estimates how hard it is to grasp for some one who hasn't. Chemists, Physicists and Mathematicians are used to dumbing things down, and for some reason, I find that isn't the case with these computerphile videos.

[@aaronkoch3273]

It's pronounced "ROUT-er," not ROOTer, and it's DIKE-strah, not dickstraw. :|

Hehe, dickstraw

[@pierreabbat6157]

A /ɹutəɹ/ (from "route") is a networking tool. A /ɹautəɹ/ (from "rout") is a woodworking tool. As to Dijkstra, you're close. The diphthong is /æi/, as I've heard Dutch people pronounce it.

[@teslainvestah5003]

@@pierreabbat6157 Well, I've never heard of that woodworking tool. Also, I think it's more important to pronounce root and (networking) route differently, because they're both mathematical terms here, and can actually cause confusion. For the first couple minutes, he could have been talking about a circuit or machine to calculate the root of some number, and it was actually a more reasonable guess than _I'm hearing someone pronounce route as root for the second time in my life (with the first time being 14 years ago in pixar's Cars talking about Route 66)._

[@recklessroges]

"Its Wingardium Leviosa" different accents exist, and unless you are casting a spell, there isn't a "correct" pronunciation, (as long as the audience can understand... which clearly you can.)

[@pierreabbat6157]

@@teslainvestah5003 In that case, "root" is /ɹʊt/. It's not my pronunciation (I say /ɹut/ for both "root" and "route"), but it's a common one, and not used for "route" or "rout".

[@busterdafydd3096]

so poorly explained I think