0:00

At the beginning of the course we mentioned that a developing ford

Â algorithm provides the foundation for modern day internet routing protocols

Â this video is going to supply a few of the details.

Â So for starters, when you look at the code of the Bellman-Ford algorithm I hope

Â on an intuitive level it seems like a sort of distributed algorithm in some

Â sense of the word. Right?

Â Think about what you need to compute a given subproblem A of I comma V.

Â Well the vertex V just needs to know from each of the possible previous hops.

Â So from each of the vertices that can talk directly to V.

Â What their subproblem solution was on the previous round.

Â So in each round each vertex in some sense only communicates with immediate

Â neighbors. Vertices to which it has direct

Â connection. Now as you can imagine, there's a fairly

Â long list of engineering challenges that have to be tackled to move from the basic

Â Bellman-Ford algorithm to a routing protocol that you could conceivably use

Â in practice. So what I'll do here is highlight some of

Â the main issues and what's the high level solution to those issues and with those

Â fixes to the basic Bellman-Ford algorithm, we'll actually have something

Â that's surprisingly close to how modern day Internet protocols, protocols really

Â work. That said, the discussion here will be

Â necessarily brief, and somewhat deliberately naive.

Â So for those of you who want to understand this material on a really

Â nitty-gritty level, I encourage you to buy a networking book, take a networking

Â class, or read more about the topic on the web.

Â So, I want to talk about three modifications to the basic Bellman-Ford

Â algorithm. I'll discuss them in order from the most

Â trivial to the least trivial. The first and simplest modification to

Â the algorithm is motivated [SOUND] by the fact that routing in the internet is

Â destination-driven. Given a piece of data floating around in

Â the internet, you really don't care that much where it came, where it came from.

Â What you really care about is where it needs to go, right?

Â It's exactly the same thing as with snail mail, the way it gets routed around the

Â globe. And if I'm on vacation in, say, Croatia,

Â and I put a postcard in the mail, I don't even need to put a return address.

Â I just say the address of my friend who might be back in the states.

Â [SOUND] And then, just based on its destination, this postcard get routed

Â appropriately. First through local hops within Croatia.

Â Then on a plane over the Atlantic Ocean and then again locally within the US

Â network. Same thing on the internet, based on the

Â destination IP address of a packet, that's how you know which intermediate

Â sequence of routers it has to go through to get to its eventual destination.

Â All you have to do to accommodate destination driven routing is reverse all

Â of the directions in the Bellman-Ford algorithm.

Â So instead of having a source vertex, S, out of which you compute all shortest

Â paths, you're going to have a destination vertex, T, into which you compute

Â shortest paths from all possible origins. Each vertex, rather than storing a

Â predecessor pointer, the final hop on a shortest path from S to that vertex, it's

Â going to store the first hop on a shortest path to the destination, t.

Â Now of course if you're a router in the Internet, you don't want to be optimized

Â purely for a single destination T. You have to be ready to accommodate data

Â down for anywhere in the Internet. So as a result these vertex stores, this

Â shortest path distance in the first hop, not just to a single destination T, but

Â to every relevant destination t. So it's prepared for any data that it

Â might acquire. So this should sound pretty intense.

Â There's a lot of potential destinations of T, there's a lot of IP addresses out

Â there in the world. So a couple comments.

Â So first of all, for most computers and the internet they're not really

Â responsible for knowing how to get to a lot of destinations t and the Internet.

Â This is cause of the hierarchical structure of the Internet,

Â right? So if it's just some computer inside the

Â stanford network, it really only needs to know how to get to other computers inside

Â the stanford network, of which there aren't that many.

Â And it also has to know how to get to the stanford gateway router.

Â And if it's data down for somewhere outside of the Stanford network, you just

Â sort of defer the responsibility to the stanford gateway router.

Â And you let it handle it. You just get that far, and then it will

Â take it from there. On the other hand, for the routers

Â embedded in the core of the Internet, they really are responsible for knowing

Â how to get to all kinds of different places.

Â Basically the entire Internet. And their routing tables, guess what,

Â they're really quite big. So the number of entries might be say in

Â the hundreds of thousands. So as you can imagine, routing table

Â implementation is, is something that people who work in networking have

Â thought about a ton. There's interesting hardware

Â optimizations, software optimizations and then people also worry about how can you

Â just make sure routing cable size doesn't get too big.

Â So, for example, you want to avoid the fragmentation of IP addresses to make

Â sure that you don't need that many distinct entries in the routing tables.

Â Hundreds of thousands is plenty, thank you very much.

Â You will sometimes hear Bellman-Ford based shortest path protocols like this

Â one, called distance vector protocols. The distance vector that this term refers

Â to, is, at a given vertex, you have a vector indexed by possible destinations

Â t. And you're keeping track of the shortest

Â path distance in the first hop for all of those destinations.

Â So, the second issue we need to address is a little more serious, but it's still

Â not too bad. This issue is asynchrony.

Â And what I mean is if you look back at our basic Bellman-Ford algorithm it was

Â synchronous in the following sense. We were careful to structure the outer

Â iteration of the four loop so that all of the sub problems corresponding to value i

Â - 1 gets solved before any of the sub problems with index i.

Â Now when you're talking about the internet and you have different routers,

Â different computers running at different speeds.

Â You have different physical connections with different bandwidth.

Â There's no way you're going to keep people in sync.

