Subject: [Lsr] Min Links for Multiple Failures on Flooding Topology

From: Huaimo Chen <[email-masked]>
Date: Mon, 1 Apr 2019 15:58:25 +0000

Hi Everyone,
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.
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.

Best Regards,
Huaimo

---

From: [email-masked]
Date: Mon, 1 Apr 2019 09:49:32 -0700

Hi Huaimo,

Thank you for your note.  I have many questions, please see inline.

> 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…

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…

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

---

From: Huaimo Chen <[email-masked]>
Date: Tue, 9 Apr 2019 04:25:56 +0000

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-masked]] On Behalf Of [email-masked]
Sent: Monday, April 1, 2019 12:50 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

Tony

---

From: [email-masked]
Date: Tue, 9 Apr 2019 09:40:53 -0700

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

---

From: Huaimo Chen <[email-masked]>
Date: Wed, 10 Apr 2019 20:29:14 +0000

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:[email-masked]] On Behalf Of [email-masked]
Sent: Tuesday, April 9, 2019 12:41 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

a) Only nodes A and B.

Tony

---

From: [email-masked]
Date: Wed, 10 Apr 2019 19:00:23 -0700

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 <[email-masked]> wrote:
> 
> Hi Tony,
>  
> <Backuppath4-FT-split.pdf>

---

From: Huaimo Chen <[email-masked]>
Date: Thu, 11 Apr 2019 17:40:07 +0000

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:[email-masked]] On Behalf Of [email-masked]
Sent: Wednesday, April 10, 2019 10:00 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

Regards,
Tony

On Apr 10, 2019, at 1:29 PM, Huaimo Chen <[email-masked]<mailto:[email-masked]>> wrote:

Hi Tony,

Best Regards,
Huaimo
From: Tony Li [mailto:[email-masked]] On Behalf Of [email-masked]<mailto:[email-masked]>
Sent: Tuesday, April 9, 2019 12:41 PM
To: Huaimo Chen <[email-masked]<mailto:[email-masked]>>
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

a) Only nodes A and B.

Tony

---

From: Sarah Chen <[email-masked]>
Date: Thu, 11 Apr 2019 11:29:01 -0700

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 <[email-masked]> wrote:

> 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.
>
>
>
> 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:[email-masked]] *On Behalf Of *
> [email-masked]
> *Sent:* Wednesday, April 10, 2019 10:00 PM
> *To:* Huaimo Chen <[email-masked]>
> *Cc:* [email-masked]
> *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.
>
>
>
> 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.
>
>
>
> 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.
>
>
>
> 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:
>
>
>
> 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.
>
>
>
> 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).
>
> 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:[email-masked] <[email-masked]>] *On
> Behalf Of [email-masked]
> *Sent:* Tuesday, April 9, 2019 12:41 PM
> *To:* Huaimo Chen <[email-masked]>
> *Cc:* [email-masked]
> *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.
>
>
>
>
>
>
>
> This raises similar questions: A and B could be anywhere within their
> respective partitions.  How is the shortest hop count path between them
> optimal?
>
>
>
> 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
>
>
>
>
>
> _______________________________________________
> Lsr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lsr
>

---

From: David Allan I <[email-masked]>
Date: Fri, 12 Apr 2019 12:56:49 +0000

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 <[email-masked]> On Behalf Of Huaimo Chen
Sent: Thursday, April 11, 2019 1:40 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Tony,

Best Regards,

Huaimo

From: Tony Li [mailto:[email-masked]] On Behalf Of [email-masked] <mailto:[email-masked]> 
Sent: Wednesday, April 10, 2019 10:00 PM
To: Huaimo Chen <[email-masked] <mailto:[email-masked]> >
Cc: [email-masked] <mailto:[email-masked]> 
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

Regards,

Tony

On Apr 10, 2019, at 1:29 PM, Huaimo Chen <[email-masked] <mailto:[email-masked]> > wrote:

Hi Tony,

Best Regards,

Huaimo

From: Tony Li [ <mailto:[email-masked]> mailto:[email-masked]] On Behalf Of  <mailto:[email-masked]> [email-masked]
Sent: Tuesday, April 9, 2019 12:41 PM
To: Huaimo Chen < <mailto:[email-masked]> [email-masked]>
Cc:  <mailto:[email-masked]> [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

 

 

a) Only nodes A and B.

 

 

