0:00

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.

Â 9:00

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.

Â 10:20

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?

Â 13:56

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,

Â 16:30

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?

Â 18:35

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.

Â