Subject: Re: [tsvwg] comments about draft-ietf-tsvwg-aqm-dualq-coupled-01.txt

From: Bob Briscoe <[email-masked]>
Date: Sat, 4 Nov 2017 17:02:13 +0000

Sowmini and list,

A week ago we posted a major revision: 
draft-ietf-tsvwg-aqm-dualq-coupled-02

It includes all the offline advice you (Sowmini) said would be good to 
have in the doc itself.
Apologies for the long delay replying, I started a couple of month's 
break between jobs just as we started talking.

[Actually I just noticed the way you quoted it in your email is clearer 
than how we wrote it in the draft, so I have just updated our local copy 
again (will appear on IETF servers in the next rev).]

There's also 2 whole new sections:
* DualQ Coupled AQM structure (2pp)
* Management Requirements (Normative) (1p)

The cleaner structure mainly affects the management requirements (config 
and statistics monitoring), which we will present in Singapore.
We now have a modular separation between the three main pluggable 
components:
* the Base AQM
* the L4S AQM
* the framework (classifier, coupling, and conditional priority 
scheduler) [+ policing (TBA)]
(plus of course the sender CC algorithm is also pluggable)

This structure has been reflected in the Linux implementation (these 
updates are still in the private development version). Thanks to Henrik 
Steen this now makes the 2 queues within the qdisc classful, so they 
inherit all their config and statistics monitoring from the qdisc class. 
This gives operators a regular hierarchical queuing structure. Whereas 
before the dualQ was a monolithic blob that didn't fit well within any 
larger queuing hierarchy.

We also clarified numerous technical aspects that have changed over the 
last year, where the pseudocode has changed, but the text hasn't kept up.
Particular thanks to you (Sowmini) & Gabi Bracha off-list, who were 
trying to understand it and gave useful review comments.

Main changes:
* Added diagram and description of structure of AQM framework.
* Supports a pair of AQMs 'native' to each queue, both time-based.
Examples (in the order: native Classic + native L4S):
* DualPI2 = PI2 + shallow step
* DualCurvyRED = Curvy RED + shallow step
Explained distinction between DualPI2 and PI2 (and PIE).

Added Management Requirements:
* Configuration
* Monitoring

Explained pseudocode much more clearly.
* Removed implementation tricks to focus on how it is meant to work.

Curvy RED pseudocode is not as well-maintained.
However, we have provided a clear list of all the peripheral aspects 
that would have to be added (all can be translated from DualPI2).

