etwork usage At home you might be looking at a web page Surfing the web So you're demanding that the network send lots of packets To download the page Then you'll read the page While you're doing this Of course you won't be using the network at all perhaps You will be imposing no load on the network So there'll be a short pause Then you might do something And there's a burst of activity again and so forth In short, the load in data communications networks Of a particular user Usually varies greatly over time If I just make up Here are different users User 1 and User 2 These are completely hypothetical as examples Here's a profile for user 1 Maybe this is the different rate At which they send traffic over time Sometimes they're very busy Sometimes they're not so busy They're not doing much And User 2 We could see they might look like this Okay, that's just an example What does it mean? Well, it means that methods such as time revision multiplexing And frequency division multiplexing Which are geared towards continuous traffic For a fixed number of users are not very effective To serve these users well in the network We would need to allocate a bandwidth level here R Which corresponds to the amount of bandwidth they'd need When they actually need the network If we have to pick one level We want to pick this level If we picked a much lower level Then they wouldn't have enough bandwidth When they actually wanted to use the network But of course the difficulty with this level Is we're wasting all of the bandwidth I'm shading in the portion here Which is not being used at any given time That's a waste This is good bandwidth We'd like to get something out of it Instead, well there's an alternative That we would like to get to When we multiplex network traffic And that is We would like to multiplex network traffic According to the demands Which every user is placing on the network And we can do this with what is called Multiple access schemes We would really like For these users to share a link Whenever they want to send packets They get to send packets And all of their packets are mixed up On the link according to their demands To do this We would get the gains of statistical multiplexing Remember from early on in the course We talked about sharing based on statistics As being a way to pack more users Into a given amount of bandwidth You can see that here In that I have the two users They both need bandwidth R But if I combine their signals I might get a load line Like this green line Which I'm drawing over Well, the amount of bandwidth We need to support that Is going to be some level I've called here R dash The main site is that R dash Is likely to be somewhat less than 2R So by using less than the bandwidth We would need if we handled these users Individually with TDM We should be able to serve them Both of them as effectively This is what we want to happen We don't know how to do this yet TDM and FDM don't do this Instead multiple access protocols Share this link at a fine By dividing the bandwidth finally over time We're going to look at these multiple access protocols In the next videos We're going to look at two families Of multiple access protocols One is this class of Randomized multiple access protocols Where nodes randomize their attempts To access the medium Essentially they're going to try And access it whenever They've got something to send This is good for low load situations And I'll tell you now This is what's used For a Wi-Fi editor 2.11 We'll also look at an alternative Just so you can see Some of the pros and cons This alternative is called A contention-free multiple access protocol In this family of protocols Nodes take turns In a well-defined order To access the medium So it shows you just A different way you can do things It's better where you need Much more control over The quality of service you'll get Okay, well let's see These two different kinds Of multiple access protocols Today viewers In this segment We'll talk about Randomized multiple access Control protocols Okay, so that's a mouthful of a phrase Randomized multiple access control But the topic is a fundamental one And also an important one In computer networking The issue is simply this We have multiple nodes A set of nodes Who want to share a link How do they do it? When they have traffic to send Who gets to send when? This is a scenario That comes up in Wi-Fi For example When you might have multiple access Sorry, multiple laptops And they would all like to talk To the one access point How do they decide Who gets to send when? We've looked previously At multiplexing schemes Called TDM and FDM Which divide up the link In terms of either time or frequency They're well suited For continuous traffic But not very well suited For computer networking Where the traffic is bursting So in this segment We're going to start looking At alternatives To do that We'll use the simple model That's shown here Where we have The multiple computers Just all attached to a single wire So if we wire them together They can all talk over that wire And we have the multiple access problem Of deciding who gets to use the wire when Now, like many networking issues Protocols This actually turns out to be Quite a subtle issue In many ways The designs you come up with Can have strange effects Strange side effects One of the key things Which makes this hard Is that it is a distributed system All of the different nodes there Get to see what they can see Locally attached to the wire So they can send and receive messages To other nodes But they have no overall view Of what's going on in the system And there's no one in charge There's no special party If there's someone in charge Like you or I And we can look at this network And see what's where We can organize things fairly easily But we're now trying to solve A multiple access control protocol Without that central view That's what's difficult Okay, so the schemes we'll explore Are a family of Randomized multiple access control protocols What does this mean? It simply means that they use Randomization to handle Some of the difficulties Like collisions When multiple nodes Try and send at once Randomization Or randomized Multiple access control protocols Are the basis for Classic Ethernet This is one of the most Successful networking technologies Of all time That we'll learn about And before we dive into it I'll remind you of the central problem here Which is that we want sharing While the data traffic is bursty In this figure, for instance These nodes of these nodes The middle one looks like it's asleep The one on the right Maybe occasionally sending A bit of traffic But not much The one on the left is very busy If we use TDM or FTM To divide the link up Into three different parts The one on the left Would only get a third of it The other ones aren't Really using their share What we would like to do Is statistically multiplex These demands So that the one on the left Could use most of the wire While the middle one's asleep And the right one's not using it much So let's see how that works Well, our story For randomized multiple access control protocols Actually begins in the Hawaiian islands In the late 1960s In this setting A new kind of way Of multiplexing a link was developed Rather than use TDM or FTM This new protocol was devised By a guy called Norm Abritsom The setting here was That we have all of these different islands Hawaiian islands They have a wireless link The islands want to send to one another They're distributed How do they decide Who gets to send when And let's not use Simple TDM and FTM Here's the protocol Like many things It's a very simple idea It works like this The Aloha protocol When a node has traffic to send Guess what, it just tries to send If you send successfully You're going to end up Getting an acknowledgement back Of some form I won't go into all of the details here And then that means Everything's okay It was received If you don't get a knack That means there's been Some collision Maybe two nodes Have tried to send it once So all you do Is you wait around In the amount of time And try again That's it A very simple protocol What could possibly go wrong Here's how it works Just as a bit of a diagram You can see we have Five different users here And they're all sending packets over time If we follow the protocol They'll all just send When they have traffic to send Now if more than one of them Sends at the same time The signals will superimpose We won't be able to receive it Correctly There's a collision And it's lost So you can see here Several packets Are involved in a collision Over this time We know Some portion of the packets Have been transmitted At the same time And also over here However Even though Some of these frames are lost Many of the other frames Get through Okay So is this a good idea Or a bad idea You can think about that For a minute And I'll tell you the answer Actually It's a pretty good idea on the whole Or at least a reasonable one It's a dead simple scheme It's fully decentralized There's no central point of control Here that can fail Or is required for the system And it works quite well Under circumstances of low load Where the link is not busy Most of the time Now for many networks Low load is actually A common case We might have many computers But often they're really Not doing anything much With the network At least they used to Before we have all of these background processes Under low load Well If the network's mostly not being used And someone has a packet to send They can just go for it It works So it's relatively effective Under low load Of course The problem is When you really want to use it And multiple people want to send Which is basically a problem It's not efficient then You'll get collisions You can actually do some Randomized analyses Of this And if you dived into all of the details You'd find that The most efficiency you could get In terms of The fraction of the link That's successfully used To transfer packets Topps out at about 18% So we've wasted More than three quarters More than four fifths Of this link Its capacity That's not so good You can actually come up With some improvements here If you slot time So all packets begin On regular boundaries It turns out that you can double The efficiency from 18% to 36% And the reason for that is Now collisions are all or none You no longer have a packet Or a frame that's mostly made And then at the very end Someone just clips the end of it And the whole thing is ruined But rather than look at that We're going to look at Other kinds of improvements To turn this into A much more effective protocol And the place that I want to get to Is so that you understand The design of something called Classic Ethernet Ethernet was invented By Bob Metcalf In the, let's see, in 73 The early 70s here It became really the most popular Land, local area network Technology of all time So in the 80s and 90s It was very common to see Ethernets deployed in buildings And it worked like this Essentially all of the different Computers here were wired To the one cable which sneaked Around the building And connected all of these together It was, you know, usually A 10 megabit per second cable Somewhere near the beginning All the nodes really have to do Is solve the multiple access control Problem and then they can All talk to one another So to do that We're going to improve on Aloha in several ways Let's look at those improvements The first way that Ethernet Improves upon Aloha is With a technique called CSMA The carrier sends multiple access This simply means that a node Should listen to the medium To see if it's busy before It sends its frame It sounds like rather An obvious technique But it's not quite so obvious In the sense that it's easy To engineer with wires And so Ethernet does it In a wide context But it's actually more involved In the case of wireless As we'll get to in the Subsequent lecture Okay, so our technique is now Simply to listen Before we send packets And the question I have for you Is whether this is in fact An eliminate collisions completely Let's think about it for a minute If every node listens before it sends Will this eliminate collisions? Why or why not? Well actually it doesn't Eliminate collisions completely Now many people When post with that question Will say well it's still possible If two nodes send instantaneously To have a collision If they send it the same instant Even if they send it slightly different times A collision is possible And the reason for this The intuition is that it takes time For these frames to propagate Along the medium So for instance Here's what could happen Well actually it's possible For both of these nodes Here's one on the left We have our three nodes In a network This node to listen Let's see is there anything here No and start sending a frame At the same instant in time This node can listen Is there anything here No and start sending a frame Now this can happen Because it takes a finite amount of time For the frames to propagate From one end to the other And cause a collision In fact that time To propagate is D Our delay Here's a picture of that You know once again Just the two nodes both Here does idle both send There will be a collision It just hasn't happened yet So it turns out What we're really saying here Is to remember the bandwidth delay product Which is a measure Of how much information Can fit on the network CSMA carries sense multiple access Is a good defense against collisions Only when this bandwidth delay product is small And by small I mean Less than one packet Much less than one packet If that's the case Well if there's much more than one packet You can see in this picture The kind of thing that can happen Someone can send Their packet can be on the medium A collision will happen much later If it's much larger than one packet You're still sending And your packet time is sufficiently long That the interval during which A collision can happen Is small relative to a packet time So collisions are less likely Or less damaging Because they only occur During a smaller window of time The second improvement That Ethernet uses on top of LOHA Is to use collision detection Not only do we listen Before we send or talk But if someone else is talking Or using the medium at the same time Then we stop sending We detected there's been a collision And we abort our own collision In Ethernet The way you abort a collision Is you send a jam signal Just to say to everyone Well stop You know there was a problem And then you can see Transmitting your frame Now again this sounds Like a fairly easy technique It works well enough with wires It's a little harder In the wireless context So here in our picture Both nodes have detected a collision And they're both going to issue a jam signal It's actually a little more complicated Than I've been making out When there is a collision You would like all nodes That are involved in the collision To realize that a collision has occurred Otherwise a node could send its frame Think that everything is fine And not realize that the frame Never got there because of a collision If there is one and all nodes know Then they can take action in the future Such as retransmitting their frame So this leads us to think about How every node is going to realize That a collision has happened And again a key factor here Is the propagation delay of the medium There is a window of time During which a node can Detect a collision You would hope that if you send And someone else is sending You know right away But because of the propagation delay It can take a finite amount of time Here's the scenario This node starts sending It signal propagates down to the other end Of the wire Now that takes about d seconds Well just before the signal gets here This other node decides to send a packet Just an epsilon before It starts sending and immediately It's going to detect a collision But its signal is going to take You guessed it Another d seconds To return to the other end And it's only when it returns to the other end That this node here will see That there is another signal on the wire And detect a collision That's then taken up to 2 d seconds To detect a collision In Ethernet or with CSMACD The technique that used to detect collisions We ensure that all nodes know That a collision has occurred By imposing a minimum frame time We require nodes to send frames So that the minimum frame Takes at least 2 d seconds to send That way you'll still be sending the frame For the time interval During which you could detect a collision Or if there was going to be one You'll know that a collision occurred The node can't finish before the collision Is what it says here Which is a good way to put it If you do the math for an Ethernet Depending on the bit-rate And the maximum length And hence the d The amount of time things can propagate You can work out that the minimum frame For an Ethernet is 64 bytes This means that actually If you wanted to send a packet With a one character in it Or a short message like ok The minimum message size That you're going to send Is 64 bytes regardless If you try to send something small It will be padded out And finally there's a third issue In Ethernet as we move away From Aloha And that's the issue of persistence This is a good illustration actually That these protocols In a simply random access protocols Where you just send Can sexually they sound very simple But there can be very complicated Interactions between different nodes When everyone independently Follows all of these rules And persistence is one illustration of that So the persistence issue Is simply the question of What one node should do If it senses that another node Is using the medium Obviously it's going to wait And not send right away Or that would cause a collision But how long should it wait That's the question So what do we do now Ok well I have a brilliant idea The node here on the left Should simply wait until The other node is finished And then go for it That's the simplest solution I can come up with I like simple Generally we like simple designs But in the end It sounds good What could possibly go wrong Well you might have guessed Something can go wrong Here's the problem that you get If you use that scheme Where you know that Senses the medium Busy waits for that sender And then sends immediately Actually that is a good design If you are the only node That is waiting on the medium For someone else to finish Because then you go right away But what if there are two Or three or four different nodes All of whom wanted to send And they are waiting for another node to finish If they send immediately They will all collide In fact we have really Created a problem here With this rule of wait Till someone finishes And then go for it In that the node that is sending Is almost acting as a perfect Synchronizer for the other nodes It's lining up all of their Transmission so that A collision is guaranteed If there is more than one of them This is not good It's also more of a problem With more load Because the more load The more likely it is That more than one node Will be waiting to send So that you will get collisions And the more collisions there are The more nodes will have to Resend their frames To try and get them through So we'd like to do something about this Well if we shouldn't send right away How quickly should a node send The difficulty here Is that it depends On the number of queued senders If there is only one sender That's queued up and waiting to send It should send right away If there are two senders You would like each of them to send With probability about a half So that on average Only one of them would go right away And the other one would wait That would be good On the other hand If there are ten senders You would like each of them to send With probability about one in ten We would expect that way That only one of them Is likely to go That way we'll make sure The network's used But there's unlikely to be a collision Which we'll waste that bandwidth In general If there are n queued senders Then you'd want each to send With a probability of one on n That's what we would like to happen But since this is a distributed system And the load is changing Dynamically over time This node Or any of these nodes here Does not know what n is What is n If you knew what it was You'd be able to send With probability one on n But at any given time A node doesn't know what n is Well, it's a clever heuristic Which is used in Ethernet To solve this problem It's called binary exponential back-off And it's a technique That's probably useful In a lot of other contexts Where you're trying to adapt To a certain level of load Binary exponential back-off Cleverly estimates The one in n probability And it does this By starting and optimistically Assuming after a collision That, well, since we're a collision At least two people were involved But it will assume There was only two of you And so every node That's going through this process Will say, okay, I will Wait only zero or one frame times That's two options So I'm going to send right away With roughly probability a half Is roughly what it corresponds to Not exactly, but roughly If you collide again You say, well, whoops Maybe there were actually More than two of us I'm going to try again This time I will send My retransmission chosen randomly Over a four-slot time So that's like sending With probability one on quarter A quarter for every time slot Roughly If you collide again You say, wow Well, maybe there are actually More than four of us I'm going to double The number of slots I'm going to wait for That's eight slots now I'll send with probability One on eight, roughly And so on So what binary exponential Back-off is doing Is it's doubling the interval For which you're waiting Over with each successive collision Now as you know This exponential growth and doubling Gets quickly very rapidly So even if you needed to wait For, you know If a hundred nodes were containing all at once Binary exponential back-off Will get you there relatively quickly All you would need to go through Is, you know, six or so different collisions Six or seven different collisions And you'll get up there fairly quickly So in practice Binary exponential back-off Is very efficient It's able to adapt Over a large different operating range And this is a property We very much like to see In our network protocols We would, you'll often hear the word Scalability in networking We would like to design network protocols Which work when the number of nodes In the network is very small But they also work well When the number of nodes In the network is very large That way as our network grows There should be no problem Binary exponential back-off works well When there are very few nodes Because it optimistically starts By assuming that there's No one much around And you can send rapidly But it also works well If there are a large number of nodes Because by doubling this back-off It very quickly gets to About the right operating point Okay, so when you put All of these improvements together We have Classic Ethernet Recall, Classic Ethernet Was this hugely popular Land technology for connecting computers This shared cable Snaked around the building You connected the computers to it They could all talk There's some details here Just to relate to our physical layer talk It was a 10 megabit per second cable It's a coaxial cable The signals were sent here Using baseband signaling Now the key for Ethernet Is this multiple access control problem And the solution that Ethernet uses Is one persistent CSMACD With BB Wow, that's a mouthful But we've seen everything That you need to understand this So Ethernet uses Carrier sense multiple access That's this bit where you listen Before you talk And it further uses collision detection So that if two people start Sending it once They realise there's a collision And stop So that we don't lose Too much efficiency The stations, the nodes Using the Ethernet are persistent They're what's called one persistent Meaning that if someone else is Sending they wait for a moment And then they send right away They try and send right away Well we know that can cause collisions If people queue up So Ethernet also includes Binary exponential back off To adapt the persistence So that everything works And there we have this technology I'll tell you just a little bit More about it And to do that What we'll do is we'll look At the structure of frames That are sent across the network It's often very helpful for protocols To look at the format of their messages Because we can see The different functions that are included The different information That's in these messages And that helps us understand The different functions of the protocol One thing that you'll immediately see If you look at an Ethernet frame That we haven't talked about before Is it has addresses on it It's also a destination address We didn't need this when we were talking About a link where You know sender is connected to a receiver Because whatever was sent It just went down to the other end For our multiple access scenario We do need this Because there might be several laptops Around an APing If there is a frame in the air Who's it for And who did it come from Ethernet includes this kind of addressing The destination address Actually goes first here That's the first thing that is sent out Because remember here to the left Is this is what is transmitted first So this means the destination address Comes first Everyone can look at it And see if the packet The frame I should say is destined for them There is a whole frame format here We can see some of our framing concepts What we learned before really is useful The frame begins with a preamble here To identify it That's actually a bit of a signal From the physical layer To help with our framing problem The frame ends here with a What's called a checksum This is used in a generic way The checksum is actually this CRC32 Or a 32 bits cyclic redundancy check So that's a check that's used for error detection If you remember all of that That will allow us to work out If something's gone wrong Now interestingly here There are no acknowledgments Or retransmissions Ethernet because it's sent over A wire is usually fairly reliable The CRC is just there in case Something goes wrong to weed out errors But mostly there won't be any errors If there are errors This means since they're not handled by Ethernet Other than collisions That is something that might be thought of As an error that is repaired by Ethernet But anything else that's caught by the CRC Well that will just have to be handled By the higher layers And we'll see some of that much later Okay and before we wrap up on Ethernet There's one important thing That I want to remind you about And that is we've just looked at classic Ethernet Now it turns out that modern Ethernet The kind of Ethernet that you'll see In any building today Does not use this multiple access control protocol It's really based on switches That's these boxes here So there is a twisted pair For instance cable That connects every different computer To a different port on the switch And the connectivity is happening Inside this switch This is called switch Ethernet Or modern Ethernet The difficulty is that everyone will call Both of these things They're all just Ethernet Which can be very confusing But again we've studied classic Ethernet Which is how the Ethernet evolved And it's all about multiple access control Ethernet as you'll find it in buildings today Is this switch form of Ethernet That we'll look at a little later G'day viewers In this segment we'll talk about Wireless multiple access protocols And yes this is it This is Wi-Fi What we've been waiting for So let's find out how it works Okay so our setting here Is the same as the setting That we looked at in the previous lecture We have multiple nodes They just want to share a link How do they do it In this setting however The nodes are wireless Or the link is wireless And the nodes are using that wireless link So we have four different laptops here They're talking to an AP They just need to decide when to send Now to understand the way The protocols work in this setting What we're going to do is build On the schemes we used in our simple wired model So all of that Carriers since multiple access stuff That was more useful than just For classic Ethernet We'll use it as a foundation To understand how 802.11 works today Well the first thing that You might ask is Why wouldn't we just use Some of the protocols we've seen before That were used for classic Ethernet And the reason for this Is that the wireless case Is more complicated than the wired case I say surprise here Because this always seems to be The case for wireless The way signals propagate Across the wireless medium Is much more complicated Than sending signals down a wire And that seems to have all sorts Of implications for how you design The rest of the protocols For a wireless system In our case Just thinking about multiple access There are a couple of issues here One issue is that Nodes can have different coverage areas When you send down a wire If everyone's attached to the same wire You expect that everyone on the wire Can hear all of the messages That's not the case with wireless The nodes might be A fair distance apart And so they might not be able To hear one another clearly This will mean that our schemes Such as carrier sense Don't work very well The second complication is That nodes can't easily hear One another while sending There can be enormous differences In the power level between A signal that's sent and received The received one can be so much weaker That it's difficult to hear both signals At the same time So it's difficult to detect collisions So we'll have to come up With alternatives to that The bottom line here You can see in that The figure at the bottom Is just to remind you That wireless 802.11 does not operate According to CSMA CD We have to improve it So let's see how we do that Well first we've got to go into These two issues The first issue is the different coverage areas Here's what's going on In the figure here We have four different nodes A, B, C and D And they just spread out over space Now the wireless signal is broadcast And as it's broadcast It propagates over an area It's attenuated It can be received By receivers As long as the signal to Noise ratio is high enough And that's just within a region So here it looks like A can send to a neighbor B That's adjacent to it But A's signal can't be received by C It's too far away The signal's grown too weak It can no longer be received Similarly for B, C and D And this leads to Different coverage areas You can see the radio range here Is indicated as just enough To get from one node to the next But not a lot further B by the way When it sends The signal will be received by A But also by C Because that's also within radio range Different coverage areas Lead to problems And one of the classic problems here Is something called hidden terminals When you think it's okay to send Because you can't hear someone Yet interfere and still results So in this figure We have a hidden terminal situation When A and C are hidden terminals When sending to B Let's see what happens Now A and C When they want to send They cannot hear one another's transmissions This means if they use something like carrier sense They would listen And they would hear no one and say Okay, the medium is not in use It's fine to send However, if they both send at the same time Both of their signals receive at B Are received at B Or arrive at B simultaneously Those signals are mixed Superimposed on one another The result is a jumble Two people speaking at once So B cannot separate these messages And receive them It's a collision And we would like to avoid this Because we've just wasted Some of the resource of the link We could have used it To deliver a real frame Instead we got a collision And neither of the frames gets through The second problem that arises Because of different coverage regions Is something that's called The exposed terminal problem Now exposed terminals are a situation When you think you have interference Because senders can hear one another But actually there is no interference At the receivers So you would really like to send Multiple packets at the same time Here B is sending to A So B is sending to A there And C is sending to D And in this situation They are exposed terminals They're exposed terminals Because B and C can hear one another When they're sending It looks like their signals will collide here However C signal doesn't propagate All the way to A There's no problem here So A will be able to receive B signal cleanly Similarly B signal doesn't propagate to D So D will be able to receive C signal cleanly When this situation occurs We would like to take advantage of it When B and C send at the same time Because we'll get more performance out of the network We can send two friends concurrently And get them both through the network The second problem The second complication for wireless Had to do with the inability to detect collisions And that's really because With wires we can engineer the relative strengths Of the transmission and reception signals So we can work out if both are going on At the same time There can be a tremendous difference Between the power levels of the sent signal And the received signal Which might be a million times weaker This makes it very difficult To process them both at the same time So essentially when you're sending You're shouting and you're deaf You can't hear if someone else is talking With wires We're able to detect collisions And because of that we can abort The transmission and this greatly lowers The cost of collisions Takes only a very short amount of time It happens Everyone sees it's happening They stop sending Then we can recover With wireless These two nodes are sending But neither node can hear one another So the collision goes on for a long time This wastes more of the link It's more inefficient So that's why it's a problem So now we need to solve these problems We know that wireless is more complicated than wired What can we do about it We know about a possible solution Which is quite influential And that solution is something called MACA I think it stands for multiple access With collision avoidance You don't need to remember that MACA is actually not quite what's used in 802.11 802.11 users are a refinement of MACA But going over MACA will give you A sense of just how these issues Can be handled if you're designing protocols And it'll help us understand What 802.11 uses The idea in MACA Since we have these problematic scenarios Instead of simply sending The frames directly and maybe encountering them We're going to use a short handshake Between the sender and receiver To find out what's going on And make sure it's okay Here are the rules for MACA With that short handshake Step one here The sender simply Sends a small frame Called a request to send That's very short Packet It sends that request to send to the receiver The request to send Also includes a frame length So it tells you how big a frame The sender wants to send to the receiver next The receiver, when it gets this Replies with a clear to send That's simply Another short packet saying Okay, yep, you know Coast is clear, I'm expecting your frame Go ahead, fine We've just sort of added a bit of preamble And then after all of this The sender simply transmits the frame That's it The interesting part however Is that nodes That heard the CTS stay silent While the sender transmits the frame They can do this because The RTS and CTS including information About how long a frame is So the nodes that hear the CTS know How long to be silent And this is the key addition Of MACA that's going to solve The problems, we'll see how in a minute It's true that The RTS and CTS are just Sort of like short frames And as we send them we could run into Some of these same problems But the RTS and CTS are much shorter Relative to packets They might be a hundred or a thousand times smaller And in this case The collisions since they're a lot shorter Are just less likely so we're running to Fewer problems So let's see how MACA solves some of these First of all hidden terminals Let's suppose that A wants to send to B And C is a hidden terminal that might interfere Okay first of all A sends the RTS Here it is To B That should be received Now I've shown that Next step B is going to reply with the CTS to A To say okay go ahead B sends the CTS to A Great Of course that transmission Which will also be heard by C Right Now C At this stage will say oh boy I didn't hear a request to send You know so maybe Well since you didn't hear that You didn't know anything was going on But luckily C did hear a clue to send So C knows that something is about to go down Even though it didn't hear the request to send Here's that picture Cleaned up so you can see C is now In a state of alert With the wireless Now A simply sends to B C because it heard this clue to send Differs or just waits For this time period to pass So that the transmission from A to B Would be successful Great we solved hidden terminals What about exposed terminals Now A is going to Sorry B will send to A And C will send to D And we want them to both be able to send in parallel Step one Request to send to A C sends a request to send to D Now of course B's request to send Will also Propagate to C And C's request to send Will also propagate to B Neither of those nodes will probably hear the request to send Because they're transmitting at the same time So they can't also receive Next step We've got the request to send there Will also send a clear to send A gets the request to send Intended for it And it's going to reply to B with a clear to send Saying yep go ahead Similarly D is going to send It's clear to send to C and say yep Go ahead Now observe that The clear to send from B doesn't make it to D B only hears one clear to send Everything's good Similarly for C So they both get just one clear to send And This tells them both that they can both go ahead Here's what happens The diagram is cleaned up According to the protocol They've heard their clear to send And there haven't been any problems With either of these messages so everything's good So now we simply send B sends to A C sends to D At the same time Because we're in radio range The signals from C propagate to B The signals from B propagate to C So the situation around B and C Is a mess with superimposed signals This doesn't matter though Because what really matters Is what goes on at the receiver To receive the signal Both A and D have clean reception scenarios Because the other signals Don't propagate far enough to interfere At the receiver So it's interference at the receiver Which is the problem Because we have no interference And that's what we want So we've solved the exposed terminal problem Now that we know how Makka works we can move on to 802.11 or Wi-Fi We've really seen Most of the machinery we need to understand How multiple access works In 802.11 So 802.11 of course Is this incredibly popular land technology That we use today It's been around since the 1990s Getting more and more popular 20 years on, it's new ubiquitous It's really the ethernet of wireless That's everywhere In Wi-Fi, the way it's commonly used These clients, different laptops Or other devices, phones and so forth Get their connectivity to the internet From an access point So they're all wirelessly talking to this access point The access point is typically wired To provide connectivity to the greater internet The key bit we're looking at here Is this multi-access problem Of how these different laptops Get to talk to the AP The multi-access problem Is at the heart of Wi-Fi I'll also point out It's a little difficult even talking About Wi-Fi because Many different flavours of Wi-Fi Have been developed over time So if you really wanted to know any details We have to be clear what kind of Wi-Fi We're talking about But generally I'd say I have gotten faster over time And added many more features We'll see just a little bit on some of this What I'm going to do now Is just talk about the Physical layer and the link layer of wireless The physical layer I'll tell you a little bit about it Just so you know, this will relate To some of the lectures we saw on Physical layer characteristics So you should be able to understand Some of these parameters So Wi-Fi is sending using A 30 or 40 megahertz channel Of bandwidth on these ISM bands The bands that the government opened up For unlicensed usage in about 1985 They let anyone Make equipment that would use it With some constraints but no expensive License like a TV station This led to huge innovation Mostly in the form of Wi-Fi Which is taken off so that was really A very valuable thing to do Of the different flavours of Wi-Fi 2.11B and G And also N They're all different flavours of Wi-Fi That work differently at the physical layer Though the same at the link and high layers Mostly These flavours of Wi-Fi operate on The ISM bands around 2.4 gigahertz And the added 2.11A And N flavours Work around 5 gigahertz So N is capable of working in either one Now they use a kind of Frequency division Multi-plexing scheme To modulate information Over those bands They divide this band 20 megahertz up into many fine channels Which are used in parallel It's actually a form of FDM called OFDM It's more detailed than we're going to have time To go into. You can read a little bit In your book about it if you'd like This is for 8.211 G And A and N G is mostly the legacy form Of 8.211 out slower Has some different physical layer details We're not going to worry about it When we're sending wirelessly Here the different symbols Use different amplitudes And different phases to convey information Depending on your SNR You might be able to distinguish more amplitudes And different phases So you will have many different Kinds of symbols And you can get different bit rates 24 megabits per second Just depending on your SNR And how many amplitudes and phase levels you're using In addition to this Many other bits are transferred across the physical layer To provide error correction In wireless errors are common Just because the medium is very noisy Because of interference So we need to use error correction In the form of error correcting codes To be able to even receive packets And sort of clean them up You might, well Have heard of faster kinds Of 8.211 than 54 megabits per second Various tricks are used Including for some of the fastest Kinds of 8.211 using multiple antennas At the same time This is pretty cool It's well beyond what we can cover in this class But if you're interested You could look at a little article here I recommend it 8.211 with multiple antennas for dummies Would give you a sense of what's going on Let's talk about the link layer Because that's where the multiple access Control problem comes up In 8.211 Multiple access is done with a scheme Called CSMACA It's a carrier sense multiple access Scheme with CA stands for collision avoidance So it's not quite MACA But it's a variant of it And it optionally includes RTS-CTS as part of that RTS-CTS we've seen Although it tends not to be used very much In practice because it's often not necessary For typical Wi-Fi configurations With Wi-Fi Unlike Ethernet The frames are acknowledged And retransmitted with ARQ With Ethernet we just had a CRC32 If an error was detected You threw it away, that happened really With Wi-Fi Because wireless is more prone To errors, many packets Would be lost if we did this So the packets are acknowledged And if they don't get through they're retransmitted Just to up the likelihood of them getting through Now I said Just moving on to the third bullet here That a good thing to do with protocols Is to look at the format of their messages To see what's going on If you do this for Wi-Fi You'll see pretty funky things with the addressing Most data frames Are going to have three addresses on it It's kind of weird You'd usually think of a source and a destination What's going on here So we actually have three addresses Identifying a source and a destination And an AP that's potentially in between them Although Often The AP is really the destination as well Errors here As well as the acts and transmissions We have a 32-bit CRC Just to sort of detect residual problems And there are many, many more features You could read about for Wi-Fi That I'm not going to go into But I'll just mention By way of example That these features include encrypting The contents of the frames You can't read what's there And other functionalities such as power save functionalities So devices can tell the AP That they're going to sleep So they can save on their battery Finally Let's look at this 802.11 CSMA CA scheme for multiple access To see how it works It's somewhat simplified Compared to MACA Multiple access control is the subject Which hasn't really been definitively solved For wireless There are different variations around And they sort of work okay, but none of them are quite ideal And so this is just what 802.11 Does as a reasonable trade-off Instead of using RTS-CTS Most of the time You can optionally do that as well What 802.11 does is It avoids collisions By inserting small random gaps Instead of an RTS-CTS If we have these small random gaps That's why you don't need RTS-CTS Always So in this scenario We have a timeline here Time is just going from left to right Across the page And we have timelines for three different centers A, B and C A is going first A is just sending a data frame There's also going to be an AC after that Because that's how wireless works Unlike Ethernet I know that's not shown here Now let's suppose that B and C both Want to send While A is sending Here, B is ready to send its packet But it uses CSMA It senses the medium and it hears A A must be talking to the AP or something Similarly, C was sending Oh sorry Not sending, C became ready to send While A was sending It heard A So both B and C are waiting to send Eventually A is finished It's data frame and AC frame is done What happens? If we just sent right away As is the case with Ethernet We would run into a collision We would waste a lot of the medium It would be a problem Instead Both B and C Insert small random gaps Here's a small random gap C inserts this random gap Waits after this much time has gone by Let's just pack it here There's the data frame Followed by the AC B happened to choose randomly A slightly large day Even though it was very first Everyone picks a random one And its roll of the dice was bigger It waited this long And then it stopped here Simply because it heard that C was sending So it suspended its timer After C was done It continued counting down its timer B got to send its frame And in this fashion By inserting these small random gaps Just to sort of test and allow Someone else to use the medium And see who's waiting to send B and C, even though they both wanted to send Have ordered themselves And they both got to send their frame These back offs Are sort of wasted time Vital time on the air And this is the cost of using wireless But these back offs are small So we do okay in wireless And finally Just to wrap up 802.11 Let me just talk a little bit about Some of the future trends for 802.11 802.11 is a key technology So I thought it might be interesting Just to do this Now I don't really know what's going to happen With 802.11 of course So this is just a guess Firstly, it's likely that 802.11, well it's already ubiquitous It's likely to become more ubiquitous But really all devices these days Seem to have an 802.11 Nick for a wireless connectivity What's likely to happen here though Is that we'll have greater diversity You can have very fast computers High end computers and very low end Computers, wristwatch or whatever Can all have Wi-Fi And all want to use the same AP So now the nodes are not generally Equaling capability like a laptop Some are more powerful, some are less powerful That will affect the protocols Small and subtle ways We can also expect a lot of innovation Everyone wants to be able to send More information across Wi-Fi It always seems to be getting faster This is likely to continue And maybe more so than simply getting faster Wi-Fi is likely to get more power efficient So that the nodes that can use it If their battery operated Don't deplete their batteries so quickly This kind of innovation Is very much driven by physical Air technologies As these technologies advance Wi-Fi just sort of gets better Even without the Mac layer changing very much And finally I'd point out right now That Wi-Fi is a bit of a hassle to use It's quite manual in terms of identifying What access point you can use For which you have credentials Typing things into web pages and so forth It's also a little limited in that Transmissions go through an AP Even when you have two devices In the same room most of the time It's often more easier to use something Like the cloud Dropbox or something to exchange files Than Wi-Fi even when your devices Are in the same room That's just wrong in some sense So we're likely to see more Seamless integration of Wi-Fi Into the massive connectivity That devices have Then people would have to be less involved In setting up and configuring Wi-Fi This is likely to happen over time Okay so now you know about Wi-Fi Good day viewers In this segment we'll talk about Contention-Free Multiple Access An alternative design to the method Of multiple access used in Wi-Fi And Classic Ethernet So in Wi-Fi and Classic Ethernet The multiple access problem is solved With randomization What we'll talk about in this video Is a completely different technique Which is based on taking of turns So in this picture here The four nodes might take turns From left to right Before we get into the design Of turn taking multiple access protocols One issue we need to talk about A little bit is why we would bother Why aren't random multiple access protocols Good enough If they were after all There's no need to worry about These different turn taking protocols Well it turns out that CSMA The carrier sense multiple access method We looked at For Wi-Fi and Ethernet Is good under low load It's very effective there And the reason is that it grants Immediate access so there's no delay And under conditions of low load Few collisions are expected So the overhead is very low But the issue And the reason we're talking about Turn taking multiple access Is this bullet here Randomized schemes are not so good under high load The issue is that under high load You expect collisions And this leads to a high level of overhead It's also the case That the access time varies A node when it tries to send Is unlucky Try and send And get its packet off right away Its frame off right away Or it might get unlucky It might have suffered repeated collisions And so it might take a long time For its frame to be sent We would like to do better Under conditions of high load With turn taking multiple access protocols The protocol is to find an order In which the nodes send The order is really an opportunity to send It's a chance to send So if you have a frame When your turn comes around You get to send it If you don't you just pass And the next node gets turned to send a frame All we really need to do To come up with these protocols Is to devise some ordering I'll talk about one on the next slide A method called token ring But you can imagine other methods For instance the nodes could use their addresses To impose an ordering From lowest to highest Or vice versa In terms of who gets to send next So with token ring The physical topology Is used to provide the ordering The nodes are wired together In a circle, in a ring And then a special frame Called the token Is put on and sent Around the ring You can see the token here And it's going around the ring And clockwise As the token passes the nodes It gives each node The who has the token An opportunity to send They grab the token Then they Instead of sending it on The first of all they send their frame And after their frame has been sent They then pass the token on to the next node Further along So the sending order here is going to go one The token has gone to node two To node three Four Five Six Seven Eight Nine And then we're back and so forth That's our order And that's token ring in a nutshell This kind of turn taking protocol Token ring As well as other turn taking protocols Do have advantages In this scheme There is a fixed overhead With no collisions The collisions are gone As a source of overhead And in particular We won't have an increasing number of collisions Or a large number of collisions As the load gets high Just the fixed overhead Because of this The turn taking protocols Are more efficient under high load We also get a regular opportunity to send This leads to More predictable levels of service You know that you'll get to send a packet Every say a hundred milliseconds or so And the concept is Easily extended to different qualities of service As you might imagine We could just allow one node To send say two frames Every time we've got an opportunity to send Instead of one That way we get to send Twice as much traffic As another node If it was a high priority node for instance There are some disadvantages though And the principal disadvantage Is this complexity There's more to this protocol Defining the ordering And imposing it And that means that there's more to go wrong What could go wrong? Well just as an example What would happen if the token was lost? Now this really shouldn't happen The token's just a frame going around the ring But unexpected things Can happen occasionally Let's just suppose that the token is corrupted By bit errors And it's too corrupted For any error correcting code That's used down there to deal with Or even an error detecting code To recognize that the token's in error To be repaired If that were the case The token might suddenly appear to disappear And then the whole protocol would lock up And if you can't send Until you've got the token And there is no token Boy you just never get to send That would be no good So we'll obviously need to guard against that How? Well Token ring protocols in practice Have every node Have extra machinery To guard against these kind of failures Know it's my run of timer For instance And if they haven't seen a token for a long time They might decide there's been an error And the nodes would collectively Mint a new token They'd work out who would do it They would have to coordinate So they didn't have to have multiple tokens And so forth You can see that even though Losing a token is a rare case It can add considerable complexity To the protocol There's also a somewhat higher overhead At low load The overhead of token ring is fixed Just passing that token around But it's non-zero And at low load CSMA or randomized schemes Have almost no overhead whatsoever Today viewers In this segment We're going to talk about switches Which are a very widely used technology To connect computers together Into small networks inside buildings Okay so we've talked about Multiple access schemes a lot Now they are very widely used For wireless networks 802.11 was the popular example But when we're using wires Rather than have the host run a multiple Access control protocol The method which is used today Which is vastly more popular Is to connect all the hosts To a switch device in the middle You can see in this figure at the bottom here I have four different boxes Which are all wired to one switch The switch will provide connectivity Between all of these different devices This architecture is the basis Of switch Ethernet Or modern Ethernet And it's used ubiquitously To tie together computer equipment In all manner of buildings Let's just drill down in a little more detail So the scenario is like this Inside your building, your home Your office, the campus You have different hosts And these hosts are connected By a twisted wire cable A twisted pair cable typically To a box called a switch This switch has many ports So you can connect many different hosts to it Somehow, this switch Is going to provide connectivity Between all of the hosts Because we're still operating in the link layer When they send frames The frames will go From one host to the right other host Typically the wiring Is done so that the switch Will be in some kind of central location And all of the wires in your building Will be run to a wiring closet In a convenient location So the big question for us Is how do we make a box To provide all of the connectivity That's a pretty interesting question If you remember back to our diagrams On protocol layers I said something like this That all of these different kinds of boxes There are many boxes That have cables attached to them They're distinguished by the functionality Of what goes inside And we can draw different kinds of protocol diagrams To describe the processing that goes inside In a hub Box or a repeater box The switches The devices operated the physical layer So they're really just connecting bits Around moving bits around In a switch device that we're looking at now The functionality inside the box Runs a link layer So it's connecting frames From one port to another port And in a device called a router The functionality inside the box Works at the network layer So it looks at the details of IP packets In the case of the internet To work out which way to send them We'll get to routers later on So we're not going to look at IP packets and routers now Instead we're just looking at Switches Operating at the link layer Sending around ethernet frames To understand that We'll go over both hubs and switches Because this will show us the difference between the two We'll start with hubs These are physical layer devices In a hub Inside view for what could be going on inside this box We have all of the different lines coming in These lines come from some hosts They attach to the ports inside the box If this is a hub As a physical layer device You could simply imagine that all of the ports Are wired together This will provide physical layer connectivity And that's all we need So for instance, if a frame comes in On this port from some host And it's all wired together The same frame will go out On all of the other lines Functionally This is equivalent to the setting on the right Whereas if one host Sends onto the wire The frame will be delivered to all of the other hosts It's just another way of wiring it It's generally more convenient Than winding one long wire through All of the different offices Because now we can run twisted pair To a central wiring closet It's also more reliable If we lose one particular wire here Well Some host is out of luck But chances are that the rest of the host Are still able to communicate However, if we break This wire here You Generally do more damage You might have broken your land in half It just doesn't work anymore The signals get messed up too Inside a switch Something very different is going on That looks like the same box Switches operate at the link layer So as the frame comes in now The switch will look at the link layer information That's the source and destination Ethernet addresses To be able to forward this frame Out the right output port This means for instance That if let's just say I just number these hosts 1, 2, 3, 4 If I send a frame in here It might be destined The host on port 4 I would then send it through the switch fabric And out port 4 At the same time The host on port 2 Might be sending A frame To the host on port 3 Using a different path Through the switch fabric The switch fabric here is shown as a grid You could just imagine this as You know almost a street map And traffic lights The switches that are on the frame Different kinds of traffic lights Or switches here have been turned on or off To connect different input ports To different output ports And so that is how We can use different parts Of this switch fabric To connect different input Hosts to different output hosts At the same time Here's just a clean up of that figure Where 1 is sending to 4 and 2 is sending to 3 At the same time A couple of other things First of all I just sort of draw a line between the host And the port here to represent a link Typically for all switches you get today This is a full duplex link So even though I draw one line Really you might think of this as having Two halves inside the cable There's usually a Y going one way And a Y going another way to make it full duplex And this port really has an input And an output port structure Yes, so they're full duplex Also what that means Is that I can use Because I can do the sending in parallel There's no multiple access control Protocol for a switch The host just send the frame into the switch When they're ready And the switch will deal with making All of the right connections To send information at the same time This is quite different than a hub For instance with a hub When one host sent The message was received on the wire At all of the other hosts This means that two hosts couldn't send At the same time Those hosts need to use a multiple access control protocol To coordinate their actions With a switch there is no MAC protocol Though what lines are full duplex They send into the switch The switch works it out This new method Of working however does pose some problems There is a lot going on inside a switch In particular In particular You might wonder what happens If two different inputs Are sent to the same output So let's say That the first host here Is sending a packet Through the fabric To the same host on the output side Well What happens if all of the other hosts Are also sending there It's just a very popular destination So we're all sending through the switch fabric To this one output This can't happen at the same time If the lines are the same speed Only one Frame could be going in Or out of a given port Maybe in and out if we can use it By direction at the same time The other frames which are coming in from other ports Which are destined for this one port over here Will need to be stored somewhere temporarily For this reason A switch has buffering Either on the input side of the switch Or both You can see I've shown the buffering here As the pink here So this is a little bit of storage memory To temporarily store frames Until they can be sent on an output port The right output port The issue here however Is that This buffering is fine If there are very short term mismatches Two hosts sent to one given output And it took two frame times To send it out But it's not going to work Even buffering won't solve the problem If these hosts are sending To a If multiple hosts are sending to one output In a sustained manner If that's the case The frames will build up inside the buffers Eventually the buffers will be full And we will have loss Now this Is an example of some kind of Contention or congestion Happening inside the network Because of this loss As you send packets or frames Across the network they can Almost disappear inside the network They can be thrown away because the network Could not support the traffic pins We're going to look at this issue much more Later on when we get to TCPAP Because this same sort of issue Happens as you send packets across the network They can be lost due to lack of buffering Inside switches For now we're not going to worry about it too much We're going to say if the switch is well engineered It can happen but we hope it won't happen very often So switches And also hubs Have some significant advantages Over just connecting all the hosts To a single shared wire As was the case with classic Ethernet Hubs and then switches Became possible Really due to Moore's law As electronics sped up greatly And also became a lot cheaper And nowadays they're prevalent They're what you find everywhere It's just possible because of technology But they have definite advantages It's more convenient generally To run wires to one central location Rather than to sneak it through the offices Imagine what you have to do to change it If you want to add another host And you've just got this one wire They're also more reliable as we said before In that if the wire fails You might lose a host But you probably have connectivity For all of the other hosts in the network This is different than a classic Ethernet If there's a break in the Ethernet Actually it doesn't work for all hosts For electrical reasons You may wonder if the switch itself Is a problem for reliability It is after all a single point of failure You blow up the switch You lose connectivity to all hosts That's true But if you lose connectivity to all hosts You know exactly what to do Go find the switch, take it out And put another one there So it can be repaired fairly easily The other key advantage For switches is this Switches offer scalable performance This is a real win With our single shared cable Maybe you have a 100 megabit per second cable You attach 10 hosts to it Each host's fair share Is maybe 10 megabits per second of bandwidth With a switch Because we can send frames in parallel You might provide 100 megabits of bandwidth Per port So every host Is able to send and receive it up to 100 megabits per second Performance is much more scalable For these switches I'd like to go into one particular issue For making switches work You might have wondered as they talk through there How switches, if they deal with Ethernet frames Find the right output port To which to send a frame This would be easy If frames carry port addresses Send me output port number 7 But they don't The addresses which are on these frames Are Ethernet addresses They indicate a host Either the source host Or the destination host Now that destination host Might be plugged into any port On the Ethernet switch We could imagine Having someone manually Configure a big table This would be a terrible job to have That's exactly what we want computers to do So let's try and solve it with an algorithm And we also want an algorithm which will allow Hosts to move around You might move your computer to another office And connect it to a different switch And that should be okay too So we need to find some way When frames come in And we just have a source and destination address To work out what output port To send that frame to The algorithm we use To solve this problem with switches Is called backwards learning It works as follows The switch needs to build up its own table That maps between Addresses and ports So it knows which port to use It does so as follows Step one, first thing we do Is we build up this table An insight to allow us to fill in This table without having any human Configure it is to note That Ethernet frames carry both source And destination addresses So if you see a frame on a port You can look at the source address and say Well, you know, I see a certain source address So this port is where This address lives If I ever see a frame Which is destined to this same address Now I know what port to send it on So you look at the source address Of the frames to find out what port they're on That's the backward bid and backward learning Usually you might think you just look At the destination to work out Where to send the frame But by looking at the source We can also work out where people live To forward these frames You just got a frame on an input port Destined for a particular destination What do you do You look at your table If you know the port where it lives Because you've learned it earlier somehow Then you just send it to that port And you're done What if you don't know, what do you do In that case you broadcast it By sending it out all ports You just say I don't know It's attached to some port That way it's going to get To the right port destination It'll also get to a lot of other ports And they'll just have to ignore it Let's see how that works in action So the very first time The network's used after it's powered up A is going to send to D No one knows anything at this stage So A's frame comes in It just says hey I'm a frame from A I'm trying to reach D is the destination address This switch is clueless It's just been turned on There's nothing in my table So therefore I'm going to broadcast this frame I'm going to send it out all ports It reached D That's very good It also reached B and C Oh well Not a very efficient use of bandwidth We also learned something here We learned that A is on port one That's a valuable bit of information So this is what happened Now step two Let's assume because most communication Evolves requests and then replies Sometime later D is going to send a frame Back to A What will happen? Here's D Sends its frame in destined for A This stage the switch can look up It's table here and say yep I'm just going to send it directly out that port Wonderful We did not have to broadcast it out the other ports Here we are, cleaned it up I just changed the color so you can see them Oh I should have said we also learned something We also learned that D is on port four By looking at the source addresses The frame came in This is the normal situation Now everyone sent a little bit of traffic And we've learned Because if they're using the network They're going to send some traffic Then we learn what port they're on Now we're fine Let's imagine now that A Happens to send another frame to D The frame will go into the switch It'll come in port one The switch will know yep D port four Now we're sending frames Between the port one And port four between A and D Fine without broadcasting And sending extra traffic to other hosts That just happens once And this mechanism is fully automatic We've learned how How to get from one port to another With no configuration From a human and in a way Which is fairly efficient So that's pretty cool There's something actually that's even cooler about this This same mechanism works If you run it independently In the different switch, they're shown here as B1 and B2 Even if you have some hubs in there here too By the way, there's a hub in here H1 Assuming there are no loops in the topology This is a crucial assumption We're going to want loops in the topology At least we're going to want to allow them So in the next segment We'll handle the case where there are loops in the topology But now we're assuming there are no loops Then the mechanism I've shown you Has solved a problem Let's see what would happen When A sends to D and then later D is going to send to A OK, A sends to D Here the frame comes in Beginning of the world, everyone's just woken up This switch, B1, has no clue This switch says, OK, I will broadcast it Out all of my ports Because I don't know I'll also remember that if I ever want to get to A I use this port, port 1 OK, so this frame Is going to go to host B and C I'll also go over this link And into switch B2 Through this input port B2 actually doesn't know that it's come from another switch As far as B2 is concerned A could be directly connected here It really doesn't know You can't see the overall topology But B2 runs exactly the same algorithm It gets something in From A, destined to D It's clueless also It learns, hey, A is here D, no idea That's what we do, we broadcast if we don't know It'll go to D Yes, that's what we wanted It'll also go out here to the hub The hub by definition Wires everything together So it will go out the other ports It'll reach E and F So A's frame went everywhere But at least it got to D Here's that again And now let's look at what happens next Now D is going to send to A Here's D's frame comes in There's one on this switch It wants to get to A Well, switch B2 Actually remembered that the way you get to A Is you send out this port So it'll simply send it out that port There's no need to broadcast It'll come in this port Switch B1 As far as switch B1 is concerned This could have come in directly from D D could be plugged here, it doesn't know Switch B1 Looks at the destination that's A No worries, done No broadcast, we now have an efficient way For D to send to A And of course, you know where I'm going here You can work through yourself the case of how A Sends back to D And you'll see that we're using the switch very efficiently So this algorithm extends naturally To topologies with multiple switches And hubs That's pretty cool Now you know a lot about how switches work This is how a modern switched ethernet works We've just In one condition and that's There might be loops in the topology I'll get to that in the next segment G'day viewers, in this segment We'll talk about the spanning tree algorithm Which will complete our understanding Of how land switches work Okay, so in the previous lecture I talked about switches Modern switched ethernet How hosts were connected to them And how they forwarded frames So thus providing connectivity Between all of the hosts The solution we made was that the topology In the way these switches were connected Could not contain loops Now I'd like to talk about how we can allow These switches to be connected in ways That do contain loops And still have the overall system work There are a couple of reasons you might want To have a loop in the topology You might simply want some redundancy In your network You can see here on the diagram On the right I've added a redundant link In the middle between the two switches In the middle You might do this simply because one of them Might fail and you'd like to provide A little bit of redundancy ahead of time So if there is a failure There are still links in the network So it can work You might also make a simple mistake Networks evolve over time I think components are always Been added and removed And it would be very easy for someone To plug a cable into the wrong port And inadvertently create a loop This could happen and we wouldn't want a simple mistake To take the whole network offline And have it not work So we would really like For these LAN switches to just work To provide very much A plug and play environment LAN switches in fact are some of the earlier Plug and play computer networking That just works I guess Ethernet does too But LAN switches are really an extension of that We also want to do this One of the constraints for the design of LAN switches For Ethernet switches Was that the switches should work With no change to the hosts So we don't want to have to go and upgrade All the software and millions of hosts Just to be able to connect switches with loops But if we don't Do something Compared to what we've seen so far We have a major problem with loops Let's look at that for a minute What can happen? So suppose that the network is started And we have our network here And we're able to host A through F What's going to happen? I think I'm just going to overwrite On this diagram And draw a series of frames A sends to F Well at the beginning of time No one knows where anything is So they're just going to broadcast frames A's frame goes into C C gets it, C will broadcast So we'll send it out the other ports That's what we've got to do initially So it went to B and it went to D Twice Because we have a loop in our topology D, well now let's just look At the first of these frames it gets Consider the right one first D will get that frame in And then it will send it out everywhere else To F, to E It will also send it back to C On the other port to C Oh boy, you can see that things are going to go A bit south here D will look at the second frame that it gets This is from D on a different port Now it doesn't know this is the same frame You might think we could just look At the contents, but you don't know Whether this is a second message from A Or not, we really have no way of telling D will then send this frame Out to E and F And of course up the other link back To C Wow, E and F are now not so happy They've now received two copies of this And they didn't want, well at least E Didn't want any of them Not done yet We now have these two frames that have gone to C Let's look at the one on the left It went to C, what does C do with it It broadcasts it because it still doesn't know where F is Hasn't seen any frame from F Goes out to A and B and down to D On the other link And similarly For the frame from D to C The second one, it will come up Go out to A, B And down to the other link Back to D Now, this diagram is getting very messy If you follow some of the logic through I could write all this down I think I'll do that on the next slide You'll see that we have something nasty going on I'm just going to draw a big massive circle here Some packets are spinning around here left to right There's another series of packets Spinning around here in another direction And traffic has been forwarded out To all of these nodes A, B, E and F As we go around this loop So we have a storm here in the network One packet was sent in by A It never ends, traffic keeps going around the network And fresh copies of packets have been delivered To all hosts on the edge This is really nasty So here is just the beginning of that logic Spelled out for you a little more In terms of who sends where So you can follow it through And it just goes on and on It never ends, so a forwarding loop here Is something pretty nasty to happen The solution that we'll come up with To prevent this problem And we would really like to nip this problem in the bud Because you can see that one packet Can cause devastation here with the loop The solution we'll use is for switches To collectively find and agree On something called a spanning tree A spanning tree of the topology A spanning tree is simply A subset of links of the topology Which is a tree So it has a root and branches out from the root But it has no loops In that topology The subset of links In the spanning In this topology Is a spanning tree, if it's a tree And it spans the topology It reaches all switches So it will allow us to deliver Frames to all hosts on the network Once we find this spanning tree This is the first step The thing we want to do We simply use it as before Switches simply forward frames Along the spanning tree So they just Pretend that the topology was only the spanning tree If we know which way to go Grady will get there If we don't we're going to broadcast And if we broadcast on the spanning tree Frames will tend to go Up the spanning tree to the root And then down all branches So they'll get everywhere But they won't loop You know this sounds pretty messy With spanning trees I'll show you some examples To get a sense of what a spanning tree is And then I'll talk about the algorithm to find one Here on the left we have the topology This is the links which were Physically installed in the network Now I want to talk about some spanning trees There are actually Usually there are many different Possible spanning trees for a network Let's just see some of them Let's just pick a node here arbitrarily Top left one as the root of a spanning tree How are we going to create a spanning tree Let's create some branches Let's say I go down here and here And you know I'm just going to say There are only two branches in the tree So from here I'll go up to here And from here I'll go over to here This then is one spanning tree It reaches all switches in the network I can cross out the links we haven't used Okay, fair enough Here's another spanning tree Just to show you that multiple ones are possible I'll select a different node as the root From here I'm going to just arbitrarily And from here I'll divide I'll just say I'll use this other branch here That's going to reach these switches And a different branch here will reach these switches In this spanning tree I don't use these three links Of the topology These are all different Possible spanning trees Of course in our automated solution We're only going to want to choose a single Spanning tree and everyone agree Which spanning tree we'll use Here's that same diagram cleaned up Oh You can see Oh, it looks like in this example here Sorry, I chose a slightly different spanning tree This is just yet another possibility Instead of going here I went over here Okay, well that just shows you Yet another spanning tree But conceptually The point is exactly as I'm saying Okay, so now we need an algorithm To find the spanning tree We've seen there are few I can't even agree Amongst my slides on which spanning tree Is which one But we want all of the switches to find A single spanning tree Then they can use it How are they going to do this It's a little complicated Or subtle Again because this is a distributed game You know If someone Like you or I could just see the network We could draw a spanning tree and say Here use this But the switches can't do that Firstly every switch runs the same algorithm There's no special distinguished Switch which is in charge This is actually helpful because then there's no Switch that can fail and throw your network into chaos All switches can handle What's going on in the network These switches are going to start With no information because we don't want to Have to have configuration or make assumptions Now switches can only See what's going on with themselves They can send and receive messages But they don't know what's happening In fact all of the switches are not only doing this But they're operating in parallel Because they have no way to otherwise coordinate Their actions with other switches As they operate in parallel and send messages We want these switches to continually Search for the best solution If we do this We will end up If we can solve this problem I haven't told you how to yet We will end up with a highly robust solution We'll work for any topology With no configuration Because we assume that we start with No information and have no special Switches or position in the network It will also adapt To link and switch failures And the reason that we will try And do that is that we'll have The switches continually search For the best solution And we'll have them throw out information About nodes that's not Repeated over time so if there's really Old information about a switch that you Haven't heard from for half a day You'll eventually forget that And find the best solution in the network That you believe exists now And that way If some component fails You'll converge to another spanning tree Which uses the nodes that are in the network And cut over maybe From a failed link to another redundant link I'm getting a little bit ahead of myself Let's work through some examples To see this spanning tree algorithm Because if you haven't seen algorithms like this There's a lot to it And I'll just tell you That the spanning tree algorithm That I'm going to go through Was pioneered by Radia Perlman She's shown here, you can see her picture She did much of the early work On different kinds of Spanning tree and early routing protocols In the internet She worked on different kinds of routing In the internet, the spanning tree algorithm We're going to look at And also different kinds of link state routing In particular link state routing When we get to IP networks Nowadays she works on network security But what we need to go through now Is the spanning tree algorithm Here is an outline For that algorithm These are the steps that will happen First of all To come up with a particular spanning tree We need to elect a root The root could be any node That's possible, they just need to agree on who it is So we're going to let the switch With the lowest address be the root The switches can use their addresses to look And send messages and agree on who's the root When we have the root We are going to Grow the tree From the root using The shortest distance from the root As a way to decide what branches are on the tree If we have ties Because from one particular switch You can get to the root by two different paths Of equal length We will again use the lowest address As a tie breaker to decide Which branches Are on the spanning tree And when we have the spanning tree We'll then simply turn off Any of the links, the ports Which don't forward onto the spanning tree And we can then use the spanning tree To forward using our learning algorithm Now actually One thing that's slightly complicated Is that steps one and two happen in parallel There's no phase one and then phase two This kind of logic is interleaved Whereas once things have stabilized Then we proceed with turning The ports off and using the tree for forwarding Okay now in a little more detail I've said what these nodes want to do Find the lowest node Grow a tree out From that node But they do that by sending messages So here's a few more details on the messages they sent Initially Each switch is going to believe that it's the root of the tree That sends its messages And every switch is then going to follow This same behavior Every switch Will send periodic updates to its neighbors These updates Will contain its address The address of the root And the distance in hops to the root So an example is shown below here Here's switch C It's sending out a message It might say to its neighbor Hi, I'm switch C And it's two hops away from me We will abbreviate that message As CA2 When I write down what happens Or the state of a switch Now all different switches Are going to get messages from their neighbors And they're going to process them When they hear different messages Switches are going to Update their configuration And they will favor ports Which reach better roots Lower cost roots With shorter distances Again using lowest addresses as a tiebreaker And it's quite amazing Really that if all switches follow The simple process This rule, this one two punch rule An update, the network as a whole Will converge to a single shared spanning tree Wow Okay, let's see how that could happen This is kind of tricky stuff We do need to work through an example To see what's going on Okay, so in the beginning All nodes here have a simple topology With their state Everyone thinks they're the root And they're just zero from the root Now In every round All nodes send out messages to their neighbor With their state And then they receive the messages from their neighbors And update their own state Let's look at the kinds of messages That are sent out I'm just going to pick one node So node C, this is its state To nodes A B and D, D twice They'll all get these messages And similarly, every other node will send that information To its neighbors Having got that information, they'll then update Node A, for instance, will hear from node C But A will say, well My state's better, I'm a better root Node B Will get messages in From node C And node F saying that they both think they're the root And node B will sort of say, well rubbish I'm a better root than either of you, so I'm sticking with my state Some people will change though Let's imagine node E Node E will send out And it will get messages back from D and A Well, guess what A is lower than E D is lower than E2 So E will actually hear two better messages The best one is A So E will be forced to update its state It will say, oh, okay, well, I'm still E But now I've heard this is root A And I am distance one from it The message from A is saying it was zero hops away Similarly There are going to be some other updates C is going to update To say C, A1 C now thinks A is the root And it's next to it D will also update D will actually think The best thing it hears here is from C It thinks it's next to C1 Now, I can also see here That F will update To be F From B is its best option And it's one hop away So that is the new state of nodes Let's go to round two now Round two, I've replaced the diagram I've updated the state of nodes All of the nodes send these messages Out to their neighbor So C sends the message C, A1 Out to neighbors A, B And D, twice, for instance What's going to happen? Well, A still sticks with its configuration It's the root No one can beat it B, as it gets This message from C Let's see here Unfortunately, B learns That it is not the best option B will update its state to be B A2 It's two hops from A A is a better root than B And it's going to reach The root through C C is going to keep it state It won't change D will actually update too D will hear from both E And C that there is a root A In fact, D could get to the root A By two different routes It could either send via C to A Or E to A D is going to decide that it will send Via C To reach A Because C is a lower address than E And D state is going to update From DC1 to D A 2 And I think everyone else Is about where they were Okay, so here it's cleaned up Third iteration Everyone sends out their state again We process to receive messages What happens? This is a lot of work How long can this go on? We'll see Okay, A And B And actually C and D remain where they are Now you notice here for D I said that D Is going to reach the root via C On the left-hand side There were two possibilities Actually both of these ports will have addresses So D will be able to choose the lowest port That's just a quote there E Yep, E stays the same F However, he's going to update F is going to hear That there is a better route Because B sent this message out Saying I'm B You know there's this route A I'm two hops from it D actually will also send a message out And F will update its state To be F A 3 Well, I think we've finished now Let's see Which steady state has been reached Every node will now continue To send out its message But nothing will change The algorithm will continue to run And it will time out information So that for instance If node A fails Then eventually other messages Other nodes switches here Will discard the messages from A And forget about it Because it really doesn't seem to be there anymore B will become the new route And that new spanning tree for B Will be computed and then used We can see how the node Will be used We can see how the spanning tree is used Forwarding proceeds just as usual According to the backwards algorithm The backwards learning algorithm So let's see that The network has just been turned on D wants to send to F What's going to happen? Well, now since no one knows where anyone is Everyone will forward cast Out a broadcast And forward out all ports We're only going to use ports on the spanning tree though That was our restriction So D sends to C C sends to A and B A sends down to E B sends down to F Got it, we've reached F Now when F sends back to D We're going to proceed along the reverse path Because now this switch F knows that you get to D Through here And A knows that D is down here And C knows that D is down here We're more efficient sending back From F to D In that we did not broadcast Over our spanning tree So we didn't reach all switches on the network Nonetheless You might have noticed That we didn't really use the best route There was a link here between D and F But our spanning tree didn't include it So we didn't get to use it This should give you a hint That we can do better than the spanning tree We'll see how when we get to the network layer And think more about routing We can come up with better algorithms Works well In that no hosts were changed That we've solved this problem It's completely plug and play And we can handle any topology This slide cleans things up Just shows you some of the transmissions In different colors I don't know why I think I see one area here There are two areas here I'm just going to cross one off There should only be one A will only send to E once I've written down just the transitions here So that you can see them So the forwarding And if you're sort of wondering How you would remember all of this Here's a poem, an algorithm That Radia put together She came up with the spanning tree When she was at deck Well it initially seemed like a very difficult task It proved to be easier than she thought When she worked at how to think about it She did that in the early part of a week And it gave her enough time to write a poem So there you have it You can see this algorithm And now you know how LAN switches work G'day viewers In this segment I'm going to give you an overview Of some aspects of the network layer And we'll go into more detail in these aspects In the following lectures Okay so first of all let's look at where we are In the course Well we're starting the network layer That's where we're at And yes this is IP This is the unit in which we'll learn As you can see from this Reference model We've gone through the physical and link layers So you know how to send information Bits across a link Instead of signals And you know how to send frames of information Across connected links That's great Now we're going to move on to the network layer The network layer builds on the link layer And its job is to have routers Send packets of information Across multiple connected networks So let's see how that works Well actually before we do that One of the first questions I'd like to talk With you about Is why we even need a network layer in the first place Now we've already seen With switches and links That we can build small scale networks So here's a small scale network And if we follow all of the ideas We've seen so far We would be able to send frames From one computer to another computer That's connected somewhere to those switches Pretty good If we can do this already We should ask what it is That we're going to get out of a network layer Since a network layer would seem to be doing Much the same thing Sending packets across all of the hosts And routers that are connected together Across many networks Well I'm glad you asked There were actually three shortcomings Of the switch approach we looked at That I remarked on very briefly At the end of that unit The thing was that the method we looked at Didn't really scale up to large networks Now as your network gets larger It goes from tens to hundreds To thousands up to millions of different hosts Think for a moment About how the switching approach would scale A couple of things happen One, A, there is a blow up Of the routing table So that's this situation here Every different switch in this diagram Is keeping a table Which maps for every different destination Which way to go That table is going to have millions of entries With our switching approach As the network gets bigger That's a lot, everyone needs to maintain this table A second issue Is this broadcast That's here And you remember to reach new destinations That they haven't heard of before Switches broadcast This means that the first time you send to a new destination It could get sent across the entire network Imagine sending a packet To a new destination And having it go through millions Millions of other hosts on the network Just because you weren't sure which way to go So this design doesn't scale As well as we would like A second shortcoming Is that the switch approach we've seen Doesn't work across more than one Kind of link layer It's a link layer approach So it's designed for a particular link layer Now we've already seen different kinds of links We've seen Ethernet inside Wide enterprises Ether to 11 inside many houses And 3G for cellular Mobile connectivity There are different kinds of links from our point of view We would like to be able to network them All together and send packets From an Ether to 11 Host through to a host On a wide Ethernet But the switching approach We've seen so far doesn't really take this into account It isn't equipped to join These different kinds of link layer technologies Together And a third reason Is that switches don't give us much control Over the routes which are taken Through the network The spanning tree algorithm we looked at Is pretty impressive really And that you can just plug your network together However you like And the network will be able to find A spanning tree and get packets From any host to any other host But it didn't guarantee that the paths Which were taken were necessarily very good ones Traffic in our spanning tree network Might follow this path Say from one switch to another We might go along this path of outline When in fact there was a direct link Which would have gotten you straight there That's not what you would necessarily want Because usually the most precious resource In a network is the network bandwidth On all of the links We would like to use it well And to do that we want to have good control Over the paths that packets take Through the network So when we look at a network layer approach We're going to see ways in which We can improve on all of these shortcomings We look at ways to scale The network Essentially instead of sending To an individual destination We'll be able to do all of the routing And forwarding through the network Of the wall of the work at routers In terms of blocks of IP addresses Called prefixes This is applying hierarchy So that all of these different routers Have smaller tables that won't necessarily Need to have millions of entries For millions of hosts We'll also see in the network layer Support for heterogeneity IP uses an approach called internet working In which different link layer technologies Are put together And we'll study IP really as The big case example here In which there's a lot of experience In what you have to do to make an effective network And finally Eventually we'll look at different ways Of having better control over how you use bandwidth Rather than the spanning tree We'll look at lowest cost Or shortest cost routing Which is a different framework For deciding which way to go And eventually we'll even look at quality of service Although that will come later in the course Quality of service is really also About different ways in which You would make good use of the bandwidth you have Okay so this slide here Gives you a topic list Of what we're going to go through in this unit It's fairly detailed and I don't expect you to understand All of the terms here right now You can use it as a roadmap For the units that All the different topics in lectures That we're going to go through in the different segments First of all I'm going to tell you About different network service models As well as a traditional Packet model, datagrams There's also a virtual circuit model So there are different possibilities for networks Then we're actually Going through different segments on IP IP is the big example From which we can learn a lot About how to build networks As well as understanding how the internet works So we'll go through many different Aspects of IP And we'll cover all of these things You'll get to know what all of these are And DHCP and MTU and ICMP Acronyms mean So don't worry about it now We'll go into it This that we're going to look at IP is really IP version 4 IP which are essentially Most of us probably use today with our computers There's a new version Of IP and internet that's now been deployed It's the future And that is IPv6 So to finish up on IP we'll look at IPv6 To find out what's different And what's going on with its deployment Many of you have probably heard of IPv6 As something that's coming To the internet And finally In this unit we'll look at NAT NAT is a strange kind of forwarding technology It's called a middle box It is something that many of you Probably have in your houses If you have it inside an AP That you hook to the internet Usually has NAT technology inside it We're going to see We're going to understand exactly what it is Since it's something that many of you Probably encounter today And we'll see how it does fit Or rather how it doesn't fit With the standard IP model And here that's greyed out for now Routing algorithms which we'll get to In the next unit There's actually a lot of detail in there Routing is a big and important topic But we're going to put that off for a while Before we go ahead though I want you to be able to Be aware of one important distinction And that's the distinction Between routing and forwarding They're two different things It's a little confusing because routers in the internet Do both of them So that's why I'm pointing it out Now routing is the process Of deciding which way Your traffic should go in the network This is a process in which all of the routers Participate, so routing involves Talking to all of your neighbours And saying hey who's where And do you know who's over here And generally working out What is the best way The best links you should use to Send to reach all different destinations So it's a network-wide process It's global and because of that It's relatively expensive Forwarding on the other hand Is the process of deciding What to do when you get a packet Someone tosses your packet What do you do with it? You forward it By throwing it out the link on which it needs to go And doing a few other things So forwarding of course uses The information that comes out of routing After routing you're sort of left with a table Which tells you which way to go to get To different destinations So you have to be active using this table This means that it's a process That happens purely at one node It's a local process And because of that it's fast Actually it has to be fast Because a router might have to process millions Of packets a second So we've got to be able to forward quickly Now our plan Looking ahead is to Treat these two topics differently Actually the first one we're going to do is forwarding And understand what routers do with packets Actually you might think that routing comes first It's difficult to know How to forward a packet until you know Which way they need to go But we think that it will actually prove Easier for you to understand the internet If we go through the forwarding model first And then we deal with routing later So I'm going to ask you just to Spend disbelief for now And just imagine that routers somehow Magically know which way to send packets What we're going to look at In the upcoming segments is how they Packets on their way because there's quite a lot Involved in that Now that we've got this distinction in mind Let's go for it and find out How the internet and IP work Good day viewers In this segment I'm going to talk about The different kinds of network service models So our topic Is really the kind of service Which the network layer provides To the transport layer Like all good layers the network layer Is going to provide some kind of service interface To the higher layer the transport layer In this case and so what We would like to talk about is just What kind of network service Is going to be presented By the network layer and how that Service is implemented at routers We're just going to talk about these topics At a high level and in Future segments when we dive Into IP you'll see how one of these models Is realized in detail So it turns out that there are actually Two quite different kinds of service Models that the network provides To the transport layer Both of which have been talked about a lot And experimented with in practice One kind of model Is what's called the datagram Model datagrams or connectionless Service the analogy here Is the post office So datagrams are just like Sending letters through the postal system They're self-contained units You send them you know you write You seal it up you hand it to the post office They're all treated individually The post office delivers them by looking At the address and sends them on their way This is very much like IP IP is based on a datagram service And that's really the way You might have expected the internet to look Because of that but there is another model Here too this other model Is called the virtual circuit model Or a connection oriented model And the analogy here Is one of the telephone system You need to make some kind of connection That's like dialing someone Before you can use the network But once you've made this connection You can then send data down the pipe And it will arrive out the other side So this is quite a different kind of model Both of these models Have their pros and cons And I think it's useful for us to Know about both of them Before we dive into the details of IP too much So I'll also say That both of these different models Are implemented with a technique That's called store and forward packet switching Well that's a bit of a mouthful It really doesn't mean anything too complicated It essentially means That the way routers are going to work Is that they will receive A complete packet unit And they will store that packet Temporarily While they work out what to do with it And send it out on the right link So that it's going to arrive at the destination They won't necessarily need to store it For very long They might only need to store it If there's contention for that destination Other people are trying to use the link at the same time One thing that's important About this model That's one reason why it's used widely For all Data communications networks Is that it uses statistical multiplexing To share the link bandwidth over time In the description I gave you Of having packets come in on links And simply sending them out links The other thing is we're sharing The bandwidth of all of the output links At a fine grain over time By sending different packets Maybe coming from different hosts And going to different hosts over that link And we're using a bit of buffering inside the router To queue things up if you can't get on right away So this is statistical multiplexing at work It's quite different Than dividing that link According to fixed time periods Or fixed frequency periods Like radio stations using the link Any of the advantages of Networks in terms of using the capacity well As an aside I'm going to dive into the store and forward model a little more Just to give you a better sense Of what can go on inside these routers So here's a fairly general model For all switching elements Switchers, routers, funny devices That have a lot of input and output connections Inside the network They're all going to look something like this They have inputs here They have inputs on one side So these will be plugged into ports Twisted pair wires coming in maybe And they'll have outputs on the other side Really the input and output might be combined in a port But it's more convenient for me to draw this From left to right Inside the box, it's just another box You can't tell what the functionality is Inside until you have some description Of what layer it's doing the processing at And so forth Inside the box is usually a switching fabric That's what's providing the connectivity Between different input ports and output ports And What I want to highlight here Is this also necessarily some buffering That's these pink things here That's both the input and the output Why is the buffering? Well it's buffering because maybe At the very same moment A packet came from This first input up top And it was destined for this output up top And also a packet came from another link And it was destined for this output And yet another link and it was destined For this same output All three of those inputs can't go to the One output at the same time So if the packets enter the switch They need to be stored somewhere Either on the input buffering side Or the output buffering side But we do need buffering And that buffering is just for temporarily Holding the packets to help with Our multiplexing of the output link That model I just gave you Is a little detailed in some ways And it will often suffice To think of a much simpler conceptual view Of what's going on inside a router So here's another picture of a router I've really drawn here just one output port And In the simplified model here We imagine that there is output Buffering for each output port So there's just one unit of buffering And that unit is provided At the output port That buffer, that big long buffer Is then filled up with packets You can see I'm drawing them in here As the packets come in From the input side and they're waiting To go out that output link Exactly how that buffer is managed Depends on how the router or switch is implemented There are all sorts of different possibilities But a typical one Is to use a policy that's called FIFO First in, first out That just means that whatever packet gets In the buffer first is going to go out The output link first And the rest of them will just have to queue up behind it If this buffer gets full By the way, there's no space And another packet comes That packet will be discarded Or there'll be some discard policy A packet will be discarded So you can see here an important implication Of these switching elements with buffering And that's that packets may be discarded Under load This is actually what we refer to as congestion And we're going to study it In a lot of detail later on Okay, so now you know Some of the internals of routers I'm going to tell you about the two different models We talked about in a little more detail So first of all A datagram model, here's a network And packets are going to go through this network Between different hosts In the datagram model Each packet contains a destination address So every packet contains A full destination address That's what the router uses To be able to deliver the packets onwards Now the path through the network To get from one host to another might be This path here initially The way that will work Is all the routers Here A, C And E As a packet comes in, router A Will look at the destination address And if it sees it's really h2 But let's just say it's F over in this direction A will look up in its table See what it is F And it will learn that the way afforded Is along this path to here And then arrive at C Which will go through the same process But now realize because every packet Is handled individually And a different process is responsible For maintaining the routes It's possible that the routes can change While someone's using the network At a later time A might change its mind And packets might follow a different route Through the network Thus the host at the other end Might receive its packets fine Because the packets could actually Have gone along different routes Some of the time We can just look at that in a little more detail Just to sort of complete our thoughts About the datagram model These pictures here show you The forwarding table that's used In each of those routers So here over here Maybe is C's table And you can see that it has a table Where for every different destination It has a next hop To output the packet to That next hop is really going to correspond To which output line you should send it on To send it to there I've shown you Tables here for A, C, and E And A's table actually changes Over time Let's just imagine that we're trying to send a packet From A to F And if When the packet arrived at A What A would do is it would look up In its table it would see that it was going towards F And the next hop for that is C So it would then send it over the network It would arrive at C C would similarly see the packets trying to go to F Look it up, see that it's meant to send it to E And so on, it would get through the network At some later time A's table might change You can see here that for some reason Routes towards the destination E and F Have changed They're now forwarded onwards To the next hop of B Rather than C That doesn't really matter We don't have control over it We don't know when it could happen The datagram model will still be fine These packets, when they arrive We will look up a destination like F If another packet came This time we would send it to B No B will have to look at its table And maybe now we're following that other path Through the network So this is datagrams The most popular datagram model By far is IP Sorry, example of a datagram model IP is the network layer Of the internet It's what you have to use to be on the internet So it's used everywhere Almost defines the internet The addresses I've shown you here Just shade it These are the 32 bit addresses In IPv4 They're on each and every packet Often packets might be up to Around a kilobyte and a half long So you can see the picture here shows the header Which is going to occupy some number of bytes Not that many if you've got a kilobyte And a half packet, the overhead is not too much There are various fields there And the bottom one that says payload Or TCP segment That's all of the data Of the packet beyond the header Don't worry about all of these details On the header here, all of these different fields They're the fun bits of IP that we get to go into In all of the segments which are coming up But for right now I just want you to know That IP is the most famous example Of a datagram model That's out there and we're going to look at it In detail to understand how it works Second model The second model I talked about For providing a network service to The transport layer was the virtual circuit model Virtual circuit model is Unlike a datagram model Datagram model letters Packet is independent Self-contained, fully addressed Not the case in a virtual circuit model In a virtual circuit model Just like the telephone, we go through three phases The first phase here Is a connection establishment phase You've got to set up Some connection or circuit From the person who wants to send To the person who wants to receive the information Setting up the connection Really means finding a path through the network Choosing that path And setting information about the circuit That we're about to use in all of the routers That are along that path So they'll know what to do when they see Packets from this virtual circuit Once it's set up, then there's a data transfer phase This is the useful bit in some sense The bit we want We send packets Along this virtual circuit And all of the routers along the path Ford them on to their destination And then finally when we're done Particularly if we're nice There is a circuit teardown phase In which everything is cleaned up The state about this circuit is deleted From all of the routers along the path You can forget about it And move on to new circuits So this model is called a virtual circuit Because it's fairly similar Conceptually to a telephone circuit But it's But unlike imagining a physical wire Or a certain level of resources That are reserved for a telephone call It's virtual in the sense That there's usually no bandwidth Associated with this circuit The bandwidth across the links Are still shared with statistical multiplexing So how much bandwidth you get From this circuit is just going to depend On how much traffic you send And all of the other traffic In the network that was competing for it Well let's look in a little more detail Here's our picture of our network again Now unlike Packets in a data RAM model Packets in a virtual circuit model Don't necessarily, well they don't Contain a full address All they need is a short label Which says what circuit they run For circuit number 7 So that the router will then know what to do with it Because during the connection establishment phase It's worked out what circuit's number 7 Means and where it should go So these low labels don't have any kind of Global meaning They just have to be unique to the Link, to the router where they're going to arrive In a certain link so the router will know what to do But they don't have to have any other Unique meaning In this network we might have two different circuits Going at the same time Now both of these circuits might be going Along some of the same links So here's one and here's another Both of these circuits could be used At the same time, maybe if Host 3 and host 1 Maybe if they're both sending to Host 2 Well it's just because we're going to want to be able To send multiple circuits on the one link Otherwise we haven't got much of a network Okay let's look At just a little more detail We looked at the forwarding tables inside A datagram network Let's look at the forwarding tables inside A virtual circuit network And the reason to do this Is for you to see how they're different Than the forwarding tables Inside a datagram network So now all we really need Is a table which tells us The incoming circuits And what to do with them By convention the table tells you The incoming circuit, it tells you What link they're coming from One thing arriving at A could be coming from Either host 1 or host 3 And what circuit number they have on the link They're coming in, these both happen to be Labelled circuit number 1 On their respective input links And then the output table tells us What to do So you can see that the circuit that comes From host 1 with identifier 1 Is forwarded out The link going towards C Where it is known to C as circuit number 5 What that means Is that we're going to change the label Or the circuit number Inside the packet as it goes through the network This packet Is Going in the link from A to C It's identified by 5 When it arrives at C it comes from A With 5 that's right and what happens We look it up in the table We're meant to send it on to E With the circuit identifier of 1 So we're going to change that 5 to a 1 Send the packet out the link to E It gets to E What happens, it's coming from C with a 1 It goes out to F with a 1 And so on I'll just go back now and consider Traffic from host 3 Going to F And eventually on to host 2 Let's say The reason to do this is because This circuit travelled down some of the same links So we've got to be able to separate These two different circuits on this link This example will show us how we do that Now the traffic from host 3 Comes in with circuit identifier 1 To A A has different input lines For host 1 and host 3 So it knows which one is which When it gets circuit identifier 1 In from host 3 It's instructions in it's table here And this is just one example You could construct many different tables But it's instructions here Is to send this packet onwards to C With circuit identifier 2 To change the 1 to a 2 Send it on to C At C, this comes in on link A With circuit identifier 2 Note that both of these circuits At C came in from On link A So we really needed them to have different circuit Identifiers so we'd be able to distinguish them We have, one's 9 by 5 And the other's 9 by 2 So we couldn't have called them both 1 Going out C From A's table because that would have resulted In confusion at C C wouldn't have been able to separate these two circuits But they have different numbers so it can Now we send it onwards To E with a circuit number of 2 E When it receives it from C with a circuit number of 2 Sends it on to F with a circuit number of 2 And so forth They still have different numbers so we've distinguished these circuits Okay, so that's virtual circuits Here's a cleaned up version And hopefully I've got everything right there You can check that I've got all the numbers right And work through it yourself Okay We all hear about datagrams a lot Because that's what IP is all about But I'm also here to report to you that Virtual circuits are alive and well Some of you might have heard Of a technology called MPLS, multi-protocol Label switching This is a virtual circuit like technology Which is widely used inside ISPs The way it works Is that ISPs set up circuits Inside their backbone From different ingress points To different egress points So across their network they set up all of these circuits By doing this They can carefully control The path through the network And separate traffic in different circuits And handle them differently It allows them better control over their network This means by the way That when the packet comes in To the network Since it's now using circuit switching Is going to need to add this MPLS header To the packets So you can see a packet Here's an IP packet came in And what happened inside the ISP network Is we added this MPLS header That header What's the most important part in it The label we talked about The label is this circuit identifier Which is going to tell routers inside the ISP Which way to go So this packet will then follow The labels to follow the circuit It will eventually get to the other side of the ISP And when it does All of this MPLS header And the PPP link layer header Are going to be stripped off And will then be left with the IP packet And you can then send that onwards To internet style routers That understand IP as datagrams I'm not going to go into more detail about MPLS You can look at it in your book If you want to know more about How ISPs work in detail It is worth finding out about Although it's a bit of an advanced topic For our course And finally we're able to Now that we've seen these two different Alternative service models To draw a bit of a comparison between them So just on a bunch of different issues You find that datagrams and circuits Behave a different way This is actually a good way to check your understanding Of datagrams and virtual circuits So let's go through them First issue, a setup phase A setup is not needed You just make your datagram packet Throw it into the network whenever you like On the other hand For virtual circuits A connection Setup is required Router state What do routers need to remember? With datagrams they just need their table Of how to get to different destinations With virtual circuits They actually need to remember more For every different circuit or connection To remember what to do about it So you might have a lot of different circuits On going at the same time Addressing Datagrams carry the full address IPv4 address say of 32 bits Whereas a packet might carry a short label 20 bits or less 20 bits for the case of MPLS Routing Routing essentially happens On you have to do the work For every packet, so it's on a per packet Basis for datagrams Routing for virtual circuits is really done When it's set up, and after that We're just sending packets down the circuit However it is So there's a chance to amortize work Across the whole circuit full of packets Failures On the other hand Well, in datagrams Failures are easier to mask Because we're not storing any information In the network about a circuit And how to handle it With virtual circuits we are Doing something and we have to scramble To do a lot of work to repair it So in theory, datagrams should be easier To mask failures in Than a virtual circuit Quality of service is the other way around With datagrams Every packet is handled independently So it's hard to add quality of service Because quality of service Is usually not something that applies To an individual packet Usually it applies to a group of packets Like all of the packets in a video conference For example With virtual circuits it's easier to add Because we do have this identifier For all of the packets in a circuit We might have one circuit for the whole video conference For example Okay, so now you know about these two different models Datagrams and virtual circuits And we're going to dive into the datagram model In lots more detail as we go through IP Good day viewers In this segment we're going to talk about Internet working, or how to combine Multiple networks together into one larger network So internet working Or connecting all of these different networks Into a single larger network Is difficult because the networks we might Want to connect might be very different In terms of how they operate internally They can just Be different in many ways I'll go into some in a moment And what we would really like to do with internet working Is to paper over these differences So that we're able to connect from host on one network To host on another network As though it was a single network That sounds kind of hard It is hard, it doesn't always work What we'll do to learn about internet working Is we're going to essentially look at IP IP is a case example If you like a case study But it's the most extensive case study around And it has a lot of experience With how to combine different networks together Because IP of course is the protocol That grew up into the internet That connects all of the different kinds of networks today So how might networks differ To connect them we need to understand Some of the differences Basically they can differ in a lot of ways And we're not going to be able to resolve all of those ways I talked about In an earlier segment for instance Different kinds of network service models Suppose you have a network service model Using datagrams in one network And one using virtual circuits in another network Imagine combining these It's a little like combining the post office And the telephone network It's not clear that would work very well Different networks might have Different kinds of addressing Since they'll basically They'll normally be designed by different people So they might have different kinds of addresses So it's not clear that we can even write The different kinds of addresses in the right place In other networks And there may be many different features In these different networks They can range from large to small A fairly large one for instance Might be quality of service Imagine if one of the networks Has all different kinds of qualities of service Maybe it has regular packets And packets that are priority packets Which should be afforded ahead of regular packets And another network doesn't It just has basic service How are we going to combine these networks And still provide Still honor the quality of service Arrangements of the one network That uses quality of service It's not clear Smaller examples of a difference Might be that different networks Or packets of different sizes Is this going to be the case? Yes, it's the case all of the time For technological reasons Different kinds of link-layer technologies Can handle packets of different maximum sizes This seems like a small mundane detail But even this detail Actually turns out to require a lot of work From the architecture to deal with Let alone larger things like Networks that have different kinds Of quality of service or security The job of internetworking Is to hide all of these differences Across networks with a common protocol If you think that sounds kind of tricky You're right, it is Just to give you an example And sort of get into the flavor Of how we might connect these things I'll talk about connecting Datagram and virtual circuit networks As an example So suppose that you have a source Sending to a destination The source is on a datagram network The destination is also on a datagram network And here in the middle I put a virtual circuit network Just to make things a little tricky And bring up some of these issues So let's imagine what's going to happen When you want to send from this source To this destination We have the packet here on the left So first of all You need to be able to write the destination Addressing this packet Even though the formats might be different Because one's on 80 to 11 and the other's on ethernet Suppose we could do that In the datagram network It will be forwarded Using the destination address All the way through here At a time until it reaches the virtual circuit network At that point Something needs to