was our IPv4 And IPv6 model As well as other things like NATS Now it's all about routing So I'm going to tell you just about Some different frameworks For routing, like what shortest paths are As well as different algorithms For computing routes On some of these networks to find their way through And we'll start by looking At enterprise networks Or even individual ISP networks And by the end of this unit We will have grown in scope Instead of routing across the internet Where all of the ISPs and networks Are combined together You can look at this topic list That will just be your roadmap For where we're going to go through But I won't go into it in detail now Let's just jump ahead and see some of those units Good day viewers In this segment I'm going to talk about Shortest path routing For selecting good paths through the network So in previous segments I've talked a fair bit about That routing is going to find the best path Through the network But we haven't really said what that means In this segment we're going to delve into that topic And provide an answer And the answer we're going to provide Is going to assign costs to links And use the notion of shortest paths As a way of defining what a good path is Let me go into that in a little more detail So we would like routing To find best paths or good paths Well what are they It really depends on what you the network operator want And there are many different possibilities here You might want a good path To have low latency Because this would avoid a Securedest route There's no need to sort of go from the west coast To the east coast and back If you could avoid it On the other hand If you had a different kind of network We might want paths which had High bandwidth You might want to avoid any kind of slow This way you would fit more traffic through your network Depending on exactly How you paid for your network too You might want to avoid expensive links Maybe you'd want to avoid cellular links Of some kind for instance Just because you had some budget on them And you were going to have to pay a lot of money If you used them too much Or you might want to minimize the number of hops That packets went through the network Because in some way that would reduce the volume Of switching that goes on And if you're lucky maybe some of your equipment Would be good for your facilities Now there's actually While it might seem like I've admitted Pretty much everything here There's a class Of best That we've actually ruled out here That I haven't mentioned And that is to do with hotspots Now it might be the case that just in this network There's a bit of a hotspot at B And if we've sent traffic from A To E along that blue path there That's shown in the network here But then maybe we would say Hey there's already a lot of traffic at B So we don't want to send traffic from G say to C We would like other traffic to go round Instead of through B Well we're not going to focus On those kind of policies today Because that kind of routing Involves the traffic And best as we're going to define it now Will only consider static features Of the topology such as what nodes Are connected where You might also see That just I'm going to represent Networks as these kind of graphs So in this diagram here A line here this is a link And the circle here This is a node Previously I had a little icon or a picture For some of these things But often for routing it will suffice Just to call it a dot and give it a label Like a name like A through G Okay so best could be all of these things This is a little bit too complicated What can we do? With shortest paths We come up with an approximation Which can represent Many of these factors Roughly and what we will do Is make a cost function So that we'll be able to compute The cost of different paths And we'll choose the path Which has the lowest total cost To be the best path By assigning the cost In different ways we'll be able to Assign different factors Now often we'll call The lowest cost path the shortest path This is what you would get If you assigned the cost function To be the distance And since this is a common choice In large ISP networks What I will tend to do is use I'll be a little sloppy And I'll use cost or distance interchangeably And we'll also use Lowest or shortest interchangeably So don't be too confused about that The best paths will work As we'll go through these three steps First of all we'll assign To every link a cost Or a distance And we'll do that to capture The factors we care about It's literally distance If we wanted to minimize the latency Through the network If you made it all one You would minimize the hops through the network If every link was one If you cared about bandwidth Then we'll assign a cost to a link Because that way if we take the lowest cost We'll tend to prefer the faster links At any rate you assign a cost to a link And the operator does this This is policy And then we simply define The best path through the network Between every pair of nodes As the path through the network That has the lowest total cost Or is shortest And if we turn up any ties In that process We're just going to randomly break those ties And pick a path Whatever we pick out of those ones Since we'll have lowest cost It will be best according to our definition Let's see some examples To see how shortest paths work Here I have a picture On the right of a fairly complicated Looking network topology It's that graph from before Where the Lines represent links And the nodes Represent different equipment Kinds of icons And what you can see I've added here Is I've added a number on every link This is the cost of using the link Which I've assigned In this diagram all of the links Are bidirectional and they have the same cost In either direction It's possible to extend all of these models To networks that have links Which are not bidirectional And which have unequal costs In either direction We're going to ignore all of this And in the networks we'll look at We'll have bidirectional links with equal costs So the task here Is to find the shortest path From node A to node E Through this network What's it going to be In this segment we're going to solve problems like this Simply by inspection And later we'll see algorithms Which will work this out Now just looking at this network I see different possibilities here That could be good That has cost 10 Well actually I can see I can do a little better Than that if I go through here If I go A, B, E That has cost 8 That's lower so it's a shorter path It's best Is this the shortest possible path Well you should have a look for a moment And see if you can come up with anything better There is actually a better path through this network Hopefully you've worked it out Now I'm going to draw it in for you A to B B to C And C to E That has cost 4, plus 2, plus 1 Is 7 and that's the shortest path On this graph I've cleaned up this diagram a little bit And retraced it over and you can see it there And I've also listed Just the costs Or the distance function For some other paths that you might think of Here was our AE That was 10 But A, B, E is 8 We did slightly better than that You might also come up with some other paths Just looking around but they'll turn out not to be better For instance A, B, F, E This path Has cost 9 Not quite so good Or you could imagine doing something Going a little further around looking for something better A, B, C, D, E Cost 10 And everything else is getting longer So the other one is definitely the shortest path So now we know what a shortest path is The interesting thing about these shortest paths Which we're going to use as part of our routing Algorithms to compute these things Is that the paths have What's called an optimality property And the optimality property is that If you have a shortest path Any sub-path of it Is also a shortest path That's kind of handy actually So in one shortest path There are actually many different shortest path segments we've found So for instance Our path A, B, C, E is a shortest path Okay Well that means I actually found a lot of other shortest paths A, C is a shortest path Sorry A, B, C That first segment C, E is a shortest path B, C, E is also a shortest path And so on Now You can actually reason fairly easily to see Why these must be shortest paths The reason for instance Is that B, C, E is a shortest path If A, B, C, E is a shortest path Is Imagine for the moment that I could find A better path than B, C, E Well If that was the case I would simply Use a different route to reach E By taking that path And stapling the A to B bit on front of it And then I would have a better path From A to E But we know that the path from A to E We have is the shortest It's a contradiction So that means that the path from B, C And E must itself be a shortest path There's also another nice property we get With some of these shortest paths And this should give you a nice warm feeling You should be beginning to see why in fact We work with shortest paths because they can approximate Some of these different cost factors And they have a lot of attractive properties So the other interesting property Is that if I take the union Of all of the different shortest paths From all nodes to A particular destination Then I will get what's called the sink tree It will actually be a tree Because once you go further in Then the path When two paths meet They will both follow the same route From there on to the destination Because of this optimality property So let's see if we can find The sink tree for E So that's all destinations going towards E You can also similarly In our formulation Find source trees Which would be all of the paths from one node Say E again, out to all other nodes In fact, given that we're looking at Bidirectional links with equal cost The sink tree and the source tree will basically Be the same though, just be pointing in different Directions to go towards The route or away from the route And I'll use them a little interchangeably too Depending on what is most convenient So let's find the sink tree for E Well C goes towards E So we had this link here Now I can see the shortest way to get From D to E is just to go along this link So that will be part of the sink tree From F to E The shortest way is along this link There's no other shorter way around It's not always the case that the direct link Is shortest by the way From B to E, we actually saw That we want to go to C And then from C up to E, a dog link Way rather than going along that direct link To C What's left? Can all of the nodes get to E yet? Not quite, I need to extend it We need to work out how H gets to E Well, it's going to have to go along here To C and then from C It's going to go straight up to E And G also Is going to have to decide which way to go I can see cost 7 Sorry, let's see 3 6 here Or I can also see cost 6 up here That's a tie And we could use either of these And I'm somewhat arbitrarily going to go like this So this is a sink tree For E, and since we broke a tie There could be more than one Let's just clear that up So there are some very nice implications of sink trees Because Of this shortest path property Given that we have these shortest paths All we need to follow them Towards a destination is the destination The source that they came from Is irrelevant So you can see here Once I get to node C I'm going to then go onwards To E, it doesn't matter Whether the packet came from H Or whether it came from B Or whether it actually came from A Once it gets to C It simply follows the same remainder root to E So all we need to do is look at the destination That's fairly simple What's more We can sort of see How we might send the whole path But really all A needs to know For instance Is that it needs to send it to B Rather than directly to E And then someone else like B Will carry it further onwards This leads to a notion of a forwarding table For a node We assume that there are forwarding tables To do IP forwarding At a node the forwarding table Is going to list the next hop So that's going to allow us to forward a packet Because we'll know the direction to send it By simply looking at the destination You can see this will fit well With shortest path routes It may be that if we compute shortest path routes We will actually know a lot more About the routes through the network Than simply the next hop As I was saying in this diagram We know the whole path that you're going to take From a node to the destination But we're not going to need that forwarding So we might distill a forwarding table Of the information we have So far we've just been using Inspection to look at these graphs And find out which way to go With the sync trees In the next segment we'll look at how you can compute These paths yourself Or rather the nodes can compute it themselves By using well-defined algorithms Good day viewers In this segment we'll talk about Dijkstra's algorithm For computing shortest paths This will let computers do the calculations Instead of us, which is generally a good thing So the figure down below here Shows an example of a network topology What we'd like to be able to compute In this network topology Is the source tree from a particular node Like for instance E Out to all of the other Destination nodes in the network All of the other nodes as destinations This will allow us to work out The forwarding table for E Or which way to go To reach all the different destinations You can do that We've solved the forwarding problem Dijkstra's algorithm provides One way of computing these source trees And it's widely used as part Of a common routing protocol Which is why we're covering it Dijkstra's algorithm is named after E.W. Dijkstra, a famous computer scientist He is Well known for his contributions To programming languages You might have heard of a paper Called GoToConsideredHarmful It's also made many contributions To distributed algorithms Such as the algorithm we'll study For computing shortest paths As well as program verification So Dijkstra's algorithm That we'll look at, or it dates from 1969 So it's been around for a while It's a Single source shortest Paths algorithm Which means that it takes a given source And from that source it computes shortest paths To all of the other nodes in the network To do this it needs to know The network topology And there's also a caveat, a little restriction here All of the link costs That are on the various links in the network Need to be non-negative This is usually perfectly fine For using network graphs Because if the quantities The cost correspond to Anything physical or meaningful Chances are that they're non-negative anyhow So here's an outline of the algorithm I'll go through this outline And then we'll work through an example So you can see it in action So the first of all is an initialization step Dijkstra's algorithm Is going to visit all of the nodes So we begin by marking all of the nodes As tentative And we set up distances for them All of the nodes are keyed by their distance The distance of the source From which we want to compute The shortest paths from there Out to everywhere else is set at zero And the distance of all of the other nodes Will initialize it to be some constant That means infinity We don't know how to reach them yet And then we proceed in this main loop This main loop says while there are any nodes Which are tentative, meaning the algorithm Hasn't found them yet how they fit in To the source tree Then what we will do is we'll Extract the node with the lowest Distance that we know We'll then add that node To the source tree We'll be drawing a link from wherever It was used to get its current Distance to the node And then we will We will use the information from that node To relax other costs To lower other costs We do that by taking the cost of the node Looking at the nodes' neighbors And seeing if there is a lower distance Way to reach any of the nodes' neighbors That might sound a little mysterious But let me go through an example And you'll see that this relaxation step Is straightforward Okay, here's an example That I'm going to walk through It's the same topology from before And I've shown it with an initialization phase Where you can see That next to all of the nodes I've written in red Their costs For many nodes, it's infinity For the source node where we're going to start From, it's zero Now I'll proceed through that while loop First step of the while loop The node with the lowest distance That's A where we want to start from And do a relaxation around A So if A now has cost zero You can see I've changed the cost to blue It's locked in Once we visited the node And taken it Then we found the path to that node Of course this is just the source Now I'm going to color nodes that we visit Black And then the relaxation from here It looks at the cost of this node at zero All of its neighbors And sees if it can lower the cost What are its neighbors of A One is B You can see here I've circled B B's cost used to be infinity But B is one link of cost four Away from A which has cost zero Therefore B's cost could be reached By A at cost four That's less than infinity So we're going to lower the cost of B From infinity to four That's one relaxation So B's cost used to be infinity When we didn't know how to get there But now we have an option We can go from A to E directly Over this link of cost 10 So E's cost will be 10 Both of these nodes have been relaxed That's a step in the right direction Next iteration What do we do? We pick the next lowest node That's going to be B with cost four Just circled B So we add B to the shortest path tree From the source tree from A Now B with cost four was reached from A Directly over this link So we add that this link to the shortest path tree Now let's perform a relaxation We'll go around all of the nodes Connected to B And see if we can use the links From B to lower the cost Let's look at C first C's cost used to be infinity But C is a link of cost two Away from B at cost four So C can go down to cost six It got lowered E is A link of cost four Away from B so that can be reached at eight E's cost before used to be 10 So actually E has now been lowered To be cost eight So interestingly E's distance is full and not just from infinity down But it used to be some finite number 10 Now it's gone down to eight So we're finding better paths over time As we go out Further and further away from A Similarly we'll do the relaxation From B When we look at its neighbour F Its cost goes down to seven And G goes down to seven Two. This is great Okay next step What do we do? The next lowest cost Well the lowest cost of the remaining nodes That haven't been visited is C with cost six So we take it I've changed its cost to blue To say it's done We add this link C with cost six could be reached At that cost from B So we add that to the tree that's a new link My coloured C black too To indicate that node is visited Now we do our relaxation around C What's going to happen? Well H's cost is going to fall We have the cost of D can be reached now At eight here So I think D's cost Will fall in two I'm not sure we'll see that I guess Well you have to look at the previous slide Relaxing from C We get That the cost of E Has now gone down to seven Because it can be reached over a link of cost one From C is six when plus six is seven So it's gone down again Well our route to E Is just getting better and better I guess D went down from Well I don't know You can look at the previous slide It's hard work going through these graphs I hope I haven't made too many mistakes That you're going to find Okay so continuing Well it looks like we've done All of the relaxations for C So let's continue on Now we've got to pick the next lowest node There are actually three nodes That have cost seven So any of those will do As the minimum cost to extract We're going to arbitrarily pick G Just to work our way around The graph G could be reached at cost seven from B So we've now added this link here To the shortest path tree Out from A And I've changed the cost Of G in seven to blue And marked the no G in black Let's do the relaxation from G G has one other neighbor So that other neighbor We can reach A link at cost four So the cost to reach F by G Would be eleven Eleven is not bigger than seven So actually that means that Routing to F by G would be a bad move And we don't lower the cost And remember that as a new route So that hasn't changed anything Next moving on We'll do a relaxation Around F So first of all We're taking F as the next lowest node We're going to add The link at which F was reached At cost seven to the shortest path tree That is a link from B It was reached from B at cost seven So we've added this node to the shortest path tree We do the relaxation And we find actually that it doesn't lower Anyone else's cost Everyone else has reached a better way Than going through F I guess Is what that means Continuing Now we get to E So we want to do a relaxation around E So we take E Make its cost in seven Is now in blue We've colored the node black We've added the link E at cost seven was reached via C So we add this line From C To our shortest path tree Now as we do that relaxation I think nothing much changes By the way all of these nodes That are already being visited They're not going to change We've found the lowest cost way to reach them The only node that could potentially change Is this one in red But seven plus two is nine That's bigger than eight Doesn't change Okay going on what's left D Now we'll take that as the next lowest And we will Take this link So relaxation doesn't change anything And finally There's one node left that's eight at cost nine So we add this one And we're done We've now found the source tree From A to all nodes If you just look at all of these blue lines You can see that they started A They go out And they provide a set of paths To reach all other nodes on the graph And these are the least cost paths To reach any of these other nodes We've done it We have a nice methodical procedure For finding this source tree From a given node For a particular topology And that's Dijkstra's algorithm Let me make just a couple of comments Before we wrap up So you might have noticed that Dijkstra's algorithm Finds the shortest paths In order of increasing distance from the source What it's really doing is leveraging This optimality property That for long shortest paths Smaller shortest paths Sub-paths are also shortest paths So we can build up From small paths to large paths And they all overlap That's why it works to Go out at increasing Distance and that ensures that once We've gone out to a certain distance We'll never change your mind later And change any of the paths we've already selected This algorithm Can take a little while to run on a graph topology Actually the efficiency Of running it depends on how you Implement this Extract minimum cost node function Depending on what data structure you use You can use different ones Depending on if your network is Dense in edges or sparse in edges But in any case the running time Is super linear in the size of the network That means as the network grows larger The run time of this algorithm Is going to go even more quickly And eventually for very large networks The run time will get very large It's not surprising really There are so many different little paths That you can easily imagine Some of the complexity here And finally I'll note that it gives us The complete source tree or sync tree Depending on which way you run it This is actually more than we need for Fording each node Just needs to know the next hop For all particular destinations So we have more than we need for Fording and we can use it That's great. To get this of course We need to know the complete topology So that's going to be an issue We'll have to address in routing Now that we know Dijkstra's algorithm I think we can keep moving on And look at other routing algorithms In this segment I'm going to tell you About distance vector routing One of the two main methods Which you use to find routes So we've talked about the notions Of shortest paths and how you can use These paths if you have the topology All in front of you What we're going to see now Is how to compute these same shortest paths But in a distributed network setting As we need to in the internet And we're going to look at what's called The distance vector approach to do so Distance vector is a fairly simple approach To computing routes It was used fairly on in the internet Actually when it was called the ARPANET And also in a protocol that you might have heard of Called RIP Distance vector is one of the two main approaches Towards routing the construction Of routes that is If you want to impress someone I guess you can tell them that technically This is a distributed version Of the Bellman Ford algorithm Maybe they won't impress them, who knows The algorithm itself works fairly well It's correct But it does suffer from very slow convergence behavior After some kinds of link failures And for that reason The kind of algorithms which we use In routes in most Real networks today Are often link state algorithms Which we'll see in a little while These algorithms are a little more involved In terms of the work they do But result in better overall behavior Okay, now here's one thing That I would like to stress Because I think it's very interesting For our routing protocols We had looked at a centralized scheme Where you run Dijkstra if you know the whole topology That's not how networks work at all You need to compute routes in a distributed setting What is a distributed setting Well, I'm glad you asked It's really very different than the centralized setting Where we have the whole network in front of us In fact, if you're a node in this setting All you know is your neighbors And maybe the cost to reach your neighbors So you just have local knowledge You don't know the overall topology at all In terms of finding out things And deciding things, you can only talk To your neighbors using messages You can't send messages magically You can only gossip and exchange messages With your immediate neighbors It's also the case That all nodes run the same algorithm concurrently There's no special leader or boss Or centralized place that's in control of it Every node is equal And yet amongst themselves Somehow they all need to decide On compatible routes And just to make things a little more challenging Nodes and links can fail And messages can be lost Actually, so it's not just the links That can fail and messages that can be lost But nodes themselves can go down and fail And that's going to be a little tricky Because you might have been talking to a node A while ago and now it's gone away And yet we still want to be able to find correct routes How do we do this? Well, distance vector is one approach And here's how it works just in one slide And then we'll go through an example Now in the distance vector algorithm Each node maintains a vector of distances Let me just underline that As well as next hops To all destinations This is the distance vector And that's the heart of the algorithm What you're going to do is compute the best distance vector And keep that best distance vector over time So you start by initializing Your distance vector with zero For yourself as a destination Because you're already there, congratulations And infinity to everywhere else You don't know anything else And then this algorithm All you do, and this is a simple repeated step Is you exchange every node Since its distance vector The one it currently has to all of its other neighbors You just, you keep doing this And then as you receive From your other neighbors The new distance vectors periodically You update your own distance vector And you update your own distance vector To choose the best path And that's going to be the Since we're after shortest paths The lowest distance to each destination That you've heard When you correct of course Your neighbor that you've just gone across That's the one extra link From the distance vector information they gave you And you're going to pick the best route And then you'll use it for 40 Okay, that's the distance vector algorithm It's a little bit of a mouthful If you're not used to these kinds of algorithms So let's see an example of how it works in practice So here's a simple network I'm just going to look at this basic network With four nodes, A, B, C and D And just a few links here You can see I put the costs On all of the different links And every node In this network is going to run its own Its own instance of the distance vector algorithm And keep its own distance vector And exchange messages with hosts Here, with its neighbors, excuse me Here is the view Of just the distance vector that A has At the beginning of time So A says, well, I can reach A with cost zero Great, I'm already here B, C and D, they're the other nodes in the network They're the same And you note here that A can only talk To nodes B and D directly Can't reach C directly So what happens? Well, what's going to happen Is that A Is going to send its distance vector To the other nodes B and D Now B and D and all other nodes Are of course going to be sending their distance vectors To all of the other links So A is going to be receiving two distance vectors One from B and one from D And I put them here in this table The distance vector Tells us information to all of the different destinations A, B, C and D And we can see what B says B can just reach B And everything else is infinity And D can just reach D Now A needs to choose the best entries After correcting for the local link costs So for B We really want to look at B plus 3 Because 3 is the cost to go over the link From B to A To A, that's the special case We already had 0 For everyone else So to B What did we find? Here was the lowest It's just cost 3 Going directly via B To C We want to choose the lowest number As we go across So what do we have? Well, A actually To A, that's the special case Going directly via B To C, we don't have any lowest cost It's still an infinity And to D, we have 7 So that's going to go over here And then we can see here is the distance vector That A has learned after the first iteration And it will have in fact found the best One hop routes which are possible in this network And all you can do with one hop Is just reach B and D directly So this is what A is going to do A is really here learning the minimum Of B plus 3 For a special case of reaching itself At cost 0, because it knows its own identity Of course This is the same process As you're going on, not simply at node A But everywhere else So wow, this looks a little more complicated But let's just imagine for a moment What's going on elsewhere Now here This table here shows us all of the distance vectors That B, C and D Exchange with their neighbors We worked out what happened today We copied it over here B is going to learn the minimum Of A plus 3 As it comes in here C plus 6 As we come in on the link on the right And D plus 3 is becoming those things And I've written that there I could also tell you that C C is going to be equal to The minimum Of, let's see, C is connected To B Over a link with cost 6 and to D over a link with cost 2 So that would be what you would want to use To compute the routes for C So if we follow this same process And you can check this Hopefully I've got all of the numbers right Then you can compute the first The one hop best routes That B, C and D learn Well this process doesn't end Actually it's quite complicated Thinking just trying to keep in your head What's going on in all of these nodes The second exchange Here are the distance vectors That are going to be advertised These are simply the best ones Which were learned at the end of the first exchange So they're going to be sent out And we will then Every node will go through exactly the same process And here you'll end up finding The best two hop routes After the second exchange Well what's A going to learn Remember we said that A Is equal to the minimum And D plus 7 Let's look here So we really want these ones Plus 3 And these ones plus 7 What's going to be the minimum here Well to A of course is the special case of 0 To B Let's see, well 0 plus 3 is 3 That's lower than 10 So we're going to learn a route to Well I guess we already had that We're still like that I've coloured in pink here the ones that changed We've got C To C by B is cost 6 Plus 3 is 9 To D To C by D is cost 2 Plus 7 Is the cost of that link So A now actually knows two routes To reach C at cost 9 So we'll choose simply one of them Let's say it's arbitrarily here chosen D by D To reach C Similarly if we look down here 6 and 7 and 0 is 7 So we find that A can actually reach D at cost 6 by B It's learned a better to hop route That is this route to get to D We've now learned that that is shorter Cost 6 instead of this route That A was using after the first exchange Well this process continues I'm going to leave you to Check some of it at home What we will find out is that We're now finding the best 3 hop routes For the better A here is reaching C Via B at cost 8 So that's actually going to be like this Is the shortest route Looks like we're actually using this In two directions C is seen to A by D So it's going to go like this too So we found that is the best 3 hop route Well after that If you go through and check all of this table You should find that there are no shorter 4 hop routes Because the diameter of this network There are no longer paths So we've converged now And all subsequent exchanges should send the same information Until there's a failure that is And then the routes may change So in distance vector You should imagine that In the dynamics here In terms of adding routes News about new possible routes Is being added in 1 hop Per exchange Every exchange we were finding information about routes Which were 1 hop longer We haven't yet got to when you remove routes But I'll tell you when you remove routes What happens is that A node fails So actually it doesn't send a message saying You can no longer use any of my routes What happens instead is that other nodes Need to forget and time out the information Over time if it's not Reiterated There are problems though with distance vector Remember we said some convergence Issues can arise Particularly with something that's called partitions Partition is when you divide a network Into two different portions So that you can't get from one side to the other side If this happens Because say a key link breaks This is why you actually want more than one key link In network so there's a little bit of reliability You get a convergence problem You get what's called the count to infinity scenario Here's that scenario So I've shown on the left The desired behavior This is a simple chain and we're looking at how information From the destination A propagates You can see here good news Reaching A, news travels quickly After one hop B knows you can reach it Node 1, it's down here After two hops C knows you can reach A across two and similarly As we're going down and down and down this table What about when there's a failure Here on the right hand side And A can no longer tell people how it can be Reached Well initially we'd found out all of these Good routes and now there's a failure What's going to happen Actually if you look at B B will now get that announcement Not from A because A can no longer reach it But from C, C will say well I can Reach A it costs two because that's what it could So B will now say Okay well I can reach A it costs three Because that is The C's distance plus one to go over that link Well You can imagine what might happen here In the next iteration C Is learning how to get to A from B C's going to raise its cost to four Uh oh That will cause B to raise its cost To five and D to raise Its cost to five in the next round And subsequently C Is going to have to raise its cost to six Oh because they depend on one another And you can see that something really screwy Is going on here This is called a count to infinity scenario Because the network is really exploring Ever longer routes in a vain attempt To try and reach a destination which is Not reachable For desirable convergence behavior Because it means that for a long time The routes in the network can be in flux Now you might think that my example Was a little contrived because C shouldn't be fooled so easily C knew that it was getting to Uh sorry B shouldn't be fooled So easily because B knew That it was normally getting to A directly And it was in fact telling C The best route to use so B Shouldn't really decide to go via C And then just add one to the cost However these same effects Arise in larger Uh cycles In longer paths and other networks Even when you're not talking to one another directly Cycles of three nodes and so forth So they're uh They're very involved In these networks and they're quite hard to get rid of There are various heuristics They have colorful names here like split horizon And poison reverse just means You know B Don't suddenly start using information from C If you told C how to actually get to A But these heuristics turn out not to be very effective In practice They get complicated and they don't really solve the problem In nearly all of the cases For that reason link state algorithms Are more favored in practice And we'll look at link state protocols In the next segment One exception is that distance vector Is really very lightweight and all you're doing Is keeping this distance vector and propagating No complicated graph algorithm This distance vector When you're very resource constrained Might be one exception Okay so distance vector Is the technique Distance vector is the technique which is used In a protocol called RIP It's one of the more famous distance vector protocols It uses hop counters A metric so we're simply counting The number of hops routers we go through And we use infinity as 16 hops Just to this limits the network size But also It stops us exploring ever longer routes In case of some of these weird things It also includes these heuristics For split horizon and poison reverse RIP is actually quite An old protocol now You're unlikely to use it in practice So you might look at it just to understand How some of these protocols worked There's an old IRFC you could look at It's quite dated now But it's a nice small IRFC You can read the whole thing and understand the protocol You get all of the details like the 30 second timers For sending these distance vectors It's run on top of UDP Information times out if a node goes away After 180 seconds As a way of detecting failure So there can be a failure Once there's a failure it can be a long time Before the network responds and fixes routes This is not so good these days But And this is why we run faster And better routing protocols these days But nonetheless it's an interesting protocol to look at Okay you know about distance vector G'day viewers In this segment we'll talk about flooding A useful primitive for routing So flooding Is a mechanism to broadcast A copy of a message from one node To all other nodes in the network It's called flooding Because it really works By making sure that the message appears everywhere It's flood throughout the entire network Just like water going everywhere This makes sure it'll be received by everyone It's a simple mechanism But somewhat inefficient such that You wouldn't want to use it Regularly a lot of the time So Here is the rule for flooding Now I'll remind you that this is a distributed setting So all nodes are executing This rule in parallel concurrently Right and none of them know The overall topology of the network The rule for flooding is very simple That's its virtue Every node When you Receive an incoming message Which is meant to be flood to the network You simply send it out on all of your other links So it will reach all of your other neighbors Except where it came from Great And there's one condition here Just to make sure that we don't keep sending Messages around and around in circles You need to remember the message That you've flooded in some way So that if you see it again Because it arrived at another path And keep it going around the network Flooding is inefficient Because one node Can receive multiple copies of the message Along different network paths And really It only needed one copy of the message To see it, the copies that come along the other Network paths are wasted in some sense So let's go through an example Just to see how flooding works Same topologies before For our examples We're going to flood from A I've shown the node that is busy Doing the forwarding of messages It starts at A I've labeled A in red A is going to flood the message By sending it to its neighbors So it will send to B Via A, B and E Via A, E And I've shown both of those Floods In blue, so you can see that the message Is propagated to the other nodes And is used some of the links What happens next? So our message reached Both B and E So let me just circle the nodes which were reached Both of these nodes should now flood Let's look at B B received the message from A So flooding means it should send it On all of the other links So it's going to send it to C It's going to send it to E In this way It's going to send it up to F And it's going to send it to G Similarly E is going to flood By sending it to all of its neighbors So it will send it down here to D It will send it down to C It will send it back to B And it will send it to F So you can see this message Is really getting copied around the network So F here has received Two copies of it One from B and one from E It only wanted one but it's got two And B and E Actually happened to do their flooding At the same time So both of them have sent each other The same message So it's crossed the link between them In both directions This is what flooding can do It'll really make sure the message gets everywhere What next? Well we've gone through A, B and E The other nodes which Received the message most recently And haven't yet flooded it Were C, D, F And G They all need to do their flood Let's have C do the flood C received two copies of the message One from B and one from E So it's going to send it to the other Nodes It's H and D here D Received the message from E So it can send it to its other neighbor That's C down here So you can see the messages crossed C and D two times Now F Is going to flood F's actually received a copy of the message On two links from B and E So all F has to do is send Down to G And G similarly received it from B It can send up to F So F in fact You'll see here Is very fortunate or popular It's getting another copy of the message So F has received a copy of this message On two links and it's sent it out once And finally We've reached H H has no one left to flood Because it's at a dead end And we're done with the flooding algorithm You can see here That the algorithm was fairly simple And it caused the message to be carried On each link at least once Sorry Each link in at least one Direction is maybe a better way to say that So for a given link Both directions are only one These pink arrows show you what happened This is inefficient Because really to reach nodes like F We didn't need to send it along all of these links We could have omitted many Of these messages and we would have Still broadcast the message Effectively So there are a couple more details I could tell you about flooding Just to complete the algorithm I said one of the keys here is to remember the message So that you can stop the flood eventually Well we only considered one message This would be harder if many different nodes Were using flooding What is typically done is instead of Literally memorizing the whole message You will, for each source Associate a sequence number And put sequence numbers in the message That way we might remember that A Last flood a message with sequence number Seven If you ever see a message from A Whose sequence number is seven or lower You know that you've already flooded If you see a message from A with a higher sequence number You assume it's new Flooded and then update your sequence number And the flooding we saw was also unreliable If you want to make flooding reliable You can simply use the ARQ mechanism we saw So when we flood And one node sends it to a neighbor The neighbor can acknowledge that flood And if the node doesn't receive the acknowledgement Then it can resend The flood message At a later time by using a timeout This will make sure that we reliably Send the information and reliably broadcast it To all of the nodes in the network So now you know about flooding Flooding is fairly simple It's a little inefficient but it's a good Building block or foundation on which to build Other more efficient protocols G'day viewers In this segment we'll talk about the Link state approach to routing So our topic is really computing This shortest path that we've talked about Previously in a distributed setting That corresponds to a network We've looked at distance vector routing Now we'll look at link state A very different approach One in which there are a couple of phases First everyone floods the information And then we compute the routes So it's interesting to compare Link state routing with the distance Vector approach that we've seen Because they operate quite differently The distance vector approach Spread the work of computing the routes Across all of the nodes of the network In link state we give Everyone a copy of the topology And let everyone compute Their own routes so we're really replicating A lot of work in some ways As opposed to having everyone work Cooperatively as in distance vector So link state is actually a little Closer to that old view Of giving everyone a map of the network And then letting them work out their own routes Now link state routing Is widely used in practice It's been around for a long time Almost as long as distance vector It's been used in the ARPANET Since about what's it say here in 1979 Onwards And many modern networks today Use protocols That are based on the link state approach Here I mention OSPF and ISIS Which we'll just mention Very briefly at the end But these are protocols that would be used In ISP networks, large enterprise networks Like on campus or in a big company They all use this link state approach Before I dive into the details Of the link state approach Let me just remind you of the setting we're working in This is the same as the setting for distance vector It's really our distributed setting Which makes routing more complicated Than simply looking at a picture And being able to centrally compute things Or remind you briefly So in this setting The nodes only know about who they're connected to Their neighbors and their costs to the neighbors They don't apriori when they're turned on Know the whole topology They can only talk to their neighbors Using messages to find out what's going on For the network at large So they have no other way to gain information About the network All of the nodes are running The same algorithm concurrently None of the nodes are special So there's no centralized controller They're just going to have to agree on monks themselves On what's going on And they operate in parallel And they coordinate their actions And finally, since this is routing We would like to be able to deal with Fail components So some of the nodes and links may fail And we would like the remaining portion Of the network that's working To correctly find routes Messages may also be lost So that's the setting What about the link state algorithm Here's how it works There are two phases In the first phase It floods information about It's local portion of the topology To everyone else using what's called Link state packets In this way every node Will get a picture of the full topology So we do this whenever the topology Changes or when we start And then when everyone has The full topology Will move from step one to step two Each node is simply going to Compute its own routes And forwarding table The first step here uses flooding Which we've looked at previously And the second step uses Dijkstra's algorithm Which we've also looked at previously Link state really just combines these two steps And that's how it works I'll go into just a little more detail So the first phase Is flooding to disseminate the topology Each node Is going to flood what is called A link state packet that describes Their portion of the topology So I've shown the link state packet For node E Here And you can see from node E If I just look at node E Its portion of the topology includes a link To D Actually let me go through it in order It includes a link to A Which I'm drawing over here With cost 10 Then a link to B With cost 4 And you can see in the Link state packet The connectivity from node E So we can see there's a link here to A At cost 10, B at cost 4 And similarly there's C here D trace over And then E well There's no connection to E because that's where we are And there is a connection to F All of those are listed in this vector With the appropriate cost That is the link state packet That's what node E will flood out And every other node will do similarly For its portion of the topology Well once that phase 1 is completed Every node will have received every other node's Link state packet By putting them together they'll have a picture of the Complete topology Phase 2 is to compute the roots All we do is have every node run Dijkstra's algorithm So there's some replicated computation here The nodes are looking for the source trees From themselves out And so that can be different in different parts of the topology Although there's definitely some overlap here Once we find the Source tree in the node We'll be able to compile the forwarding table From it directly That sort of tells us all we need to know And that's it Let's look in just a little more detail to get comfortable With that Here at node E again I've shown the source tree That is the result of running Dijkstra's algorithm So node E will gain this picture And gain this source tree By itself by going through these steps And it will then know which way to go To reach all of the nodes What I've done now From this source tree All of the different lines here have arrows Which show the path to take For instance, to get from A To Sorry, from E to A I follow this path through the network Through here and over here Through E, C, B, A What I can do now Is simply compile it Into a forwarding table The forwarding table lists for every destination The next step So for instance, to get to A The next step is simply to forward to C And that's all E needs to know C will then take care of the packet from then on And similarly for all of the other destinations That's our forwarding table And if that's all that's going on in the network We're done But of course, the whole purpose Of routing protocols Is to be able to adapt to changes So when there's any change in the topology Because a component is failed Or maybe because a new router or link has been added We want to Redo some of this process Go through the phases again So you'll flood any updated versions Of the link state packets And recompute the routes Let's look at an example here Of just what would happen What is going to happen when there's a failure Is that the nodes that are adjacent To the failed link or node Notice that something's changed They'll be able to update Send updated information And everyone who receives it will be able to recompute So you can see here A failed node G It's gone, I don't know, it blew up What will happen? Eventually its neighbors B and F Should realize that it's gone They'll need to be exchanging some sort of regular Hello message to make sure that it's alive But eventually when there's no answer They'll notice that it's gone Now at this stage they can issue Updated link state packets In their link state packets I've listed the same neighbors as before But you can see I've changed the cost From both those nodes to reach G To be infinity Meaning this link does not work The cost is infinite so don't take it When that information is spread Around the other nodes will recompute And they'll work out paths which do not Go through G Now if you think about it Notice that there's a subtle difference Between a link failure and a node failure When there is a link failure Then both of the nodes that are adjacent To the connect to the link Will notice that the link no longer carries Packets so they'll both send Updated link state packets Saying the cost of that link is infinity And therefore the link will be Removed from the topology effectively When nodes calculate their links Now imagine though That there's a node failure That's kind of interesting Well all of the neighbors of that node Will notice that they can no longer talk To it over the link So there's something wrong with the link To the node Actually these neighbors don't know Whether it's their link to the node That's failed or the node that's failed Both of these cases look the same In any case All of the neighbors of the failed node Will notice that something's gone wrong And they'll be able to issue That node anymore The node that's failed however Won't issue a new link state packet I mean it's failed that can hardly send A message saying hi you know I'm sorry I failed because it's no longer there And it's very unlikely we could count on it To issue something saying I'm going to fail That's just not the way failures work However It's okay here Because since all of the neighbors send Messages saying they can no longer get to that node The shortest path computation Will effectively remove paths Which go through the node Even though that node didn't send an update itself Saying that it's links had got A change to cost infinity It's interesting if you think about it And just for the sake of completeness Let me mention that there are other changes For instance you might add New links or nodes to the topology In this case The nodes that have the new links Or the new nodes will send Updated link state packets And some will learn of extra bits of the topology And they'll use some of those new Links and nodes as they Recompute the shortest paths Really here additions are the easy case It's failures where someone fails And can no longer tell everyone they fail Which are the tricky case But we want routing to be able to adapt To either one of course Now to be fair I also want to tell you that There are complications in link state protocols I'm making it sound kind of easy But when you're describing the normal operation The normal cases They work as I've described them But when you design a protocol You want it to be correct and work Pretty much no matter what happens And there are some bizarre cases That we could come up with And I've made up some here Now As part of flooding You have a sequence number on the flood So that we can stop the flood And only flood new information That reaches its maximum We could make that maximum very high But then what's going to happen If the sequence number somehow gets corrupted To a very high number And gets close to the maximum This seems very unlikely But the point is we don't want the network To be jammed up permanently if this happens Another case Would be that a node might crash And when it comes back up It's forgotten what sequence number it was using before It can't just start at zero again Other nodes might know higher sequence numbers For its messages that are flood And so they won't listen to the low numbered Sequence messages Or other bizarre cases The network could partition itself It could divide into two components Due to failures Both of these components could evolve independently And then when the network connects itself again You know, each side Could think the other portion of the network Is in a different state and we would need to fix that Wow, this is a little messy Really a lot of the complexity Of real protocols has to do with handling These corner cases So that things work well in the common case But they are correct Even in these weird cases I'm not going to go into these complications In any detail at all I just want to point out to you That it's important that real protocols handle them You can read a little bit more about them In your text I'll tell you one strategy that's used And that is aging So one strategy that's used Is that we include a time stamp On all of our link state packets And most information that goes around Networks If this information is not refreshed over time Because whatever created it has gone away Then we forget the old information This tends to remove Old Information which is no longer relevant From our network and lets the network get on And adapt to the real situation That we're now faced with Used in link state protocols But it's also a general useful strategy Okay What else about link state One thing we've reached now Now that we've gone over it Is we can compare it briefly with distance vector This is useful just to see Some of the differences between the two Here's a table that lists our goals For routing protocols from long ago And we'll see how the two stack up Now for correctness We wanted to be able to calculate Even in this distributed environment The two approaches Used different algorithms Link states based on a diextra With some replication Distance vector is based on A version of the Bellman Ford algorithm Which has been distributed Different approaches but they're both work In terms of efficient and fair paths We're using our Shortest path framework Where we assign costs to links for both It's the same in both Well where they differ a little bit Is in these last two entries Convergence we would like rapid convergence To the new routes after any kind of change To the topology like a failure We've seen That distance vector can be slow In some cases it can have this count To infinity and require many exchanges Whereas link state generally Tends to provide fast convergence All you have to do Is flood the new topology and everyone Recomputes so it wins here In terms of scalability however The trade off is the other way around Distance vector really has Excellent scalability in terms of Storage and computation at a node Because it does the minimum We just have the lists of nodes The computation is really adding Numbers and comparing them You can't beat it Link state on the other hand Has more computation The amount of computing we need to do And storage to store the whole graph Is super linear with the network So it increases more rapidly Than the size of the network So distance vector actually wins In terms of scalability here It's an interesting trade off Okay and finally I'll just mention a couple of real protocols Which use the link state approach And they are ISIS Intermediate system to intermediate system And OSPF open shortest path first OSPF is really the IETF or internet version Of the ISIS protocol Which had its roots More on the OSIS side of the house These are Modern link state protocols They're very widely used In ISPs and large enterprises They have supplanted distance vector protocols Because they have different Better convergence behaviour Even though they require a little more computation While computation's gotten cheaper over time The basic operation Is as I've described it So you know the heart of how they work With the link state protocol I'll also tell you they have many more features That are added There are notions for instance Of different kind of regions So that will help to scale the protocol To larger networks Or stub areas So that it's easy to compute Roots for stub areas you just need to Go out, you don't need to worry about Doing a lot of shortest path computation Don't worry too much about these features Or any real protocol I'm just mentioning them so you have some sense But you know how these protocols work And now you have a sense Of the link state approach to routing Good day viewers In this segment we'll talk about equal cost multi-path routing That's a mouthful But it's really an extension To the shortest path routes we've seen before What we would like to do now Is to allow The use of multiple routes Between a given node A destination In everything we've seen so far With the shortest path formulation We picked a single path from a node to a destination But what if you want to allow multiple paths For instance in this network To get from A to E you can see I could take This path here Or there's another path through the topology Which actually turned out to be a shortest path Before I could allow both of these to be used at the same time That's what we're going to look at The general name for this Procedure is multi-path routing The use of multiple paths Now These multiple paths usually exist In the topology already And the reason for that is you want to provide Enough links in your network topology For redundancy in case one link fails You want to be able to have a different link To reach a destination So there probably were multiple paths somehow We would just like to be able To use them both at the same time During forwarding The reason for this is simply to Improve performance Maybe we can fit more traffic through the network If we can use these multiple paths What we're going to look at now Is really a simple extension to our framework So far to incorporate multiple paths It's fairly straightforward There are really two questions we need to answer How do we find these multiple paths As opposed to finding a single path We did before And when we have them How do we use them for forwarding The second question is about forwarding Given that we have multiple paths How do we use them at the same time To send traffic So let's go through These questions And we'll do it in the context Of equal cost multipath routing This is really one form of Multipath routing Which is an extension of our shortest path model All we do here The extension really is to keep a set Of next hops and routes If there are ties Previously we just chose one randomly When the costs happened to be the same That was one that was not a unique Minimum cost So here's our picture of the network again Just to illustrate that And I've changed a few of the costs here In red Now we're going to have some Paths, multiple paths Which have the same minimum cost So you can see them in this graph I've sketched them And just compute them to make sure that they're okay The path A, B, E Is one way to get from A to E That has cost 8 Okay Well there's also another path And that is the path A, B A, B, C, E That has cost 4 Plus 2 Plus 2 is 8 And there's even another path Which goes A, B, C, D, E That Is more hops But it happens that the cost of these hops Is lower and so when you add it up Guess what you get again, 8 All of these paths are the minimum path And in our equal cost multi path Formulation we'd like to use them all Now Equal cost multi path Since it generalizes Shortest path routing and actually changes Our notion of a source tree And a sync tree With ECMP These source and sync trees They're actually not trees anymore They become a slightly more general structure Called a DAG Which stands for a directed acyclic graph Now In a normal tree We have a structure like this on the left And you can see just a classic hierarchical Tree there Every To get to a particular destination One next hop In a DAG However You can see I've added some of these cross links Every node can have a set of next hops That it can use to reach a destination So for instance There are two paths through here From the source to the one destination So that means From the root I could go Either of two different ways And I would still be able to arrive At this same particular node down at the bottom It's a DAG It's acyclic So there are no cycles or loops in this topology As you follow paths through here You'll definitely get to a destination Without going round and round in loops So we haven't admitted loops There's also still a compact representation For routing Each node now has not a single next hop But a set of next hops To reach a destination But we don't need to have nodes Store the entire path or anything like that So here's a little bit of an example Here's our graph again Now we'd like to find the source tree Or really DAG for E The procedure that we go through Is simply dykstra But keep all of the tires Instead of randomly picking one And then once we've got this tree We'll be able to compile it into a forwarding table I'm not going to show you here But you'll find that as well as dykstra There's also a straightforward extension For distance vector Using one minimum cost route You can keep multiple of the minimum cost routes The set of neighbors If you like Okay, let's see that source tree for E Well, let's see I'm going to start going out with minimum cost From E we can reach D here Now at distance 2 You can get to F We can get to C Now interestingly This is where things have been added I can get to C in two different ways The direct route here And by D, still cost 2 And we can then go on Adding other Paths through the network So for instance to get to Well to get to H Well let me do B first You can get to B here But you can also get To B Along this path They both have cost 4 And similarly A along here H along here And F along here None of this has changed And this is the shortest path Sorry, the source tree Which is really a directed acyclic graph If I just flip ahead You'll see now hopefully they were actually the same as what I drew That there are two new Lines here that really got added With the ECMP case I'm just tracing over them We can now compile The source tree is before But a slight generalization of it You can verify that for yourself We can now compile this into a forwarding table It's the same procedure as before Just mapping from a tree Down to all we need to do Is remember the next hops But you'll notice here That to get to certain destinations I have a choice of next hops One of the biggest ones is To get from E to A I can go many different ways I could go this way These are the examples I sketched before I could go this way Or I could go this way Three different paths All of minimum cost 8 That means from E I could choose Any of B, C or D As the next hop And you can see that in the table Now instead of one entry We have multiple entries And you can go through the rest of the table And you can see that I've colored in pink They have sets Instead of the single next hop That's it for the routing What about the forwarding We like to forward with these Equal cost multi paths One way you could do this Is when you have a packet You only want to send the packet Down to one neighbor Otherwise we'll be making copies of it You could simply choose at random For every packet Which of the next hops to use That's this option here That's actually very effective in terms of balancing Traffic across all of the different paths However, it adds jitter Now what I mean by this Is that the different nodes Going from a given source To a given destination Might experience quite different delays Through the network For instance, maybe if you send packets One, two, three, four At a particular node One and three and four Will take a certain choice Which is a shorter path physically And in terms of seconds I mean the cost is going to be the same Whereas path two might randomly Be chosen to take a different next hop Which will be a more secure route Which will take longer So we might send packets one, two, three, four But they might be received at the destination One, three, four Because they took the short path And a long time later packet two Will arrive At the destination So we would like to avoid these kind of effects So instead What we'll try to do Is send packets from a given source destination Pair on the same path This is um Imagine if you've got a video conference It's between a particular It's a set of traffic or a flow This is sometimes called Traffic between a particular source Destination pair Often for a particular purpose We would like to send the traffic From a given flow along the same path Through the network This way the ordering of packets Should be preserved We shouldn't get any of this wild jitter So all we do to handle this Is we make the choice not at random per packet But we map a flow To a single next hop How do we do this Well here's an example I've shown the paths here Just a segment of the paths From f to h We have different paths through the network We might go this way Or we might go this way This also includes By the way the paths from e to h We can take those different choices And the paths from f to c And the paths from e to c As well as e to h Well I said one twice there But you can see that there are four different Source destination pairs I've listed them here as flows Traffic from f to h and f to c As well as e to h and e to c Now for all of these different flows As they go through e They could be seen Either to c or d Instead of choosing at random We'll simply make this set of choices For the packets that come from f We'll send them to d And for the packets that come from e When they're going to h or c We'll send them to c as a next hop In this way we have some consistency For the flows But if we think about Traffic that's heading towards c We're actually using both of the next Hops, we're using d And c So traffic towards those destinations Is utilizing multiple different paths Through the network in parallel And that's how we forward With ECMP Now you know this slight generalization Of the shortest paths we've seen before Good day viewers. In this short segment We'll talk about how hosts and routers Are combined in the internet For the purpose of routing Now this topic is really just to Provide a little bit of a bridge Because we've talked about routing and nodes But we've also talked about forwarding And said that there is a distinction Between hosts and routers Routers, routers and hosts don't And we would like to glue them together Into a network Just to recap that slightly As I told you before In the internet Hosts on the same network Have IP addresses that come from the same prefix We do this in order to be able To scale routing And assign addresses And the way hosts handle the issue of routing Is that they send any traffic That is not for a local host That has to go off the network They just send it to the nearest router They don't need to know what the router does with it Their rule is simply if you don't know The local network, send it to the router Routers on the other hand Have to talk to one another And discover the routes to use To get packets to every address in the internet And the way they do this And implement this Is that they use a longest prefix Max longest prefix Matching algorithm On their forwarding table To decide what next hop To send a packet to based on their address Okay, so let's try And put these pieces together Here is how hosts and routers Would be combined in a network Now the networks I've drawn Have pictures here like a Router, here's a router A And that router has links That connect it to the rest of the network That's fine, that's mostly What we've seen with our pictures of graphs The dots represent all of the Different routers which are doing the routing But we also have hosts in these Networks, so where do they fit Well the hosts are attached to the routers Now often there is like A switch, a LAN switch here So that we can attach multiple different Hosts to the same LAN As far as the router is concerned All of these hosts are reachable Over that one wire or wireless link And even though there are Multiple hosts here, it's really a Single network, a single prefix That they're all representing Whether it's one host or meaning They're all on the same prefix Let's draw that as the topology This is the situation I have All of these other nodes before A and B and E Really are what we saw In the other diagrams, here's maybe a portion Of it, E and B go off to the rest Of the network, but what we do To add the hosts is we add Them by adding a link from a router Towards one prefix Which represents all of the different hosts And that way We've connected the host to our network Now what do we do? Well, now all we do is proceed With the routing algorithms exactly As I've described, and they all just Work. The routers What they're going to do, now that they're Connected to this prefix to represent The hosts, is they will advertise The IP prefixes for the hosts It will just go out instead Of a single node address, it's a prefix This fits, by the way With the way they advertise their own addresses A router address An individual address is really like a Slash 32 prefix, it's most Specific, it's a block of addresses With one address in it When they do this All of the routers will be able To find a path to all of the different prefixes That have been sent around And this will allow them to find a path To all of the different hosts, great The hosts are also able To fit into this equation because They have this simple routing rule That says essentially they don't Rout, if it's not for someone on the local Network where they can reach directly They simply send to the router And the router knows the route To all of the other hosts in the network And we're done, this is really Just a little bit of glue So that you can be clear on how we plug Our routing algorithms together with the Host forwarding behaviors we've seen In IP Good day viewers, in this short segment We'll talk about how hosts and routers Are combined in the internet for the Purpose of routing Now this topic is really just to Provide a little bit of a bridge Because we've talked about routing and nodes But we've also talked about forwarding And said that there is a distinction Between hosts and routers Routers, routers and hosts don't And we would like to glue them together Into a network Just to recap that slightly And remind you what's going on Here's what I've told you before In the internet, hosts Are addresses that come from the same prefix We do this in order to be able to Scale routing and assign addresses And the way hosts handle The issue of routing Is that they send any traffic That is not for a local host That has to go off the network They just send it to the nearest router They don't need to know what the router does with it Their rule is simply if you don't know If it's not on the local network Send it to the router Routers on the other hand Are the routes to use to get packets To every address in the internet And the way they do this And implement this Is that they use a longest prefix Longest prefix Matching algorithm On their forwarding table To decide what next hop To send a packet to based on their address Okay, so let's try And put these pieces together Here is how hosts and routers Would be combined in a network Now the networks I've drawn have Pictures here like a router Here's a router A And that router has links That connect it to the rest of the network That's fine, that's mostly what We've seen with our pictures of graphs The dots represent all of the different routers Which are doing the routing But we also have hosts in these networks So where do they fit Well, the hosts are attached to the routers Now often there is like A switch, a LAN switch here That can attach multiple different hosts To the same LAN As far as the router is concerned All of these hosts are reachable Over that one wire or wireless link And even though there are multiple hosts here It's really a single network A single prefix that they're all representing Whether it's one host or many They're all on the same prefix So if I just draw that as the topology This is the situation I have All of these other nodes before A and B and E Really are What we saw in the other diagrams Here's maybe a portion of it E and B go off to the rest of the network But what we do to add the hosts Is we add them by adding A link from a router Towards one prefix Which represents all of the different hosts And that way we've connected The host to our network Now what do we do Well now all we do is proceed With the routing algorithms exactly As I've described And they all just work The routers, what they're going to do Now that they're connected to this prefix To represent the hosts Is they will advertise the IPP Prefixes for the hosts It will just go out instead of A single node address, it's a prefix This fits by the way With the way they advertise their own addresses A router address An individual address is really like a Slash 32 prefix With one address in it When they do this All of the routers will be able to Find a path to all of the different Prefixes that have been sent around And this will allow them to find a path To all of the different hosts, great The hosts are also able To fit into this equation Because they have this simple routing rule That says essentially they don't route If it's not for someone On the local network where they can reach directly They simply send to the router And the router knows the route To all of the other hosts in the network And we're done This is really just a little bit of glue So that you can be clear on how we plug Our routing algorithms together with the Host forwarding behaviors we've seen In IP Good day viewers, in this segment We'll talk about hierarchical routing So our topic here Is really how to scale routing To very large networks And the technique we're going to use is hierarchy Where we route not to an individual node But to a large Region of the network So before we get into that I'd like to give you a little bit of motivation Here's a slide you've seen before About internet growth We're growing very rapidly There are now more than a billion internet hosts And growing And of course The previous slide was just the number Of internet hosts This slide shows the growth Routing tables Which are the tables which are maintained In routers to be able to forward packets To all directions This table is also growing very rapidly You can see pretty much exponential growth And just looking At the axis Right now As of about 2013 The number of IP prefixes In a router in the middle of the internet That's got to be able to reach everywhere Is around 450,000 That's a lot The impact of all of this routing growth Is bad In pretty much every dimension you look at You might look at the size of the forwarding tables That need to be kept in memory That's growing, that's the one that's reached 450,000 That means Both are larger tables So more memory in routers And it could potentially mean an increase In look up time depending how it's done As well as the size Of the forwarding table itself Another concern is the number of routing messages Which need to be sent around As there are more places and addresses to reach The number of routing messages continues to grow And it can actually grow very quickly Because not only are there more locations But we need to be able to inform Every node about What's going on in terms of paths To reach every other node So there's a lot Of growth there And finally The routing computation itself grows If every node gets to learn enough About a topology to be able to compute roots The computation Over this graph grows faster Than the size of the network It's super linear in terms of the amount of work That needs to be done So this is all bad, routing growth Is going to stress the network We would like to come up with techniques To scale routing So that it can more gracefully Handle a large network What are those techniques I'm glad you asked because I've written them down here In fact, we've seen some of them The first technique here Is the use of IP prefixes Where we don't have an entry In the table for every individual host Rather we have an entry for A block of hosts called an IP prefix We've seen how IP prefixes work In this segment We're going to talk about network hierarchy Which is the routing to the different Regions of the network And then in our future segment We'll talk about IP prefix aggregation Which essentially Are more games you can play To join or split prefixes That use hierarchy in different ways We'll see that later So let's look at hierarchical routing That's our focus here In a little more detail And find out what it actually is So the overall goal here Is to introduce some kind of Larger routing unit And be able to structure tables And packets towards that unit We've already seen That we now have IP prefixes Which are groups of hosts That's a larger routing unit from an individual host That's great, we want to build on that And we'll build on that By introducing the notion Of a region of the network This might be a complete ISP network For instance But I'll just call it a region for now And we would like to change our routing procedure So that we route To the region And then when we've arrived at the region We route to the particular node within the region This is really no different Than to pick a real world example Navigating by driving To the city you're trying to reach And only when you get to the city Trying to find a particular address And worrying about how to get around the city What we're doing here really The gain that we'll get for routing Is that we'll hide the details That are internal to the region Outside of that region Well, I'm sure you get the sort of Theory of how we could use hierarchy In regions, but let's go through An example to make some of this concrete And make sure we understand it So I have a network here on the left And you can see that there are Five different regions, and within each Region there are a few nodes connected Together, and the regions are connected Together too Now every node in this network Is going to have its own forwarding table So that it can send packets in different Directions The forwarding table here is shown For node 1a, that's this Big long table, and you can see it lists All of the other nodes, and Which output line, which next hop To get there, and how many hops Away, so this is shortest path Where the distance is simply The number of hops So this is the kind of table You would get this large table If you use the techniques we have so far On the right, I have the hierarchical Table for 1a Now you notice in this table It lists in detail It has the same entries for Entries within Region 1 Because it's 1a, that's 1a 1b and 1c, well 1a, not hard to get to Since you're already there However, the other entries have been Collapsed, if you look at the full table It had four entries For Region 2 That's collapsed into a single entry We don't care about differences here We just want to know which way to go To get to Region 2 Similarly Region 3 Has been collapsed into a single entry And Region 4 And Region 5 Once My arrow is a little off there But you get the idea Okay, so we now have a much smaller table We can also use it to Root Let's just see, here we have a packet That's trying to go from 1a to 5c And I've coloured in those nodes Just so you can see them on the graph At 1a, we can look up the decision For 5c Now since this is a hierarchical Table, there's no entry for 5c In particular, there's just a Blanket entry for 5 It's this last one It says to get to Region 5 Go via 1c So we'll go here We don't have the table for 1c Written down, but the reason we went here Of course is to go this way And you can imagine that the path we will take To get to 5c That's this path Let me just clean up this figure Okay, so you can see the path we took To get from 1a to 5c And we could perform the same exercise For different paths Through this network But I chose this path for a reason And that's to illustrate the penalty That we can pay Sometimes when we use hierarchical routing For most of the paths We're using hierarchical routing The distance that we take in hops When we follow them is the same Even if we didn't use hierarchical routing And we've just got a smaller table But for some paths We can actually end up taking slightly longer paths Than the shortest possible path That's the example here Now you can see in the full entry The full table From 1a if I want to go to 5c That's this entry here It says I can get there in 5 hops Going by a 1b And you can see I've put in blue on the diagram The path we would have taken To get there And you can count it and you can see that it's 5 hops However In the hierarchical routing version The best route To get to region 5 Is simply given here as 1c And that took us along the other path That's because we've forgotten about All of the detail inside region 5 And we simply wanted to get into region 5 As quickly as possible So that's the penalty we might pay sometimes And just to close on this I'll make a couple of observations About hierarchical routing Just to reinforce the concept So the main concept here is that Outside a region Every node has a route All hosts within that region We're hiding what's inside that region We don't worry about it when we're far away This is what gives us the savings in table size They can be substantial It's also a savings In terms of messages and computation We also get benefits there Even though we didn't look at them in detail One thing I want to point out though Because it's sometimes a source of confusion Is this doesn't mean That all nodes inside a region Need to take the same path To reach another region They typically don't Every node has a path to a region For all destinations in that region But every node could take a different path To reach the same region The reason for this Is that routing decisions Are still being made individually by nodes It's just we're looking At the routing decision To reach an entire region There's no notion of taking a single decision That everyone within a region Can get somewhere else Okay now you know about hierarchical routing Good day viewers In this segment we'll talk about things you can do With IP prefixes Aggregating, joining them together And subdividing them to split them up Our topic here really Is how to help scale the routing Of the internet As well as improve its management And we can do that by adjusting The size of IP prefixes And in particular we'll look at two ways Split up a large prefix Into smaller subnets Or we might join together Several prefixes into an aggregate Into a larger prefix So just a little bit of background So recall that IP addresses As we've gone through, they're allocated in blocks Called IP prefixes Such as this prefix 18, 31, 0, 0, 16 And a key observation is The hosts on one network share the same prefix Now just as a quick reminder And because they share the same prefix We can route towards the prefix That's where we're getting scalability in routing As we've gone over Just as a reminder, let's work through an example here A slash n prefix has the first n bits fixed And so it contains The other 32 minus n bits are free So it contains 2 to the 32 Minus n addresses So for instance A slash 24 will have 8 bits free so it will contain Actually 2 to the power of 8 addresses That's not very clear 2 to the 8 is 256 addresses And a slash 16 will have 2 to the 16 addresses In it and that is What's that? 64k addresses 64,000 different addresses 65,000 actually If you compute all of the numbers out Okay, now The key flexibility That we get from using prefixes Is that actually it's routers that keep track Of the length of different prefixes They use it for the longest prefix Longest prefix matching algorithm To decide which way to forward track Traffic Now because it's routers That keep track of the length of prefixes Not hosts The key flexibility we gain with prefixes Is that routers can change the length Of prefixes without affecting the hosts For the most part In particular, we can change an IP prefix To make it more specific By lengthening the prefix Turning it into a block which has Fewer addresses so dividing a big block Into blocks with fewer addresses Or we can change the prefix to make it less Specific and we can take several Blocks and then join them together into A bigger block which is the less specific Prefix Well let's just go over a little bit How that would work Here is just an example Of the sort of thing we're going to do In this figure down here we have 3 slash 18 prefixes IP 1, IP 2 and IP 3 And what we'll do when we use Aggregation is we would join those together For instance into 1 larger slash 16 If all of the addresses were of the right form Such that we could aggregate them That slash 16 would then represent the whole region Here and we'd be able To route towards that for instance In fact there are two different use cases Which are really just converses That allow us to adjust The size of IP prefixes Both of them are taking advantage of hierarchy In slightly different ways And they'll help us both manage the network And to reduce the size of the routing table Really after scalability By doing this So one of the two use cases One is that you can do What's called subnetting You can divide a large prefix Which has many addresses Into Multiple more specifics Which represents a smaller network These are a smaller portion of the network These more specifics Prefixes are then called the subnets And in this way You can acquire a big block Of addresses Or a block of addresses from your ISP And you can divide it up into different chunks To help you use it most effectively Within your organization The converse side of this is aggregation Externally we might have IP prefixes for several networks And we might be able to join them together Into a more specific Sorry, into one large prefix Which is a less specific prefix We take all of those more specifics And we join it into less specific prefixes Which will represent A larger number of addresses We can do this if all of the addresses Are about right if they're in the same portion Of the address space so that they can be aggregated Let's see an example of how this would work So here Externally maybe this is a company here You can see the line is dividing it The company is to this side And here's the rest of the internet So from the ISP The company has acquired This IP prefix here For all of its computers 12820800 slash 16 So it's a slash 16 So it has 64k different addresses Well internally It might want to divide that into different structure Because often there is structure Inside an organization Here it's a university and we have the ECS and art departments So what are they going to do Well internally they could divide a slash 16 Up into a slash 17 A slash 18 and a slash 19 There's actually a little bit left over Now I'll let you Go ahead and afterwards Work out all of the different addresses Here just to see That in fact this block of addresses If you draw the address space has been divided up Properly It looks like the slash 18 Here starts at the very bottom Of the address range The slash 17 It looks like it starts about halfway through the address range And then goes up And there's also a slash 19 Somewhere in there above the slash 18 And there's actually a little bit of space left over It can be a little confusing unless you look at the values Of the binary In binary and draw a bit of a map Of how the address space has been divided And here's an example Of the flip side I might have Three different universities here Cambridge, Oxford and Edinburgh Have a slash 21, a slash 20 and a slash 22 Now It just so happens That these prefixes Are also chosen from A address space Which is quite close, it's all related In fact it all forms a larger block I can aggregate those prefixes So into a single slash 19 Is large enough to contain All of the IP addresses in here And you can see here's the address Of the slash 19, the lowest address In the slash 19 And again to really understand How these prefixes have been joined You need to be able to write down the top and bottom Address for all of these things And see how they relate For the size of the prefixes And the size of the overall block But there's an example of subnets and aggregation Of using IP prefixes to suit our needs Good day viewers In this segment we'll talk about routing When there are multiple parties in the network So this formulation For routing is very much like the internet In which we work There are now, the network is comprised Of multiple parties altogether And in the internet here There are the ISPs You can see three ISPs here And the complication is that Each of these parties might have its own goals About what would be a good route Yet somehow they all need to work together To be able to get traffic From a source to a particular destination Across the network Ok so first of all Let's just drill down on the Overall formulation a little bit By looking at the structure of the internet To give us a better idea of what we're talking about So here's a picture of the internet architecture And you can see that There are a series of different networks Here that are shown There are three, four, five, six Different networks that are connected here The networks act as They source and sync traffic They have different prefixes here We talked about prefixes being blocks Of IP addresses They're everywhere here These are all the sources and destinations On the networks Now there are different kinds of networks ISP networks, host customers here CDN networks Provide content which is often delivered Enterprise networks and so forth All of these different networks Are richly interconnected With one another In all sorts of different ways They might be connected directly But it's a common strategy That many different networks Will actually connect together They will connect to what's called an IXP IXP stands for internet exchange point And IXP is really a meeting place Where many different networks Are connected to traffic Our routing problem is that Somehow, even though these are all different Networks run by different people They have different ideas of what routes They would like to choose We want to be able to find routes From Source, let's say the CDN here Is sending traffic somehow To reach a particular destination Such as a customer here Within the ISP We'll get to how exactly we do that But first of all are just the issues Which are introduced By this internet wide view of routing Across multiple parties Because really These multiple parties bring in Two different problems That go beyond what we've seen In routing in individual networks The first one is just of scale We now have a very large network Because we're gluing all of the different networks We can think of together to form the internet So we're going to need to use techniques That work We've already seen things like IP prefixes And how they provide hierarchy And we'll see other kinds Of The scaling techniques that will be used Such as prefix aggregation I guess we talked about that But we'll also see the use of How we can use these parties Also for a bit of scaling that's going to help The other thing that I want to talk about In more detail Because this is really what's unique In different decisions Each different party They might have their own idea About what constitutes a good route So they might want to choose routes Or at least portions of routes to suit their own needs The way they choose it is described According to a policy So I said Yikes here because What's going to happen to the overall route When different people are trying to choose Different portions of it Will it even work? That's exactly the issue In fact A route with different preferences Can lead to some strange effects So let's look at The kinds of things that can and do Happen in the internet today So here's a simple model network We have two ISPs, ISPA on the left And ISPB on the right Now the policy for each of these ISPs Is that they want to choose The shortest path within their own network Why? Well If they carry the traffic the shorter distance It'll probably be cheaper And cost effective to run the network Okay, that seems like a pretty reasonable policy And actually you might think That if everyone chooses short routes Everything would all be fine But let's see what we would get Short routes overall That's not quite what's going to happen Let's look at what happens Let's consider Amongst all of the different prefixes We have here just the path that gets chosen Between traffic going from A2 to B1 So here is A2 We start inside ISPA ISPA gets to control how traffic Goes through its network So from here we want to send it along the shortest path To reach B2 Well we could go by any Of these different points These links which connect to To ISPB To reach prefix B1 This is where we're trying to reach B2 So which of these am I going to choose Well I'm going to choose the one that's closest To wherever I am because that will be the shortest path In the network Now I've drawn this figure so I can tell you That this one is the shortest path So then we'll go over this segment here Out the network we'll land in ISPB Here and we'll take the most direct path To B1 here Okay It's a little bit of a roundabout path as you can see Well what about the path from B1 To A2 Okay Well I start in B1 I'm going to go back but I similarly want to go to ISPA To reach prefix A2 I could use any of these three exit points Which I'm drawing The closest one is this top one here So I will go there and then across the link Then within ISPA I'll go directly To prefix A2 So you can see here the result Of the best paths that would be found According to these two policies If we could somehow come up with a mechanism To find them And I've just cleaned up this diagram To draw them And I'd like to make a few points About these paths Because they're not quite what you might expect If we had done one overall routing formulation Called this one big happy network We would have found the shortest path Between these two points Actually both of the shortest paths Between both of the paths Which is selected according to these policies From A2 to B1 And back Neither of them are the shortest path The shortest path here Is the one that's shown In the pink I'm tracing over it And we took a different path In one direction that was longer And a different path in the other direction Which was also longer than the shortest path Not only that But the two paths are different In different directions So they're asymmetric So you can see that policy routing In fact these effects are common in the internet Policy routing often leads to asymmetric paths Where it's different Going from A to B to B to A And often paths Which are not quite shortest And these effects are really consequences Of the independent goals And decisions Which have been made by the parties Rather than simply the effect Of hierarchy hiding a bit of information Causing us to take longer paths Well So this is what we're up against What I'm going to do now Is talk just a little bit about policies And then we'll have Fulfilled our goal of just understanding The formulation for routing With multiple parties And what policies are And later in the next segment We'll move on to BGP The protocol which finds Policy routes in the internet today So policies The idea with policies Is that they'll capture the goals Of the different parties Now Policy is this general word And that's because It's abstract Because policies could actually be anything Here's an example of a real policy The internet too Is a research and education network In the United States That's used to connect universities One of its policies Is that it will only carry Non-commercial traffic So it will carry traffic Between educational institutions So U-dub to MIT and back But it won't carry traffic From those educational institutions To commercial networks So that we could all serve Google For instance Why? Well that's just It's acceptable use policy Because that's what the network is for And that's a condition Of funding the network So the routes will be Computed to comply with this That's one policy In fact we don't know For all the commercial networks Exactly what their policies are Because these are proprietary They can depend on The two different parties That are connecting Can have all sorts Of different policy What we're going to do instead Is talk about two common policies We're going to talk about The policy of transit ISPs give transit service To their customers That's one kind of common example Of a policy that's often held up And we'll talk about A different kind of policy Called a peering service Where an ISP provides A peering kind of service To ISPs often provide A peering service To one another under some situation So let's look at those two policies Well here's this transit service So the idea of transit service Is one party in this deal That's the customer Who's going to pay for this Is going to get What's called transit service From another party The ISP So transit service is what you get When you connect to your ISP You're paying it for transit service And the idea of transit service The policy is that the ISP Party I'm going to refer to them As just the ISP and the customer Will accept traffic from the customer And make sure that traffic Can be delivered to Anywhere else in the network So you're a customer here You can hand packets to your ISP And destined for wherever And your ISP will somehow send them To the rest of the internet And where they will reach customers Who are outside that ISP Similarly your ISP will accept traffic From the rest of the internet And deliver it to you So some traffic could come from here And the ISP will accept this traffic Because it's for you And make sure that it gets to you And you the customer Generally pay for this privilege When we connect to the internet Pricing is often depends on The amount of bandwidth we have The size of our DSL link How rapidly it can send information But often what we're really paying for As well as the size Is connectivity to the rest of the internet The ability to send traffic And receive traffic from all of the other Destinations that are out there And the transit policies providing us that But there are other kinds of policies too And here's our peering policy In this policy We have two parties I have ISP A on the left And ISP B on the right These parties are both going to give one another They're going to use a policy Which gives peer service to each other Now in peer service Each ISP accepts traffic From the other ISP Only when it's for the customers To and from their customers So I have the two customers down here And you can see we can send from one customer To the other across this link and back And similarly for the customers up here We can do the same Okay that's great You might wonder what I've precluded by that Well actually why is this not transit service Well here's what ISPs don't do ISPs do not carry traffic To the rest of the internet for each other So in fact customer A1 Can't send via this link To reach some other place on the internet Not allowed I'm going to cross that off Not allowed we don't do that Why? Because that's not part of the peer policy So the ISPs will allow these routes Just between their customers but not further out And as a consequence of this Both ISPs are sort of doing one another a favor Because by doing this they then Don't have to send traffic via a transit provider And pay for it And usually as part of peer service We said that the ISPs don't pay one another Because they're both providing value For each other So these are the two policies that we've seen And in the next segment We'll look at a mechanism called BGP A protocol Which finds these kinds of routes In the internet today G'day viewers In this segment we'll talk about The border gateway protocol Which is used to find routes across the internet So we talked before about the fact That the internet is comprised of Multiple independently run parties Such as ISPs And we need to find routes across those parties That respect the policy constraints Of the different parties What we haven't told you so far Is how those routes are actually found Well in the internet It's with a protocol called BGP But in this segment I'm going to give you a brief introduction To some of the issues that we find in BGP Rather than extensive coverage Because BGP is kind of complicated And you might go over more details In an advanced networking course Okay so just as context Recall that we're viewing the internet As made up of all of these different Independent independently run networks We have here content distribution networks ISPs and just generic networks here You might be trying to find paths Through this network from a source here Say prefix C1 Acting as a source address That's going to send along some path Through the internet To get to a destination here Such as A1 Now which path will be chosen Through this graph Well I've just picked an arbitrary path there But the routing protocol needs to decide Which one will actually be used And that's exactly what BGP does So here's just an overview Of some of the aspects of BGP We'll move into some examples So BGP computes inter-domain routes As they're called These are routes across different entities Such as across ISPs and the internet As distinct from intra-domain routes Intra-domain routes are routes within One single network such as within an ISP Now we've already talked about Distance vector and link state protocol Methods for computing routes BGP it turns out is what's called A path vector protocol Not related to a distance vector protocol But a little more general In a path vector protocol What happens is that route announcements Which carry the path From the point in the network Back towards the destination Propagated throughout the internet So you can see here The blue line is meant to represent A route announcement Which is propagating out in the network It's propagating out from prefix F1 So it's going to tell people How to get to F1 And if we look at it inside ISPA We might receive a route announcement That says something like Well, to get to prefix F1 That's the destination here Here is a path you can use It goes ISPB net F Well, they are the networks Through which you go along this path Once you leave your ISPA To get to the destination And the way you access this path The next top is to go Via the IXP That's here So you just send across the link To the IXP And you'll be on your way Along this path That's an example Of a path vector announcement Okay, a little more terminology About BGP before we see examples First of all, we're used to talking About ISPs Here are the different parties In the internet But in BGP terminology These are ASs That stands for autonomous system All sorts of networks Might be autonomous systems You don't have to be an ISP It could be a content distribution Network A campus network And so forth So ISP and AS are not one to one We're also interested here In what are called the border routers These are not surprisingly The borders Sorry, the routers Which are on the border Of the ISP And they send routing announcements To border routers That are on the edge of another ISP Or another AS To which this AS is connected So we're really interested In the announcements that flow Between the ISPs here There are also announcements That can flow within a network Such as an ISP But I'm not looking at them here We're really going to focus On these route announcements As they move around And I'll tell you that A route announcement Just like we saw in that picture before Contains several things It contains an IP prefix That's the destination That you're trying to reach So that was F1 in our example On the previous slide A path vector That you go through to reach This destination I forget what that was That was maybe ISPB And netF on the other slide And a next hop That you use To get onto this path And that was via the ISP Or internet exchange point In our example Now the reason that you actually Carry the list of ASs The whole path Rather than the distance Actually if you think And just compare it To a distance vector protocol In a distance vector protocol You'd be sending a prefix Or a destination A next hop Which way to go maybe And a distance metric To decide which way is best In BGP We don't send this distance metric We just send the whole path As a list of ASs One reason this is done Is that the designers Were very worried about loops Between multiple ISPs Just imagine that packet Zapping around across multiple ISPs That would be pretty nasty And so the idea is That if you list the whole path You'll be able to recognize Directly if there's a loop If you've already gone through A particular ISP And you'll be able to Not use that route And you're going to see Two kinds of flows In network diagrams I'm primarily going to be talking About the route announcements How they go out from a destination To other places in the network To tell you how to reach That destination But if you think about Actual traffic that is forward Along the internet Realize that this traffic Will go in the opposite direction To the route announcements So it will go from wherever You are in the internet Towards that destination Well, here's a little example Just to look at To see how some simple Announcements would propagate In this diagram here We have three ASs You could think of them As ISPs if you like Here's one Here's two And there's three I'm just going to look At the announcements That propagate out From prefix C So that's the destination Well, along these dotted paths You can see that Announcements VGP announcements Carrying path vectors Propagate out in the network And I've shown them Here above Now This announcement here To reach prefix C You go via AS3 And the next hop is here R3A Is the announcement You would see If you would look over this wire Connecting this border router In AS3 R3A To a corresponding border router In AS2 R2C As that announcement Propagates further along If we look at it Over this link here Between AS1 and AS2 You can see that now The path has changed So the path you go through Now is AS2 And AS3 To get to C And also the next hop has changed Now to access it You go via here And this last announcement Just looks at what you would see Actually in the middle here Of AS1 Since it can't really Propagate any further out to A Similarly You'll note that Routes towards Prefix C Are also propagated Along this other path Along the bottom of the diagram So it's not the case that Each AS Is making a single Decision for routes Towards each prefix In different places In the AS Different routes Are propagating Using different next hops And so forth So we can see As we go down here I'll just circle The corresponding places Where these announcements are That here we go out The paths actually look the same In terms of the path vectors The ASs that you go through But the next hops Are all different Here Actually let's do this one here You can see that AS1 Which here is this announcement Goes via R2B Not R2A To get to C So anyone down In the lower portion here Of AS1 Is probably going to go Via a path here to reach C Whereas anyone up here Is probably going to end up Going via a different path To reach C Even though they go through The same sequence of ASs I've also drawn Darker arrows on this diagram And those dark lines Represent the flow of traffic Which is the opposite Of the flow of the routing announcements So for instance Over the top of the diagram A dark line goes from C All the way through The top of the diagram To A Going in the reverse direction That the round announcements propagate Right, well So you've now seen A lot of the mechanics Of BGP I haven't explicitly Talked about policy though And that's really What we wanted to get out of this So far I've just shown Your path vector How do we get this policy Of our ISPs Being able to make decisions Which suit their need Choose routes Which suit their need Well in two ways When a border router The first way is That when a border router Announces paths To the border routers Of other ASs It only announces paths That it's willing To have those ASs used Doesn't need to Announce other paths That might exist But it doesn't want Someone else to use It can just Withhold them And filter them out That is applying policy A second way Is that when A border router In an AS Here's multiple routes Towards a particular Destination prefix It can choose Whichever one Of those routes It would like to use If this was A distance vector protocol We'd choose the one Which has the shortest distance In BGP We don't have to Choose the one That has the shortest path We can choose Whichever one we want For our own reasons Which may have to do With strange Contractual Requirements Between the companies For instance Which you wouldn't Normally think Would be part Of a protocol But BGP Can accommodate Them by letting You choose The particular route You want Regardless of The length Let's see an example And then we'll call it quits And you'll have a rough idea Of how BGP works Here's another diagram In this diagram I have four ASs And I'm going to focus On this one here This is AS2 We'll look at The route announcements It makes And receives And how it chooses Its own paths To get elsewhere In the network I will also tell you That in terms Of commercial relationships Between these ISPs Two things are going on AS1 Is buying transits Sorry, AS2 The one we're looking at Is buying transit service From AS1 AS1 up the top here Is this big ISP That's kind of Providing transit service To everyone It will connect everyone To one another If you pay it money AS2 is also Getting a peering service A peer service With AS3 And it looks like They're doing that To exchange traffic Between A and B Just for their traffic Between A and B That's what you would do With a peer service To see how This is paths Found Which are consistent With these policies What happens Well, several kinds Of route announcements Flow around First of all We're going to look at What are called Customer route announcements The customer side Is really the flip side Of transit For an AS Like AS1 To provide transit Service To let everyone Reach a certain Prefix And to allow Traffic from That prefix To go everywhere else The prefix Needs to get To the transit provider That destination Needs to tell The transit provider Who they are That they want service This is a customer Announcement It's going up here It's labeled Cu In this diagram So AS2 Is going to tell AS1 Okay I am Here's an Announcement To prefix A That's the destination The path Is going to be AS2 Just by me And it's going To AS1 That's pretty straightforward Really This is really just saying To AS1 Hey Prefix A Exists down In me AS2 Well let's look at The flip side AS1 To The one we're looking at That's this one here Is also going to Receive Transit Routing announcements From AS1 Which will tell it How to Reach other Prefixes in the internet What transit Announcements Will it receive Well AS3 Has B As a prefix destination And AS4 Has C As a prefix destination Both of those Are going to advertise B And C To AS1 And since AS1 Is providing transit It will tell AS2 About the possibility Of reaching these destinations So AS1 Will tell AS2 A couple of routes For B As a destination AS1 Will say Hey, this is prefix B You can reach it Via the route AS1 Here you can see Our path has now gotten longer So we're now going through Two ASs To reach that destination And I'm ignoring the next Top here And similarly We will hear AS2 Will hear from AS1 That it can Reach prefix C Via the path AS1 AS4 Okay, that's a Transit Announcement But wait There's more AS2 Here is also Going to receive A peer routing Announcement Across here And it's also going to Send a peer routing Announcement So what are they for? Well this is really AS2 Wants to tell AS3 That it is allowed To send to A Over this link And AS3 Is also going to tell AS2 That it can send to B Over the same link So AS2 Is going to say Well AS3 You can send to A Via the path AS2 Over this link And AS3 Will say AS2 You can send to B You know AS3 Over this link So now we have All of these different Announcements That have been received By AS2 So what route Will AS2 Actually choose To use in the internet? Well let's do An easy one first AS2 Will actually Only hear One route to C So the way From AS2 That you're going To reach C Is actually This is the way The traffic will flow It's the dark line And the routing Announcement That we're selecting To follow The direction That's the only one We heard So that's the watch You're going to use To reach C What about to reach B Well we actually Heard two announcements We heard One which came Up here That the transit One And we heard One which came Here from AS3 Directly to AS2 Since AS2 Is now Heard two announcements It can use Its policy To decide Which of them Is better And the answer Is paying For transit service By the volume So AS2 Is going to send Over this Link to reach B And similar You can work through On your own What's going to happen For the route That AS3 And AS4 Will choose To be able to Send from B To other destinations On the internet Well that's Our simple example Of BGP So you're now Seeing a little bit About how it works And hopefully That gives you a feel For it For those of Strange effects We're going to leave That though For a more advanced Networking course I hope that One thing I would like you to take Away from this Is an appreciation That policy The policies Which ISPs use Is a substantial Fact in the routes Which are used In practice AS2 Could have chosen Any of two paths And they're really Quite different Different things Would have happened And it totally Depended on what AS2 wanted In fact The overall routes Will actually work This is an interesting Problem Something that Researchers look at How we guarantee That will be the case And there are Key factors That you might care about For BGP We're not going to look At them now But I'll just mention Some of them So you know What an interesting area Is to find out More about If you would like to One is convergence Just how fast These protocols Converge When new changes To find a new route Another is scalability BGP needs Routing messages Are going around At how much work Routers have to do And also You'll note That I skipped the integration Between the BGP We looked at Where messages Are sent across ISPs With the routing That goes on inside ISPs Really those two Parts of routing Need to be integrated Together well For overall Internet routes To work well So that's it For BGP I hope you've Learned a little bit And we're done G'day viewers For the transport layer But first Congratulations are in order This diagram shows Where we are in the course And you can see That we've gone through The physical, link And network layers And now we're starting On the transport layer The transport layer Builds on the services Of the network And it delivers data Across the network To applications With different kinds Of reliability Or quality Depending on The transport service model So here are A couple of slides Just to recall Where we are In the course Of the protocol In general This diagram Shows two hosts Communicating Across the network With a single router And you can Ignore all the details Of the protocol They happen to be TCP, IP And so forth The point I want to Make is That TCP The transport layer Is communicating Information From host To host Across the network This is the first Time we've Reached a layer Where all of The information That's sent by The network Or at least it shouldn't be That wasn't the case With the Network Lincoln Physical layer Where intermediate Systems Switches and routers Handled all of The information there The transport layer Is really using The network Simply to get Information Between hosts And we can Also provide Just a brief Review In terms of Data units The name For a message At the transport Level Is a segment And you can Transport control Information like a TCP header As well as A payload The payload is Application data That's carried Across the network The segment itself Is carried within A packet At the network Layer And within a Frame At the link layer Okay so I'm going to spend Most of this Segment Talking about The different Clients of transport Services That a transport Layer Might offer to Its user Information The axes I'm going to use To classify them Here are the Ones that we use In the internet A transport Service could Provide Either reliable Or unreliable Transport By reliable We mean If you send it It will be Delivered to the other Side Unreliable Packets can be Lost in the Network And this will Be exposed to The transport user Packets can Still be lost In the network That was this Top Axis And you can also see A distinction in The unit of Data that's Transferred We might transfer Individual messages Sort of like a Post Office model Or an Infinite stream of Bytes That's the Bytes stream model Now in the internet We really provide Two kinds of Service For applications To use Two transport services The common one You probably Heard of Is TCP TCP is actually The protocol The service itself Is a stream Service It's a A reliable Bytes stream A bidirectional Reliable Bytes stream Between applications The other Service that the Internet provides Is a Datagram model Where you send messages That service is Implemented by UDP Okay, let's Just compare Some of the features Of these Two different Transport services To get a little Bit of a feeling For how They differ About what A layer does for you So on the left here We have TCP In this table And you can see That TCP Well, it Sends information Reliably And so there are Many features That are related To reliability Connections have To be set up The Bytes Then are delivered Reliably Meaning Essentially that They delivered once And in the same order That they were sent Actually ordering And reliability Is somewhat separate But we get both Of them here This also Since it's a ByteStream It's an Arbitrary content length Model You can send as many Bytes as you like They will have to be Divided into Packets or segments Inside the network But that's The Transport Layer's business At the other side You'll receive messages As if they came in On an Infinite ByteStream The Transport Layer with TCP also provides Flow control To match Sender to the Receiver Capabilities We haven't seen Expect you to know What flow control Is yet Nor congestion control That's going to be A mechanism That matches the Sender to the Network's capabilities In terms of its bandwidth So you can see here TCP is really Quite a full Featured protocol It does a lot On top of the Network layer To provide a service For applications On the other hand UDP on the left side Sorry On the right side Of this table Is really just A glorified Packet Transport Very little Over IP You send Datagrams Well, they really like Packets The messages Just like the Post Office They can be lost And reordered Somewhat like The Postal Service They can be Duplicated on Networks You could send One copy And two could Come out That's a little Lot But that could happen There's a limited Message size Because these are Like packets These datagrams But essentially Here I'm saying That the transport service Provides you No guidance On when it's A good time to send In terms of The receiver Being able to handle Those messages Or the network Being able to deliver Them TCP Helps us With those tasks So this Right hand column You can also See that If I wrote down The capabilities For packets That would be Very much like this So here We see a bit Of a dichotomy For the whole Kitchen sink In terms of features Okay Let me go on And talk more About the Interface Between the transport Layer And the application Layer Which is using It as a service We've actually Seen this interface Before It's our good old Sockets API Now A socket's provided The simple abstraction Called a socket To use The network Before We talked About the Network That we zoomed in You can see They're really providing An interface To a transport Layer service Sockets are used To write All of the different Internet applications You see out there The socket API Supports both Of these Kinds of internet Transport services Both the streams And the datagrams That we just saw When we looked At sockets Before We only looked At the stream Model And you might Have also seen This Or a connection-oriented Transport And datagrams Are connection-less Just different names For some of those Kinds of services A little bit more About the Sockets If you recall One of the key Addressing attributes In the socket model Is ports Ports are Where applications Attach To the Transport Layer And Sockets Sorry These different Ports Is what lets Multiple different Applications Use the same Transport Layer Instance So we can Multiplex The network between Different applications You can see here Two applications One and two Using different Sockets And ports To attach To the Transport Layer Here was The API Again For Sockets Again We went through this A long time ago When we did An introduction To the course I'm not going to Provide you Going out here Is the table Now you know That it's the same Kind of API That's used for both Sockets and Datagrams It turns out however That these three calls Here listen Accept and connect You only need them For streams Because this is all About setting up the Connection Datagrams are connectionless So you don't need To establish any Connection Before you use them Similarly For send And receive With the streams We simply use Send and receive To send the information And receive it At the other side With our Datagrams Slightly different forms Are used Send to And receive from This is because If you have no connection And you want to send Information Missing parameter You need to specify Who to send it to And with A datagram model You can actually Send datagrams To many different Receivers Without having to Set up any Different connection Between them Over the same socket Similarly Receive Users a form Could receive from That provides information About who sent the Datagram to you Since many Different senders Could have sent their Datagram that could be Received on your Port in a Datagram model Let's talk A little bit more About ports And that will round out The service API That the transport Layer provides In the internet To applications So we say That there are Ports These are Identifiers Which provide Addressing For applications To use Actually it turns out That in an Application process Which is running on Machine Is identified by The tuple Of the IP address So that sort of Told you the machine The protocol Since this could be TCP and UDP And they share The same port space And the port Number itself Now you could Simply think Of a port Even though it's A 16 bit number As representing A numbered mailbox Can lease Those mailboxes To use the services Of the Transport layer Just like you Might get a A mailbox Or a post office To use the postal system In this case Not only Would you get Things delivered to it But that's where You put things in When you want them sent Across the network Clients and Servers use Ports slightly differently Servers Often bind To what are Called Well-known po