Â There's noway you can implement synchronized rounds at the Internet

Â scale. But what's cool is that the Bellman-Ford

Â algorithm is surprisingly robust, to the order in which you solve its subproblems.

Â Really if you solve them in any kind of reasonable order, you're still going to

Â be computing correct shortest paths at the end of the day.

Â So to explain what I mean, let's change the Bellman-Ford algorithm to be

Â push-based rather than pull-based. So the basic Bellman-Ford algorithm is

Â pull based in the following sense. For each other iteration I, and each

Â vertex V, in this iteration, the vertex V in effect asks its neighbors, for their

Â most recent information. So, for there, sub-problem solution

Â values, from the last iteration of the outer four loop.

Â We're going to change it to be push based, which is rather than asking your

Â neighbor for the latest information, whenever you have something new to say,

Â whenever your sub-problem value changes you're just going to go ahead and tell

Â all of your neighbors. You're going to push that information

Â onto your neighbors whether they want it or not.

Â So, I'm not going to define this especially formally.

Â It's easy to do, let me just show you a very quick example which hopefully gives

Â you a gist of the idea. So, consider this green network and

Â suppose you're trying to compute shortest paths from everywhere to t.

Â Remember we've switched form source driven to destination driven routing.

Â So, initially t knows how to get to it'self with link zero and everyone else

Â only has plus infinity. So to get started the destination t is

Â going to inform all of its neighbors that it can get to itself with a path of

Â length zero. So who does it notify?

Â It notifies V and W because U is not directly connected to T.

Â U does not learn this information yet. So because the Internet is asynchronous,

Â even though t probably sends out messages at exactly the same time, to v and w,

Â telling it about its cool zero path from it to itself, who knows, which of v or w

Â gets that information first. So maybe, the line speed is faster to w,

Â and w finds out first, the t can get to itself with a path of link zero.

Â At that point, w says well cool, I didn't have any path at all previously, but I

Â can get to t with cost only four and once I'm at t I'm done.

Â T can get to itself with cost zero. So, w updates its shortest path estimate

Â to the destination t from plus infinity down to four.

Â So now remember we're doing this push-based implementation.

Â So W has new information, it has a better shortest path to T.

Â So it needs to tell all of its neighbors. In particular it's going to tell, the

Â neighbor U that it has a path of length four to T.

Â And now remember still floating around in the internet is this message from T to V

Â advertising T's empty path, from itself, of length zero.

Â But then who knows what happens first. Maybe in fact W's message to U arrives

Â before T's message to V arrives. So then U's going to say, Oh, cool.

Â Well, if from W to T has cost only four, I can get to W would cost only three.

Â So, that gives me a path of like seven all the way to t.

Â Now in this graph, there are no incoming arcs to U.

Â So U doesn't have anybody to notify. And now at some point in the future, the

Â message from T actually arrives at the node V.

Â And so at that point V says, oh, okay cool.

Â So I can get direct to T on an edge of cost two, from T I only have to pay zero

Â to get the rest of the way to T. So I'm going to update my estimate of my

Â distance to T from plus infinity down to two.

Â V now that it has a revised estimate, it's responsible for notifying all of

Â it's neighbors. So it tells U, it says hey U, I can get

Â to T on a path of length only two. And then U says well, hey great, that's

Â actually an improvement. My old path had length seven.

Â I can get to the node V with cost only one and V tells me it get, get the rest

Â of the way with cost only two, so that gives me a path of length three all the

Â way to T. So in this particular example, this

Â asynchronous, push-based implementation of Bellman-Ford did correctly compute

Â shortest paths, and that is in fact true in general in any network.

Â And of course when I state this fact, I'm assuming that there's no negative cycles.

Â In the context of Internet routing, actually, negative cycles aren't a big

Â deal. Usually you think of all the edges having

Â non-negative length in internet routing applications.

Â Why does the algorithm converge eventually?

Â Well essentially it's because every single update strictly decreases

Â somebody's estimate of their shortest path distance to the destination T.

Â And there's only a finite number of these configurations you can go through until

Â you finally must be at the correct shortest path distances.

Â So this very crude convergence argument only provides an exponential upper down

Â on the, on, on number of updates that you might need before you correctly compute

Â shortest paths. And in fact, at least in the worst case

Â theoretically this asynchronous version of Bellman-Ford can require an

Â exponential number of updates before it successfully finds all of the shortest

Â paths. That's a nontrivial problem you might

Â want to think about. So, if you have the luxury of

Â implementing the Bellman-Ford rhythm in a synchronous or centralized setting, you

Â do want to use the synchronous version that we discussed in the basic version.

Â If you're in an asynchronous setting you don't really have a choice other than to

Â implement it asynchronously. And then of course if you're hoping

Â you're going to in your particular network have convergence time much better

Â than the worst case, exponential bound. So the original Bellman-Ford Algorithm is

Â from the 1950s, and with the modifications we've discussed to this

Â point, we're up to routing protocols that were deployed as late as the 1970s.

Â So if you want to read more you can look at the RIP and RIP2 Internet routing

Â protocols. And if you really want to be nerdy about

Â it you can check out the request for comments related to these protocols.

Â RFC number 1,058. So what is an RFC?

Â What's a request for comments? Well this is the mechanism by which the

Â community around the Internet sort of vets proposed modifications proposed

Â protocols. So if you really want to see nitty gritty

Â details those that's a good place to look.

Â