Understanding Distributed Bellman-Ford Algorithm

Having now covered Dijkstra's link state routing algorithm, we're ready to dive down to the second broad class of routing algorithms. Take a look at the distributed Bellman-Ford algorithm. And this is really just, it's a beautiful algorithm. It's the best example I know of how simple, local, intuitive, distributed calculations can be used to compute the same result. In this case, least-cost PES as a centralized algorithm. I think you're really going to like this. The distance vector algorithm for computing least cost paths is based on what's known as the Bellman-Ford equation shown here. And while the equation itself might look a little bit daunting, it's really pretty intuitive. The Bellman-Ford equation expresses the notion that if I want a minimum cost from source x to destination y, then that path must have one of x's neighbors, say v, as a first hop. So I'll sum the cost of getting from source x to neighbor v. plus the cost of then getting from neighbor V to destination Y. This is X's cost of getting to destination Y through neighbor V. And then I'll take the minimum cost path over all neighbors V, since X's minimum cost path must pass through one of its neighbors, V. That's it. That's the Bellman-Ford equation. Well, probably the best way to understand Bellman-Ford is to take a look at an example. So let's do that in the context of the network, which you'll recognize. We're going to look at a source node U and a destination node Z. And notice that U has three neighbors. V, X, and W. And here's what the neighbors know. Neighbor V knows that it can reach destination Z with a cost of five. Neighbor X knows that it can reach destination Z with a cost of three. And neighbor neighbor W knows that it can reach destination Z with a cost of 3. So that's what the neighbors know. The neighbors are going to communicate this information back to you. What is this going to mean for you? For this example, the Bellman-Ford equation says that the minimum cost path from U to Z is going to be the minimum of three quantities. The cost of getting from source U to neighbor V plus the cost of getting from neighbor V to destination Z. The cost of getting from U to neighbor X plus the cost of getting from U to destination Z. the cost of getting from x to z, and the cost of getting from u to w plus the cost of getting from w to z. If you plug in the numbers here, you'll find that the minimum cost to get from u to z is v and neighbor x and at a cost of 4. Well, the Bellman-Ford equation expresses a relationship among the distance vectors in neighboring nodes. But of course, we still need to compute these distance vectors. But the way to do that is naturally expressed by the form, the relationship between distance vectors and the distance vectors. distance vectors in neighboring nodes. Function, how we compute these distance vectors, is going to follow form. And here are the key ideas behind the distance vector algorithm. From time to time, each node is going to send its own distance vector estimate to its neighbors. And when a node x receives a new distance vector estimate from one of its neighbors, it's going to send its own to update its own distance vector using the Bellman-Ford equation. That is, node x is going to say, well, for each node y in the network, I'm going to compute my distance x to y to be the minimum across all of my neighbors v, the cost of getting from me to v, and then v's cost of getting from itself to y. The distributed Bellman-Ford algorithm has three steps and all nodes of the network are going to perform the same three steps. So if I'm a node, the first step is I'm going to wait. I'm going to wait till either I receive a distance vector from one of my directly attached neighbors or I'm going to wait for a local link cost change. Two, after I receive one of these events, I'm going to run the Bellman-Ford calculation for all destinations in the network using the most recently received distance vectors from my neighbors. Three, if my own distance vector changes as a result of the Bellman-Ford calculations, I'm going to send my new distance vector to each of my neighbors. And that's it. Then I'm going to iterate again. Well, this algorithm could hardly be simpler. And believe it or not, and hopefully you'll believe it when we're done, this distributed algorithm will result in all nodes having iteratively computed a distance vector that will tell them the least cost path to... every other node in the network and the neighbor to route to to start a packet along that minimum cost path to a given destination. And note that unlike the link state algorithm, a node doesn't know the entire path from source to destination. But in the end, it doesn't really need to, does it? It just needs to know which neighbor to forward a packet to in order to reach a given destination along the minimum cost path. Well, the distance vector algorithm has some amazing properties. It's iterative and asynchronous. Each iteration is caused by either a local link cost change or the receipt of a distance vector update message from a neighbor. And we've talked about this as if it's synchronous, that all nodes are exchanging distance vector in lockstep. But in fact, nodes can iterate asynchronously from each other and with very different iteration speeds will still converge. The algorithm is also distributed and it's self-stopping. Each node node notifies its neighbor only when its distance vector changes. Neighbors then notify their neighbors only if necessary. And if no change is sent or no notification is received, then no actions need to be taken. Well that's it for describing the distance vector algorithm. It's a pretty simple algorithm, isn't it? Just three steps. Waiting to receive the distance vector from a neighbor, performing a distance vector calculation, and then if my own distance, my local distance vector, has changed, I'm going to send my local distance vector to all of my immediately attached neighbors. That's it. Let's now take a look at Bellman-Ford in action, and let's start with a high-level view of the overall structure of a computation. Here's a simple nine-node grid network that we use as our example. It's pretty symmetric, except there's a missing link between C and F, and this link here from A to B has a cost of 8, while all other links have a cost of 1. At t equals 0, all nodes have their distance vector estimates to their directly connected neighbors only. Here you can see the distance vector. node A. Its DV entry for destination B has a cost of 8, and its DV entry for destination D has a cost of 1. Note that these are just estimates of the least cost paths even to direct neighbors, since as we can see here, there's a three-hop path of cost 3 to get from A to B, which we'll found to be cheaper than this initial cost of 8 via the direct link between A and B. So at t equals zero, let's assume that all nodes have initialized their distance vectors. and after doing so, send their distance vectors to their immediate neighbors. At t equals 1, all nodes receive distance vectors from their neighbors, compute their local distance vector, and if any component of their distance vectors changed, they'll send their new local distance vector to their neighbors. At t equals 2, nodes receive distance vectors from their neighbors, compute their local distance vector, and if any component of their distance vectors changed, again, they'll send their new local distance vector to their neighbors. vector to their neighbors and so on. And let me stress here that we've described the iterative process here as if all nodes are operating in link step. It's easier to understand it that way, but in fact nodes can iterate at different speeds and this will still work. Well, the short animation here has shown you a little bit about the overall structure of the distributed Bellman-Ford calculations, but we still need to look at the local computation that's at the heart of the algorithm when we take the individual distance vectors. from our neighbors, we run the Bellman-Ford equation over and compute our new local distributed distance vector. Let's take a look at this local computation. Let's recall that at t equals zero, all nodes have computed their local distance. vectors, which you can see here. Let's take a look at B's distance vector. B knows that it can get to A directly with a cost of 8, to C directly with a cost of 1, and to E directly with a cost of 1. This is B's initial distance vector. The distance vectors of A, C, and E are also shown here. After computing the initial distance vectors, all nodes send their initial distance vectors to their directly attached neighbors only. And let's suppose that at t equals 1, 1, B now receives these distance vectors from its neighbors. And here are the Bellman-Ford calculations carried out by B at t equals 1, following B's receipt of the initial distance vectors from its neighbors a, e, and c. Remember that at each step when a new distance vector is received, a node will recalculate its own local distance vector using this newly received information. Let's take a look at a couple of B's calculations. Let's first look at how how B calculates its distance to A. B says, well, my distance to A is the minimum of three things. My direct cost to A plus A's distance to itself, which is zero. My direct cost to C plus C's cost to A or my direct cost to E and E's cost to A. That's the minimum of 8, infinity, infinity, which is 8. So there's no change here in B's distance vector with respect to A. But now let's take a look at B's new distance table. for D. Recall that at T equals zero, B had an infinite cost to get to D. Now it recomputes that cost as follows. B says, well, my cost to get to D is going to be the minimum of three things. My cost to get from myself, B, to A, plus A's cost to get to D. My cost to get from B to C, and C's cost to D. My cost to get to E, plus E's cost to D. If you plug in the values, that becomes the minimum of... 9, 2, and infinity, which is 2. And you can see that B similarly recomputes new DV entries for destinations F and H as well. And so here's the new overall distance vector computed by B. Note that compared with B's previous distance vector, there are three new lower-cost entries for destinations D, F, and H. This new distance vector then becomes B's current distance vector. Now let's take a look at node C, again at time t equals 1, and after C has received B's initial distance vector. Let's see how C recomputes its own distance vector, but before doing so, let's step back and take a look at the picture. here and think intuitively about what B is telling C by B sending its initial distance vector. Well, B is saying, hey, look, I can reach A at a cost of 8 and I can reach E at a cost of 1. Well, B is C's neighbor, and C knows if that B can reach E with a cost of 1, and C knows that it can reach B with a cost of 1, then C knows that it can reach E with a cost of 2 via B. And this is precisely the Bellman-Ford equation. That's the intuition behind Bellman-Ford. It's not clear? Well, hit the rewind button and listen to that explanation again. And so here are C's calculations of its new decision. distance vector. Let's focus on C's DV entry to destination E here. C's calculation is simple since it's only got one neighbor. C says for me to get to E, I can get to B with a cost of one, and B tells me that if B can get to E with a cost of one, so my cost, C's cost to get to E via B is one plus one equals two. Well, you're probably thinking it's getting a little tedious to go through one example after another, but you might. You might want to do a few calculations for yourself, just to test your understanding. For example, consider the scenario here where node E is receiving distance vector tables from its neighbors B, D, H, and F. What's the new distance vector computed by node E? Which entries have changed? The Bellman-Ford algorithm can be thought of as diffusing information throughout the network. To appreciate this notion of diffusion, let's take a look at node C and ask ourselves the question, what do other nodes in the network know about the state of the network? of node C, say at T equals 0, and when do they learn this information? At T equals 0, C hasn't communicated with anybody, so no other nodes have information about node C. At T equals 1, C's state at t equals 0 has propagated over to b by the exchange of distance vectors. So at t equals 1, c's state at t equals 0 can influence the calculations at b at t equals 1. At t equals 2, information from node c at t equals 0 has propagated further to nodes e and to nodes a. And imagine your node e. At t equals 2, you're seeing the first influence of the state of node c at t equals zero, now at t equals two, two time units later. This notion of information propagation speed, it's almost like looking at a star at night. The light you're seeing now was emitted by that star many light years ago, and so it is with information propagation in a network. The cost that e is seeing at t equals two regarding c reflects c state at t equals zero, even though e is receiving this information at t equals two. Well, continuing on... At t equals 3, C's state at t equals 0 can influence distance vector computations up to 3 hops away. That's at nodes D, F, and H. And finally, at t equals 4, C's state at t equals 0 can influence distance vector computations up to 4 hops away. In this case, at nodes G and I as well. And note that it's taken 4 time steps, the diameter of the network, for information to propagate from one edge of the network to the other. So far, we've only looked at the initial distance vector calculation. After some number of iterations, the computational process will have quiesced. Remember, if there are no changes in a local distance vector, I'm not going to send out distance vector updates to the computer. to my neighbors. So eventually, when there are no local changes computed anymore, the algorithm will have converged. There'll be no more distance vectors being exchanged. Now, let's take a look at what happens if there are link cost changes. Because our distance vector algorithm can already accommodate that. And the steps are the same. A link cost change is noted. I'm a local node. I note that local change. I recompute my local distance vector using the new local link costs as well as the old distance vectors that I have for my neighbors. And if my local distance vector is changed once again, I just send it out to my local neighbors. So the algorithm is pretty much unchanged. So let's now take a look at an example of how link cost changes propagate. You using the network shown up here on the right. And let's take the point of view of node Y, who sees the XY link cost change from 4 to 1. It goes down. So at t equals 0, let's say Y detects this link cost change, updates its distance vector to note that now it's got a new cost to X of 1, and sends its new distance vector to its neighbors. At t1, Z receives this updated distance vector from Y, updates its own distance vector, computing its new... least cost path to x as 2. And now since z's distance vector has changed, z sends its distance vector to its neighbors x and y. At t2, y receives z's updated distance vector, recalculates its own distance vector, and in this case y's least costs in its distance vector don't change. And so y doesn't send anything back out to z or x. The algorithm quiesces and is done. So just after two iterations, the recomputation... of the distance vector here concludes. And we'll note that the network-wide recomputation of the distance vectors happened pretty quickly for this link cost change example. The exact amount of time needed was related to the diameter of the network, as you might imagine. And that's as fast as it could happen, given our earlier starlight analogy. And there's a saying in networking that good news travels fast. When a link weight goes down in Bellman-Ford, all nodes recompute their final distance vectors relatively quickly. But we'll get to that in a minute. But what happens if link costs go up? In this example here, the cost of the link from X to Y now goes to 60. And you'll want to think about what happens in this example, but basically, this is what happens. When the link cost goes to 60, Y says, uh-oh, I better start routing through Z since Z has advertised the path to me with a cost of 5 to X, giving me an overall cost of 6. Y informs Z of its Y's new cost to X via a distance vector update. Will Z then says this update and says, golly, if y's cost to x is 6, then my cost to x is now 7 through y, and informs y. y says, uh-oh, if z's cost is 7 to get to x, then my cost is going to be 8. z then says, well, if y's cost to get to x is 8, then mine is 9, and so on. This is what's known as the count to infinity problem. And think about what would have happened if the link cost had changed to 6 million instead of just 60. Well, Well, it'd be a lot of iterations. Of course, there are workarounds to the count to infinity problem, but I think the larger lesson here is that as beautiful and elegant as distributed algorithms are, their operations and their pathologies can often be sunk. Well, let's wrap up our discussion of routing algorithms with a comparison of link state and distance vector algorithms. And let's start off with message complexity. We saw earlier that the message complexity to do link state dissemination is order n squared for the link state algorithm. For distance vector, we learned that it takes the order of the diameter of the network, potentially order n for information to propagate from one end of the network to the other. And we saw that at each step, a node may potentially need to communicate with each of its neighbors. In terms of speed of conversion, We saw that link state is order n squared computational algorithm, order n squared communication algorithm. And we saw that there can be oscillations. In the case of distance vector, we saw that convergence times, again, can vary. And there can actually be routing loops while the algorithms converge. And lastly, let's think about what can happen in a link state or a distance vector algorithm if a router malfunctions or is compromised. Well, under link state, a router can advertise. incorrect link costs, but each router computes its own routing and forwarding tables. So failure is rather localized under link state. Under distance vector, a router can advertise an incorrect path cost. For example, a router could say, hey, I've got a really low path cost to everywhere in the internet. This is known as black holing. Since each router's distance vector is used by others, errors can then propagate through the network as additional routers advertise their new distance vector. vector. And this type of black hole routing failures actually occurred in the internet when a small ISP advertised, hey, I've got a zero cost pass to a major ISP. I think that ISP was AT&T when this ISP wasn't really connected to that major ISP. And hey, what network can pass up a zero path cost to a major destination network? And so many other networks in the internet who wanted to route traffic to AT&T sent their traffic to this small ISP where it was was black-holed. Now imagine you're AT&T and you're saying, hey, why am I no longer receiving traffic from a good portion of the internet anymore? Well, the answer was that traffic's been black-holed in a small ISP instead due to a misconfigured router in that ISP. Well, that wraps up our discussion of routing algorithms, Dijkstra's centralized link state algorithm, the distributed Bellman-Ford algorithm. In the next two sections, we're going to cover the embodiment of these routing algorithms. algorithms and internet routing protocols, the Open Shortest Path First OSPF routing protocol, and the BGP, Border Gateway Protocol. I think you'll enjoy them.

