Re: [Cake] total download rate with many flows

[George Amanakis <g_amanakis@yahoo.com>]

I meant proportionally to (1-1/sqrt(x)).


On 11/13/2017 8:51 PM, George Amanakis wrote:
> I am exploring this idea further. If q->time_next_packet is 
> incremented for dropped packets proportionally to (1-1/x), where x is 
> the count of all flows in the tin that is being served, ingress mode 
> works much more smoothly: latency is still <50ms and throughput is 
> very near to the set limit.
>
> I *tried* to make a patch from latest cobalt.
>
> =============8<=============
> diff --git a/sch_cake.c b/sch_cake.c
> index 82f264f..752783a 100644
> --- a/sch_cake.c
> +++ b/sch_cake.c
> @@ -145,6 +145,7 @@ struct cake_flow {
>         struct list_head  flowchain;
>         s32               deficit;
>         struct cobalt_vars cvars;
> +       struct cobalt_vars cvars2;
>         u16               srchost; /* index into cake_host table */
>         u16               dsthost;
>         u8                set;
> @@ -254,6 +255,7 @@ struct cake_sched_data {
>         u32             avg_window_bytes;
>         u32             avg_peak_bandwidth;
>         u64             last_reconfig_time;
> +       u32             drop_len;
>  };
>
>  enum {
> @@ -820,7 +822,7 @@ static unsigned int cake_drop(struct Qdisc *sch, 
> struct sk_buff **to_free)
>         sch->qstats.drops++;
>
>         if(q->rate_flags & CAKE_FLAG_INGRESS)
> -               cake_advance_shaper(q, b, cake_overhead(q, len), now);
> +               q->drop_len += len;
>
>  #if LINUX_VERSION_CODE < KERNEL_VERSION(4, 8, 0)
>         kfree_skb(skb);
> @@ -1274,7 +1276,9 @@ retry:
>                 /* drop this packet, get another one */
>                 if(q->rate_flags & CAKE_FLAG_INGRESS) {
>                         len = cake_overhead(q, qdisc_pkt_len(skb));
> -                       cake_advance_shaper(q, b, len, now);
> +                       flow->cvars2.count = 
> b->bulk_flow_count+b->sparse_flow_count+b->decaying_flow_count+b->unresponsive_flow_count;
> +                       cobalt_invsqrt(&(flow->cvars2));
> +                       q->drop_len += (len - reciprocal_scale(len, 
> flow->cvars2.rec_inv_sqrt));
>                         flow->deficit -= len;
>                         b->tin_deficit -= len;
>                 }
> @@ -1286,8 +1290,6 @@ retry:
>                 qdisc_qstats_drop(sch);
>                 kfree_skb(skb);
>  #endif
> -               if(q->rate_flags & CAKE_FLAG_INGRESS)
> -                       goto retry;
>         }
>
>         b->tin_ecn_mark += !!flow->cvars.ecn_marked;
> @@ -1340,7 +1342,7 @@ static void cake_advance_shaper(struct 
> cake_sched_data *q, struct cake_tin_data
>         if(q->rate_ns) {
>                 s64 tdiff1 = b->tin_time_next_packet - now;
>                 s64 tdiff2 = (len * (u64)b->tin_rate_ns) >> 
> b->tin_rate_shft;
> -               s64 tdiff3 = (len * (u64)q->rate_ns) >> q->rate_shft;
> +               s64 tdiff3 = ((q->drop_len + len) * (u64)q->rate_ns) 
> >> q->rate_shft;
>
>                 if(tdiff1 < 0)
>                         b->tin_time_next_packet += tdiff2;
> @@ -1348,6 +1350,7 @@ static void cake_advance_shaper(struct 
> cake_sched_data *q, struct cake_tin_data
>                         b->tin_time_next_packet = now + tdiff2;
>
>                 q->time_next_packet += tdiff3;
> +               q->drop_len = 0;
>         }
>  }
>
> @@ -1711,6 +1714,7 @@ static void cake_reconfigure(struct Qdisc *sch)
>  {
>         struct cake_sched_data *q = qdisc_priv(sch);
>         int c, ft;
> +       q->drop_len=0;
>
>         switch (q->tin_mode) {
>         case CAKE_MODE_BESTEFFORT:
> @@ -1941,6 +1945,7 @@ static int cake_init(struct Qdisc *sch, struct 
> nlattr *opt)
>
>                         INIT_LIST_HEAD(&flow->flowchain);
>                         cobalt_vars_init(&flow->cvars);
> +                       cobalt_vars_init(&flow->cvars2);
>
>                         q->overflow_heap[k].t = i;
>                         q->overflow_heap[k].b = j;
>
> =============8<=============
>
>
>
> On 11/11/2017 10:48 PM, George Amanakis wrote:
>> I totally understand what you are saying. However, I believe cake's 
>> egress and ingress modes currently behave as two extremes. One could 
>> argue that neither of them is the golden mean. With a patch in 
>> ingress mode (see below) and a single host using 32 flows to download 
>> I managed to increase throughput from ~7Mbps to ~10Mbps (configured 
>> limit 12200kbps) while latency increased from ~10ms to ~50ms, which 
>> would still be acceptable. As a comparison egress mode in the same 
>> setup gives me throughput ~11.5Mbps and latency ~500ms.
>>
>> I would like to hear your thoughts about this idea: the patch is 
>> incrementing q->time_next_packet for dropped packets differently than 
>> for passed-through ones. Please focus on the idea, not the actual 
>> implementation :) (also pasted in https://pastebin.com/SZ14WiYw)
>>
>> =============8<=============
>>
>> diff --git a/sch_cake.c b/sch_cake.c
>> index 82f264f..a3a4a88 100644
>> --- a/sch_cake.c
>> +++ b/sch_cake.c
>> @@ -769,6 +769,7 @@ static void cake_heapify_up(struct 
>> cake_sched_data *q, u16 i)
>>  }
>>
>>  static void cake_advance_shaper(struct cake_sched_data *q, struct 
>> cake_tin_data *b, u32 len, u64 now);
>> +static void cake_advance_shaper2(struct cake_sched_data *q, struct 
>> cake_tin_data *b, u32 len, u64 now);
>>
>>  #if LINUX_VERSION_CODE < KERNEL_VERSION(4, 8, 0)
>>  static unsigned int cake_drop(struct Qdisc *sch)
>> @@ -1274,7 +1275,7 @@ retry:
>>                 /* drop this packet, get another one */
>>                 if(q->rate_flags & CAKE_FLAG_INGRESS) {
>>                         len = cake_overhead(q, qdisc_pkt_len(skb));
>> -                       cake_advance_shaper(q, b, len, now);
>> +                       cake_advance_shaper2(q, b, len, now);
>>                         flow->deficit -= len;
>>                         b->tin_deficit -= len;
>>                 }
>> @@ -1286,8 +1287,6 @@ retry:
>>                 qdisc_qstats_drop(sch);
>>                 kfree_skb(skb);
>>  #endif
>> -               if(q->rate_flags & CAKE_FLAG_INGRESS)
>> -                       goto retry;
>>         }
>>
>>         b->tin_ecn_mark += !!flow->cvars.ecn_marked;
>> @@ -1351,6 +1350,24 @@ static void cake_advance_shaper(struct 
>> cake_sched_data *q, struct cake_tin_data
>>         }
>>  }
>>
>> +static void cake_advance_shaper2(struct cake_sched_data *q, struct 
>> cake_tin_data *b, u32 len, u64 now)
>> +{
>> +       /* charge packet bandwidth to this tin, lower tins,
>> +        * and to the global shaper.
>> +        */
>> +       if(q->rate_ns) {
>> +               s64 tdiff1 = b->tin_time_next_packet - now;
>> +               s64 tdiff2 = (len * (u64)b->tin_rate_ns) >> 
>> b->tin_rate_shft;
>> +               s64 tdiff3 = (len * (u64)q->rate_ns) >> q->rate_shft;
>> +
>> +               if(tdiff1 < 0)
>> +                       b->tin_time_next_packet += tdiff2;
>> +               else if(tdiff1 < tdiff2)
>> +                       b->tin_time_next_packet = now + tdiff2;
>> +
>> +               q->time_next_packet += (tdiff3*27)>>5;
>> +       }
>> +}
>>  static void cake_reset(struct Qdisc *sch)
>>  {
>>         u32 c;
>>
>> =============8<=============
>>
>> On 11/10/2017 4:50 PM, Jonathan Morton wrote:
>>>
>>> In fact, that's why I put a failsafe into ingress mode, so that it 
>>> would never stall completely.  It can happen, however, that 
>>> throughput is significantly reduced when the drop rate is high.
>>>
>>> If throughput is more important to you than induced latency, switch 
>>> to egress mode.
>>>
>>> Unfortunately it's not possible to guarantee both low latency and 
>>> high throughput when operating downstream of the bottleneck link.  
>>> ECN gives you better results, though.
>>>
>>> - Jonathan Morton
>>>
>>
>