Subject: [aqm] Fwd: New Version Notification for draft-baker-aqm-sfq-implementation-00.txt

From: "Fred Baker (fred)" <[email-masked]>
Date: Fri, 13 Jun 2014 22:07:50 +0000

I’d be interested in comments on this.

> From: <[email-masked]>
> Subject: New Version Notification for draft-baker-aqm-sfq-implementation-00.txt
> Date: June 13, 2014 at 2:52:07 PM PDT
> To: Fred Baker <[email-masked]>, Rong Pan <[email-masked]>, Fred Baker <[email-masked]>, Rong Pan <[email-masked]>
> 
> 
> A new version of I-D, draft-baker-aqm-sfq-implementation-00.txt
> has been successfully submitted by Fred Baker and posted to the
> IETF repository.
> 
> Name:		draft-baker-aqm-sfq-implementation
> Revision:	00
> Title:		On Queuing, Marking, and Dropping
> Document date:	2014-06-13
> Group:		Individual Submission
> Pages:		14
> URL:            http://www.ietf.org/internet-drafts/draft-baker-aqm-sfq-implementation-00.txt
> Status:         https://datatracker.ietf.org/doc/draft-baker-aqm-sfq-implementation/
> Htmlized:       http://tools.ietf.org/html/draft-baker-aqm-sfq-implementation-00
> 
> 
> Abstract:
>   This note discusses implementation strategies for coupled queuing and
>   mark/drop algorithms.
> 
> 
> 
> 
> Please note that it may take a couple of minutes from the time of submission
> until the htmlized version and diff are available at tools.ietf.org.
> 
> The IETF Secretariat
>

---

From: Dave Taht <[email-masked]>
Date: Fri, 13 Jun 2014 16:04:44 -0700

Really excellent, Fred, on a first reading!

nit 1) drops tend to happen in bursts on a tail drop queue (not
necessarily on this bottleneck, but elsewhere on the network). By
breaking up flows into sequences of distinctly different packets, this
applies minor damage to more flows, instead of severe damage to one
flow.

I don't know where to put this or how to express it anywhere near as
well as you expressed everything else.

2) weighted FQ algos like QFQ and WFQ are interesting from a
take-advantage-of-diffserv perspective. I keep hoping to get a
simplified and more fq_codel-like implementation of QFQ, in
particular.

3) sch_fq is a *perfect* fq algo, instead of using a hash, it uses a
red-black tree to keep track of all flows. While memory and compute
intensive for a router, it's pretty awesome on hosts, and makes it
possible to schedule (and pace) tcp flows at a level much closer to
the driver hardware, using the same new/sparse vs persistent queue
distinction fq_codel does.

4) While I think I finally understand your longstanding criticism of
how aqm and scheduling technologies are indeed distinct, there is a
parameter that must be
shared globally between the two algorithms: the maximum overall queue
length (governing worst case drop behavior). This is the basic flaw of
applying
(at least in linux) sfq, drr, qfq, htb, etc naively with a drop tail
queue, as the maximum overall queue length is additive.

Take for example a simple QoS setup

filter that breaks up stuff into 4 QoS queues:

drr 1 -> sfq limit 127 (prio)
drr 2 -> sfq limit 127 (video)
drr 3 -> sfq limit 127 (BE)
drr 4 -> sfq limit 127 (background)

So you end up with worst case drop tail and delay behavior for drr +
sfq queue of 4*127 packets. If using weighted drr, the proportions
change, but the worst case drop behavior does not. If using something
like htb, the background queue has a worst case drop tail and delay
behavior of 4*127, be, 3*127, and so on. Having a shared overall queue
size is extremely important for being able to classify queues and get
sane behavior. You could, for example, try using 32 packet queues to
get the same overall worst case latency guarantee but you'd sacrifice
bandwidth if the majority of traffic was BE only.

This is less important with a system that tries to measure latency and
be intelligent about drop behavior, but you still have worst case
behavior that is additive in the case of non-responsive flows.

4a) The problem with using individual queues for something like
pie-per-fq'd_queue, is that pie depends on being able to sample X
number of packets in order to determine it's drop decision, which it
may not get relevant to the overall load on the system for flows that
are too small to tweak pie's estimator, yet worth dropping a packet
from.

4b) and the opposite problem in codel, with a single codel queue
taking fq'd packets (rather than one codel queue per fq) is the
reliance on timestamps for dropping in and out of drop state, which
doesn't work if you don't do the timestamp in the right place.