It's the best example I know of how simple, local, intuitive, distributed calculations can be used to compute the same result. In this case, least-cost PES as a centralized algorithm. I think you're really going to like this.

The distance vector algorithm for computing least cost paths is based on what's known as the Bellman-Ford equation shown here. And while the equation itself might look a little bit daunting, it's really pretty intuitive. The Bellman-Ford equation expresses the notion that if I want a minimum cost from source x to destination y, then that path must have one of x's neighbors, say v, as a first hop.

So I'll sum the cost of getting from source x to neighbor v. plus the cost of then getting from neighbor V to destination Y. This is X's cost of getting to destination Y through neighbor V. And then I'll take the minimum cost path over all neighbors V, since X's minimum cost path must pass through one of its neighbors, V. That's it. That's the Bellman-Ford equation. Well, probably the best way to understand Bellman-Ford is to take a look at an example. So let's do that in the context of the network, which you'll recognize.

We're going to look at a source node U and a destination node Z. And notice that U has three neighbors. V, X, and W. And here's what the neighbors know. Neighbor V knows that it can reach destination Z with a cost of five.

Neighbor X knows that it can reach destination Z with a cost of three. And neighbor neighbor W knows that it can reach destination Z with a cost of 3. So that's what the neighbors know. The neighbors are going to communicate this information back to you. What is this going to mean for you? For this example, the Bellman-Ford equation says that the minimum cost path from U to Z is going to be the minimum of three quantities.

