So this is the physical manifestation, this is the mathematical representation.
Okay? And on each link there is such a pricing signal P that going to be fed
back from the network to the sources to enable the negative feedback loop.
And we're going to sum up all those from the links, that's along the path used by
source I. Keep writing S of source I as given by
routing. Okay?
So by summing up all these PL with respect to the path of a particular
source I, we get a number called a QI, because we're talking about a particular
source I. This is the path,
the price, because it's a sum of the prices.
Again, it's an interpretation, as mentioned at the beginning of the
lecture, along the path used by source I.
And this Y arrow is the short hand notation for link load, okay?
It is the sum of the load from the sources that's using this link,
because routing is fixed and given, we don't get to change the summation index.
Okay. But we get to change X and will be
varying P in a dynamic way. So, just remember short hand notation, Y
sub I, link load q sub I path price. Skipping the very interesting derivation,
here is what end up where we end up with. In each source I, will autonomously,
okay, run the following update iteratively from discrete-time slot T to
T + 1. Okay? You're going to update your right.
Okay? X at time T, basically as the demand
function. Okay? Where the price is the path price,
at this time T and the path price, time T, will be the update from the path right
price from the last iteration T - 1, that will be down here in a minute.
Okay? So this says that if you have source I,
just look at your total path price, and that is the price that you pay,
and put it into your demand function, that should be your source rate.
Now, what is demand function again? You may remember it is the utility
function's first derivative inverse. Why is that?
Because, numeric function is derived by looking at the net utility maximization.
Look at my utility minus the price I have to pay, which is the path price,
for the path I'm traversing times the volume which is X, you maximize this over
X. Then you will see that X as a function of
price is, is U prime inverse. Okay?
And that is the demand function, exactly as what we saw back in lecture
11. So this is done, at each time slot T, at
each source I, and each link L will also autonomously
execute a following computation. You will update the link price at time T
from the link price in the last iteration T - 1 by updating it with the following
summation. You look at the y out, at time T now.
The link load at this point and the supply,
this is the demand, this is supply.
Supply's fixed, since we assume fixed capacitors on each
link out. Demand is dynamically changing based on
the price that you have been generating and the difference is the difference
between demand and supply on your link. And this is the direction of change.
Does it make sense? yes it does.
If the demand is bigger than the supply during this step of the transient, then
you are going to increase your price next time.
When this P is increased then all those Qs okay, for those sources we use this
link arrow, we'll see a bigger Q, as Q becomes bigger.
U prime inverse of the demand function is a decreasing function that will make the
source rate lower. Exactly what happens in many market
places in an iterated way, when demand exceeds supply and say rank up the price.
The price is cranked up, then, the demand will drop.
So, in the next iteration, those links, sources using link l would
see a smaller x, and therefore their total sum, y, the
link load, will be smaller. That's moving in the right direction.
When y is bigger than c, this iteration, next iteration, will be smaller.
Conversely, if the current demand is actually less than the capacity, then
while you're not fully utilizing this link's capacity, so you can see a smaller
p. And that will reflect in a smaller q
which will reflect into a bigger X and then reflect in a bigger Y.
Next iteration demand will go up. So it's a very smart and intuitive
arrangement. So this direction is correct.
We just need two more modifications. Number one is while the direction is
right. We need a little thing called a step
size, you know to buy beta here. Beta is some positive constant.
It's called step size because it says, even you've got the right direction, you
don't want to overshoot, okay? For those of you who have played golf,
not me, but played golf on Wii, which is very difficult, you know that when you
get close enough to here's your ball. Okay, here's the hole,
to the hole. If you, even if you get the right
direction, and you give too big of a kick.
Okay? The force is too big.
You'll overshoot and land over there. Then you say, alright.
The right direction's this way. Right direction, but you overshoot again.
And this may oscillate back and forth, unless you start to kick with smaller
forces, as you get closer and closer to the hole.
So that force to used hit the golf ball is the step size.