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

[Dave Taht <[e-mail]>]

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) <[e-mail]> wrote:
> Thanks
>
> On Jun 13, 2014, at 4:04 PM, Dave Taht <[e-mail]> wrote:
>
>> 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) <[e-mail]> wrote:
>>> I’d be interested in comments on this.
>>>
>>>> From: <[e-mail]>
>>>> 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 <[e-mail]>, Rong Pan <[e-mail]>, Fred Baker <[e-mail]>, Rong Pan <[e-mail]>
>>>>
>>>>
>>>> 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
>>>>
>>>
>>>
>>> _______________________________________________
>>> aqm mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/aqm
>>>
>>
>>
>>
>> --
>> Dave Täht
>>
>> NSFW: https://w2.eff.org/Censorship/Internet_censorship_bills/russell_0296_indecent.article
>



-- 
Dave Täht

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