The cost of getting from source U to neighbor V plus the cost of getting from neighbor V to destination Z. The cost of getting from U to neighbor X plus the cost of getting from U to destination Z. the cost of getting from x to z, and the cost of getting from u to w plus the cost of getting from w to z. If you plug in the numbers here, you'll find that the minimum cost to get from u to z is v and neighbor x and at a cost of 4. Well, the Bellman-Ford equation expresses a relationship among the distance vectors in neighboring nodes. But of course, we still need to compute these distance vectors.

But the way to do that is naturally expressed by the form, the relationship between distance vectors and the distance vectors. distance vectors in neighboring nodes. Function, how we compute these distance vectors, is going to follow form.

And here are the key ideas behind the distance vector algorithm. From time to time, each node is going to send its own distance vector estimate to its neighbors. And when a node x receives a new distance vector estimate from one of its neighbors, it's going to send its own to update its own distance vector using the Bellman-Ford equation. That is, node x is going to say, well, for each node y in the network, I'm going to compute my distance x to y to be the minimum across all of my neighbors v, the cost of getting from me to v, and then v's cost of getting from itself to y. The distributed Bellman-Ford algorithm has three steps and all nodes of the network are going to perform the same three steps.

So if I'm a node, the first step is I'm going to wait. I'm going to wait till either I receive a distance vector from one of my directly attached neighbors or I'm going to wait for a local link cost change. Two, after I receive one of these events, I'm going to run the Bellman-Ford calculation for all destinations in the network using the most recently received distance vectors from my neighbors.

