[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: new WRR sched, updated TBF and "real" ingres implementation



> I believe it is based on what the CBQ paper says (it's been a while since
> i last looked at it).

No, no. CBQ papers doesn't specify what kind of estimator is to be
used or how should it work. It only said (see Appendix A) that in their
work at NS they used avgidle approach with right-edge measurement.

> Alexey refers to it as "virtual time" -- it is actually the
> bit-serialization time of the last seen packet (eg it takes 10 ns to
> transmit 1 bit on 100Mbps wire). So it is necessary to know the hardware
> speed for this.

IMHO you are not right. The virtual time (in Alexander's words) is assumed
transmission time of last packet - as you said above. It is computed in
cbq_update as last_pktlen/rate. pktlen/HW_rate is substracted here
from new "undertime" value because we are measuring from right edge so
that the time needed by hw already passed at time of update so we need
to correct value of undertime.
If we use left edge we don't need it.
When I talk about "artifical time" it is the integrated time which
is hold in q->now (as oposed to real time in q->rt_now). The "artifical
time" (Alexander's words again) is computed in cbq_dequeue and it is
second place where real HW rate is needed. The clock integrator is
(in my understanding) used to have correct time of right edge of last
packet. It is because we don't know packet's right edge in linux.
We only know left edge of next packet and because they are not always
the same, Alexander uses clock integrator to minimize error (it is
partialy explained in top comment in source file).

> In order to calculate the "diff"/idle between the estimation and reality,
> you need to take into account the departure time which translates to be
> the right edge. I might still be missing something ...

you are right but estimation is based on allocated rate, not on HW rate.
The hw rate is used here only for undertime correction.
But left to left edge gives you nearly the same results only delayed
by one packet - it leads to simple linear equation which is hopefuly
simple to solve.
I patched CBQ code in this manner but I'm not sure about it. Probably
you or Alexander are only guys I can spoke with ..

> > to mail Alexander about it but with no success :-(.
> 
> He is a very busy guy.

yes I understand. I'm glad that you take some of your time to
discuss with me.

> I still havent understood how you will kill the dependency by going 
> with the left edges; it is very useful if you are sure you can do it. The
> other two CBQ implementations i have seen still have the dependency on.

well, it is probably possible as I stated in paragraph above.
The idle time is diff between time which should be taken by
packet and time which has been really taken.
It should not matter which edge you use. In left-edge solution
you can update idle time at successful dequeue event which is
left edge of the current packet. Now you can compute idle of
last packet. 
A bit trickier is computing of new undertime.
Let X be new undertime. Then class will be under-time when
 avgidle*(1-W)+W*(X-curr_len/class_rate)==0.
The equation is simple to solve using shift & adds. So
that now you have both avgidle & undertime values without
using device BW.
Maybe I'm missing something but it seems resonable, doesn't it?
When I got some time I'll try it with NS-2.

> > I didn't too .. I was only interested in its principles.
> > Still I'd like to write CBQ but with TBF classifiers instead
> > of idle est. But I have not much time for it :-(
> 
> ;-> then i think you shouldnt call it CBQ anymore. But seriously: isnt

:) I can. As I said above the Floyd's CBQ paper doesn't mandate
type of estimator ..

> this what prioor you WRR would achieve if you stash a TBF inside it?

Not exactly. It will have still one drawback. Delay. With
CBQ (with or without TBF estimators) class will be allowed
sent when it is underlimit or when it can borrow.
In both cases there will be NO delay for packet. This is
only place where WRR+TBF will stuck - it will wait until
delay action for current packet finishes.
In CBQ+TBF it will be fixed because there is one TBF estimator
per class and when one of then wants wait (penalize class)
and another class is able to send it will work. It is due
to cbq_over_classic which computes minimum from all delays...

I have the CBQ+TBF already written but when I tried it at
weekend it gave me some oops. But some debugging will sure
fix it.
I will post some measurements then ;)

regards, devik