Subject: Re: [tsvwg] two questions on draft-ietf-tsvwg-aqm-dualq-coupled-06

From: Bob Briscoe <[email-masked]>
Date: Fri, 3 Aug 2018 00:18:07 +0100

Tom,

On 02/08/18 19:34, Tom Henderson wrote:
> Bob,
> I have two questions about the pseudocode in Appendix A of 
> draft-ietf-tsvwg-aqm-dualq-coupled-06.
>
> 1) in Figure 3 enqueue logic:
>
>    1:  dualpi2_enqueue(lq, cq, pkt) { % Test limit and classify lq or cq
>    2:    if ( lq.len() + cq.len() > limit )
>    3:      drop(pkt)                     % drop packet if buffer is full
>
> I have observed that the C queue, if it overflows, can induce drops on 
> L4S traffic even if the internal L queue is empty.  Is this intended 
> (or required) behavior?
>
> In the ns-3 implementation, we implement separate L- and C- internal 
> queues (i.e. not a shared buffer) and we implement limit:
>
>    15:   limit = MAX_LINK_RATE * 250 ms               % Dual buffer size
>
> as an aggregate limit on the overall queue as described in the 
> pseudocode, and also configure the internal L- and C-queue to the same 
> limit (assuming that one or the other queue could accept all of the 
> packets for the aggregate queue).
>
> I don't see anything in the normative part of the draft regarding limit.
[BB] 'limit' is specific to the example (pseudocode) implementation of 
dualpi2 in Appendix A, which was based on the reference Linux 
implementation that uses a shared buffer. If your implementation does 
not use a shared buffer, there's no need to implement line 15, or the 
condition to check that there's space in the shared buffer in line 2 
above. Instead, you would only need to check there is sufficient buffer 
space in the appropriate buffer that each packet is classified into.

>
> I see this discussion in Appendix A below Figure 4:
>
>    When packets arrive, first a common queue limit is checked as shown
>    in line 2 of the enqueuing pseudocode in Figure 3.  Note that the
>    limit is deliberately tested before enqueue to avoid any bias against
>    larger packets (so the actual buffer has to be one MTU larger than
>    limit).
>
> I am not sure how to interpret this, however.
[BB] I'm not sure which part you're not sure about. If it's the first 
sentence, I hope I've explained that above. I suspect it's the second 
sentence tho, cos I've just noticed that it leaves assumptions unstated...

...The assumption was that the packet would be classified and buffer 
space checked while temporarily holding the packet in the shared buffer, 
hence the need for limit to be 1 MTU less than the memory allocated to 
the buffer. Then, if the sum of the two queues plus the size of the 
arriving packet is greater than limit, the packet is tail-dropped.

As before, the assumption of a shared buffer is not a requirement, it's 
just an example.
Similarly for the assumption that the arriving packet is temporarily 
held in the shared buffer.

Would it be sufficient to add text to the Appendix to make these 
assumptions explicit, and to explain they are not requirements? Or do 
you think the example is problematic even if the implementation is using 
a shared buffer?

>
> Also, enqueue is not covered in the overload details that follow.
[BB] The first para of Appendix A.2 "Overload Details" says:

    The initialization and enqueue functions are unchanged.

This appendix concerns handling of overload by the AQMs. In our 
experiments, AQM drops kept queuing delay on target during persistent 
overload, so tail drop didn't happen. However, with a large and fast 
enough burst, I think tail drop will always be possible, which must be 
the case in the traffic scenario you are using.

>
> In summary, can you clarify what the normative (if any) or intended 
> behavior should be if an ECT(1) or CE packet arrives to a dual queue 
> whose internal C-queue has consumed the (aggregate) limit due to a 
> burst, if space in the internal L-queue exists?
In summary, there is no need to implement this test for the sum of both 
queues if you're not implementing a shared buffer.

Having separate buffers for the two queues will certainly prevent 
Classic overload leading to tail drop for L4S traffic. It's just a 
question (for the implementer) of whether it's (financially) worth 
allocating separate memory to isolate the L4S queue from a Classic 
burst, or whether the Classic AQM can be tuned to start dropping large 
Classic bursts soon enough so that Classic bursts into a shared buffer 
will rarely lead to (shared) tail-drop.

>
> 2) in Figure 4 dequeue logic:
>
>    5:        if ( ((lq.time() > T_time)              % step marking ...
>    6:              AND (lq.len() > T_len))
>    7:            OR (p_CL > rand()) )             % ...or linear marking
>
>
> shouldn't this be p_L instead of p_CL to match Figure 1 schematic?
[BB] No, p_L is intended to be the outcome of this OR, which is the 
implementation of the max() function in Figure 1 that combines p'_L and 
p_CL into p_L

BTW, max() can be implemented as a logical OR in this case, only because 
the native L AQM is a step function that outputs either 0 or 1.

If the L AQM were a ramp function, p'_L and p_CL would have to be 
combined into p_L with an actual max() function, not a logical OR. Then 
the pseudocode would become

    5:        p'_L = LLaqm( lq.time() );              % ramp marking ...
    6:        p_L = max(p'_L, p_CL)		% combining function
    7:        if (p_L > rand()) )             % ...or linear marking
    8:          mark(pkt)

This would be more general pseudocode for any combination of AQMs.
The pseudocode in the draft is really an optimization for the case where 
the native L AQM gives a binary output for p'_L.

