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.
- Fibonaccing CID lengths Dmitri Tikhonov
- Re: Fibonaccing CID lengths Mikkel Fahnøe Jørgensen
- Re: Fibonaccing CID lengths Christian Huitema
- Re: Fibonaccing CID lengths Dmitri Tikhonov
- Re: Fibonaccing CID lengths Kazuho Oku
- Re: Fibonaccing CID lengths Roberto Peon
- Re: Fibonaccing CID lengths Dmitri Tikhonov
- Re: Fibonaccing CID lengths David Schinazi
- Re: Fibonaccing CID lengths Marten Seemann
- Re: Fibonaccing CID lengths Mikkel Fahnøe Jørgensen
- Re: Fibonaccing CID lengths Dmitri Tikhonov
- Re: Fibonaccing CID lengths Christian Huitema