Fibonaccing CID lengths

Dmitri Tikhonov <dtikhonov@litespeedtech.com> Wed, 22 May 2019 14:12 UTC

Return-Path: <dtikhonov@litespeedtech.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 7AA71120033 for <quic@ietfa.amsl.com>; Wed, 22 May 2019 07:12:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=litespeedtech-com.20150623.gappssmtp.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 BI3M2663c1m1 for <quic@ietfa.amsl.com>; Wed, 22 May 2019 07:12:47 -0700 (PDT)
Received: from mail-qk1-x729.google.com (mail-qk1-x729.google.com [IPv6:2607:f8b0:4864:20::729]) (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 4471F12004F for <quic@ietf.org>; Wed, 22 May 2019 07:12:46 -0700 (PDT)
Received: by mail-qk1-x729.google.com with SMTP id z128so1549914qkb.6 for <quic@ietf.org>; Wed, 22 May 2019 07:12:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=litespeedtech-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:subject:message-id:mail-followup-to:mime-version :content-disposition:user-agent; bh=MlHCW3JoS/VEdAfqnBa6PX37/ILvL0Jmvt0Jsts7k70=; b=0P35hiRqVzyGEZ4xHwNtmZwW4YkWbz9JHkzI/mNbfqeFldUz2ym3YcAciVc3Ve+erd BofejR0yokQO9X1qjEjjf5zLnS/DfPV+SpBEdcMIm2A22giVYb5u/nhPMt5ZRknJHuQH L13J1CK5kke3fMcG/kmssgtCSFf9xbCj92Av4+/uPdVs/2u1MReneuwp+1GNHOpbpkNt Y5H0kWjUvfe4vkBrnmA6DURnps7jvDqmkHmDecyxiD2ogZit8ofPlfQZB/AnHewuEgnf CXEY3Ma8haWco0ybBXZC7RGUcws6JMCCxWxwiu3cIgvczqxuqAXIY4PwKhv9oAGaHYfv W+CQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:mail-followup-to :mime-version:content-disposition:user-agent; bh=MlHCW3JoS/VEdAfqnBa6PX37/ILvL0Jmvt0Jsts7k70=; b=R6ahmEN7dW0F4XGqyLsTMTk/nsgn6IMOpltZTmCGBp734gzNCDzaTeYfkLH6EwgyCf 0hifsuy5+GzagAcbf5EWIDgZSgM4n6lCo9jOxh25S/J4J/dH1kTLWEDHl8o9v01Z3Vsr MEjNwhG5jSX3nFH6NLvv2bsmzxTyuphDwZtUnUgQs3b3jebF4ywKJb2nqypCsZLlQbI/ vlRKG61H69LvcwQC30kLjUSZEk9XXpOPRQ/uO2WEUDeAyX9I7taIoerZ3QyIQNmmSnR+ XsN2hH4fzCUxYuF9dv/NveK87GkiUznba2chXHLsnbOs6EoXoGcceJ2gKmFyXsTBAHGZ mOHg==
X-Gm-Message-State: APjAAAVwPj6tsm3eE8MMLkjhYGr0sgQGO9s+dRkrEjc8bTbKo3s3tMaD oZGVQoIUlWRR2Et72d1638Ju5BY3g9c=
X-Google-Smtp-Source: APXvYqye8nF4Yi3X9H6uQpEM0Yy5kjC9CAIDeKinMOvSW6LpJeIfPgRg1maOn4QDbn0UbBXweIgKvQ==
X-Received: by 2002:a37:a8d7:: with SMTP id r206mr56634772qke.264.1558534365083; Wed, 22 May 2019 07:12:45 -0700 (PDT)
Received: from ubuntu-dmitri (ool-44c1d219.dyn.optonline.net. [68.193.210.25]) by smtp.gmail.com with ESMTPSA id t58sm13474721qtj.4.2019.05.22.07.12.44 for <quic@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 22 May 2019 07:12:44 -0700 (PDT)
Date: Wed, 22 May 2019 10:12:39 -0400
From: Dmitri Tikhonov <dtikhonov@litespeedtech.com>
To: IETF QUIC WG <quic@ietf.org>
Subject: Fibonaccing CID lengths
Message-ID: <20190522141238.GA23472@ubuntu-dmitri>
Mail-Followup-To: IETF QUIC WG <quic@ietf.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
User-Agent: Mutt/1.5.24 (2015-08-30)
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/iuTyOr_83o9q0RUPoiIblScoqMc>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.29
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: Wed, 22 May 2019 14:12:48 -0000

Idea: we can keep the one-byte SCIDL/DCIDL field but map the 4-bit
parts to a larger range of values.  For example, we could map the
16 values to a range of Fibonacci numbers:

    0   ->  0
    1   ->  1
    2   ->  2
    3   ->  3
    4   ->  5
    5   ->  8
    6   ->  13
    7   ->  21
    8   ->  34
    9   ->  55
    10  ->  89
    11  ->  144
    12  ->  233
    13  ->  377
    14  ->  610
    15  ->  987

This particular mapping has several profitable properties:

    - It covers the whole range of values from zero to the
      practical maximum imposed by the protocol (about 1K).

    - There is a good selection of small values.

    - 8 is one of the values, convenient for storage in
      uint64_t.

    - Each step up is not too large (double or more) or too
      small (less than 50% increase).

    - The mapping can be easily generated: its name says how.

  - Dmitri.