RE: [RPRWG] Some questions about the pseudo-code in Gandalf
Donghui,
Many thanks for response. I'm going to go ahead and
delete the answers that I'm happy with, but would like
to continue the discussion on some of the things that
are still unclear in my mind.
-Anoop
> -----Original Message-----
> From: Donghui Xie [mailto:dxie@xxxxxxxxx]
> Sent: Wednesday, January 02, 2002 11:01 AM
> To: Anoop Ghanwani
> Cc: stds-802-17@xxxxxxxx
> Subject: RE: [RPRWG] Some questions about the pseudo-code in Gandalf
>
> >- lp_allow is computed but never used. Is something missing?
>
> Please see the pseudo code in the section of "THESE ARE
> UPDATED EVERY CLOCL
> CYCLE" on page 46.
In an actual implementation, would one really have to do these
updates _every single_ clock tick? Or is there some way to make
it less frequent? If so, what frequency of update is recommended?
> > > - 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.
>
> > >
> > > - 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.
> > > > - First off, it seems that the pseudo-code does not handle
> > > > the multi-choke point feature discussed in the proposal.
> > > > It would be nice to see this.
>
> ditto.
I guess you agree with my statement above :-)
>
> > > >
> > > > - When a fairness packet is received, there's some
> > > > code that says:
> > > > if (fairness_pkt.SA == my_SA) &&
> > > > ((node_state == wrapped)) {
> > > > ..
> > > > } else {
> > > > ..
> > > > }
>
> One check condition is missing here. We'll update it Gandalf in next
> version. The complete check should be
> if ( (fairness_pkt.SA == my_SA) &&
> ( (fairness_pkt.ring_id == my_ring_id) || ( node_state ==
> wrapped) ) ) {
> rcvd_rate = NULL_RCVD_INFO;
> } else {
> rcvd_rate = fairness_pkt.rate;
> }
>
> The first check states that if a node receives a fair rate
> originated from
> itself in same ringlet, which means its rate is the smallest
> around the
> ring, it will treat the received rate as a NULL info so that
> its allowed
> fair rate will be able to ramp up.
>
> In case of the node is in wrap, if it receives on its outer
> ring a fair
> rate info transmitted from its inner ring, it understands
> that the ring is
> wrapped, both inner ringlet and outer ringlet become one ring
> essentially,
> so its rate is the smallest around the ring, it will treat
> this case the
> same way as in previous case.
>
> > > > Should we also be checking the RING ID in the fairness
> > > > packet? Or is it proposing that we don't do any
> > > > bandwidth management when the ring wraps?
>
> Ditto. Gandalf checks RING ID, and its fairness algorithm guarantees
> bandwidth fairness management in all situations.
OK. That's what it seemed like to me when I read it. I wanted
to make sure that you did intend to check the ring ID as well.
> > > >
> > > > - 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.)
>
> > > >
> > > > - 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.