[Cake] progress? dual-src/dsthost unfairness

[Cake] progress? dual-src/dsthost unfairness

[Kevin Darbyshire-Bryant]

Last month there was an extensive thread about dual-src & dual-dst mode unfairness.  Has there been any progress on the topic?

It seemed to revolve around sparse flows v bulk flows being included in some overall host fairness count/bias.  Naive out loud thought experiment…is it worth maintaining a count of sparse flows & bulk flows per host so the sparse group and bulk group are treated separately?


Cheers,

Kevin D-B

012C ACB2 28C6 C53E 9775  9123 B3A2 389B 9DE2 334A

[Cake] progress? dual-src/dsthost unfairness

[George Amanakis]

I recently rewrote the patch (out-of-tree cake) so as to keep track of the 
bulk/sparse flow-count per host. I have been testing it for about a month
on a WRT1900ACS and it runs fine.

Would love to hear if Jonathan or anybody else has thought of
implementing something different.

Best,
George

---
 sch_cake.c | 120 +++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 88 insertions(+), 32 deletions(-)

diff --git a/sch_cake.c b/sch_cake.c
index d434ae0..10364ec 100644
--- a/sch_cake.c
+++ b/sch_cake.c
@@ -146,8 +146,10 @@ struct cake_flow {
 struct cake_host {
 	u32 srchost_tag;
 	u32 dsthost_tag;
-	u16 srchost_refcnt;
-	u16 dsthost_refcnt;
+	u16 srchost_bulk_flow_count;
+	u16 srchost_sparse_flow_count;
+	u16 dsthost_bulk_flow_count;
+	u16 dsthost_sparse_flow_count;
 };
 
 struct cake_heap_entry {
@@ -844,8 +846,6 @@ skip_hash:
 		 * queue, accept the collision, update the host tags.
 		 */
 		q->way_collisions++;
-		q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
-		q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
 		allocate_src = cake_dsrc(flow_mode);
 		allocate_dst = cake_ddst(flow_mode);
 found:
@@ -865,13 +865,13 @@ found:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 				i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].srchost_refcnt)
+				if (!q->hosts[outer_hash + k].srchost_bulk_flow_count &&
+						!q->hosts[outer_hash + k].srchost_sparse_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].srchost_tag = srchost_hash;
 found_src:
 			srchost_idx = outer_hash + k;
-			q->hosts[srchost_idx].srchost_refcnt++;
 			q->flows[reduced_hash].srchost = srchost_idx;
 		}
 
@@ -887,13 +887,13 @@ found_src:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 			     i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].dsthost_refcnt)
+				if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count &&
+						!q->hosts[outer_hash + k].dsthost_sparse_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
 found_dst:
 			dsthost_idx = outer_hash + k;
-			q->hosts[dsthost_idx].dsthost_refcnt++;
 			q->flows[reduced_hash].dsthost = dsthost_idx;
 		}
 	}
@@ -1912,21 +1912,39 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		flow->set = CAKE_SET_SPARSE;
 		b->sparse_flow_count++;
 
-		if (cake_dsrc(q->flow_mode))
-			host_load = max(host_load, srchost->srchost_refcnt);
+		if (cake_dsrc(q->flow_mode)) {
+			srchost->srchost_sparse_flow_count++;
+			host_load = max(host_load, srchost->srchost_sparse_flow_count);
+		}
 
-		if (cake_ddst(q->flow_mode))
-			host_load = max(host_load, dsthost->dsthost_refcnt);
+		if (cake_ddst(q->flow_mode)) {
+			dsthost->dsthost_sparse_flow_count++;
+			host_load = max(host_load, dsthost->dsthost_sparse_flow_count);
+		}
 
 		flow->deficit = (b->flow_quantum *
 				 quantum_div[host_load]) >> 16;
 	} else if (flow->set == CAKE_SET_SPARSE_WAIT) {
+		struct cake_host *srchost = &b->hosts[flow->srchost];
+		struct cake_host *dsthost = &b->hosts[flow->dsthost];
+
 		/* this flow was empty, accounted as a sparse flow, but actually
 		 * in the bulk rotation.
 		 */
 		flow->set = CAKE_SET_BULK;
 		b->sparse_flow_count--;
 		b->bulk_flow_count++;
+
+		if (cake_dsrc(q->flow_mode)) {
+			srchost->srchost_sparse_flow_count--;
+			srchost->srchost_bulk_flow_count++;
+		}
+
+		if (cake_ddst(q->flow_mode)) {
+			dsthost->dsthost_sparse_flow_count--;
+			dsthost->dsthost_bulk_flow_count++;
+		}
+
 	}
 
 	if (q->buffer_used > q->buffer_max_used)
@@ -2097,23 +2115,8 @@ retry:
 	dsthost = &b->hosts[flow->dsthost];
 	host_load = 1;
 
-	if (cake_dsrc(q->flow_mode))
-		host_load = max(host_load, srchost->srchost_refcnt);
-
-	if (cake_ddst(q->flow_mode))
-		host_load = max(host_load, dsthost->dsthost_refcnt);
-
-	WARN_ON(host_load > CAKE_QUEUES);
-
 	/* flow isolation (DRR++) */
 	if (flow->deficit <= 0) {
-		/* The shifted prandom_u32() is a way to apply dithering to
-		 * avoid accumulating roundoff errors
-		 */
-		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
-				  (prandom_u32() >> 16)) >> 16;
-		list_move_tail(&flow->flowchain, &b->old_flows);
-
 		/* Keep all flows with deficits out of the sparse and decaying
 		 * rotations.  No non-empty flow can go into the decaying
 		 * rotation, so they can't get deficits
@@ -2122,6 +2125,17 @@ retry:
 			if (flow->head) {
 				b->sparse_flow_count--;
 				b->bulk_flow_count++;
+
+				if (cake_dsrc(q->flow_mode)) {
+					srchost->srchost_sparse_flow_count--;
+					srchost->srchost_bulk_flow_count++;
+				}
+
+				if (cake_ddst(q->flow_mode)) {
+					dsthost->dsthost_sparse_flow_count--;
+					dsthost->dsthost_bulk_flow_count++;
+				}
+
 				flow->set = CAKE_SET_BULK;
 			} else {
 				/* we've moved it to the bulk rotation for
@@ -2131,6 +2145,22 @@ retry:
 				flow->set = CAKE_SET_SPARSE_WAIT;
 			}
 		}
+
+		if (cake_dsrc(q->flow_mode))
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
+
+		if (cake_ddst(q->flow_mode))
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
+
+		WARN_ON(host_load > CAKE_QUEUES);
+
+		/* The shifted prandom_u32() is a way to apply dithering to
+		 * avoid accumulating roundoff errors
+		 */
+		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
+				  (prandom_u32() >> 16)) >> 16;
+		list_move_tail(&flow->flowchain, &b->old_flows);
+
 		goto retry;
 	}
 
@@ -2151,10 +2181,24 @@ retry:
 					       &b->decaying_flows);
 				if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
 					b->decaying_flow_count++;
 				} else if (flow->set == CAKE_SET_SPARSE ||
 					   flow->set == CAKE_SET_SPARSE_WAIT) {
 					b->sparse_flow_count--;
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_sparse_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_sparse_flow_count--;
+
 					b->decaying_flow_count++;
 				}
 				flow->set = CAKE_SET_DECAYING;
