Hi Tony, Computing a whole backup path between two end nodes of a failure and enabling temporary flooding at each hop of the path will guarantee that these two end nodes are connected on the FT, thus the FT partition caused by multiple failures is fixed.
The backup path is not a guarantee. Consider the case of other link or node failures along the backup path. In particular, consider the case when the destination node failed. There will be no working backup path. In fact, everything along the computed backup path may have failed. Consider the case that the multiple failures occur at almost the same time and there is no other failure following these multiple failures shortly. In this case, the backup paths will connect the live end nodes of the failures on the FT, and the FT partition is fixed. Note that we assume that the real network topology is not split. So there will be working backup paths that connect the FT partitions. For the case that the multiple failures occur at almost the same time and then other failures happen following the (old) multiple failures shortly, we can consider all these failures (i.e., the old multiple failures and the other failures including destination node failure) as new multiple failures. For these new multiple failures, the backup paths for all these failures will connect the live end nodes of the failures on the FT, and the FT partition is fixed. Enabling temporary flooding on a link attached to one or each of the two end nodes may not connect the two end nodes of the failure on the FT in some cases when the backup path has multiple hops, thus may not fix the FT partition created by multiple failures. It’s true that just adding one link may not heal the partition. This is exactly why we feel we need to iterate. Each iteration increases the size of the partition (or decreases the cut set, depending on how you want to look at it) and because the graph is finite, we are guaranteed to converge. The convergence in this way may take a long time. Each iteration takes a time Ti. If we need n (n > 1) iterations, then the total time for convergence is n times Ti. For centralized flooding reduction, Ti is the time including three parts: 1) for the link states (i.e., LSPs or LSAs) representing some of the multiple failures to travel to the area leader in the network over the FT that is partitioned, 2) the leader to compute and send a new FT, and 3) the other nodes (i.e., non area leader nodes) receive and build the new FT. Best Regards, Huaimo From: Tony Li [mailto:[email protected]] On Behalf Of [email protected] Sent: Saturday, April 13, 2019 1:09 PM To: Huaimo Chen <[email protected]> Cc: Sarah Chen <[email protected]>; [email protected] Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology Hi Huaimo, Computing a whole backup path between two end nodes of a failure and enabling temporary flooding at each hop of the path will guarantee that these two end nodes are connected on the FT, thus the FT partition caused by multiple failures is fixed. The backup path is not a guarantee. Consider the case of other link or node failures along the backup path. In particular, consider the case when the destination node failed. There will be no working backup path. In fact, everything along the computed backup path may have failed. Enabling temporary flooding on a link attached to one or each of the two end nodes may not connect the two end nodes of the failure on the FT in some cases when the backup path has multiple hops, thus may not fix the FT partition created by multiple failures. It’s true that just adding one link may not heal the partition. This is exactly why we feel we need to iterate. Each iteration increases the size of the partition (or decreases the cut set, depending on how you want to look at it) and because the graph is finite, we are guaranteed to converge. Partition repair in the face of imperfect and insufficient information is a hard problem. We shouldn’t be expecting a closed form solution. Tony
_______________________________________________ Lsr mailing list [email protected] https://www.ietf.org/mailman/listinfo/lsr
