Re: [quicwg/base-drafts] Improve ACK_ECN frame encoding (e.g., use bit-vector) (#1439)

Kazuho Oku <notifications@github.com> Thu, 14 June 2018 00:59 UTC

Return-Path: <noreply@github.com>
X-Original-To: quic-issues@ietfa.amsl.com
Delivered-To: quic-issues@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 66DD2130EE1 for <quic-issues@ietfa.amsl.com>; Wed, 13 Jun 2018 17:59:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.009
X-Spam-Level:
X-Spam-Status: No, score=-8.009 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, MAILING_LIST_MULTI=-1, RCVD_IN_DNSWL_HI=-5, SPF_PASS=-0.001, T_DKIMWL_WL_HIGH=-0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=github.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Nzo-zg4LVOK0 for <quic-issues@ietfa.amsl.com>; Wed, 13 Jun 2018 17:59:13 -0700 (PDT)
Received: from out-3.smtp.github.com (out-3.smtp.github.com [192.30.252.194]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DDDFF128CF3 for <quic-issues@ietf.org>; Wed, 13 Jun 2018 17:59:12 -0700 (PDT)
Date: Wed, 13 Jun 2018 17:59:11 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=github.com; s=pf2014; t=1528937952; bh=gz/MC7CiveNZIPBDthLMq6EoO+TE5cgFaShzSXFnz3I=; h=Date:From:Reply-To:To:Cc:In-Reply-To:References:Subject:List-ID: List-Archive:List-Post:List-Unsubscribe:From; b=IvM5wdKbOzLVWmhqpOZg23agguGSSkoxyIqqJ5CG2Gf6UFUbQd/sC9/9Ls5kCzOBb KxNcEWjQnnUxS7DYr33SoBJcWhqpasLrsx9lggp9QRctIuASEX+CAx1H9/8ZAVL5C/ tzmp4s1VAPUD6XUH44eE6Emq1lnmo5un3zc4TuC0=
From: Kazuho Oku <notifications@github.com>
Reply-To: quicwg/base-drafts <reply+0166e4aba31fb27d063a727fa07ddf99e16b667dbef7871692cf0000000117397fdf92a169ce13c0caa7@reply.github.com>
To: quicwg/base-drafts <base-drafts@noreply.github.com>
Cc: Subscribed <subscribed@noreply.github.com>
Message-ID: <quicwg/base-drafts/issues/1439/397133920@github.com>
In-Reply-To: <quicwg/base-drafts/issues/1439@github.com>
References: <quicwg/base-drafts/issues/1439@github.com>
Subject: Re: [quicwg/base-drafts] Improve ACK_ECN frame encoding (e.g., use bit-vector) (#1439)
Mime-Version: 1.0
Content-Type: multipart/alternative; boundary="--==_mimepart_5b21bddfebea0_2d922ac14f502f541141b8"; charset="UTF-8"
Content-Transfer-Encoding: 7bit
Precedence: list
X-GitHub-Sender: kazuho
X-GitHub-Recipient: quic-issues
X-GitHub-Reason: subscribed
X-Auto-Response-Suppress: All
X-GitHub-Recipient-Address: quic-issues@ietf.org
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic-issues/z3ytkDlTtwZuRJXozP3F3VZ5qYg>
X-BeenThere: quic-issues@ietf.org
X-Mailman-Version: 2.1.26
List-Id: Notification list for GitHub issues related to the QUIC WG <quic-issues.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic-issues/>
List-Post: <mailto:quic-issues@ietf.org>
List-Help: <mailto:quic-issues-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 14 Jun 2018 00:59:15 -0000

@gloinul 
>> The core idea here is to use that mechanism to determine if a PN with the CE bit set is acknowledged for the first time. Use of a bit-vector is one of the possible approaches.
> 
> But, that doesn't work unless you are able to ACK each duplication in separate ACKs, as well as having no redundancy in the ACKing. I think that will make QUIC work very poorly if any ACK packet loss is experienced. There need to be some redundancy to ensure that ACK loss, doesn't equal forward loss from the senders perspective.

I do not see why you think that it does not work when folding duplication into single ACK. That is something that should have been handled by existing implementations. Folding of the CE bit is a natural extension to that. If I sounded like there would be no deduplication on the receiver side, then I apologize. The requirement to send exactly which PN arrived to with the CE bit _enforces_ the receiver to deduplicate using the ACK queue.

Re your second point, the proposed encoding does work under loss, because the sender can tell exactly which newly acknowledged packet was received by the peer with the CE bit set.

Consider the case you are sending an ACK_ECN frame for PN 2,3,4 where 3 had the CE bit. The bit vector of the ACK_ECN frame will be 010. When the ACK_ECN frame is retransmitted, the bit vector will once again contain 010. Either of the two ACK_ECN frames that first reaches the sender will be considered as the frame that newly acknowledges PN 3, and the CE bit will be taken into consideration.

If the receiver has no duplication detection and an attacker injects a duplicate of packet 4 with CE bit set, the receiver will send ACK_ECN frame with the bit vector set to 011. If that packet reaches the sender first, the sender will take that bit into consideration.

However, this is not an issue. It is just that where deduplication is applied is changing from the receiver to the server. And as stated in my first comment, detecting duplication on the sender side is a better guard against an injection attack, because the sender has the logic to recognize an acknowledgement at most once for every one packet it sends, whereas it is hard to implement such complete guard on the receiver side.

> I don't see that working reliably during capability checking, especially not when we add ECN black hole mitigation into the mix. It is the sender that knows which of the packets that are marked during the capability check. If all packets are marked, then yes a trustworthy receiver could detect bleaching. But then we need a signal where the receiver tells the sender to stop mark.

Sorry for my confusion. Bleaching here is the term that means ECN-CE turning into ECN-CT(0) or ECN-CT(1).

For that case and also for blackhole detection, what you would do in the proposed encoding scheme is this:
* sender remembers in it's inflight packet map which packets were sent with ECN or with the CE bit set
* if sender receives an ACK frame or an ACK_ECN frame that does not indicate that packet had the CE bit set, bleaching is happening
* if sender detects loss of the packet that was sent with ECN, there is a blackhole

As you can see, support for ECN can be nicely tied to the inflight packet map and the detection of issues become accurate, if we allow the receiver to send back exactly which packet was received with the CE bit set.

Note that we do not even need to have a separate phase for detecting these issues. Sender can just periodically send packets with CE bit set, and ignore the signal from receiver expressing that a certain packet was received with the CE bit set, if that packet was sent with the CE bit set. Or if the sender detects a consecutive loss of the packet that had the CE bit set, there is a blackhole.

And, thank you for the strawman. My comments in-line.

> My strawman if one like to address providing more detailed information on which packets are CE marked, ensure robustness around recovery periods and ensure that sender side verifications work is the following:
> * Receiver side suppression of duplicates

A limited form of that is inherently part of the bit-vector-based approach. Please see the first lines of this comment.

> * An ACK format for ECN where
>     * ECT(0) and ECT(1) are counters. However, they are variable encoding only the least number of bits needed to detect roll over, i.e. receiver track ACKs of ACKs to determine how many bits this needs to be.

Assuming that the sender needs to know the breakdown of the number of packets received without the CE bit set, I would prefer sending that information rather than using a counter, because it simplifies (or eliminates the need for) the logic to detect bleaching / blackhole.

>     * ECN-CE marks as bit-vector. Only needing to go as far back as there are CE marks. i.e. bit-vector may be shorter than full PN space covered by ACK. Truncation can be considered.
> * ACKs are assumed to have redundancy, either all the way to latest ACK of ACKs or at least across the last couple of ACKs.
> * ACK loss handling for when there are wholes in ACK information received by the sender due to ACK loss and ECN-CE vector truncation. This is to handle continuous verification. ACK holes will trigger loss response also.

I can understand the tendency to have those requirements.



Having all that said, let me propose another encoding, that IMO will have all the properties both of us have been looking for. How about expressing ECN information the same way we express gaps?

In the current draft, ACK Block is a repetition of two types of "blocks": PNs that are acked and PNs that are not acked (i.e. gap). We can extend it to express 5 types of "blocks": non-ECT acked, ECT(0) acked, ECT(1) acked, ECN-CE acked, gap.

In the approach, the definition of ACK Block will become:

```
 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Block (i)                        ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The value of the Block will be calculated as:
block_mode = gap (0), non-ECT (1), ECT0 (2), ECT1 (3), ECT-CE(4)
block_size = the number of contiguous PNs that were received (or not) under the block_mode
block_value = ((block_size - 1) << 3) | block_mode
```

For example, ACK frame that is encoded as `04 00 03 0a 00 04` means:
* Largest Acknowledged: 4
* ACK Delay: 0
* ACK Block Count: 3
* first Block (0a): PN 4 and 3 received with ECT0
* second Block (00): gap for one packet
* third Block (04): PN 1 received with ECT-CE

The benefits of this encoding are:
* sender will have complete information on how the packets were received
    * therefore it is easy to see if there is bleaching / blackhole (see the discussion above)
* the overhead of sending ECN information is as same as sending gap
    * therefore the overhead will be a non-issue, assuming that ECN bit flips will happen as likely as gaps will appear on ECN-unaware networks
* no *additional* overhead for supporting ECN
* only one ACK frame type
* definition of the ACK frame becomes simpler!

The downside is that a single-octet Block can only express up to 8 packet numbers, because block_mode takes 3 bits and the varint length bits take 2 bits. I do not think that is an issue considering the fact that the ACK_ECN frame proposed in #1372 increases the size of an acknowlegement by at least 3 octets. But if we want to optimize, we can adopt the PN encoding used in the packet header.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1439#issuecomment-397133920