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.
Data centers and Cloud Market Segments
Loading...
From the course by Princeton University
Networks: Friends, Money, and Bytes
59 ratings
From the lesson
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.
Meet the Instructors
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
Now how do we think about this capacity allocation problem here?
First of all, in the rest of this lecture, when we say a flow, we mean a
session, we mean the source. Because we equate a session with a
source. As each session traverse a single path.
That is already given to us. And a session has one source node and one
destination node. So this is a unicastic session over a
single path. We're going to use these three words
interchangeably, flow, session, outsource.
We're going to index each of them by say, I.
And routing is already fixed, so you cannot change what path will a session
take. Okay. You can only change the transmission rate
of the source of that session or flow, not the path that it takes.
Now the interaction between routing and congestion control which we briefly
mentioned last lecture, in network architecture, you can think about that,
and maybe in the homework problem you can encounter one of those.
But for the lecture, fixed routing, you only adjust the degree of freedom for
congestion control, namely, the source rates.
Now this capacity allocation problem. We first have to make sure that the
solution we propose is a feasible one. Meaning that, it can satisfy the link
capacity constraints on all the links in the network.
Otherwise the vector is infeasible. It might be great to have but you cannot
accommodate that. There might be a single bottleneck link
somewhere. And then, there will be likely
uncountable number of feasible allocation vectors.
The question then is which one you should pick as the optimal.
Optimal with respect to what? What you want, efficiency and you want
fairness in this allocation. You don't want to waste link capacity.
For example, assigning zero to all the sources as the rates met as a feasible
solution, but clearly is very inefficient.
You also want it to be fair. Let's take a look at an example.
Okay. Here is example with four links, kay, and four nodes in a graph and there
are three sessions. So, four links.
Right by one, two, three, four, and three sessions labeled by a, b, and c.
Session a traverses all three lengths in this tandem, okay?
So from source node to destination node. Section, session b goes from this source
to this destination, sharing one link with session a, and then go through
another link by itself. Session c also share one link, session a
in fact, that is the only link to session c goes through.
Okay. Now the question is.
If I have a unit capacity on each of these links then what should be the, the
allocation of the capacity? So first of all you need to be feasible.
Okay, for example I want to give all three sessions one megabit per second.
So I want to give the vector 111 to sessions A, B, and C.
Now that's not feasible. Right?
because then link one cannot accommodate two megabit per second.
It can only have the capacity of one megabit per second.
Same thing for link four. So, you have to pick a feasible solution.
And you start to think that, hey maybe links one and four are kind of the
bottleneck links, right? If they are saturated, then even if link
three has leftover capacity, I cannot add more rates to session a.
Because the bottleneck might be on links one and four, competing with the other
two sessions. So it is not just about the number of
links that you traverse. Its not like c goes to one link, b goes
to two link, a goes to three link and therefore you know, a should fewer rate
than b, b should get fewer rate than c is really about what kind of links are you
tra, traversing. If you're using a lot of bottlenecks
links then may be you should not receive too many rates, too much rates.
And in that sense, we can see that A uses two bottleneck links, one and four, B
uses one bottleneck link and C uses one bottleneck link.
So, maybe B and C even though B traverse one more link it should be treated in
similar ways because the additional link B traverses is really not a bottleneck
link. Okay?
In the configuration of equal one unit. One mega per second capacity for all four
links. Of course, if you change that
configuration, the, the implications can be different.
Then we want it to be efficient. Now, it is actually impossible to fully
utilize four megabits per second across all four links.
Okay, but you can try to use as much as possible.
For example, if I give session one, session A, one megabit per second and the
other two sessions zero. Okay.
That is a particular allocation. Right?
It actually would use three out of four megabits available in the network.
Hm, here's another way, for example I can give half, half, half negative per second
through the three sessions. That actually also uses three out of four
negative per second available in the network.
Right, because this link and this link will be fully utilized.
That's two megabit per second, this link got half, this link got half for sessions
A B respectively. So, if you look at these two vectors,
they are both efficient. Okay.
But clearly they look very different. In particular, this allocation actually
starves, sessions B and C, giving them zero rates.
So you probably think, this is unfair. Later, in lecture twelve, the last
lecture of the course, we'll devote a whole lecture to quantifying notions of
fairness. But you may remember alpha fairness,
okay? And this one looks more fair than that
one. But you may think, gee,
session A is actually taking up a huge amount of resources.
So why should we treat it equally as if this is same as sessions B and C, right?
It goes through two bottleneck lengths. Not one.
And indeed, if you go through the derivation of a proportionally fair.
You may remember if we do logarithmic utility maximization, we get proportional
fairness. Then the answer is that you could give
session A 1/3 of a unit, so 1/3 of a megabit per second.
And sessions B and C 2/3 Again the efficiency is that you are using four,
three out of four megabit per second in the network.
But allocation is. One unit of share for A.
Two units for B and C. And that confor, conforms to our
intuition that B and C should be treated about the same, because they use one
single bottleneck link. And A should not be the same because it
uses two. And indeed, you see a sense of
proportionality. If you use twice as many bottleneck links
you will be given, half of the capacity, as the other sessions.
And if you impose that condition you can quickly see that this 1/3 2/3 2/3 will be
the most efficient solution. So If we want feasible solution and then
strike a trade-off between efficiency in utilizing the link capacities, and the
fairness of allocating them among competing sessions.
So now the question is how do we formulate this problem in general.
Let's first look at the constraints of this optimization problem which is the
link capacity constraint. We have to find a representation of the
routing decisions which is again given to us already.
We don't get to change that. But we have to write it down because that
clearly changes the configuration of what session uses what path, what links.
There are a few different ways to do that is to say that, if you look at each
source. Okay.
Is that a source that uses link l? For each link l, you can write out a
subset of nodes which are the sources that use this link l.
Denote that set by S(l) and you can ask yourself is node i in that set.
Conversely you can say is link l being used by the source given the routing you
know for each source i there is a set of links a concatenation of which provides
the end to end path. Is this link l in that path?
Is it an element in the set l of i? There is yet another way to represent
this in a matrix. Think about a number R which is a binary
number 01 sub li. It is one if node i uses link l and 0
otherwise. So if link l out is all the path used by
source i then Rli is 1 otherwise it's 0. And soon you'll see an example
illustrating this using the same topology that you just saw.
So now I can write down the link capacity constraint by saying that multiply Rli Xi
which is my source rate as source i summing over all the I's.
What is this? Well, we can give it a symbol.
This is y sub l because we sub over all the i's fixing a particular l.
This is the load on link l. So the load on link l.
Okay? Or equivalent, we can write it as the
summation of all the Xi's but summing only over those Is in the set of sources
using link l. We can either represent it in this index
way, or represent it in this binary, matrix way.
And what we want is to say this load on link l should be no bigger than the
capacity on link l, denoted as C sub l. So each link indexed by L, got a fixed
known number capacity C. Now you see that the routing matrix
collectively called R and the link capacity vector, which we can put this
number into a vector C, are both given constants.
Our vec, our matrix, and C vector our constants.
We do not get to change the link capacities or the routing decisions.
We get to change the X vector. Hopefully distributively.
That is the source rates. Okay,
y is just a shorthand notation of a sum of certain X with respect to a particular
link, you know?'K? So we want a linear function of X called
y to be less than the capacity C. During the transient the,
this inequality will be valid as you try to search for the right loading, on the
link l. But at equilibrium you want this
inequality to be satisfied for all links l.
Okay. Now we can of course write this as
shorthand matrix notation R, matrix multiply X vector should be less than
equal to the C vector. So this is yet another way, a shorthand
notation to represent this link capacity constraint.
Of course this inequality is comparing two vectors, the Y vector and the C
vector. This inequality here means component
wise. the first component's less than the first
component, the second component's less than the second component, and so on.
Okay? Now what about the objective function?
Well the objective function here as we just mentioned can be alpha fair utility
function. They capture both efficiency and a notion
of fairness. Promethized by this alpha.
So again, reminding ourselves from lecture eleven that the utility function
is a function of the convex right at the source promethized by alpha equals x to
the power of 1 minus alpha over 1 minus alpha, if alpha is not equal to 1.
If it is equal to 1 then, in the limit, this becomes log of x Okay.
So different sources I may have different alpha.
So you can say, this source have 1 alpha. Another source has a different shape.
Or we can say they all share the same Alpha.
In which case we are just maximizing the summation of U times, a U(Xi) subs, alpha
sharing the same shape, summing over all of these sources i.
And this will be the objective function: maximize the sum U(Xi).
Subject to the constraint of RX less than equal to C and therefore we have our
formulation of Network Utility Maximization, N U M the NUM formulation.
Maximize summation U(Xi) summing over i such that RX is less than or equal to C
where the variables is the X vector, collecting all the source transmission
rates Xi for a given constant. The routing matrix given, and the
capacity given. And say the shape of the utility function
Alpha, given. If you look at this optimization problem,
see that it is linearly constrained and objective function assuming smooth
increasing and concave functions of the utility function which is the case Alpha
fear utility function, this is a concave maximization which as you may recall from
lecture four. is equivalent to minimizing a convex
function. Same as minimizing minus the sum of
utilities. Okay.
So instead of maximizing this you are talking about minimizing this.
Subject to linear constrains. And this is a nice problem.
It is a convex optimization. Because you are minimizing convex
function or equivalently maximizing concave functions.
Subject to convex constrains that which turns out to be a set of linear
constrains in equalities. So it is a nice optimization.
Even though we did not spend time talking about the exact algorithms that will
belong to an operations research course. but you can believe me that they are very
efficient centralized algorithm to solve it.
Now better still, and as needed in this case, we need more than just efficient
centralized computation. We need distributed algorithm to solve
this efficiently. And.
That indeed turns out to be the case because this problem is so called
decomposable. Clearly the objective functions is a sum
of different sources utility and therefore it is already decomposed the
problem, the trouble resides in this coupling constraint, Okay?
Each links shared by many sessions and each session traverses through many links
just like what we saw already in this example.
Okay. So we cannot ignore those coupling
represented by this RX less than equal to C.
But fortunately we can do what we call dual decomposition.
Is called dual decomposition because it's actually solving the so called La Grange
dual problem. Give me an optimization problem, I can
always derive, so called dual problem. And there are many strong, nice
properties between the primal and the dual problem.
Okay, one of which allows us to look for cracks in the original problem and solve
it through solving the dual problem. And you get a distributed solution.
This is a very interesting topic. And it's quite a, a powerful mathematical
tool in designing networks of various kinds.
But we will have to defer this to advanced material part of the lecture.
Okay. So suffice it to say at this point that, indeed this is a convex and
decompose for problem and we'll now present the distributed algorithm.
If you want to see the derivation, please wait until the advanced material part.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
