0:20

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? Cuz 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 differe nt. 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,

Â cuz 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 one-third

Â of a unit, so one-third of a megabit per second. And sessions B and C two-thirds

Â 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 cuz 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

Â one-third two-thirds, two-thirds 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.

Â 8:37

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 cuz 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 zero otherwise. So if

Â link l out is all the path used by source i then Rli is one otherwise it's zero.

Â 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 loa d

Â 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.

Â 12:53

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 one

Â minus alpha over one minus a lpha, if alpha is not equal to one.

Â If it is equal to one 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 one 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.

Â