Three, if my own distance vector changes as a result of the Bellman-Ford calculations, I'm going to send my new distance vector to each of my neighbors. And that's it. Then I'm going to iterate again. Well, this algorithm could hardly be simpler.

And believe it or not, and hopefully you'll believe it when we're done, this distributed algorithm will result in all nodes having iteratively computed a distance vector that will tell them the least cost path to... every other node in the network and the neighbor to route to to start a packet along that minimum cost path to a given destination. And note that unlike the link state algorithm, a node doesn't know the entire path from source to destination. But in the end, it doesn't really need to, does it?

It just needs to know which neighbor to forward a packet to in order to reach a given destination along the minimum cost path. Well, the distance vector algorithm has some amazing properties. It's iterative and asynchronous.

Each iteration is caused by either a local link cost change or the receipt of a distance vector update message from a neighbor. And we've talked about this as if it's synchronous, that all nodes are exchanging distance vector in lockstep. But in fact, nodes can iterate asynchronously from each other and with very different iteration speeds will still converge. The algorithm is also distributed and it's self-stopping.

Each node node notifies its neighbor only when its distance vector changes. Neighbors then notify their neighbors only if necessary. And if no change is sent or no notification is received, then no actions need to be taken. Well that's it for describing the distance vector algorithm. It's a pretty simple algorithm, isn't it?