However, I didn't want to write the more general code into the draft 
until we had fully tested a ramp AQM.

Cheers

Bob

> Thanks,
> Tom

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 9 Aug 2018 12:28:22 +0100

Tom,

I've written the following into my local copy of the draft, to be 
included in the next rev of the draft:

    When packets arrive, first a common queue limit is checked as shown
    in line 2 of the enqueuing pseudocode in Figure 3. Note that the
    limit is deliberately tested before enqueue to avoid any bias
    against larger packets (so depending whether the implementation
    stores a packet while testing whether to drop it from the tail, it
    might be necessary for the actual buffer memory to be one MTU larger
    than limit).

    Line 2 assumes an implementation where lq and cq share common buffer
    memory. An alternative implementation could use separate buffers for
    each queue, in which case the arriving packet would have to be
    classified first to determine which buffer to check for available
    space. The choice is a trade off; a shared buffer can use less
    memory whereas separate buffers isolate the L4S queue from tail-drop
    due to large bursts of Classic traffic (e.g. a Classic TCP during
    slow-start over a long RTT).

    Returning to the shared buffer case, if limit is not exceeded, [...]

You're right that it isn't at all obvious that the use of a logical OR 
on line 7 of the dequeue pseudocode (Fig 4) is the implementation of the 
MAX() function in Fig 1, even though we put the following text in the 
walk-through description:

       This logical 'OR' on
       a per-packet basis implements the max() function shown in Figure 1
       to couple the outputs of the two AQMs together.

This is a symptom of the stepwise evolution of the various parts of the 
spec. as we have generalized it from the original implementation. For 
the next rev, I'll take up your suggestion and change the pseudocode from:

to:

    5:        p'L = laqm(lq.time(), lq.len());        % Native L4S AQM
    6:        p_L = max(p'_L, p_CL);                  % Combining function
    7:        if (p_L > rand()) )                     % Linear marking

Then I'll give two examples (ramp and step) of the laqm() function in an 
additional figure. And I'll alter the walk-through text accordingly. I 
won't do this yet - I'll wait until ramp experiments are complete (I've 
put a "note-to-self" in the draft so I don't forget).

Status of ramp marking:

DCTCP is particularly sluggish when a new flow tries to push-in (which 
we found limited how fast paced chirping could push-in without building 
too much of a queue). For congestion avoidance in TCP Prague (and in an 
evolved DCTCP), by taking the step AQM out of the network, I am hoping 
that we can allow the sender to smooth the congestion signal faster than 
current DCTCP does.

With a step, you get long (often RTT-long) sequences of CE-marking, 
which IMO loses much of DCTCP's main advantage - using the extent, 
rather than the existence, of ECN marking. As a consequence, Current 
DCTCP has to use a moving average with very slow smoothing (the EWMA 
currently uses a weight of 1/16, so it takes around 16 RTTs to respond 
adequately to a change in congestion).

In ramp experiments so far, it's been tricky to get the operating point 
to stay on a ramp, but at least the CE-marking isn't as on-off as a 
step, so the sender's averaging can still be faster.

Bob

On 03/08/18 01:00, Tom Henderson wrote:
> Bob, inline below.
>
> On 08/02/2018 04:18 PM, Bob Briscoe wrote:
>> Tom,
>>
> (trimmed)
>> [BB] As before, the assumption of a shared buffer is not a 
>> requirement, it's just an example.
>> [BB] Would it be sufficient to add text to the Appendix to make these 
>> you think the example is problematic even if the implementation is 
>> using a shared buffer?
>
> Yes, your additional explanation above clarified it for me, so I agree 
> with your suggestion to clarify further in the appendix.
>>
>>
>>>
>> enough burst, I think tail drop will always be possible, which must 
>> be the case in the traffic scenario you are using.
>
> Yes, a large base RTT relative to the queue size.
>
>>
>>>
>> In summary, there is no need to implement this test for the sum of 
>> both queues if you're not implementing a shared buffer.
>>
>> burst, or whether the Classic AQM can be tuned to start dropping 
>> large Classic bursts soon enough so that Classic bursts into a shared 
>> buffer will rarely lead to (shared) tail-drop.
>
> OK, this clarifies it for me.  I don't see reference to the shared 
> buffer assumption in the draft so perhaps the implications of this on 
> the pseudocode could be pointed out in an additional paragraph?
>
>>
>>
>>>
>> implementation of the max() function in Figure 1 that combines p'_L 
>> and p_CL into p_L
>>
>> BTW, max() can be implemented as a logical OR in this case, only 
>> because the native L AQM is a step function that outputs either 0 or 1.
>>
>> combined into p_L with an actual max() function, not a logical OR. 
>> Then the pseudocode would become
>>
>> The pseudocode in the draft is really an optimization for the case 
>> where the native L AQM gives a binary output for p'_L.
>>
> Yes, I am using a ramp there.
>
> For consistency with Figure 1, and also the curvy RED example (uses 
> p_L), what about using p_L notation and your revised pseudocode above, 
> with line 5 instead reading:
>
>     5:       p'_L = f(lq.time(), lq.len()); % native L4S AQM
>
> and then mention that the simplest f() is a step (provided below) but 
> a ramp is possible
>
>     5:    p'_L = ((lq.time() > T_time) AND (lq.len() > T_len)) ? 1 : 0;
>
>
> - Tom