@@ -2162,16 +2206,28 @@ retry:
 				/* remove empty queue from the flowchain */
 				list_del_init(&flow->flowchain);
 				if (flow->set == CAKE_SET_SPARSE ||
-				    flow->set == CAKE_SET_SPARSE_WAIT)
+				    flow->set == CAKE_SET_SPARSE_WAIT) {
 					b->sparse_flow_count--;
-				else if (flow->set == CAKE_SET_BULK)
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_sparse_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_sparse_flow_count--;
+
+				} else if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
-				else
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
+				} else
 					b->decaying_flow_count--;
 
 				flow->set = CAKE_SET_NONE;
-				srchost->srchost_refcnt--;
-				dsthost->dsthost_refcnt--;
 			}
 			goto begin;
 		}
-- 
2.20.1

Re: [Cake] progress? dual-src/dsthost unfairness

[Jonathan Morton]

> On 13 Feb, 2019, at 8:31 pm, George Amanakis <gamanakis@gmail.com> wrote:
> 
> I recently rewrote the patch (out-of-tree cake) so as to keep track of the 
> bulk/sparse flow-count per host. I have been testing it for about a month
> on a WRT1900ACS and it runs fine.
> 
> Would love to hear if Jonathan or anybody else has thought of
> implementing something different.

This does actually look more reasonable.  However:

1: Why is host_load calculated using host_sparse_flow_count instead of host_bulk_flow_count in cake_enqueue()?

2: Do we actually need to maintain host_sparse_flow_count at all, or only the bulk one?  If the above is corrected, I don't think there are any uses left.

 - Jonathan Morton

Re: [Cake] progress? dual-src/dsthost unfairness

[gamanakis]

>1: Why is host_load calculated using host_sparse_flow_count instead of
host_bulk_flow_count in cake_enqueue()?
Because the flow for which cake_enqueue() is run is by definition a sparse
one. So the host_load should be adjusted according to the sparse flow count
for the particular host. That's my reasoning behing this, would be happy to
hear other opinions.

>2: Do we actually need to maintain host_sparse_flow_count at all, or only
the bulk one?  If the above is corrected, I don't think there are any uses
left.
See above.

George
 

Re: [Cake] progress? dual-src/dsthost unfairness

[Jonathan Morton]

> On 13 Feb, 2019, at 9:26 pm, <gamanakis@gmail.com> <gamanakis@gmail.com> wrote:
> 
> Because the flow for which cake_enqueue() is run is by definition a sparse
> one. So the host_load should be adjusted according to the sparse flow count
> for the particular host. That's my reasoning behing this, would be happy to
> hear other opinions.

On the contrary, even if a particular flow is sparse, the relevant quantum calculation should involve the number of *bulk* flows attached to the same host.  Though there is possibly an argument for making it the *sum* of the sparse and bulk flows, making it just the sparse ones is wrong.

I need to think about this a bit more.  But meanwhile, try it with the sum.

 - Jonathan Morton

Re: [Cake] progress? dual-src/dsthost unfairness

[gamanakis]

> On the contrary, even if a particular flow is sparse, the relevant quantum
> calculation should involve the number of *bulk* flows attached to the same
> host.  Though there is possibly an argument for making it the *sum* of the
> sparse and bulk flows, making it just the sparse ones is wrong.

I was about to point out that my assumption is obviously wrong.
cake_enqueue() can still assign a packet to a bulk flow. 
Will try with the sum of the flows and report.

[Cake] progress? dual-src/dsthost unfairness

[George Amanakis]

Updated version with Jonathan's suggestion. Fairness is preserved.

            enp4s0	    enp1s0
Client A/B <------> router <------> server

tc qdisc add dev enp1s0 root cake bandwidth 100mbit dual-srchost
besteffort

tc qdisc add dev enp4s0 root cake bandwidth 100mbit dual-dsthost
besteffort

-----------8<-----------
Client A:
Data file written to ./tcp_8down-2019-02-13T150846.110370.flent.gz.
Summary of tcp_8down test run at 2019-02-13 20:08:46.110370:

                             avg       median          # data pts
 Ping (ms) ICMP   :         0.82         0.66 ms              340
 TCP download avg :         5.97         5.80 Mbits/s         301
 TCP download sum :        47.73        46.42 Mbits/s         301
 TCP download::1  :         5.96         5.82 Mbits/s         297
 TCP download::2  :         5.96         5.82 Mbits/s         298
 TCP download::3  :         5.97         5.82 Mbits/s         297
 TCP download::4  :         5.96         5.82 Mbits/s         297
 TCP download::5  :         5.97         5.82 Mbits/s         297
 TCP download::6  :         5.97         5.82 Mbits/s         297
 TCP download::7  :         5.97         5.82 Mbits/s         297
 TCP download::8  :         5.97         5.82 Mbits/s         297
Data file written to ./tcp_1up-2019-02-13T150847.148563.flent.gz.
Summary of tcp_1up test run at 2019-02-13 20:08:47.148563:

                           avg       median          # data pts
 Ping (ms) ICMP :         0.87         0.68 ms              340
 TCP upload     :        47.46        46.39 Mbits/s         265



Client B:
Data file written to ./tcp_1down-2019-02-13T150848.112225.flent.gz.
Summary of tcp_1down test run at 2019-02-13 20:08:48.112225:

                           avg       median          # data pts
 Ping (ms) ICMP :         0.75         0.65 ms              340
 TCP download   :        47.50        46.57 Mbits/s         300
Data file written to ./tcp_8up-2019-02-13T150849.120750.flent.gz.
Summary of tcp_8up test run at 2019-02-13 20:08:49.120750:

                           avg       median          # data pts
 Ping (ms) ICMP :         0.79         0.68 ms              340
 TCP upload avg :         5.95         5.78 Mbits/s         301
 TCP upload sum :        47.61        46.23 Mbits/s         301
 TCP upload::1  :         5.97         5.82 Mbits/s         171
 TCP upload::2  :         5.95         5.83 Mbits/s         224
 TCP upload::3  :         5.95         5.81 Mbits/s         223
 TCP upload::4  :         5.95         5.82 Mbits/s         224
 TCP upload::5  :         5.94         5.82 Mbits/s         223
 TCP upload::6  :         5.95         5.76 Mbits/s         275
 TCP upload::7  :         5.95         5.77 Mbits/s         222
 TCP upload::8  :         5.95         5.77 Mbits/s         221
-----------8<-----------

---
 sch_cake.c | 125 +++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 93 insertions(+), 32 deletions(-)

diff --git a/sch_cake.c b/sch_cake.c
index d434ae0..7567378 100644
--- a/sch_cake.c
+++ b/sch_cake.c
@@ -146,8 +146,10 @@ struct cake_flow {
 struct cake_host {
 	u32 srchost_tag;
 	u32 dsthost_tag;
-	u16 srchost_refcnt;
-	u16 dsthost_refcnt;
+	u16 srchost_bulk_flow_count;
+	u16 dsthost_bulk_flow_count;
+	u16 srchost_sparse_flow_count;
+	u16 dsthost_sparse_flow_count;
 };
 
 struct cake_heap_entry {
@@ -844,8 +846,6 @@ skip_hash:
 		 * queue, accept the collision, update the host tags.
 		 */
 		q->way_collisions++;
-		q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
-		q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
 		allocate_src = cake_dsrc(flow_mode);
 		allocate_dst = cake_ddst(flow_mode);
 found:
@@ -865,13 +865,13 @@ found:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 				i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].srchost_refcnt)
+				if (!q->hosts[outer_hash + k].srchost_bulk_flow_count &&
+						!q->hosts[outer_hash + k].srchost_sparse_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].srchost_tag = srchost_hash;
 found_src:
 			srchost_idx = outer_hash + k;