Just three steps. Waiting to receive the distance vector from a neighbor, performing a distance vector calculation, and then if my own distance, my local distance vector, has changed, I'm going to send my local distance vector to all of my immediately attached neighbors. That's it. Let's now take a look at Bellman-Ford in action, and let's start with a high-level view of the overall structure of a computation. Here's a simple nine-node grid network that we use as our example.

It's pretty symmetric, except there's a missing link between C and F, and this link here from A to B has a cost of 8, while all other links have a cost of 1. At t equals 0, all nodes have their distance vector estimates to their directly connected neighbors only. Here you can see the distance vector. node A.

Its DV entry for destination B has a cost of 8, and its DV entry for destination D has a cost of 1. Note that these are just estimates of the least cost paths even to direct neighbors, since as we can see here, there's a three-hop path of cost 3 to get from A to B, which we'll found to be cheaper than this initial cost of 8 via the direct link between A and B. So at t equals zero, let's assume that all nodes have initialized their distance vectors. and after doing so, send their distance vectors to their immediate neighbors.

At t equals 1, all nodes receive distance vectors from their neighbors, compute their local distance vector, and if any component of their distance vectors changed, they'll send their new local distance vector to their neighbors. At t equals 2, nodes receive distance vectors from their neighbors, compute their local distance vector, and if any component of their distance vectors changed, again, they'll send their new local distance vector to their neighbors. vector to their neighbors and so on. And let me stress here that we've described the iterative process here as if all nodes are operating in link step. It's easier to understand it that way, but in fact nodes can iterate at different speeds and this will still work.