Finally, a note about the command line API for DualPI2 (documented in 
the code, not the draft, but we've changed the draft to be consistent):
We decided we had to break backward compatibility with the PIE AP:
   - So that parameters could be changed independently
     (when you changed one PIE parameter, you sometimes had to change 
another to keep it unchanged underneath)
   - Some PIE parameters had to be entered in obscure units like 1/16 of 
1 Hz

Extra responses inline...

On 08/08/17 20:34, Spencer Dawkins at IETF wrote:
> Speaking as an individual, but as an individual who needs to 
> understand what's going on at PubReq time :-) ...
>
> On Mon, Aug 7, 2017 at 9:31 AM, Sowmini Varadhan 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     I had some questions as I was going over this document and
>     Bob Briscoe suggested that this might be a useful discussion to
>     share with a list, so here's a current summary, including
>     clarifications that Bob provided for me offline
>
>     In general, I liked the fact that the Appendix starts off by first
>     discussing core concepts and then gets into the more complex overload
>     case- this makes it easy to understand how the various blocks build on
>     each other.
>
>     In keeping with that same core -> complex flow, it might be easier to
>     refactor Appendix A.1 a bit, so that it first goes over the
>     enque/dequeue
>     logic and then gets into the more complex PI-update Pseudo-code.
>
[BB] We've sort-of done that. Except I wanted to start by highlighting 
that maintaining and applying p is the ultimate point of all this.

>
>     I realize the document *is* trying to do that, but it took
>     me some time to figure out the semantics of alpha/beta/alpha_U/beta_U
>     (these get defined in Figure 1, but a detailed description
>     is only available at the bottom Page 17..)
>
>     What eventally helped me put things in place was the brief background
>     that Bob offered (in the offline thread)
>
>     Bob> A Proportional Integral (PI) algorithm changes the controlled
>     variable (the
>     Bob> loss probability p) dependent on how fast the queue is
>     increasing (which is
>     Bob> Proportional to excess load) and how far any standing queue is
>     Bob> from its target (which represents the Integral of load). Two
>     "gain
>     Bob> factors", beta and alpha, respectively weight how strongly
>     each of
>     Bob> these elements alters p.
>
>     Bob> The stability analysis in [PI216] recommends the values of alpha
>     Bob> and beta (in the header file in Fig 1) on the basis that these
>     Bob> cause the AQM to change p (loss prob) as fast as poss in response
>     Bob> to changes in load without over-compensating and therefore
>     causing
>     Bob> oscillations in the queue.
>
>     Bob> The recommended values of alpha and beta determine how much p
>     ought
>     Bob> to change if it was updated every second. It is best to update p
>     Bob> as frequently as possible, but the actual update interval
>     (Tupdate)
>     Bob> is constrained by hardware performance. For link rates from 4 -
>     Bob> 200 Mb/s, we found Tupdate=16ms is sufficient. Whatever value of
>     Bob> Tupdate is chosen, p should change by the same amount per second,
>     Bob> but in more smaller steps. So the gain factors used need to
>     Bob> be scaled by (Tupdate/1s). This is why alpha_U and beta_U are
>     Bob> used for updating p in Fig 4, where alpha_U= alpha*Tupdate and
>     Bob> beta_U=beta*Tupdate.
>
>     Some/all of this information would be useful to have in the doc, since
>     it provides the needed brief background for dualpi2_update, within
>     the draft itself.
>
>
> I found Bob's note to be very helpful to me. It might be helpful to 
> include something like that text in the document itself.
>
> Do the right thing, of course.
>
> Spencer
>
>     One follow-up question (I've not read all of [PI216] yet, it's on my
>     reading list) - what is the general trend of Tupdate for faster
>     link-rates? E.g., what is the expected Tupdate at 1Gb/s?
>
[BB] Tupdate doesn't depend on the link rate per se {Note 1}.
Tupdate depends on your target Qdelay, which depends on the max e2e RTT.

You want to have a reasonable number of updates (ideally >= 2) in the 
time the queue drains naturally from target to zero. So,
     Tupdate <= target/2
would be a good rule of thumb. But so far we've used Tupdate (16 ms) ~= 
target (15 ms) so I'll continue like that.

So, if your link is in a DC with 100x lower max RTT than the public 
Internet, you might have target = 150 µs
Then Tupdate = 160 µs

If max RTT is 100x smaller, alpha and beta need to be 100x larger; i.e. 
1000 Hz^2 and 10,000 Hz^2 respectively.

Nonetheless, the gain factors actually used internally are:
     alpha_U = alpha * Tupdate
     beta_U  = beta  * Tupdate
So, because Tupdate is 100x smaller, alpha_U and beta_U will be the same 
as before.

Of course, if Tupdate is 100x larger, p is calculated 100x more often.

You might notice that, in a DC where you have say 100x lower RTT and 
100x higher bit-rate than the public Internet, even tho the 
bandwidth-delay product is roughly the same as on the public Internet, 
the switch is forwarding 100x faster and calculating p 100x more often. 
Superficially this looks like 10,000x more processing, but at least the 
process to update p is decoupled from packet forwarding.

We'll write a new scaling section into the next rev of the draft. But 
first I'll check that I'm correct with my co-authors tho.

{Note 1} The Qdelay target depends on the degree of flow multiplexing. 
All the above assumes the low degree of flow multiplexing typical both 
in a public Internet per-customer access link and in 'typical' DCs (i.e. 
1-10 flows). Then you have to configure the AQM for the "typical 
worst-case" when you have 1 TCP flow. For high levels of flow 
multiplexing, target Qdelay can be 1/sqrt(N) smaller, where N is the 
"typical minimum" no. of flows on the link. E.g. for N=100 flows, target 
Qdelay can be 1/10 of the figures above.

"Typical minimum" is deliberately arm-wavey. It might be the 10%-ile or 
something. The implication of setting target too low would be slight 
under-utilization when the number of flows is less than the N you've 
guessed, so it's not critical to be precise.

BTW, this sqrt() is nothing to do with the sqrt() in the TCP equation. 
It comes from the Central Limit Theorem.

BTW2, this 1/sqrt(N) rule doesn't continue indefinitely. The Qdelay 
flattens out for really high N. From memory there's something about a 6 
packet limit, but I'd have to re-read the relevant (very short) paper 
below.
Ganjali, Y. & McKeown, N., "Update on Buffer Sizing in Internet 
Routers," ACM SIGCOMM Computer Communication Review 36 ACM (October 2006)

>
>     It would also be helpful to define the high-level semantics
>     of cq.time(), cq.len(), lq.len() etc. E.g. the description that Bob
>     offered in the offline mail (below) could be added in the preamble
>     to enque/dequeue, to improve readability (and also help an implementor
>     quickly see what the function indirections are supposed to do).
>
>     Bob> cq.time() is a function that returns the time that the head
>     packet
>     Bob> has been in the classic queue (cq), which is called the "service
>     Bob> time" of the queue, or sometimes the "sojourn time".
>
>     Bob> Similarly for lq.time(), cq.len() and lq.len(), where lq is the
>     Bob> L4S queue and len() is the length in bytes.
>
Done.

And thx again for your patience trying to understand this.

Bob

>
>     I'm still working through the doc, will get back here with additional
>     questions/comments.
>
>     Thanks
>     --Sowmini
>
>

---

From: Sowmini Varadhan <[email-masked]>
Date: Tue, 7 Nov 2017 11:27:02 -0500

>    draft-ietf-tsvwg-aqm-dualq-coupled-02

Thanks for incorporating the suggestions- I'm happy with the new
version. I esp like the new format of Section 2.4 and Figure 1.

--Sowmini

---

From: Sowmini Varadhan <[email-masked]>
Date: Tue, 7 Nov 2017 17:49:26 -0500

One possible typo: 

Section A.1, page 21 of draft*02, 
  "... However, on
      slow links the packet serialization time can approach the
      threshold T_time, so line 6 sets a floor of 2 MTU to the
      threshold."

should refer to line 19 (not line 6) of initialization code (Figure 2)?

--Sowmini

---

From: Bob Briscoe <[email-masked]>
Date: Tue, 7 Nov 2017 23:11:38 +0000

Sowmini,

No, that's line 6 of the dequeue code, not the initialization code. I 
think that's clear from the context which is walking through the dequeue 
code (the para that introduces the bullets says they're about the 
dequeue code and the previous sentence within the bullet says we're at 
lines 5 to 8).

Nonetheless, I will change it to
     "so line 6 sets a floor of T_len (=2 MTU) to the threshold"

Is that OK?

Bob

---

From: Sowmini Varadhan <[email-masked]>
Date: Tue, 7 Nov 2017 18:27:32 -0500

On (11/07/17 23:11), Bob Briscoe wrote:
> Sowmini,
> 
> No, that's line 6 of the dequeue code, not the initialization code. I think
> that's clear from the context which is walking through the dequeue code (the
> para that introduces the bullets says they're about the dequeue code and the
> previous sentence within the bullet says we're at lines 5 to 8).
> 
> ?????? "so line 6 sets a floor of T_len (=2 MTU) to the threshold"
> 
> Is that OK?

yes that helps, thanks

--Sowmini