Subject: Re: [aqm] FQ-PIE kernel module implementation

From: "Fred Baker (fred)" <[email-masked]>
Date: Thu, 2 Jul 2015 22:42:39 +0000

> On Jun 10, 2015, at 1:56 AM, Polina Goltsman <[email-masked]> wrote:
> 
> Hello all,
> 
> If I understood the code correctly, in fq_pie there is a single PIE instance that controls all "fq" queues. In contrast in fq_codel there is a separate instance of codel for each queue. Is this the case? If it is, doesn't it contradict with original idea of fq_something where each queue is supposed to be managed by "its own" AQM?
> 
> Thanks in advance,
> Best Regards,
>   Polina

Sorry for the delay in getting back to you.

I'm not sure it makes sense to discuss fq_codel having a separate instance for each queue. It could, I suppose (by having a separate target delay value for each queue), but... the codel algorithm timestamps packets on enqueue and compares the difference between that timestamp and the current time against a common target delay value on dequeue. If that comparison shows that the induced latency is greater than some value, the packet is discarded with some probability. In the linux fq algorithm, or its counterpart in fq_codel, there is one queue for mice and zero or more separate queues for elephant flows. It is technically possible for a packet to be delayed inordinately long in the "mice" queue, if the interface is undergoing a long term overload, but that would be pretty unusual (can you say "DDOS"?). More probably, discards happen to the "elephant" data flows and their corresponding queues, as they are more likely to build a backlog.

The fq_pie algorithm operates similarly, with the exception that (like pie without fq) the entire pie algorithm happens at enqueue or in a background process. The background process determines the rate at which drops occur, and the algorithm at enqueue drops at that rate. This has the down side that it can happen to "mice" data flows with a little greater probability than fq_codel (it's not something one would tie to DDOS, it's simply the probability that any given arriving packet is selected). However, something that is true of codel without fq and true of any other AQM algorithm, if packets are selected for mark/drop with some probability,  packets from elephant flows are more likely to be selected simply because there are more of them.

> On 06/05/2015 12:06 AM, Hironori Okano -X (hokano - AAP3 INC at Cisco) wrote:
>> Hi all,
>> 
>> I’m Hironori Okano and Fred’s intern.
>> I’d like to let you know that I have implemented FQ-PIE as a linux kernel module “fq-pie" and iproute2 for fq-pie.
>> This was done in collaboration with others at Cisco including Fred Baker, Rong Pan, Bill Ver Steeg, and Preethi Natarajan.
>> 
>> The source codes are in my github repository. I attached patch file “fq-pie_patch.tar.gz” to this email also.
>> I’m using the latest linux kernel (git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git)
>> 
>> fq-pie kernel module
>> https://github.com/hironoriokano/fq-pie.git <https://github.com/hironoriokano/fq-pie.git>
>> 
>> iproute2 for fq-pie
>> https://github.com/hironoriokano/iproute2_fq-pie.git <https://github.com/hironoriokano/iproute2_fq-pie.git>
>> 
>> If you have any comments, please reach out to me.
>> 
>> Best regards,
>> 
>> Hironori Okano
>> [email-masked] <mailto:[email-masked]>
> _______________________________________________
> aqm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/aqm

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Fri, 03 Jul 2015 01:21:02 +0200

"Fred Baker (fred)" <[email-masked]> writes:

> I'm not sure it makes sense to discuss fq_codel having a separate
> instance for each queue.

Why not? It does. Completely separate state variables and everything...

> It could, I suppose (by having a separate target delay value for each
> queue), but... the codel algorithm timestamps packets on enqueue and
> compares the difference between that timestamp and the current time
> against a common target delay value on dequeue.

That much is true: all the queues *start out* the same. Doesn't mean
they're not separate...

> If that comparison shows that the induced latency is greater than some
> value, the packet is discarded with some probability.

The state variables (drop count) governing when packets are dropped *are*
separate for each queue, so you can have completely different drop rates
for different queues if they build queues at different rates.

> In the linux fq algorithm, or its counterpart in fq_codel, there is
> one queue for mice and zero or more separate queues for elephant
> flows.