(I'll no doubt find more nits later :) )

On Fri, Jun 13, 2014 at 3:07 PM, Fred Baker (fred) <[email-masked]> wrote:
> _______________________________________________
> aqm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/aqm
>

-- 
Dave Täht

NSFW: https://w2.eff.org/Censorship/Internet_censorship_bills/russell_0296_indecent.article

---

From: Dave Taht <[email-masked]>
Date: Fri, 13 Jun 2014 17:26:43 -0700

doing this privately...

" The weakness of a WRR approach is the search time
   expended when the queuing system is relatively empty, which the
   calendar queue model obviates."

This is a little strong.

Fq_codel (and DRR) is darn close to O(1) on the dequeue side for
sparse numbers of flows. I wouldn't use the word "searching" in describing
the behavior of DRR in this case.

        head = &q->new_flows;
        if (list_empty(head)) {
                head = &q->old_flows;
                if (list_empty(head))
                        return NULL;
        }
        flow = list_first_entry(head, struct fq_codel_flow, flowchain);

        if (flow->deficit <= 0) {
                flow->deficit += q->quantum;
                list_move_tail(&flow->flowchain, &q->old_flows);
                goto begin;
        }

If you have one flow only, and it's over it's quantum, you go through
this loop twice. If you have two flows and they are both over quantum,
3 times, but the next 2 times no more than once. Three flows, all over
quantum, 4 times, but the 3 next 3 times through no more than once
each.

(this is assuming that quantum is set for mtu size packets) So you end
up with times through the loop averaging less than 2.

Then applying codel to the queue, codel will iterate through it's list of
packets eventually delivering 1 or not. This too is short (function elided)

        skb = codel_dequeue(sch, &q->cparams, &flow->cvars, &q->cstats,
                            dequeue);

        flow->dropped += q->cstats.drop_count - prev_drop_count;
        flow->dropped += q->cstats.ecn_mark - prev_ecn_mark;

// the original fq_codel code would never hit this point below as codel always
// stopped dropping at one packet remaining per queue.

        if (!skb) {
                /* force a pass through old_flows to prevent starvation */
                if ((head == &q->new_flows) && !list_empty(&q->old_flows))
                        list_move_tail(&flow->flowchain, &q->old_flows);
                else
                        list_del_init(&flow->flowchain);
                goto begin;
        }

As drop rates are typically measured in fractions of a percentage
point, and IF codel empties a queue entirely and you have to select a
new drr queue, you have the sum of these behaviors as your maximum
overhead.

Does QFQ meet your definition of a calendar queue model?

On Fri, Jun 13, 2014 at 4:43 PM, Fred Baker (fred) <[email-masked]> wrote:
> Thanks
>
> On Jun 13, 2014, at 4:04 PM, Dave Taht <[email-masked]> wrote:
>

-- 
Dave Täht

---

From: grenville armitage <[email-masked]>
Date: Fri, 20 Jun 2014 13:12:57 +1000

Fred,

Just read it -- clear, easy to comprehend. I'd be happy pointing AQM newcomers at it.

One nit: Might be just me, but the Acknowledgements section feels more like an editorial/opinion. For a newcomer to AQM it wouldn't necessarily be clear how the body of the I-D supports the expressed opinion.

cheers,
gja

-- 
Professor Grenville Armitage
Director, Centre for Advanced Internet Architectures
School of Software and Electrical Engineering
Faculty of Science, Engineering and Technology
Swinburne University of Technology, Australia
http://caia.swin.edu.au

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Fri, 20 Jun 2014 15:51:48 +0000

> One nit: Might be just me, but the Acknowledgements section feels more like an editorial/opinion. For a newcomer to AQM it wouldn't necessarily be clear how the body of the I-D supports the express…

Fair enough. The second sentence likely belongs in the conclusions.

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 23 Jun 2014 13:32:07 +0000

<as individual>

Hi Fred,

thank you for writing this down; one aspect that gets referred to, but not made completely explicit in sections 3.2 and 3.3 is the interaction of the AQM / Queue signals with the transport control loop.

IMHO, it should be made very clear, when the AQM action is done before the queueing, that the AQM signal is delayed for the outer control loop; obviously in a defensive loss situation, this will always be the case. In comparison, when the Queue prepends the AQM action, the AQM signal is delayed less to the outer control loop.

Depending on the depth of the queue / departure rate, that timing difference can be significant...

I don't know how to put that into better words that would fit into your draft though.

Best regards,

Richard Scheffenegger

> -----Original Message-----
> From: aqm [mailto:[email-masked]] On Behalf Of Fred Baker (fred)
> Sent: Freitag, 20. Juni 2014 17:52
> To: grenville armitage
> Cc: [email-masked]
> Subject: Re: [aqm] New Version Notification for draft-baker-aqm-sfq-
> implementation-00.txt
> 
> 
> > One nit: Might be just me, but the Acknowledgements section feels more
> like an editorial/opinion. For a newcomer to AQM it wouldn't necessarily
> be clear how the body of the I-D supports the expressed opinion.
> 
> >> I'd be interested in comments on this.
> >>
> >>> Subject: New Version Notification for
> >>> draft-baker-aqm-sfq-implementation-00.txt
> >>> To: Fred Baker <[email-masked]>, Rong Pan <[email-masked]>, Fred
> >>> Baker <[email-masked]>, Rong Pan <[email-masked]>
> >>>
> >>>
> >>> has been successfully submitted by Fred Baker and posted to the IETF
> >>> repository.
> >>>
> >>> Please note that it may take a couple of minutes from the time of
> >>> submission until the htmlized version and diff are available at
> tools.ietf.org.
> >>>
> >>> The IETF Secretariat
> >>>
> >>
> >>
> >>
> > Director, Centre for Advanced Internet Architectures School of
> > Software and Electrical Engineering Faculty of Science, Engineering
> > and Technology Swinburne University of Technology, Australia
> > http://caia.swin.edu.au
> >

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Tue, 24 Jun 2014 07:41:11 +0000

> I don't know how to put that into better words that would fit into your draft though.

I can go into that if you want.

My logic here goes something like this.

You can think of a TCP session as a control loop stuck into the middle of a larger stream. Imagine I’m moving a gigabyte file from here to there, the MSS is 1440 bytes (an IPv6 packet containing it is 1500 bytes), the bottleneck link between “here” and “there” is some specific rate, and the propagation delay between “here” and “there” is some non-trivial value. The least effective window that would maximize throughput is the number of segments that could fully use the bottleneck capacity; any additional quantum that is there sits in a queue and increases the RTT. So at any given point in time, we can think of the transfer as having several components:

     K segments that are actually “in flight” somewhere
     An additional K segments that hack been received and whose acks are in flight.
     cwnd-2*K segments sitting in a queue, probably at the bottleneck.
     Some number of bytes that haven’t been transmitted yet
          of those, the next cwnd segments will be transmitted as acks arrive.
     Some number of bytes that have already been received at the far end but not delivered yet to the application
     Zero or more segments that have been received out of order and are being held pending retransmission

Now, let’s mark a specific segment; I’ll call it segment N. I don’t really care what the value of N is. But it is the segment that the AQM algorithm will select and drop, by whatever algorithm it decides. In a tail-drop case, for the sake of argument, we can assert that the entire cwnd segments are between segment N and the receiver or are represented in acknowledgments on their way back. In a head-drop case, there are cwnd-2K segments sitting in the queue after segment N, K segments between it and the receiver, and K acks in flight.

  +------+      +--------+                      +--------+
  |      |      | Queue  |Data    K segments    |        |
  |      +----->+        +----> - - - - ------->+        |
  |Sender|      |Router 1|                      |Receiver|
  |      +<-----+        +<---- - - - - <-------+        |
  |      |      |        |Acks    K acks        |        |
  +------+      +--------+                      +--------+

So now, the whole thing rotates clockwise. 
1) K segments already in flight arrive and are acknowledged while K acks arrive at the sender and trigger new transmissions. The queue still has cwnd-2*K segments in it.
2) depending on whether it was head drop or tail drop, somewhere between zero and cwnd-2*K segments arrive and are acknowledged while as many acks are received at the sender and trigger new transmissions. The queue still has cwnd-2*K segments in it.
3) the missed packet is detected by the receiver, who starts responding with duplicate acks. However, there are still K acks in flight, so the sender is going to send another K new packets before he even sees the first dupack. The queue still has cwnd-2*K segments in it.
4) we now get a long stream of dupacks, and the sender presumably retransmits the dropped packet. AT THIS POINT, SENDER REDUCES CWND. If more than one packet got dropped, let’s hope the SACK logic retransmits it as well.
5) At long last, the retransmission arrives at the receiver, who sends a giant ack and starts sending a stream of acks, triggering new transmissions.

