You pick up your iPhone while waiting in line at a coffee shop. You google a not-so-famous actor, get linked to a Wikipedia entry listing his recent movies and popular YouTube clips of several of them. You check out user reviews on Amazon and pick one, download that movie on BitTorrent or stream that in Netflix. But suddenly the WiFi logo on your phone is gone and you're on 3G. Video quality starts to degrade, but you don't know if it's the server getting crowded or the Internet is congested somewhere. In any case, it costs you $10 per Gigabyte, and you decide to stop watching the movie, and instead multitask between sending tweets and calling your friend on Skype, while songs stream from iCloud to your phone. You're happy with the call quality, but get a little irritated when you see there're no new followers on Twitter. You may wonder how they all kind of work, and why sometimes they don't. Take a look at the list of 20 questions below. Each question is selected not just for its relevance to our daily lives, but also for the core concepts in the field of networking illustrated by its answers. This course is about formulating and answering these 20 questions. All the features of this course are available for free. It does not offer a certificate upon completion.
Pros and Cons of Cloud
Loading...
來自 Princeton University 的課程
Networks: Friends, Money, and Bytes
62 個評分
從本節課中
What's Inside the Cloud?
The Cloud is another rapidly growing Internet service, allowing users to rent storage and computation resources inside the network. In this lecture, we will see how the large data centers operated by Cloud providers can be constructed from a multitude of small switches.
與講師見面
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
What is that distributed algorithm? First list captured two shorthand
notation, okay? One is, if you sum up those sources,
whose rights from those sources that belong to the set of sources used in link
arrow, we call this y sub L. The load on link L is just shorthand
notation of summing the rates from the right sources.
Okay? We can also give a mirror image of, what happens on a link. Okay?
On a link, we're going to see that there is a pricing signal.
The physical manifestation, turns out, can be packet loss or packet delay,
and the mathematical interpretation is v, Lagrange dual variables.
So this is the physical manifestation, this is the mathematical representation.
Okay? And on each link there is such a pricing signal P that going to be fed
back from the network to the sources to enable the negative feedback loop.
And we're going to sum up all those from the links, that's along the path used by
source I. Keep writing S of source I as given by
routing. Okay?
So by summing up all these PL with respect to the path of a particular
source I, we get a number called a QI, because we're talking about a particular
source I. This is the path,
the price, because it's a sum of the prices.
Again, it's an interpretation, as mentioned at the beginning of the
lecture, along the path used by source I.
And this Y arrow is the short hand notation for link load, okay?
It is the sum of the load from the sources that's using this link,
because routing is fixed and given, we don't get to change the summation index.
Okay. But we get to change X and will be
varying P in a dynamic way. So, just remember short hand notation, Y
sub I, link load q sub I path price. Skipping the very interesting derivation,
here is what end up where we end up with. In each source I, will autonomously,
okay, run the following update iteratively from discrete-time slot T to
T + 1. Okay? You're going to update your right.
Okay? X at time T, basically as the demand
function. Okay? Where the price is the path price,
at this time T and the path price, time T, will be the update from the path right
price from the last iteration T - 1, that will be down here in a minute.
Okay? So this says that if you have source I,
just look at your total path price, and that is the price that you pay,
and put it into your demand function, that should be your source rate.
Now, what is demand function again? You may remember it is the utility
function's first derivative inverse. Why is that?
Because, numeric function is derived by looking at the net utility maximization.
Look at my utility minus the price I have to pay, which is the path price,
for the path I'm traversing times the volume which is X, you maximize this over
X. Then you will see that X as a function of
price is, is U prime inverse. Okay?
And that is the demand function, exactly as what we saw back in lecture
11. So this is done, at each time slot T, at
each source I, and each link L will also autonomously
execute a following computation. You will update the link price at time T
from the link price in the last iteration T - 1 by updating it with the following
summation. You look at the y out, at time T now.
The link load at this point and the supply,
this is the demand, this is supply.
Supply's fixed, since we assume fixed capacitors on each
link out. Demand is dynamically changing based on
the price that you have been generating and the difference is the difference
between demand and supply on your link. And this is the direction of change.
Does it make sense? yes it does.
If the demand is bigger than the supply during this step of the transient, then
you are going to increase your price next time.
When this P is increased then all those Qs okay, for those sources we use this
link arrow, we'll see a bigger Q, as Q becomes bigger.
U prime inverse of the demand function is a decreasing function that will make the
source rate lower. Exactly what happens in many market
places in an iterated way, when demand exceeds supply and say rank up the price.
The price is cranked up, then, the demand will drop.
So, in the next iteration, those links, sources using link l would
see a smaller x, and therefore their total sum, y, the
link load, will be smaller. That's moving in the right direction.
When y is bigger than c, this iteration, next iteration, will be smaller.
Conversely, if the current demand is actually less than the capacity, then
while you're not fully utilizing this link's capacity, so you can see a smaller
p. And that will reflect in a smaller q
which will reflect into a bigger X and then reflect in a bigger Y.
Next iteration demand will go up. So it's a very smart and intuitive
arrangement. So this direction is correct.
We just need two more modifications. Number one is while the direction is
right. We need a little thing called a step
size, you know to buy beta here. Beta is some positive constant.
It's called step size because it says, even you've got the right direction, you
don't want to overshoot, okay? For those of you who have played golf,
not me, but played golf on Wii, which is very difficult, you know that when you
get close enough to here's your ball. Okay, here's the hole,
to the hole. If you, even if you get the right
direction, and you give too big of a kick.
Okay? The force is too big.
You'll overshoot and land over there. Then you say, alright.
The right direction's this way. Right direction, but you overshoot again.
And this may oscillate back and forth, unless you start to kick with smaller
forces, as you get closer and closer to the hole.
So that force to used hit the golf ball is the step size.
You don't want to oscillate and overshoot back and forth, so you want to use a
smart step size rule. One rule says that if the step size is a
constant, independent of iteration T, and very small then when it's sufficiently
small then you can guarantee convergence, meaning you will get it into the hole.
Another rule says if I make B smaller and smaller.
As I move along the time axis.'Kay? As I, as I get closer and closer to the
hole, I start to be more and more careful.
That can also guarantee convergence. So the selection of the step-size in a
distributed uncentralized way is both a science and an art, we just don't have
time to talk too much about it. A little bit more in advanced material
but for our problem, there are simple and, good choices of beta.
Simple in the sense it's easy to come up with it.
And good in the sense it will guarantee convergence.
The second modification we need is that these prices, okay, cannot be negative.
So you can just say if it becomes negative we'll just take it as zero.
We usually use the symbol of big bracket sup plus to denote the fact that if
whatever's in the big bracket dips below zero we just take the zero as the floor.
Alright. Now, this is our algorithm.
Okay? At each source I, you just look at your
current path price into your demand function, driven by your own utility
function. And at each link L, there is this price
update. And as T goes on through the iterations,
you actually guaranteed, as long as the step size is smart enough, to converge
and converge to what? To an optimizer of this convex
decomposable optimization problem, called the basic network utility maximization.
But the proof of that is in the man's material.
Here we just want to look at this and make sure we can intuitively understand
why it makes sense. Number one is that we know the direction
is right, bigger demand will lead to smaller demand next times.
Smaller demand now lead to a bigger demand next time with respect to given a
fixed length capacity. Number two, is it distributed?
Well, it is actually very distributed. Now the source rate updates are very
distributed. All you need to know is as a source eye
your own path price QI. Not only you don't need to know the other
sources, so you are you know, source one, you
don't need to know Q2, Q3 and so on. In fact you don't even need to know the
individual link prices along the links used by yourself.
You only need to know the end-to-end. Half price,
the link price update computation is also distributed.
You only need to know the load on yourself.
So you're link one, why one?
You do not need to know why two, why three, what happens on the other links.
And you don't even need to know the ingredients in your Y1.
You don't need to know the individual source rates, you just need to know the
total link load. The sum of the source rates among the
sources using. So this is a very distributed action.
As long as the sources can get these path prize with some message passing.
Okay. Either explicit or implicit.
As we'll see in a minute, actually in the next module I guess.
where we'll see that it can be done in the implicit message passing to get these
path prices interpretable as the end to end loss rate or queuing delay.
Number three. There is a very nice economic
interpretation. Just like back in lecture eleven when we
used the pricing to coordinate demand and supply.
Back in lecture two when we used pricing to coordinate demand and supply in
auctions. Okay,
now we're using pricing, at least as interpretation of this machine protocol
called TCP Congestion Control. Prices, again, coordinate demand and
supply in a very fast time scale around round trip time, time scale.
And in this case distributively over a network.
We're looking at a more complicated version than the simpler ones, before.
Now we have to run it over a network, and the good news is that it can be done
distributively. Now this can be summarized in a feedback
loop. This is the negative feedback loop that
we we're looking for about one hour ago, in the beginning of this lecture.
Okay? Each source labelled by one, two, three,
I denote, draw this, this way because I want to highlight the fact that their
actions will be autonomous as distributed.
Actions we'll decide in XI, this induces a vector X into the network.
Okay? You can represent as this routing matrix
R. Then each link only sees the link load
Ys, again, autonomous action. Distribute it across the links.
And then they will update these prizes P.L.
Independent of each other through the network, and the sources will only see
the corresponding path prize's, QIs. Okay.
X goes up, P will go up. Q will go up, then X will go down.
Now Y will go down. And with a sufficiently smart step-size
beta, this is guaranteed to converge. Now, will they converge using existing
TCP protocols? We'll come back to that towards the end
of the lecture. Well first let's look at a small numeric
example using the same topology that we saw.
