Hi Tony, The algorithm/procedure proposed is to determine the exact links on a backup path for a failure on the FT. For example, for the failure of a link between node A and node B on the FT, the backup path for the link computed is deterministic and the same even though there are many links attached to every node. The start point and end point of the backup path are deterministic, and are the node with smaller ID and the node with larger ID respectively. The backup path is the path with minimum number of hops from the start point to the end point, wherein whose links are not on the FT. When there are multiple paths with the same minimum number of hops, only one of them is selected deterministically. Since the nodes on the backup path for the failed link get this same backup path and enable the temporary flooding over the links on the path, this path connects the two end nodes of the failed link on the FT. When the FT is split because of this failed link and others, this path fixes the FT split.
Best Regards, Huaimo From: Tony Li [mailto:[email protected]] On Behalf Of [email protected] Sent: Monday, April 1, 2019 12:50 PM To: Huaimo Chen <[email protected]> Cc: [email protected] Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology Hi Huaimo, Thank you for your note. I have many questions, please see inline. When multiple (i.e., two or more) failures on the current flooding topology (FT for short) happen at almost the same time, the FT may be split even though the real network topology is connected. A solution or procedure for fixing the FT split is described below. It uses almost the minimum number of links, and is triggered by the multiple failures. When the multiple failures on the FT occur, a backup path for each of the failures is computed, wherein the links on the backup path are not on the FT. The links on the backup path are temporarily added to the FT (i.e., the temporary flooding is enabled on the links on the backup path). Thus the split FT is connected by the backup paths. When any node N detects the multiple failures on the FT, it computes a backup path for each of the failures. If it (i.e., node N) is on the backup path, it adds its local links (e.g., local link L1 and L2) on the backup path to the FT temporarily; otherwise, it does not do anything. What you seem to be suggesting here is a distributed algorithm. Each node is going to do this computation independently. In a dense network, there are going to be many possible ways of repairing the flooding topology. For example, if the base topology is a complete graph (e.g., a full mesh), then every node in the graph can provide at least one link that will help restore the flooding topology. Which ones should be used? We agree that some links should be enabled, and that’s what’s currently in the draft. We do not today have a constructive algorithm to select exactly which links to enable. If you have such an algorithm, that would be a welcome contribution. A centralized algorithm for this is hard because the FT is partitioned. While we could do some computation, we could only easily communicate that to one partition of the FT. A distributed algorithm that does not enable unnecessary links also seems hard. How do all nodes make this same decision? Even a first order approximation to a solution would be an improvement. But we very much need specifics. And the algorithm needs to address general topologies. For a failure on the FT, the backup path computed by any node N needs to be the same. Suppose that the two end nodes of a failed link L on the FT is A and B, and A's ID is smaller than B's. Node N computes a path from A to B with minimum hops and whose links are not on the FT. This path is a backup path for link L. When every node on the backup path computes a backup path in this way in parallel, the same backup path is obtained, and used to fix the FT split. In most dense topologies, we should be able to repair the FT with the addition of a single link. Thus, we have many single hop candidates. Which one do we select? Since we have had at least a double failure, we know that two links have failed. Without loss of generality, suppose that these were the links AB and CD. Suppose that there are no other paths between A and B that are not on the FT already, but that the link AD would repair things. How do we find and agree on that link? Tony
_______________________________________________ Lsr mailing list [email protected] https://www.ietf.org/mailman/listinfo/lsr
