What makes WiFi faster at home than at a coffee shop? How does Google order its search results from the trillions of webpages on the Internet? Why does Verizon charge $15 for every GB of data we use? Is it really true that we are connected in six social steps or less? These are just a few of the many intriguing questions we can ask about the social and technical networks that form integral parts of our daily lives. This course is about exploring the answers, using a language that anyone can understand. We will focus on fundamental principles like “sharing is hard”, “crowds are wise”, and “network of networks” that have guided the design and sustainability of today’s networks, and summarize the theories behind everything from the social connections we make on platforms like Facebook to the technology upon which these websites run. Unlike other networking courses, the mathematics included here are no more complicated than adding and multiplying numbers. While mathematical details are necessary to fully specify the algorithms and systems we investigate, they are not required to understand the main ideas. We use illustrations, analogies, and anecdotes about networks as pedagogical tools in lieu of detailed equations. Please note that per Princeton University policy, no certificates, credentials or reports are awarded in connection with this course.
CSMA Backoff
Loading...
来自 Princeton University 的课程
Networks Illustrated: Principles without Calculus
39 个评分
从本节课中
Random Access in Wifi Networks
In this lesson, we will investigate WiFi, another type of wireless network. Rather than having stringent power control algorithms as we saw for cellular, WiFi relies on "random access" methods to manage interference among users in the same location.
与讲师见面
Christopher BrintonLecturer
Electrical Engineering
Mung ChiangProfessor
Electrical Engineering
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.