Well, the short animation here has shown you a little bit about the overall structure of the distributed Bellman-Ford calculations, but we still need to look at the local computation that's at the heart of the algorithm when we take the individual distance vectors. from our neighbors, we run the Bellman-Ford equation over and compute our new local distributed distance vector. Let's take a look at this local computation.

Let's recall that at t equals zero, all nodes have computed their local distance. vectors, which you can see here. Let's take a look at B's distance vector. B knows that it can get to A directly with a cost of 8, to C directly with a cost of 1, and to E directly with a cost of 1. This is B's initial distance vector.

The distance vectors of A, C, and E are also shown here. After computing the initial distance vectors, all nodes send their initial distance vectors to their directly attached neighbors only. And let's suppose that at t equals 1, 1, B now receives these distance vectors from its neighbors. And here are the Bellman-Ford calculations carried out by B at t equals 1, following B's receipt of the initial distance vectors from its neighbors a, e, and c. Remember that at each step when a new distance vector is received, a node will recalculate its own local distance vector using this newly received information.

Let's take a look at a couple of B's calculations. Let's first look at how how B calculates its distance to A. B says, well, my distance to A is the minimum of three things.

My direct cost to A plus A's distance to itself, which is zero. My direct cost to C plus C's cost to A or my direct cost to E and E's cost to A. That's the minimum of 8, infinity, infinity, which is 8. So there's no change here in B's distance vector with respect to A.

But now let's take a look at B's new distance table. for D. Recall that at T equals zero, B had an infinite cost to get to D. Now it recomputes that cost as follows.

B says, well, my cost to get to D is going to be the minimum of three things. My cost to get from myself, B, to A, plus A's cost to get to D. My cost to get from B to C, and C's cost to D. My cost to get to E, plus E's cost to D.

If you plug in the values, that becomes the minimum of... 9, 2, and infinity, which is 2. And you can see that B similarly recomputes new DV entries for destinations F and H as well. And so here's the new overall distance vector computed by B.