-			q->hosts[srchost_idx].srchost_refcnt++;
 			q->flows[reduced_hash].srchost = srchost_idx;
 		}
 
@@ -887,13 +887,13 @@ found_src:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 			     i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].dsthost_refcnt)
+				if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count &&
+						!q->hosts[outer_hash + k].dsthost_sparse_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
 found_dst:
 			dsthost_idx = outer_hash + k;
-			q->hosts[dsthost_idx].dsthost_refcnt++;
 			q->flows[reduced_hash].dsthost = dsthost_idx;
 		}
 	}
@@ -1901,6 +1901,7 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 	if (!flow->set || flow->set == CAKE_SET_DECAYING) {
 		struct cake_host *srchost = &b->hosts[flow->srchost];
 		struct cake_host *dsthost = &b->hosts[flow->dsthost];
+		u16 sum;
 		u16 host_load = 1;
 
 		if (!flow->set) {
@@ -1912,21 +1913,43 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		flow->set = CAKE_SET_SPARSE;
 		b->sparse_flow_count++;
 
-		if (cake_dsrc(q->flow_mode))
-			host_load = max(host_load, srchost->srchost_refcnt);
+		if (cake_dsrc(q->flow_mode)) {
+			srchost->srchost_sparse_flow_count++;
+			sum = srchost->srchost_sparse_flow_count +
+				srchost->srchost_bulk_flow_count;
+			host_load = max(host_load, sum);
+		}
 
-		if (cake_ddst(q->flow_mode))
-			host_load = max(host_load, dsthost->dsthost_refcnt);
+		if (cake_ddst(q->flow_mode)) {
+			dsthost->dsthost_sparse_flow_count++;
+			sum = dsthost->dsthost_sparse_flow_count +
+				dsthost->dsthost_bulk_flow_count;
+			host_load = max(host_load, sum);
+		}
 
 		flow->deficit = (b->flow_quantum *
 				 quantum_div[host_load]) >> 16;
 	} else if (flow->set == CAKE_SET_SPARSE_WAIT) {
+		struct cake_host *srchost = &b->hosts[flow->srchost];
+		struct cake_host *dsthost = &b->hosts[flow->dsthost];
+
 		/* this flow was empty, accounted as a sparse flow, but actually
 		 * in the bulk rotation.
 		 */
 		flow->set = CAKE_SET_BULK;
 		b->sparse_flow_count--;
 		b->bulk_flow_count++;
+
+		if (cake_dsrc(q->flow_mode)) {
+			srchost->srchost_sparse_flow_count--;
+			srchost->srchost_bulk_flow_count++;
+		}
+
+		if (cake_ddst(q->flow_mode)) {
+			dsthost->dsthost_sparse_flow_count--;
+			dsthost->dsthost_bulk_flow_count++;
+		}
+
 	}
 
 	if (q->buffer_used > q->buffer_max_used)
@@ -2097,23 +2120,8 @@ retry:
 	dsthost = &b->hosts[flow->dsthost];
 	host_load = 1;
 
-	if (cake_dsrc(q->flow_mode))
-		host_load = max(host_load, srchost->srchost_refcnt);
-
-	if (cake_ddst(q->flow_mode))
-		host_load = max(host_load, dsthost->dsthost_refcnt);
-
-	WARN_ON(host_load > CAKE_QUEUES);
-
 	/* flow isolation (DRR++) */
 	if (flow->deficit <= 0) {
-		/* The shifted prandom_u32() is a way to apply dithering to
-		 * avoid accumulating roundoff errors
-		 */
-		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
-				  (prandom_u32() >> 16)) >> 16;
-		list_move_tail(&flow->flowchain, &b->old_flows);
-
 		/* Keep all flows with deficits out of the sparse and decaying
 		 * rotations.  No non-empty flow can go into the decaying
 		 * rotation, so they can't get deficits
@@ -2122,6 +2130,17 @@ retry:
 			if (flow->head) {
 				b->sparse_flow_count--;
 				b->bulk_flow_count++;
+
+				if (cake_dsrc(q->flow_mode)) {
+					srchost->srchost_sparse_flow_count--;
+					srchost->srchost_bulk_flow_count++;
+				}
+
+				if (cake_ddst(q->flow_mode)) {
+					dsthost->dsthost_sparse_flow_count--;
+					dsthost->dsthost_bulk_flow_count++;
+				}
+
 				flow->set = CAKE_SET_BULK;
 			} else {
 				/* we've moved it to the bulk rotation for
@@ -2131,6 +2150,22 @@ retry:
 				flow->set = CAKE_SET_SPARSE_WAIT;
 			}
 		}
+
+		if (cake_dsrc(q->flow_mode))
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
+
+		if (cake_ddst(q->flow_mode))
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
+
+		WARN_ON(host_load > CAKE_QUEUES);
+
+		/* The shifted prandom_u32() is a way to apply dithering to
+		 * avoid accumulating roundoff errors
+		 */
+		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
+				  (prandom_u32() >> 16)) >> 16;
+		list_move_tail(&flow->flowchain, &b->old_flows);
+
 		goto retry;
 	}
 
@@ -2151,10 +2186,24 @@ retry:
 					       &b->decaying_flows);
 				if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
 					b->decaying_flow_count++;
 				} else if (flow->set == CAKE_SET_SPARSE ||
 					   flow->set == CAKE_SET_SPARSE_WAIT) {
 					b->sparse_flow_count--;
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_sparse_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_sparse_flow_count--;
+
 					b->decaying_flow_count++;
 				}
 				flow->set = CAKE_SET_DECAYING;
@@ -2162,16 +2211,28 @@ retry:
 				/* remove empty queue from the flowchain */
 				list_del_init(&flow->flowchain);
 				if (flow->set == CAKE_SET_SPARSE ||
-				    flow->set == CAKE_SET_SPARSE_WAIT)
+				    flow->set == CAKE_SET_SPARSE_WAIT) {
 					b->sparse_flow_count--;
-				else if (flow->set == CAKE_SET_BULK)
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_sparse_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_sparse_flow_count--;
+
+				} else if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
-				else
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
+				} else
 					b->decaying_flow_count--;
 
 				flow->set = CAKE_SET_NONE;
-				srchost->srchost_refcnt--;
-				dsthost->dsthost_refcnt--;
 			}
 			goto begin;
 		}
-- 
2.20.1

Re: [Cake] progress? dual-src/dsthost unfairness

[Toke Høiland-Jørgensen]

gamanakis@gmail.com writes:

>> On the contrary, even if a particular flow is sparse, the relevant
>> quantum calculation should involve the number of *bulk* flows
>> attached to the same host. Though there is possibly an argument for
>> making it the *sum* of the sparse and bulk flows, making it just the
>> sparse ones is wrong.
>
> I was about to point out that my assumption is obviously wrong.
> cake_enqueue() can still assign a packet to a bulk flow. Will try with
> the sum of the flows and report.

From a fairness perspective it doesn't really matter whether you count
the sparse flows or not. You use this for assigning a single quantum's
worth of initial deficit; any flow that actually needs fairness enforced
is going to be backlogged anyway, and the deficit increase in bulk state
is what matters for enforcing fairness.

