Distance Vector Algorithm (Bellman Ford) - Computerphile

Key Takeaways

we had a brief discussion about um it's pathfinding and networks right yeah it's it's about about finding groups through networks in your previous video mike pound talked about the dykstra algorithm and that's one way of finding your route through the network it's what we call a link state algorithm so today i'd like to talk about a different way of doing that the bowman ford a distance vector algorithm and it's just a different way of achieving the same thing we're trying to find our way through a network it's i guess a gossipy algorithm so let's imagine all of our routers are named after colours and what they want to do they want to inform the other routers of their their distance that they have to travel to get to the routers so let's imagine i'm the black router i'm going to give my routing table to all my neighbors so let's imagine i'm going to shout out some of my routes to my neighbours so i go hey green router i can get to the blue router in one hey blue router i can get to the green router in one dixtra imagine it like this the routers are trying to build up a picture in their head each router is trying to build up a complete map of the network so the routers are sending each other it's a link state algorithm they send each other oh i've got a link from the black router to the red router it costs three add that to your map the bellman ford album works differently it's it's a distant feature algorithm so each router is telling the other routers i can get to black in a cost of one the green router will receive that information and go oh thank you blue router so it's passing around what we call this routing table the distance it takes to get to all the other routers so let's turn to the old school uh overhead projector here if you like let me get this lined up we've got our lovely line printer paper here let's have some rooters so let's have a black green blue and our red router and let's assume there's a certain cost of travel for each of these paths red links to black got a cost of one red links to blue got a cost of three black links to green cost one black links to blue got a cost of three blue links to black we've got across one there's our routing network that we're going to work with pretty simple but the routers need to find their way through it let's imagine we switch on red and blue first so we've just switched on the red router we've just switched on the blue router and they can see each other and they know that the cost between them is three so these blocks represent the distance if you like it's going to take that router to get to velvet so red can see blue in a cost of three blue can see red in a cost of three so these blocks the routing table now let's imagine we're going to switch on black for the first time so black when we switch it on we can see red cost of one blue cost of one and nothing else because we haven't yet switched on green so now with black is switched on blue can see black red can see black so they've been added in to the rooted tables now we're going to switch on green so if we switch on green green can see its neighbors so green you can see blue in a cost of three green can see black in a cost of one but also blue you can see green at a cost of three can see green in a cost of one let me check i've got this right but if we've got this all right then green can see its two neighbors red you can see it's two neighbors can see it's three neighbors black consists three neighbors now the routers are going to exchange their routing tables so let's take the black router and imagine it's going to send out its routing tables to its neighbors so it's going to show and it's going to say hey red i can get to red in one blue in one green in one what are you going to make of that so when red sees that red hears for the first time about green red didn't previously know about green so red can now go i can get to green in the one cost you told me plus the one cost that takes me to get to you so i've got a new route to green red can also say oh you can get to blue in just one brilliant because if i add on the one it takes me to get to you now i've got a route to blue and two that routine table is going to arrive with green green's going to say oh you can get to blue in one brilliant i've got a cheaper cost to blue he's going to hear for the first time about red i can get to red now in a cost of two that's brilliant okay and then when blue here's about the same routine table blue has also got cheaper paths now i think you or i can see looking at that but we've now got the cheapest cost path for everything the routers aren't so clever so what they need to well they haven't got the global view of the network so what they need to do again so let's imagine now we're ready we've received that and we've updated our routing table we've made changes whenever we make changes we send on our routing table so now red is going to send its rooting table on to blue red sends that table to blue and blue learns that red has a cost of black and white that's not used to it it's already got a one cost path got a cost path to green and two that's not used to it it would add on this three so blue is not going to update its reason table as a result if blue doesn't update it through the table it's not going to send anything on and that's the essence really of the bellman ford distance vector algorithm my guess here is the trick's going to be in configuring this right in setting those numbers yeah yeah actually well there are issues with this yeah there are tricks and little hacks you have to make what there's some things we haven't talked about so how often does it send those what happens when things go wrong um so for example one of the great things about bowman ford is if there's good news if a uh a new computer comes on that spreads through the network pretty quickly if a new route came when we saw that news spreads quickly there's an issue which i don't i don't think we can quite cover in this video where if a link dies bad news spreads very slowly because a red router might think it's still got a route to black the black router might still think it's got a route to red and they're exchanging with each other that they've still got that route even once that route has disappeared now it's called the count to infinity problem there's various hacks to get around that but with a distance vector algorithms no no real satisfactory solution is this something that's used on um is this i love your mug by the way show us your mug there we go look uh the themed mug it's always computer file we'll have to get some of those made is this used then is this used extensively now absolutely yes this is this is used very extensively so the uh this is used in rip rooting information process but the daddy of them all are one of the oldest routine protocols we have um igrp interior gateway routing protocol uh used this and then when that became enhanced interior gateway region protocol they they hacked it a little bit and they added in a little bit of link stay but the way the way it's really used and perhaps we don't have time to get into this you've got an excellent video about tim griffin border gateway protocol uses an extension of distance vector it uses what we call path vector where instead of just sending i am the black router here's my router table and you've got costs of this it sends the entire path and that gets around this whole um problem with bad news very slowly and that that that variant on distance retrograde in that variant of bellman ford that's how the big scale routing of the internet works today where did bellman ford come from is it is it a recent thing no no no this this algorithm dates way back to the 50s and actually it wasn't even bellman and ford who discovered it i can't remember the names of the original discoveries but uh belgium and ford weren't the uh original originators of this algorithm they just uh popularized it with them exactly exactly lucky to get the credit well ford did a lot of the old algorithms for networks so there's a lot of algorithms known for right so we're here we can't go to s we can only go to l that's a nice easy one so i need to find l so l goes to c and it's three plus two is five so l comes in one column to start with and each of these nodes within the network has connections to other nodes this is how you initialize network