Not so. There can be several 'mice' queues. In fact, each and every
queue starts out its life as a 'mice' queue (getting prioritised) before
being demoted to the second tier ('elephant' queues) after having
dequeued its first quantum (by default an MTU's worth of bytes).

> It is technically possible for a packet to be delayed inordinately
> long in the "mice" queue, if the interface is undergoing a long term
> overload, but that would be pretty unusual (can you say "DDOS"?). More
> probably, discards happen to the "elephant" data flows and their
> corresponding queues, as they are more likely to build a backlog.

The way fq_codel is implemented pretty much guarantees that packets are
not dropped from the mice flows: By definition, they are only mice flows
when dequeueing their first quantum of bytes, at which point the CoDel
state vars are zeroed. Which means that even if the first packet is
queued for longer than the target (which can easily happen at low
bandwidths), this will trigger the wait time for an interval before an
actual drop happens. So unless the mice flow has two consecutive
packets, totalling less than a quantum (MTU) bytes, of which the first
takes more than an interval to put on the wire, the mice flow is not
going to see a drop.

This is, as far as I can tell from your explanation, different than what
fq_pie does.

-Toke

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Thu, 2 Jul 2015 23:30:05 +0000

> On Jul 2, 2015, at 4:21 PM, Toke Høiland-Jørgensen <[email-masked]> wrote:
> 

OK, apologies for the misinformation.

In any event, the matter is not fundamental to fair queuing.

---

From: Fred Baker <[email-masked]>
Date: Fri, 3 Jul 2015 02:52:53 -0700

> On Jul 3, 2015, at 2:45 AM, Polina Goltsman <[email-masked]> wrote:
> 
> As I understand the FQ-Codel draft, it seems to be fundamental to FQ-Codel that each queue has separate state variables.
> So my question is: is it indeed fundamental ?

If you're asking whether it is fundamental to fair queuing, I'll recommend you start researching that question with RFC 970 and the articles in SIGCOMM and INFOCOMM on the topic circa 1988-1995 or so. Also take a look at Class-based Queing (aka CBQ) in the same timeframe. I think you'll find that FQ systems are not approached as collections of queues with different characteristics; they are collections of queues with essentially the same set of characteristics, using scheduling to make the queues share bandwidth in a manner similar to the Generalized Processor Sharing model. On the other hand, CBQ systems are systems with separate queues or classes for different sets of traffic, with different characteristics such as drop policy or target latency.

When we built the differentiated services model, we modeled a FQ subsystem as if it were a single queue in a larger CBQ system, We might, for example, have a FQ system for an AF class, but give EF priority over the entire FQ subsystem.

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Fri, 03 Jul 2015 12:16:40 +0200

Polina Goltsman <[email-masked]> writes:

> As I understand the FQ-Codel draft, it seems to be fundamental to
> FQ-Codel that each queue has separate state variables. So my question
> is: is it indeed fundamental ?

I suppose that becomes a matter of semantics: What exactly do you mean
by 'fundamental'. If you mean "an integral part of the current
algorithm", then yes. If you mean "it's unthinkable to build a similar
algorithm without the separate state variables" then no. I understand
Fred's comment to take the second interpretation. :)

-Toke

---

From: "Bless, Roland (TM)" <[email-masked]>
Date: Fri, 03 Jul 2015 13:40:39 +0200

Hi,

> Fred's comment to take the second interpretation. :)

I guess Polina's point was:
it is a question how "similar" two realizations of PIE would be
if one applies PIE per flow like in FQ-Codel or alternatively
(as proposed by FQ-PIE) FQ first and then PIE working on the
aggregated queue.
Was it a deliberate choice for the latter and if so, why?
It would be good to document this difference to FQ-Codel explicitly.

Regards,
 Roland

---

From: Polina Goltsman <[email-masked]>
Date: Fri, 3 Jul 2015 11:45:12 +0200

> In any event, the matter is not fundamental to fair queuing.
According to the code and Toke in FQ-Codel there are separate state 
variables for each queue,
whereas in FQ-PIE there is a single instance of state (see line 72-75 in 
sch_fq_pie.c
  <https://github.com/hironoriokano/fq-pie/blob/master/sch_fq_pie.c>). 
This is [should be] equivalent to a PIE queue
which uses FQ instead of FIFO as a child queue.

As I understand the FQ-Codel draft, it seems to be fundamental to 
FQ-Codel that each queue has separate state variables.
So my question is: is it indeed fundamental ?

P.S. comment on line sch_fq_pie.c  should probably be updated

---

From: Simon Barber <[email-masked]>
Date: Fri, 03 Jul 2015 10:55:11 -0700

One impact that come to mind is RTT fairness. A single AQM instance 
results in RTT unfairness (flows with higher RTT achieve lower bandwidth 
than flows with low RTT), whereas one AQM per queue results in RTT fairness.

Simon

---

From: Dave Taht <[email-masked]>
Date: Fri, 3 Jul 2015 10:56:27 -0700

> If you're asking whether it is fundamental to fair queuing, I'll recommend you start researching that question with RFC 970 and the articles in SIGCOMM and INFOCOMM on the topic circa 1988-1995 or…

I do not think how FQ-codel works is fundamental to FQ, rather, it is
an innovation that seems to work well in practice, with extremely low
overhead, leaving (mostly) untouched, request-response traffic like
dns, and other low rate traffic, but
while getting large bursts under control *rapidly*, yet allowing short
flows through, with no further configuration. So it is a set of queues
with different characteristics - which is why we ended up calling it
"Flow queueing", not fair queuing.

AQMs (like pie) traditionally rely on applying increasing amounts of
random drops/marks to a stream of packets, hoping to eventually pick
out the fattest flows and shoot at them, and yet modern traffic is A)
assymmetric, and B) bidirectional, and C) bursty, with large bursts
coming from various forms off TSO/GSO/GRO offloads, IW10 (and now quic
IW10+22 paced packets), and things like web browsers opening up many
connections simultaneously.

Any form of FQ reduces the impact of C) enormously. So much so that I
regard FQ as the biggest part of the answer to achieving reliably low
latency for all forms of traffic.

No AQM deals particularly well with B - if you have 20 acks vs 1 full
size MTU packet filling up the queue, it can take a lot longer for the
AQM to find an ideal drop rate - which is not, actually, ideal. Toke
did a preso on this on B and C.

As for A) - I am seeing a 12x1 ratio of down to up in my current cable
modem services, and this makes acks actually far more important and
painful than they ever have been before. It does not take a lot of fat
uplink traffic to start starving the downlink. Wifi and LTE are also
often painfully assymmetric.

FQ does impose some structure  - per packet fairness has problems in
some scenarios, byte fairness at the MTU size does not shoot at enough
acks, the compromise in deployed fq_codel systems at lower bandwidths
is a DRR quantum of 300 bytes. Cake uses peeling (to deal with up to
64k byte "packets" common now in consumer and server hardware), an 8
way set associative hash (much more flow isolation) and has a variable
quantum (presently), based on the number of extant flows, and has some
thoughts about the ideal BDP in the AQM, as the number of flows goes
up, and is smarter about quite a few things, and perhaps dumber about
others.

http://www.bufferbloat.net/projects/codel/wiki/Cake

I think FQ-pie is a good idea (aside from worrying about it
over-prioritizing millions of small flows). I lean still towards
stochastic methods (as in cake and fq_codel) along the edge. As for
the core, or where you have a lot of cpus on the ingress side, damned
if I know. As for wifi/wireless, we still have tons of work left to do
there.

On my benchmarks fq-pie, fq_codel, and cake all win pretty big. I
think cake is now more or less "better" than sqm-scripts was, and
handles more edge cases.

> When we built the differentiated services model, we modeled a FQ subsystem as if it were a single queue in a larger CBQ system, We might, for example, have a FQ system for an AF class, but give EF…

What we did with sqm-scripts (and other deployed fq_codel based
systems, like free.fr's) was to have 3 tiers of relative fq_codel
queues for priority, best effort, and background. That seems to work
pretty well. There is not a lot of effective use of classification in
my sample sets.

Cake is experimenting with various means of layering diffserv on top
of that, presently with a default of 4 fq_codel-ish queues,
We are collecting a great deal more stats on queue behavior and actual
loads in cake, now, example here:

http://pastebin.com/bX1HmDP6

Couple notes on that url:

Class 0 is just a name (background traffic goes here), class 1 is CS0,
classes 2 and 3 are higher prio than 1. We need a better name than
"class" as CS0 is actually in class 1....

" Sent 65725311796 bytes 52559409 pkt (dropped 11935, overlimits 0
requeues 449329) "

requeues are when the FQ system kicks in, which is about 44 times more
often than the AQM in this case.

as for drops vs marks - every machine on this campus that I have got
my hands on (which is only a few percent) has ecn enabled. Obviously,
that is not enough...