Note that compared with B's previous distance vector, there are three new lower-cost entries for destinations D, F, and H. This new distance vector then becomes B's current distance vector. Now let's take a look at node C, again at time t equals 1, and after C has received B's initial distance vector. Let's see how C recomputes its own distance vector, but before doing so, let's step back and take a look at the picture.

here and think intuitively about what B is telling C by B sending its initial distance vector. Well, B is saying, hey, look, I can reach A at a cost of 8 and I can reach E at a cost of 1. Well, B is C's neighbor, and C knows if that B can reach E with a cost of 1, and C knows that it can reach B with a cost of 1, then C knows that it can reach E with a cost of 2 via B. And this is precisely the Bellman-Ford equation. That's the intuition behind Bellman-Ford. It's not clear?

Well, hit the rewind button and listen to that explanation again. And so here are C's calculations of its new decision. distance vector.

Let's focus on C's DV entry to destination E here. C's calculation is simple since it's only got one neighbor. C says for me to get to E, I can get to B with a cost of one, and B tells me that if B can get to E with a cost of one, so my cost, C's cost to get to E via B is one plus one equals two. Well, you're probably thinking it's getting a little tedious to go through one example after another, but you might.

You might want to do a few calculations for yourself, just to test your understanding. For example, consider the scenario here where node E is receiving distance vector tables from its neighbors B, D, H, and F. What's the new distance vector computed by node E?

Which entries have changed? The Bellman-Ford algorithm can be thought of as diffusing information throughout the network. To appreciate this notion of diffusion, let's take a look at node C and ask ourselves the question, what do other nodes in the network know about the state of the network?

of node C, say at T equals 0, and when do they learn this information? At T equals 0, C hasn't communicated with anybody, so no other nodes have information about node C. At T equals 1, C's state at t equals 0 has propagated over to b by the exchange of distance vectors. So at t equals 1, c's state at t equals 0 can influence the calculations at b at t equals 1. At t equals 2, information from node c at t equals 0 has propagated further to nodes e and to nodes a.

And imagine your node e. At t equals 2, you're seeing the first influence of the state of node c at t equals zero, now at t equals two, two time units later. This notion of information propagation speed, it's almost like looking at a star at night. The light you're seeing now was emitted by that star many light years ago, and so it is with information propagation in a network. The cost that e is seeing at t equals two regarding c reflects c state at t equals zero, even though e is receiving this information at t equals two.

Well, continuing on... At t equals 3, C's state at t equals 0 can influence distance vector computations up to 3 hops away. That's at nodes D, F, and H.

And finally, at t equals 4, C's state at t equals 0 can influence distance vector computations up to 4 hops away. In this case, at nodes G and I as well. And note that it's taken 4 time steps, the diameter of the network, for information to propagate from one edge of the network to the other. So far, we've only looked at the initial distance vector calculation. After some number of iterations, the computational process will have quiesced.

Remember, if there are no changes in a local distance vector, I'm not going to send out distance vector updates to the computer. to my neighbors. So eventually, when there are no local changes computed anymore, the algorithm will have converged.

There'll be no more distance vectors being exchanged. Now, let's take a look at what happens if there are link cost changes. Because our distance vector algorithm can already accommodate that. And the steps are the same.

A link cost change is noted. I'm a local node. I note that local change.

I recompute my local distance vector using the new local link costs as well as the old distance vectors that I have for my neighbors. And if my local distance vector is changed once again, I just send it out to my local neighbors. So the algorithm is pretty much unchanged.

So let's now take a look at an example of how link cost changes propagate. You using the network shown up here on the right. And let's take the point of view of node Y, who sees the XY link cost change from 4 to 1. It goes down.

So at t equals 0, let's say Y detects this link cost change, updates its distance vector to note that now it's got a new cost to X of 1, and sends its new distance vector to its neighbors. At t1, Z receives this updated distance vector from Y, updates its own distance vector, computing its new... least cost path to x as 2. And now since z's distance vector has changed, z sends its distance vector to its neighbors x and y.