What the initial quantum does is that it limits how big packet(s) a
sparse flow can send before it is demoted to bulk. There are certainly
some esoteric cases where this might matter (things like, can a DNS flow
get two small back-to-back packets through in one go); but this is going
to vary with the traffic conditions anyway, so I doubt it matters in
practice.

Given this, and given that the state tracking is already plenty
complicated, I'd suggest not counting per-host sparse flows at all, and
just using the bulk count. I'm pretty sure you'll get the same fairness
behaviour in this case.

Care to try that? :)

-Toke

[Cake] progress? dual-src/dsthost unfairness

[George Amanakis]

I tried Toke's and Jonathan's suggestion, dropping the
sparse_flow_count. Tthe results are the same (fairness).
In a hash collision in this patch the host_bulk_flow_count is not updated,
does this make sense?

-------------------8<-------------------
Client A:
Data file written to ./tcp_8down-2019-02-14T115248.702453.flent.gz.
Summary of tcp_8down test run at 2019-02-14 16:52:48.702453:

                             avg       median          # data pts
 Ping (ms) ICMP   :         0.78         0.69 ms              341
 TCP download avg :         6.00         5.81 Mbits/s         301
 TCP download sum :        48.00        46.51 Mbits/s         301
 TCP download::1  :         6.00         5.82 Mbits/s         297
 TCP download::2  :         5.99         5.82 Mbits/s         297
 TCP download::3  :         6.00         5.82 Mbits/s         297
 TCP download::4  :         6.00         5.82 Mbits/s         297
 TCP download::5  :         6.00         5.82 Mbits/s         297
 TCP download::6  :         6.00         5.82 Mbits/s         298
 TCP download::7  :         6.01         5.82 Mbits/s         297
 TCP download::8  :         6.00         5.82 Mbits/s         298
Data file written to ./tcp_1up-2019-02-14T115249.700445.flent.gz.
Summary of tcp_1up test run at 2019-02-14 16:52:49.700445:

                           avg       median          # data pts
 Ping (ms) ICMP :         0.79         0.69 ms              341
 TCP upload     :        47.69        46.33 Mbits/s         266



Client B:
Data file written to ./tcp_1down-2019-02-14T115250.817948.flent.gz.
Summary of tcp_1down test run at 2019-02-14 16:52:50.817948:

                           avg       median          # data pts
 Ping (ms) ICMP :         0.83         0.69 ms              341
 TCP download   :        47.82        46.57 Mbits/s         300
Data file written to ./tcp_8up-2019-02-14T115251.710755.flent.gz.
Summary of tcp_8up test run at 2019-02-14 16:52:51.710755:

                           avg       median          # data pts
 Ping (ms) ICMP :         0.78         0.69 ms              341
 TCP upload avg :         5.99         5.79 Mbits/s         301
 TCP upload sum :        47.88        46.30 Mbits/s         301
 TCP upload::1  :         5.98         5.81 Mbits/s         224
 TCP upload::2  :         5.99         5.82 Mbits/s         224
 TCP upload::3  :         5.98         5.77 Mbits/s         219
 TCP upload::4  :         5.98         5.82 Mbits/s         224
 TCP upload::5  :         5.99         5.77 Mbits/s         218
 TCP upload::6  :         5.99         5.77 Mbits/s         221
 TCP upload::7  :         5.98         5.77 Mbits/s         219
 TCP upload::8  :         5.99         5.77 Mbits/s         221
-------------------8<-------------------


---
 sch_cake.c | 84 +++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 55 insertions(+), 29 deletions(-)

diff --git a/sch_cake.c b/sch_cake.c
index d434ae0..ed3fbd9 100644
--- a/sch_cake.c
+++ b/sch_cake.c
@@ -146,8 +146,8 @@ struct cake_flow {
 struct cake_host {
 	u32 srchost_tag;
 	u32 dsthost_tag;
-	u16 srchost_refcnt;
-	u16 dsthost_refcnt;
+	u16 srchost_bulk_flow_count;
+	u16 dsthost_bulk_flow_count;
 };
 
 struct cake_heap_entry {
@@ -844,8 +844,6 @@ skip_hash:
 		 * queue, accept the collision, update the host tags.
 		 */
 		q->way_collisions++;
-		q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
-		q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
 		allocate_src = cake_dsrc(flow_mode);
 		allocate_dst = cake_ddst(flow_mode);
 found:
@@ -865,13 +863,12 @@ found:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 				i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].srchost_refcnt)
+				if (!q->hosts[outer_hash + k].srchost_bulk_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].srchost_tag = srchost_hash;
 found_src:
 			srchost_idx = outer_hash + k;
-			q->hosts[srchost_idx].srchost_refcnt++;
 			q->flows[reduced_hash].srchost = srchost_idx;
 		}
 
@@ -887,13 +884,12 @@ found_src:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 			     i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].dsthost_refcnt)
+				if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
 found_dst:
 			dsthost_idx = outer_hash + k;
-			q->hosts[dsthost_idx].dsthost_refcnt++;
 			q->flows[reduced_hash].dsthost = dsthost_idx;
 		}
 	}
@@ -1913,20 +1909,30 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		b->sparse_flow_count++;
 
 		if (cake_dsrc(q->flow_mode))
-			host_load = max(host_load, srchost->srchost_refcnt);
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
 
 		if (cake_ddst(q->flow_mode))
-			host_load = max(host_load, dsthost->dsthost_refcnt);
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
 
 		flow->deficit = (b->flow_quantum *
 				 quantum_div[host_load]) >> 16;
 	} else if (flow->set == CAKE_SET_SPARSE_WAIT) {
+		struct cake_host *srchost = &b->hosts[flow->srchost];
+		struct cake_host *dsthost = &b->hosts[flow->dsthost];
+
 		/* this flow was empty, accounted as a sparse flow, but actually
 		 * in the bulk rotation.
 		 */
 		flow->set = CAKE_SET_BULK;
 		b->sparse_flow_count--;
 		b->bulk_flow_count++;
+
+		if (cake_dsrc(q->flow_mode))
+			srchost->srchost_bulk_flow_count++;
+
+		if (cake_ddst(q->flow_mode))
+			dsthost->dsthost_bulk_flow_count++;
+
 	}
 
 	if (q->buffer_used > q->buffer_max_used)
@@ -2097,23 +2103,8 @@ retry:
 	dsthost = &b->hosts[flow->dsthost];
 	host_load = 1;
 
-	if (cake_dsrc(q->flow_mode))
-		host_load = max(host_load, srchost->srchost_refcnt);
-
-	if (cake_ddst(q->flow_mode))
-		host_load = max(host_load, dsthost->dsthost_refcnt);
-
-	WARN_ON(host_load > CAKE_QUEUES);
-
 	/* flow isolation (DRR++) */
 	if (flow->deficit <= 0) {
-		/* The shifted prandom_u32() is a way to apply dithering to
-		 * avoid accumulating roundoff errors
-		 */
-		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
-				  (prandom_u32() >> 16)) >> 16;
-		list_move_tail(&flow->flowchain, &b->old_flows);
-
 		/* Keep all flows with deficits out of the sparse and decaying
 		 * rotations.  No non-empty flow can go into the decaying
 		 * rotation, so they can't get deficits
@@ -2122,6 +2113,13 @@ retry:
 			if (flow->head) {
 				b->sparse_flow_count--;
 				b->bulk_flow_count++;
+
+				if (cake_dsrc(q->flow_mode))
+					srchost->srchost_bulk_flow_count++;
+
+				if (cake_ddst(q->flow_mode))
+					dsthost->dsthost_bulk_flow_count++;
+
 				flow->set = CAKE_SET_BULK;
 			} else {
 				/* we've moved it to the bulk rotation for
@@ -2131,6 +2129,22 @@ retry:
 				flow->set = CAKE_SET_SPARSE_WAIT;
 			}
 		}
+
+		if (cake_dsrc(q->flow_mode))
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
+
+		if (cake_ddst(q->flow_mode))
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
+
+		WARN_ON(host_load > CAKE_QUEUES);
+
+		/* The shifted prandom_u32() is a way to apply dithering to
+		 * avoid accumulating roundoff errors
+		 */
+		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
+				  (prandom_u32() >> 16)) >> 16;
+		list_move_tail(&flow->flowchain, &b->old_flows);
+
 		goto retry;
 	}
 
