So, as we said, when acknowledgements aren't received, we assume that

collisions occurred, because it's likely that they did, and we have to

re-transmit. So, the way that we deal with it is by

having the stations back off to a later time.

When they back off, they don't want to back off to the exact same point because

you collide with someone, and then you both wait five seconds, and then you

transmit again, then you're going to call out again.

So, they randomize the next transmission and they choose some random time in which

to retransmit in the hope that they're not going to chose the same exact time.

Now, if you have a larger window on which that randomization is chosen, then

clearly there's going to be less of a chance that you chose the same time.

So let's look at a little example here. Take two stations again, A and B.

Which both send data. Then they see that they don't have an

acknowledgement. Okay, then what happens is, once they

don't have an acknowledgement they decide, well, we have to re-transmit.

So they both go through the wait and listen period again.

Which they have to do before they start this back-off period they go through that

wait and listen. Okay, then the backoff starts.

And then they choose a random number between right now and and the current

contention window size. And the contention window gets larger as

we have more interference as we will see in a minute.

But right now, the contention window size is 15.

So they choose at random number between zero and 15 and the contention window

size changes based from what station it is but, so, and again, between zero and

15. And in this case now, A chooses 13,

'okay? So he decides to wait.

13 time slots before we transmit, okay so then here we transmit time slot 13 and B

decides to pick 3 time slots between 0 and 15 and so you can think of this again

as if you have a, a spinning wheel and the wheel that you are spinning now has

15 different sections. So say we cut this up, if that was

possible, into 15 different pieces. And then you're basically going to spin

it and then whichever one you land on you number them 1, 2, 3, 4, and so on.

And then you just choose that random one. And that's what these devices do

internally. And, so this one's choosing three, and

this one's choosing 13. Now, granted that b doesn't take more

than three or more than 10 time slots that transmit, there would be a collision

between these two stations again. Of course, it's possible that they

collide with other stations like CDE, which may also be sharing the same access

point, but still every station goes through the same procedure.

And again, the randomization helps to avoid collision with the same station

again. So you don't want to, you know, keep

colliding with one another. But then, when collisions persist, and

you keep having more and more collisions, then you infer that there's a lot of

congestion happening right now in the network.

And then we have to deal with that. So, the way that we deal with that

congestion is by backing off more and more.

That's by changing that contention window size.

So the possible random numbers of time slots that we're going to choose.

What CSMA mandates is that the exponential backoff be Multiplicative.

Meaning by, and in this case, multiplicative could be by any factor but

by factors of 2. And factor of 2 means that it's binary

exponential backoff. So we could have multiplicative backoff

in general, which would be multiplicative exponential backoff would mean that we're

multiplying by any number. Like it could be 3 or 4.

Or whatever you want, but the, the standard is to do it with binary because

everything computers, logics likes do to a things in terms of [UNKNOWN],

multiplying and increasing by factors of 2 each time.

Doubling, that's just a standard. So, then first you would.

Go by two, then four, then eight, then sixteen times the original and so on.

And just increasing. Keep multiplying it by a factor of two.

And keep doubling the current window size.

So, you're probably wondering why do we do it with multiplicative backoff.

And the reason is really just that from looking at networks and seeing what

works, people thought that linerar backoff, like if we just increased by two

and then we increased by one more, then one more, then one more, so.

From 2 to then to 3 to 4 to 5. They thought that, that really it just

wasn't aggressive enough. So, it's, it's not aggressive enough.

So then when we see congestion we want to back off as soon as possible and say

woah, woah, woah, woah, what's going on here.

Let's try to alleviate this congestion from the network.

So, rather than increasing starting 2, then going to 3, 4, 5, we start at 2,

then go to 4, then 8, then 16. And so on, and so here's an example.

So suppose this is the previous frame, right, and after your initial attempt you

go through a wait and listen period because you had a collision, right, and

you randomly pick one and the current window size is seven right now, okay?

So, you pick a random number between zero and seven, right?

So suppose then you choose three. Then if you have a collision again, then

you do a retry, so then now you're going to just retry.

And then once you have the collision, your window size goes up to 15, okay?

And now you're probably saying well, 15 isn't a factor of two, seven isn't a

factor of two. So the window size is eight, or two to

the three, which is just 2 times 2, times 2.

Which is equal to eight, and then we subtract one just simply because we want

to include zero. So rather than going from 1 to 8, we go

from 0 to 7. It's just the way we count, because zero

with indicate that right after the wait and listen period they're going to

immediately start transmitting, which is also a possibility, right?

So then, in this case we start, we have a window size then of 16 and then we

subtract 1 to get 15. And this case then 16 times 2 is 32.

So we have 32 minus 1 which is equal of 31.

And then we go from 0 to 31 here. And this is from 0 to 15 and so on.

And the next time if there was a collision again, we would go to 64.

It's 32 times 2 is 64 minus 1 is 63. So we would choose a random number

between 0 and 63, and that would determine when we would transmit, again,

next. So again, we subtract 1 from the window

size. So it's the size minus 1 is where we go

up to. And we choose a random number between

that size minus 1. So in this first retry, then Say we

randomly pick one, it's 10. Then we have another collision for some

reason, then we randomly pick one and we get 7.

And then so on and so forth until we finally get our data through.

So we can draw an analogy here to conversation again.

And it's again, we just keep doing analogies because they just make sense

and they can allow us to relate to these. And so, in a, in a typical conversation

with someone, now if you and someone else speak at the same time then you might

wait a second and then you each try to speak again and then you interfere again.

You've probably had that before where then you're just exchanging a bunch of a

bunch of sounds of your voices and they're not really getting anywhere

because each of you doesn't want to keep interfering, but then eventually you

might wait a longer and longer time like, [NOISE] and then eventually someone will

say. Alright, well I'm just going to start

talking right now, and then there won't be any more interference between the two

of you, because they could get their words out and then you would wait until

they were done.

CSMA Backoff

Networks Illustrated: Principles without Calculus

Meet the Instructors