Routers, The Internet & YouTube Offline - Computerphile

in the UK in British English we say Rooter for this thing that forwards data that finds a route and we say rent it for the woodworking tool that you make a groove with in America they use the word ranked in both it's the same pronunciation for both gotcha and now I believe routing is something completely different in Australia but we don't have to go up with another what happens if there's a serious problem with routers ultimately will mean that you can't get your data through so either you can't get your requests through when you can't get the responses back so it will stop you interacting with the services you not be interact with so you might notice that because your web browsing and suddenly you can't get somewhere you might notice that so you can't get the Facebook for example you might notice that because you start receiving very poor performance so you can still get through but everything slows down a lot so what's going on inside the routes and I suppose that's there so I guess the way to think of it is you've got a Rooter and so there's going to be some data arriving some stream of packets that are arriving into one of these interfaces and the route has to decide which of those packets are going to go out here which of those packets may be difficult to do and maybe some of those packets are just going to get drops and the routes not gonna know what to do with them this is the in interfacing these the out interfaces so these would be mirrored yes you've got you know this interface one two three this would be one two three as well selectors going in both directions on each interface the route has to make this decision about what should occur must happen it should it drop it should it forward it and if it's going to forward it which intervation is fought it out of and that's the process of forwarding and the information it uses to make those decisions is routing so it's got to build up some information that allows it to know that for this given packet that's trying to get to some destination IP address which one of these interfaces is closer because these are going to connect off to some other router with some interfaces on and then these are going to connect off to other rooters and so at some point there's a destination over here which is where you want to get to and these routers have to figure out okay this route it gets it in those that it should go out of that interface and not this interface because this is going to go off somewhere else and then when this route to gets it nice no it's got to go out of that interface and not this interface and so on and so they all have to build up this information and that's what the routing protocols do is that these are protocols have run so the route is exchanging information in order they can work out how to build the tables they'll use for forwarding and then when a packet actually comes in that needs to be forwarded they look up the destination address in that forwarding table and they make a decision on where to send it based on the information that previously sorted out through the region protocol something like ibv 4 you've got 32-bit addresses the destination address can be approximately any bit pattern and so you've got 2 to the 32 possible destinations which is about 4 billion so logically speaking each route or kind of has a table with 4 billion entries in a packet comes in you look at the destination address in the table and that says go out of interface 3 or guide an interface to whatever it might be now in practice that clearly would be a stupid thing to do because a table of 4 billion entries big table to look through every time and so there's ways of that table is essentially compressed by using what are called IP prefixes so that instead of just having all the possible addresses you say well ok let's group the addresses together by some prefix university of nottingham prefix is one 28.24 3/16 so all the dresses on the internet that begin one 28.24 3 belong to the universe you're not taking and so a Rooter out there on the internet will receive a packet this destination is one 28.24 3.6 dot 7 or something and it doesn't need to look up exactly that address it just matches that prefix this table of entries might have dot 6.5 slash 24 it might have one 28.24 3/16 lots of different prefixes and all of these are simply saying okay well there's going to be some bit paths of ones and zeros 1 0 0 0 0 0 0 0 I think would be 1 2 8 and then the bit pattern for 6 or lots of zeros and a one 10.5 start be again zeros 1 0 1 at the end so it doesn't need to match any of these remaining 8 bits and so it will go down doing that and what it does is it picks the longest prefix that matches so you could have an entry here that was 1 28.24 3/16 slash 24 for example and it might be that both of these entries matched right so you had the address that you're actually searching for let's say it's 1 2 8 2 4 3 . 16.7 now that address going to match both of these entries because the prefix is the same so these initial bits on the front are the same and so what will be picked as it will be this entry that's picked because that's the longest prefix 24 bits is longer than 16 bits so it's looking through this to find the most specific because it's most needed literally the most specified subnet so they designate ranges of IP addresses and what you're trying to do is you're trying to find a prefix that best matches the IP address that you've got that you're looking for the destination of and so you look through this list and you'll find the most specific which means the longest prefix match and that's the subnet that you're matching against the routier would then essentially look at the packet with with this as the destination address it would look up in this table it would say okay this matches here so that's a possibility capes on the come to the table o matches here this is the best match so far looks for the rest table this is still the best match so this packet with this destination dress gets sent out of interface on the wall and that's how forwarding happens so this is just software that's running on them that's causing certain packets to be transmitted so packets to be received and interpreted in it's information exchange between the rooters to build on these 40 tables there's a couple of standard ways that happens that the one I personally find easiest to explain is that you run a protocol that's called the link state routing protocol and what's essentially happening there is the protocol runs and it attempts to build a map of the network and then the rooster can take this map and it can run an algorithm called the shortest path algorithm and it can find the shortest path between any two points so then it knows what to do if it gets a packet coming in it Maps it to a destination which it can then look up in this on this map of the network and say right what's the shortest path to get to that destination so you'll have a bunch of rooters in the network they'll be connected in some configuration packet comes in let's say to this one route looks up in the forwarding table what it needs to do with it and it says for example this is the shortest path but it's worked that out in advance by having all of the routers inside this network have been exchanging information with each other as part of the routing protocol so that they can construct this map so if this packet comes in here and it has to get out of here then this router will know that the best way to get down to here might be through this guy which means it's got to go out of this interface not this interface obviously if that guy or something failed along that if something crashes there then yeah the routing protocol is still running and it will detect this guy's crash or detect that in particular these links have failed and so it will now say okay so now the shortest path to get here is to come out of this interface the three sort of bits this process are there's a little protocol that will run between two routers on the link so they essentially will exchange packets with each other called hello packets and the idea there is simply that if this guy can transmit a packet to this one this guy receives it transmits the packet back to say I've received that and then this guy transmits a packet back say and I received your receipt if you like so once they've made these exchanges they both know that that link is live and that somebody on the other end is listening so they can both say right well I know that this is route of 100 or two they both know now that the link between r1 to r2 and this will happen on all of these links and so each router builds up a set of information that says what it's connected to so that's kind of phase one and then phase two is that this gets disseminated I will try and spell this sermon incorrectly probably get it wrong each router now starts broadcasting to everybody else this is what I'm connected to and that gets disseminated through the whole network so everyone now knows what every other reader is connected to and then each Rooter can run the shortest path algorithm and each router is trying to build up a consistent set of data about the whole network and then it runs an independent computation part of the normal operation of these is that when one of these links fails let's say it's not the root of the fails just this link fails there's a time delay while this router and this Rooter notice because they're continually doing this hello exchange and there are various different ways that's going to shortcut but it could be the case that if they have to wait until they stop getting hello packets through and I think the default configuration on at least one of the instances of this sort of protocol is that have to wait for three exchanges to fail before they decide that really the link is down they then have to update the link state database that they carry each one has to update that and then they have to disseminate that through the rest of the network and so there's going to be a period of time when this routes are here still thinks that the shortest path is to go write that because it's not yet learnt from this guy that in fact this link is gone for a period of time while it's still detecting the link failure then packets will still be being sent down that link and I just get dropped because they won't go anywhere so you'll get some loss then for a period of time after this has learnt about the link failure it will send packets through so the route so things will get sent to it by mistake and it will have then send them back somewhere else but you've got this period of time where things are inconsistent this is one of the things that happens is that you get routing loops so you'll have packets going around this loop because they're both disagreeing on what's there now obviously it shouldn't last very long you do get loops that last longer in more complex configurations and this kind of thing you'd expect that to be resolved fairly quickly but you can get these kind of loops occurring what you then have is the problem of you've got other networks if you have this sort of protocol across the entire internet you'd have a case where every routine internet would have to know the status of every single of the roots friendliness net which would be many many many hundreds of thousands if not millions in particular what would kill you there is that every time something happened so a link failed every roots are in the internet would have to be informed of that before they could make a consistent routing decision and so what you actually have is you have a different routing protocol and there is only one instance of this called BGP which runs between networks to allow information to transit between networks about what can be reached and its problems in BGP that caused a lot of the issues that you can't see reported about this kind of things so for example does complicated I think when YouTube has gone offline and there was one a few years ago when things the Pakistan network operator they tried to inject information into BGP to prevent people connecting to YouTube from within their network but because of the way they did that that information propagated and it caused lots of other networks to also fail to be able to connect to YouTube it comes back this prefix routing thing so there's I don't know what the prefix actually is it won't be this because this is a private network space but let's say it's 192.168 or slash 16 let's say that's the YouTube prefix so it's specified that the first 16 bits are 192.168 and then does matter what's after that and that identifies the YouTube network for the sake of argument and so you've got this table that's been built up in all the routers and when a packet comes in trying to get to YouTube the destination address gets matched it matches against that prefix that says which interface it should go out of and it gets transmitted on so what they did was they said okay well let's make it one on two dot one six eight dot one two 8/17 and 192.168.1 two 7/17 think that covers space the point is that they made it into two longer prefixes actually what should happen is that should let's say go to YouTube they said well what we'll do is we'll have these addresses go to Devon all so we'll drop those packets so instead of sending them on to YouTube as we should when they match against these prefixes in our network we'll just drop the packet just get rid of it which means that people going through our network can't get to YouTube unfortunately those prefixes got advertised through BGP so they got advertised other networks and other networks picked them up as well and because these are longer prefixes they would be preferred to the shorter prefix which was the right answer you prefer these instead because they're long prefixes so then other networks are doing the same thing and they were saying if they weren't really saying that no they would be saying to the Pakistan Network rather than going to YouTube and so other networks start believing these adverts the advertised prefixes they match destination addresses against that there should be on to YouTube and they get sent to the Pakistan now week instead and then those things get dropped this bad information got propagated out into the rest of the Internet and that now starts to mean that other people who connect to the network through other people's networks also start to see YouTube not being reachable it was noticed this was a problem and essentially all that has to happen is that you don't believe these two adverts and then this one takes over again and you tube becomes reachable again with BGP you can apply routing policies so you can start to say things like I can reach these networks but I'd prefer that you didn't use me to get there or you know I can reach these but our contract says that you should use these others in preference or you should use me in preference for these different things or when you re advertise that you can now reach these networks because you can get to them through me you have to advertise them in such and such a way or would like you to advertising in such in such a way so that not everybody in the world tries to come through me that I'm like I'm a last resort the backup link or whatever it might be so you can start to apply its kind of more complex configurations to how this information gets disseminated whereas in this case with its like link state routing it really is just a case of detect what you connect it to tell everybody else what you connect it to run shortest paths and that's it but so these numbers get assigned hierarchy so there's a body called I Anna the internet assigned numbers Authority I think

Channel: Computerphile

Views: 191,297

Keywords: computers, computerphile, computer science, university of nottingham, routers, routing, internet, The Internet (Media Genre), Router (Computer Peripheral Class)

Id: AkxqkoxErRk

Length: 13min 22sec (802 seconds)

Published: Thu Oct 23 2014