@@ -2151,6 +2165,13 @@ retry:
 					       &b->decaying_flows);
 				if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
 					b->decaying_flow_count++;
 				} else if (flow->set == CAKE_SET_SPARSE ||
 					   flow->set == CAKE_SET_SPARSE_WAIT) {
@@ -2164,14 +2185,19 @@ retry:
 				if (flow->set == CAKE_SET_SPARSE ||
 				    flow->set == CAKE_SET_SPARSE_WAIT)
 					b->sparse_flow_count--;
-				else if (flow->set == CAKE_SET_BULK)
+				else if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
-				else
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
+				} else
 					b->decaying_flow_count--;
 
 				flow->set = CAKE_SET_NONE;
-				srchost->srchost_refcnt--;
-				dsthost->dsthost_refcnt--;
 			}
 			goto begin;
 		}
-- 
2.20.1

Re: [Cake] progress? dual-src/dsthost unfairness

[Toke Høiland-Jørgensen]

George Amanakis <gamanakis@gmail.com> writes:

> I tried Toke's and Jonathan's suggestion, dropping the
> sparse_flow_count. Tthe results are the same (fairness).
> In a hash collision in this patch the host_bulk_flow_count is not updated,
> does this make sense?

Yeah, think so; it should be updated later when that flow transitions to
bulk.

Care to resend with a proper commit message + signed-off-by line (or
open a pull request on github)? I figure we can put it into the github
repo for a bit more testing before submitting a patch upstream :)

-Toke

[Cake] Make the dual modes fairer

[George Amanakis]

Host fairness does not work well with TCP flows in dual-srchost, and
dual-dsthost setup. The reason is that ACKs generated by TCP flows
are classified as sparse flows and affect flow isolation from other
hosts. Fix this by calculating host_load based only on the bulk flows
a host generates.

Reported-by: Pete Heist <peteheist@gmail.com>
Signed-off-by: George Amanakis <gamanakis@gmail.com>
---
 sch_cake.c | 84 +++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 55 insertions(+), 29 deletions(-)

diff --git a/sch_cake.c b/sch_cake.c
index d434ae0..ed3fbd9 100644
--- a/sch_cake.c
+++ b/sch_cake.c
@@ -146,8 +146,8 @@ struct cake_flow {
 struct cake_host {
 	u32 srchost_tag;
 	u32 dsthost_tag;
-	u16 srchost_refcnt;
-	u16 dsthost_refcnt;
+	u16 srchost_bulk_flow_count;
+	u16 dsthost_bulk_flow_count;
 };
 
 struct cake_heap_entry {
@@ -844,8 +844,6 @@ skip_hash:
 		 * queue, accept the collision, update the host tags.
 		 */
 		q->way_collisions++;
-		q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
-		q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
 		allocate_src = cake_dsrc(flow_mode);
 		allocate_dst = cake_ddst(flow_mode);
 found:
@@ -865,13 +863,12 @@ found:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 				i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].srchost_refcnt)
+				if (!q->hosts[outer_hash + k].srchost_bulk_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].srchost_tag = srchost_hash;
 found_src:
 			srchost_idx = outer_hash + k;
-			q->hosts[srchost_idx].srchost_refcnt++;
 			q->flows[reduced_hash].srchost = srchost_idx;
 		}
 
@@ -887,13 +884,12 @@ found_src:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 			     i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].dsthost_refcnt)
+				if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
 found_dst:
 			dsthost_idx = outer_hash + k;
-			q->hosts[dsthost_idx].dsthost_refcnt++;
 			q->flows[reduced_hash].dsthost = dsthost_idx;
 		}
 	}
@@ -1913,20 +1909,30 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		b->sparse_flow_count++;
 
 		if (cake_dsrc(q->flow_mode))
-			host_load = max(host_load, srchost->srchost_refcnt);
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
 
 		if (cake_ddst(q->flow_mode))
-			host_load = max(host_load, dsthost->dsthost_refcnt);
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
 
 		flow->deficit = (b->flow_quantum *
 				 quantum_div[host_load]) >> 16;
 	} else if (flow->set == CAKE_SET_SPARSE_WAIT) {
+		struct cake_host *srchost = &b->hosts[flow->srchost];
+		struct cake_host *dsthost = &b->hosts[flow->dsthost];
+
 		/* this flow was empty, accounted as a sparse flow, but actually
 		 * in the bulk rotation.
 		 */
 		flow->set = CAKE_SET_BULK;
 		b->sparse_flow_count--;
 		b->bulk_flow_count++;
+
+		if (cake_dsrc(q->flow_mode))
+			srchost->srchost_bulk_flow_count++;
+
+		if (cake_ddst(q->flow_mode))
+			dsthost->dsthost_bulk_flow_count++;
+
 	}
 
 	if (q->buffer_used > q->buffer_max_used)
@@ -2097,23 +2103,8 @@ retry:
 	dsthost = &b->hosts[flow->dsthost];
 	host_load = 1;
 
-	if (cake_dsrc(q->flow_mode))
-		host_load = max(host_load, srchost->srchost_refcnt);
-
-	if (cake_ddst(q->flow_mode))
-		host_load = max(host_load, dsthost->dsthost_refcnt);
-
-	WARN_ON(host_load > CAKE_QUEUES);
-
 	/* flow isolation (DRR++) */
 	if (flow->deficit <= 0) {
-		/* The shifted prandom_u32() is a way to apply dithering to
-		 * avoid accumulating roundoff errors
-		 */
-		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
-				  (prandom_u32() >> 16)) >> 16;
-		list_move_tail(&flow->flowchain, &b->old_flows);
-
 		/* Keep all flows with deficits out of the sparse and decaying
 		 * rotations.  No non-empty flow can go into the decaying
 		 * rotation, so they can't get deficits
@@ -2122,6 +2113,13 @@ retry:
 			if (flow->head) {
 				b->sparse_flow_count--;
 				b->bulk_flow_count++;
+
+				if (cake_dsrc(q->flow_mode))
+					srchost->srchost_bulk_flow_count++;
+
+				if (cake_ddst(q->flow_mode))
+					dsthost->dsthost_bulk_flow_count++;
+
 				flow->set = CAKE_SET_BULK;
 			} else {
 				/* we've moved it to the bulk rotation for
@@ -2131,6 +2129,22 @@ retry:
 				flow->set = CAKE_SET_SPARSE_WAIT;
 			}
 		}
+
+		if (cake_dsrc(q->flow_mode))
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
+
+		if (cake_ddst(q->flow_mode))
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
+
+		WARN_ON(host_load > CAKE_QUEUES);
+
+		/* The shifted prandom_u32() is a way to apply dithering to
+		 * avoid accumulating roundoff errors
+		 */
+		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
+				  (prandom_u32() >> 16)) >> 16;
+		list_move_tail(&flow->flowchain, &b->old_flows);
+
 		goto retry;
 	}
 
