Re: APack async header compression
Mikkel Fahnøe Jørgensen <mikkelfj@gmail.com> Sun, 10 December 2017 17:24 UTC
Return-Path: <mikkelfj@gmail.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 706B0127868 for <quic@ietfa.amsl.com>; Sun, 10 Dec 2017 09:24:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.698
X-Spam-Level:
X-Spam-Status: No, score=-2.698 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, UNPARSEABLE_RELAY=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 jRA8RvhTN1U2 for <quic@ietfa.amsl.com>; Sun, 10 Dec 2017 09:24:21 -0800 (PST)
Received: from mail-it0-x231.google.com (mail-it0-x231.google.com [IPv6:2607:f8b0:4001:c0b::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E4BFC128BB6 for <quic@ietf.org>; Sun, 10 Dec 2017 09:24:20 -0800 (PST)
Received: by mail-it0-x231.google.com with SMTP id m11so9607624iti.1 for <quic@ietf.org>; Sun, 10 Dec 2017 09:24:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:in-reply-to:references:mime-version:date:message-id:subject:to; bh=MCa4LdC725bHbFp77O2hStD8Uyz/+8S4+1YKhDI1Aq8=; b=AxnzvYJkqB2ZntKnspbDT7V/YgqyzEE/Yq2iL/LY4HUxeOp9lSaKQxPcIfBsjFN1H2 EErMFcupqecYuxHY2MtKXqdoBMgyzyQXOG6pKKROIQkWtHWlKhDxJKRMs9sFJpcI/U3t 9AP5gJGMOyyrZQ9a85JOCfvNk9fpcNQG1d+CmF3cxxKm1GJngEC5XIgKhLWNUJAxfhMW XMBtP6OyuhhrwDWKQKRsBcZ5VrZcHQYc5hwOr1K38abCfQhx0SQcuNs5FVAadfYLA2Cu Jh/gIsvWhiqgsK4RhVG9HJJjtprMqkPS4m6IPhcq7wGRqp1pOMy3EGh+J2gQGt8yGP9h JDHA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:in-reply-to:references:mime-version:date :message-id:subject:to; bh=MCa4LdC725bHbFp77O2hStD8Uyz/+8S4+1YKhDI1Aq8=; b=fw1HSNmLI21uNDV2ekVA36j5YWOUCVdTyPkviL7kKQphz2KEd+H+DVFr/CwTOrU2DK N4m+zBeLLbNtvuTGIgBR14B17mVNsg5+iKA8OFxKmTR/BhRXSaDQRDvWmD+Z1C5+/hNW j4MlsxPqHZX2HD+taho3BV3BC1e3D5hbQV+ENEWkwAB4l6lJB+IAwyvPLHxw2pPr+8Ww ElnXf958QHlqeIejkTLT424fM4/aonqRhx2aGSvALvgd6HdgfnTRwh1PRItNzRMhV66S 4GGqu6Hd55beHvvByNWjJn7pu8b+UF0+VeO1SH873Y3xutrZbHivCMm+2K3gNjnJyaiI e4Tw==
X-Gm-Message-State: AKGB3mIG1TiVM5i+L7T6B6MFILh2cfC19OPiQoS7Y4E0hfjODMH9zgrn q7cFyhasdJHF0S7FI74JriobJ2Bh8tby3yTjKvw13A==
X-Google-Smtp-Source: AGs4zMZRibkbFUWC3ca852LnGfpVf2C5J2uItcaPey28+tgM7T3l1txcWqEqGa02CeWHxkXqrF9UB4Tdixm1gBvRYLg=
X-Received: by 10.36.103.213 with SMTP id u204mr14032515itc.91.1512926659984; Sun, 10 Dec 2017 09:24:19 -0800 (PST)
Received: from 1058052472880 named unknown by gmailapi.google.com with HTTPREST; Sun, 10 Dec 2017 09:24:19 -0800
From: Mikkel Fahnøe Jørgensen <mikkelfj@gmail.com>
In-Reply-To: <CAN1APddN=YZjnbmEoEvLN5cCY3iao8Kjj8WBa9sz+PevNVMPPA@mail.gmail.com>
References: <CAN1APdf2PEeErxCp8H62_BHG7EE07AX_HVj33xfCVtGg8bg8gw@mail.gmail.com> <CAN1APdeji70wu14OB7jEe+vQA98_8mJDZxhxtuMs2MVLx53PgQ@mail.gmail.com> <CAN1APddN=YZjnbmEoEvLN5cCY3iao8Kjj8WBa9sz+PevNVMPPA@mail.gmail.com>
X-Mailer: Airmail (420)
MIME-Version: 1.0
Date: Sun, 10 Dec 2017 09:24:19 -0800
Message-ID: <CAN1APdfZJ2axL2Z8RCnMbA3Lvto3BW715UoFqpWwjr584mjrJQ@mail.gmail.com>
Subject: Re: APack async header compression
To: IETF QUIC WG <quic@ietf.org>
Content-Type: multipart/alternative; boundary="001a114ab8d823c148055fffb024"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/OZRbTb_NwGeqVmxnCm9wvn_R1W0>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 10 Dec 2017 17:24:23 -0000
I had discussion on Slack and was requested to do a writeup on git. While doing so I realised that though bitmaps do work, they might not be the best way to go for this use case because timestamps can cover the same problem with less accuracy, and accuracy isn’t exactly needed when you cache data and don’t know when they might be needed next. Timestamps are often used in distributed garbage collection algorithms. So this resulted in APACK for timestamps. It turns out to be not very different from the ideas in QMIN, but it is also not exactly the same, but we are still trying to figure this out. A very rough first write up is placed on https://github.com/dvidelabs/apack while qmin is found at https://github.com/litespeedtech/qmin/blob/master/id-qmin.txt Kind Regards, Mikkel Fahnøe Jørgensen On 9 December 2017 at 10.34.57, Mikkel Fahnøe Jørgensen (mikkelfj@gmail.com) wrote: I forgot to mention that a receiver must defer decoding of dynamic name references until the EOX message has been received on the control channel, otherwise it might read stale data. It must also perform the dynamic name decoding before the next commit bitmap is send on the return control channel. This still leads to some degree of HOL, but only on low data volumes, and, the control stream could be given high priority. Note that even if there are no dynamic updates in an exchange, or if the sender chooses to send updated names as explicit names on the exchange specific stream as well, the dynamic table may still depend on earlier updates, so it is still not safe to decode until EOX has been seen. Some mitigations could be taken to reduce this dependency, but it does not appear to be worth the complexity, and possibly additional bandwidth requirements. The following is not exactly correct: "When this happens we xor the allocation bitmap into the free bitmap” what we actually do is to clear the bits in the free bitmap which are set in the allocation bitmap, which is then replaced with a new free bitmap snapshot. Kind Regards, Mikkel Fahnøe Jørgensen On 9 December 2017 at 00.54.11, Mikkel Fahnøe Jørgensen (mikkelfj@gmail.com) wrote: Minor correction: The receiver can include all entries with refcount zero because it only tracks what may be evicted, not what is evicted. Eviction happens when the sender does on actual allocation from the allocation map. What is correct though, is that we only need to scan for zero entries when we have are running short of things to allocate. Old text: Refcount zero entries are only evicted when space is needed, otherwise we loose the history needed for efficient compression. Kind Regards, Mikkel Fahnøe Jørgensen On 9 December 2017 at 00.15.01, Mikkel Fahnøe Jørgensen (mikkelfj@gmail.com) wrote: The receiver does not implicitly evict any dictionary entries and the sender does not evict any entries that do not have refcount zero. Refcount zero entries are only evicted when space is needed, otherwise we loose the history needed for efficient compression.
- APack async header compression Mikkel Fahnøe Jørgensen
- Re: APack async header compression Mikkel Fahnøe Jørgensen
- Re: APack async header compression Mikkel Fahnøe Jørgensen
- Re: APack async header compression Mikkel Fahnøe Jørgensen
- Re: APack async header compression Dmitri Tikhonov