are the original values which were sent and we can recover them at the other end Then we've done a good job of using that bandwidth. We actually didn't need the high fidelity signal Um in a sense we were wasting bandwidth now Of course if you had an analog application like uh listening to a stereo you want the high fidelity signal or it will sound terrible Okay, so this last bit that we learned that fewer frequencies Degrade the signal by making it transition less rapidly and getting more routed is key to understanding what Happens to signals as they pass over a wire In fact, I can now tell you That there are roughly four rough effects here that happen as the signal propagates across a wire First of all, it's delayed because it takes a little while for the signal to propagate as we heard before So a fraction of time will pass Next the signal is attenuated You know over a wire signal might go from meters through to kilometers And the electrical signal that's going to come out the other side will be smaller in magnitude than what you put in Because some of it will be lost some of the energy will be lost The signal will also be attenuated or more rounded because not all frequencies will be passed through A wire tends to pass frequencies well up until our cutoff frequency And after that frequency the signals are fairly highly attenuated They're mostly lost as in our example And finally some noise is going to be added to the signal just thermal noise In the receiver, you know, that's the sort of thing that you can't get around And if the signal is very small this noise will end up causing errors I'm going to show you pictures of these effects in just a little while. We'll make them up Before I do that. I just want to point out the information in the box here Interestingly, the EE in the CS community have different ideas of what BAMWIT actually is In terms of the EE community BAMWIT is literally the width of the frequency band So on a frequency diagram The some of the diagrams from before we saw a range of frequencies the width the frequencies are wire passes is its BAMWIT So it's measured in hertz In the CS community BAMWIT is regarded as the information carrying capacity of a link It's given in bits a second, megabits per second. We might talk of that as BAMWIT These two quantities are really related because if you have more EE BAMWIT You'll be able to get a link which sends information more quickly It will have more CS BAMWIT, so they're certainly related But they're not quite the same thing So you need to be careful who you're talking to to understand what they mean Okay, so let's see those effects Imagine that the signal on the left is sent What's going to happen to it? Well, one of the first effects is that it will be delayed, but we're not going to picture that because I can't draw a time delay Then it will be attenuated. What will that look like? Well, a smaller version Of the signal will come out the other side Now the BAMWIT will be limited because we go through a wire and the high frequencies won't be passed What will that do? That will make it more curved. So we'll get something that might look more like this And then finally We show here that noise is going to be added. What will that look like? Well instead of being smooth the signal may go or something like this It's still rounded, but it has all of these jaggies on maybe Because there's a little bit of noise you can see here the amount of noise is small So I can still see the signal very clearly If the signal had been greatly attenuated then the noise would be a larger component of it Okay, so what about fiber? Well, I don't have much to add about the transmission mechanisms over fiber Rather the important differences in sending signals over fiber compared to wires Had to do with the physical characteristics of fiber This graph here this figure Shows you the attenuation That's on the vertical axis against our frequency or wavelength as I'll get to in a minute On the on the horizontal axis And you can see here two properties of fiber which make it very interesting to carry signals First is the low attenuation attenuation. There is given in decibels per kilometer But basically the attenuation is very low And this means that you can send signals a long long long way through fiber before they're greatly attenuated many miles Up to a hundred miles maybe The other and that's quite different than wires Now the other characteristic here is you look at the band in which the attenuation is lowest And there are these colored bands here at different frequencies Which are used for to transmit signals over fiber. Actually, I keep saying frequency But by convention the horizontal axis is given in wavelength here wavelength is equal to is inversely related to a frequency So the wavelength is equal to the speed of light divided by the frequency So that way you can relate the two of them Now in these bands first of all you see these bands if you do the computations You'll find that they run at very high frequencies So we're not able to send signals literally we need to use a carrier signal at higher frequencies to send information And I'll get to that in a sec to give you the intuition and more over the width of these bands if you compute it in terms of Hertz it's very large. We're talking about many many gigahertz of bandwidth that's available to transmit signals Over fiber in windows of lower attenuation That great bandwidth translates into being able to send information at very high rate many many gigabits per second This is where the high capacity of fiber comes from Okay, and wireless what about sending signals across wireless links? Well, uh, the principal difference compared to wires or at least one key difference I want to point out to you is that we need to send signals over wireless links using a carrier rather than directly Here's a good old baseband signal the signal We actually want to send that encodes the ones and the zeros that signal can't be sent directly out an antenna for physical reasons You need a very very large antenna and a lot of power and so forth So instead higher frequencies carrier frequencies are the frequencies which propagate over wireless channels And we need to use a carrier frequency to send information. What does that look like? Well, um, it's not as complicated as it sounds Uh, the carrier is simply a signal which goes up and down rapidly at a certain frequency the carrier frequency And what we can do is change characteristics of it here. I'm going to change its amplitude And you can see what I'm trying to do there is change the amplitude to convey just that shape of the signal We wanted to send so by looking at the uh, the envelope of the signal I'll be able to work out what kind of information it is we're sending And uh fiber also carries information uses a carrier signal to carry information because we're sending at higher frequencies than a baseband Okay, here is a second characteristic of wireless for us to look at and that is that wireless signals Ittenuated rapidly as they travel away from the source of the transmission So here I have a diagram which shows you the signal strength And the vertical axis Against distance spatial distance. We'll just consider a line on the horizontal axis and I have two points of transmission Tx for transmission here at a and b Now for each of them, uh, we transmit it with a certain power level and the signal falls off rapidly as we go away And this attenuation Is proportional to one on the distance squared The signals are going to be attenuated at least this rapid lesion move away from the source You might wonder where that one on distance squared comes from Well, it's physics if you think about the the formula for the surface area of a sphere, you know As the signal expands a real volume of space that sphere Has a surface area of 4 pi r squared So the area of the sphere is increasing as the radius squared that translates into the energy Unit area if it's the same energy decreasing At at least one on the distance squared and it's at least that because other mechanisms Can, uh, cause the wireless signal energy to be lost now. Don't worry about that If you don't need to really understand that that's just if you're curious The point I want you to take away is that wireless signals attenuate quickly At least most rapidly from the source the signal energy goes down very quickly And a third characteristic of wireless, which is important to us and this is unlike wires to where, you know In wires the signal trans uh travels directly down that wire and you know, whatever we put on the wire We sort of get out the other end Well in wireless many people can be transmitting in different locations and if they transmit here, we have our three transmitters At A, B and C If they transmit on the same frequency their signals will attenuate here's their signal attenuating but they can overlap spatially And this leads to a phenomenon called interference at the receiver Let's just imagine for the moment that we have the receiver at another location Right here. I'll call this d if you like What does dc? Good grief. I'm just trying to write dc's What does dc? Well at this particular location We can see that there are Signals from all three transmitters are present at different amounts of attenuation. So actually d will see a strong signal from c And that that's this up here high here and down here. We have weaker signals. I'll just say a weak weak signal from a And b Now d will see all of those signals together Um, you know, it would be nice if they were all separated, but that's not the way it works You see the superimposition of all of these signals. Actually, this means that d may have a lot of trouble disentangling them In fact, it may be able to cleanly separate out to receive none of these signals individually because they're all messing up one another And finally the last characteristic actually maybe not quite the last characteristic But we're almost getting there that I'll tell you about for wireless is what's called spatial reuse And that has to do with this phenomenon of interference So we talked before this is the same diagram as the previous slide and I said that, you know, if we were at point d Uh, well, we would see all of these signals overlapping But if you look at the uh, the decay of these signals, you should be able to see, you know Over at least about let's say this band and this band Here I should be able to send Uh, we within these regions I can receive the signal b without the signal from a interfering if I simply look at a point here I get a fairly strong signal for b And I get no signal that I've shown here for a a signal continues to propagate and attenuate But below about this level here I just haven't drawn it on the graph because we consider it too weak to be picked up similarly over here You can see that within this region here anywhere within the region that i'm showing here A signal can be received and the signal from b is not strong enough to really Be noticed and hence interfere with that in a noticeable way. This means that we can reuse frequencies At these two transmitter locations a and b. However, if you consider c is c A signal been transmitted. Well, if we try and receive it at, you know, a point in the middle here Actually, we get strong signals from both b and c and the interfere as we as I've described in the previous slide So that means for these two signals c and b No reuse You can't cleanly reuse the same frequency at these two transmitters because they're closer together And their signals will interfere So the notion of spatial reuse is that if the transmitters are far enough apart Spatially we'll be able to reuse and transmit information on the same frequency Okay. Well, you can see how wireless is getting kind of complicated I'm going to stop telling you about wireless effects in just a moment. I really want to make two Two points and then, you know, one more one more effect There's always one more to show you about wireless And this is really to give you a sense of the complexity. So wireless is by far the most complicated Medium in which signals propagate compared to the case of wires and fiber Really for two reasons there are all, you know, the same basic electromagnetic effects But two reasons here are getting us one is that wireless propagation is very complicated because it depends on the environment We're no longer just going down a wire. We're propagating in a complicated environment So there are buildings that can get in the way and shadow signals You know trees our signals can bounce off all sorts of things including the ground The signals can be divided and recombined in interesting ways And this makes wireless propagation a very complicated phenomenon because of the environment And the other reason that wireless propagation is complicated Is that many of the key effects depend significantly on the frequencies Signals at different frequencies propagate in different ways to use an analogy light is a very high frequency So it propagates in a very directional way like shining a torch sound is a very lower much Lower frequency phenomenon and it does things like it goes around corners You can hear people even when they're in another room So a different frequency there can be related to very different physical effects For us some of the physical effects which will be most important will be those that happen in the microwave band That's what's used for 802.11 and you know 3g cellular and so forth And in a particular effect that i'm going to tell you about is multi path We should care about multi path other than that and the other effects I've told you about i'm just i'll leave it at the wireless propagation is complicated But we won't really have to worry about any more than the effects. I've already told you about Multi path is important for us to understand because it has a big effect on communication systems Multi path occurs because in the microwave band signals bounce off objects This means that they can take multiple paths between a center and a receiver on the left here I have a transmitter and on the right I have receivers Tx and rx Now let's just look at one receiver up at the top here The signal from the transmitter is going to be sent out in all directions Some of it might go directly to the receiver Another bit of it might go in a different direction, but bounce off a filing cabinet is the classic thing And also arrive at the receiver The receiver will then see two different signals that arrived over multiple paths These signals will be superimposed so they will add Let's just say That we had one signal like this And another signal which was also going up and down just as fast When we add them We get this strong signal. It's not faded Now suppose that just because of the position of the reflector the path The same thing is going to happen down at this other receiver It's going to get a direct one-on-one by this reflector But now say that the path from this other reflector has a differently it will And in this case the phase of the signals is going to be a little different So I'll receive one signal just like this is before And the other signal Oh gosh, how can I draw this? I'm going to offset It's the same thing. It's just shifted The result when you add these things together is that these signals mostly cancel And you get a faded signal here This is called multipath fading The effect is very difficult to deal with because it can change over very small distances As I move just you know, maybe even a few centimeters my signal might go from fine To mostly gone This effect is also frequency dependent The result is that in wireless channels often you're in data communications often your signal is really quite messed up Um, it's missing portions of it because some frequencies were lost We then need to handle it with fairly sophisticated communication methods If you're interested in learning more you can look in your text in particular There's a method that you'll hear about quite a lot called OFDM that's used We're not going to have time to go into OFDM in this course G'day viewers in this segment. We'll talk about modulation or how to represent bits of signals Okay, so here is the setup you must know this setup quite well by now We have our computer on the left sending bits to a computer on the right Across a link, but of course across the link. We can't send bits literally we send analog signals So we need to work out some way to represent These bits with signals. I've said that many times you must be wondering how exactly we do it That's called modulation and that's the topic of this lecture Let's dive right in. Here is a simple modulation scheme It's the one that you would think of first. I think if you were just trying to come up with one on your own We will simply use a high voltage to represent a one and a low voltage to represent a zero This is a modulation scheme called NRZ for non-return to zero the names for archaic reasons. Don't worry about it We can work through an example. You see I have a sequence of bits here And I'm going to draw the waveform underneath. So for a zero we've got we have a low voltage down here Then I'm going to go up to a high voltage for a one Down to a zero up for a one one one one zero one zero zero zero zero zero one zero Oops looks like I've got a little bit of noise on there Must must be just the way a waveform would look Let me clean it up so you can see it a little more There it is. That's one kind of simple modulation Now there are many other schemes which are variations on this which which can be used in practice For instance, we could use more than two levels to two signal levels to represent bits If I just look at the if we group the bits that we sent Two bits at a time we could send More different levels if I go over those bits. I think the sequence was zero two three three One from the bits before if I use four signal levels, it would look something like this. This will be zero. This will be well level one two three and four To represent zero through three. So I'll start low Then I will go up two levels Then I will go to the top level top level and down to the not quite the lowest level There we are that would be using four levels The schemes which are used in practice are very much driven by engineering considerations for how you get this to work I'm going to talk about one of those considerations, which is called clock recovery So for clock recovery, here's an example of the problem. Imagine that we have this nRZ signal here Here it is a one And then a zero a zero a zero a zero lots of zeros big long run of zeros If you are the receiver you see this signal But you don't see the bits of course your job is to work out what the bits are So it's clearly a one and then how many zeros is it? After a while it gets very difficult for the receiver to accurately work out the transition points between one zero and the next We could imagine that you'd have a very accurate clock, but that turns out to be expensive Instead what you would really like are frequent transitions in the signal itself So that you could help work out the timing of the signal at the receiver Now there are several different ways that you might go about this In your text you can look at there is an example of something that called Manchester coding That is a coding where there is a transition built into every signal either a zero or one They all include a transition a waveform which has a transition Another approach is something called scrambling You could exclusive or your data with a pseudo random signal Which makes it highly likely that you'll get transitions You can look at these designs for fun Instead what I'm going to do is tell you just about one form of modulation that's used to help with clock recovery And that's called 4B5B Now the idea here is that we're going to map every four data bits Into five code bits which are then sent as a signal And we'll do this in a way where we won't have long runs of zeros So here are some examples taken from the table. Here's an input of four bits 0 0 0 0 And if we want to send those four data bits, we're instead going to send the five code bits 1 1 1 1 0 At the receiver we'll map back from code bits to data bits. So we'll know what we were talking about There are 16 entries here in the table. They're not shown. They're omitted But you know just to save space, but you could imagine there's a whole table full And if we follow this mapping you'll find that there are most three zeros you can get in a row So we won't have long runs of zeros anymore Great Of course, if you're if you've been thinking ahead, you realize that you can have fairly long runs of ones We haven't done anything to prevent long runs of ones So to prevent that being a problem We can use a kind of coding where we invert the signal level on a one and keep it at the same voltage level for a zero This form of coding is called NRZi where the i stands for invert. We invert on one And it's also shown in your text. I'll give you an example And here in our example, I've reproduced the table of 4 b 5 b for a reference or just some of it You can see the message bits. I want to send they start with 1 1 1 1 Okay, let's look that up in our table. You can see over here on the left that should go to 1 1 1 0 1 I'll write that in 1 1 1 0 1 Next we have four zeros that goes to 1 1 1 1 0 1 1 1 1 0 And finally we have 0 0 0 1 which in our table goes to 0 1 0 0 1 0 1 0 0 1 So those are the bits we actually want to send using an NRZi signal. How do I send that signal? Since this signal Inverts on a one and stays the same as a zero. I'll show that transition in the middle Of a bit time here So if I just arbitrarily start at the bottom for a one Then the one will contain an inversion And then for the next bit there's a one. It's another inversion of the signal level one and inversion Zero I stay the same one invert Invert Keep on inverting Stay the same for a zero zero Invert on the one zero zero zero invert on the one And that is the waveform that I would send I would then be able to see the transitions get enough transitions at the receiver to find the bit boundaries and You know then go back from my code words to my data bits and everything would be good I would have sent bits of information across a link Or here's that example for you just cleaned up a little bit so you can see it better Now what I've told you about so far Turns out to be what's called baseband modulation how you would literally send a signal over a wire. That's great. You can do that When we talk about wireless or fiber though, we want to send information not by putting a signal directly in the medium But by encoding it on a carrier signal, which is operating at a higher frequency The reason for this Is that um only higher frequencies are going to pass well through the media Well, we might want to divide up the medium in terms of frequency bands to permit multiple people to use it So we need to work out how to send information on higher frequencies Um, it might sound a little tricky modulating a carrier. It's not so bad. Let's see Here we can work through an example So first of all, let me show this is just the carrier The carrier is just a signal which is oscillating here at some desired frequency This could be around 2.4 gigahertz for 8 to 11 For instance Now to modulate it we can change it in several ways. We can change the amplitude. That's how far up and down it is I maybe I should draw here the amplitude is how far up and down it is The frequency is how fast it wiggles. We can have it. We all quickly or a little bit more slowly And the phase is where it is in its cycle We could change the phase from up down to maybe uh down up would be studying would be different phases Let's see an example So here is passband modulation An example of it we at the beginning I show you the baseband modulation signal It's just our old nrz signal I'm tracing over just so you can see that it just simply goes from zeros to ones And back as it encodes bits Now our first Passband modulation is going to modulate the amplitude of a carrier So you can see here the carrier is not shown directly just the modulation is And you can imagine this a carrier going up and down just as before but its amplitude has been changed Its amplitude is zero For some of the initial bits here and then its amplitude is one When it's oscillating up and down with that amplitude with that magnitude Alternatively here is another kind of uh Number two a different kind of passband modulation frequency shift key You can see now that I oscillate rapidly for a one This is a one and I oscillate more slowly for a zero And finally we have phase shift key. This signal looks a little more difficult to see But in essence I'm using a waveform which starts by going up and then down Although this would occur more rapidly there would be many cycles In each um in each bit time That will represent a one and a signal that starts by going down and then later up so it's out of phase With the other signal will represent a zero With these schemes I can now represent information on carrier signals which are in frequencies of our choice Real wireless modulation schemes are considerably more complex than I've shown you in in these examples In fact, uh, you know, you can take a whole communications course to understand some of this by In detail. Nonetheless, what we've covered gives you the basics of how we send information bits of information with signals over across either Wide or wireless links We'll move on next to error recovery Good day viewers in this segment We'll talk about some of the fundamental limits for how quickly information can be sent over a physical channel or link So when we build communication links often we like them to have high performance to run as quickly as possible So it's useful for not to know just how fast it's possible to build a link In this segment, I'm going to talk about two different results the night quiz limit And the Shannon capacity as you can see these are fairly early results They've been known for a long time. They give us limits on what it's possible to achieve So the real systems which are built are going to operate within these limits These different results are expressed in terms of the key properties of channels which we might care about The properties that are used are the bandwidth b That's important because the amount of bandwidth limits how quickly the signal can make transitions up and down and hence convey information And the signal strength s and the noise strength n These are as measured at the receiver How strong a signal they receive at the receiver? As you might imagine The relative strength of the signal compared to the noise Limits how many different signaling levels we can distinguish more signaling levels will let us send more information Let's see the results. So the first result I have for you is the nyquist limit This is for a noiseless case where we're just ignoring noise The nyquist limit tells us that the maximum symbol rate is 2b A symbol is simply a waveform which is used to convey information It might represent one bit more than one bit if you have multiple signal levels or even less than one bit in some cases So a symbol is a waveform that stands for bits Nyquist tells us that if we have a bandwidth of b We can signal symbols at a rate of up to 2b here. I've shown just a simple waveform Say that's the highest frequency we can send that kind of code two different bits per Per transition there an up and a down a one and a zero I've shown here Now if we also have different amplitude levels if we have v different signal levels That would be log to the base two of v different bits For instance, if you have four signal levels that will allow you to convey two bits with each level Eight signal levels three bits and so on putting these two terms together nyquist tells us That the maximum rate we can send information across a noiseless channel is 2b Multiplied by log to the base two of v bits per second where v is the number of signal levels Let's move on to the the other result which we'll care about the really the end result here This result is due to Claude Shannon Shannon was a giant of early computing In 1948 he put together a treaty called the mathematical theory of communication This was a landmark paper that put forth many of the key concepts and helped Found a field called information theory. It told us really what information was all sorts of things Shannon as well as making fundamental contributions to communications also made contributions to digital computing and security He was a quite an amazing guy. He also had fairly wide-ranging interests This picture shows an electromechanical mouse he built Uh, the mouse there are magnets underneath the mouse runs on this maze You can reconfigure the maze and the mouse will learn how to solve it and this was a long time ago. So it was quite amazing Shannon's capacity tells us the maximum information carrying rate of a channel And it does that by considering the noise Now the number of different levels we can distinguish signaling levels at the receiver Is going to depend on the relative strengths of the signal That we receive That signal is actually s plus n the signal plus the noise at the receiver The strength of that signal compared to the noise If it's large If that ratio is large we'll be able to distinguish many different levels in the picture here You can distinguish maybe four different levels. So if I have a if I receive something here Maybe I can know that it's most likely that a one was sent Because if I sent a one the noise would only have moved it up and down by a bit And so one is probably what was sent. On the other hand if I receive something here It's probably the case that I sent a zero Uh, keep in mind that these this noise is a random process The arrow here is only a depiction of how big it is on average So at any given time the noise could be larger And we may have some errors that are caused when our assumption is wrong We'll have to deal with them later The signal-to-noise ratio, or s divided by n Is typically expressed on a log scale because it can take on a wide range of values So if for instance we have a signal-to-noise ratio of 1,000 That's often written Using our little formula here, we express it on a log scale By taking log to the base 10 of the ratio and multiplying by 10 That's often written as 30 dB log of 1,000 is 3 multiplied by 10, you get 30 There are many other common SNR values in decibels that you might come across So as you might imagine 100 goes to 20 dB 10 goes to 10 dB 2 is a common value and that goes to 3 dB And so forth Okay, arm, arm, arm, arm, arm, arm, arm Okay, arm with this understanding of the signal-to-noise ratio We can talk about the Shannon capacity This is a limit for the information carrying capacity of a channel The limit, the capacity is given by the bandwidth Our factor from before multiplied by log to the base 2 Of 1 plus s on n Where s on n is the signal-to-noise ratio This bit in parenthesis, you might recognize this Is what we receive s plus n divided by n That's really s on n plus 1 This bit, log to the base 2, is converting to bits And then we're multiplying by the bandwidth The Shannon capacity is really quite fundamental for a channel Shannon showed that it is possible to transfer information reliably over a channel Up to that rate, but no higher This was quite revolutionary at the time When there always seemed to be errors on channels And the only way you could get rid of them was by sending a stronger signal Shannon really told us that in theory there exist codes So that you will be able to send information reliably across channels Up to a certain rate Even for whatever signal-to-noise ratio you're sending in So just to wrap up on this segment I'm going to give you a little perspective on wired versus wireless links We've now seen pretty much everything we need for the physical layer Aerocoding is a big subject that I'll get on to next But we've seen how to modulate signals and send information across links Yay! We're well on our way There is a big difference, however, between wires and fiber and wireless I would characterize it this way With wires and fiber, you can often engineer the parameters You can fix the bandwidth you're using by the quality of the wire And the signal-to-noise ratio You might send a certain value in and say the cable can be no longer than 100 feet This means that you can fix the data rate On the other hand, wireless is quite different You might be able to fix the bandwidth you're using as part of the design of the system But the signal-to-noise ratio will vary greatly It says here, up to a factor of 60 dB You do the math, that is a million That's a lot That might be the difference between signal strength and being close to an access point And 80 to 11 access point And receiving information quickly and being far away on the very edge of reception But still being able to use it Given this wide variation The signal-to-noise ratio is going to vary a lot We can't design the system for the worst case Or it will always run at a rather slow rate Instead, the name of the game in wireless Is adapting the data rate to the conditions you find So just recapping For wires and fiber, we engineer the system To give us a certain data rate that we expect and spec For wireless, we need to adapt to the SNR And finally, just to put some of these things together I can now give you an example Let's talk about a link that many of you know about Maybe you're using right now DSL or Digital Subscriber Line This is a widely used technology for providing broadband internet to homes There are many different variants of it And they run at tens of megabits per second DSL reuses the twisted pair telephone line that goes to the home So here's the local telephone exchange And there might be two different lines that go to the home Now, it turns out that the telephone is only using the bottom four kilohertz of this wire But the wire has a bandwidth of up to two megahertz We can reuse the higher portion of that bandwidth Which is currently unused to carry data That's exactly what DSL does Because it's been refitted to the existing telephone wire Rather than designed from scratch It has some of the characteristics of wireless too As you might imagine this close house If I'm close to the exchange I might get a high SNR Compared to if I'm a long way away The signal might be weaker and I might get a low SNR Because the signal is attenuated by the time it's got there When I've got a low SNR I might get a rather small data rate Compared to the other house Which could get a fast data rate over DSL This is why when you want to buy DSL Sometimes your provider will tell you That you're a long way away from the exchange And they can only sell your plan that goes this fast Or that you're lucky you're close to the exchange And they can sell your plan which runs at the maximum rate Here are a few more details for DSL DSL because it is sending at frequencies above the voice band Uses a former passband modulation I'm not going to go into all of the details That's sort of a whole course It does use a technique called OFDM Which turns up many times in communication systems You can read a bit about this in your text if you're interested Just for fun DSL divides the frequency band To provide separate bands for upstream and downstream communication You can see here that it uses four kilohertz The voice, that's not much And then it divides it into different portions For the upstream and downstream DSL, or actually the picture here Shows the frequency plan for ADSL2 Which is a fairly garden variety version of DSL It allocates more bandwidth to the downstream version Than the upstream version That more bandwidth is going to translate into a high number of bits per second The ADSL stands for asymmetric This asymmetry is deliberate To allow you to download information from the internet faster than you can send it The modulation that's used inside these bands Varies both the amplitude and phase of the different carrier signals It's called QUAM You don't need to remember that though If you're now all of the different signals in here They all can send information at different rates If you have a good portion of this band You're fairly close To the exchange you've got a good quality signal You might get a high SNR And you might be able to send it up to 15 bits per second Sorry, up to 15 bits per symbol So that's a lot of different amplitude and phase levels Two to the 15 at least to convey that number of bits On the other hand you might have a different band Part of the frequency which might be bad Not working very well This one's nice and solid let's say And the other one's not working very well This particular part of the band might give you a low SNR In which case you'll only use it to send one bit per symbol So this is how you can get different rates over DSL Okay well we've now seen a lot about the physical layer And shortly we'll move on to the next topic of error coding G'day viewers In this segment I'll give you an overview Of the topics that we're going to cover in the link layer Okay we're moving on We've now done what we need to on the physical layer We know how to send bits over a wire And we're moving up Through the link layer is our topic next Our picture here has changed This picture shows you the scope of the link layer Now that we have a bit stream The scope of the link layer Is focused on how to send messages Across one or more connected links These messages are called frames at the link layer And so you could also think of them as packets of the frames at the right word But they're going to have a limited size And they're going to build on the abilities of the physical layer So we'll no longer be talking about signals Just bits Here's a layering diagram Let's just recall how layering fits in with this The network layer shown at the top here Is sending a packet down to the link layer What happens at the link layer? You're meant to remember this By the way I'm going to draw it in But I hope you remember this The link layer will take the packet That packet is a payload there And then it will encapsulate it and add a header Actually as part of encapsulating it Often you add a header But in some cases Particularly at the link layer You may also add a trailer That unit will then be passed down to the physical layer Where it will go across the wire Come up the other side You'll have the same structure And the packet in here We'll just put H and T The packet will be unwrapped and passed up And because of that We're virtually communicating messages From one link layer protocol instance To its peer protocol instance on the other side Via the services of the physical layer This packet in here is going through unchanged And here I just cleaned it up a little bit So you can see the picture You might also be wondering Where all these different layers are implemented So I'm going to draw a diagram that just shows you The typical implementation of layers On a computer You might have applications programs Which run at user level Supported by the operating system And underneath the operating system Is the hardware itself The applications Here we are Are implemented typically at user level They're just programs which run on computers Within the operating system We'll then typically have the transport And network layers And we'll also have some of the link layer The link layer typically straddles The operating system and hardware Some of it's implemented in the operating system In the lower part of drivers Often there's some hardware support for the link layer On a NIC network interface card Which is inserted in your machine And then the physical layer Well that's hardware at the bottom Here's a slightly more cleaned up version Of that picture Or close to that picture It doesn't show the transport layer there Because that's not involved in this particular picture But don't worry about that So in our exploration of the link layer We're going to cover several topics This week we'll talk about framing Which involves how to delimit messages The beginning and end of messages And we'll also talk about error handling How to detect and correct errors Because of noise at the physical layer That'll occur and we want to be able to deal with them Later on in the following week We'll talk about yet more topics in the link layer As we work out how to retransmit And handle packet loss How to deal with multiple people Using the same channel as in 80211 And how to even build small networks By combining different links with switches G'day viewers In this segment we'll talk about Framing messages which are sent across the link layer So the need for framing arises Because the physical layer delivers a stream of bits We've worked hard with modulation To turn signals into a stream of bits But of course a stream of bits is not really what we want We would like to be able to send a sequence of messages Called frames across the link layer So we need some way to delimit The start and end of those messages That's what framing is all about In this segment we'll look at different methods Which can be used for framing First of all we'll look at a byte count method This is really a motivational method Just to get our hand around some of the different issues Then we'll look at byte stuffing Bite stuffing is a method which is used in practice And finally we'll look at bit stuffing Just to show you an alternative That's actually an older method Now I do want to point out That all of these methods Impose a framing structure on top of any bit stream You could use them in systems you design In many real low-layer links However the physical layer and the link layer Are implemented together And the physical layer often helps the link layer framing By providing signaling about the boundaries For instance by using physical air symbols That can't otherwise occur to indicate the start of frames So we're not looking at those methods Okay so our first method Bite counts What would you do if you wanted to impose a framing structure on a bit stream Here's a brilliant idea We'll just start the beginning of each frame with a length field That length field will tell us how long the frame is That way we'll know where it ends And where the next frame begins It's a simple method It's fairly efficient And hopefully it's good enough What could possibly go wrong Well, here we can see an example A byte counts I'll just show you here The first byte here is five So that says this frame is five bytes long One, two, three, four, five So if we hop beyond that We'll get to the start of the next frame And so on You can see, oops, almost missed that We're hopping down And we'll hop past Great, there's a simple scheme There is a problem with this scheme though As you might guess And the problem is this If we ever lose synchronization Because of an error For whatever reason A side crashing and restarting Then it is very difficult for us To find the start of frames once again We really have no way to resynchronize And we could be lost forever Here's an example First of all, we've got a nice byte Where we're in sync It says five, we go to here This byte is an error It should have been a five or something If we interpret it now as a seven We're going to overshoot And interpret something else As the beginning of another frame After that, we will happily invent fictitious frames Here, one byte Okay, the next one must be here Two bytes The next one must be here Four bytes One, two, three, four We must be here Sorry, here Seven bytes Where somewhere, somewhere else But we've lost synchronization And we can no longer work our When frames start and end Bite stuffing is a better idea That allows us to resynchronize The idea with byte stuffing Is that we will use a special character Called the flag byte To indicate the start and end of frames Here it is here We put down a special character That we can look for To know where frames start and end Of course, to do this We're going to have to do something With flag bytes Which might occur In the middle of a payload As real data We'll have to escape Or stuff these flag bytes With an escape character To, it's like quoting Material to indicate That it's not really the real flag There's a small complication here too If we introduce a special character Like an escape code We'll also have to escape the escape code Because there might be escapes In the real data Here's an example of byte stuffing The rules here Every time you see a flag in the data Replace it with the sequence escape flag An escape flag And every time you see escape Replace it with escape escape That's it So we can fill out this example together On the other side you'll have a Then there's a flag We better escape that ESC flag B Similarly if we have an escape inside the data ESC ESC B You could have an escape flag But if that's actually the data And we want to stuff it You will have to escape the escape Then you will see a flag character As a literal and you'll escape the flag And similarly Let me escape The two escapes So, and the receiver is going to Reapply the same rules in the other direction Whenever it sees an escape in the data It's going to take it out And replace it with the following character If we use this scheme It has the virtue that any unescape flag Is now the start or end of a frame So we can use this method To quickly re-synchronize If there's ever any error to find the start of frames All we have to do is look for that unescape flag Which doesn't exist here You can see all the flags are actually escaped So they're not real Okay, there's also another kind of stuffing You can do stuffing at the bit level Here's how that would work So we will call our flag sequence Six consecutive ones The rule we'll use at the transmitter Is if you ever send five ones in the data Sender zero Just in case the sixth thing was going to be a one On receive you're going to do the opposite If you ever get a zero After getting five ones Throw it away because it was added by the sender This is quite a simple scheme Actually, this scheme came before byte stuffing If you do an analysis You would expect that this scheme actually has slightly less overhead Nonetheless, it's more complicated than byte stuffing Because we might have to deal with messages with, for instance, 193 bits And we would rather deal with whole octet or byte numbers So byte stuffing is what's used in practice Oh, we have an example here we can go through So let's just quickly do a little bit of bit stuffing Zero Here's the data I'm going to copy it down That's two ones in a row Then a zero Oh, no problem Here we've got one, two, three, four ones in a row Now five ones problem You have to insert a zero Now we continue The next one I'll count as one, one, two, one, three ones Four ones, five ones, zero Now we're up to here Two ones, three, four, five ones, zero Then one, one, zero, zero, one, zero No problem Here are the characters I've inserted by stuffing This slide just cleans it up a little bit I mean, I've already told you how it compares In terms of maybe being slightly more efficient But being more complicated and not worth it in practice Now that we've seen how framing works I can give you an example of a real protocol PPP is what the protocol is called It stands for the point-to-point protocol It's fairly widely used in the internet To carry IP packets to frame them Over any kind of bit stream, byte stream transport For instance, PPP is used to carry IP packets Over sonnet optical links You might not know what sonnet optical links are Don't worry too much These turn out to be the big fat pipes That run at min gigabits a second Which are used by ISPs in the middle of the backbone Here's a little more on how PPP works First we have the protocol stack here You can see the IP layer here is going to produce packets And hand it down to the PPP layer Which is acting as the link layer and providing framing The link layer is then going to run over the sonnet layer That's the physical layer here And once we've got a little bit of a physical layer Eventually it'll go out that optical fiber On the right hand side It shows us some of the encapsulation And just some of the real world wrinkles That you run into here The IP packet is encapsulated inside a PPP frame That's pretty much what we expect But the PPP frame might actually be split Across two sonnet payloads It's a sort of real world complication That networking protocols are full off If we focus on the PPP bits Since that's our focus for this video Then we find that PPP frames Frames the packets it gets from the IP layer Using byte stuffing That in a way that's quite similar to what we've described Here's a picture of the frame The payload is what comes down from the IP layer And you can see to that The PPP layer adds some of its headers And control information And also some trailers And then the outer layer is the framing With our flags In fact the flag character here is 0x70 And we'll also have to escape this character If it incurs inside the IP packet That's inside the payload And we'll do that using 0x70 Is the escape character There's one slight twist here though That's a little interesting It's in the details But I think it's interesting So I'm going to tell you Here's the rule for byte stuffing To stuff or unstuff a byte You add or remove the escape character Just as we've seen And you also X or the byte Which follows the escape character With 0x20 Now if you expand all of those bits And look at that hexadecimal notation You'll find what that does is toggle the fifth bit So for instance If I have 0x70 in the data 7e If I stop that I will get 0x7d The escape character And then I'm going to X or 7e With 0x20 That will flip the fifth bit And I'll actually get 5e I've just changed the value of 1 bit Similarly If you stuff 0x7d Then what you'll get is 0x7d The escape character And then I X or 0x7d With 0x20 And I will get 5d And at the receiver I'll do the reverse I'll simply X or whatever Comes after the escape character With 0x20 And that will turn it back Into the 7e that we wanted The virtue of using this scheme Is that we've completely removed Occurrences of the flag character 0x7e From the contents of the frame So now we can just search The byte stream for 0x7e And when you see it You've got the starter frame It can't occur inside the frame Because we've modified it in some way By using this convention Okay well now you know about Real link layers And how framing is done G'day viewers In this segment I'll give you An introduction to the error codes We're going to use C To detect and correct errors Our topic is how to handle The different errors that occur At the physical layer The problem in essence Is that some bits in our messages At the link layer are going to be Received in error Because of noise at the physical layer This is unacceptable In that we can't send a message Across a network And have a different message Arrived at the other side And think that was the real message You wouldn't be very happy If this happened every time You sent messages across the internet For example So we will need some way To handle these errors There are a few alternatives That we'll look at It's possible to detect Some of these errors Using codes Well we'll look at this later It's also possible to Correct some of these errors Using codes You'll receive a message And not only realize That something's not quite right With it But be able to take a good guess About what message was actually sent And finally it's possible To after you've detected Maybe that there's a problem Retransmit a message Which was in error And has otherwise been lost We'll look at this option later And first of all Just talk about error codes These kinds of error codes Are a reliability Function And we'll also see As we go through this course That reliability is a concern That cuts across all of the layers Every layer will generally do its part To improve the reliability of the system At the link layer We're mostly concerned with bit errors That might occur and what to do about them At higher layers We might be concerned With the recovery actions and so forth Okay so the problem here Is that Noise Can flip some of the received bits You can see the signal I sent in above Just one of our good old fashioned NRZ coded Zero one signals I'm going to draw a slightly noisy version of it It's a zero The signal is kind of wandering And then a one And then a one A few zeros And a one But you can still make it out On the other hand If the line has been long And the signal is very attenuated Relative to the noise We might have something That's much more messed up What is this? Well this looks like Zero one one zero I don't know what this is This could be a zero Or it could be a one Maybe that's a zero zero I don't know what this one is either Let's make that even a little more messy Just so it's clear That there's a lack of clarity there In this case We may end up making decoding errors And think that we got a one here When we received a zero Or vice versa These are the errors that we would like to handle Observe that in our case In this scenario The receiver maybe doesn't even know there are errors It's just got the bits It's decoded them Some of them might be bad It doesn't know that yet How are we going to deal with these errors? To handle them What we will need to do Is add structure to the message By adding some redundancy Only by adding some kind of redundancy and structure Will we be able to recognize That the message doesn't look quite right That something is wrong with it With error detection With error detection codes We add a little bit of structure in the form of check bits We add these check bits to the message In these check bits Will then let us detect an error at the receiver Whether an error When an error is coded On the other hand We could pursue error correction codes In these schemes We'll add check bits also But usually more check bits So that at the other side We can look at the structure of the message See that something's wrong And take a good guess As to what the message was Thereby correcting some of the errors The key issue for us Is how we're actually going to do this It sounds kind of hard This is actually a very interesting topic Don't you think? How are we going to structure these messages With codes So that we can solve this problem Not only that But for a good code We would like the code to be able to Detect lots of different kinds of errors Not just single bit errors But maybe situations when Two bit errors occur in a packet And so forth We'd also like to do this with Few check bits Every time we send a check bit We're using the channel for something Other than the real data we care about So we're adding more overhead So don't use too many of them We'd also like to do this With a scheme that involves Only modest computation At the sender and receiver If we can We're generally willing to use A bit of computation What will really help But this is computation that has to go on You know line rate At the sender and receiver So it's adding complexity to the system To warm up to some of these codes We'll start with a motivating example So here's a simple code That we could use to handle errors Got a brilliant idea You're ready for it Here it is Send two copies It's just an error If they're different I hope no one's patented that Okay, so here's our example Here is the message Zero one zero And we're simply going to send Another copy We'll send it again Back to back zero one zero Great Actually let's not rush out And patent it Before we think about How good this code is First we could ask Well, how many errors Will it detect or correct The number of errors it can correct Is zero It can't correct anything Suppose for instance That you know we had received A one on the very end Instead of a zero Well now you can see These two things don't match So we know something's wrong But you don't know which bit is an error That this one was flipped Rather than this one You just know there's a problem With some of them How many errors can it detect Well, I don't know I guess it could detect up to three errors If there were errors in different bit positions But here's the key issue The key issue is not how many errors it could detect In the you know for very arid messages But rather the minimum number of errors Which are required Which are able to make the code fail Suppose that I also flip This same bit in the same position They match Our check will say there's no errors But all I've done is added two errors With two errors this code can fail So it's not a very good code really Not only that I guess but to get that level of protection I spent 50% of my link On overhead for error correction Error detection And I didn't really get a lot of error detection out of it Two lousy bit errors And the scheme could fail And tell me I've got a message that's right When in fact it's wrong So we want to be able to do better than this We want to be able to handle more errors With less overhead We're going to look at some real codes Which are used To do this That can detect and correct errors In stronger ways than that motivating example These codes are basically going to be Different kinds of applied mathematics In general you won't go out and invent a new code You'll look one up and you'll use some well-known Existing codes which are being checked and debugged Which have been optimized by mathematicians essentially These different codes though They won't be able to handle all errors All of the codes are built to handle some level of errors Not an arbitrary level of errors It can't be done And it's also the case That these codes focus on accidental kinds of errors Rather than malicious errors As might occur when an adversary is trying to trick you It is possible to come up with error Detection schemes which work for malicious traffic These are called secure hashes This is a cryptography subject And we'll probably mention them briefly When we get to security at the end of the course But right now I'm just focused on regular error Detection and correction codes For errors in the physical layer To use error codes Just diving into the next level of detail Here's the overall structure We're going to send code words A code word is going to consist of the D data bits That's the actually the message bits that we want to send And then to that we're going to add these check bits We talked about Our different check bits This there is a vast literature on error codes And the kinds of codes I'm going to talk to you about Just so you know They're called systematic block codes Block codes mean they operate on a block of bits at a time Systematic means you append the check bits Rather than rewrite all of the data bits Those terms will help you If you're trying to read other literature And see where these schemes fit in The way the codes will be used at the sender Is that the sender will be given the data bits D from the higher layer And it will then compute the check bits The check bits here are strictly a function of the data So they're computed by a little routine as a function of the data Well then append them And you send them into the network towards the receiver And you're away The sender has done its job On the other side The receiver will receive from the network This package of D plus R bits There could be errors in this bit In these bits Let's just say there's an error in the data here Maybe I'll do an X in the data here What the receiver will do Is it will take the data bits And it will recompute The check bits from that data There is a function of the D data bits And it will see if they match the R-bits The R-bits that it received They should match If they were both computed from the same data They should match If everything's okay If they don't match Then it's an error In the case where I put an X here We will get an error Because our R should be Hopefully we've got a good code different from our R-dash Observe that one thing that's difficult about the codes here Is that the error could also be in the check bits Suppose actually my data was fine In the errors in my check bits This procedure will still tell me there's an error There is Not an error I really care about Because my data bits are okay But I have no way of knowing that Simply that there's an error somewhere in the D plus R bits And that's because the bits that go over the physical layer Don't distinguish check bits from data bits The check bits are not magical They're sent over the channel And so they're subject to errors Just as much as the data bits This is what makes error codes Very tricky and interesting to look at Here's a little more intuition as we think about How to design some of our codes Okay we have D data bits and R check bits In this picture I'm trying to draw just the space Of some of these different designs If we look at all of the code words How many code words are there? Well a code word is D plus R check bits So there are two to the D plus R Different possible code words that could be sent And received actually That could be received on the other side There are two to the D plus R possible Incoming sequences of D plus R bits But actually the code words The really correct code words that get sent How many of them are there? Well we know that they're D plus R bits long But there are only actually Two to the D different bits Because the R bits are computed As a function of the data So there are only two to the D possibilities Well that means if I randomly pick a code word From this space Anywhere from this space It's quite unlikely to be correct In fact the chances of it being correct Would be something like one over two to the R That's what you get when you take two to the D And you divide it by two to the D plus R One over two to the R gets fairly small As R gets large If you have a 16 check bits for instance You've got a one in 65,000 chance Of accidentally picking a code word What we would like to do when we design code words Is make it so that errors Essentially make it likely that we will pull A random sequence of bits out of this space That will not be a valid code word Then we'll be able to work out That something's gone wrong and try and correct it Much of the early work in this space Was done by Heming By Richard Heming He was a pioneer of some of the early codes There's actually a very nice paper he wrote in the 1950s This one Arrow Detecting and Correcting Codes You could look for this web and read it Sorry this paper on the web and read it It's really very readable And it develops in a very elegant way Something called Heming Codes Which we'll look at Heming did all sorts of work on codes and other things He was one of the great early pioneers You could also find on the web A talk he gave on You and Your Research Which is part motivational on advice That's often quoted Okay so here are some of the concepts That Heming came up with Which we need to know to work with error codes He came up with a concept of the Heming distance The distance by itself is The number of bit flips you need to change Oh it says D1 to D2 This should really be full code words D plus R1 to D plus R2 Now let me give you an example of a code Suppose when we have a data bit of 1 I'm going to send 111 Triple repetition code Just send the same data three times Seems good, got to be better at sending it twice For 0 I'm going to send, you guessed it, 000 What is the distance So this is the complete code set here That we just 0 and 1 are the only messages So 111 and 000 are the only code words Valid code words which could be sent Of course any sequence of 3 bits could be received What's the distance between these two code words The distance is the number of bit flips To turn one of these into the other So it's 3 We need 3 bit flips Now the Heming distance of a code Is the minimum distance between Any pair of code words that are in the code In this code there's only one pair of code words The code word for 1 and the code word for 0 The distance is 3 So the Heming distance of this whole code Is also 3 Seems fairly simple so far But we'll use it in just a moment Okay, so one of Heming's results Was that if you want to do error detection If you have a code whose distance is D plus 1 Then it is able to detect up to D errors always That many errors if they occur You are guaranteed to be able to detect it Let's see an example For the code I just looked at We have D plus 1 is equal to 3 Therefore you guessed it D is equal to 2 So that says with my triple repetition code I should be able to detect up to 2 errors Here were the two code symbols That are valid that we could send the two code words Let's just write down what you can get if you make 2 bit errors Well I could get 0 0 1 Yeah that's an error because that's none of those things We haven't changed one into the other I could get 0 1 0 I could get 1 0 0 I could get 0 1 1 I could get 1 0 1 or 1 1 0 That's all I can get by flipping 2 bit flips from any one of these things And none of these are valid code words So I'll always be able to detect it Of course if I make 3 bit flips I can change one of these valid code words Into another valid code word And I won't be able to detect that But with only 2 bit flips I will Here is another of Hamming's result And this is for error correction The result here is that if I have a code of distance 2D plus 1 Then up to D errors can be corrected By mapping them to the closest code word If we assume that there are a few enough errors Then that can be done Let's give an example again Here we have the Hamming distance Is 3 for the code So that was 2D plus 1 is equal to 3 D is equal to you guessed it 1 This means we should be able to detect up to 1 Sorry we should be able to correct Up to 1 error unambiguously with our triple repetition code Let me write down just an example error 0 1 0 That's the sort of thing you could get as an error What should we map it to? I think we would map that to 0 0 0 Now if there's only been 1 error It had to be this not 1 1 1 What if we got 1 1 0 Well we could correct that If we knew that there was only up to 1 error To 1 1 1 That's the code word to which is unambiguously closest So that's what must have been said If only up to 1 error had occurred If more than 1 error could occur in this scheme All bets are off You know if 2 errors had occurred Then this code word The second received sequence could have actually been all zeros But this is why with Hamming's bound This error correction code is only good for circumstances In which there can be up to a single error G'day viewers In this segment we're going to talk about specific schemes That can be used to detect errors in packets We talked previously about errors occurring in packets Because of noise at the physical layer In this segment we're going to go over some specific schemes Which can be used to find those errors When they do occur to detect them And we will look at three schemes in particular Parry really mostly for motivation Followed by checksums and CRCs With the latter two are used fairly widely in practice I'd point out also that detection by itself won't fix errors But it will allow us to fix errors by combining detection With a mechanism such as retransmission And we'll look at retransmission later Well let's start with our first simple error detection scheme Parity or the parity bit Parity works as follows You take d data bits and then you add one check bit The parity bit and that check bit is going to be the sum of all the other d bits That sum will have to be done modulo 2 Because we've only got one bit left over to put on And by the way this is equivalent to XORing all of the bits together Here's an example Let's just say I have 1, 0, 0, 1, 1, 0, 0 There's a 7-bit sum of data to send If I then want to add parity to it An 8th parity bit The parity bit for the case of even parity Will be the sum of all of the data bits modulo 2 I've got 3 of those modulo 2 I get left back a 1 instead of a 0 So we add a 1 This is the parity bit Great That's essentially parity And you can check the computation at the receiver You would go through and add them all up again Except for the parity bit You could see if they're equal Or you could just add everything together Including the parity bit And you should get 0 out by design How well does this parity code work? Well, if you recall our concepts of error codes We can sort of begin to think about it First of all, we can ask What's the distance of this code? How many bit flips do I need to make? What's the minimum number to turn any one code word Into another code word? Well in this case If I flip any one bit The parity sum will be wrong But if I flip another bit Then I can get to a place Where the parity sum would be right Even though the data has changed So the distance of this code is 2 Given a distance of 2 How many errors are we able to correct? Well, the answer to that is 0 You don't correct anything If the parity is off You get to see if there's been one error But we don't have enough distance here To be able to correct anything What about detecting errors? How many errors are we guaranteed to detect? If the distance is 2 We're guaranteed to detect up to one error So that's all the parity is good for In terms of any guarantees Now for errors So it's not that strong For errors larger than a single bit What happens is going to depend On the structure of the computation For parity, if you think about it Actually it has this nice property That it will catch all odd numbers of errors Where an error is changing a 0 to a 1 Or vice versa If the first error will be caught by parity The second error will cancel out That parity bit won't be caught That was why it's distance 2 But the third error will bring us back To the situation Where there's a problem with the parity check bit Once again So we've detected all odd numbers of errors But not all even numbers of errors Here's a stronger alternative And one that's used in practice Much more widely today The idea here is in a checksum Is to sum up data Much as we did with parity But instead of using a single bit We're going to sum up the data In terms of n-bit words And use an n-bit checksum Or n-check bits For example TCP, IP and UDP They all use a 16-bit checksum This checksum is going to provide Stronger protection than parity We'll find out later It's really not that strong But it is stronger than parity I'll give you one specific example And that is the internet checksum This is the particular kind of checksum That's used in TCP, IP, UDP And other internet protocols Here's the definition of the checksum The checksum field is a 16-bit Ones complement of the ones complement sum Of all 16-bit words Oh my goodness That sounds very confusing It's not that confusing once you get used to it Essentially what it's saying here Is that you sum up all of the data 16 bits at a time And then you negate it So you come up with the negative sum The catch here Is that all of this arithmetic Is done with ones complement addition And it's done that way To give a better distribution Of our data over the 16 error bits Ones complement notation Is a way of describing binary numbers Such that the ones complement Or flipping all of the bits of a number Gives us negative form So for instance, if I have 001 The ones complement version Or the ones complement a bit clip of that Is 110 So this is one And this other bit one is negative one In ones complement Ones comp The computers we use Perform addition Where all of the binary numbers The integers are represented In twos complement form To get twos complement You do ones complement and you add one So for instance this negative one 110 If I add one I would get 111 This is actually negative one In twos complement The hitch With using ones complement addition On a twos complement or regular computer Is that when you add up numbers In ones complement form If any of the bits overflow Into the carry field You need to take them back And add them to the low order bits That's probably a lot more than you wanted to know Or bargained for Hearing about ones complement addition It's really not that bad though So let's have a look Here's an example we're going to work through We're going to calculate an internet checksum The first thing you do When you want to send data Is you arrange the data of the packet To be sent in 16 bit words to sum up That's these four values that I've shown here That so the packet if you like read 00, 01, F2, 03, F4, F5, F6, F7 And I've just laid it out In these 16 bit words to sum Now we're going to add these together We'll actually put a zero in the checksum position here Just so we can have the same algorithm On the receive side And we're going to add all of these things together What do we get? Uh oh This is making me work hard Okay, uh let's see When we add up these numbers We get 10, we get 16 So that's actually um Is that right? Okay, so 16 is We get a zero here And we carry the one Here we'll end up with F And we'll carry the one Now we have 11, 12, 13 13 in hexadecimal is a D And here we have three Fs Which are all added up F stands for 15 in hexadecimal What we're going to get is 20 we're going to 2 And what's left over will be a D Now so we've got that sum Of course this left bit here Is overflowed from the 16 bit position So what we're going to do is Take that back And add any carryover back So we'll just take those higher bits D, D, F, 0 We'll add the 2 The 2 is moved down here When we do that we get D, D, F, 2 Okay now our final step Is to negate by complementing This value And then we'll get the checksum So we want to negate all of those bits Okay let's negate D If you remember If I do the binary representation Representation of D D is actually 8 19, 11, 12, 0, 1 That should be 13 When I bit flip that Flip I'll get 0, 0, 1, 0 Or 2 So when I negate that I'll get 2, 2 Bitflipping F is all 1 So when I flip all of that I'll just get a 0 And when I flip 2 I'll get a D So 2, 2, 0, D Will be the internet checksum And we will then take that value Replace it where we used all zeros And then send those 5 Including the checksum 16 bit words out into the network Okay it's all cleaned up here And thankfully I ended up with the right answer Now let's look at the receiving side What's going to happen Actually exactly the same algorithm happens We just want to make sure that we get 0 out When we've negated everything at the final end Let's work through it It should be the same steps Here we arrange the message in 16 bit words The checksum is there It's the last word It's non-zero Because it was calculated on the other side Now we add it So what do we get? Well before we have 16 plus D So that will be D We'll carry the 1 1 ff That will be We'll end up with an f And we're going to carry a 1 here 10, 11, 12 Oh guess what It's what is it there 13, 14, 15 So we have an f And we're left here with ff, ff2 So when we add that together to D We'll get 2f Okay now of course we've carried over So we've got to take this high thing And add it back So we'll just do this some ff, fd plus 2 What do we get? We get ff, ff Oh this is looking good When we complement that We get 0, 0, 0, 0 That's correct The checksum passes No error was detected in this packet And it's cleaned up here You can see I've highlighted it as good I already knew I got the right answer Because it came out as zeros So that's how checksums work What we need to ask though Is whether they're any good How well does this checksum work At detecting errors We could begin by asking What's the distance of this code Actually the distance is not so impressive This is a sum So if we want to get the same sum You can imagine just having errors In two bits of the data In one place we'll add a certain value Like maybe 16 to a 16-bit word And in another place we'll subtract a certain value Like 16, the corresponding value from a word Or maybe we'll add the 64-bit position Or so forth But the point is We could make two corresponding errors And fool this sum So the distance is only two Well rats This means that as before The number of errors we can correct is zero This is just error detection Not correction So we're not trying to correct anything But the maximum number of errors That we are guaranteed to detect Is actually one Two bits can fool this checksum Well has this gotten any better It has gotten better So if we think about larger errors What's detected here is going to depend On the structure of the code We will actually find all Bursts Burst errors Up to 16 So it's a 16-bit checksum A burst error is just a sequence of errors In a row Or a window of errors Where in that window Errors occur Maybe there are Maybe some bits in the middle are not flipped But over that window A small window in space The error occurs It's a burst error So it's an advantage here That if those errors occur In bursts of 16 or less And there's just one in the packet We're going to detect it Because if you think about it Those 16 bits can only be affecting One 16-bit world Or two adjacent ones In different places So they can't cancel out If there are much larger errors In fact if we just make up random data Then we will detect random data too Random with probability One in two to the 16 If we just make up data Random data Then there are six Since there are 16 bits There are two to the 16 Different possible checksum values So there's only one in a two to the 16 chance That the checksum will actually match the data So this is much stronger than parity So we have got quite a lot By going from checksums to parity It's really much stronger But it's not as strong as we would like things to be in practice For the same number of bits We can do even better with codes Which are called CRCs Or cyclic redundancy codes The way a cyclic redundancy code works Is you take n bits of data And then you generate k check bits So that when you add them together The n plus k bits are evenly divisible By what's called the generator C I can show you an example here with numbers So let's just say we're working with decimal digits The number I want to send is 302 And I'm going to send a one digit check So I'm going to send a message 302 Something We just want to work out what that something is We want to choose a something So that the whole number Including the end is evenly divisible By our generator here Which is just going to be the number three Well one thing I can do is I can just start with 302 Let's just add a zero at the end And let's just look for the remainder When you divide it by three That's equal to what Well the 3000 falls away 320 That goes 18 So we're left with two The remainder is two And you can see Since three minus two is one I'm just one short Have been evenly divisible So all I need to do is put a one here 3021 And send that That is evenly divisible by three And so I've computed that My check digit there should be a one The catch for CRCs Is that we need to do all of this Based on the mathematics of finite fields The binary sequences here represent polynomials So in fact this binary sequence here Represents this polynomial You can see there's a zero there For x to the zero or one There's one x to the one No x to the twos One x to the three One x to the four No x to the fives No x to the sixth And one x to the seven Boy this could be complicated What this really means If we're going to do a complication Ourself Which is a little horrible and grungy But we'll try and work through it Just so you can really get to the bottom of it Is that if we're going to do these CRCs ourselves We need to work with binary values And our arithmetic will be done modulo two So the same procedure for a CRC is as follows You take the data bits And really we're mimicking here What we did with our decimal digit example You take the data bits You extend them with k zeros Then you do a division by this generator value Once you do that You look at the remainder to see what it is Keep that ignore the quotient from the division And using this remainder You adjust the check digits By the remainder So that they will be evenly divisible The received procedure Is to simply divide the whole thing Including the check the CRC bits at the end The check bits at the end And once you've divided it Checked the remainder is zero If that's the case There'll be no errors in the packet Okay, let's try and work through this Here's an example We have a sequence of data bits here You can see I've written them Over here And we're going to divide by our generator Which is one zero one one That's the divisor here The first step And I have four check bits The first step is to add four zeros to the end Since I have four check bits Now I'm going to do a long division Wow, this might take a little while Let's go with our divisor and write it out So we're going to take away one zero one one Oh sorry, good grief No it's a one zero zero one one When we take that away what do we get? One minus one that's a zero that's gone One minus zero is one zero zero zero One minus one is zero zero minus one Sounds like minus one Which is actually one in modular to addition Okay, now I could write up the top Just that the quotient goes here For instance I got a one here when I divide it But we're not going to keep this anyhow So I'm going to ignore it I'm going to keep going on now taking things away So now we're down here And we're going to take values away I'll move down what we got here There's a one So again I want to take away one zero zero one one Boy we're in luck That's the same thing here So this is all going to go to zeros or zeros And now what we're left with is down here I'm going to copy down these digits Now I'll continue subtracting one zero zero one one from this And I'll get zero one one zero one And I've got another three zero zero zeros here Do it again one zero zero one one When I subtract that I get one zero zero one zero zero One more subtraction one zero zero one one Cancel cancel cancel cancel cancel I'm left with here one zero And that's the final remainder What I would like to do then is take that remainder And use it to modify the bits that are transmitted I would like to send zero minus that I would like to add zero minus that value So that it'll be evenly divisible What will end up happening is that Well basically because this is all modulo two End up putting this value zero zero one zero from the bottom Zero so these were zeros up here And then the checksum bits that we'll send out Sorry the CRC bits that we will send out will be zero zero one zero That's a little messy let me clean that up And you can see yeah here it is And at the bottom there is the transmitted frame You can see it's the data bits And now we computed our CRC to be zero zero one zero Great here there's also a little more information Like the quotient which gets thrown away And I've shown some other steps here Which were omitted in the middle Just so you can work through that And check it all if you would like At the receiver you do the division And you should get zero We'll skip that in the interest of time As with checksums Let's think about CRCs for the moment And just ask what kind of protection we get from them The kind of protection is going to depend on exactly What generator we used Now unlike the other schemes We're not really going to be able to work this out for ourselves CRCs are based on these mathematics of finite fields People have calculated over the years Good properties of different generators And in fact there is a standard CRC Which you'll see almost everywhere Even though better ones exist these days There's a standard CRC It's defined to be this number That's actually a polynomial If you write it out But this CRC is used on Ethernet Wifi all sorts of places This CRC I'm just going to tell you the properties Since we can't really work them out From first principles ourselves The hamming distance of this CRC is four This means it will detect all errors up to And including triple bit errors So any three errors One, two or three errors you're covered Four errors there must be some way to get around it It will also detect like parity Any odd number of errors In addition it will detect or burst up to k bits in error Where k here for a 32 bit CRC That would be 32 bits And it's also stronger than checksums In that it's not vulnerable to systematic errors Check sums because it's simply a sum If you were to do something like Insert a lot of zeros inside a packet You wouldn't alter the sum You wouldn't pick it up With a CRC if you move data around Or add zeros or splice things together You will pick it up And finally to wrap up Let's talk about error detection in practice CRCs the strongest form we saw Are very widely used on all sorts of different link layers They're used in Ethernet and NATO 211 as I mentioned They're also used over your DSL link Cable links and so forth They're an industry standard Check sums, you'll also find a fairly widely used in the Internet By all of the Internet protocols TCP, IP, UDP and so forth Compared with CRCs though While they're simpler to compute, they're weaker And I would hazard to guess That if the Internet were being designed today Stronger forms of checksumming would be used Finally there's parity Which says it's a good motivating example For us to work through But it's little used in practice Because we can usually afford More sophisticated schemes for error detection G'day viewers In this segment we'll talk about codes Which can be used to correct errors In messages received across links So the context for this segment Is the same as the previous two Which is that we know That messages can be received with errors Caused by noise in the physical layer What we would like to do in this segment Is devise codes So that we can look at the structure of the message The bits we receive And from those bits work out Not only did an errors occurred But guess what the message was Which was actually sent So this goes a step beyond Codes for simply detecting that an errors occurred And we will go through the example of hamming codes They're one of the simplest Realistic error correcting codes And then I'll mention other codes Which are used in practice Finally we'll talk about Why you might use detection Rather than correction Since it seems as if you could come up with codes For error correction Then you would want to use them Rather than detection Because they're stronger But it's not quite that simple Okay Well to get the ball rolling here Let me remind you why error correction is hard Now if we had reliable check bits That you could send To go with the data bits Everything would be much easier You could send that reliable information And use them to describe the structure Of the message and narrow down Where the error was in the data But of course there can be problems In all of the check bits In fact the error could be in the check bits As well as the data bits The data might even be correct That would be all we would care about If the error was in the check bits That would maybe throw us off We would think there was an error Even though we actually wouldn't Necessarily care about it Going a little further Just suppose for the moment That we could construct a hamming code With the distance of three That means that we would need at least Three single bit errors To transform a valid code word To any other valid code word If we then have a single bit error That will be closest to a single Unique valid code word So if we can assume And here's one of the key assumptions If we can assume That the errors we will see in practice Will only be either zero or one bit Then we can correct errors By mapping whatever bits we received To the closest valid code word This argument also generalizes To work for correcting D errors If you have a hamming distance of 2D plus 1 Here's a diagram That helps us visualize this intuition You can see here in this code The pink circles represent a valid code word So the data bits and the check bits match Whereas the gray circles here They represent an error code word Where you've got a bunch of bits in But the data and the check bits don't match This code has a hamming distance of three Because we need to go at least three hops Which is changing three bits To get from any valid code word To any other one Here's another one Now let's look around A This circle This is the code words Which are within a single bit error of A What we will do for correction Is when we get in a code word Such as this one here We will say This is closest to A So therefore I'm going to correct that By saying A would be sent You can see that that must be the case If we got either zero or one error Because there's no other way That we could have got from a valid code word To be so close to A This slide just cleans it up a little bit So you can see it a little more clearly Okay so hamming codes Give us a way of constructing this code With a hamming distance of three And also an easy decoding method Which will allow us to do the correction And move to the closest valid code word In a hamming code There are parametrized families So if you pick a K for a number of check bits Then you can look out in How many data bits go with that Using the expression two to the K Minus K minus one If I have K for three for example Then I will end up being able to Send up to four data bits The way a hamming code is constructed Is you take all these bits in the code word together And you lay them out Putting check bits In any position P there is a power of two Starting your numbering from one The check bit In the position P Is then a parity sum Over all of the positions Which have a P term In their binary values When you write them out Okay that's all big mouthful Let's work through an example To see how it goes Okay now here we have some data The data is zero one zero zero We're going to use three check bits So we have seven bits all together They're shown at the bottom here Let me just write in The parity bits Or check bits and the data bits Parity will be in positions That are powers of two So that's one Two And four These are going to be the check bits The data then will go elsewhere So if I write the data in Left to right I've got a zero One zero one Now let's compute some of these parity sums Check position one Covers Sorry the check bit in position one Is going to cover all other positions Which have a one in their binary expression That's going to be one three five and seven That's P one We can ignore the one itself Because there's nothing in it yet We're going to add it the three The five And the seven Zero plus one plus one is equal to zero We'll put a zero in here Check bit two Is going to cover positions with two bit In the turned on in the binary expression That'll be two and three and six and seven The parity sum here two and three is zero Six and seven is zero One that's equal to one So we'll put a one here Parity bit three Is going to cover positions Where there are is a four in the binary expression So that is four five six and seven So if we add those together One and zero and one we get a one So I'll write a one here This then is how we constructed a code word For that particular data in the hamming Code with four data bits and three check bits And that will then get sent out the wire Okay here's a cleaned up version of that And I think we have our Parity sums are right Do we know one zero one Oops no I didn't Flip back one plus zero plus one that is a zero So parity bit three in the fourth position here Should have been zero Okay now we have that right Moving ahead the hamming code gives us a way to decode these codes What we do is we proceed by recomputing all of these check bits Using the same parity sums Now including the check bit parity value itself Because there's a value in there We then take those check bits and arrange them as a binary number And look at the value this value is called the syndrome This value will tell us the position of an error If it's zero there's no error If it's another number like three for instance Then the bit in position three is wrong And we should flip it to correct the value Wow it's pretty cool that this works out This was all worked out by Richard hamming And you can read about it in this paper that I mentioned In a previous segment So we're going to try and work through an example Okay here is the code word just that we had from before With all of the parity sums computed Let's uh let's recompute the parity bits Parity bit one we're going to add positions one three five seven And that's equal to zero parity bit two We're going to add two and three And six and seven That's a zero Parity bit four we're going to add positions four five six and seven That's a zero plus one plus a zero plus a one And guess what that's a zero Our syndrome is zero zero zero So there's no error Yay Then our data is what we get If we take everything but the check bits We see it is zero in position three One in position five zero one in six and seven Here's a cleaned up version On the other hand we might actually have had an error during transmission We want to correct it that's the whole point So let's check to see that this method actually works Parity sum one we add up positions one It's a zero three five and seven We get a zero parity bit two We add up positions two and three And six and seven That is a one Parity bit four we add up positions four five six seven That is also a one Okay, what's our syndrome then The lowest order digit is parity bit one In position binary at the least significant bit That's a zero ahead of that we have a one and a one Or six the binary representation of six This means that there is an error in position six Or which we can see is right So we're going to flip that The data that we get then is a zero A zero a one sorry a zero and a one A zero and a one That's what and that's what the real data should be Yes and we can see here that it's correct After we've flipped the bits Now the bad news here is that the error codes for correction Which you use in practice are generally much more complicated Than the Hamming codes Hamming codes are useful but they're fairly simple Some codes which you widely used in practice are convolutional codes They tend to take a stream of data and they output a mix of bits at all positions This mixing process makes the output bits less fragile They're decoded with what's called a Viterbi algorithm Which has the advantage that it can use the confidence Information from the bit values from the physical layer So we can know if some signal was really high and it really looked like a one Or if it was close to 5050 and maybe it was a one This turns out to be useful There's another kind of error code Which is widely or which is becoming widely used in practice And that is the low density parity check code Low density parity check codes are based on the mathematics of sparse matrices And they're decoded iteratively using what's called a belief propagation algorithm This is the same algorithm which is used in machine learning All comes also comes up in communications Their state-of-the-art codes today and they're increasingly being widely used An interesting side note is they were invented by Robert Gallagher One of the pioneers of network on the theory side As part of his PhD thesis in 1963 And then they were promptly forgotten for more than 30 years Put aside until they were computationally more viable Because they do involve a fair amount of computation And now those codes are all of the rage I can also talk briefly about error detection versus correction Let's consider a hypothetical example What would it be better to use? Error detection or error correction for a particular example It's going to turn out that which one we want to use is going to depend on the kinds of errors The patterns of errors we're going to correct But suppose you have bit messages which are 1,000 bits long And you have an average bit error rate or BER of 1 in 10,000 That means on average one bit will be an error out of 10,000 bits over a long-term average What should we use? Detection or correction? What do you think? How would we even go about working this out? Really we would like to use the scheme which has least overhead That will be a measure of goodness But it turns out that we can't work it out yet We actually need to know more about what kinds of errors would actually occur So I'm going to posit two different models The first model for our errors is the random 1 in 1,000 bits are erred at random Well this means sorry 1 in 10,000 bits are erred at random This means that any message is likely to have 0 at most 1 errors Most of them have 0 Now to do error correction To handle about 1,000 bits If you go through some of the hamming expressions from before You'll find that you need about 10 check bits to be able to correct a single error So the overhead here per message is how we'll work it Would be simply 10 check bits 10 bits On the other hand that's for error correction On the other hand suppose we used error detection In this case we would need only let's say 1 check bit To detect that there's an error Because we could use a simple parity bit if we're going to have 0 or 1 bits wrong But then of course if there was an error And this will happen maybe a tenth of the time If messages are 1,000 bits and we're going to have an error every 10,000 bits or so Then a tenth of the time we're going to have to retransmit that message And we all have to send 1,000 bits to retransmit it And this is a rough approximation But this is going to get us close enough The overhead there will roughly be 1 check bit plus 1,000 bits A tenth of the time that's 100 Just call it 101 check bits Wow well that's a lot of overhead So we would be paying a lot of overhead to detect those errors For the random error case where errors occur It seems to be better to use error correction On the other hand here's a different model Let's assume that errors come in births of 100 Well in this case Rather than having one in every 10 packets Likely to contain an error We're likely to have not one in every 10 But one in every 1,000 packets have an error Or maybe two out of every 1,000 If those 100 bits are spread across two packets So errors are going to be rarer In terms of packets or frames But when they occur boy it's a big error If we use error correction You've got to send the correction on every frame Just in case it's in error How many bits would we need? I don't know how many bits you'd need to correct An error that's that large 100 births of 100 bits Let's just say you need at least 100 bits of error correcting code To be able to correct 100 bit errors Probably a lot more What about for error detection? Well we would like to be able to detect Something that's gone wrong Even when there are 100 bits in error How many bits to do that boy we need? I'm not sure Maybe something like 32 Because then we would have the probability Of 1 on 2 to the 32 That something's gone wrong That's quite small That's basically 1 on 4 billion Of missing an error If there's a nice random error So 32 might do it there Plus of course If you actually do get an error You'll need to retransmit it So we'll need to send 1,000 bits again But we'll only need to resend these bits 2,000ths of the time So we're going to need our overhead here It'll be 32 plus 1,000 divided by 2,000 So 1,000 divided by 1,000 times 2 So that's 2 That's about 34 bits You can see that the overhead here Is mostly error detection code Not the retransmissions So in fact for this case Error detection turns out to be better To summarize that point Error correction is most useful When the errors are expected It's the normal case Or as an interesting aside They're also useful when there's no time To do a retransmission Because you need information to live it quickly Error detection on the other hand Is usually more efficient When errors aren't the expected case So sending long error correcting code Information would just send more bits Which are wasted Or when errors are large When they do occur Because in that case You would need an awful lot of error correcting code bits To be able to deal with them And finally Let me tell you a little bit about error correction practice We find that error correction Is heavily used in the physical layer Usually with advanced codes Like the low density parity check code That's becoming common Older convolutional codes In fact widely used in practice But LDPC is going to be the code of the future For all sorts of uses Wi-Fi Digital television Fourth generation cellular And so forth And that's because errors are expected The normal case in the physical layer And we'd like to throw some machinery at correcting them On the other hand Error detection is widely used With retransmission techniques Above the physical layer So in the link layer and above In the transport layer too This kind of mechanism Is really about dealing with residual errors Once the physical layer has got a lot of them down We'll also see much later on perhaps That correction is also used in the application layer When it's used in this context It's often called forward error correction This usage also has a different kind of error model Usually at the application level If you're correcting errors You know when you've lost bits Maybe you would lose a whole frame And stripe your information across multiple frames And want to correct it This error model is called a narration model But previously we didn't know If there was an error Which bits there were in Now here you know that there's an error in a bit And you don't know what it is This is actually very close to the setup That's used for codes that you might have heard of Like read Solomon codes Which are used widely in CDEs, DVDs and so forth So that if you were to lose some information on the disk Due to a scratch or something You could correct the Use an error correcting code To work out what the information was So that's error correction Now you know something about how to Correct, detect and correct errors In messages that are sent across the network Good day viewers In this segment I'll give an overview of the link layer To remind you where we are in the course Okay so here's our layered protocol stack And if you recall We've already done the physical layer We've talked about that Now what I'm going to do is Finish off the link layer Which builds on top of the physical layer To be able to send frames Individual units of information Across a link between computers Now we've already covered some of the Different techniques and problems And solutions that you find in the link layer In particular I've already talked about framing Which is the ability to delimit the start and end of messages So we can send complete units of information Called frames across a link And we've also talked about error detection and correction Which allows us to handle some kinds of errors As information is sent across links When you put these topics together We've actually seen quite a lot of the link layer For instance they allow us to construct A DSL link That's something that many of you might be using right now To access the internet from home And we can understand the techniques Which make a DSL link work What we're going to do now Is go beyond that and cover these three topics To round out the link layer These are actually three pretty exciting topics The first topic is that of retransmissions Which allows us to handle links where loss is quite common This is the case for many kinds of wireless links Such as 802.11 Without a mechanism such as retransmission Many frames would be lost as they're sent across the link And the network as a whole would become inefficient So we're going to want to retransmit information To get it safely across that link The second topic we'll cover in this unit Is multiple access In the links we've looked at so far There are two ends and one end just sends frames And they arrive at the other end But sometimes you can have multiple parties All of whom want to access the one link Just think of an 802.11 network Where many different clients, maybe more than two Maybe ten want to talk to the same AP That's a single wireless link And we need some multiple access scheme To coordinate the way in which these different users Will use the link We'll talk about classic ethernet schemes And also 802.11 will appear again And in the third topic To round out the link cloud Talk about something called switching Switching allows us to use boxes called switches Unsurprisingly To combine individual links together Into something that really looks like a much larger happy link That connects a host to all of the other hosts On the switch network It's used to build something called modern ethernet Actually by the time we've seen all of these units We'll know quite a lot about how to build networks For instance, we'll know a lot about how 802.11 networks work And we'll also know a lot about how modern switched ethernets work These are the garden variety wired networks that you find If you go to any enterprise or campus and so forth And ask to look at the network Okay, so let's get on with it G'day viewers In this segment we'll talk about retransmissions As a strategy for handling errors Okay, so just as a bit of context We have two general strategies Which we'll use to correct errors in networks The first strategy is to detect that an errors occurred Say with an error detecting code And then retransmit the information across the network We've already seen the error detecting code So now we're going to focus on the retransmission Half of this strategy The overall strategy goes by the name of ARQ Somewhat archaic name It just stands for automatic repeat request But we can just think of it as retransmissions The second strategy is to correct errors with an error correcting code Send enough information as part of the message That the structure can be checked And any errors that occur on the way can be corrected We've already looked at how this strategy works As part of our exploration of BellinClayer And I'll give you just a little bit of context On reliability in general before we jump into retransmissions An important question for us to consider Is where in the stack we should put reliability functions Well we have a whole stack here Should our reliability functions for dealing with errors Got the physical layer The link layer The network layer The transport layer or the application layer What do you reckon? Five different choices The answer Is essentially that reliability functionality Should go everywhere in the stack Reliability is one of those key issues for networks Networks have to be able to deliver information reliably And to support that each layer will do its part The key issue here really is How each different layer should contribute to the overall reliability What we will find is that at the low layers of the protocol stack Like the physical layer Error handling functionality will mostly be there to mask errors As we saw with an error correcting code This is often as a performance optimization Looking at retransmissions at the link layer is again about masking errors If retransmissions occur as in Wi-Fi The higher layers like TCP will never know that there's been a loss They won't have to worry about it The error will be masked And this will generally improve performance On the other hand All the protections we like at the low layers Won't stop things going wrong at the higher layers Maybe a sending application Can't connect to the right receiving application Can't find the right path through the network Or a message is received which is unexpected on the other side No amount of scrubbing the bits as they go over To detect and correct any transmission errors Will handle these scenarios So the higher layers of the protocols Will also need their own functionality to handle reliability This functionality is mostly then concerned with correctness And usually recovery actions Rather than performance and masking errors So that's reliability in general Let's go on to ARQ ARQ is used in Wi-Fi And we'll also see it in TCP It's used where errors are expected Or they're common enough And they need to be corrected In Wi-Fi it's because it's wireless And there's a lot of loss So packets might be lost In TCP it's because packets might be lost In the network due to congestion We'll cover TCP later Now we're really just talking about the link layer But much the same mechanism is used The rules for ARQ are fairly simple At the receiver All you have to do is automatically acknowledge correct frames And what an acknowledgement means Is that you will send a short packet From the receiver back to the sender This short packet is called an act Short for an acknowledgement The sender, the rules of the sender Is simply that you automatically resend the frame If you have not received the act After a certain time period This is called a timeout So a timeout essentially means That the sender hears no act Within a certain timeout If that's the case The sender will automatically resend Here we can see how ARQ works Let's just go through some examples This is the normal operation case And this is a, well, no packet loss No frame loss occurs And this is a new kind of diagram for us This is a time sequence diagram The sender and receiver are both shown as vertical lines In this diagram time runs down the page So I'll trace over the action on the diagram Two things really happen here The sender sends a frame to the receiver Here we go The arrow slopes downwards Because sending takes some time So time passes to send this message across the network But at any rate the receiver receives the frame And it sends its own message and act Back to the sender to say, yep Got a good packet there This act is received before the timeout period passes So the sender doesn't need to resend Everything's good The frame has been transferred across the network And no retransmissions are needed Here's the loss and retransmission case The frame is sent Something happens Doesn't make it to the receiver correctly After a certain amount of time passes The sender says, hey, what's going on here I know something must have gone wrong And it automatically resends the message To the receiver This time the message gets through The receiver sends an act back And I guess that is before another timeout passes That being the case Both sides are happy This could go on if the more frames were lost The sender would repeat again and again and again Now there are a couple of things we might note about this diagram First you might actually wonder how it is that a frame can be lost inside a link I mean what happens? Does the signal just get tied and stop propagating? No, the signal continues to propagate Two things could happen The frame could make it to the other side But an error could be detected Because some of the bits were corrupted When this happens It's normal for the receiver to throw the message away And not take any action Because it's uncertain what the correct message is So this could look like a message disappearing Even though it really reached the receiver However, it's also possible that the receiver will not even see the message This could happen if the transmission error is severe enough That say the framing was affected In this case the receiver might not even find the starter frame So it might not even detect that there is a frame there This would look like a frame has been lost inside the network A second thing to note is you can see why ARQ In the simple form here is normally done by having the sender automatically Resend a message It's difficult for us to have the receiver send a message to the sender saying Hey, you know, could you send that again? Here the receiver doesn't even know that it's missing a message It didn't even hear something So it's in no position to request it again Even if it did The ARQ is just another frame It could get lost So the sender might not hear the message to resend So this is ARQ ARQ looks fairly simple as a mechanism Once you get it, you just automatically resend But you know, a funny thing about network protocols Is that there can be some quite subtle interactions And that's also the case with ARQ We'll find this a lot for network protocols With ARQ there are two non-trivial issues that I'm going to talk about The first is this timeout What should the value of the timeout be? We've got to pick something How long should it be? And the second is actually a more serious issue About how to avoid accepting duplicate frames as new frames If the sender sends three frames Three different frames across the network One, two, three Maybe with some retransmissions We would like the receiver to receive the same set of frames In the same order One, two, three It's no good if the sender sends three frames From a higher layer It passes them over the network And the receiver thinks that four frames have in fact been sent across the network This could really muck with messages if they were transformed In some ways they went across the network We don't want that to happen In fact, what we want to happen for ARQ Which we also usually want for many protocols Is we want performance in the common case All right, so performance is linked to the common case But we want correctness always No matter whether our performance is good or bad We want this protocol to be correct So let's look at these two issues Timeouts Okay, well the value of the timeout is one of these Not too big and not too small kind of issues We don't want it to be too big Because if it is too big We'll sit around twiddling our thumbs for a long time The link will go idle and we'll be wasting network resources If it's too small The ARQ will be on its way But we'll panic a little early And we'll go ahead and resend a packet or a frame This is also a waste because we could have sent a new frame Now, coming up with a value for this timeout Is fairly easy on the LAN In the case of most links And that's because for a LAN like a Wi-Fi There's usually a clear worst case In the case of Wi-Fi, for instance You know about how big the network can be So you can work out the maximum propagation delay Wi-Fi also has rules that are a sender Sorry, a receiver needs to send an act within a certain time period So we can usually bound pretty well when an act will come back And that's the case for most links However, timeouts are actually much harder When we're talking about sending across the internet as a whole And timeouts in the case of ARQ being used at the TCP level And this is because there's a lot of variation In the amount of time it can take to use a path across the internet You could be sending next door or to the other side of the world There can also be variation due to other traffic effects on the internet So it's very hard to predict We'll revisit this topic later For now, we'll mostly ignore timeouts and pick a value that's about right Just to make the performance good Okay, duplicates is a more thorny issue Let's see what happens if an act is lost Okay, here's our frame being sent The act comes back, the act is lost What's going to happen? The sender will not see anything And so after the timeout period, the sender will send the frame again The receiver will see it and send an act Great, looks good Except What happens at the receiver here? We get another frame The receiver has no real way of knowing what this frame is Is this a new frame? As far as the receiver knows, it might well be If that's the case, the sender will think it's sending one frame The receiver will get two frames and the network has gone astray Here's that diagram cleaned up Similarly, what's going to happen if the timeout is early? Here's our frame being sent Our act coming back, but just a little late The timeout goes off here So we will send the frame again And the receiver will receive it and send an act Again, what's going on here? As far as the receiver is concerned We've got another frame here A second frame, this is probably the next frame It's a new frame, but it's not Because of the spurious timeout And that diagram's cleaned up Okay, we need to fix this problem To ensure that the retransmission mechanism is correct To do this, it turns out that it's required That both frames and acknowledgments carry sequence numbers The sequence numbers, we're going to check them As part of our protocol, the receiver To make sure that we've got the right frame And the protocol is operating correctly Now, it turns out that in the protocol I'm showing you Where the sender's only sending a single frame at a time And resending until it gets through We only need a flag, a single bit To indicate two different states or two numbers To distinguish the current frame that's been sent From the next one That's going to be sufficient The name of the protocol in this case Is called stop and wait Let's see it in action So our two states with a single bit We're just going to call them zero and one We're going to alternate packets And number them zero and one, zero and one So here's how it would work This is a frame F for frame We'll call this one zero So I'm going to get an act for that I'll call that A zero Okay, the sender will now advance to the next frame It will send F of one And we'll act A of one You can see here at the receiver First of all we get frame zero And now down here we can see this is frame one We have some way to distinguish these two So here's this cleaned up And you can see I've added the timeout Just to show it's the normal case Let's look at some of the problematic cases from before Here's the ACLOS case So what's going to happen when we have ACLOS? Well after the timeout The sender will resend Now since it's a resend It is sending frame zero The receiver will act Act zero Here The receiver received frame zero Now it is receiving frame zero again So the receiver is clear That this is a resend Yes, got that one right Always comforting Okay, the other case A spurious timeout The timeout goes off a little early We'll send frame zero We're going to act Frame zero The receiver Here it got number zero When here it can see it is a resend Wonderful You'll also note over here The sender is going to get another ACLOS for frame zero Oh okay, that's fine I guess that's what it expects since it's sent two The receiver Sorry, the sender here does not actually know whether here is first ACLOS It probably thinks this ACLOS could be in response to the second time it's sent It's just got a very short timeout For all it knows the first frame was lost And the second frame got through and produced this ACLOS It can't really disambiguate these cases And it doesn't matter A protocol is correct in either case Even though the sender and receiver Don't necessarily know what's going on That's all of the subtlety and the design of the system So here's a cleaned up version of that figure And now you've seen stop and wait ARQ and all other rules And this is basically the protocol This is how it works And you've seen the different cases Before we finish I do want to tell you about one limitation of stop and wait Stop and wait allows only one frame to be outstanding from the sender at a time That is the sender tries to deliver its frame Resending it until it's there Before it moves on to the next frame That is effective for a LAN And it's used in Wi-Fi But it's not effective for networks That have a high bandwidth delay product That's what BD is Let me just write that Bandwidth delay And the reason for this is Because with a high bandwidth delay product Many packets could fit on the network at one time But with stop and wait we'll only send one Let's see an example Here we have a picture of a network Where the rate is 1 megabit per second And the delay is 50 megabits per second That means that the round trip time Or the time taken to send a frame across And receive a reply is going to be 2D Or 100 milliseconds How many frames could we then send a second? We could send 10 frames a second And if you imagine a frame is roughly 10,000 bits That's about 100 kilobits per second Hmm, that's not so great considering we've got a megabit per second link 10 times as fast What would happen if we raised the bandwidth to 10 megabits per second? The rate of the link Well actually you wouldn't be able to send any faster With stop and wait you can only send up to 10 packets a second over this link So the maximum throughput you can achieve Is 100 kilobits per second No matter how fast the rate is Wow, that's not so good The generalization of stop and wait Which handles this problem Is called the sliding window algorithm The sliding window algorithm allows up to W frames to be outstanding What we want to do is set W, the number of frames outstanding To be roughly twice the delay Expressed in packets Twice the delay is also called the RTT Where RTT stands for round trip time That's a useful thing to know And if that's the case, as you can see from the figure here We'll have multiple packets in the network going across and the X coming back And this traffic will keep the network busy This is what we will use when we get to the transport layer in TCP Because the bandwidth delay product is higher than it is for most links like a Wi-Fi And when we get there we'll see various options For handling the way we number frames, X and so forth But there's no need to go into all of that now We'll look at that later And for now you know how ARQ and retransmissions work with stop and wait G'day viewers In this segment we'll talk about multiplexing schemes Which allow the bandwidth of a link to be shared Okay, so recall that multiplexing is just the fancy network word for sharing The classic scenario is sharing the bandwidth of a link amongst the different users I'm going to talk about two different methods Which you use to do that Time division multiplexing and frequency division multiplexing Here we go Okay, so in time division multiplexing this is simply sharing over time Different users take turns on a fixed schedule at different times So you can see here we have traffic coming in from three users on the left And a portion of the traffic is taken from each of those users in turn So this diagram is showing the evolution over time Of how the users are sharing one link or a channel You can see one user here in the pink user two gets to send some information at the beginning Then the user has to wait and gets to send no information while users three and one send And later user two will get to send again, gap And then later user two will get to send again And this is our regular schedule that we follow There may be a very small gap between these transmission times These transmission times called the guard time just to allow for a transition from one source to another Conversely, in frequency division multiplexing The user shared the channel by transmitting simultaneously on different frequency bands So this picture shows the way the channel is divided in frequency Each of these users has about the same amount of bandwidth to send The middle user, the bandwidth profile is shown in pink And you can see that for all of these users they have about the same bandwidth requirement To share according to frequency division multiplexing We just shift the frequency band on which the user is transmitting to a different portion Of the overall channel The width of the frequency band describes the amount of or limits the amount of the data rate With which the user can send Moving this band round in absolute frequency space Does nothing to the data rate It keeps it the same As we add all of these different transmissions together onto the same wire You can see here that we have three channels in three different frequency bands Which correspond to the original transmissions So now we're sharing the channel in frequency space That might be a little strange to get your head around So let me just draw the time evolution of how we're sharing the channel With TDM if we just consider one user What's happening is that user gets to send at a high burst They get the whole channel Like user 2 gets to send all of its bits at the whole channel rate Then they get no bits per second for a while while other people send When it's their turn again they get to send at the very high rate Then no bits per second High rate No bits per second High rate and so forth So their evolution of their bit rate over time looks something like this On the other hand with frequency division multiplexing All users are sending in parallel At their lower bit rate on the channel By simply dividing the channel into different frequency bands So the same user will have a bit rate like this It's continuous but at a slower rate Time division multiplexing and frequency division multiplexing Are simply alternative ways to divide the resources of a link Neither one is inherently better Neither one provides for more capacity They do have some trade-offs You can see here in time division multiplexing It's a little more complicated in the sense that we require synchronization Of where to send This is just one user so the other users have to fit into these time gaps In the middle On the other hand with time division multiplexing When you get to send You're sending the information at a faster rate So if the information arrives from an upstream link Just at the beginning time, just here Well the delay will be lower because it will go out at a faster transmission speed So there are maybe a few minor trade-offs But there's no inherent difference in the capacity we're getting Here's that cleaned up version of that diagram So time division multiplexing and frequency division multiplexing Are typically used in telecommunications To statically divide the bandwidth or the resources of a link They're well suited for cases where traffic is continuous And there is a relatively fixed number of users So classic scenarios for using these techniques Would be with for example, television or radio stations These stations might always transmit You could allocate them a different frequency band They can all send in parallel on their different frequencies And the spectrum is used effectively This is good With cellular systems such as the GSM Is a second generation cellular system One of the most popular cellular systems still deployed today Is we transitioned to 3G cellular systems Calls in GSM are allocated on different frequency bands So we're using frequency division multiplexing to divide the spectrum Within each different frequency band Time division multiplexing is used to give many different calls A slice of that band at different times So these methods can be combined However, there's a problem for the kinds of traffic we would like to handle Network traffic And the issue is this Unlike a radio station or a TV station Which is constantly putting out a signal Network traffic tends to be very bursty It's described as an on-off source If you just think for a moment about your own n