@@ -2151,6 +2165,13 @@ retry:
 					       &b->decaying_flows);
 				if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
 					b->decaying_flow_count++;
 				} else if (flow->set == CAKE_SET_SPARSE ||
 					   flow->set == CAKE_SET_SPARSE_WAIT) {
@@ -2164,14 +2185,19 @@ retry:
 				if (flow->set == CAKE_SET_SPARSE ||
 				    flow->set == CAKE_SET_SPARSE_WAIT)
 					b->sparse_flow_count--;
-				else if (flow->set == CAKE_SET_BULK)
+				else if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
-				else
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
+				} else
 					b->decaying_flow_count--;
 
 				flow->set = CAKE_SET_NONE;
-				srchost->srchost_refcnt--;
-				dsthost->dsthost_refcnt--;
 			}
 			goto begin;
 		}
-- 
2.20.1

Re: [Cake] progress? dual-src/dsthost unfairness

[Pete Heist]

Thanks for the work on this George! That’s a nice step forward for Cake’s fairness with bi-directional traffic. :)

I’ll try some tests when I get a chance...

> On Feb 14, 2019, at 7:02 PM, George Amanakis <gamanakis@gmail.com> wrote:
> 
> I tried Toke's and Jonathan's suggestion, dropping the
> sparse_flow_count. Tthe results are the same (fairness).
> In a hash collision in this patch the host_bulk_flow_count is not updated,
> does this make sense?
> 
> -------------------8<-------------------
> Client A:
> Data file written to ./tcp_8down-2019-02-14T115248.702453.flent.gz.
> Summary of tcp_8down test run at 2019-02-14 16:52:48.702453:
> 
>                             avg       median          # data pts
> Ping (ms) ICMP   :         0.78         0.69 ms              341
> TCP download avg :         6.00         5.81 Mbits/s         301
> TCP download sum :        48.00        46.51 Mbits/s         301
> TCP download::1  :         6.00         5.82 Mbits/s         297
> TCP download::2  :         5.99         5.82 Mbits/s         297
> TCP download::3  :         6.00         5.82 Mbits/s         297
> TCP download::4  :         6.00         5.82 Mbits/s         297
> TCP download::5  :         6.00         5.82 Mbits/s         297
> TCP download::6  :         6.00         5.82 Mbits/s         298
> TCP download::7  :         6.01         5.82 Mbits/s         297
> TCP download::8  :         6.00         5.82 Mbits/s         298
> Data file written to ./tcp_1up-2019-02-14T115249.700445.flent.gz.
> Summary of tcp_1up test run at 2019-02-14 16:52:49.700445:
> 
>                           avg       median          # data pts
> Ping (ms) ICMP :         0.79         0.69 ms              341
> TCP upload     :        47.69        46.33 Mbits/s         266
> 
> 
> 
> Client B:
> Data file written to ./tcp_1down-2019-02-14T115250.817948.flent.gz.
> Summary of tcp_1down test run at 2019-02-14 16:52:50.817948:
> 
>                           avg       median          # data pts
> Ping (ms) ICMP :         0.83         0.69 ms              341
> TCP download   :        47.82        46.57 Mbits/s         300
> Data file written to ./tcp_8up-2019-02-14T115251.710755.flent.gz.
> Summary of tcp_8up test run at 2019-02-14 16:52:51.710755:
> 
>                           avg       median          # data pts
> Ping (ms) ICMP :         0.78         0.69 ms              341
> TCP upload avg :         5.99         5.79 Mbits/s         301
> TCP upload sum :        47.88        46.30 Mbits/s         301
> TCP upload::1  :         5.98         5.81 Mbits/s         224
> TCP upload::2  :         5.99         5.82 Mbits/s         224
> TCP upload::3  :         5.98         5.77 Mbits/s         219
> TCP upload::4  :         5.98         5.82 Mbits/s         224
> TCP upload::5  :         5.99         5.77 Mbits/s         218
> TCP upload::6  :         5.99         5.77 Mbits/s         221
> TCP upload::7  :         5.98         5.77 Mbits/s         219
> TCP upload::8  :         5.99         5.77 Mbits/s         221
> -------------------8<-------------------
> 
> 
> ---
> sch_cake.c | 84 +++++++++++++++++++++++++++++++++++-------------------
> 1 file changed, 55 insertions(+), 29 deletions(-)
> 
> diff --git a/sch_cake.c b/sch_cake.c
> index d434ae0..ed3fbd9 100644
> --- a/sch_cake.c
> +++ b/sch_cake.c
> @@ -146,8 +146,8 @@ struct cake_flow {
> struct cake_host {
> 	u32 srchost_tag;
> 	u32 dsthost_tag;
> -	u16 srchost_refcnt;
> -	u16 dsthost_refcnt;
> +	u16 srchost_bulk_flow_count;
> +	u16 dsthost_bulk_flow_count;
> };
> 
> struct cake_heap_entry {
> @@ -844,8 +844,6 @@ skip_hash:
> 		 * queue, accept the collision, update the host tags.
> 		 */
> 		q->way_collisions++;
> -		q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
> -		q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
> 		allocate_src = cake_dsrc(flow_mode);
> 		allocate_dst = cake_ddst(flow_mode);
> found:
> @@ -865,13 +863,12 @@ found:
> 			}
> 			for (i = 0; i < CAKE_SET_WAYS;
> 				i++, k = (k + 1) % CAKE_SET_WAYS) {
> -				if (!q->hosts[outer_hash + k].srchost_refcnt)
> +				if (!q->hosts[outer_hash + k].srchost_bulk_flow_count)
> 					break;
> 			}
> 			q->hosts[outer_hash + k].srchost_tag = srchost_hash;
> found_src:
> 			srchost_idx = outer_hash + k;
> -			q->hosts[srchost_idx].srchost_refcnt++;
> 			q->flows[reduced_hash].srchost = srchost_idx;
> 		}
> 
> @@ -887,13 +884,12 @@ found_src:
> 			}
> 			for (i = 0; i < CAKE_SET_WAYS;
> 			     i++, k = (k + 1) % CAKE_SET_WAYS) {
> -				if (!q->hosts[outer_hash + k].dsthost_refcnt)
> +				if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count)
> 					break;
> 			}
> 			q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
> found_dst:
> 			dsthost_idx = outer_hash + k;
> -			q->hosts[dsthost_idx].dsthost_refcnt++;
> 			q->flows[reduced_hash].dsthost = dsthost_idx;
> 		}
> 	}
> @@ -1913,20 +1909,30 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
> 		b->sparse_flow_count++;
> 
> 		if (cake_dsrc(q->flow_mode))
> -			host_load = max(host_load, srchost->srchost_refcnt);
> +			host_load = max(host_load, srchost->srchost_bulk_flow_count);
> 
> 		if (cake_ddst(q->flow_mode))
> -			host_load = max(host_load, dsthost->dsthost_refcnt);
> +			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
> 
> 		flow->deficit = (b->flow_quantum *
> 				 quantum_div[host_load]) >> 16;
> 	} else if (flow->set == CAKE_SET_SPARSE_WAIT) {
> +		struct cake_host *srchost = &b->hosts[flow->srchost];
> +		struct cake_host *dsthost = &b->hosts[flow->dsthost];
> +
> 		/* this flow was empty, accounted as a sparse flow, but actually
> 		 * in the bulk rotation.
> 		 */
> 		flow->set = CAKE_SET_BULK;
> 		b->sparse_flow_count--;
> 		b->bulk_flow_count++;
> +
> +		if (cake_dsrc(q->flow_mode))
> +			srchost->srchost_bulk_flow_count++;
> +
> +		if (cake_ddst(q->flow_mode))
> +			dsthost->dsthost_bulk_flow_count++;
> +
> 	}
> 
> 	if (q->buffer_used > q->buffer_max_used)
> @@ -2097,23 +2103,8 @@ retry:
> 	dsthost = &b->hosts[flow->dsthost];
> 	host_load = 1;
> 
> -	if (cake_dsrc(q->flow_mode))
> -		host_load = max(host_load, srchost->srchost_refcnt);
> -
> -	if (cake_ddst(q->flow_mode))
> -		host_load = max(host_load, dsthost->dsthost_refcnt);
> -
> -	WARN_ON(host_load > CAKE_QUEUES);
> -
> 	/* flow isolation (DRR++) */
> 	if (flow->deficit <= 0) {
> -		/* The shifted prandom_u32() is a way to apply dithering to
> -		 * avoid accumulating roundoff errors
> -		 */
> -		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
> -				  (prandom_u32() >> 16)) >> 16;
> -		list_move_tail(&flow->flowchain, &b->old_flows);
> -
> 		/* Keep all flows with deficits out of the sparse and decaying
> 		 * rotations.  No non-empty flow can go into the decaying
> 		 * rotation, so they can't get deficits
> @@ -2122,6 +2113,13 @@ retry:
> 			if (flow->head) {
> 				b->sparse_flow_count--;
> 				b->bulk_flow_count++;
> +
> +				if (cake_dsrc(q->flow_mode))
> +					srchost->srchost_bulk_flow_count++;
> +
> +				if (cake_ddst(q->flow_mode))
> +					dsthost->dsthost_bulk_flow_count++;
> +
> 				flow->set = CAKE_SET_BULK;
> 			} else {
> 				/* we've moved it to the bulk rotation for
> @@ -2131,6 +2129,22 @@ retry:
> 				flow->set = CAKE_SET_SPARSE_WAIT;
> 			}
> 		}
> +
> +		if (cake_dsrc(q->flow_mode))
> +			host_load = max(host_load, srchost->srchost_bulk_flow_count);
> +
> +		if (cake_ddst(q->flow_mode))
> +			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
> +
> +		WARN_ON(host_load > CAKE_QUEUES);
> +
> +		/* The shifted prandom_u32() is a way to apply dithering to
> +		 * avoid accumulating roundoff errors
> +		 */
> +		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
> +				  (prandom_u32() >> 16)) >> 16;
> +		list_move_tail(&flow->flowchain, &b->old_flows);
> +
> 		goto retry;
> 	}
> 
> @@ -2151,6 +2165,13 @@ retry:
> 					       &b->decaying_flows);
> 				if (flow->set == CAKE_SET_BULK) {
> 					b->bulk_flow_count--;
> +
> +					if (cake_dsrc(q->flow_mode))
> +						srchost->srchost_bulk_flow_count--;
> +
> +					if (cake_ddst(q->flow_mode))
> +						dsthost->dsthost_bulk_flow_count--;
> +
> 					b->decaying_flow_count++;
> 				} else if (flow->set == CAKE_SET_SPARSE ||
> 					   flow->set == CAKE_SET_SPARSE_WAIT) {
> @@ -2164,14 +2185,19 @@ retry:
> 				if (flow->set == CAKE_SET_SPARSE ||
> 				    flow->set == CAKE_SET_SPARSE_WAIT)
> 					b->sparse_flow_count--;
> -				else if (flow->set == CAKE_SET_BULK)
> +				else if (flow->set == CAKE_SET_BULK) {
> 					b->bulk_flow_count--;
> -				else
> +
> +					if (cake_dsrc(q->flow_mode))
> +						srchost->srchost_bulk_flow_count--;
> +
> +					if (cake_ddst(q->flow_mode))
> +						dsthost->dsthost_bulk_flow_count--;
> +
> +				} else
> 					b->decaying_flow_count--;
> 
> 				flow->set = CAKE_SET_NONE;
> -				srchost->srchost_refcnt--;
> -				dsthost->dsthost_refcnt--;
> 			}
> 			goto begin;
> 		}
> -- 
> 2.20.1
> 
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] progress? dual-src/dsthost unfairness

