0:00

So, what is really our overall objective here?

Well, we want to get as much data through the network as possible and the way we

measure that is with this thing called throughput.

And throughput is the amount of success and success here is the amount of

successful transmission. [UNKNOWN] or message deliveries that

actually get to the receiver. [NOISE] And are properly decoded at the

receiver. So, the amount of successful

transmissions and bits per second. So, we measure How many bits the network

sends on average in one second and how are you going to get through and that's

the throughput we'll recall. So, we can speak of per device throughput

which is basically on average how much each device gets or we can speak of total

throughput which is how much over the entire network everyone is getting.

And so, that's clearly different from the amount of bits per second we're sending

because Success and just total number are two different things.

Right? because if we have collisions, they're

not all going to get there. And that's what's the difference between

the amount and the throughput. So, now, When we talk about a Random

Access Protocol, Random Access Protocol governs how stations are going to answer

that question that we talked about in the last slide, Which is Should I transmit or

should I not transmit it each time. And we're going to look at how we can try

to optimize the random access protocol in order to get the maximum amount of

throughput. And we'll see if it's a very complicated

question to answer. And we're only going to just graze the

landscape slightly at random access protocols.

There's so many different protocols that have been developed out there.

That are really sophisticated and [INAUDIBLE] down mathematically can get

very difficult so we're only going to look at really basic concepts here.

And, so now, I said the word station and when we mean station, we actually mean

either a device or an access point because never they can both transmit and

they can both receive. So have a station really doesn't

distinguish between device or access point, so now the first random access

protocol that we're going to discuss is ALOHA, and you might think that ALOHA is

a cool acronym for something. But really it's because it was invented

in the 1970s at the University of Hawaii, so it's very fitting to the place of

Hawaii and that's why it's called Aloha, which is a really cool name.

And with Aloha it's very, very simple protocol, so this is the one protocol

that we will look at in detail, and we'll try to apply some math to it to see how

it works all it does is it assigns a fixed probability, or probability really

is just a chance of a device transmitting in each time slot.

So it really has no sensing aspect of it at all.

So there's no sensing going on. And, now, when we talk about probability,

we could get really complicated. But we'll try to just illustrate it very

simply and to just talk about what we're discussing here.

So, if you've ever taken any course [INAUDIBLE] probability, or you've just

taken simple probability. One question you could ask is when you

flip a coin what's the chance of it then it has and you know its 50%, because it

has two sides, but in general then we are not necessarily just going to be talking

about 50% we might talk about 40%, 30%, 20% chance.

And just to understand what that is, really a good way to think about that is

just to think about a wheel that you might spin, like if you've ever seen

Wheel of Fortune before, and what's the chance that it's going to land on any one

of these sections here. Well the more sections you have the less

chance it is that you're going to land on the one that you want, so for instance if

there were ten sections here. And you wanted to just choose one of them

you would, you know, roughly speaking, if you just randomly spun the wheel you

would have 1 over 10 of a chance of landing on it.

And if there were 20 sections you would have a 1/20th chance of landing on it.

So, here when we talk about assigning a fixed probability of transmitting at each

time slot. What we mean is that each device, we

actually basically spin the wheel and choose one of the slots on the wheel and

say, well, if my dial lands on that slot than I will transmit, and if it doesn't,

than I won't transmit.I'm not going to look at anything in the network.

I'm just going to spin my internal wheel of fortune and if it lands then sure I'll

transmit, but if it doesn't then it doesn't, so if the probability was 2%, or

that would be one over 50, then it would basically be saying every one in 50 time

slots on average I would be transmitting, so it's a very low chance and we'll look

at more what that means exactly. So the first thing we want to see is,

what's going to happen as we change that probability of a station transmitting if

it's a low high protocol? Really simple kind of a cool protocol

cause it really is simple. So, let's call it ProbTrans for

probability of transmitting just to keep it simple.

And so, when we have a higher probability of transmitting.

So, my every station transmits more on average or as higher chance.

higher chance means that on that wheel there are less section, so there could be

ab four sections which means you have a 1 4th chance of transmitting or something

like that, because less sections overall. You're going to have more transmissions

on average, right, because everyone is going to land on their section of the

wheel more, but then at the same time you're going to have more collisions,

because every time you have more than one device tram sitting you're going to have

a collision if we're just talking about say a single basic server set.

Now if we lower the probability of transmitting we're going to have less

transmissions which may not be a good thing but, we'll also have less

collisions. So, there's a trade off here clearly and

the question's, what should it be? What should we make that probability

transmitting? Well, let's look at this example right

here. This, this is an example if we start with

a higher probability of transmitting and what we see is in the first time slot.

A transmits to only. Then the second time slot A, B and C all

transmits, that's a collision. So, this was successful collision, this

was successful. This is a collision because they're both

transmitting. This is a collision.

This is successful. Now, in this case we have a less lower

probability of transmitting. So, this is, this one's higher and this

one's lower down here. So, you can see is that we don't actually

have any collisions in this case. But the problem is that we have wasted

time slots, which is really just as bad as a collision.

because we're not getting anything from that time slot anyway.

It's a wasted opportunity, so this is really an x.

Meaning that it's not good and we have all of these as being successful as well.

So, there is a trade off here. Between making it higher, and then we

have more collisions but never any waste of time slots and making it lower which

means we have less collisions but some waste of time slots.

The questions is, what should it be? What should the probability of

transmitting be and what should we make and can we come up with a simple

solution, a simple mathematical solution?