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.
ALOHA Inscalability
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 just taken again the equation that we just found for the per-station
throughput. We said that a per-station throughput was
going to be the probability of transmitting times 1 minus the
probability of transmitting. And then we would do that multupliatin.
However, many stations we had minus 1, because the one that's transmitting we
don't have to include in this. So this is numstat minus 1 times.
So we see that This throughput is dependent on two things.
The first is the probability of transmitting, which we expected, and then
the seconds also the number of stations, okay, and so we don't really have control
over the number of stations that are under our access point because they will
come and go especially if it's a free access point, that's one of the
advantages of having a locked... [INAUDIBLE] besides the fact that people
can't steal your WiFi, then you don't have people actually disrupting your data
rate, as well, but what we can control is this probability of transmitting.
So, let's see what happens, and let's see if we can figure out what the throughput
will be as we change The probability of transmitting.
So in this graph right here, we're showing, for example five stations.
So we're saying that Numstat is equal to five in that equation.
So this really gets, this multiplication happens four times.
And then we're seeing what happens when we change the probability of a station
actually transmitting. And so, we can look at either the total
or the per-station throughput here it doesn't really make much of a difference
because it's just a multiplication factor as we said.
We just, to get the total throughput we just multiply this again by the number of
stations we have and that's how we translate from, from this graph up to the
top. And the higher one, total throughput will
always be greater than the per-station throughput.
Obviously, because we're just considering more stations.
But you see this trend here that first it's going to increase.
Right? And then it's going to hit some maximum
value before then it starts to taper off and decrease.
And this fits our intuition that we don't want it to be zero, because then the
throughput will be zero, and we also don't want it to be one because then
we'll always have collisions, because that's 100% transmission.
It's somewhere in between but it's skewed now towards the lower side.
And that maximum we hit we can see right here graphically, is when the probability
of transmission is at 20%. So we can say the best ProbTrans is 20%,
so then we might say from this graph, well okay then let's set probability of
transmission to be 20%. So then one in every five frames, on
average, every station will transmit. Notice how there are five stations.
So the next question is, well, are we done?
Are we satisfied with this 20% probability of transmission.
Clearly we can't do any better if we have five stations.
We see here it's, we're getting our maximum.
We don't have anything else to play with. There's no other knobs that we can turn
or anything to change any other parameters.
And, so, but it turns out that as we change the number of stations we're
going to see a little bit of a different story.
Okay? So, that what we just saw was for NumStat
which we're showing here equal to five. And now, this is a graph That's showing
what happens as NumStat varies. So it's just a bunch of superimposed
plots. The first one in the blue over here, this
straight line is for NumStat equal to one and that should make sense that if we had
one station, we would always want that station to transmit.
Because then we get 100% throughput, because we never have to worry about
interfering, so if you're the only station, go ahead.
You can get your maximum possible throughput and your really impressive
data rate, but once we have even two stations, that's when these things start
to taper off. Right, and that's when the throughput
starts to decrease. So if you notice a few trends about this
graph. The first thing is that the maximum that
we can achieve goes down. And it goes down pretty quickly as the
number of stations increases. So we have one station we can get 100%.
Two stations, the maximum we could get was 0.5.
Three stations, the maximum we can get is up over here and then with five stations,
it's down here. With ten stations, it's down here.
And so, as you can see, [INAUDIBLE] as soon as we add a second station in, we
already have had their total throughput that we can get.
So, and that's not even saying that pre-station throughput is half, that each
one gets half. It's the total throughput.
So when you add the two throughputs up, they're less than what one station can
get if the one station was there just by itself.
So that's a pretty unfortunate situation, clearly.
The second thing that you'll notice is the probability of transmitting.
The ideal, the optimal probability of transmitting, or the best one that we can
select goes down as the number of stations goes up.
Which should make sense because it's kind of along the lines that you have to wait
more. As there's more stations there because
there's more of a chance that someone else Has something to send.
Or someone else is going to send in that time slot.
So, prob-trans here, for two stations, the ideal is 50%.
So, half, and half, which should make sense.
For three stations it's 0.333. It's actually one third.
This is one half. For five station its actually 1 5th and
for 10 stations its 1 10th. You should know there is the trend there
and indeed that trend is the case that the [UNKNOWN] probability of transmitting
is simply going to be equal to one over the number of station [SOUND] For this
version of Aloha that we're looking at. So, if you could find the total number of
stations and you took one over that, and every device was following that, that
would be giving you the maximum total throughput that you could possibly get.
But the key idea again is that the best probability of transmitting is going to
depend upon the number of stations. So we can't just set it at 20%, or 50%,
or anything. We have to know the total number of
stations in order to get the best total throughput.
So in this graph right here I'm plotting a maximum total throughput So I am
basically taking this graph and I am just plotting these values here and seeing
what happens as the change number of stations, this is for one station, this
is for two, this is for three stations, this is for This is for five, this is for
ten. So, this is what happens as the number of
stations change. So, we start at one station we saw before
it drops down to 50%. This is just showing there's a simpler
form then we dropping it down again and again and it turns out that the, the
maximum or the sorry, the minimum that we can get as we increase the number of
stations to infinity we're going to approach Some limit here, that it won't
drop below. And at least that's something good, I
suppose, in that we do hit some limit, so it doesn't go down to zero.
And that nobody's ever going to get through.
And that limit is about about 37%. [SOUND] So it's going to go down, and
keep going down and crawl around 37%. But this is again, this is maximum total
throughput. So, the per-station throughput, you have
to take this and divide this by the number of stations.
So, as the number of stations goes to infinite, this would go down to zero for
the per-station throughput. So, the total throughput, the limit and
the lowest I can go is 37%. [SOUND] But for the per-station [SOUND]
that would go all the way down theoretically to 0%.
I mean, you'll never actually hit 0% because obviously someone has to be
getting something in order for to be a total of 37%, but in the [UNKNOWN] you're
going to be getting such a small amount of throughput.
And that's really not a very desirable scenario to be in.
