RE: [RPRWG] Some questions about the pseudo-code in Gandalf
Donghui,
Comments inline.
-Anoop
> -----Original Message-----
> From: Donghui Xie [mailto:dxie@xxxxxxxxx]
> Sent: Monday, January 07, 2002 9:38 AM
> To: Anoop Ghanwani
> Cc: stds-802-17@xxxxxxxx
> Subject: RE: [RPRWG] Some questions about the pseudo-code in Gandalf
>
> >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
>
> Is this a limit test? It can be impressive if a weight of 15
> can increase a
> node's transmission power to 15G on 10G link.
Indeed, this is somewhat of a limit test, but not an unreal
one. If you consider a ring with 15 nodes and you have
one of them acting as a hub, then the hub needs to be able
to send that much more traffic than any other node on the
ring.
>
> >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 fairness message would allow upstream node to increase
> its transmission
> fast. There should be some effects. But certainly not as
> effect to 15G.
Well, by using the fairness message, the node computes
a fair rate of 15 G. Given that line rate is 10 G, the
fairness message has had no effect whatsoever.
>
> >(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.)
>
> What control do you think needed? What's the reason for
> having to control
> any temporary overload? It may be clear if the overload is
> from 9G to 15G.
> I don't see any harm for temporary overload from 9G to 10G in
> a ramp-up
> as-fast-as-possible fashion. This temporary overload allows dynamic
> fairness convergence to take place while maintaining 100%
> link utilization.
> Besides, it saves on the simplicity of weighted fairness.
> Though going
> limit tends to be short on the balance between temporary overload,
> simplicity ... and full link utilization ...and maybe even possible
> operational savings associated with weight provisioning ....
Temporary overload will impact your ability to provide guarantees
to the medium priority traffic as its packets get queued behind
large buffers. And if the buffers are not big enough, you'll
end up having packet loss.
> >Again, I'm still in the midst of understanding this stuff
> >so please let me know if my analysis is off.
>
> You understand well since your analysis looks very good.
>
Thanks!
>
> > >
> > > > >
> > > > > > >
> > > > > > > > >
> > > > > > > > > - 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?
>
> Boy, did I spell the "pseudo-code" wrong as "algorithm" in
> my last sentence?
May be I'm misunderstanding something, but I was referring to
the following statement made by you. The MAC does need to do
some extra work to allow for multiple choke points. That extra
work does not appear in the pseudo-code. That's all that I was
trying to say. I'm not sure what you meant by the above statement
when you said that "But for the algorithm, it is simply not a
right thing to do."
>
>
> > >
> > > >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
>
> Agreed. This is what Gandalf MAC does.
>
> >pseudo-code does not cover this.
>
> Not exactly sure the pseudo-code not cover it. One thing is
> for sure that
> once MAC utilizes the pseudo-code, especially the part of generating
> my_rate_ok, MAC exhibits the behavior you described. I think Gandalf
> section 6.2 and 6.3 write about this.
Yes, the behavior is covered in Section 6, but it doesn't
appear in the pseudo-code. Someone wanting to implement Gandalf
with multi-choke needs to figure it out themselves.
> > > > > > > > > > - 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?
>
> It is necessary in making Gandalf rate counters, not other type of
> counters. These counters only need to accumulate bytes. At
> Gandalf decay
> interval, these counters get reduced by the scaling factor.
> As such, the
> computing for the counters is efficient and simple.
I still don't get it. You keep saying it makes the computation
simple and efficient but you don't explain how or why. As far
as I can tell, reducing the value of a counter by some predetermined
fraction does not make the procedure any more simple or efficient.