Tony

---

From: Huaimo Chen <[email-masked]>
Date: Sat, 13 Apr 2019 15:10:15 +0000

Hi Sarah,

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. 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.

Best Regards,
Huaimo
From: Sarah Chen [mailto:[email-masked]]
Sent: Thursday, April 11, 2019 2:29 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

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 <[email-masked]<mailto:[email-masked]>> wrote:
Hi Tony,

Best Regards,
Huaimo
From: Tony Li [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of [email-masked]<mailto:[email-masked]>

Hi Huaimo,

Regards,
Tony

Hi Tony,

Best Regards,
Huaimo

Hi Huaimo,

a) Only nodes A and B.

Tony

_______________________________________________
Lsr mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/lsr

---

From: Huaimo Chen <[email-masked]>
Date: Sat, 13 Apr 2019 15:39:55 +0000

Hi Dave,

Thank you for your observations.
My explanations are inline below with prefix [HC].

>From: David Allan I [mailto:[email-masked]]
>Sent: Friday, April 12, 2019 8:57 AM
>To: Huaimo Chen <[email-masked]>; [email-masked]
>Cc: [email-masked]
>Subject: RE: [Lsr] Min Links for Multiple Failures on Flooding Topology
>
>Hi
>
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.

[HC]: Can you give some more details about this?

2)      If node failures are considered, I’m not sure what criteria is used to deem a backup path as useful…..

[HC]: Regarding to the failure of a node X on the FT, suppose that there are multiple (i.e., two or more) nodes that were connected to the failed node X through the links on the FT. For each pair of these multiple nodes, a backup path between this pair is computed and enabled for temporary flooding. Thus the backup paths will connect these multiple nodes on the FT, and the FT partition caused by multiple failures including the failure of node X is fixed through the backup paths for the failed node X and the backup paths for the other failures.

For example, if the failed node X was connected to two nodes Ri and Rj (assume that Ri’s ID < Rj’s ID) by the links on the FT before node X fails, there is only one pair of nodes: (Ri, Rj). A unique backup path from Ri to Rj is computed and enabled for temporary flooding. This backup path will connect Ri and Rj on the FT and fix the FT partition caused by multiple failures with the backup paths for the other failures.

In another example, if the failed node X was connected to three nodes Ri, Rj and Rk (assume that Ri’s ID < Rj’s ID < Rk’s ID) by the links on the FT before node X fails, there are three pairs of nodes: (Ri, Rj), (Ri, Rk) and (Rj, Rk). A unique backup path from Ri to Rj, a unique backup path from Ri to Rk, and a unique backup path from Rj to Rk are computed and enabled for temporary flooding. These three backup paths will connect three nodes Ri, Rj and Rk on the FT, and fix the FT partition caused by multiple failures with the backup paths for the other failures.

Best Regards,
Huaimo

---

From: [email-masked]
Date: Sat, 13 Apr 2019 10:08:32 -0700

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

---

From: [email-masked]
Date: Sat, 13 Apr 2019 10:21:48 -0700

Hi guys,

I think that there’s some confusion here.

> [HC]: Can you give some more details about this?

I think that when we originally started talking about backup paths, they were intended as a protection mechanism. However, I think we’ve moved on from that and are now considering backup paths as a restoration mechanism.  

Tony

---

From: David Allan I <[email-masked]>
Date: Sun, 14 Apr 2019 18:32:35 +0000

Hi Huaimo:

Replies are in line….prefaced with DA>

<snipped> 

[DA] There is a bit of a chain of logic I did not well elucidate…

If we have an FT sufficient to be complete in the presence of any single failure, AND if we have a multiple failures situation such that the FT has been partitioned, and the information at any node is incomplete, then IMO the heuristic to attempt a blind repair with the highest probability of success is to 

a.	Assume any observed failure is the worst possible class of failure (e.g. node, as if the FT is severed the surrounding nodes will only see one or some of the LSAs associated with the node failure).
b.	Attempt to restore using links that are not part of the FT as if I assume the probability of multiple failures decreases exponentially in proportion to the number of simultaneous failures, it has a higher probability of success….

