0:44

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.

Â 6:09

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.

Â 9:15

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.

Â 12:37

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.

Â 17:03

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.

Â