...

There are also weighted FQ systems (like qfq+ + pie or codel) under
development. (Actually you can prototype qfq+ codel/pie/red/whatever
today - we used QFQ + red/codel HEAVILY while evaluating various means
to make a hybrid fq+aqm system more lightweight, doing up "sfqred"
first, before codel arrived. A hope is to simplify QFQ+ and see how it
does, one day.

-- 
Dave Täht
worldwide bufferbloat report:
http://www.dslreports.com/speedtest/results/bufferbloat
And:
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast

---

From: Michael Welzl <[email-masked]>
Date: Fri, 3 Jul 2015 20:20:13 +0200

No.

> On 3. jul. 2015, at 19.55, Simon Barber <[email-masked]> wrote:
> 
> One impact that come to mind is RTT fairness. A single AQM instance results in RTT unfairness (flows with higher RTT achieve lower bandwidth than flows with low RTT), whereas one AQM per queue results in RTT fairness.
> 
> Simon
>

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Fri, 3 Jul 2015 18:22:20 +0000

> On Jul 3, 2015, at 10:56 AM, Dave Taht <[email-masked]> wrote:
> 
> development.

Actually, A WFQ system has been in Cisco product for 20 years, and I wrote one at a different company four years earlier. having FQ systems be weighted is pretty normal.

---

From: Dave Taht <[email-masked]>
Date: Fri, 3 Jul 2015 11:25:16 -0700

> Actually, A WFQ system has been in Cisco product for 20 years, and I wrote one at a different company four years earlier. having FQ systems be weighted is pretty normal.

yep! Sorry! What is the current limit on number of queues, however?

/me gets head out of linux sand

---

From: "Agarwal, Anil" <[email-masked]>
Date: Sat, 4 Jul 2015 20:12:58 +0000

Roland, Fred,

Here is a simple example to illustrate the differences between FQ-AQM with AQM per queue vs AQM per aggregate queue.

Let's take 2 flows, each mapped to separate queues in a FQ-AQM system.
	Link rate = 100 Mbps
	Flow 1 rate = 50 Mbps, source rate does not go over 50 Mbps
	Flow 2 rate >= 50 Mbps, adapts based on AQM.

FQ-Codel, AQM per queue:
	Flow 1 delay is minimal
	Flow 1 packet drops = 0
	Flow 2 delay is close to target value

FQ-Codel, AQM for aggregate queue:
	Does not work at all
	Packets are dequeued alternatively from queue 1 and queue 2
	Packets from queue 1 experience very small queuing delay
	Hence, CoDel does not enter dropping state, queue 2 is not controlled :(

FQ-PIE, AQM per queue:
	Flow 1 delay is minimal
	Flow 1 packet drops = 0
	Flow 2 delay is close to target value

FQ-PIE, AQM for aggregate queue:
	Flow 1 delay and queue 1 length are close to zero.
	Flow 2 delay is close to 2 * target_del :(
		qlen2 = target_del * aggregate_depart_rate
	Flow 1 experiences almost the same number of drops or ECNs as flow 2 :(
		Same drop probability and almost same packet rate for both flows
	(If flow 1 drops its rate because of packet drops or ECNs, the analysis gets slightly more complicated).

See if this makes sense.

If the analysis is correct, then it illustrates that flow behaviors are quite different
between AQM per queue and AQM per aggregate queue schemes.
In FQ-PIE for aggregate queue, 
	- The total number of queued bytes will slosh between 
	  queues depending on the nature and data rates of the flows.
	- Flows with data rates within their fair share value will experience 
	  non-zero packet drops (or ECN marks).
	- Flows that experience no queuing delay will increase queuing delay of other flows.
	- In general, the queuing delay for any given flow will not be close to target_delay and can be
	  much higher

Regards,
Anil

-----Original Message-----
From: aqm [mailto:[email-masked]] On Behalf Of Bless, Roland (TM)
Sent: Friday, July 03, 2015 7:41 AM
To: Toke Høiland-Jørgensen; Polina Goltsman
Cc: [email-masked]; Hironori Okano -X (hokano - AAP3 INC at Cisco); Fred Baker (fred); AQM IETF list
Subject: Re: [aqm] FQ-PIE kernel module implementation

Hi,

I guess Polina's point was:
it is a question how "similar" two realizations of PIE would be if one applies PIE per flow like in FQ-Codel or alternatively (as proposed by FQ-PIE) FQ first and then PIE working on the aggregated queue.
Was it a deliberate choice for the latter and if so, why?
It would be good to document this difference to FQ-Codel explicitly.

Regards,
 Roland

_______________________________________________
aqm mailing list
[email-masked]
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_aqm&d=AwIF-g&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=pcEVvl4qisljUGX7ogOyVICZ56p8s6lOuh8toIjEWzE&s=z1oQXxfgw7lLAkyQS7rwBUBlhihe3hD8IY623asr6vs&e=

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Mon, 6 Jul 2015 21:11:41 +0000

> On Jul 3, 2015, at 11:25 AM, Dave Taht <[email-masked]> wrote:
> 

At what point do we declare this a rathole and return to the algorithm?

---

From: "Bless, Roland (TM)" <[email-masked]>
Date: Tue, 07 Jul 2015 10:06:51 +0200

Hi,

thanks for your analysis. Indeed, Polina came up with
a similar analysis for an unresponsive UDP flow and
a TCP flow. Flow queueing can achieve link share fairness
despite the presence of unresponsive flows, but is ineffective
if the AQM is applied to the aggregate and not to the individual
flow queue. Polina used the FQ-PIE implementation
to verify this behavior (post will follow).

Regards,
 Roland

---

From: Polina Goltsman <[email-masked]>
Date: Tue, 7 Jul 2015 11:08:52 +0200

Hello all,

Here are my thoughts about interaction of AQM and fair-queueing system.

I think I will start with a figure. I have started a tcp flow with 
netperf, and 15 seconds later unresponsive UDP flow with iperf with a 
send rate a little bit above bottleneck link capacity. Both flows run 
together for 50 seconds.
This figure plots the throughput of UDP flow that was reported by iperf 
server. (Apparently netperf doesn't produce any output if throughput is 
below some value, so I can't plot TCP flow.).  The bottleneck is 100Mb/s 
and RTT is 100ms. All AQMs were configured with their default values and 
noecn flag.

Here is my example in theory. A link with capacity is C is shared 
between two flows - a non-application-limited TCP flow and unresponsive 
UDP flow with send rate 105%C. Both flows send max-sized packets, so 
round robin can be used instead of fair-queueing scheduler.

Per definition of max-min fair share both flows are supposed to get 50% 
of link capacity.

(1) Taildrop queues:
UDP packets will be dropped when its queue is full, TCP packets will be 
dropped when its queue is full. As long as there are packets in TCP flow 
queue, TCP should receive its fair share. ( As far as I understand, this 
depends on the size of the queue)

(2) AQM with state per queue:
Drop probability of UDP flow will always be non-zero and should 
stabilize around approximately 0.5.
Drop probability of TCP flow will be non-zero only when it starts 
sending above 50%C. Thus, while TCP recovers from packet drops, it 
should not receive another drop.

(3) AQM with state per aggregate:
UDP flow always creates a standing queue, so drop probability of 
aggregate is always non-zero. Let's call it /p_aqm/.
The share of TCP packets in the aggregate /p_tcp = TCP send rate / (TCP 
send rate + UDP send rate)/ and the probability of dropping a TCP packet 
is /p_aqm * p_tcp. /This probability is non-zero unless TCP doesn't send 
at all.

In (3) drop probability is at least different. I assume that it is 
larger than in (2), which will cause more packet drops for TCP flow, and 
as result the flow will reduce its sending rate below its fair share.

Regards,
Polina

---

From: Dave Taht <[email-masked]>
Date: Tue, 7 Jul 2015 09:30:27 -0700

On Tue, Jul 7, 2015 at 2:08 AM, Polina Goltsman <
[email-masked]> wrote:

> netperf, and 15 seconds later unresponsive UDP flow with iperf with a send
> rate a little bit above bottleneck link capacity. Both flows run together
> for 50 seconds.
> Here is my example in theory. A link with capacity is C is shared between
> two flows - a non-application-limited TCP flow and unresponsive UDP flow
> with send rate 105%C. Both flows send max-sized packets, so round robin can
> be used instead of fair-queueing scheduler.
>
> Per definition of max-min fair share both flows are supposed to get 50% of
> link capacity.
>
> (1) Taildrop queues:
Well, no. Tail drop will misbehave here also.

> Drop probability of UDP flow will always be non-zero and should stabilize
> around approximately 0.5.
> Drop probability of TCP flow will be non-zero only when it starts sending
> above 50%C. Thus, while TCP recovers from packet drops, it should not
> receive another drop.
>

Yes. You will get an interesting result if you ECN enable the udp flows and
ecn enable the aqm and fq-aqms, in that fq-codel presently has a very
compute intensive means of dealing with that (at least on initial
overload), that we have reduced the impact of a great deal in cake that may
well one day go into fq_codel.

Too many folk believe that once ECN is unleashed that everybody will play
nice. The game theory win for treating ecn is to treat it as an earlier
signal than drop, of course, and various folk are working on that. I would
also like it if tcps treated CE marks with drops also as an even stronger
signal of congestion. (cake drops, then marks, on serious overload)

Also, sch_fq, at least, has a large initial quantum, so in this scenario
small flows would at least get a bit of throughput. I don't know what
fq-pie will do.

> UDP flow always creates a standing queue, so drop probability of aggregate
> is always non-zero. Let's call it *p_aqm*.
> The share of TCP packets in the aggregate *p_tcp = TCP send rate / (TCP
> send rate + UDP send rate)* and the probability of dropping a TCP packet
> is *p_aqm * p_tcp. *This probability is non-zero unless TCP doesn't send
> at all.
>
> In (3) drop probability is at least different. I assume that it is larger
> than in (2), which will cause more packet drops for TCP flow, and as result
> the flow will reduce its sending rate below its fair share.
>
> Regards,
> Polina
>
>

---

From: "Agarwal, Anil" <[email-masked]>
Date: Tue, 7 Jul 2015 17:31:25 +0000

Polina, Roland,

This is good info.
So, here is a short summary of our analysis -
For FQ-PIE with aggregate-queue AQM -

1.      In the presence of unresponsive flows, FQ-PIE has similar properties as single-queue AQMs - the responsive flows are squeezed down to use leftover bandwidth, if any. FQ-AQM with per-queue AQM performs better.

2.      In the presence of flows that do not use their fairshare (temporarily or permanently), FQ-PIE has similar properties as single-queue AQMs - the flows, that do not use their fairshare, experience non-zero packet drops. FQ-AQM with per-queue AQM performs better.

3.      In the presence of flows that do not use their fairshare (temporarily or permanently), the queue size and queuing delay of flows that use their fairshare can grow above the desired target value.

#2 and #3 are probably not major issues - especially in a network bottleneck with a large number of diverse flows.
But it is worth pointing out and documenting these properties (somewhere).

Regards,
Anil

From: Polina Goltsman [mailto:[email-masked]]
Sent: Tuesday, July 07, 2015 5:09 AM
To: Bless, Roland (TM); Agarwal, Anil; Fred Baker (fred); Toke Høiland-Jørgensen
Cc: [email-masked]; Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: Re: [aqm] FQ-PIE kernel module implementation

Hello all,

I think I will start with a figure. I have started a tcp flow with netperf, and 15 seconds later unresponsive UDP flow with iperf with a send rate a little bit above bottleneck link capacity. Both flows run together for 50 seconds.
This figure plots the throughput of UDP flow that was reported by iperf server. (Apparently netperf doesn't produce any output if throughput is below some value, so I can't plot TCP flow.).  The bottleneck is 100Mb/s and RTT is 100ms. All AQMs were configured with their default values and noecn flag.

Here is my example in theory. A link with capacity is C is shared between two flows - a non-application-limited TCP flow and unresponsive UDP flow with send rate 105%C. Both flows send max-sized packets, so round robin can be used instead of fair-queueing scheduler.

Per definition of max-min fair share both flows are supposed to get 50% of link capacity.

(1) Taildrop queues:
UDP packets will be dropped when its queue is full, TCP packets will be dropped when its queue is full. As long as there are packets in TCP flow queue, TCP should receive its fair share. ( As far as I understand, this depends on the size of the queue)

(2) AQM with state per queue:
Drop probability of UDP flow will always be non-zero and should stabilize around approximately 0.5.
Drop probability of TCP flow will be non-zero only when it starts sending above 50%C. Thus, while TCP recovers from packet drops, it should not receive another drop.

(3) AQM with state per aggregate:
UDP flow always creates a standing queue, so drop probability of aggregate is always non-zero. Let's call it p_aqm.
The share of TCP packets in the aggregate p_tcp = TCP send rate / (TCP send rate + UDP send rate) and the probability of dropping a TCP packet is p_aqm * p_tcp. This probability is non-zero unless TCP doesn't send at all.

In (3) drop probability is at least different. I assume that it is larger than in (2), which will cause more packet drops for TCP flow, and as result the flow will reduce its sending rate below its fair share.

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Tue, 7 Jul 2015 19:04:48 +0000

Hi Anil,

One comment about the first point of your summary:

While FQ-PIE does drop TCP throughput compared to the fair share, a single-queue AQM will do even worse in the same scenario where the input rate of the UDP flow exceeds the output rate of the queue (no TCP throughput at all). I also suspect that, if the FQ-PIE experiment is repeated with a smaller RTT, closer to the PIE delay target, we may see some improvement for TCP (and more so with CUBIC vs. Reno).

FQ-AQM with per-queue state (including the case of a fixed tail-drop threshold per queue) does succeed in enforcing the fair share, but if the drop threshold is oversized compared to the flow RTT the price to pay is a large self-inflicted queuing delay.

It is true that any scheme that uses aggregate state (typically the overall buffer occupancy or queuing delay) to make drop decisions will lose flow isolation/protection to some extent. However, there are important quantitative differences that may emerge depending on the way the FQ-AQM uses the aggregate state.

Regards,

Andrea

From: aqm [mailto:[email-masked]] On Behalf Of Agarwal, Anil
Sent: Tuesday, July 07, 2015 1:31 PM
To: Polina Goltsman; Bless, Roland (TM); Fred Baker (fred); Toke Høiland-Jørgensen
Cc: [email-masked]; Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: Re: [aqm] FQ-PIE kernel module implementation

Polina, Roland,

This is good info.

Regards,
Anil

Cc: [email-masked]<mailto:[email-masked]>; Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Tue, 7 Jul 2015 22:32:35 +0000

FQ_PIE still uses rate estimation so the aggregated queue length would
give us more precise estimation of the latency. Actually, on second
thought, if we are going to afford the complexity of FQ, then timestamp
packets become trivial. If we use time stamp in FQ_PIE, all these concerns
would be gone. 

Having said that, drop probability can be easily tuned according to each
queue¹s queue length:
Drop_Queue_i = Queue_lenth_i/Total_Queue_length*drop_prob. This has shown
to work. Hiro¹s previous implementation of FQ_PIE has it and it is
working. Unfortunately, in his new version of FQ_PIE, this somehow gets
lost. 

He will update FQ_PIE accordingly. But I will vote for timestamp this time
as FQ is a lot more complicated than time stamp. If one decides to use FQ,
timestamp comes easy as well.

Thanks,

Rong

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Tue, 7 Jul 2015 22:58:43 +0000

Hi Rong,

In the ns2 version of (then) SFQ-PIE described in the May 2014 CableLabs document titled "ACTIVE QUEUE MANAGEMENT IN DOCSIS 3.X CABLE MODEMS", a different formula than the one you gave below was used to compute the drop probability of Queue i:

Drop_Queue_i = (Queue_lenth_i / Longest_Queue_length) * drop_prob  

i.e., the length of the longest queue was used at the denominator instead of the aggregate queue length (Total_Queue_Length).

I am curious about the reason that required that particular algorithmic change. 

Thank you,

Andrea

-----Original Message-----
From: aqm [mailto:[email-masked]] On Behalf Of Rong Pan (ropan)
Sent: Tuesday, July 07, 2015 6:33 PM
To: Polina Goltsman; Fred Baker (fred); Toke Høiland-Jørgensen
Cc: [email-masked]; Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: Re: [aqm] FQ-PIE kernel module implementation

Thanks,

Rong

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Tue, 7 Jul 2015 23:00:14 +0000

My bad, my memory has slipped… What you quote below is accurate….

Rong

On 7/7/15, 3:58 PM, "Francini, Andrea (Andrea)"
<[email-masked]> wrote:

>Hi Rong,
>
>In the ns2 version of (then) SFQ-PIE described in the May 2014 CableLabs
>document titled "ACTIVE QUEUE MANAGEMENT IN DOCSIS 3.X CABLE MODEMS", a
>different formula than the one you gave below was used to compute the
>drop probability of Queue i:
>
>i.e., the length of the longest queue was used at the denominator instead
>of the aggregate queue length (Total_Queue_Length).
>

---

From: "Agarwal, Anil" <[email-masked]>
Date: Wed, 8 Jul 2015 01:26:38 +0000

Hi Andrea,

I am quite sure FQ-PIE with aggregate queue AQM will have some advantages over PIE with a single queue.
Although, it is not much in this use case, described by Polina.
In this case, assume that the unresponsive traffic is at a rate just 1% over the link rate.
PIE will converge to a drop probability of around 1%.
The TCP connection will also experience ~1% packet drop rate.
At that drop rate, the TCP goodput will be quite small - ~160 kbps.

I suspect that the advantages will show up in cases with multiple responsive flows and
better fairness and delay properties across flows.

Also, we have not discussed any advantages of FQ-PIE with aggregate queue vs FQ-PIE with per-queue AQM.
I am sure there are some.
One thought is that the aggregation will result in less "noise" in the algorithm input variables and
more stability in the state variable values.
Imagine per-queue AQM having to deal with individual short-lived TCP connections and
slow starts for each connection and very few RTTs to adapt connection rates. How well will it
control delays and aggregate buffer usage? (Better than single queue with tail-drops, but
that is a very low bar). Perhaps, we will need help from techniques such as TCP Hybrid Slow Start.
Some analysis or simulations of FQ-PIE with aggregate queue vs FQ-PIE with per-queue AQM
would be useful.
Note that FQ-Codel with aggregate queue AQM is not a viable option.

Regards,
Anil

From: Francini, Andrea (Andrea) [mailto:[email-masked]]
Sent: Tuesday, July 07, 2015 3:05 PM
To: Agarwal, Anil; Polina Goltsman; Bless, Roland (TM); Fred Baker (fred); Toke Høiland-Jørgensen
Cc: [email-masked]; Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: RE: [aqm] FQ-PIE kernel module implementation

Hi Anil,

Regards,

Andrea

Polina, Roland,

This is good info.

Regards,
Anil

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Agarwal, Anil" <[email-masked]>
Date: Wed, 8 Jul 2015 08:06:24 +0000

Rong,

Can you please elaborate on how packet timestamps would be used with FQ-PIE?
It is not obvious.

Is there a written description of FQ-PIE?  Does it describe use of timestamps as well?

For equation -
	Drop_Queue_i = (Queue_lenth_i / Longest_Queue_length) * drop_prob
is there a fast algorithm for computing Longest_Queue_length for large number of queues?

Thanks,
Anil

-----Original Message-----
From: aqm [mailto:[email-masked]] On Behalf Of Rong Pan (ropan)
Sent: Tuesday, July 07, 2015 7:00 PM
To: Francini, Andrea (Andrea); Polina Goltsman; Fred Baker (fred); Toke Høiland-Jørgensen
Cc: [email-masked]; Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: Re: [aqm] FQ-PIE kernel module implementation

My bad, my memory has slipped. What you quote below is accurate..

Rong

>I am curious about the reason that required that particular algorithmic

>change. 

>Cc: [email-masked]; Hironori Okano -X (hokano - AAP3

>INC at Cisco); AQM IETF list

>>>> On Jul 2, 2015, at 4:21 PM, Toke Høiland-Jørgensen <[email-masked]>

>>>>wrote:

>>>> This is, as far as I can tell from your explanation, different than

>>>>what

>>  <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_hironoriokano_fq-2Dpie_blob_master_sch-5Ffq-5Fpie.c&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEBMToS4eye5KU&s=90jYjRUO0hcRiGb1Kd3owxwftY2Pd3WrK2Hs-sq619E&e= >).

>https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEBMToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e= 

_______________________________________________
aqm mailing list
[email-masked]
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEBMToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=

---

From: Polina Goltsman <[email-masked]>
Date: Wed, 8 Jul 2015 10:47:38 +0200

Anil,

I can't understand what you mean in (3). Each flow's share depends on 
the presence of all other flows. If a fair queueing algorithm calculates 
the share of the flow to be X, it is then for congestion control and/or 
AQM to ensure that the sender sends with rate X. Queue size/delay will 
grow in the process, since  AQM uses them as an indicator that the flow 
sends above its share.

In (1) and (2) on the other hand the AQM per aggregate forces flows to 
not receive their fair share, which is a problem.

Regards,
Polina

On 07/07/2015 07:31 PM, Agarwal, Anil wrote:
> 1.In the presence of unresponsive flows, FQ-PIE has similar properties 
> as single-queue AQMs - the responsive flows are squeezed down to use 
> leftover bandwidth, if any. FQ-AQM with per-queue AQM performs better.
>
> 2.In the presence of flows that do not use their fairshare 
> (temporarily or permanently), FQ-PIE has similar properties as 
> single-queue AQMs - the flows, that do not use their fairshare, 
> experience non-zero packet drops. FQ-AQM with per-queue AQM performs 
> better.
>
> 3.In the presence of flows that do not use their fairshare 
> (temporarily or permanently), the queue size and queuing delay of 
> flows that use their fairshare can grow above the desired target value.
>
> #2 and #3 are probably not major issues - especially in a network 
> bottleneck with a large number of diverse flows.
>
> *From:*Polina Goltsman [mailto:[email-masked]]
> *Sent:* Tuesday, July 07, 2015 5:09 AM
> *To:* Bless, Roland (TM); Agarwal, Anil; Fred Baker (fred); Toke 
> Høiland-Jørgensen
> *Cc:* [email-masked]; Hironori Okano -X (hokano - 
> AAP3 INC at Cisco); AQM IETF list
> *Subject:* Re: [aqm] FQ-PIE kernel module implementation
>
> Hello all,
>
> This figure plots the throughput of UDP flow that was reported by 
> iperf server. (Apparently netperf doesn't produce any output if 
> throughput is below some value, so I can't plot TCP flow.).  The 
> bottleneck is 100Mb/s and RTT is 100ms. All AQMs were configured with 
> their default values and noecn flag.
>
>
> between two flows - a non-application-limited TCP flow and 
> unresponsive UDP flow with send rate 105%C. Both flows send max-sized 
> packets, so round robin can be used instead of fair-queueing scheduler.
>
> UDP packets will be dropped when its queue is full, TCP packets will 
> be dropped when its queue is full. As long as there are packets in TCP 
> flow queue, TCP should receive its fair share. ( As far as I 
> understand, this depends on the size of the queue)
>
> The share of TCP packets in the aggregate /p_tcp = TCP send rate / 
> (TCP send rate + UDP send rate)/ and the probability of dropping a TCP 
> packet is /p_aqm * p_tcp. /This probability is non-zero unless TCP 
> doesn't send at all.
>
> larger than in (2), which will cause more packet drops for TCP flow, 
> and as result the flow will reduce its sending rate below its fair share.
>
> Regards,
> Polina
>

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Wed, 8 Jul 2015 17:51:55 +0000

Hi Anil,

I have run a few experiments in my ns2 environment, using my own FQ version of a rather old PIE module. I used 16ms for both the tUpdate and qdelay_ref parameters.

DISCLAIMER: Please do not take the results as indicative of the actual FQ-PIE (and plain PIE) behavior, but rather of a multi-queue (and single-queue) AQM scheme that instantiates some of the PIE principles.

The link has 100Mbps capacity. The buffer size is rather large (at least 6x BDP) so that buffer overflow occurs only if the AQM drop decisions are not sufficient to keep the queue length from growing uncontrolled.

The UDP traffic comes in at the constant rate of 101 Mbps. TCP traffic is from a CUBIC source (also a very old ns2 model). I used 50ms and 100ms RTT for the TCP traffic.

The experiments run for 300s of simulated time. The collection of statistics starts at time 100s, so all averages are computed over a 200s period. The scenario may be far from realistic, but it helps highlight basic properties of the AQM scheme.

With 50ms RTT, the CUBIC flow gets 32.3% of its 50Mbps fair share (2.15% with plain PIE -  a 15x drop). The PIE drop probability (which applies directly to UDP traffic, while it is scaled down for the shorter TCP queue) settles around 16%.
With 100ms RTT, the CUBIC flow gets 23.6% of its 50Mbps fair share (1.33% with plain PIE). The PIE drop probability also settles around 16%, but with wider oscillations.

The plot in attachment shows a 25s window in the evolution of the aggregate queue length and congestion window size for the CUBIC source (100ms RTT case). The 100% dashed line is for the cwnd size that yields 100% of the fair share.

The drop probability is much larger than 1%. This is because the TCP traffic adds to the 101% input load of UDP. The queue length oscillates at every high frequency, loosely modulated by the CUBIC cwnd. As soon as the length of the CUBIC queue accumulates a few units, the TCP drop probability given by the FQ-PIE formula becomes sufficiently large to cause the loss of a TCP packet and push the TCP queue back to zero occupancy.

TCP traffic suffers because the TCP drop probability is tied to the overall buffer occupancy, which UDP keeps trying to increase. We agree that it would be much better if the drop probability was defined exclusively by the state of the TCP queue, but this is not easy to realize in practice, at least according to the explanation given in the May 2014 CableLabs document for the decision made there to use aggregate state for setting the drop probability  (the explanation overlaps in part with the issues you identify in your message). The aggregate approach could be improved with a better formula for the per-queue drop probability, but I doubt it will be easy to find one that fits well all use cases and types of TCP source.

Regards,

Andrea

From: Agarwal, Anil [mailto:[email-masked]]
Sent: Tuesday, July 07, 2015 9:27 PM
To: Francini, Andrea (Andrea); Polina Goltsman; Bless, Roland (TM); Fred Baker (fred); Toke Høiland-Jørgensen
Cc: Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: RE: [aqm] FQ-PIE kernel module implementation

Hi Andrea,

Regards,
Anil

Hi Anil,

Regards,

Andrea

Polina, Roland,

This is good info.

Regards,
Anil

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Wed, 8 Jul 2015 18:16:50 +0000

We can take the timestamp values to figure out latency and plug into PIE’s
basic control law. 

p = p + alpha*(est_del-target_del) + beta*(est_del-est_del_old);

We have tried this implementation before for comparison purpose. This
would react slowly than deriving latency for queue length because latency
value is only available when a packet leaves a queue. But it would remove
any inaccuracy in calculating the latency. For PIE, we go for rate
estimation as we think timestamping packets in hardware would be hard.
FQ_PIE is a different story. If someone affords to implement FQ, then
timestamping would not be too much of an overhead.

The other twist works as well. We will experiment and decide what we want
to do.

Thanks,

Rong

On 7/8/15, 1:06 AM, "Agarwal, Anil" <[email-masked]> wrote:

>>><https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_hironor
>>>iokano_fq-2Dpie_blob_master_sch-5Ffq-5Fpie.c&d=AwIGog&c=jcv3orpCsv7C4ly8
>>>-ubDob57ycZ4jvhoYZNDBA06fPk&r=FyvaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq
>>>4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEBMToS4eye5KU&s=90jYjRUO0hcRiGb1Kd3owx
>>>wftY2Pd3WrK2Hs-sq619E&e= >).
>
>>https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman
>>_listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=Fy
>>vaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJ
>>JEBMToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=
>
>
>
>https://urldefense.proofpoint.com/v2/url?u=https-3A__www.ietf.org_mailman_
>listinfo_aqm&d=AwIGog&c=jcv3orpCsv7C4ly8-ubDob57ycZ4jvhoYZNDBA06fPk&r=Fyva
>klKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJJEB
>MToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=

---

From: "Agarwal, Anil" <[email-masked]>
Date: Wed, 8 Jul 2015 20:39:11 +0000

Rong,

Since the timestamp discussion came up in the context of FQ-PIE, it is not clear how we would use timestamp-based delay values measured across many queues to perform the computation of p. The delays experienced in different queues can have vastly different values.
FQ-PIE has a single instance of PIE across all queues and a single value of p. How do you compute est_del from the various delay values from multiple queues?
Or are you thinking of using a separate PIE instance per queue?
Can you please elaborate?

Thanks,
Anil

-----Original Message-----
From: Rong Pan (ropan) [mailto:[email-masked]] 
Sent: Wednesday, July 08, 2015 2:17 PM
To: Agarwal, Anil; Francini, Andrea (Andrea); Polina Goltsman; Fred Baker (fred); Toke Høiland-Jørgensen
Cc: [email-masked]; Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: Re: [aqm] FQ-PIE kernel module implementation

We can take the timestamp values to figure out latency and plug into PIE's basic control law. 

We have tried this implementation before for comparison purpose. This would react slowly than deriving latency for queue length because latency value is only available when a packet leaves a queue. But it would remove any inaccuracy in calculating the latency. For PIE, we go for rate estimation as we think timestamping packets in hardware would be hard.
FQ_PIE is a different story. If someone affords to implement FQ, then timestamping would not be too much of an overhead.

The other twist works as well. We will experiment and decide what we want to do.

Thanks,

Rong

On 7/8/15, 1:06 AM, "Agarwal, Anil" <[email-masked]> wrote:

>	Drop_Queue_i = (Queue_lenth_i / Longest_Queue_length) * drop_prob is 
>there a fast algorithm for computing Longest_Queue_length for large 
>number of queues?
>
>Thanks,
>Anil
>
>>vaklKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkr
>>eFJ JEBMToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=
>
>
>
>klKYrHaSCPjbBTdviWIW9uSbnxdNSheSGz1Jvq4&m=ZhwYVG7trmH21ngvxzmFV1-mkreFJ
>JEB MToS4eye5KU&s=hAK-RY-wfp0zIHzoazmmKJ03TrFqQ2TM9SqbDo_ku3Q&e=

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Wed, 8 Jul 2015 21:01:00 +0000

Yes, if we use timestamp, then we can have separate PIE per queue.

Rong

On 7/8/15, 1:39 PM, "Agarwal, Anil" <[email-masked]> wrote:

>Rong,
>
>Since the timestamp discussion came up in the context of FQ-PIE, it is
>not clear how we would use timestamp-based delay values measured across
>many queues to perform the computation of p. The delays experienced in
>different queues can have vastly different values.
>FQ-PIE has a single instance of PIE across all queues and a single value
>of p. How do you compute est_del from the various delay values from
>multiple queues?

---

From: "Agarwal, Anil" <[email-masked]>
Date: Thu, 9 Jul 2015 09:31:21 +0000

Andrea,

This is good info.

Slightly surprising how CUBIC manages to keep cwnd large in the presence of such a large packet discard probability.

Might be useful to try and compare with the per-queue packet drop probability algorithm mentioned in the DOCSIS report.

Regards,
Anil

Sent: Wednesday, July 08, 2015 1:52 PM

Hi Anil,

Regards,

Andrea

Hi Andrea,

Regards,
Anil

Hi Anil,

Regards,

Andrea

Polina, Roland,

This is good info.

Regards,
Anil

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Thu, 9 Jul 2015 13:26:48 +0000

The packet drop rate is very different for the TCP and UDP queues: 0.017% and 12.7% are the values measured in the 100ms RTT case (with PIE drop probability at about 16%). The random generator for the drop probability would indeed drop at the 16% rate, but whenever a TCP packet arrives at the FQ-PIE queue (10.4% of the cases), the drop probability is scaled down quite drastically. In other words, the full 16% packet drop probability only applies to a fraction of the incoming packets, which yields a lower total packet drop rate (11.3%).This is an intrinsic property of FQ-PIE with drop probability derived from aggregate state: the effective drop rate is systematically lower than the drop probability set by the algorithm, because the scaling by queue length ratio produces a drop probability value that is never larger than the one produced by the control equation. I wonder if this discrepancy should be a reason for concern from a control-theory perspective.

I also wonder if there is an equation that accurately relates the long-term CUBIC drop rate to the long-term CUBIC throughput when the CUBIC drop probability oscillates with the CUBIC queue length.

Regards,

Andrea

Sent: Thursday, July 09, 2015 5:31 AM

Andrea,

This is good info.

Regards,
Anil

Hi Anil,

Regards,

Andrea

Hi Andrea,

Regards,
Anil

Hi Anil,

Regards,

Andrea

Polina, Roland,

This is good info.

Regards,
Anil

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Rong Pan (ropan)" <[email-masked]>
Date: Thu, 9 Jul 2015 17:33:57 +0000

The drop probability does not agree with the drop rate is highly possible as it is in the case here. However, the power of the PI controller would make sure that the latency is in check. The drop probability’s exact value does not matter as long as the final drop rate is correct so that the queue/latency is stable.

CUBIC is kinda magic. I don’t know whether there is theoretical study about its behavior. If so, I would like to know and study.

Thanks,

Rong

From: aqm <[email-masked]<mailto:[email-masked]>> on behalf of "Francini, Andrea (Andrea)" <[email-masked]<mailto:[email-masked]>>
Date: Thursday, July 9, 2015 at 6:26 AM
To: "Agarwal, Anil" <[email-masked]<mailto:[email-masked]>>, Polina Goltsman <[email-masked]<mailto:[email-masked]>>, "Bless, Roland (TM)" <[email-masked]<mailto:[email-masked]>>, "Fred Baker (fred)" <[email-masked]<mailto:[email-masked]>>, Toke Høiland-Jørgensen <[email-masked]<mailto:[email-masked]>>
Cc: "Hironori Okano -X (hokano - AAP3 INC at Cisco)" <[email-masked]<mailto:[email-masked]>>, AQM IETF list <[email-masked]<mailto:[email-masked]>>
Subject: Re: [aqm] FQ-PIE kernel module implementation

Regards,

Andrea

Andrea,

This is good info.

Regards,
Anil

Hi Anil,

With 50ms RTT, the CUBIC flow gets 32.3% of its 50Mbps fair share (2.15% with plain PIE –  a 15x drop). The PIE drop probability (which applies directly to UDP traffic, while it is scaled down for the shorter TCP queue) settles around 16%.
With 100ms RTT, the CUBIC flow gets 23.6% of its 50Mbps fair share (1.33% with plain PIE). The PIE drop probability also settles around 16%, but with wider oscillations.

Regards,

Andrea

Hi Andrea,

One thought is that the aggregation will result in less “noise” in the algorithm input variables and

Regards,
Anil

Hi Anil,

Regards,

Andrea

Polina, Roland,

This is good info.

Regards,
Anil

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Agarwal, Anil" <[email-masked]>
Date: Thu, 9 Jul 2015 18:29:42 +0000

Andrea,

Can you please clarify, whether in your simulation, there is a common drop probability applied to all queues or
is the drop probability explicitly scaled by queue length, as described in the DOCSIS report?
"Then, at enqueue time, the drop probability applied to a packet destined for queue X
is scaled based on the ratio of the queue depth
of queue X and the queue depth of the current largest queue."

The latter would help explain the observed packet drop rates.

Anil

From: Rong Pan (ropan) [mailto:[email-masked]]
Sent: Thursday, July 09, 2015 1:34 PM
To: Francini, Andrea (Andrea); Agarwal, Anil; Polina Goltsman; Bless, Roland (TM); Fred Baker (fred); Toke Høiland-Jørgensen
Cc: Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: Re: [aqm] FQ-PIE kernel module implementation

The drop probability does not agree with the drop rate is highly possible as it is in the case here. However, the power of the PI controller would make sure that the latency is in check. The drop probability's exact value does not matter as long as the final drop rate is correct so that the queue/latency is stable.

CUBIC is kinda magic. I don't know whether there is theoretical study about its behavior. If so, I would like to know and study.

Thanks,

Rong

Regards,

Andrea

Andrea,

This is good info.

Regards,
Anil

Hi Anil,

Regards,

Andrea

Hi Andrea,

Regards,
Anil

Hi Anil,

Regards,

Andrea

Polina, Roland,

This is good info.

Regards,
Anil

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher

---

From: "Francini, Andrea (Andrea)" <[email-masked]>
Date: Thu, 9 Jul 2015 21:36:37 +0000

In my simulation model, the drop probability is scaled just as described in the DOCSIS document and in Rong's revised formula.

Andrea

From: Agarwal, Anil [mailto:[email-masked]]
Sent: Thursday, July 09, 2015 2:30 PM
To: Francini, Andrea (Andrea); Rong Pan (ropan); Polina Goltsman; Bless, Roland (TM); Fred Baker (fred); Toke Høiland-Jørgensen
Cc: Hironori Okano -X (hokano - AAP3 INC at Cisco); AQM IETF list
Subject: RE: [aqm] FQ-PIE kernel module implementation

Andrea,

Anil

Thanks,

Rong

Regards,

Andrea

Andrea,

This is good info.

Regards,
Anil

Hi Anil,

Regards,

Andrea

Hi Andrea,

Regards,
Anil

Hi Anil,

Regards,

Andrea

Polina, Roland,

This is good info.

Regards,
Anil

Hello all,

(1) Taildrop queues:

Regards,
Polina

Hi,

Regards,

 Roland

Roland, Fred,

   Link rate = 100 Mbps

FQ-Codel, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

   Does not work at all

FQ-PIE, AQM per queue:

   Flow 1 delay is minimal

   Flow 1 packet drops = 0

See if this makes sense.

     much higher