[Jonathan Morton]

>> I tried Toke's and Jonathan's suggestion, dropping the
>> sparse_flow_count. Tthe results are the same (fairness).
>> In a hash collision in this patch the host_bulk_flow_count is not updated,
>> does this make sense?
> 
> Yeah, think so; it should be updated later when that flow transitions to
> bulk.
> 
> Care to resend with a proper commit message + signed-off-by line (or
> open a pull request on github)? I figure we can put it into the github
> repo for a bit more testing before submitting a patch upstream :)

The important thing is that the host_bulk_flow_count values match the actual bulk-status and host-reference properties assigned to each flow queue.  When a hash collision occurs, the bulk-status of the affected flow doesn't change but the hosts to which it refers might do.  In that case the host_bulk_flow_count values must be decremented on the old hosts and incremented on the new ones *if* the queue is in the bulk set.

 - Jonathan Morton

Re: [Cake] progress? dual-src/dsthost unfairness

[gamanakis]

> The important thing is that the host_bulk_flow_count values match the
> actual bulk-status and host-reference properties assigned to each flow
> queue.  When a hash collision occurs, the bulk-status of the affected flow
> doesn't change but the hosts to which it refers might do.  In that case
the
> host_bulk_flow_count values must be decremented on the old hosts and
> incremented on the new ones *if* the queue is in the bulk set.

Thanks for the clarification, I think I get it. Have to rewrite that part.

[Cake] Make the dual modes fairer

[George Amanakis]

Host fairness does not work well with TCP flows in dual-srchost and
dual-dsthost setup. The reason is that ACKs generated by TCP flows
are classified as sparse flows, and affect flow isolation from other
hosts. Fix this by calculating host_load based only on the bulk flows
a host generates. In a hash collision the host_bulk_flow_count values must
be decremented on the old hosts and incremented on the new ones *if* the
queue is in the bulk set.

Reported-by: Pete Heist <peteheist@gmail.com>
Signed-off-by: George Amanakis <gamanakis@gmail.com>
---
 sch_cake.c | 92 +++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 63 insertions(+), 29 deletions(-)

