Now the problem is that it is despite those two great ideas, you can run into the following situation. Let's say you are station A, okay, and you want to say talk to station B, which is an access point, and then someone else across from you in the Starbucks or in a hotel room hotel lobby want to talk to this same AP. Now, if you both talk the same time actually, you will collide, okay. But, let's say, your sensing range has only this radius, which is the same as your, let's say, transmission range, okay. So, you can not sense the existence of C, and when C is talking actually you can't even hear it. So you may just start talking again, and then be, suddenly get confused. So this is the problem that, two stations in WiFi may interfere. But they do not sense each other. And this is one of the fundamental limitation that says that if you want to use random access, and yet, sensing range is not the same as interference range, then you have a problem. So how can we tackle this problem? Now, so far, we have used no explicit message passing yet. Now we're going to need a little explicit message passing, have to send some control signals, what we call rts cts, okay, request to send and clear to send. So the basic idea is that, the sender. Okay, when you want to send something you first send a control packet. It's a tiny one called a request to send, 'kay? And then, upon a small listening interval, the receiver will send another control packet called, clear to send. And then after another little interval, you can start sending. Now, whys would this work? It works, because when you send a request to send. Okay. Everybody in your int, transmission range hears this. So B hears this, and then B will then send a clear to send. And everybody that B can talk to can hear this, including yourself and others who might want to talk to B. Oaky. Now assuming a symmetric, transmission range. B talk to C is same to same as C talk to B for now. Now, C will then say, Oh! I didn't ask to send something, but I get a clear tone signal, that means somebody else is going to send something. So, I will refrain from talking. Okay again all these discussion here on tcp assume that the network elements obey the protocols. If they actually try to trick the system then you need some other kind of game thematic analysis. Alright so now A says hey I send RTS and I got a CTS. That means I'm clear to send because all potential interfere I cannot hear have got this CTS and will they refrain from sending. So, that's the smart idea of RTS-CTS use a little sequence. Okay? So, there's the overhead. You have to pay the overhead of the spending this much time just doing control signal, signalling in order to guaranty that the data will not be colliding, even when you cannot sense somebody. So, this is the famous hidden node problem. C send a note to a or vice versa and, rts cts solution of that problem. Of course it's not perfect, for example, the rts packets may collide, so it does not completely solve the issue, but helps quite a bit. All right now, we're going to try to understand csma built upon the ideas one, two, three that we just mentioned. Okay, wait and listen through carrier sensing, Use randomize the binary exponential backup upon collision, that is, no acknowledgement back, and use RTS CTS explicit control messaging if needed. Well it turns out that analyzing a CSMA and WiFi is not that easy, okay? For a more proper understanding we need to use something called two dimensional mark of chain to specify the protocols, because there's a lot of probabilistic actions and extracting those out like in TCP our discussion of TCP will not have enough predictive power. So we need to do some probability theory and instead of doing a two dimensional mark of chain which we will not have the prerequesites in this class. We will do a very basic, a little hand wavy type of basic probability argument. The main difficulty here is that, the frame collision. Depends on the action of each radial, as well as the history of binary exponential back off. So put B. And the binoexponential backoff is turn coupled with the transmission decision. Should I transmit or not which is again probabilistic by each station. So because of this complication even this hand wavy simplified version of argument would take a little derivation, okay, through basic probability theory. Now the basic idea where we want to do is we want to look at true probabilities. One is the probability, the probability okay, of transmission. At the given time slot. The other is the probability of collision. And then we'll try to relay to these two probabilities, and derive two equations, and solve two variables. Now let's go into the detail here. First, a little notation, say we want to derive the performance metric of CSMA random access. Denote that by S, okay, which is really the average through put, it's the average number. Of bits, transmitted successfully over. Successfully transmitted. Okay. A time slot divided by the average length of a time slot. There're different kinds of time slots and this is an average notion. Okay so average number of bids successfully transmitted over the average length of a time slot. That is as they will want to arrive, and want to see how does s depends on different barometers in problem. Okay, we're going to use a p sub t to denote the probability. Of, transmission. In fact, I should say a probability of at least one, it could be more transmission in the entire wifi network. And then we use P sub S to denote the probability that the transmission is successful. Given a time slot. And that means, there must be on one single transmission, conditioned on someone. Transmits. So it's a conditional probability. Okay. And now we're going to use tau to represent the probability, that a particular station so your phone transmits at a given time slot. The difference between tau and pt is that pt is the probability that someone in the whole network transmits, and this is for each individual. Now let's assume that each individual station acts independently. Okay. And now we're going to define some time slots. T, okay, we say TB is the time slot when there is basically, back off. Okay everybody is backing off nobody is transmitting. T sub C is the time slot where there is a collision. Somebody transmitting but turns out more than one and Ts is this one and only one transmits so there is a success for transmission. So Tb, Tc, Ts are little different will work through in numerical example in the next module. So these are the main notation. Now we can look at the basic quantities here. First of all, the chance that there's no transmission at all, the probability is one minus P sub T. Okay? And the time slot associated with that is TV. The probability that there's some transmission, but it. Doesn't go through, is pt times one minus ps. And the, the time slot for that is collision time slot. The third one is that somebody transmit, and, actually there's only one, so it's successful. Pt times ps and then the corresponding time slot is t sub s. So this expression is the denominator for s. It's the average length of a time slot, okay, it's this quantity. So we have this quantity now. We want to now get numerator. The average number of bits. Well, what is average number of bits? Well, it is PT times PS. That's the probability that you have a successful transmission. Okay? Somebody transmits an condition on that. There's a successful transmission. Multiply them together. You get successful transmission probability. And then you times the payload. Denote that by L. So now we have. The overall expression that we need, okay? This is the numerator and this is the denominator. So we divide this expression by this expression, and that is our S. Alright. Looks like we're done. Well this is just a start because we have not yet derived at the expression of PT MTS. So what is PT? Pt is the probability that somebody is transmitting. So the, that equals to the probability that. If you say tau is the probability that one station is transmitting, one minus tau is the probability that a station is not transmitting. Because they are all acting independently you raise to the power N because you multiply self N times. N is the number of stations in this wifi network okay. So it could be five at your home and twenty in a hotspot'kay. So this is the expression that says, no one is transmitting. And a 1- that is the probability that at least some one. It could be one, could be more, is transmitting. Now this expression 1-[ 1- some probability to the power N for a crowd of N, is another type of wisdom of crowd. If you remember, wisdom crowd as a factor of N. And back then in lecture five or six, five, we said that this is what we call, A multiplexing gang.'Kay? Because of independent of actions of crowd, you can have a factor of N reduction of some error metric. Now, this is another type, what we call. Multiplexing gave a diversity game. It says because of independent actions we actually have this one minus some probability to the power N shape at the expression. Alright that's a little detour. So this Pt. Now what is Ps times Pt? That's the probability of success for transmission. Okay. Now for each individual station, that means that you have to transmit, but no one else transmits. So tau multiply one minus tau, n minus one times, and there are n of these independent actions, so the total probability is this. So now we have both pt and pt times ps, and therefore we can substitute into this expression. We got a numerator, we got a denominator. We're done. But wait a moment, we actually don't know what is actually the tau factor. Right, and that's the hardship, hard part. Tao really depends on history of the exponential back off, that determines the transmission decision. So, as long as we can find expression for Tao we'll be done. We can then substitute into these expressions for PTPS, and then substitute into expression for S. Alright. So give me Tao now. Well, one thing I do know is that the probability of coalition. Probability of coalition. Lets express that quantity as C. Okay? Let's assume that this probability C is independent of the which back off stage you are at. Okay? Have you backed off once, have you backed off twice, three times. Let's say we're independent, it's the independent land. This is our approximation and under this approximation we have C equals one minus, one minus tao to the power N minus one. Okay. This is probablity at least one of the other N minus one station transmits, in addition to yourself. Then you have a collision. Alright. Say, hold on. I want to find tau. Now you express something else. A C in terms of tau. How does that help? Well, we're going to find tau as a function of C now. And then, once we have a tau as function C, C is a function of tau. We put the two together. Then, we can solve two variables with two equations. At least numerically. So, that is the game plan. Find tau as a function of C. The probability that you transmit, is a probability of coalition. Alright. The way we do this is a little roundabout. Here is a, an interesting Bayesian expression. Okay. Third time I using Bayesian. Haven't used in a few lectures, the probability of, that we transmit. Okay. We mean well, H station transmit times the probability that. The station is in certain back off state, back off stage I, condition on it, it transmit, is the same as the probability that it is in stage I, back of stage I, times the probability that you transmit condition that you're in stage I. Because both sides of the equation is expressing the joint probability that, you as a station is transmitting, and you are in backs of stage I. I just express it in two different ways. As in the Bayesian expression. Okay, do now I can use a little short hand notation.'Kay now say this is tau'kay times the probability that you in stage I given you transmit equals the probability you in stage I times the conditional probability that you transmit given you in stage i. Okay. So now we can say tau, therefore, equals, or tau multiply pi of tau over p, you are transmitting conditional stage i. Equals p of i. Now, we've, we summed both side across all the back off stages. From the zero stage, which is, certain minimum backup window, okay? W min says that you need to at least back off, up to this much, and then you can randomly choose a point in time between now and W min. All the way to the maximum stage of back off. Now back off cannot keep on going for ever. Okay. At some point you just give up and declare the packet the frame is lost, and you ask maybe upper layer to help you. So we say they are at most the B stages of back off. And each stage is a doubling the window size, during which your uniformly pick a form to transmit. Okay so there are two fixed parameter- W mean and B. B stages Mx and also you have to at least start by waiting W mean number up to W mean number of slots. I keep saying up to because the actual transmission time is done in a random way uniformly sampled between now and the windows hours. Okay. All right so back to this expression. This right hand side is obviously one, because you are summing over the probability in some stage I across all possible stages. So it got to be one. All right. So now, if we can express pi condition on transmitting and p transmission condition on i. Then on the. Alright. So that's the round of Albatian detour we are taking. So can I derive a pi of condition tau and pt conditional I? Well, let's see. P I. Condition on that your transmitting. What's the probability is back up stage I if you're transmitting now? Well that means you must have suffered I collisions in the past, and you have one non-collision right now, okay? So the probability of that is C to the power I times one minus C. But this is not a probability. You have to normalize it. It turns out the normalization constant, skipping the derivation is this. Okay? So this is the expression that we want. Now what about P tran-, from condition probability that your transmitting condition on, on that you are in stage I. Well at this point you have a certain the value of the back off counter at the stage I. Okay? Plus you are using one time slot to transmit. So, there's altogether oneTsubI, plus T sub I is the average area of the back of the counter in stage I, okay. And, you are going to randomly, uniformly pick from one specific time over here, okay. so, it will be one over one plus T sub I. Now, what is T sub I, then? We just need to find T sub I, T sub I, if you think about it, okay, is really the average value between not waiting to two to the power I times w mean. Okay. This is the minimum window of time you have to wait up to. And you've suffered I stages of collision, so you've been multiplying by two I times. So two to the I times w mean. Okay? Plus zero, which is, you so happens you choose exactly, you know, the current time to transmit. And in between the average matter is the half. So this is the expression for T I, which you can substitute over here, and then you get the probability of transition conditioned your in state I. Alright. So, finally, we got everything. More strictly speaking, actually the actual contention window size W is two to the raised to some integral power, then minus one. So, but we're skipping that level of detail here, okay. So finally we say, plug this expression into TI, put it in here, you get P of T condition I. You also know P of I condition on T. Now, plug those two expressions in here as a function of C, and then multiply by tau, summing over I from zero to the max number of stages allowed. That should equal to one. Now that's a complicated looking expression, but nonetheless, now we can finally express tau, okay, as a function, after simplification, of C. You can try this yourself or look at a textbook, and after simplification, this is what you got. So now tau is a function of c, as well as constant parameters, okay, such as w mean and b, in the network. And C is a function of tau. So, this is equation one. This is equation two. Put equations one and two together you can solve for both how and C actually would only need a towel. Now stick towel into the expression of PT and TS and then you stick that expression into the expression for S and finally your done. In computing the fruper through this approximation. Now as a function of what of the constant perometer in your system such as the payload. Now, okay, the maximum number of backup stages is W, and the minimum back up window Wmin, as well as the time slot definition tdtcts, and finally the number of stations involved n. All these are constants given by the network to you, and then you can now finally express s in terms of these constants.