Hi
A couple of quick observations…. 1. The alternate backup path would appear to also require the criteria of being link diverse with the FT if the goal is to protect against multiple failures. 2. If node failures are considered, I’m not sure what criteria is used to deem a backup path as useful….. Hope this helps Dave From: Lsr <lsr-boun...@ietf.org> On Behalf Of Huaimo Chen Sent: Thursday, April 11, 2019 1:40 PM To: tony...@tony.li Cc: lsr@ietf.org Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology Hi Tony, Thank you for your questions and comments. An enhancement to the algorithm/procedure (described in my previous email) is proposed to reduce the number of links to be added to the FT temporarily for fixing possible FT split by multiple failures on the FT happening at almost the same time. An example with Figures for the enhanced algorithm/procedure is shown in the file attached. During the computation of a unique backup path for a failure on the FT (e.g., for the failure of the link R0-R2, assume that R0’s ID < R2’s ID, a unique backup path from R0 to R2 is to be computed), for each candidate path from the source (e.g., from R0), a new variable HC-FT (which is short for hop count on the FT) is used to record the number hops of the candidate path that are on the FT. The backup path computation with the enhancement is described as follows (note that the enhancement is underlined below): 1. Obtaining all the minimum hop count paths from the source to the destination (e.g., from R0 to R2), wherein each minimum hop count path has a HC-FT value; 2. If there is only one minimum hop count path that has the maximum HC-FT value, then this path is the unique backup path; otherwise, from multiple backup paths that have the maximum HC-FT value, selecting the one with the links having smaller or smallest remote node ID along the direction from the destination to the source. Best Regards, Huaimo From: Tony Li [mailto:tony1ath...@gmail.com] On Behalf Of tony...@tony.li <mailto:tony...@tony.li> Sent: Wednesday, April 10, 2019 10:00 PM To: Huaimo Chen <huaimo.c...@huawei.com <mailto:huaimo.c...@huawei.com> > Cc: lsr@ietf.org <mailto:lsr@ietf.org> Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology Hi Huaimo, Thank you for the example, this helps a lot. It’s clearer and I think it will help illuminate many things. Of course, it also generates more questions. In your algorithm you’re computing the full backup path to provide connectivity between the previously connected nodes (e.g., R0 - R2) and not just between the partitioned pieces of the FT. In this case, you would enable both R1-R2 and R2-R9. Yet, all of those nodes are still connected on the FT. Isn’t this inefficient? Moreover, since we’re enabling more flooding than is necessary, isn’t this somewhat risky? If we look at we’re proposing in the draft, each of R0, R1, R2, and R3 would recognize that they have a neighbor that is not part of their partition. They would then enable temporary flooding on R0 - R1 and R2 - R3. Either link would seem to be sufficient. Adding both is of course more risky, but without global coordination, it would be difficult to optimize further. The latter approach still seems like a simpler and more efficient solution. Regards, Tony On Apr 10, 2019, at 1:29 PM, Huaimo Chen <huaimo.c...@huawei.com <mailto:huaimo.c...@huawei.com> > wrote: Hi Tony, Thank you very much for your comments and questions. An example with Figures for computing a unique backup path for each failure on FT and enabling temporary flooding on the backup path is illustrated in the file attached. The algorithm/procedure is triggered when two or more failures on the FT happen at almost the same time. At first, for each of the failures, a deterministic backup path is computed. For example, if the link between R0 and R2, and the link between R3 and R9 on the FT failed at almost the same time, a backup path for link R0-R2 and a backup path for link R3-R9 are computed. And then, temporary flooding over the links on these backup paths are enabled. These backup paths fix the FT split. (Note: In this case, one of the backup paths may be redundant. This may be optimized in the future if needed.) For a failure on the FT (e.g., the failure of the link R0-R2, assume that R0’s ID < R2’s ID) and two end nodes of the failure, a deterministic/unique backup path from the (source) node with smaller ID (e.g., node R0) to the (destination) node with larger ID (e.g., node R2) is computed by each node in following steps: 1. Obtaining all the minimum hop count paths from the source to the destination (e.g., from R0 to R2); 2. If there is only one minimum hop count path, then this path is the unique backup path; otherwise, from multiple backup paths, selecting the one with the links having smaller or smallest remote node ID along the direction from the destination to the source (e.g., from R2 to R0). Starting from the destination node (e.g., node R2) of the backup paths, if there are multiple links on the backup paths (i.e., there are two or more links attached to the destination node on the backup paths), the link with the smaller or smallest remote node ID is selected. From the remote node X (e.g., R1) of the link selected, if there are multiple links on the backup paths (i.e., there are two or more links attached to node X on the backup paths except for the link between the destination and node X), the link with the smaller or smallest remote node ID is selected. This process continues until the source node (e.g., node R0) of the backup path is reached. We have a unique backup path for the failure. A backup path for a failure is enabled for temporary flooding by every node Rk on the backup path as follows: Rk adds its local links on the backup path to the FT temporarily if they are not on the FT. (e.g., node R2 on the backup path R0-R1-R2 adds its local link R2-R1 on the backup path to the FT temporarily since its local link R2-R1 is not on the FT). (Note: any other nodes, which are not on the backup path, do not do anything). The backup path connects the two end nodes of the failure on the FT. When the FT is split by two or more failures on the FT, the backup paths for the failures fix the FT split. For discussions: one option (called option A) is that the algorithm/procedure is triggered by one/any failure. Another option (called option B) is that the algorithm/procedure is triggered by two or more failures happening at almost the same time. Option B is the one described above. Option A seems simpler. It fix the FT split by two or more failures. But for one failure, its work may not be needed. Best Regards, Huaimo From: Tony Li [ <mailto:tony1ath...@gmail.com> mailto:tony1ath...@gmail.com] On Behalf Of <mailto:tony...@tony.li> tony...@tony.li Sent: Tuesday, April 9, 2019 12:41 PM To: Huaimo Chen < <mailto:huaimo.c...@huawei.com> huaimo.c...@huawei.com> Cc: <mailto:lsr@ietf.org> lsr@ietf.org Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology Hi Huaimo, Thank you for your discussion. Unfortunately, I (and apparently others) are still not following you. We need you to be very specific and explicit because if your algorithm is accepted, we must write code that implements it. It will not help interoperability if we have to guess about what you meant. 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. Ok, I’m already quite confused. Which sets of nodes are we considering when looking at the node IDs? Do you mean: a) Only nodes A and B. Without loss of generality, let’s assume that node A has the smaller ID. Are you suggesting that we compute the least hop count path from A to B? What happens if there are links on that path that are already on the FT? If adjacency CD also straddles the partition, wouldn’t that be a more optimal solution? An AB backup path might require several hops. In many cases, we got to a partition because of a double failure. Link EF also failed to create this situation. How do all nodes know to compute the AB path rather than the EF path? We cannot depend on time, since LSP propagation is not deterministic. Some nodes may see the EF failure first, others may see the AB failure first. b) The smallest ID in one partition (A) and the largest ID in the other partition (B). This raises similar questions: A and B could be anywhere within their respective partitions. How is the shortest hop count path between them optimal? c) Something else entirely? 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. How do we select the path uniquely, and in a distributed fashion? I can see many potential approaches, but I’m unclear on what your intent is. Tony <Backuppath4-FT-split.pdf>
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Lsr mailing list Lsr@ietf.org https://www.ietf.org/mailman/listinfo/lsr
