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.