Re: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04

"Gengxuesong (Geng Xuesong)" <> Mon, 11 May 2020 13:17 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 7DB463A0ABE for <>; Mon, 11 May 2020 06:17:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id F5A5CcRPuqqy for <>; Mon, 11 May 2020 06:17:33 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 278013A0B1B for <>; Mon, 11 May 2020 06:17:25 -0700 (PDT)
Received: from (unknown []) by Forcepoint Email with ESMTP id DEC2460AC3A5EB02C9D0 for <>; Mon, 11 May 2020 14:17:22 +0100 (IST)
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1913.5; Mon, 11 May 2020 14:17:21 +0100
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256) id 15.1.1913.5; Mon, 11 May 2020 21:17:19 +0800
Received: from ([]) by ([]) with mapi id 15.01.1913.007; Mon, 11 May 2020 21:17:18 +0800
From: "Gengxuesong (Geng Xuesong)" <>
To: "" <>
CC: "" <>, "" <>
Thread-Topic: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04
Thread-Index: AdYlyowYbZl6t8IpSKWUsfFF00+SFQAGECIAAGyWhIA=
Date: Mon, 11 May 2020 13:17:18 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: zh-CN, en-US
Content-Language: zh-CN
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/related; boundary="_004_5fae04a3f0c5429f84af69f3ba001abfhuaweicom_"; type="multipart/alternative"
MIME-Version: 1.0
X-CFilter-Loop: Reflected
Archived-At: <>
Subject: Re: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Link State Routing Working Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 11 May 2020 13:17:37 -0000

Hi Tony,

Thank you for giving detailed proof, and it is very helpful to understand the mechanism.
As I understand, it is showed in the proof that if there is proper temporary flooding in R = E - E* - E’, same connectivity could be achieved by the flooding topology F’ just as G’. I agree with this.
The problem for me now is how to enable the temporary flooding properly.
Here is an example:
The solid line presents the physical link inside flooding topology, and the dashed line presents the physical link out of flooding topology.
From the view of me, when multipoint failure happens, node 3 is supposed to enable the temporary flooding between 3 and 4, in order to connect with the nodes inside the red box, while the other dashed line between node 1 and node nobody is not supposed to do temporary flooding although node 1 is connected to the failed link directly.
It seems a little unclear for me about how the node itself could decide whether a dashed line should do temporary flooding or not in this case.

Best Regards

From: Tony Li [] On Behalf Of
Sent: Sunday, May 10, 2020 1:18 AM
To: Gengxuesong (Geng Xuesong) <>
Subject: Re: [Lsr] Questions about draft-ietf-lsr-dynamic-flooding-04

Hi Xuesong,

Thank you for your work about Flooding Reduction mechanism. I think it is very useful for IGP scalability.

Thank you, we very much appreciate that.

When Sarah giving presentation for draft-chen-lsr-dynamic-flooding-algorithm-00 in LSR interim meeting, I raised a question about how to handle multipoint failure in the flooding topology. I remembered that draft-ietf-lsr-dynamic-flooding-04 was mentioned. I have read this draft, especially section 6.8.11 and temporary flooding relevant content. I think it is a valid method logically. (We have tried to raise some examples to challenge this method, but in all these cases, this method works) Considering that reliability of IGP is crucial for deployment, we are still wondering whether some mathematical proof is necessary (or possible) to guarantee that, in all the possible scenarios, proper convergence could be achieved when using flooding reduction algorithm, just as traditional IGP mechanism. The proof may be case by case depending on the flooding reduction algorithm, but we think even some example or clue about how to do this will be very helpful.

A proof? Ok, I can try to be rigorous, but it’s been a very long time. I apologize in advance to Kireeti, Mr. Myers, Mr. Douglas, and Prof. Greever for what follows.

Definition: Let G=(V, E) be a finite graph. F=(V, E’) is a ‘flooding topology’ on G if E’ is a subset of E and F is connected.

We normally have other properties for flooding topologies, such as being bi-connected, relatively sparse, minimal diameter, and minimal degree, but those properties are not relevant for this proof.

Definition: Let C=(V*, E*), V* a subset of V, E* a subset of E, be the ‘cut’ of G. This represents the failures in the topology. Let G’ = G - C, the topology after failure, and let F’ = F - C, be the flooding topology after failure.

Definition: Let R = E - E* - E’. This is the set of 'recovery edges': edges that have not failed and are not part of the flooding topology.

Corollary: R is finite.

Proof: G is finite, by definition. Therefore E is finite, E* must be finite, and E’ is finite.

Lemma 1: If G’ is connected, then F’ + R is connected.


G’ = G - C = (V, E) - (V*, E*) = (V - V*, E - E*).

F’ + R = (F - C) + (E - E* - E’) = (V, E’) - (V*, E*) + (E - E* - E’) = ( V - V*, E’ - E* ) + ( E - E* - E’) = ( V - V*, E’ - E* + E - E* - E’ ) = ( V - V*, E - E* - E* ) = ( V - V*, E - E* ) = G’.


Lemma 2: If G’ is connected, then incrementally adding edges from R to F’ will yield a connected flooding topology.

Proof: By induction. Let R’ be a subset of R. Induction property: Either F' + R’ is connected, or R’ is a proper subset of R.

Base case: R’ is the empty set. If F’ is connected, then F’ + R’ is connected and the property is satisfied. If F’ + R’ is not connected, R’ is empty, which is a proper subset of R.

Induction case: Let r be a recovery edge in R - R’ (i.e., a new edge to add).  If F’ + R’ is connected, then the property is satisfied already. If F’ + R’ + r is connected, the property is satisfied. If R’ + r = R, then by Lemma 1, the property is satisfied. Otherwise, R’ + r != R, and the property is satisfied. By our corollary, the induction must terminate.


Bugs, questions, and comments are welcome.