Hi, Huaimo, Why do we need to compute a whole backup path and enable flooding at each hop? In your example, when R0-R2 and R3-R9 fail, R0 (and R3) will find out that its neighbor R1 (and R2) are no longer on the FT. R0 (and R3) will then enable temporary flooding on R0-R1 (and R3-R2), which fixes the partition.
Thanks, Sarah On Thu, Apr 11, 2019 at 10:41 AM Huaimo Chen <huaimo.c...@huawei.com> wrote: > 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 > *Sent:* Wednesday, April 10, 2019 10:00 PM > *To:* Huaimo Chen <huaimo.c...@huawei.com> > *Cc:* 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> 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 <tony1ath...@gmail.com>] *On > Behalf Of *tony...@tony.li > *Sent:* Tuesday, April 9, 2019 12:41 PM > *To:* Huaimo Chen <huaimo.c...@huawei.com> > *Cc:* 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> > > > _______________________________________________ > Lsr mailing list > Lsr@ietf.org > https://www.ietf.org/mailman/listinfo/lsr >
_______________________________________________ Lsr mailing list Lsr@ietf.org https://www.ietf.org/mailman/listinfo/lsr
