IETF Logo Mail Archive

Re: [Ideas] Computing collisions

Dino Farinacci <farinacci@gmail.com> Wed, 14 December 2016 04:33 UTC

Return-Path: <farinacci@gmail.com>
X-Original-To: ideas@ietfa.amsl.com
Delivered-To: ideas@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id F3295129562 for <ideas@ietfa.amsl.com>; Tue, 13 Dec 2016 20:33:26 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 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, 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=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 gX8jpk9rOWjv for <ideas@ietfa.amsl.com>; Tue, 13 Dec 2016 20:33:25 -0800 (PST)
Received: from mail-pg0-x242.google.com (mail-pg0-x242.google.com [IPv6:2607:f8b0:400e:c05::242]) (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 7622612948E for <ideas@ietf.org>; Tue, 13 Dec 2016 20:33:25 -0800 (PST)
Received: by mail-pg0-x242.google.com with SMTP id 3so1013593pgd.0 for <ideas@ietf.org>; Tue, 13 Dec 2016 20:33:25 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=69wkSBVZXI18bfkER8HaN/kag4nC4YFe8pkJ7LAYTWY=; b=v5/xrUQv2jK0+SEwtQGoIAEjOh871ylW/gpq7v80uNw+4yvirmevjxfXtefJSzB/cd Z9drcYvTlcsJCy0+V3VCefSmLvkHuw4FD190WMswb0jW3x6687MTIZrf1MCKdSCbFy+b yKO0/ej+p98lCWlNq9wScyStoKANZPnGDL/BrQq0VkA9k6jU2jU20lRtCrS8lCMP24v8 EV67quVOBcRqWsZLbr3WQ9L3kPEQTR2fOeargWI5BM4gx8W+/mClaynWQGOGuLrCQJzY 1ZvgYrnJsUxJxvHuHs51ioOaiQe9tfLbMS0ToAC/eFo3Wwi012qlOBVMI0kUZJDjvB2G HwwA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=69wkSBVZXI18bfkER8HaN/kag4nC4YFe8pkJ7LAYTWY=; b=ASlh503892y//uYQcpdgRVhUGxAi/unlnY02t2uX9PCKPMZ4N9lcnOX9xSSxRJ71+T AP5UXP7K0S544hSw/lE+Upic1mbgPrlef4iCJGAphzJf8zVtb/lx6XJUq4qKXiZuzcTc mERVsECegRjnN3gPoiDSqdsciNUYl6vvRB5vMeLEJLOLeouLaXVFIKqXCl3kyl3hnPGb 0HP1bk0fPyUKJrLNflPMn/NzgrReATRuNpvvrcMeyyt9u7G5+EZAoPe4MFevDEwP9+ED /ENeEZg4enmIW/BH+9kmC1CeGL8EPFu5cwAj1qgQezVw2A2Qhvty+ZYV3gjydqvec9H9 CTkQ==
X-Gm-Message-State: AKaTC016mzt34IztqYg+DsYnzDaoilSgZ60fbjnbybbIm6RVFeJG58QGUHjvOl//vWiGEA==
X-Received: by 10.84.197.1 with SMTP id m1mr204814104pld.159.1481690005096; Tue, 13 Dec 2016 20:33:25 -0800 (PST)
Received: from ?IPv6:2603:3024:151c:55f0:945:7274:9118:f6b4? ([2603:3024:151c:55f0:945:7274:9118:f6b4]) by smtp.gmail.com with ESMTPSA id x4sm83708385pgc.14.2016.12.13.20.33.23 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 13 Dec 2016 20:33:24 -0800 (PST)
Content-Type: text/plain; charset="us-ascii"
Mime-Version: 1.0 (Mac OS X Mail 10.1 \(3251\))
From: Dino Farinacci <farinacci@gmail.com>
In-Reply-To: <CALx6S37G5xc48a3sxCAq5Qm7z7sBhcUF5+i_buBA_2yBMrtZ7w@mail.gmail.com>
Date: Tue, 13 Dec 2016 20:33:23 -0800
Content-Transfer-Encoding: 7bit
Message-Id: <F8E2C071-6F73-46C0-9833-40CB7561D500@gmail.com>
References: <fb888f85-22ed-5e87-bf84-2b6244d587e6@htt-consult.com> <CAG-CQxqds9osqTTAi_Gm-VCVKGo49pW5OVALxYiYCrqNQ2yvRA@mail.gmail.com> <83be2a30-1b46-2397-976e-6e2736921e19@htt-consult.com> <6AA7A937-AEC5-4E6F-9D87-87BC257EF9F8@gmail.com> <CALx6S37G5xc48a3sxCAq5Qm7z7sBhcUF5+i_buBA_2yBMrtZ7w@mail.gmail.com>
To: Tom Herbert <tom@herbertland.com>
X-Mailer: Apple Mail (2.3251)
Archived-At: <https://mailarchive.ietf.org/arch/msg/ideas/ggmRwZbr6MyXTscCkk5hEmedRlg>
Cc: Padma Pillay-Esnault <padma.ietf@gmail.com>, Robert Moskowitz <rgm-ietf@htt-consult.com>, ideas@ietf.org
Subject: Re: [Ideas] Computing collisions
X-BeenThere: ideas@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: "Discussions relating to the development, clarification, and implementation of control-plane infrastructures and functionalities in ID enabled networks." <ideas.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/ideas>, <mailto:ideas-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/ideas/>
List-Post: <mailto:ideas@ietf.org>
List-Help: <mailto:ideas-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ideas>, <mailto:ideas-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 14 Dec 2016 04:33:27 -0000

> That sounds a lot like what we do in ILA. The identifier is split into
> a registry number and identifier within that. In our case each host is
> assigned a unique 24 bit registry number, and then each host can
> independently create identifiers. For the latter we just take a
> timestamp. Assuming a rate of 100 identifiers per second being
> allocated we have 21.8 years before wraparound (described appendix B
> of ILA draft). We'll also check when the identifier is registered with
> the map system, but in this case collisions should pretty much be
> nonexistent.

A good algorithm. Nice job.

Dino

v2.23.0 | Report a Bug | By Email