[altq 1466] Re: Another source of HFSC-ALTQ unfairness

[Oleg Cherevko <olwi@aq.ml.com.ua>]

Hi Kenjiro!

On Mon, 29 Apr 2002, Kenjiro Cho wrote:

> > link-sharing service curves. It is, however, a bit against the "spirit of 
> > HFSC" in the sense that it simply drops service curves min operation
> > altogether as soon as there are any troubles with aligning those curves
> > against single consistent virtual time from one parent backlogged period.
> 
> Hmm, the patch doesn't change the logic when the parent backlog period
> doesn't change.

Oops. Sorry, I probably worded my idea badly.
By "as soon as there are any troubles with aligning those curves against
single consistent virtual time from one parent backlogged period"
I referred to the case when parent the backlog period *did* change.
Exactly because it did change we would have trouble aligning the class
virtual curve from the earlier parent backlog period with its link-sharing
service curve applied to fresh-calculated vt from the current parent
backlog period. By "aligning the curves" I refer to the graphical
representation of the rtsc_min() operation when we first put both curves
to the common coordinate system (this is "aligning"), then calculate
minimum.

Now I see that I made yet another mistake in my previous posting by
suggesting that rtsc_min() is dropped in this case. It is not dropped.
(In fact, to drop rtsc_min() in favor of rtsc_init() was an idea that *I*
was thinking about, and somehow I managed to convince myself that your
patch does exactly this. This is not true, I'm sorry).

Nevertheless, the main idea of my previous posting still holds, so let
me try to formulate it once again.

Take 2. :)

In the case of linear link-sharing service curves your patch should work
just great. However, for non-linear (in particular, concave) service
curves it is not that obvious what the effect of this patch would be.
Let me explain.
In the case of concave service curves the result of 
rtsc_min( virtual, fsc, vt, total ) operation may be of 3 types:
1) the original virtual rtsc unchaged
2) some combination of both curves (when they intersect)
3) the fsc applied to the point with coordinates (vt, total)
The case 3) happens when "enough" time passed since the last packet for
this class was dequeued, i.e. the class was idle "long enough" (the exact 
value of "enough" may vary but it should be <= d*(m1/m2)).

In your patch (in the case parent backlog period did change) you
initialize the virtual rtsc to be fsc applied to the point with
coordinates (0, total). This is effectively a sort of "case 3) for
rtsc_min() operation", thus suggesting that in the case of the new parent
backlog period we assume that there is "enough" time passed by the moment
vt=0 (i.e. by the start of the new parent backlog period). We assume this
simply because we don't know how to calculate exactly what amount of
(virtual) time "really" passed. Sometimes this assumption will work OK,
but I'm afraid that there are cases when it would lead to rather
unexpected effects. I don't know what kind of unexpected effects it may
lead to, and I'm not going to actively search for ones, instead I want to
invent method of combining virtual time values from differnet parent
backlog periods into one consistent virtual time spanning all the periods,
thus making rtsc_min() with curves from different periods possible.

Anyway, as I said earlier, the init_v() with your patch should work better
than the nonpathced version of init_v().

BTW, I looked more closely to the CMU HFSC implementation and it finally
started to make some sense to me. :) I got a couple of ideas from their
code that should be of help in this particular case with init_v().

-- 
Olwi