How do we handle 4 billion CRH-FIB entries ¿?

"Pablo Camarillo (pcamaril)" <pcamaril@cisco.com> Fri, 22 May 2020 11:00 UTC

Return-Path: <pcamaril@cisco.com>
X-Original-To: ipv6@ietfa.amsl.com
Delivered-To: ipv6@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E5DFB3A0B02; Fri, 22 May 2020 04:00:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.597
X-Spam-Level:
X-Spam-Status: No, score=-9.597 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com header.b=LvCwZ1H+; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=f+7UlhzN
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 x_226AMKAswX; Fri, 22 May 2020 04:00:22 -0700 (PDT)
Received: from alln-iport-7.cisco.com (alln-iport-7.cisco.com [173.37.142.94]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A52403A0AF9; Fri, 22 May 2020 04:00:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=10493; q=dns/txt; s=iport; t=1590145221; x=1591354821; h=from:to:cc:subject:date:message-id:mime-version; bh=juSGtXCWwwsDBWPcV1IvvHh/plzlSqFNV7vuB3S6LJs=; b=LvCwZ1H+lEaAG+JDMker7imz5ctkZBeylbRDsnEUbr7wsZ5RtNsZdOd5 /a6P30q1cYRKs0O2k1rBu073Ea9QwLBAfwCKClKjA9DjSj5J0jua8v+XK wZ66S7Yw9QknAOXxm3tTgxm2KM4nI0/zH1CmLw8XlvgNiJigK1n76ONyn I=;
IronPort-PHdr: =?us-ascii?q?9a23=3A/TW5wBCmbeezCE1qMGtqUyQJPHJ1sqjoPgMT9p?= =?us-ascii?q?ssgq5PdaLm5Zn5IUjD/qw03A3LQIPa8/9ezezbr/OoVW8B5MOHt3YPONxJWg?= =?us-ascii?q?QegMob1wonHIaeCEL9IfKrCk5yHMlLWFJ/uX3uN09TFZX8elvTunCoqzgfBk?= =?us-ascii?q?a3OQ98PO+gHInUgoy+3Pyz/JuGZQJOiXK9bLp+IQ/wox/Ws5wdgJBpLeA6zR?= =?us-ascii?q?6arw=3D=3D?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BvBwDxr8de/4kNJK1mgQmBR4ElL1E?= =?us-ascii?q?Hb1gvLAqHYAOhFYRmgS6BJANVCwEBAQwBAS0CBAEBhEQCghwkNQgOAgMBAQs?= =?us-ascii?q?BAQUBAQECAQUEbYVWDIV0AQMTGxMBATcBBA0BgQAmAQQBDQ0agwWBfk0DDiA?= =?us-ascii?q?BojcCgTmIYXSBNIMBAQEFhUEYgg4JgTiCY4lfGoFBP4FUgh+FPINFgi2OVIk?= =?us-ascii?q?0gS6JUJAhCoJUBJhynX6QTZ1hAgQCBAUCDgEBBYFTATeBVnAVO4JpUBgNkEw?= =?us-ascii?q?Xg0+KVnQ3AgYIAQEDCXyLdgGBDwEB?=
X-IronPort-AV: E=Sophos;i="5.73,421,1583193600"; d="scan'208,217";a="483213380"
Received: from alln-core-4.cisco.com ([173.36.13.137]) by alln-iport-7.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 22 May 2020 11:00:20 +0000
Received: from XCH-ALN-001.cisco.com (xch-aln-001.cisco.com [173.36.7.11]) by alln-core-4.cisco.com (8.15.2/8.15.2) with ESMTPS id 04MB0KcX025660 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Fri, 22 May 2020 11:00:20 GMT
Received: from xhs-rtp-002.cisco.com (64.101.210.229) by XCH-ALN-001.cisco.com (173.36.7.11) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Fri, 22 May 2020 06:00:20 -0500
Received: from xhs-aln-002.cisco.com (173.37.135.119) by xhs-rtp-002.cisco.com (64.101.210.229) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Fri, 22 May 2020 07:00:19 -0400
Received: from NAM10-MW2-obe.outbound.protection.outlook.com (173.37.151.57) by xhs-aln-002.cisco.com (173.37.135.119) with Microsoft SMTP Server (TLS) id 15.0.1497.2 via Frontend Transport; Fri, 22 May 2020 06:00:18 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=IvUy0ED0GQjxvpRnGvYVrHd2cXucq6R95zNU7gFANSQqLvy3OyPAEjCW8GHmBY1BQYTbl2IerEMEBEtJB3DenuGrI88H8jMxHhUAq7E0a5SVpD4ESXndG5KQyfNalH/7WI4iCl/zEoopnAeTot+FyENL7Qwtu9yPqiqm+VLBR//Qp0YorhfwXGc8pt5fpHFlERQBSMDHZ4ZFwIHaKXMrXvSf4MVc7/rQ5x2jF6cnogJkqlYJXGd+3kt9/XPsk3Fg5VJxcYnVwa3/QDABmGQhxTQRM92oisZVXnft6rR+/QbvJvwyvmvgW+glN+ouE7NyHDO6QlrHOireQdI9pTOKiw==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=8/30LIgSkrnA7Ky7sojWbfVV5gT1npQiGNovYwh0yQc=; b=fk13ZzE82wV+6tHE83uGEfz6qTj+kGdmPGI4FktMwHq36c6rYdzJ9rG+/BDxgLYltCfqwGcizSrZzGdE9bh1jfbk+6/Nqne40ROmzBTTDupZP4VdUh28E1WwJIGJrTXojVKQnkl8A88Nekct3HxGPRnDlVRh4z/W/pbo4yqTgNsaN1PO6uarAoZEOcwCx4Cuq5m55kpM7Ih1lUIsXYa3qug61hPEO6YurqzmGHQuikDs2EHpSwkaU6EhVx08HPsSrdp4241E6qGmFbrRuvO+kKWCzH3W4TCXHGrCvRwVLV6F5HoVknzpZSoRzV+t+xJ7W2BZxUQ/we70q+RsGmsmUQ==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=cisco.com; dmarc=pass action=none header.from=cisco.com; dkim=pass header.d=cisco.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cisco.onmicrosoft.com; s=selector2-cisco-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=8/30LIgSkrnA7Ky7sojWbfVV5gT1npQiGNovYwh0yQc=; b=f+7UlhzN+XRDRPF1GqYPJRpCKcng2akxu9yb8lwZOUr+t/UaDJXo7tdqEnVPkod9KPU/XzyfAOE3+pbc8e7xtEDLAxz/skS5TCwVzjW8iLiCaqTSuz3d6CZzHAV6p5/Ugj6tLxK8ViNpf+X+wQfeQbGlNbSlCgmHuM+gjcGUes4=
Received: from MWHPR11MB1374.namprd11.prod.outlook.com (2603:10b6:300:24::8) by MWHPR11MB2048.namprd11.prod.outlook.com (2603:10b6:300:27::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3000.26; Fri, 22 May 2020 11:00:17 +0000
Received: from MWHPR11MB1374.namprd11.prod.outlook.com ([fe80::3919:ef10:f837:9efc]) by MWHPR11MB1374.namprd11.prod.outlook.com ([fe80::3919:ef10:f837:9efc%9]) with mapi id 15.20.3021.027; Fri, 22 May 2020 11:00:17 +0000
From: "Pablo Camarillo (pcamaril)" <pcamaril@cisco.com>
To: "rbonica@juniper.net" <rbonica@juniper.net>, "draft-bonica-6man-comp-rtg-hdr@ietf.org" <draft-bonica-6man-comp-rtg-hdr@ietf.org>
CC: "6man@ietf.org" <6man@ietf.org>, Ole Troan <otroan@employees.org>, "Robert Raszuk" <robert@raszuk.net>
Subject: =?iso-8859-1?Q?How_do_we_handle_4_billion_CRH-FIB_entries_=BF=3F?=
Thread-Topic: =?iso-8859-1?Q?How_do_we_handle_4_billion_CRH-FIB_entries_=BF=3F?=
Thread-Index: AdYwJjh/R/k43WV0RIKSb2XOux8mcw==
Date: Fri, 22 May 2020 11:00:04 +0000
Deferred-Delivery: Fri, 22 May 2020 10:59:00 +0000
Message-ID: <MWHPR11MB13748B1068560BD2878C89CBC9B40@MWHPR11MB1374.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: juniper.net; dkim=none (message not signed) header.d=none;juniper.net; dmarc=none action=none header.from=cisco.com;
x-originating-ip: [173.38.220.57]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: f6a31a61-91e7-43ce-b270-08d7fe3f5032
x-ms-traffictypediagnostic: MWHPR11MB2048:
x-microsoft-antispam-prvs: <MWHPR11MB2048381E51D38E34EDCFDC8AC9B40@MWHPR11MB2048.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-forefront-prvs: 04111BAC64
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: lItKbH/NUjH+47d7wcB/F0hewKL8ci0goCEnkgmvT+5wgeiVPx1F726D1+JpgRsZSaW97jcwM/l4ApBuCbCsgyDzWuTreYKLbTjmx7hf2de0QiRmHuCqExIWIR7Obqkzl2Z6OWjuim40g0OOoEtZgIPtuSuIeYtk6Xwd8iUsPKiI5z03vZk+0S1jESgfiW83ukKXFPWRYyOIKlwUjUkrypwIBtgxNyRezulXM1NHVw3VQfPTCOsK3J3Wp7wgyzA9LA9uHWNGs/2TSrlkCJQSD1JDlTrRHvy5EoBDdi5M/xoEpEKOMT+hrRCtApJgEh6HGoKIKmA92Bm3s4yW5xg9ZHGsB8u51RteujvrJ5q47CylRXtpWlx+yWzXLiJuKdyndmX4JrRbpAqw0YcO/tZKQNtgiQBP+AXnHF7fsYnv1UeETjf2dOvAxa7ZPAAl4vtg
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MWHPR11MB1374.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(39860400002)(396003)(376002)(366004)(346002)(136003)(76116006)(66476007)(316002)(86362001)(6506007)(26005)(71200400001)(186003)(55016002)(66946007)(54906003)(110136005)(66446008)(64756008)(8936002)(66556008)(5660300002)(52536014)(7696005)(478600001)(6666004)(9686003)(2906002)(66574014)(4326008)(33656002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: agJH3mpGOwpgoigoK9+hK8GybVw+faImWvBFg6umhFRj5cJt/GuEMmZRm1XTCCrOovNtjyOfNrYUFuAwjayCFboL0OotoWEL4h4Rotn8Lmdz8tJIgiY22gIHvY0oK0aU2o1FAhu6oLHb53u2SUMUmPmnk8SasoGPeLooj/9lDiN8QRyjjK72Byd3I2e9kJt/3YeHydCmm0FIV8hJeRezRj+hIbBkqXgkhEg0vjjHkmw+gZdiblAn1qifXs4zOxHc6nMawWkF/+4mGclpKp2pADXi1I+rD5/XYlQJiEr4xx20r8iH2GXZw0wMg3lEF8ureYOHmtNLZlygRpfsEEtMiTPU5kse0GWIP462E70Eu1+iIa9OEO5oNEzzk72w0wkiHRhS78sr6KvuUxEjHNY9OQUyJC9dYmnmpY0LyqXXGN33sgt4dC78M7AQgkPEGlfqd2qsZjzuNhhbPltFBp1gDPJKmT2VhRU1LQrFqsJdjQ8=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_MWHPR11MB13748B1068560BD2878C89CBC9B40MWHPR11MB1374namp_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: f6a31a61-91e7-43ce-b270-08d7fe3f5032
X-MS-Exchange-CrossTenant-originalarrivaltime: 22 May 2020 11:00:17.7409 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 5ae1af62-9505-4097-a69a-c1553ef7840e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: XCXzE0JRM25APTfNKyAA0rHRlRFz23fHmjer7EkUEUBYvin+tu2F0V9xuFE3CSi4atIuA0Z9ejyTsWCQKUAQVg==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR11MB2048
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.36.7.11, xch-aln-001.cisco.com
X-Outbound-Node: alln-core-4.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/ipv6/jrt1JRmQ58vhm6GVx-7FmONYkx8>
X-BeenThere: ipv6@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "IPv6 Maintenance Working Group \(6man\)" <ipv6.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/ipv6>, <mailto:ipv6-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/ipv6/>
List-Post: <mailto:ipv6@ietf.org>
List-Help: <mailto:ipv6-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ipv6>, <mailto:ipv6-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 22 May 2020 11:00:27 -0000

Hi Ron, authors,

I've been reading the example you provided to Robert/Ole, and there's something concerning to me:

> Consider the following network:
>
>      -    Contains 65,000 routers
>      -    Each router has 500 directly connected neighbors or fewer
>      -    Uses 16-bit CRH
>
>In this network, each node might have 65,499 CRH-FIB entries:
>
>     -     64,999 CRH-FIB entries cause packets to follow the least-cost path to another node in the domain
>     -     500 CRH-FIB entries cause packets to traverse a specific link to a specific neighbor.

In addition, you've said several times that:
> Now recall that identifiers have node local significance

In summary:
You have 65000 routers in your network, and each router has 65499 "node-local" CRH-FIB entries.
In other words, this network has in total 4257435000 node-local CRH-FIB entries.

1.- How does it scale for an operator to configure on CLI more than 4 billion node-local CRH-FIB entries for the entire network?
2.- Assuming that some day in the future you would like to advertise this in the IGP: how is it going to deal with 4 billion node-local entries?

Also, you said:
> Somewhere in the network, there is an entity constructs the CRH and the list that it contains. That entity needs access to another data structure, that includes a global view of each node's CRH-FIB.

So, this entity needs a data structure with 4 billion node-local entries, and I guess some path computation algorithms with that scale...

Note that as per your explanation, we could configure the same CRH-FIB entry/tag on several nodes. However this changes nothing: as long as entries are defined as node-local you still have to deal with 4 billion.

In my opinion this is a fatal scalability problem.

Thanks,
Pablo.

PS. Those numbers are only assuming 65.000 routers; however as part of the 16b vs 32b the authors have stated several times the need to support more routers...