Re: [Lsr] Flooding Topology Computation Algorithm - draft-cc-lsr-flooding-reduction-08 Working Group Adoption Call

Huaimo Chen <huaimo.chen@futurewei.com> Mon, 25 May 2020 01:28 UTC

Return-Path: <huaimo.chen@futurewei.com>
X-Original-To: lsr@ietfa.amsl.com
Delivered-To: lsr@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C80223A0C61 for <lsr@ietfa.amsl.com>; Sun, 24 May 2020 18:28:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.089
X-Spam-Level:
X-Spam-Status: No, score=-2.089 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_H2=-0.001, T_SPF_PERMERROR=0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=futurewei.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 ur5PpUHXK8Wl for <lsr@ietfa.amsl.com>; Sun, 24 May 2020 18:28:22 -0700 (PDT)
Received: from NAM11-CO1-obe.outbound.protection.outlook.com (mail-co1nam11on2095.outbound.protection.outlook.com [40.107.220.95]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B96663A0BD3 for <lsr@ietf.org>; Sun, 24 May 2020 18:28:22 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=JCjb/VysNy3rIoMADTMpd4fVsMYrFUEa784XLdsF/jX1aJx7d5G6vdgLlask3gOuGoID4wkhvYb/t2w+eEiyHPk8nfkRBsHMHoA67zC7tCohNlexZyqeh9jol6YhVflb6CipTIPxbHjqyjCeTkPImAUVzPmj0i2ndzvHnojwgXG6R9emlCjTlXBMGc5q6o4Uo/QFIrKIxH93ClhtgT2lJ/i/q4/A8Ws3BbDyIbdEmy9B9/do43ylJnfO5vdtpg2bkhoCqpPBqEdm+6vBQKZeTLy3SNw3HTdyz6LiAEVbulfctQlFcH3P6+hnF1rxizmiY3/835vAii4DlYziQ7i37Q==
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=VbwGLeVRRRVzbmuVQBHruGukJ2P/N7RrN2LN8SzBW8I=; b=WLNzvFkQgiyRbUiLdnPVYcclO0FJ6UA7pEIDUJXZBAqt/YPVi3fTri558GzXboyD/zfVRe3xwbvFiokgT0SgYlbiS+M+OQjxSkAuS5VWXAlKF1jDsWMK3tTBJZ9oeF682HJZb3r4RtIdBKVsUuTlDF8L8lXYeesBV2SHcwI35eBqMkP0IEr10ovIkJqBSvi+IPwxdbgL2F5/RNZflNsvu+S66HBqC8xcStMNI5qZMGSDVf7t3t/BOK/SbAGyVYnauaTsc8FZIgW6Cn8UhVmZ1ZN2Q60NnQcALxImR7/RCL39JxGPovOuPY5KsDYnQSG72bbEzCqxelE40Nz8Bid4qg==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=futurewei.com; dmarc=pass action=none header.from=futurewei.com; dkim=pass header.d=futurewei.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Futurewei.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=VbwGLeVRRRVzbmuVQBHruGukJ2P/N7RrN2LN8SzBW8I=; b=bO1GOy4zbxRjk0gIoqb4VnVUyn1e7KhnbRZ0z6zO5hJHiPHUzC49KSV6iICjJJb03s/baZYaP5wWGgkZWudO+bQi4hCNoDx2YxzoZ6um+7ML/AHnIKlD1m7LzxuPNWaHH8KhKqu3PAxsyMlJHHL6agEzGsGgzYokhxg8HoufrcU=
Received: from MN2PR13MB3117.namprd13.prod.outlook.com (2603:10b6:208:13a::20) by MN2PR13MB2879.namprd13.prod.outlook.com (2603:10b6:208:f3::27) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3045.9; Mon, 25 May 2020 01:28:18 +0000
Received: from MN2PR13MB3117.namprd13.prod.outlook.com ([fe80::d5b6:8550:9c40:eec2]) by MN2PR13MB3117.namprd13.prod.outlook.com ([fe80::d5b6:8550:9c40:eec2%7]) with mapi id 15.20.3045.009; Mon, 25 May 2020 01:28:18 +0000
From: Huaimo Chen <huaimo.chen@futurewei.com>
To: Gyan Mishra <hayabusagsm@gmail.com>
CC: "Acee Lindem (acee)" <acee@cisco.com>, "lsr@ietf.org" <lsr@ietf.org>
Thread-Topic: [Lsr] Flooding Topology Computation Algorithm - draft-cc-lsr-flooding-reduction-08 Working Group Adoption Call
Thread-Index: AQHWKvCWbO+rNwui80Sty0q3wo/aI6iuQDRQgAC6fICAAVrmiIAAx0uAgADIYX+AAL9sAIAAAVeagAA06ID//+MZAIAARoiA///qD4CAAHjEgIAAvJSBgAC7/oCAAyNr1A==
Date: Mon, 25 May 2020 01:28:18 +0000
Message-ID: <MN2PR13MB31170A83209564D545228B6EF2B30@MN2PR13MB3117.namprd13.prod.outlook.com>
References: <63330FD6-EDE8-4938-AA85-948279C57E34@cisco.com> <DM6PR06MB509842BA0E42A4938ACB2B94EEB80@DM6PR06MB5098.namprd06.prod.outlook.com> <CABNhwV3jQ=C6ynJBsKhJW_b=hkq7CKPFG2ci0vXE_0jZH9KtXQ@mail.gmail.com> <MN2PR13MB3117C43CA052E4E29D7428CBF2B60@MN2PR13MB3117.namprd13.prod.outlook.com> <CABNhwV2Y3kemTdHYBamZwAB+m5DefxqTC0shPan2cGHd9TARTg@mail.gmail.com> <MN2PR13MB3117E84C778B11D71FAF8135F2B70@MN2PR13MB3117.namprd13.prod.outlook.com> <CABNhwV1W3EDJpqUjLGj3-E-8L1R=75oAgtHX==9qkfrvrZy2ZQ@mail.gmail.com> <MN2PR13MB3117A5E68B341A203266C64AF2B70@MN2PR13MB3117.namprd13.prod.outlook.com> <CABNhwV3e_qm=RmTQyQ+yCWN+pt_d1Aw8-W9gkRwH+_kAyphu8Q@mail.gmail.com> <424B17B1-D66D-4708-A819-855E972841AF@cisco.com> <CABNhwV2cDoNotaePw30eZa5wE61NC_vh8cFaZHh_nPqs1ibFsg@mail.gmail.com> <E093695B-78DE-4332-B4E7-87343077624E@cisco.com> <CABNhwV1cfOE+trZGM-s44xU0su5RUgL2c7ubRCdc3EFCWsdujw@mail.gmail.com> <MN2PR13MB31179DB87C96DA218F9EB1D0F2B40@MN2PR13MB3117.namprd13.prod.outlook.com>, <CABNhwV0CC6wBrPkiA+vKjpX--JPBPfRzJ=0GDP3BqH4NPaecKQ@mail.gmail.com>
In-Reply-To: <CABNhwV0CC6wBrPkiA+vKjpX--JPBPfRzJ=0GDP3BqH4NPaecKQ@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: gmail.com; dkim=none (message not signed) header.d=none;gmail.com; dmarc=none action=none header.from=futurewei.com;
x-originating-ip: [2601:199:4300:8e5a:74ce:8eb8:ed16:ceb1]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 363b83c4-0176-41cf-cc0c-08d8004ae7a6
x-ms-traffictypediagnostic: MN2PR13MB2879:
x-microsoft-antispam-prvs: <MN2PR13MB2879EEA25C8596DD1C3CCB43F2B30@MN2PR13MB2879.namprd13.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-forefront-prvs: 0414DF926F
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: 2n4Kn+pJZkURC+IfdT1gVQjjNfjBpSceybxCqKSCDy13FEQie3saA1O+CmvUjqE28bgKZYaCQE8ml7Clf6yEngSnrhiQRHW2GlYXkf4x2wRfnHQk/6MoDC3onp+nhIA6iaOJjawG4WM/0WxwabiHWGv3ON+EeU8xd10hhVswqkiv5TaM8S0C1UpcmTTmbLEZGg8/FMw8wcAeDDVKDS1AvCnGgsye6yYDg7IZzT1ehwmkmB4RVgkEucI14vosOFoeT8vGaXiTawNLZzb2yZeVgO7EpJ9xYCTzMeHYiwHmU5IBuQb+yIQfQDFjcD9/IOxNM5rE8kW0NFeFbKF8QQndyQ==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MN2PR13MB3117.namprd13.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(396003)(136003)(39830400003)(346002)(376002)(366004)(52536014)(71200400001)(64756008)(66446008)(66476007)(76116006)(66946007)(55016002)(9686003)(19627405001)(66556008)(478600001)(186003)(53546011)(6506007)(316002)(7696005)(44832011)(4326008)(5660300002)(6916009)(2906002)(33656002)(86362001)(54906003)(8676002)(8936002); DIR:OUT; SFP:1102;
x-ms-exchange-antispam-messagedata: HsdYqaIAyQXOh8J4KfSYMcQEOTuhxzSLkWWyALZmYOQeQQ59KKbtLlsh4vdJo9KMyTRrEUIB/XilvvV6lxxYYhoSMycplAJZJtlTYBYmJWQXhNXxF9d9PjqdT/CSbg4p3muoGXUyV4AtH0ysKLDg8JkW7ayVuLdvYSMP/mF7fpOU9/eubRuclO0DathBZPXX3jh3RQdt91M+zKFXFJW+AR8totL4QJE42UfLJWUxfbf20mPupwkb5ABgzitFLUHlh7cvAt3WQk9gOhM7m9yyXT9b24zM5Lb1y9BkcPSJI/OgPs2/6zV1MjkF/r2Nd/+m0CrhKMIdQONwiO3BCwV0/LOh87aPEZjrRIpqnv6Bw7u8A8iuuErSIlGdvN5J0GgPNjQ0OnyjJJ7Yw3XwQRFPBKm5XSUzxN05zUPeb8ZCb7a/IFe8OWoGF7XexhdFvc2xqF/Pl2SiyLig+QAvq/TxFfbZl0SdX8BAs3CrmF9/Y5pGuvxADinNP1O4I/YWw5M62XFQk4h7zkeii9laGUvWK8bLGfn5ZU6jyDqz11tGg7F6WCLGWCZZU8kP/cjOmV+l
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_MN2PR13MB31170A83209564D545228B6EF2B30MN2PR13MB3117namp_"
MIME-Version: 1.0
X-OriginatorOrg: Futurewei.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 363b83c4-0176-41cf-cc0c-08d8004ae7a6
X-MS-Exchange-CrossTenant-originalarrivaltime: 25 May 2020 01:28:18.5753 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 0fee8ff2-a3b2-4018-9c75-3a1d5591fedc
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: oigEwAIoYKddmieQsm9/taA0v3Y7o8d/4kOmK3B4YfhcjUxWtLFPtYWin7gDm0ksePkE5Nl3ilbd5YsgmppdiA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR13MB2879
Archived-At: <https://mailarchive.ietf.org/arch/msg/lsr/PUKB-zHLV2OnUifE3Pq0zIceISc>
Subject: Re: [Lsr] Flooding Topology Computation Algorithm - draft-cc-lsr-flooding-reduction-08 Working Group Adoption Call
X-BeenThere: lsr@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Link State Routing Working Group <lsr.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/lsr>, <mailto:lsr-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/lsr/>
List-Post: <mailto:lsr@ietf.org>
List-Help: <mailto:lsr-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/lsr>, <mailto:lsr-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 25 May 2020 01:28:25 -0000

Hi Gyan,

    Thanks much for your questions. My answers/explanations are inline below.

Best Regards,
Huaimo
________________________________
From: Gyan Mishra <hayabusagsm@gmail.com>
Sent: Friday, May 22, 2020 8:41 PM
To: Huaimo Chen <huaimo.chen@futurewei.com>
Cc: Acee Lindem (acee) <acee@cisco.com>om>; lsr@ietf.org <lsr@ietf.org>
Subject: Re: [Lsr] Flooding Topology Computation Algorithm - draft-cc-lsr-flooding-reduction-08 Working Group Adoption Call

Hi Huaimo

Thank you for the slide deck.  That really helps understand the algorithm.

I will let you know if I have any questions.

The goal of the algorithm is to speed up convergence by limiting the convergence scope and expanding out 1 link at a time until all nodes and links are part of the flood scope.  From the examples in the slide deck I did not see mentioned what is done with the dynamic flooding algorithm where when you have a meshed network in the slide 5 examples, how do you limit the flooding on redundant links duplicate flooding with the many meshed paths as you iteratively grow the FT nodes scope Cq().  I believe with the dynamic flooding it does a degree of 2 so 2 links between nodes.
[HC]: The slide 5 example illustrates step 4 of the algorithm in section 4.1. When the algorithm reaches this step, all the nodes are  on the FT, but some of them may have degree of 1 (i.e., one link on the FT connected to the node). This step makes sure that every node on the FT has degree of at least 2.  It seems that the dynamic flooding expects the FT having its every node with degree of at least 2 for redundancy. In the Dynamic Flooding on Dense Graphs, link states will be flooded over the links on the FT. For example, for a node with degree of N (e.g., 3), when the node receives a link state from one link on the FT, it will flood the link state to the other N-1 (e.g., 3-1=2) links on the FT.

I think with clos spine leaf the mesh is much more intensive and problematic with ECMP then a circular topology nodal mesh that results in duplicate redundant flooding that slows down convergence.  With spine leaf it’s like an X horizontal width axis and then depth is spine to leaf links.  With spine leaf as you grow sideways and the spine expand the redundant ECMP grows and redundant flooding grows exponentially and is much worse then circular nodal mesh.
[HC]: In the slides, a full mess topology is used to illustrate the algorithm in some details. The algorithm can be used to compute FT for any other topology such as clos spine leaf. For topology with M (e.g., 100) parallel links between any pair of nodes X and Y, the algorithm will just add one link to the FT between X and Y, the other M - 1 (e.g., 100-1 = 99) links will not be added to the FT. Thus the link states will flood over only this one link between X and Y on the FT and will not flood over the other M - 1 (e.g., 100 - 1 = 99) links, which are not on the FT.

Thank you

Gyan