[altq 92] Re: When a class is delayed (undertime)

[Kenjiro Cho <kjc@csl.sony.co.jp>]

Before going into the details, I think it is better to summarize the
history of the CBQ code.

During 93-95, LBL, UCL and SUN work on the CBQ implementation.
I don't know how they work together but I have an impression that
 - LBL wrote the original CBQ core part (rm_class.[ch]) and the CBQ
   code for the ns simulator.
 - UCL developed a Solaris stream module for CBQ
 - Sun was mainly working on RSVP support using CBQ
(correct me if I misinterpreted their roles.)

The original CBQ paper was published in 1995, LBL cbq1.0 release was
also in 1995.

ALTQ started in 1996, its CBQ code was based on LBL cbq1.0, and UCL's cbq
that was available by ftp.  The first ALTQ release was in March 1997.

Micheal Speer of Sun and Sally Floyd of LBL released cbq2.0 in April
1997.  This version implements top-level link sharing, weighted-round
robin scheduler and other enhancements.
ALTQ merged cbq2.0 in Jun 1997.

Since then, ALTQ and SUN/LBL have continued to develop the code
independently but both parties have imported bug fixes and
enhancements from the other party.

So, my point here is that the original CBQ paper was written a long
time ago and is not completely consistent with the current code.

Another point is that the borrowing mechanism of CBQ is still weak;
the current mechanism cannot distribute the excess bandwidth in a
predictable manner. 
I've come to believe that we need to decouple scheduling of underlimit
classes and scheduling of classes borrowing from others, but it
requires a fundamental change in the CBQ scheduling algorithm.

>> I somehow agree with what Muthu said. Please check (Appendix A1 of "Link
>> sharing and resource management models for packet networks).
>> For a nonregulated class with avg negative, the time_to_send(undertime) is
>> set to make the next avgidle become 0.
>> But for a regulated calss with avg negative, the link-sharing scheduler sets
>> the undertime field for the class to f(s,b) (for minburst > 1, should be
>> offtime)  ahead of the current time. A regulated calss is never restricted
>> by the link-sharing scheduler to less than its allocatd bandwidth,
>> regardless of the "excess" bandwidth used by that class in the past. And in
>> the middle of A.3 in the same paper it says, the link-sharing scheduler sets
>> the time-to-send field for a regulated class to f(s,b)=s/b (for minburst >
>> 1, should be offtime) secondes ahead of the current time. .....at that time
>> the general scheduler is allowed to send a packet from that class regardless
>> of the value of avg.... . If the class is still overlimit after a packet is
>> ent, then the time-to-send field is again set to f(s,b)=s/b seconds ahead of
>> the current time.
>> So I also feel that this code
>>   TV_ADD_DELTA(&cl->undertime_,
>>         -((1 - RM_POWER) * cl->avgidle_) >> RM_FILTER_GAIN,
>>         &cl->undertime_);

>> in rmc_delay_action()needs to be retained so that this regulated class will
>> not be ponished by the bandwidth it used before.

First, if a class is not borrowable, a negative value of avgidle must
be very small so that adding the target idle time is not a big deal.

The second point is if we prefer a small penalty for the excess
bandwidth use in the past.
It doesn't matter for steady state traffic but I think it is safer for 
dynamic traffic since we don't exactly know how CBQ works with dynamic 
traffic.
(WFQ keeps no information about the past, which makes it difficult for 
a TCP flow to compete with a UDP flow...)

-Kenjiro