To determine the difference between head-drop and tail-drop, we have to ask ourselves how big cwnd-2*K is. If we are using traditional too-full-drop-something without AQM, it might be a largish number (it could be the size of the memory allocated to the queue if there is no competing traffic), and it is probably fair to say that head-drop would get the event back to the sender more rapidly than tail-drop.

If we are using any AQM technology - RED, WRED, ARED, PIE, CoDel, Blue, AVQ, or whatever else, the fundamental purpose of the logic is to keep the queue relatively shallow, even if it ha a large memory system behind it. In RED terms, we would estimate that the mean queue depth will approximate min-threshold or less; each of the other technologies has its counterpart to that and will similarly keep the latency and/or queue depth down.

Hence, cwnd-2*K is a function of the mean queue depth at the bottleneck, and is a relatively small number. Hence, if we’re using an AQM algorithm - any AQM algorithm as long as it works - the real differences between had-drop and tail-drop is a relatively small number.

Which makes me ask - what are we really talking about? Does it actually matter?

---

From: Daniel Havey <[email-masked]>
Date: Tue, 24 Jun 2014 12:45:57 -0700

Yup, this is what my experiments are showing.  I'm not doing head/tail drop, but, I am dropping/marking at the device before and after the bloated device.  That would be counterclockwise or clockwise of the bloated (slow and overqueued) device.  This is essentially the same thing.