On reflection ‘b’ seems too simplistic, and does not reflect that some knowledge of what parts of the FT survive in the partition the node contemplating restoration is in, would be available for decision making.  And the fact that the concept of path as a response to the failure scenario being discussed IMO is not realistic (I elaborate a bit below).

DA> Again I need to back this up a bit and incorporate a bit more subsequent reflection in my response.  What I was referring to blurred two discussions, adding links in response to severing and your post where path establishment seemed to be based on a previously known network state.

As observed above, I do not think a restoration strategy focused on a repair path that assumes a link failure will do anything useful for the partitioning scenario under consideration.  I also do not see a simple heuristic for a collection of nodes that are blind to the overall state of the FT to create a new path in the FT as a distributed response and where no signaling is involved.  I’d assume that is why what is being discussed is to add links temporarily as that is about the only strategy that can work with unilateral decisions by single nodes not acting in a coordinated fashion….If a path is required, a node trying to instantiate a portion of the path cannot depend on its neighbor to independently come to the same conclusion, in fact for an actual repair the opposite is just about guaranteed.  

I hope that is clearer

Dave

---

From: Huaimo Chen <[email-masked]>
Date: Mon, 15 Apr 2019 15:09:27 +0000

Hi Tony,

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.

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-masked]] On Behalf Of [email-masked]
Sent: Saturday, April 13, 2019 1:09 PM
To: Huaimo Chen <[email-masked]>
Cc: Sarah Chen <[email-masked]>; [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

Tony

---

From: [email-masked]
Date: Mon, 15 Apr 2019 08:37:10 -0700

Hi Huaimo,

> 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 l…

I don’t think you can just assume that the network topology is not damaged in some way.  After all, the FT partitioned because of real failures.  Your algorithm for computing backup paths relies on old information about the topology of other partitions.  That information may be out of date and incorrect. This can lead to the paths not being viable.

> 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…

Again, how can you consider any new failures in the computation of the backup paths? You have no way of getting information since the FT partitioned.

> The convergence in this way may take a long time.

Agreed.  However, the alternatives that we have on the table right now are (a) take several iterations, or (b) turn on many links and risk a cascade failure.

> 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…

We agree that it is linear in the time taken to add new nodes to the topology.  However, due to rate limiting, I suspect that the overall time is more constrained by the rate limiting.  

After a multiple failure, all nodes can evaluate the state of their adjacencies against the current, existing, and now partitioned FT.  Information about the partition has been flooded using the current FT, but only within the partitions.  Any node with an adjacency outside of its partition can enable temporary flooding to one neighbor and begin rate limiting.

While rate limiting is in progress, a new area leader election and FT computation can happen within the partition.  This may or may not yield LSDB updates.  Similarly, the temporary addition to the flooding topology may or may not yield LSDB updates. 

Whether the area leader election and FT computation is faster than the rate limiting is unknown, since both are implementation dependent.

Tony

---

From: Huaimo Chen <[email-masked]>
Date: Thu, 18 Apr 2019 05:13:46 +0000

Hi Dave,

    My explanations are inline below with prefix [HC2].

From: David Allan I [mailto:[email-masked]]
Sent: Sunday, April 14, 2019 2:33 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: RE: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo:

<snipped>

[HC]: Can you give some more details about this?
[DA] There is a bit of a chain of logic I did not well elucidate…
If we have an FT sufficient to be complete in the presence of any single failure, AND if we have a multiple failures situation such that the FT has been partitioned, and the information at any node is incomplete, then IMO the heuristic to attempt a blind repair with the highest probability of success is to
a)       Assume any observed failure is the worst possible class of failure (e.g. node, as if the FT is severed the surrounding nodes will only see one or some of the LSAs associated with the node failure).
b)      Attempt to restore using links that are not part of the FT as if I assume the probability of multiple failures decreases exponentially in proportion to the number of simultaneous failures, it has a higher probability of success….
On reflection ‘b’ seems too simplistic, and does not reflect that some knowledge of what parts of the FT survive in the partition the node contemplating restoration is in, would be available for decision making.  And the fact that the concept of path as a response to the failure scenario being discussed IMO is not realistic (I elaborate a bit below).

