[Cake] Choosing a tin to work on

[Cake] Choosing a tin to work on

[George Amanakis]

[-- Attachment #1: Type: text/plain, Size: 1210 bytes --]

Hi Jonathan,
I have some questions regarding the algorithm to choose a tin to dequeue from in sch_cake.c:-----------8<------------        int oi, best_tin=0;
        s64 best_time = 0xFFFFFFFFFFFFUL;

        for(oi=0; oi < q->tin_cnt; oi++) {
            int tin = q->tin_order[oi];
            b = q->tins + tin;
            if((b->sparse_flow_count + b->bulk_flow_count) > 0) {
                s64 tdiff = b->tin_time_next_packet - now;
                if(tdiff <= 0 || tdiff <= best_time) {
                    best_time = tdiff;
                    best_tin = tin;
                }
            }
        }-----------8<------------
1) best_time is defined as a positive signed integer, this equals to 78 hours if I did the calculations right. Why did you choose this? Did you mean to define it as "-1"?2) If you meant to define it as "-1", the condition "tdiff <= best_time" would not matter. I can see no case where "tdiff > 0" and "tdiff <= best_time".
Could you shed some light into this?
Thank you,George




 

[-- Attachment #2: Type: text/html, Size: 2684 bytes --]

[Cake] Fw: Choosing a tin to work on

[George Amanakis]

[-- Attachment #1: Type: text/plain, Size: 1228 bytes --]

Hi Jonathan,

I have some questions regarding the algorithm to choose a tin to dequeue from in sch_cake.c:-----------8<------------
        int oi, best_tin=0;
        s64 best_time = 0xFFFFFFFFFFFFUL;

        for(oi=0; oi < q->tin_cnt; oi++) {
            int tin = q->tin_order[oi];
            b = q->tins + tin;
            if((b->sparse_flow_count + b->bulk_flow_count) > 0) {
                s64 tdiff = b->tin_time_next_packet - now;
                if(tdiff <= 0 || tdiff <= best_time) {
                    best_time = tdiff;
                    best_tin = tin;
                }
            }
        }
-----------8<------------

1) best_time is defined as a positive signed integer, this equals to 78 hours if I did the calculations right. Why did you choose this? Did you mean to define it as "-1"?
2) If you meant to define it as "-1", the condition " tdiff <= best_time" would not matter. I can see no case where " tdiff > 0" and " tdiff <= best_time".

Could you shed some light into this?

Thank you,
George






[-- Attachment #2: Type: text/html, Size: 2170 bytes --]

Re: [Cake] Choosing a tin to work on

[Kevin Darbyshire-Bryant]

On 11/04/17 14:59, George Amanakis wrote:
> Hi Jonathan,
>
> I have some questions regarding the algorithm to choose a tin to dequeue
> from in sch_cake.c:
> -----------8<------------
>         int oi, best_tin=0;
>         s64 best_time = 0xFFFFFFFFFFFFUL;
>
>         for(oi=0; oi < q->tin_cnt; oi++) {
>             int tin = q->tin_order[oi];
>             b = q->tins + tin;
>             if((b->sparse_flow_count + b->bulk_flow_count) > 0) {
>                 s64 tdiff = b->tin_time_next_packet - now;
>                 if(tdiff <= 0 || tdiff <= best_time) {
>                     best_time = tdiff;
>                     best_tin = tin;
>                 }
>             }
>         }
> -----------8<------------
>
> 1) best_time is defined as a positive signed integer, this equals to 78
> hours if I did the calculations right. Why did you choose this? Did you
> mean to define it as "-1"?
> 2) If you meant to define it as "-1", the condition "tdiff <= best_time"
> would not matter. I can see no case where "tdiff > 0" and "tdiff <=
> best_time".
>
> Could you shed some light into this?
>
> Thank you,
> George


I'll try to answer this based on a vague bit of understanding...and then 
Jonathan can shoot me down as well :-)

So the 'best_time' is signed because we can have a packet in a tin that 
is not yet due to be sent (a positive result...ie. we have got here 
early) and/or we can have a tin that is due now/overdue (a zero/negative 
result, we've got here late)

The complication is that we can have multiple tins overdue, so we want 
the highest priority *and* least overdue (least late) tin - this is the 
reason for searching in tin_order[oi] and as a result tdiff can be <=0 
and bigger than best_time.

best_time is initialised to the 'most early' time possible.


Kevin  (awaits to be shot at :-) )

Re: [Cake] Choosing a tin to work on

[xnor]

Hey,