What I am observing is that if I drop/mark after (clockwise) the system is snappy and manages the queue quickly.  Dropping counterclockwise (before) the bloated device is a slightly different story.  If I let the flow run for a few seconds the bloat builds up in the queue at the slow device.  Switching AQM on at this point causes "overshoot" and burns the connection.

I think what is happening is that it takes so long for the drop signal to propagate that by the time the retransmitted packet arrives it's time to drop again so we lose the retransmission and have to wait for an RTO.  Whatever.  Baaaad mojo.  Don't let this happen.

Anyways, as long as the AQM system is on before the flow starts then the queuing is managed and the system remains snappy.

So IMHO it really doesn't matter except in the weird corner case where a a running flow has already bloated the queue and then we switch on the AQM.

BTW...On a related note: I tried to address that problem by using ECN.  If I don't drop a packet then there will be no RTX so...Well anyways, I switched on the ECN on my Linux boxes and the thing doesn't work!  Is ECN in Linux broken?  Here are the details:

I switched ECN on using the /proc filesystem setting it to request ECN and to accept ECN requests.  However examining the wireshark trace shows that the flow is marked Not ECN capable.  I'm running 3.12 kernels.

I find it difficult to believe that ECN is broken in Linux, but, it's definitely not working. Uhhhh, seriously?  ECN is broken in Linux?  You gotta be kidding me?!?  Did I do something wrong?  Anybody else notice this?

*** I don't care that much about it because my experiments don't actually require that I use ECN, but, how on earth can we expect people to activate ECN when it doesn't even work?  Errrrggggghhh!

