So now, let's talk about the final and most serious problem, which is that stuff
in the Internet, nodes, links, etc., is failing all the time.
You know its true that we just argued that the asynchronous bellman ford
shortest path rounding protocol is guaranteed to converge to correct
shortest path. that was assuming that the network was
static that no legs were coming up and down.
So one particularly simple problem in a presence of failure is what's known as
the counting to infinity problem. So I'm going to show you a particularly
contrived version of this problem just to kind of illustrate the form in the
simplest way, but it's quite easy to come up with more realistic examples.
And this problem is not just some kind of theoretical flaw in the distributed
Bellmanu2013Ford algorithm. This problem really was observed in
practice with those running protocols from the 1970's.
So imagine we just have a super simple network verticies s, v, and t by directed
arch from s to v and an arc from v to t everything has unit cost and we're doing
it routing to the destination t. You might if you want a more realistic
example, think about the arcs between S and V as standing in for longer paths
that have multiple hops. In any case let's imagine that we
successfully computed shortest paths on this basic network so that distance form
T to itself is zero, from V to T is one and from S to T is two.
Now, again, the issue is that links are failing all the time on the internet.
So, at some point, this link from V to T might go down.
So, at some point, V is going to notice that its link to T has failed and it's
going to have to reset its shortest path estimate to T to be plus infinity.
And in an effort to recover connectivity to t, it makes sense for v to ask it's
neighbors, do they have paths to t? And if so, how long are they?
So in particular, v will pull s, and s will say, oh yeah, I have a path to t of
distance only two. And v says, oh well that's great.
I, currently my estimate to t is plus infinity.
I can get to s with length one, s says it can get back to t with length two.
So that gives me a path of length three to t.
Now, of course the flaw in this reasoning is that s was depending on v to get to t
and now all of a sudden, v circularly is going to use s in its mind to get all the
way back to t. So this already illustrates the dangers
of naively implementing the asynchronous Bellman Ford algorithm in the presence of
link failures. Where does the name counting to infinity
come from. Well you can imagine that for some
implementations of this protocol, S would then say, oh boy, okay, V just revised
it's shortest path estimate to T to be three.
My next hop was to V. So if V takes two longer to get to T then
I'm going to take two longer to get to T as well.
So at that point S updates it's shortest path distance to be four.
And now this keeps going on. At this point V says, oh well, if S is
going to take two longer to get to T, I was depending on S.
So, I have, have to go up by two. And then, S goes up by two and B goes up
by two and so on, forevermore. So failures cause problems for the
convergence of the distributive shortest-path routing protocols.
Not just the counting-to-infinity problem, there are others as well.
And this is a tough issue. Much blood and ink has been spilled over
the relative merits of different possible solutions for dealing with failures.
Back in the 1980s people were largely proposing sort of hacks to the basic
protocol. I will the, give them credit, they had
some pretty ridiculous and fun names for their hacks, like split horizon with
poison reverse." but what eventually people converged on is moving from these
so-called distance-vector protocols to what are called path vector protocols.
And what happens in a path vector protocol is, each vertex maintains not
just the next top to every possible destination, but they actually keep
locally the entire path, which is going to get used from v to each destination t.
So there's definitely some irony here because this is essentially the solution
to reconstructing optimal solutions in dynamic programming that we've been
studiously avoiding this whole time. You might, you might recall when we first
started discussing reconstruction algorithms, this was back independent
sets of path graphs. We first said, well, you know, you could
in the forward pass through the array store not just the optimal solution value
but the optimal solution itself. But we argued, well, that's, that's not
really the best idea. It wastes time.
It wastes space. Much smarter is to just reconstruct an
optimal solution via a backward pass through the filled in table.
But what's happening here is this optimized version of the reconstruction
algorithm that doesn't use extra time or space, it's just not robust enough to
withstand the vagaries of internet routing.
So we are going to the crudest solution, where we literally just store optimal
solutions, not just the solution value it's self.
So that explains why this is called a path vector protocol.
Distance vector protocol you store a distance for each possible destination.
Here were storing a path for each possible destination.
So the drawback is exactly what we've been saying all along.
If you store the optimal solutions, and not just the optimal solution value, it's
going to take quite a bit more space. And indeed, doing this blows up the
routing tables in routers, that's just a fact.
There are two quite important benefits. The first we've already discussed,
they're more robust to failures. I am not going to discuss the details
about how you use this extra path information to handle failures better.
But certainly in our contrived motivating example you can see how if S and V
actually knew the entire path they were storing to T, they could make sure that
they didn't get into this counting to infinity problem.
But moving to a path vector protocol doesn't just add robustness, it also
enables new functionality. So in particular, passing around entire
paths allows. Vertices to express more complicated
preferences over routes than merely what their lengths are.
Imagine, for example, you were a small internet provider.
And you have a much more favorable contract with AT&T than you do with
Sprint. So it cost you much less money to send
traffic through AT&T as an intermediary than it does through Sprint.
Well, now imagine you're running this, distributive shortest-path protocol.
And two of your neighbors offer you two paths to get to some destination T.
The first path goes through AT&T, the second path goes through Sprint.
And, of course, the only reason you know this information is because it's a path
vector protocol, and you're passing around the actual path and you can see
what the intermediate stops are. Well then your free to say oh well I'm
going to use as my path to t and this is what I'm going to advertise to other
people I'm going to advertise and store the path that goes through AT&T.
I'm going to ignore the one that goes through Sprint.
So that is more or less how the border gateway protocol, aka the BGP protocol,
works, and that is the protocol which governs how traffic gets routed through
the core of the Internet. So that wraps up our discussion of how
shortest path algorithms dating back to the 1950's has played a fundamental role
in how shortest path routing has evolved in the Internet over the past half
century.