1 00:00:00,000 --> 00:00:03,695 At the beginning of the course we mentioned that a developing ford 2 00:00:03,695 --> 00:00:07,887 algorithm provides the foundation for modern day internet routing protocols 3 00:00:07,887 --> 00:00:11,180 this video is going to supply a few of the details. 4 00:00:11,180 --> 00:00:15,767 So for starters, when you look at the code of the Bellman-Ford algorithm I hope 5 00:00:15,767 --> 00:00:20,180 on an intuitive level it seems like a sort of distributed algorithm in some 6 00:00:20,180 --> 00:00:21,574 sense of the word. Right? 7 00:00:21,574 --> 00:00:25,696 Think about what you need to compute a given subproblem A of I comma V. 8 00:00:25,696 --> 00:00:30,167 Well the vertex V just needs to know from each of the possible previous hops. 9 00:00:30,167 --> 00:00:33,477 So from each of the vertices that can talk directly to V. 10 00:00:33,477 --> 00:00:36,787 What their subproblem solution was on the previous round. 11 00:00:36,787 --> 00:00:41,378 So in each round each vertex in some sense only communicates with immediate 12 00:00:41,378 --> 00:00:44,565 neighbors. Vertices to which it has direct 13 00:00:44,565 --> 00:00:48,010 connection. Now as you can imagine, there's a fairly 14 00:00:48,010 --> 00:00:52,640 long list of engineering challenges that have to be tackled to move from the basic 15 00:00:52,640 --> 00:00:56,878 Bellman-Ford algorithm to a routing protocol that you could conceivably use 16 00:00:56,878 --> 00:00:59,890 in practice. So what I'll do here is highlight some of 17 00:00:59,890 --> 00:01:04,463 the main issues and what's the high level solution to those issues and with those 18 00:01:04,463 --> 00:01:08,479 fixes to the basic Bellman-Ford algorithm, we'll actually have something 19 00:01:08,479 --> 00:01:12,941 that's surprisingly close to how modern day Internet protocols, protocols really 20 00:01:12,941 --> 00:01:15,565 work. That said, the discussion here will be 21 00:01:15,565 --> 00:01:18,099 necessarily brief, and somewhat deliberately naive. 22 00:01:18,099 --> 00:01:21,596 So for those of you who want to understand this material on a really 23 00:01:21,596 --> 00:01:25,548 nitty-gritty level, I encourage you to buy a networking book, take a networking 24 00:01:25,548 --> 00:01:28,600 class, or read more about the topic on the web. 25 00:01:28,600 --> 00:01:32,522 So, I want to talk about three modifications to the basic Bellman-Ford 26 00:01:32,522 --> 00:01:35,300 algorithm. I'll discuss them in order from the most 27 00:01:35,300 --> 00:01:38,755 trivial to the least trivial. The first and simplest modification to 28 00:01:38,755 --> 00:01:42,554 the algorithm is motivated [SOUND] by the fact that routing in the internet is 29 00:01:42,554 --> 00:01:45,440 destination-driven. Given a piece of data floating around in 30 00:01:45,440 --> 00:01:49,191 the internet, you really don't care that much where it came, where it came from. 31 00:01:49,191 --> 00:01:51,932 What you really care about is where it needs to go, right? 32 00:01:51,932 --> 00:01:55,827 It's exactly the same thing as with snail mail, the way it gets routed around the 33 00:01:55,827 --> 00:01:57,943 globe. And if I'm on vacation in, say, Croatia, 34 00:01:57,943 --> 00:02:01,550 and I put a postcard in the mail, I don't even need to put a return address. 35 00:02:01,550 --> 00:02:04,820 I just say the address of my friend who might be back in the states. 36 00:02:04,820 --> 00:02:08,283 [SOUND] And then, just based on its destination, this postcard get routed 37 00:02:08,283 --> 00:02:10,880 appropriately. First through local hops within Croatia. 38 00:02:10,880 --> 00:02:14,879 Then on a plane over the Atlantic Ocean and then again locally within the US 39 00:02:14,879 --> 00:02:17,372 network. Same thing on the internet, based on the 40 00:02:17,372 --> 00:02:21,216 destination IP address of a packet, that's how you know which intermediate 41 00:02:21,216 --> 00:02:26,240 sequence of routers it has to go through to get to its eventual destination. 42 00:02:26,240 --> 00:02:31,290 All you have to do to accommodate destination driven routing is reverse all 43 00:02:31,290 --> 00:02:34,109 of the directions in the Bellman-Ford algorithm. 44 00:02:34,109 --> 00:02:38,630 So instead of having a source vertex, S, out of which you compute all shortest 45 00:02:38,630 --> 00:02:42,741 paths, you're going to have a destination vertex, T, into which you compute 46 00:02:42,741 --> 00:02:47,146 shortest paths from all possible origins. Each vertex, rather than storing a 47 00:02:47,146 --> 00:02:51,844 predecessor pointer, the final hop on a shortest path from S to that vertex, it's 48 00:02:51,844 --> 00:02:56,200 going to store the first hop on a shortest path to the destination, t. 49 00:02:56,200 --> 00:03:00,906 Now of course if you're a router in the Internet, you don't want to be optimized 50 00:03:00,906 --> 00:03:05,319 purely for a single destination T. You have to be ready to accommodate data 51 00:03:05,319 --> 00:03:09,613 down for anywhere in the Internet. So as a result these vertex stores, this 52 00:03:09,613 --> 00:03:14,261 shortest path distance in the first hop, not just to a single destination T, but 53 00:03:14,261 --> 00:03:18,379 to every relevant destination t. So it's prepared for any data that it 54 00:03:18,379 --> 00:03:21,840 might acquire. So this should sound pretty intense. 55 00:03:21,840 --> 00:03:25,440 There's a lot of potential destinations of T, there's a lot of IP addresses out 56 00:03:25,440 --> 00:03:27,240 there in the world. So a couple comments. 57 00:03:27,240 --> 00:03:30,255 So first of all, for most computers and the internet they're not really 58 00:03:30,255 --> 00:03:33,810 responsible for knowing how to get to a lot of destinations t and the Internet. 59 00:03:33,810 --> 00:03:36,510 This is cause of the hierarchical structure of the Internet, 60 00:03:36,510 --> 00:03:38,625 right? So if it's just some computer inside the 61 00:03:38,625 --> 00:03:42,360 stanford network, it really only needs to know how to get to other computers inside 62 00:03:42,360 --> 00:03:44,745 the stanford network, of which there aren't that many. 63 00:03:44,745 --> 00:03:47,715 And it also has to know how to get to the stanford gateway router. 64 00:03:47,715 --> 00:03:51,180 And if it's data down for somewhere outside of the Stanford network, you just 65 00:03:51,180 --> 00:03:54,060 sort of defer the responsibility to the stanford gateway router. 66 00:03:54,060 --> 00:03:57,144 And you let it handle it. You just get that far, and then it will 67 00:03:57,144 --> 00:04:00,470 take it from there. On the other hand, for the routers 68 00:04:00,470 --> 00:04:04,388 embedded in the core of the Internet, they really are responsible for knowing 69 00:04:04,388 --> 00:04:06,627 how to get to all kinds of different places. 70 00:04:06,627 --> 00:04:09,985 Basically the entire Internet. And their routing tables, guess what, 71 00:04:09,985 --> 00:04:13,496 they're really quite big. So the number of entries might be say in 72 00:04:13,496 --> 00:04:16,841 the hundreds of thousands. So as you can imagine, routing table 73 00:04:16,841 --> 00:04:20,079 implementation is, is something that people who work in networking have 74 00:04:20,079 --> 00:04:22,314 thought about a ton. There's interesting hardware 75 00:04:22,314 --> 00:04:26,053 optimizations, software optimizations and then people also worry about how can you 76 00:04:26,053 --> 00:04:28,516 just make sure routing cable size doesn't get too big. 77 00:04:28,516 --> 00:04:32,073 So, for example, you want to avoid the fragmentation of IP addresses to make 78 00:04:32,073 --> 00:04:35,448 sure that you don't need that many distinct entries in the routing tables. 79 00:04:35,448 --> 00:04:38,420 Hundreds of thousands is plenty, thank you very much. 80 00:04:38,420 --> 00:04:42,681 You will sometimes hear Bellman-Ford based shortest path protocols like this 81 00:04:42,681 --> 00:04:47,053 one, called distance vector protocols. The distance vector that this term refers 82 00:04:47,053 --> 00:04:51,204 to, is, at a given vertex, you have a vector indexed by possible destinations 83 00:04:51,204 --> 00:04:53,584 t. And you're keeping track of the shortest 84 00:04:53,584 --> 00:04:56,960 path distance in the first hop for all of those destinations. 85 00:04:56,960 --> 00:05:01,332 So, the second issue we need to address is a little more serious, but it's still 86 00:05:01,332 --> 00:05:04,340 not too bad. This issue is asynchrony. 87 00:05:04,340 --> 00:05:08,434 And what I mean is if you look back at our basic Bellman-Ford algorithm it was 88 00:05:08,434 --> 00:05:12,270 synchronous in the following sense. We were careful to structure the outer 89 00:05:12,270 --> 00:05:16,623 iteration of the four loop so that all of the sub problems corresponding to value i 90 00:05:16,623 --> 00:05:20,044 - 1 gets solved before any of the sub problems with index i. 91 00:05:20,044 --> 00:05:23,879 Now when you're talking about the internet and you have different routers, 92 00:05:23,879 --> 00:05:26,367 different computers running at different speeds. 93 00:05:26,367 --> 00:05:29,736 You have different physical connections with different bandwidth. 94 00:05:29,736 --> 00:05:32,224 There's no way you're going to keep people in sync. 95 00:05:32,224 --> 00:05:35,749 There's noway you can implement synchronized rounds at the Internet 96 00:05:35,749 --> 00:05:38,948 scale. But what's cool is that the Bellman-Ford 97 00:05:38,948 --> 00:05:42,876 algorithm is surprisingly robust, to the order in which you solve its subproblems. 98 00:05:42,876 --> 00:05:46,707 Really if you solve them in any kind of reasonable order, you're still going to 99 00:05:46,707 --> 00:05:50,100 be computing correct shortest paths at the end of the day. 100 00:05:50,100 --> 00:05:55,364 So to explain what I mean, let's change the Bellman-Ford algorithm to be 101 00:05:55,364 --> 00:06:00,058 push-based rather than pull-based. So the basic Bellman-Ford algorithm is 102 00:06:00,058 --> 00:06:04,022 pull based in the following sense. For each other iteration I, and each 103 00:06:04,022 --> 00:06:08,496 vertex V, in this iteration, the vertex V in effect asks its neighbors, for their 104 00:06:08,496 --> 00:06:11,781 most recent information. So, for there, sub-problem solution 105 00:06:11,781 --> 00:06:14,839 values, from the last iteration of the outer four loop. 106 00:06:14,839 --> 00:06:18,916 We're going to change it to be push based, which is rather than asking your 107 00:06:18,916 --> 00:06:23,164 neighbor for the latest information, whenever you have something new to say, 108 00:06:23,164 --> 00:06:27,637 whenever your sub-problem value changes you're just going to go ahead and tell 109 00:06:27,637 --> 00:06:30,877 all of your neighbors. You're going to push that information 110 00:06:30,877 --> 00:06:34,580 onto your neighbors whether they want it or not. 111 00:06:34,580 --> 00:06:37,174 So, I'm not going to define this especially formally. 112 00:06:37,174 --> 00:06:41,462 It's easy to do, let me just show you a very quick example which hopefully gives 113 00:06:41,462 --> 00:06:45,384 you a gist of the idea. So, consider this green network and 114 00:06:45,384 --> 00:06:49,098 suppose you're trying to compute shortest paths from everywhere to t. 115 00:06:49,098 --> 00:06:53,190 Remember we've switched form source driven to destination driven routing. 116 00:06:53,190 --> 00:06:57,281 So, initially t knows how to get to it'self with link zero and everyone else 117 00:06:57,281 --> 00:07:01,581 only has plus infinity. So to get started the destination t is 118 00:07:01,581 --> 00:07:06,505 going to inform all of its neighbors that it can get to itself with a path of 119 00:07:06,505 --> 00:07:08,651 length zero. So who does it notify? 120 00:07:08,651 --> 00:07:12,501 It notifies V and W because U is not directly connected to T. 121 00:07:12,501 --> 00:07:18,200 U does not learn this information yet. So because the Internet is asynchronous, 122 00:07:18,200 --> 00:07:23,038 even though t probably sends out messages at exactly the same time, to v and w, 123 00:07:23,038 --> 00:07:28,000 telling it about its cool zero path from it to itself, who knows, which of v or w 124 00:07:28,000 --> 00:07:32,156 gets that information first. So maybe, the line speed is faster to w, 125 00:07:32,156 --> 00:07:36,960 and w finds out first, the t can get to itself with a path of link zero. 126 00:07:36,960 --> 00:07:42,361 At that point, w says well cool, I didn't have any path at all previously, but I 127 00:07:42,361 --> 00:07:46,516 can get to t with cost only four and once I'm at t I'm done. 128 00:07:46,516 --> 00:07:51,709 T can get to itself with cost zero. So, w updates its shortest path estimate 129 00:07:51,709 --> 00:07:55,780 to the destination t from plus infinity down to four. 130 00:07:55,780 --> 00:07:59,185 So now remember we're doing this push-based implementation. 131 00:07:59,185 --> 00:08:02,649 So W has new information, it has a better shortest path to T. 132 00:08:02,649 --> 00:08:07,151 So it needs to tell all of its neighbors. In particular it's going to tell, the 133 00:08:07,151 --> 00:08:10,038 neighbor U that it has a path of length four to T. 134 00:08:10,038 --> 00:08:14,829 And now remember still floating around in the internet is this message from T to V 135 00:08:14,829 --> 00:08:17,946 advertising T's empty path, from itself, of length zero. 136 00:08:17,946 --> 00:08:22,391 But then who knows what happens first. Maybe in fact W's message to U arrives 137 00:08:22,391 --> 00:08:25,970 before T's message to V arrives. So then U's going to say, Oh, cool. 138 00:08:25,970 --> 00:08:31,226 Well, if from W to T has cost only four, I can get to W would cost only three. 139 00:08:31,226 --> 00:08:35,320 So, that gives me a path of like seven all the way to t. 140 00:08:35,320 --> 00:08:38,228 Now in this graph, there are no incoming arcs to U. 141 00:08:38,228 --> 00:08:42,649 So U doesn't have anybody to notify. And now at some point in the future, the 142 00:08:42,649 --> 00:08:45,325 message from T actually arrives at the node V. 143 00:08:45,325 --> 00:08:47,710 And so at that point V says, oh, okay cool. 144 00:08:47,710 --> 00:08:52,305 So I can get direct to T on an edge of cost two, from T I only have to pay zero 145 00:08:52,305 --> 00:08:56,552 to get the rest of the way to T. So I'm going to update my estimate of my 146 00:08:56,552 --> 00:08:59,170 distance to T from plus infinity down to two. 147 00:08:59,170 --> 00:09:03,050 V now that it has a revised estimate, it's responsible for notifying all of 148 00:09:03,050 --> 00:09:05,793 it's neighbors. So it tells U, it says hey U, I can get 149 00:09:05,793 --> 00:09:09,519 to T on a path of length only two. And then U says well, hey great, that's 150 00:09:09,519 --> 00:09:12,261 actually an improvement. My old path had length seven. 151 00:09:12,261 --> 00:09:16,298 I can get to the node V with cost only one and V tells me it get, get the rest 152 00:09:16,298 --> 00:09:20,334 of the way with cost only two, so that gives me a path of length three all the 153 00:09:20,334 --> 00:09:23,794 way to T. So in this particular example, this 154 00:09:23,794 --> 00:09:28,717 asynchronous, push-based implementation of Bellman-Ford did correctly compute 155 00:09:28,717 --> 00:09:33,320 shortest paths, and that is in fact true in general in any network. 156 00:09:33,320 --> 00:09:37,082 And of course when I state this fact, I'm assuming that there's no negative cycles. 157 00:09:37,082 --> 00:09:40,431 In the context of Internet routing, actually, negative cycles aren't a big 158 00:09:40,431 --> 00:09:42,588 deal. Usually you think of all the edges having 159 00:09:42,588 --> 00:09:45,320 non-negative length in internet routing applications. 160 00:09:45,320 --> 00:09:47,586 Why does the algorithm converge eventually? 161 00:09:47,586 --> 00:09:51,381 Well essentially it's because every single update strictly decreases 162 00:09:51,381 --> 00:09:55,228 somebody's estimate of their shortest path distance to the destination T. 163 00:09:55,228 --> 00:09:59,550 And there's only a finite number of these configurations you can go through until 164 00:09:59,550 --> 00:10:03,200 you finally must be at the correct shortest path distances. 165 00:10:03,200 --> 00:10:07,211 So this very crude convergence argument only provides an exponential upper down 166 00:10:07,211 --> 00:10:11,222 on the, on, on number of updates that you might need before you correctly compute 167 00:10:11,222 --> 00:10:13,930 shortest paths. And in fact, at least in the worst case 168 00:10:13,930 --> 00:10:17,590 theoretically this asynchronous version of Bellman-Ford can require an 169 00:10:17,590 --> 00:10:21,551 exponential number of updates before it successfully finds all of the shortest 170 00:10:21,551 --> 00:10:23,757 paths. That's a nontrivial problem you might 171 00:10:23,757 --> 00:10:26,902 want to think about. So, if you have the luxury of 172 00:10:26,902 --> 00:10:30,651 implementing the Bellman-Ford rhythm in a synchronous or centralized setting, you 173 00:10:30,651 --> 00:10:34,261 do want to use the synchronous version that we discussed in the basic version. 174 00:10:34,261 --> 00:10:38,057 If you're in an asynchronous setting you don't really have a choice other than to 175 00:10:38,057 --> 00:10:40,556 implement it asynchronously. And then of course if you're hoping 176 00:10:40,556 --> 00:10:44,121 you're going to in your particular network have convergence time much better 177 00:10:44,121 --> 00:10:48,725 than the worst case, exponential bound. So the original Bellman-Ford Algorithm is 178 00:10:48,725 --> 00:10:52,569 from the 1950s, and with the modifications we've discussed to this 179 00:10:52,569 --> 00:10:56,995 point, we're up to routing protocols that were deployed as late as the 1970s. 180 00:10:56,995 --> 00:11:01,537 So if you want to read more you can look at the RIP and RIP2 Internet routing 181 00:11:01,537 --> 00:11:05,292 protocols. And if you really want to be nerdy about 182 00:11:05,292 --> 00:11:10,295 it you can check out the request for comments related to these protocols. 183 00:11:10,295 --> 00:11:12,930 RFC number 1,058. So what is an RFC? 184 00:11:12,930 --> 00:11:16,621 What's a request for comments? Well this is the mechanism by which the 185 00:11:16,621 --> 00:11:20,414 community around the Internet sort of vets proposed modifications proposed 186 00:11:20,414 --> 00:11:23,044 protocols. So if you really want to see nitty gritty 187 00:11:23,044 --> 00:11:25,320 details those that's a good place to look.