--------------------------------------------
On Tue, 6/24/14, Fred Baker (fred) <[email-masked]> wrote:

 Subject: Re: [aqm] New Version Notification for draft-baker-aqm-sfq-implementation-00.txt
 To: "Scheffenegger, Richard" <[email-masked]>
 Cc: "[email-masked]" <[email-masked]>, "grenville armitage" <[email-masked]>
 Date: Tuesday, June 24, 2014, 12:41 AM

 On
 Jun 23, 2014, at 6:32 AM, Scheffenegger, Richard <[email-masked]>
 wrote:
 
 > <as
 individual>
 > Hi
 Fred,
 > thank you
 for writing this down; one aspect that gets referred to, but
 not made completely explicit in sections 3.2 and 3.3 is the
 interaction of the AQM / Queue signals with the transport
 control loop.
 IMHO, it should be made very clear, when the AQM action is
 done before the queueing, that the AQM signal is delayed for
 the outer control loop; obviously in a defensive loss
 situation, this will always be the case. In comparison, when
 the Queue prepends the AQM action, the AQM signal is delayed
 less to the outer control loop.
 > 
 > Depending on the depth of the queue /
 departure rate, that timing difference can be
 significant...
 > I
 don't know how to put that into better words that would
 fit into your draft though.
 > Richard Scheffenegger
 
 I can go into that if you
 want.
 
 My logic here goes
 something like this.
 
 You
 can think of a TCP session as a control loop stuck into the
 middle of a larger stream. Imagine I’m moving a gigabyte
 file from here to there, the MSS is 1440 bytes (an IPv6
 packet containing it is 1500 bytes), the bottleneck link
 between “here” and “there” is some specific rate,
 and the propagation delay between “here” and “there”
 is some non-trivial value. The least effective window that
 would maximize throughput is the number of segments that
 could fully use the bottleneck capacity; any additional
 quantum that is there sits in a queue and increases the RTT.
 So at any given point in time, we can think of the transfer
 as having several components:
 
      K segments that are actually
 “in flight” somewhere
  
    An additional K segments that hack been
 received and whose acks are in flight.
  
    cwnd-2*K segments sitting in a queue, probably
 at the bottleneck.
      Some
 number of bytes that haven’t been transmitted yet
           of those, the next cwnd segments
 will be transmitted as acks arrive.
  
    Some number of bytes that have already been
 received at the far end but not delivered yet to the
 application
      Zero or more
 segments that have been received out of order and are being
 held pending retransmission
 
 Now, let’s mark a specific segment; I’ll
 call it segment N. I don’t really care what the value of N
 is. But it is the segment that the AQM algorithm will select
 and drop, by whatever algorithm it decides. In a tail-drop
 case, for the sake of argument, we can assert that the
 entire cwnd segments are between segment N and the receiver
 or are represented in acknowledgments on their way back. In
 a head-drop case, there are cwnd-2K segments sitting in the
 queue after segment N, K segments between it and the
 receiver, and K acks in flight.
 
   +------+      +--------+           
           +--------+
   |      | 
     | Queue  |Data    K segments    |        |
   |      +----->+        +----> -
 - - - ------->+        |
  
 |Sender|      |Router 1|                     
 |Receiver|
   |      +<-----+     
   +<---- - - - - <-------+        |
   |      |      |        |Acks   
 K acks        |        |
  
 +------+      +--------+                     
 +--------+
 
 So now, the
 whole thing rotates clockwise. 
 1) K
 segments already in flight arrive and are acknowledged while
 K acks arrive at the sender and trigger new transmissions.
 The queue still has cwnd-2*K segments in it.
 2) depending on whether it was head drop or
 tail drop, somewhere between zero and cwnd-2*K segments
 arrive and are acknowledged while as many acks are received
 at the sender and trigger new transmissions. The queue still
 has cwnd-2*K segments in it.
 3) the missed
 packet is detected by the receiver, who starts responding
 with duplicate acks. However, there are still K acks in
 flight, so the sender is going to send another K new packets
 before he even sees the first dupack. The queue still has
 cwnd-2*K segments in it.
 4) we now get a
 long stream of dupacks, and the sender presumably
 retransmits the dropped packet. AT THIS POINT, SENDER
 REDUCES CWND. If more than one packet got dropped, let’s
 hope the SACK logic retransmits it as well.
 5) At long last, the retransmission arrives at
 the receiver, who sends a giant ack and starts sending a
 stream of acks, triggering new transmissions.
 
 To determine the difference
 between head-drop and tail-drop, we have to ask ourselves
 how big cwnd-2*K is. If we are using traditional
 too-full-drop-something without AQM, it might be a largish
 number (it could be the size of the memory allocated to the
 queue if there is no competing traffic), and it is probably
 fair to say that head-drop would get the event back to the
 sender more rapidly than tail-drop.
 
 If we are using any AQM technology - RED, WRED,
 ARED, PIE, CoDel, Blue, AVQ, or whatever else, the
 fundamental purpose of the logic is to keep the queue
 relatively shallow, even if it ha a large memory system
 behind it. In RED terms, we would estimate that the mean
 queue depth will approximate min-threshold or less; each of
 the other technologies has its counterpart to that and will
 similarly keep the latency and/or queue depth down.
 
 Hence, cwnd-2*K is a function
 of the mean queue depth at the bottleneck, and is a
 relatively small number. Hence, if we’re using an AQM
 algorithm - any AQM algorithm as long as it works - the real
 differences between had-drop and tail-drop is a relatively
 small number.
 
 Which makes
 me ask - what are we really talking about? Does it actually
 matter?

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Tue, 24 Jun 2014 20:01:01 +0000