[HC2]: Consider the case that there are failures of two links and these two links are on the FT and the FT is split by these two failures and no other failures follow shortly. In this case, every node has the information about the normal/real network topology before the failures, and the indications about these two failures. Based on this information, the backup paths for these two failures can be computed and enabled for temporary flooding. Thus the FT partition is fixed.
If the backup path for one failure on the FT does not share any link with the backup path for the other failure on the FT (Note that this can be achieved through using diverse links when computing backup paths), the backup paths can also survive the failure of any other link that is not on the FT and happens at almost the same time as the two failures of the two links on the FT.
Consider the case that there is another failure of one link on the FT in addition to these two failures. This failure is on one partition of the FT and not on the other partition. In this case, the information about the other failure will flood through the backup paths. Moreover, the backup path for the other failure is computed and enabled for temporary flooding in its partition. The information about the two failures will food through this backup path. Thus the topology is converged quickly.
In order to speed up the convergence further, we may increase the connectivity on the FT when there are failures on the FT to let every node have more information about failures. In one way, when a link attached to a node fails and the link is on the FT, we find another link attached to the node and not on the FT, and add it to the FT temporarily. In another way, only after two or more failures on the FT happen, for a link attached to a node that is on the FT and fails, we find another link attached to the node and not on the FT, and add it to the FT temporarily.

[HC2]: The backup paths are computed based on the information there. Even though some information may be missing, the backup paths for a failure are created by the nodes close (or local) to the failure and connect two partitions. Through locally repairing the partitions and iterations, the topology is converged quickly.
I considered to use signaling to setup backup paths. However, this is complicated since we may introduce a simplified tunneling protocol into IGP.  In an IP network,  when an IP packet with a destination D is sent from any node, this packet will travel to D along a path. This path is “created” as a distributed response to topology changes and no signaling is used.

Best Regards,
Huaimo

I hope that is clearer
Dave

---

From: David Allan I <[email-masked]>
Date: Thu, 18 Apr 2019 18:27:46 +0000

Hi Huaimo:

Thanks for replying, my comments in line prefaced with DA2>

<snipped> 

DA2> Frankly, I cringe a bit at this characterization. Part of this is that:

*	there isn’t a way to instantiate a path, and IMO to maximize coverage against all possible scenarios it should be a unilateral action by a single node for each direction across the partition, not something that requires coordinated action by a number of potentially unsynchronized nodes
*	the statement “no other failures follow shortly” IMO is wishful thinking
*	the nodes on either side of a partition are all FT participants so what is actually needed is a node to self elect to flood information on a non-FT adjacency that by some heuristic it believes crosses the chasm….which then starts really looking like “adding links until the partition(s) is/are fixed”….

So while thinking a path can solve a partition, as there is no method of signaling it, or reliably depending on a distributed solution to create it, it therefore it would have to be composed of FT adjacencies, with the exception of the one that crosses the partition.  Which collapses down to the case under consideration and would be the only link that mattered.  

So IMO at best what you propose may a heuristic that would be a guideline for the first try to add a link but is not a complete solution in itself.

DA2>  I think we are talking past each other, as I see the problem as one of sets once partitioning occurs. I need a means of reconnecting disconnected sets of FT members, where within a given set there is full connectivity and in a reasonably rich topology there would be any number of candidate links that could be added that would eliminate the partitions. Paths is “a” way to think of this, but as noted above, instantiating one will by necessity reduce to adding a link to the FT, so it would merely be a guideline for selecting a link with a high probability of reconnecting severed sets in the presence of incomplete information.

DA2> Well you’ve now seen my comments above on instantiation and utility of paths. Tunneling is a solution I had not considered, and I’m insufficiently an expert to consider all the ramifications, such as does that tunnel become an adjacency and forward non IGP traffic… etc. (like an MPLS FA)…And I again cringe and the security implications of accepting any control plane packet that randomly arrived on my doorstep.

I hope this helps

Dave

---

From: Huaimo Chen <[email-masked]>
Date: Fri, 19 Apr 2019 15:24:31 +0000

Hi Tony,