At t2, y receives z's updated distance vector, recalculates its own distance vector, and in this case y's least costs in its distance vector don't change. And so y doesn't send anything back out to z or x. The algorithm quiesces and is done.

So just after two iterations, the recomputation... of the distance vector here concludes. And we'll note that the network-wide recomputation of the distance vectors happened pretty quickly for this link cost change example. The exact amount of time needed was related to the diameter of the network, as you might imagine. And that's as fast as it could happen, given our earlier starlight analogy.

And there's a saying in networking that good news travels fast. When a link weight goes down in Bellman-Ford, all nodes recompute their final distance vectors relatively quickly. But we'll get to that in a minute.

But what happens if link costs go up? In this example here, the cost of the link from X to Y now goes to 60. And you'll want to think about what happens in this example, but basically, this is what happens. When the link cost goes to 60, Y says, uh-oh, I better start routing through Z since Z has advertised the path to me with a cost of 5 to X, giving me an overall cost of 6. Y informs Z of its Y's new cost to X via a distance vector update. Will Z then says this update and says, golly, if y's cost to x is 6, then my cost to x is now 7 through y, and informs y.

y says, uh-oh, if z's cost is 7 to get to x, then my cost is going to be 8. z then says, well, if y's cost to get to x is 8, then mine is 9, and so on. This is what's known as the count to infinity problem. And think about what would have happened if the link cost had changed to 6 million instead of just 60. Well, Well, it'd be a lot of iterations. Of course, there are workarounds to the count to infinity problem, but I think the larger lesson here is that as beautiful and elegant as distributed algorithms are, their operations and their pathologies can often be sunk.

Well, let's wrap up our discussion of routing algorithms with a comparison of link state and distance vector algorithms. And let's start off with message complexity. We saw earlier that the message complexity to do link state dissemination is order n squared for the link state algorithm. For distance vector, we learned that it takes the order of the diameter of the network, potentially order n for information to propagate from one end of the network to the other.

And we saw that at each step, a node may potentially need to communicate with each of its neighbors. In terms of speed of conversion, We saw that link state is order n squared computational algorithm, order n squared communication algorithm. And we saw that there can be oscillations.

In the case of distance vector, we saw that convergence times, again, can vary. And there can actually be routing loops while the algorithms converge. And lastly, let's think about what can happen in a link state or a distance vector algorithm if a router malfunctions or is compromised. Well, under link state, a router can advertise. incorrect link costs, but each router computes its own routing and forwarding tables.

So failure is rather localized under link state. Under distance vector, a router can advertise an incorrect path cost. For example, a router could say, hey, I've got a really low path cost to everywhere in the internet.

This is known as black holing. Since each router's distance vector is used by others, errors can then propagate through the network as additional routers advertise their new distance vector. vector.

And this type of black hole routing failures actually occurred in the internet when a small ISP advertised, hey, I've got a zero cost pass to a major ISP. I think that ISP was AT&T when this ISP wasn't really connected to that major ISP. And hey, what network can pass up a zero path cost to a major destination network?

And so many other networks in the internet who wanted to route traffic to AT&T sent their traffic to this small ISP where it was was black-holed. Now imagine you're AT&T and you're saying, hey, why am I no longer receiving traffic from a good portion of the internet anymore? Well, the answer was that traffic's been black-holed in a small ISP instead due to a misconfigured router in that ISP.

Well, that wraps up our discussion of routing algorithms, Dijkstra's centralized link state algorithm, the distributed Bellman-Ford algorithm. In the next two sections, we're going to cover the embodiment of these routing algorithms. algorithms and internet routing protocols, the Open Shortest Path First OSPF routing protocol, and the BGP, Border Gateway Protocol.

I think you'll enjoy them.

Transcript for:Understanding Distributed Bellman-Ford Algorithm

Transcript for:
Understanding Distributed Bellman-Ford Algorithm