> So IMHO it really doesn't matter except in the weird corner case where a a running flow has already bloated the queue and then we switch on the AQM.

That actually has me a little worried with the 100 ms delay built into codel. Imagine, if you will, that you have a deep buffer at the bottleneck and a relatively short RTT, and are moving a large file. I could imagine codel’s delay allowing a session to build a large backlog and then “suddenly turning on AQM”. on a 10 MS link with O(200) packets queue depth, for example, you could build 100 ms plus of data in the queue, spend the delay mostly emptying it, and then drop the last queued packet because 100 ms had gone by, there was still data in the queue, and the next packet had sat there longer than 5 ms.

---

From: Daniel Havey <[email-masked]>
Date: Tue, 24 Jun 2014 13:33:35 -0700

So far in my observations (admittedly a very small sample size) it's more of an annoyance than a problem.  We get an unwanted congestion event and lose a little bandwidth, but, after that the queue is drained and can begin building up again.

But yeah, I see your concern.  There may be scenarios where the interaction of the interval, the RTT and the bandwidth cause this to happen recurringly constantly underflowing the bandwidth.

...Daniel

 Subject: Re: [aqm] New Version Notification for draft-baker-aqm-sfq-implementation-00.txt
 To: "[email-masked]" <[email-masked]>
 Cc: "RichardScheffenegger" <[email-masked]>, "[email-masked]" <[email-masked]>, "grenville armitage" <[email-masked]>
 Date: Tuesday, June 24, 2014, 1:01 PM

 On
 Jun 24, 2014, at 12:45 PM, Daniel Havey <[email-masked]>
 wrote:
 
 > So IMHO it
 really doesn't matter except in the weird corner case
 where a a running flow has already bloated the queue and
 then we switch on the AQM.
 
 That actually has me a little worried with the
 100 ms delay built into codel. Imagine, if you will, that
 you have a deep buffer at the bottleneck and a relatively
 short RTT, and are moving a large file. I could imagine
 codel’s delay allowing a session to build a large backlog
 and then “suddenly turning on AQM”. on a 10 MS link with
 O(200) packets queue depth, for example, you could build 100
 ms plus of data in the queue, spend the delay mostly
 emptying it, and then drop the last queued packet because
 100 ms had gone by, there was still data in the queue, and
 the next packet had sat there longer than 5
 ms.

---

From: Dave Taht <[email-masked]>
Date: Tue, 24 Jun 2014 13:44:29 -0700

>> So IMHO it really doesn't matter except in the weird corner case where a a running flow has already bloated the queue and then we switch on the AQM.

Hmm? In practice, changing the qdisc in Linux, at least, does
completely blow up the existing queue: all packets are discarded, the
various data structures removed, the new data structures created, then
switched.

Don't do that. Do it once, at init time, or before address
acquisition. Simple schemes can be handled now (linux 3.13 and later)
by a single sysctl variable, set either in /etc/sysctl.conf or via

sysctl -w net.core.default_qdisc=fq_codel # or pie, or sfq, or fq

Arguably this needs to allow for arguments, be more flexible and
interface specific. Same goes for enabling ecn or not.
(net.ipv4.tcp_ecn=0)

More complex implementations, like htb, have a "default" direction
things go until things are fully setup. Other linux implementations,
like drr and qfq, do not, and result in packet loss until entirely
setup.

Recently support for a "plug scheduler" was developed in order to
assist vm migration, which might make it more possible to switch out
qdiscs without interrupting service.

> That actually has me a little worried with the 100 ms delay built into codel.

"Initial delay" until it finds a sane delay to drop at.

>Imagine, if you will, that you have a deep buffer at the bottleneck and a relatively short RTT, and are moving a large file. I could imagine codel’s delay allowing a session to build a large backlog and then “suddenly turning on AQM”. on a 10 MS link with O(200) packets queue depth, for example, you could build 100 ms plus of data in the queue, spend the delay mostly emptying it, and then drop the last queued packet because 100 ms had gone by, there was still data in the queue, and the next packet had sat there longer than 5 ms.

Given that pie depends on an estimation window being filled this is
not a problem pie has. However needing that window filled is a big
problem at low bandwidths for pie.

As for codel....

