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.