Distance Vector Routing Algorithm with Example | IIT Lecture Series

a horse sends a packet and it reaches the destination how does this magic happen one of the earliest and widely used routing protocol is the RIP protocol this protocol is based on distance vector routing algorithm so that's the focus of this video what comes next you know it routing is a very important functionality at the network layer mainly ins job is to find the least cost path between nodes we have seen that there are many approaches to routing we will focus on dynamic distributed algorithms so distance vector algorithm is one such algorithm we will cover it in detail this algorithm also goes by the name bellman-ford algorithm these two were the inventors of this algorithm this was the algorithm that was originally used in the very first packet switching Network ARPANET later in internet also this algorithm was used but it was used under a standard stands for rip routing information protocol while it was very popular earlier these days it is not used much because of reasons will become apparent soon so this is how the algorithm works to begin with a given node knows the distance or the cost just to its neighbors so that's the state at which each node begins with as the algorithm all trades a node gets to know the distance to all the nodes in the topology not only this it also knows to reach a given destination what is the next hop whenever we want to implement an idea as a protocol we saw earlier that we need to handle this three questions first is what information do you need to exchange this boils down to the message format once in order receives a message what should it do the action portion of it and when should such messages be sent and when you are executing a protocol you also need to maintain state so what is the state that the surrounding algorithm basically the following each nod maintains what is called a routing table this is also called a distance vector so here is the state that just maintains it consists of three components one is the destination another is the estimated cost to the destination I would like to emphasize on estimated because it doesn't really know the exact cost it is making an estimate and as the algorithm proceeds this estimate will converge to the actual cost and to reach the particular destination which hop should it take - as I mentioned this is the initial routing table at B so it has three neighbors a C and E so the initial routing table will correspond to the three neighbors and it is a cost of one three nine since it can directly reach them the next hop also happens to be these nieghbors fences it's a rather boring calculation but still tell me what is the final routing table at B just look at the figure and do the calculations manually so here is the answer this topology was small so he could quickly calculate this final routing table but when the number of nodes are really large you need a very efficient algorithm that does these iterations to get it the final routing tables so that's why we are studying this algorithm this is the state maintained getting back to the protocol what is the actual message content that is exchanged so each node exchange chills with all its snipers let me emphasize that this is just neighbors it is not exchanging with others only the neighbors its routing table information that is the destination and the estimated cost to the destinations well it should be destinations because a node can maintain information about many destinations note that the next hop information is not shared so for example B here exchanges only this information to its neighbors a C and E now once a node receives this message what should it do so this action is based on the bellman-ford equation suppose this term here represents the least-cost path from node X to Y and let me represent by V the set of XS neighbors the least-cost path from X to Y is dictated by this particular equation where the minimum is taken over this entire set of XS nieghbors where you will determine what is the cost of going from X to this neighbor let me call it a what is the cost of this so this is C X a and then what is the cost of reaching this destination Y from a then taking the summation of the cost from X to the ninth and the least cost part from the neighbor to the destination y and taking the minimum over all such possibilities is what is going to eat the least cost path from this node X to the destination y a node really doesn't know the actual least cost path it has an estimate so it starts working on the estimates and as long as you are taking the minimum it converges finally to the least cost path so basically here is what happens so on receiving a message from an i / v this is what a node does it will update its cause based on this particular equation so this neighbor we said that it can reach Y at this particular cost it already has an estimate maybe this estimate was determined based on some other neighbor for its initial state information then what it does is it adds the cost of reaching the neighbor V so that is CX V so this is the total cost of x - y if it were to take the next hop as the neighbor v and this it compares with its current estimate and it will update the current estimate with the minimum of this value so after this step the current estimate will be equal to DX Y and as it keeps hearing from the neighbors this estimates keeps on revising the neighbors themselves are hearing from are the neighbors so it finally through this message exchange it converges so nothing like an example let's see how this works so we are focusing on this node see and this is the initial routing table of C as I mentioned earlier it maintains information only about sit neighbors abd and these are the costs respectively and the next hop since it can directly reach them these next hops also correspond to the destination now suppose C were to receive a message from a and this is nothing but the initial routing table at a so that is what a sent and now C is going to act on that particular information it knows that the cost from itself to a is equal to 5 so what it does is it is going to add this file to all this information and compare it with its current estimates if this information is giving a better cost it is now going to replace the next host via a and change the cost also accordingly so let's see step by step so here it is directly connected to a this is what this is also telling so this information does not change so currently it is directly connected to B and it has a cost of 3 now it can also reach B via a and this is a cost of 5 plus 1 so this is equal to 6 but this number is more than its current estimate so it will retain its current estimate and keep the next hop as before it doesn't act on this because we are focusing on node C itself D it didn't even get any information so it will retain the previous information that it had so after receiving a message from a this is going to be the routing table at C suppose node C were to receive a message from B with its initial table so this again is the initial routing table of B and the cost from C to B is 3 and again you should do the same procedure where you try to determine whether its current estimates are better or whether B can provide better paths do the calculations and what the routing table at C is going to be after the step so let me just do one step let's look at this destination a so node C has a cost of 5 to a according to its current estimate but B is saying I can reach a at a cost of 1 but the C to B there is a cost of 3 so 3 plus 1 is 4 this is better than the previous estimate so it is going to update it with this information where it says I can reach a at a cost of 4 via B so that is how it had updated now it heard new information here which you didn't have this also it has made note of so the same step happens when it receives a message from D you do the same process and you can arrive at this so as messages keep coming at node C it is going to update its cause not just at C this is happening at all the nodes and as new routes are discovered and as the cost matrix change they are going to exchange their new information to the neighbors thereby the neighbors also are going to change their estimates so here are a few points to note if there was no topology change while you are running this algorithm the nodes converged to the final cost in just a few rounds basically what happens is after one message exchanged by the way when I say one message exchange I don't mean that there was one message transferred in the network rather every node has exchanged one message with its neighbors after such an event each node knows about nodes 2 hops away so why like this because from the perspective of this node let me call it a its neighbor has given information about nodes that are one hop away from it thereby a now knows about nodes that are too hot sitting by the same count this sniper let me call it B also got to know about nodes that are 2 hops away from it now when another round passes B is now going to convene Meishan about nodes that are two hops away from it thereby a gets to know information about nodes that are three hops away so this kind of progresses so does the selca rhythm fall under the global knowledge or the local knowledge approach local knowledge approach no node has any idea of the entire network topology that is who are the neighbors of any given node it knows only about its neighbors and through message exchange has determined route to the destinations so this is a fully distributed algorithm yet it maintains correct view going back to the protocol we have seen what messages are exchanged the content of the message next we have seen outers a node act once it receives a message now we will see when does the node send a particular message what do you think when should a note send a routing message to its neighbors naturally whenever the distance vector the routing table changes you need to inform your neighbors of the change in the matrix so this happens whenever a link node fails or the cost increases so these are called triggered updates but often a node also sends periodic updates even when the distance vector does not change why do you think this is needed well for one this informs the neighbors that this specific node is still alive but for this it is not necessary to include the routing information more importantly this is done to ensure others can find an alternate route if some route had become invalid what do I mean by this let me give an example suppose this was the specific network topology where all the link costs are equal to one and this link has failed thereby the cost has become infinity let's now assume that there is some mechanism based on which a will detect that this link has failed so it's distance vector so the cost to see at a is now set equal to infinity now this is going to do a trigger update and based on that it will send triggered update to be now be is going to ignore that particular triggered update because it is anyway has a cost of one to see it is directly connected to see now with be kept quiet how will I ever find an alternate path to see which is this nothing really changed it B so it is not going to generate a triggered update only by a periodic update will a get to know about this alternate path so such periodic updates are sent ranging from a few seconds to few minutes it's a configurable parameter since we are talking about node or link failures how does a given node figure out that something went wrong either this link failed or let's say this node has failed how does it figure B figure this out well since anyway we are sending periodic updates for the more important reason we might as well leverage on this and use these as keepalive messages that is if I don't hear a periodic message from a given I per for some time then I will conclude that either the link or the node itself has failed one could also actively probe an I per by sending probe requests and it is expected this neighbor is going to act this probe request there is more to distance vector however let me stop here so here is a quick summary of what we have seen in this video so we look at a dynamic distributed algorithm called the distance vector that works with local knowledge this algorithm is based on the bellman-ford equation basically each node iteratively through message exchange with its neighbors refines the cost to all the other nodes in the network this algorithm can also handle node and Link failures as we have seen again and again there are always going to be issues with any idea so up the head we will see some problems associated with distance vector as well as some solutions to the problems and the standard that implements the distance vector but it

Channel: CSE Technical Videos

Views: 330,557

Keywords: #DistanceVectorRoutingProtocol, #computernetworks

Id: dmS1t2twFrI

Length: 15min 17sec (917 seconds)

Published: Thu Nov 17 2016