diff --git a/sch_cake.c b/sch_cake.c
index d434ae0..7ddbe37 100644
--- a/sch_cake.c
+++ b/sch_cake.c
@@ -146,8 +146,8 @@ struct cake_flow {
 struct cake_host {
 	u32 srchost_tag;
 	u32 dsthost_tag;
-	u16 srchost_refcnt;
-	u16 dsthost_refcnt;
+	u16 srchost_bulk_flow_count;
+	u16 dsthost_bulk_flow_count;
 };
 
 struct cake_heap_entry {
@@ -844,8 +844,10 @@ skip_hash:
 		 * queue, accept the collision, update the host tags.
 		 */
 		q->way_collisions++;
-		q->hosts[q->flows[reduced_hash].srchost].srchost_refcnt--;
-		q->hosts[q->flows[reduced_hash].dsthost].dsthost_refcnt--;
+		if (q->flows[outer_hash + k].set == CAKE_SET_BULK) {
+			q->hosts[q->flows[reduced_hash].srchost].srchost_bulk_flow_count--;
+			q->hosts[q->flows[reduced_hash].dsthost].dsthost_bulk_flow_count--;
+		}
 		allocate_src = cake_dsrc(flow_mode);
 		allocate_dst = cake_ddst(flow_mode);
 found:
@@ -865,13 +867,14 @@ found:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 				i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].srchost_refcnt)
+				if (!q->hosts[outer_hash + k].srchost_bulk_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].srchost_tag = srchost_hash;
 found_src:
 			srchost_idx = outer_hash + k;
-			q->hosts[srchost_idx].srchost_refcnt++;
+			if (q->flows[reduced_hash].set == CAKE_SET_BULK)
+				q->hosts[srchost_idx].srchost_bulk_flow_count++;
 			q->flows[reduced_hash].srchost = srchost_idx;
 		}
 
@@ -887,13 +890,14 @@ found_src:
 			}
 			for (i = 0; i < CAKE_SET_WAYS;
 			     i++, k = (k + 1) % CAKE_SET_WAYS) {
-				if (!q->hosts[outer_hash + k].dsthost_refcnt)
+				if (!q->hosts[outer_hash + k].dsthost_bulk_flow_count)
 					break;
 			}
 			q->hosts[outer_hash + k].dsthost_tag = dsthost_hash;
 found_dst:
 			dsthost_idx = outer_hash + k;
-			q->hosts[dsthost_idx].dsthost_refcnt++;
+			if (q->flows[reduced_hash].set == CAKE_SET_BULK)
+				q->hosts[dsthost_idx].dsthost_bulk_flow_count++;
 			q->flows[reduced_hash].dsthost = dsthost_idx;
 		}
 	}
@@ -1913,20 +1917,30 @@ static s32 cake_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 		b->sparse_flow_count++;
 
 		if (cake_dsrc(q->flow_mode))
-			host_load = max(host_load, srchost->srchost_refcnt);
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
 
 		if (cake_ddst(q->flow_mode))
-			host_load = max(host_load, dsthost->dsthost_refcnt);
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
 
 		flow->deficit = (b->flow_quantum *
 				 quantum_div[host_load]) >> 16;
 	} else if (flow->set == CAKE_SET_SPARSE_WAIT) {
+		struct cake_host *srchost = &b->hosts[flow->srchost];
+		struct cake_host *dsthost = &b->hosts[flow->dsthost];
+
 		/* this flow was empty, accounted as a sparse flow, but actually
 		 * in the bulk rotation.
 		 */
 		flow->set = CAKE_SET_BULK;
 		b->sparse_flow_count--;
 		b->bulk_flow_count++;
+
+		if (cake_dsrc(q->flow_mode))
+			srchost->srchost_bulk_flow_count++;
+
+		if (cake_ddst(q->flow_mode))
+			dsthost->dsthost_bulk_flow_count++;
+
 	}
 
 	if (q->buffer_used > q->buffer_max_used)
@@ -2097,23 +2111,8 @@ retry:
 	dsthost = &b->hosts[flow->dsthost];
 	host_load = 1;
 
-	if (cake_dsrc(q->flow_mode))
-		host_load = max(host_load, srchost->srchost_refcnt);
-
-	if (cake_ddst(q->flow_mode))
-		host_load = max(host_load, dsthost->dsthost_refcnt);
-
-	WARN_ON(host_load > CAKE_QUEUES);
-
 	/* flow isolation (DRR++) */
 	if (flow->deficit <= 0) {
-		/* The shifted prandom_u32() is a way to apply dithering to
-		 * avoid accumulating roundoff errors
-		 */
-		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
-				  (prandom_u32() >> 16)) >> 16;
-		list_move_tail(&flow->flowchain, &b->old_flows);
-
 		/* Keep all flows with deficits out of the sparse and decaying
 		 * rotations.  No non-empty flow can go into the decaying
 		 * rotation, so they can't get deficits
@@ -2122,6 +2121,13 @@ retry:
 			if (flow->head) {
 				b->sparse_flow_count--;
 				b->bulk_flow_count++;
+
+				if (cake_dsrc(q->flow_mode))
+					srchost->srchost_bulk_flow_count++;
+
+				if (cake_ddst(q->flow_mode))
+					dsthost->dsthost_bulk_flow_count++;
+
 				flow->set = CAKE_SET_BULK;
 			} else {
 				/* we've moved it to the bulk rotation for
@@ -2131,6 +2137,22 @@ retry:
 				flow->set = CAKE_SET_SPARSE_WAIT;
 			}
 		}
+
+		if (cake_dsrc(q->flow_mode))
+			host_load = max(host_load, srchost->srchost_bulk_flow_count);
+
+		if (cake_ddst(q->flow_mode))
+			host_load = max(host_load, dsthost->dsthost_bulk_flow_count);
+
+		WARN_ON(host_load > CAKE_QUEUES);
+
+		/* The shifted prandom_u32() is a way to apply dithering to
+		 * avoid accumulating roundoff errors
+		 */
+		flow->deficit += (b->flow_quantum * quantum_div[host_load] +
+				  (prandom_u32() >> 16)) >> 16;
+		list_move_tail(&flow->flowchain, &b->old_flows);
+
 		goto retry;
 	}
 
@@ -2151,6 +2173,13 @@ retry:
 					       &b->decaying_flows);
 				if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
 					b->decaying_flow_count++;
 				} else if (flow->set == CAKE_SET_SPARSE ||
 					   flow->set == CAKE_SET_SPARSE_WAIT) {
@@ -2164,14 +2193,19 @@ retry:
 				if (flow->set == CAKE_SET_SPARSE ||
 				    flow->set == CAKE_SET_SPARSE_WAIT)
 					b->sparse_flow_count--;
-				else if (flow->set == CAKE_SET_BULK)
+				else if (flow->set == CAKE_SET_BULK) {
 					b->bulk_flow_count--;
-				else
+
+					if (cake_dsrc(q->flow_mode))
+						srchost->srchost_bulk_flow_count--;
+
+					if (cake_ddst(q->flow_mode))
+						dsthost->dsthost_bulk_flow_count--;
+
+				} else
 					b->decaying_flow_count--;
 
 				flow->set = CAKE_SET_NONE;
-				srchost->srchost_refcnt--;
-				dsthost->dsthost_refcnt--;
 			}
 			goto begin;
 		}
-- 
2.20.1

Re: [Cake] Make the dual modes fairer

[Toke Høiland-Jørgensen]

George Amanakis <gamanakis@gmail.com> writes:

> Host fairness does not work well with TCP flows in dual-srchost and
> dual-dsthost setup. The reason is that ACKs generated by TCP flows
> are classified as sparse flows, and affect flow isolation from other
> hosts. Fix this by calculating host_load based only on the bulk flows
> a host generates. In a hash collision the host_bulk_flow_count values must
> be decremented on the old hosts and incremented on the new ones *if* the
> queue is in the bulk set.

Right, thanks! Pushed this to master; go forth and test, everyone! :)

-Toke