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.