Well there is a specific inhibit in present forms of codel to not drop
the last packet in the queue even if it has sat there too long. Codel
stops dropping at minbytes (called maxpacket in the code), which is a
variable determined from the flow characteristics, and is usually 1MTU
in size, but can be larger if TSO or GRO are in operation on the
device.

The first versions of fq_codel preserved this behavior: it would never
drop the last packet in any fq_codel queue. This (still) seems like
desirable behavior in the case of having nearly one queue per flow,
but it led inevitably to what I had called the horizontal standing
queue problem (where we could end up with 1024 queues all with one
packet and no longer meeting the latency target(s)). So eric made the
backlog maxpacket check global to all queues, and that's what's been
deployed ever since.

Later work, (I think) is showing, that in practice any inhibit at all
hurts on the architectures available, as htb or (bql and the tx-ring)
are already buffering up packets below where codel was dropping from
near-head.

More packets will always be along, later.

This patch disables the maxpacket check entirely, and results in a
space and cpu savings, without much observable negative or positive
effect on latency and utilization on the bandwidths available to me. I
remain a bit concerned about what happens with TSO and/or GRO enabled.

http://snapon.lab.bufferbloat.net/~cero2/0003-codel-eliminate-maxpacket-variable.patch

I'd love it if people tried it.

Of higher concern to me has long been more sanely applying hysteresis
in the drop rate over wildly varying high bandwidths and loads, but
not a lot of work has gone into codel since it's inception, as it was
so good to start with and so dramatically improved by fq_codel as to
be barely worth debating. But certainly better control laws are
welcomed!

-- 
Dave Täht

---

From: "Fred Baker (fred)" <[email-masked]>
Date: Tue, 24 Jun 2014 20:48:48 +0000

On Jun 24, 2014, at 1:33 PM, Daniel Havey <[email-masked]> wrote:

> There may be scenarios where the interaction of the interval, the RTT and the bandwidth cause this to happen recurringly constantly underflowing the bandwidth.

To be honest, the real concern is very long delay paths, and it applies to AQM algorithms generally. During TCP slow start (which is not particularly slow, but entertains contains exponential growth), we have an initial burst, which with TCP Offload Engines can, I’m told, spit 65K bytes out in the initial burst. The burst travels somewhere and results in a set of acks, which presumably arrive at the sender at approximately the rate the burst went through the bottleneck, but elicit a burst roughly twice as fast as the bottleneck. That happens again and again until either a loss/mark event is detected or cwnd hits ssthresh, at which point the growth of cwnd becomes linear.

If the burst is allowed to use the entire memory of the bottleneck system’s interface, it will very possibly approach the capacity of the bottleneck. However, with pretty much any AQM algorithm I’m aware of, the algorithm will sense an issue and drop or mark something, kicking the session into congestion avoidance relatively early.

This is well-known behavior, and something we have a couple of RFCs on.

But yes, it can happen on more nominal paths as well.

---

From: Dave Taht <[email-masked]>
Date: Tue, 24 Jun 2014 16:06:01 -0700

> To be honest, the real concern is very long delay paths, and it applies to AQM algorithms generally. During TCP slow start (which is not particularly slow, but entertains contains exponential growt…

I think tcp offloads have been thoroughly shown by now to blow up all
sorts of networks, and there has been a lot of work in recent linux
kernels for hosts to mitigate it (use smaller bursts), most recently
the sch_fq + pacing work. The objective of slow start is to "fill the
pipe" and especially in the case of long rtts like in satellite and
lte networks, it needs to be, well, slower.

tcp offloads are an assist to slower cpus and a per-ethernet-device
"feature" to get more "bandwidth" for less cpu... at the cost of
latency, bursty loss, and packet mixing. modern x86 hardware can
easily saturate gigE links without TSO in use at all. many lower end
(arm) products can't, as yet, and 10GigE is still the realm of TSO
(with mitigations arriving in software as per above)

I do hope things like TSO2 (bursts of 256k packets) are not widely
adopted, and smarter mixing happens on multi-queued ethernet devices
instead.

> If the burst is allowed to use the entire memory of the bottleneck system’s interface, it will very possibly approach the capacity of the bottleneck. However, with pretty much any AQM algorithm I’m…

big bursts are bad. let packets be packets!

Kicking things into congestion avoidance early turns out to have
interesting interactions with hystart.

-- 
Dave Täht