From: Tony Li [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Monday, April 15, 2019 11:37 AM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

[HC]: In general, using the backup paths for the failures to repair the FT partition works well to some extend even though the nodes in one partition have some information about the topology that the nodes in another partition do not have.

At first, it can survive two or more failures. For example, it can repair the FT partition created by the failures of any two links on the FT. It can also repair the FT partition caused by the failures of any two links on the FT and the failure of any other link if the algorithm for computing backup paths is enhanced to consider using diverse links (i.e., the backup paths are computed in such a way that one backup path does not share any link with the other backup paths if possible).

Secondly, it helps the convergence. The backup paths for a failure are created by the nodes close (or say local) to the failure and connect the two partitions. After this local repair of the FT partition, the link states in the two partitions are synchronized, and the topology is converged. Locally repairing the FT partition is faster than the repairing by the area leader.

Moreover, if one extra backup path for a failure is computed and enabled for temporary flooding, the FT partition created by one more failure can be repaired.

The network topology is damaged.  This is considered in the algorithm for computing backup paths.  Every node uses its LSDB for computing backup paths if needed. The FT is portioned, but the real network topology is not, and is used. For the information about a failure that is on one partition and not on another partition, if the part damaged by this failure is not used in any other backup paths, then there is no problem; otherwise (i.e., it is used in some backup paths), if the damaged part is used only in one backup path, the backup paths can survive the damaged part if that one backup path does not share any link with the other backup paths.

[HC]: The information about the new failures will flood through the backup paths for the old failures if the backup paths are created. Refer to the explanation above.

[HC]: It seems that using the backup paths for the failures to repair the FT partition may make the convergence faster. Refer to the second point in the first explanation above.
It may be better to use both the backup paths for the failures and the rate limiting. The former repairs the partitions locally, and the latter helps the former to work better. Thus the convergence will be faster.

Best Regards,
Huaimo

Tony

---

From: [email-masked]
Date: Fri, 19 Apr 2019 10:20:16 -0700

Hi Huaimo,

> At first, it can survive two or more failures. For example, it can repair the FT partition created by the failures of any two links on the FT. It can also repair the FT partition caused by the fail…

Well, I’m still not seeing how this works.  AFAICT, when there is a partition, your proposal is to compute a shortest path between the previously connected nodes using link state information that is now out of date.  What you compute is a multi-link path, tho it’s not clear at all how this is enabled.  Since the FT is down, there is no way to signal to the other half of the partition about what links are requested.  

At best, it seems like you’re having one partition-edge router enable one link towards the other partition.

> Secondly, it helps the convergence. The backup paths for a failure are created by the nodes close (or say local) to the failure and connect the two partitions. After this local repair of the FT par…

The area leader cannot repair the partition, since the FT cannot be propagated across the partition.  This is why enabling links across the partition edge is necessary.

It is not clear that your backup path computation (an SPF?) is any faster (or slower) than determining whether a neighbor is in a separate partition.

> The network topology is damaged.  This is considered in the algorithm for computing backup paths.

Only partially.  Your algorithm does not know what the damage is in the other half of the partition.  There is no way to get it this information. As a result, the backup path that’s computed may traverse nodes and links in the other half of the partition that are no longer functional. It may also completely ignore links and nodes that could heal the partition.

> Every node uses its LSDB for computing backup paths if needed. The FT is portioned, but the real network topology is not, and is used. For the information about a failure that is on one partition and not on another partition, if the part damaged by this failure is not used in any other backup paths, then there is no problem; otherwise (i.e., it is used in some backup paths), if the damaged part is used only in one backup path, the backup paths can survive the damaged part if that one backup path does not share any link with the other backup paths. 

It seems to me that this leads to enabling flooding throughout the entire topology, leading us back to cascade failure.

> [HC]: The information about the new failures will flood through the backup paths for the old failures if the backup paths are created. Refer to the explanation above.

This reasoning is circular.  You have still not shown that the backup paths will repair the failures.

> It may be better to use both the backup paths for the failures and the rate limiting. The former repairs the partitions locally, and the latter helps the former to work better. Thus the convergence…

You have not shown that the backup paths will provide any benefit at all, much less improve convergence.  First and foremost, we need an algorithm that will lead to partition repair.  

We still need you to provide a specific, detailed proposal that we all agree will heal the partition.

Instead of continuing to argue about the merits of your proposal at a high level, I suggest we return to specific examples.  I think that you’ll find that as we work through them that the greedy algorithm described in the draft is very difficult to improve upon in the general case.

Regards,
Tony

---

From: Huaimo Chen <[email-masked]>
Date: Thu, 25 Apr 2019 14:26:31 +0000

Hi Tony,

Considering the different information about the link states in the different FT partitions caused by failures, attached (5 pages) contain an example with Figures, which illustrate and explain almost every step in details for computing a unique backup path for each of the two failures on the FT and enabling temporary flooding on the backup path. Would you mind indicating if any thing missing or incorrect?

In this example, the failures of two links R4-R7 and R5-R8 on the FT happen at the same time and split the FT into two partitions: partition A and partition B. Partition A contains R0, R1, R2, R3, R4, and R5. Partition B has R6, R7, R8, R9, R10, R11, and R12. Refer to Fig. 1.

Every node in partition A receives the link state (LS) from R4 indicating link from R4 to R7 down and the LS from R5 indicating link from R5 to R8 down. It has the FT and the real topology, shown in Fig. 2. There are two uni-directional links: link from R7 to R4, and link from R8 to R5. These uni-directional links will not be used in backup path computations.

Similarly in partition B, every node receives the LS from R7 indicating link from R7 to R4 down and the LS from R8 indicating link from R8 to R5 down. It has the FT and the real topology, shown in Fig. 3. There are two uni-directional links: link from R4 to R7, and link from R5 to R8. These uni-directional links will not be used in backup path computations. Note that Fig. 2 and Fig. 3 are equivalent if the uni-directional links are not used.

A unique backup path for link R4-R7 is computed and then enabled for temporary flooding.

In this example, the basic part of the algorithm below for computing a backup path is used, which is to obtain the minimum hop count path from Ri to Rj for link Ri-Rj. Like SPF, any link used in the path must be bi-directional.

At first, for the failure of a link Ri-Rj on the FT, a unique backup path for link Ri-Rj (assume Ri’s ID < Rj’s ID) is computed by each node in following steps:

  1.  Obtaining all the minimum hop count paths from Ri to Rj, wherein each minimum hop count path has a HC-FT value.
  2.  From the multiple paths that have the maximum HC-FT value if any, selecting the one with the links having smaller or smallest remote node ID along direction from destination Rj to source Ri.
And then, the backup path for link Ri-Rj is enabled for temporary flooding by node Rk on the path as follows:
Rk adds its local links on the backup path to the FT temporarily if they are not on the FT.

The backup path for link R4-R7 is R4-R3-R6-R7 (refer to Fig. 4). It is computed by R4, R3, R6 and R7 and other nodes. R3 and R4 in partition A compute the backup path using the topology in Fig. 2. R6 and R7 in partition B compute the backup path using the topology in Fig. 3.

The backup path for link R4-R7 is enabled for temporary flooding by R4,R3,R6 and R7 that are on the backup path. R3 adds link R3-R6; and R6 adds link R6-R3 to the FT temporarily. Note that link R4-R3 is already on the FT, R4 and R3 will not add it to the FT again; link R6-R7 is already on the FT, R6 and R7 will not add it to the FT again. Refer to Fig. 4.

Similarly, a unique backup path for link R5-R8 is computed and then enabled for temporary flooding.

The backup path for link R5-R8 is R5-R2-R9-R8 (refer to Fig. 5). It is computed by R5, R2, R9 and R8 and other nodes.

The backup path for link R5-R8 is enabled for temporary flooding by R5,R2,R9 and R8 (refer to Fig. 5).

A unique backup path for link R4-R7, and a unique backup path for link R5-R8 are computed and then enabled for temporary flooding.

    The FT split is repaired. Refer to Fig. 6, FT partition A and partition B are connected by the links added to the FT temporarily.

Best Regards,
Huaimo
From: Tony Li [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Friday, April 19, 2019 1:20 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

Regards,
Tony

---

From: [email-masked]
Date: Thu, 25 Apr 2019 09:36:38 -0700

Hi Huaimo,

Thank you, this is very clear.

It leaves me with one question: how is this better than what we have?

You’ve computed the backup paths: [R4, R3, R6, R7] and [R5, R2, R9, R8].  This results in enabling flooding on (R3, R6) and on (R5, R2), (R2, R9), (R9, R8).

Per the existing algorithm, the temporary additions would be (R3, R6) and (R2, R9).  As it has less flooding, this seems like a better solution.

Regards,
Tony

> On Apr 25, 2019, at 7:26 AM, Huaimo Chen <[email-masked]> wrote:
> 
> Hi Tony,
>  
> Obtaining all the minimum hop count paths from Ri to Rj, wherein each minimum hop count path has a HC-FT value.
> From the multiple paths that have the maximum HC-FT value if any, selecting the one with the links having smaller or smallest remote node ID along direction from destination Rj to source Ri.
> <Backuppath4-FT-split-diff-lsdbs-2failures.pdf>

---

From: Huaimo Chen <[email-masked]>
Date: Thu, 25 Apr 2019 18:43:18 +0000

Hi Tony,

What is “the existing algorithm” that you have?
Is it the “rate limiting”? If so, can you describe the “rate limiting” algorithm in details?

Best Regards,
Huaimo
From: Tony Li [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Thursday, April 25, 2019 12:37 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

Regards,
Tony

On Apr 25, 2019, at 7:26 AM, Huaimo Chen <[email-masked]<mailto:[email-masked]>> wrote:

Hi Tony,

Best Regards,
Huaimo

Hi Huaimo,

Regards,
Tony

---

From: [email-masked]
Date: Thu, 25 Apr 2019 13:08:12 -0700

Hi Huaimo,

> Is it the “rate limiting”? If so, can you describe the “rate limiting” algorithm in details?

Yes.  We haven’t described it very formally, so let me see if I can be more precise:

On each node, in parallel:
	On a topology change:
		For each adjacency:
			Is there a path to the adjacent node via the flooding topology?
			If not, add it to a set of candidates.
		While the set of candidates is not empty:
			Remove one candidate from the set.
			Temporarily add it to the flooding topology
			Delay (amount is implementation defined)
			If there has been another topology change:
				Clear the candidate set
				Restart the algorithm

Does this help?

Tony

---

From: Huaimo Chen <[email-masked]>
Date: Mon, 29 Apr 2019 03:43:09 +0000

Hi Tony,

Thank you for your description. It helped me to learn more about your “rate limiting” algorithm.

Best Regards,
Huaimo
From: Tony Li [mailto:[email-masked]] On Behalf Of [email-masked]
Sent: Thursday, April 25, 2019 4:08 PM
To: Huaimo Chen <[email-masked]>
Cc: [email-masked]
Subject: Re: [Lsr] Min Links for Multiple Failures on Flooding Topology

Hi Huaimo,

Does this help?

Tony

---

From: Huaimo Chen <[email-masked]>
Date: Mon, 29 Apr 2019 14:26:53 +0000

Hi Tony,

Thank you for your question and comments.

Hi Huaimo,

[HC]: Our algorithm with an enhancement is illustrated in the attached (5 pages) file with an example. The enhancement is on page 1 in red color. The steps in the example related to the enhancement is on page 4 in red color. The result of the FT repair is on page 5. It seems that our enhanced algorithm may result less flooding in some cases. Would you mind indicating if anything missing or incorrect in this enhanced algorithm?

[HC]: The enhanced algorithm enables the temporary flooding on (R3, R6) and (R2, R9). It does not enable flooding on (R5, R2) or (R9, R8).

[HC]: It seems that the existing (rate limiting) algorithm may result more flooding in some cases. For example, if there are links (R4, R8) and (R5, R7) in Fig. 1, it seems that these two links may also be added to the FT for flooding temporarily.

Best Regards,
Huaimo

Regards,
Tony

---

From: [email-masked]
Date: Mon, 29 Apr 2019 09:08:45 -0700

Hi Huaimo,

> [HC]: The enhanced algorithm enables the temporary flooding on (R3, R6) and (R2, R9). It does not enable flooding on (R5, R2) or (R9, R8).

Thank you, yes, I missed that.

> [HC]: It seems that the existing (rate limiting) algorithm may result more flooding in some cases. For example, if there are links (R4, R8) and (R5, R7) in Fig. 1, it seems that these two links may…

Ok, that’s possible.  However, if those links existed, wouldn’t your algorithm also make use of them?

I understand that your algorithm might pick only one path, but given that the path might not be functional, it seems like there would also be cases where a bit more flooding turns out to be the right answer.

Tony