[Cake] total download rate with many flows
George Amanakis
g_amanakis at yahoo.com
Mon Nov 13 20:51:15 EST 2017
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
>>
>
More information about the Cake
mailing list