RE: [RPRWG] Some questions about the pseudo-code in Gandalf
Donghui,
Thanks for the further clarification. More discussion is inline
below.
-Anoop
> -----Original Message-----
> From: Donghui Xie [mailto:dxie@xxxxxxxxx]
> Sent: Thursday, January 03, 2002 10:46 AM
> To: Anoop Ghanwani
> Cc: stds-802-17@xxxxxxxx
> Subject: RE: [RPRWG] Some questions about the pseudo-code in Gandalf
>
>
> Anoop,
>
> Was I still excited about the fireworks on New Year's Eve ?:)
> I guess so.
> Anyway, let the discussion go to your comments directly.
>
> Donghui
>
>
>
> > > > > > > - What's the rationale for:
> > > > > > > if (recd_rate != NULL_RCVD_INFO) &&
> > > > > > > (lp_forward_rate > (allow_rate_congestion/WEIGHT))
> > > > > > > in order to determine whether to send a rev_rate?
> > > > >
> > > > > This is a part of the fairness algorithm to ensure fair rate
> > > > > transmission
> > > > > on the ring. If some downstream node is congested and
> > > > > upstream nodes are
> > > > > sending more traffic than the fair rate of the current node
> > > > > (in a weighted
> > > > > fashion), current node will pass its received fair rate
> > > > > further upstream.
> > > > > This fairness logic applies when current node is not
> congested.
> > > >
> > > >The reason I brought this up is because only the local node's
> > > >weight is being used to determine whether or not to send the
> > > >message upstream. A better design, IMHO, would account for
> > > >the weights of the other nodes as well.
> > >
> > > I see much more advantage in using local weight only, which
> > > simplifies
> > > weight calculation requirements while providing elegant
> > > weighted fairness
> > > at the same time eliminates the need for global weights
> > > information and its
> > > associated much more complex calculations. That said, in
> recognizing
> > > Alladin's needs for global weights, next Gandalf version may
> > > optionally
> > > allow people use global weights in their preferred hard way.
> > >
> >
> >Indeed using the local weight is simpler and requires less
> >information. But it does end up being an approximation
> >that works best only when all weights are equal.
>
> Long time ago, I did some simulations on the accuracy of
> weighted bandwidth
> allocation with weight granularity up to two digits after the
> dot. The
> results were surprisingly accurate. For simplicity and
> computing speed, we
> find that integer valued weights are just doing the same job without
> sacrificing much accuracy at all.
> Having said that, if you have simulation results showing the
> approximation
> effects with unequal weights, it would be certainly
> interesting, especially
> if they amount to void the trade-off.
I don't think the global knowledge of the weights (or lack
thereof) will impact the accuracy of simulations or steady-state
behavior in any way. I think it would affect transient behavior
at times when traffic pattern is changing, and especially so when
the change is drastic. As long as things remain steady for
a long enough period after the transient, the algorithm will
converge. But during the transient, lack of knowledge of the
global weights could cause a sender to overshoot its fair
rate by significant amount. For example, assume at 10 Gbps
ring. Let my weight be 15, let the downstream node's weight
be 1. I'm currently tranmitting at 9 G, and downstream at
1 G. I suddenly ramp up and try to transmit as fast as
possible. The downstream gets congested and sends a
a fair rate corresponding to 1 Gbps. I will basically allow
up to 15 Gbps of traffic overloading the downstream node
significantly before the downstream node shuts me off
to a smaller value. Actually, because the ring itself
is 10G, that is the value I would be limited to bursting.
But as you can see, the first fairness message had little
effect.
(The desirable outcome of this scenario would be the
downstream gets 10/16, and I get 150/16 G.
We'll eventually get there, but the temporary overload
could have been controlled if we had global knowledge of
the weights.)
Again, I'm still in the midst of understanding this stuff
so please let me know if my analysis is off.
>
> > >
> > > > >
> > > > > > >
> > > > > > > - The pseudo-code does not appear to account for virtual
> > > > > > > output queueing support within the MAC client.
> > > > >
> > > > > The pseudo-code presents the basic fairness algorithm
> with single
> > > > > choke-point information. A VoQ capable MAC client would run
> > > > > multiple copies
> > > > > of the basic fairness algorithm, and keep track of all the
> > > > > choke-points
> > > > > information with each running copy corresponding to one
> > > > > virtual destination
> > > > > queue. For details, please see section 6.7 for
> descriptions on the
> > > > > relationship of the basic fairness algorithm and VoQ capable
> > > > > MAC client.
> > > >
> > > >Section 6.7 does indeed explain the multi-choke point case.
> > > >In the absence of multi-choke point capability, the algorithm
> > > >can be shown to be shown to have severe limitations.
> > > >Therefore, I think it makes sense to have the pseudo-code
> > > >cover the multi-choke point case as well, even if it
> > > >just involves adding a loop. Leaving it as an exercise for
> > > >the interested reader can hide complexity that it
> > > >introduces. I would like to see how it affects data
> > > >traffic making its way from the MAC client to the MAC.
> > >
> > > Claim of "severe limitations" and the "absence of
> multi-choke point
> > > capability" are not substantiated. So no points are given on
> > > that. "hide
> > > complexity" seems to contradict "Section 6.7 does indeed
> explain the
> > > multi-choke point case."
> > > 802.17 MAC should be able to provide all the traffic
> > > information to MAC
> > > client, which may choose to utilize the info and make
> > > intelligent packet
> > > transmission so as to optimize ring utilization. Gandalf bandwidth
> > > management enables all the means for a highly sophisticated
> > > MAC client to
> > > transmit packets onto the ring while optimizing ring bandwidth
> > > utilization. If you like to see how MAC client
> > > implementations affect data
> > > traffic "making its way from the MAC client to the MAC", you
> > > are welcome to
> > > exercise the various MAC client implementations.
> >
> >Maybe "severe limitations" was too hard. I'm sorry. But
> >I think you have to agree that there were some limitations
> >that made the introduction of "multi-choke" necessary.
> >Again, as I stated earlier, even if it is just a for loop
> >that needs to be added, it would be nice to see it as
> >part of the pseudo-code. If all of the enhancements
> >don't make their way to the pseudo-code, then the
> >pseudo-code is not complete. The draft represents a
> >work in progress, so what does it cost to add it to
> >a later version?
>
> I agree with the necessity for supporting multi-choke, but I
> do not agree
> with your statement that "In the absence of multi-choke point
> capability,
> the algorithm ... have severe limitations.". The fact is that Gandalf
> algorithm enables and provides all the means for people to do
> multi-choke,
> to this end, the pseudo-code is indeed complete. As you can
> see, I simply
> don't think RPR MAC should enforce MAC client to do
> multi-choke, that is
> why there is not "a for loop" in the pseudo-code. As you may
> have implied,
> for a MAC client who likes multi-choke points, it may add "a
> for loop" to
> it. But for the algorithm, it is simply not a right thing to do.
I don't quite get this. There is a multi-choke feature, but
we don't want to use it because it brings no benefit.(?)
Why was the feature introduced?
>
> >The decision by the MAC of whether or not to accept
> >a packet from the client needs to reflect the logic
> >needed for VDQ; there have to be checks in there
> >so that the MAC can selectively deny access depending
> >on which choke point will be affecting the packet.
> >Certainly, one can figure out a way to make this
> >work, but since it's an integral part of the MAC,
> >I think it would make sense to specify that behavior.
>
> I believe Gandalf MAC provided all the logics needed for a
> VDQ client to
> behave properly. I don't see anyone needs to figure a way out
> for that. To
> intelligently utilize multi-choke information is the job for
> VDQ capable
> MAC client. For a simple MAC client without VDQ intelligence, the
> multi-choke logics provided by MAC are simply not used.
> Again, I am not
> convinced that MAC should specify the behavior of MAC client.
You're correct that we don't need to specify the behavior
of the MAC client. However, we do need to specify the
behavior of the MAC in response to a request for data
tranmission from the MAC client. With virtual destination
queueing, we would need to selectively block traffic that
is headed to a destination depending on whether or not
it is congested; yet we want to be able to admit traffic
from the same client that is headed to a destination that
does not have any congestion along its path. The
pseudo-code does not cover this.
> > > > > > > >
> > > > > > > > - Can one of the authors comment on the tolerance
> > > > > > > > of the scheme to message loss? The fairness message is
> > > > > > > > being sent hop-by-hop, and it seems like if it happens
> > > > > > > > to get lost, those that don't see it will continue
> > > > > > > > to increase their rates. If that is indeed the case,
> > > > > > > > I think something needs to be done about robustness.
> > > > >
> > > > > Fair rate messages get transmitted in fixed interval
> > > > > periodically. The
> > > > > interval is about 100us. In addition, Gandalf
> > > incorporates fair rate
> > > > > ramp-down and ramp-up in a low-pass filtered fashion at the
> > > > > intervals.
> > > > > Overall, these schemes integrate and establish a very
> > > robust Gandalf
> > > > > fairness algorithm, which is immune to occasional fair rate
> > > > > message losses.
> > > > > However, a persistent fair rate message loss over several
> > > consecutive
> > > > > intervals will trigger Gandalf protection procedure.
> > > >
> > > >I thought that the fairness messages are sent no more often than
> > > >each DECAY_INTERVAL. I haven't done the math, but maybe
> that does
> > > >work out to 100 usec. The low pass filtered ramp-up is good.
> > > >The low pass filtered ramp-down may not necessarily be the
> > > >best in times of message loss because it doesn't give up
> > > >bandwidth as quickly as it should (or could if the congestion
> > > >messages are getting lost). I think simulations should consider
> > > >the effect of fairness message loss on performance.
> > > >(I'm pushing for quantifying behavior in worst-case scenarios
> > > >as alluded to by other folks on the simulation thread.)
> > >
> > > If you like, Gandalf doesn't stop you from sending more often
> > > fairness
> > > messages. Actually, Gandalf doesn't do low pass in ramp-down,
> > > so Gandalf
> > > may well be the best.
> > > As Gandalf performance is not sensitive to occasional
> > > congestion message
> > > loss, I don't see the necessity to spend much effort to study
> > > its effects.
> > > Nonetheless, you are very much welcome to study the
> > > situations. I would
> > > certainly be interested to see your results if you may kindly
> > > share them.
> >
> >I misunderstood your earlier response. If it doesn't
> >do low pass ramp-down, that's great.
> >
> >As far as testing performance in the presence
> >of loss of fairness messages - If you were
> >following the thread on simulation, there were a number
> >of people that expressed the necessity to test the
> >algorithms to their limit. As a technical standards body,
> >I think it is our moral responsibility to find out
> >where things break so that we can work on fixing them,
> >or making sure that they break safely,
> >before the standard is written and published.
> >But anyway, I don't think this discussion is going
> >to go anywhere till one of us does the work, so let's
> >just drop this one for now.
>
> I did follow the simulation thread. In addition to the limit
> test, I also
> heard people talking about weigh-in "likelihood of occurrence of a
> pathological traffic scenario". So there is a balance to
> everything. It is
> no exception for a standard. The choice is whether you
> optimize a standard
> for actual network scenarios that can realistically occur or
> you push a
> standard to no limits and no breaks even though some of the
> limits may
> never be materialized in real network.
Let's just drop this one for now, since I think it needs more
work in order to continue discussion.
>
> > >
> > > > >
> > > > > > > >
> > > > > > > > - What is the significance of the parameter AGECOEFF
> > > > > > > > and how does one determine what is a good value to
> > > > > > > > use for it?
> > > > >
> > > > > This parameter is part of Gandalf fair rate calculation,
> > > > > which is used for
> > > > > all transmission rates and not supposed to change at all.
> > > >
> > > >It's nice to know that I don't have to change it :-), but
> > > >it doesn't help me understand why it is needed. Basically,
> > > >I'd like to know why one should be so sure that 4 is best
> > > >value.
> > >
> > >
> > > Through heuristics and simulations, we made sure a value of 4
> > > is the best.
> > > Well, you are definitely welcome to try out simulations to be
> > > certain on
> > > different values for it and share your discovery with .17 WG.
> > >
> >
> >In order to do any useful simulations, I need to understand
> >what the purpose of each parameter is so that I can start
> >with a reasonable value and measure its effect, and then
> >decide whether the results are even intuitive or not. As
> >far as AGECOEFF goes, quite frankly, I just don't know what
> >it does. All I was hoping to get from you was an explanation
> >for why the parameter was introduced. For example, LP_ALLOW
> >is used to apply a low pass filter function to one of the
> >rates. Maybe I'm too dumb, but the need for AGECOEFF is
> >just not obvious to me...
>
> Ok, if I understand you correctly this time, you are actually
> not asking
> why a value of 4 is the best, instead, you ask why there is a
> AGECOEFF in
> the algorithm. In my understanding, AGECOEFF is a scaling factor to
> simplify the rate measurement or its counting used in
> Gandalf. For example,
> the fair rate in Gandalf is not the same as transmission
> rate, but you can
> always convert a fair rate to a transmission rate.
It's still not very clear. Why it is necessary to have
a scaling factor? In what way does it simplify the rate
measurement?