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.