>>                 s64 tdiff = b->tin_time_next_packet - now;
>>                 if(tdiff <= 0 || tdiff <= best_time) {
>>                     best_time = tdiff;
>>                     best_tin = tin;
>>                 }
>
>I'll try to answer this based on a vague bit of understanding...and 
>then Jonathan can shoot me down as well :-)
>
>So the 'best_time' is signed because we can have a packet in a tin that 
>is not yet due to be sent (a positive result...ie. we have got here 
>early) and/or we can have a tin that is due now/overdue (a 
>zero/negative result, we've got here late)
>
>The complication is that we can have multiple tins overdue, so we want 
>the highest priority *and* least overdue (least late) tin - this is the 
>reason for searching in tin_order[oi] and as a result tdiff can be <=0 
>and bigger than best_time.
>
>best_time is initialised to the 'most early' time possible.
that makes no sense to me.

best_time is initialized to some high value (though why is it not 0x7FFF 
FFFF FFFF FFFFL, the highest possible positive s64?) such that no matter 
how far tdiff is in the future, best_time will always be set to the 
lower tdiff.
(Just like you would initialize a variable keeping track of the max to 
the lowest possible value, you set a min variable to the highest 
possible value.)

But if you wanted best_time to end up as the lowest value, then you 
would have to only set it if tdiff < best_time (or <= if you actually 
want to prefer the last tin if they happen to have the same tdiff), and 
not also if tdiff <= 0.

For example, if tdiff values were 5000, -5000, 0 then best_time would be 
set to 0. The last value less than or equal to zero will always win as 
best_tin.
If all tdiff values are positive then best_time will end up as the 
lowest value however.

Re: [Cake] Choosing a tin to work on

[Jonathan Morton]

> On 12 Apr, 2017, at 15:48, xnor <xnoreq@gmail.com> wrote:
> 
> Hey,
> 
>>>                s64 tdiff = b->tin_time_next_packet - now;
>>>                if(tdiff <= 0 || tdiff <= best_time) {
>>>                    best_time = tdiff;
>>>                    best_tin = tin;
>>>                }
>> 
>> I'll try to answer this based on a vague bit of understanding...and then Jonathan can shoot me down as well :-)
>> 
>> So the 'best_time' is signed because we can have a packet in a tin that is not yet due to be sent (a positive result...ie. we have got here early) and/or we can have a tin that is due now/overdue (a zero/negative result, we've got here late)
>> 
>> The complication is that we can have multiple tins overdue, so we want the highest priority *and* least overdue (least late) tin - this is the reason for searching in tin_order[oi] and as a result tdiff can be <=0 and bigger than best_time.
>> 
>> best_time is initialised to the 'most early' time possible.
> that makes no sense to me.
> 
> best_time is initialized to some high value (though why is it not 0x7FFF FFFF FFFF FFFFL, the highest possible positive s64?) such that no matter how far tdiff is in the future, best_time will always be set to the lower tdiff.
> (Just like you would initialize a variable keeping track of the max to the lowest possible value, you set a min variable to the highest possible value.)
> 
> But if you wanted best_time to end up as the lowest value, then you would have to only set it if tdiff < best_time (or <= if you actually want to prefer the last tin if they happen to have the same tdiff), and not also if tdiff <= 0.
> 
> For example, if tdiff values were 5000, -5000, 0 then best_time would be set to 0. The last value less than or equal to zero will always win as best_tin.
> If all tdiff values are positive then best_time will end up as the lowest value however.

For some reason I never seem to have got the initial question post.  The two of you are broadly right though.

The intention here is:

- Find the highest-priority tin with a packet already due;
- If none are due yet, find the one with a packet due soonest.

This should have the same type of “soft priority” behaviour as the previous WRR version, but I was hoping it could reduce the latency for processing sparse low-latency tins while under steady bulk load.

 - Jonathan Morton

Re: [Cake] Choosing a tin to work on

[George Amanakis]

[-- Attachment #1: Type: text/plain, Size: 495 bytes --]


>The last value less than or equal to zero will always win as best_tin.
>If all tdiff values are positive then best_time will end up as the lowest value however.
I agree with xnoreq. The algorithm as it is will not always return the least overdue tin. It returns either the lowest positive tdiff (if all tdiff values are positive), or the lowest negative one (if not all tdiff values are positive). This could be accomplished just with "if (tdiff<=best_time)" as xnoreq pointed out.
George

[-- Attachment #2: Type: text/html, Size: 716 bytes --]

Re: [Cake] Choosing a tin to work on

[George Amanakis]

[-- Attachment #1: Type: text/plain, Size: 333 bytes --]

I think I got the point.
For example in diffserv3: tdiff values -2, 2, -1 for tins 1, 0, 2, then:"if (tdiff<=0 || tdiff<=best_time)" returns best_time -1 and tin 2. Highest priority tin with packet overdue."if (tdiff<=best_time)" would return best_time -2 and tin 1. Not the highest priority tin with packet overdue.
Thank you,George

[-- Attachment #2: Type: text/html, Size: 570 bytes --]