draft-ietf-rtgwg-mrt-frr-algorithm-02.txt | draft-ietf-rtgwg-mrt-frr-algorithm-03.txt | |||
---|---|---|---|---|

Routing Area Working Group G. Enyedi, Ed. | Routing Area Working Group G. Enyedi, Ed. | |||

Internet-Draft A. Csaszar | Internet-Draft A. Csaszar | |||

Intended status: Standards Track Ericsson | Intended status: Standards Track Ericsson | |||

Expires: July 23, 2015 A. Atlas, Ed. | Expires: September 10, 2015 A. Atlas, Ed. | |||

C. Bowers | C. Bowers | |||

Juniper Networks | Juniper Networks | |||

A. Gopalan | A. Gopalan | |||

University of Arizona | University of Arizona | |||

January 19, 2015 | March 9, 2015 | |||

Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- | Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- | |||

Reroute | Reroute | |||

draft-ietf-rtgwg-mrt-frr-algorithm-02 | draft-ietf-rtgwg-mrt-frr-algorithm-03 | |||

Abstract | Abstract | |||

A complete solution for IP and LDP Fast-Reroute using Maximally | A complete solution for IP and LDP Fast-Reroute using Maximally | |||

Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- | Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- | |||

architecture]. This document defines the associated MRT Lowpoint | architecture]. This document defines the associated MRT Lowpoint | |||

algorithm that is used in the default MRT profile to compute both the | algorithm that is used in the default MRT profile to compute both the | |||

necessary Maximally Redundant Trees with their associated next-hops | necessary Maximally Redundant Trees with their associated next-hops | |||

and the alternates to select for MRT-FRR. | and the alternates to select for MRT-FRR. | |||

skipping to change at page 1, line 41 | skipping to change at page 1, line 41 | |||

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF). Note that other groups may also distribute | Task Force (IETF). Note that other groups may also distribute | |||

working documents as Internet-Drafts. The list of current Internet- | working documents as Internet-Drafts. The list of current Internet- | |||

Drafts is at http://datatracker.ietf.org/drafts/current/. | Drafts is at http://datatracker.ietf.org/drafts/current/. | |||

Internet-Drafts are draft documents valid for a maximum of six months | Internet-Drafts are draft documents valid for a maximum of six months | |||

and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||

time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||

material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||

This Internet-Draft will expire on July 23, 2015. | This Internet-Draft will expire on September 10, 2015. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2015 IETF Trust and the persons identified as the | Copyright (c) 2015 IETF Trust and the persons identified as the | |||

document authors. All rights reserved. | document authors. All rights reserved. | |||

This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||

Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||

(http://trustee.ietf.org/license-info) in effect on the date of | (http://trustee.ietf.org/license-info) in effect on the date of | |||

publication of this document. Please review these documents | publication of this document. Please review these documents | |||

skipping to change at page 2, line 24 | skipping to change at page 2, line 24 | |||

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 | 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 | |||

2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5 | 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5 | |||

3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5 | 3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5 | |||

4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 7 | 4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 7 | |||

4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7 | 4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7 | |||

4.2. Finding an Ear and the Correct Direction . . . . . . . . 9 | 4.2. Finding an Ear and the Correct Direction . . . . . . . . 9 | |||

4.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 | 4.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 | |||

4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 15 | 4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 15 | |||

4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17 | 4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17 | |||

5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19 | 5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19 | |||

5.1. MRT Island Identification . . . . . . . . . . . . . . . . 20 | 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 19 | |||

5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 | 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22 | |||

5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21 | 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23 | |||

5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint | 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23 | |||

inheritance . . . . . . . . . . . . . . . . . . . . . . . 22 | 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint | |||

5.5. Augmenting the GADAG by directing all links . . . . . . . 24 | inheritance . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

5.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 26 | 5.6. Augmenting the GADAG by directing all links . . . . . . . 26 | |||

5.6.1. MRT next-hops to all nodes partially ordered with | 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 28 | |||

respect to the computing node . . . . . . . . . . . . 27 | 5.7.1. MRT next-hops to all nodes partially ordered with | |||

5.6.2. MRT next-hops to all nodes not partially ordered with | respect to the computing node . . . . . . . . . . . . 29 | |||

respect to the computing node . . . . . . . . . . . . 28 | 5.7.2. MRT next-hops to all nodes not partially ordered with | |||

5.6.3. Computing Redundant Tree next-hops in a 2-connected | respect to the computing node . . . . . . . . . . . . 30 | |||

Graph . . . . . . . . . . . . . . . . . . . . . . . . 29 | 5.7.3. Computing Redundant Tree next-hops in a 2-connected | |||

5.6.4. Generalizing for a graph that isn't 2-connected . . . 30 | Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 | |||

5.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 31 | 5.7.4. Generalizing for a graph that isn't 2-connected . . . 32 | |||

5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33 | 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 33 | |||

5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37 | 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 35 | |||

6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 40 | 5.9. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 39 | |||

7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 | 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 42 | |||

7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 | 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 42 | |||

8. Implementation Status . . . . . . . . . . . . . . . . . . . . 51 | 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 43 | |||

9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51 | 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 53 | |||

10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51 | 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 53 | |||

11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 | 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 53 | |||

12. Security Considerations . . . . . . . . . . . . . . . . . . . 51 | 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 53 | |||

13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 | 12. Security Considerations . . . . . . . . . . . . . . . . . . . 53 | |||

13.1. Normative References . . . . . . . . . . . . . . . . . . 51 | 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 53 | |||

13.2. Informative References . . . . . . . . . . . . . . . . . 51 | 13.1. Normative References . . . . . . . . . . . . . . . . . . 53 | |||

13.2. Informative References . . . . . . . . . . . . . . . . . 53 | ||||

Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53 | Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 56 | |||

Appendix B. Option 3: Computing GADAG using a hybrid method . . 58 | Appendix B. Option 3: Computing GADAG using a hybrid method . . 61 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 63 | |||

1. Introduction | 1. Introduction | |||

MRT Fast-Reroute requires that packets can be forwarded not only on | MRT Fast-Reroute requires that packets can be forwarded not only on | |||

the shortest-path tree, but also on two Maximally Redundant Trees | the shortest-path tree, but also on two Maximally Redundant Trees | |||

(MRTs), referred to as the MRT-Blue and the MRT-Red. A router which | (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which | |||

experiences a local failure must also have pre-determined which | experiences a local failure must also have pre-determined which | |||

alternate to use. This document defines how to compute these three | alternate to use. This document defines how to compute these three | |||

things for use in MRT-FRR and describes the algorithm design | things for use in MRT-FRR and describes the algorithm design | |||

decisions and rationale. The algorithm is based on those presented | decisions and rationale. The algorithm is based on those presented | |||

skipping to change at page 9, line 20 | skipping to change at page 9, line 20 | |||

disjoint from the decreasing paths. E.g. in the previous example | disjoint from the decreasing paths. E.g. in the previous example | |||

node B has multiple possibilities to forward packets along an | node B has multiple possibilities to forward packets along an | |||

increasing path: it can either forward packets to C or F. | increasing path: it can either forward packets to C or F. | |||

4.2. Finding an Ear and the Correct Direction | 4.2. Finding an Ear and the Correct Direction | |||

For simplicity, the basic idea of creating a GADAG by adding ears is | For simplicity, the basic idea of creating a GADAG by adding ears is | |||

described assuming that the network graph is a single 2-connected | described assuming that the network graph is a single 2-connected | |||

cluster so that an ADAG is sufficient. Generalizing to multiple | cluster so that an ADAG is sufficient. Generalizing to multiple | |||

blocks is done by considering the block-roots instead of the GADAG | blocks is done by considering the block-roots instead of the GADAG | |||

root - and the actual algorithm is given in Section 5.4. | root - and the actual algorithm is given in Section 5.5. | |||

In order to understand the basic idea of finding an ADAG, first | In order to understand the basic idea of finding an ADAG, first | |||

suppose that we have already a partial ADAG, which doesn't contain | suppose that we have already a partial ADAG, which doesn't contain | |||

all the nodes in the block yet, and we want to extend it to cover all | all the nodes in the block yet, and we want to extend it to cover all | |||

the nodes. Suppose that we find a path from a node X to Y such that | the nodes. Suppose that we find a path from a node X to Y such that | |||

X and Y are already contained by our partial ADAG, but all the | X and Y are already contained by our partial ADAG, but all the | |||

remaining nodes along the path are not added to the ADAG yet. We | remaining nodes along the path are not added to the ADAG yet. We | |||

refer to such a path as an ear. | refer to such a path as an ear. | |||

Recall that our ADAG is closely related to a partial order. More | Recall that our ADAG is closely related to a partial order. More | |||

skipping to change at page 10, line 27 | skipping to change at page 10, line 27 | |||

cycle; therefore the ear must go from X to Y. | cycle; therefore the ear must go from X to Y. | |||

In the case, when X and Y are not ordered with each other, we can | In the case, when X and Y are not ordered with each other, we can | |||

select either direction for the ear. We have no restriction since | select either direction for the ear. We have no restriction since | |||

neither of the directions can result in a cycle. In the corner case | neither of the directions can result in a cycle. In the corner case | |||

when one of the endpoints of an ear, say X, is the root (recall that | when one of the endpoints of an ear, say X, is the root (recall that | |||

the two endpoints must be different), we could use both directions | the two endpoints must be different), we could use both directions | |||

again for the ear because the root can be considered both as smaller | again for the ear because the root can be considered both as smaller | |||

and as greater than Y. However, we strictly pick that direction in | and as greater than Y. However, we strictly pick that direction in | |||

which the root is lower than Y. The logic for this decision is | which the root is lower than Y. The logic for this decision is | |||

explained in Section 5.6 | explained in Section 5.7 | |||

A partial ADAG is started by finding a cycle from the root R back to | A partial ADAG is started by finding a cycle from the root R back to | |||

itself. This can be done by selecting a non-ready neighbor N of R | itself. This can be done by selecting a non-ready neighbor N of R | |||

and then finding a path from N to R that doesn't use any links | and then finding a path from N to R that doesn't use any links | |||

between R and N. The direction of the cycle can be assigned either | between R and N. The direction of the cycle can be assigned either | |||

way since it is starting the ordering. | way since it is starting the ordering. | |||

Once a partial ADAG is already present, it will always have a node | Once a partial ADAG is already present, it will always have a node | |||

that is not the root R in it. As a brief proof that a partial ADAG | that is not the root R in it. As a brief proof that a partial ADAG | |||

can always have ears added to it: just select a non-ready neighbor N | can always have ears added to it: just select a non-ready neighbor N | |||

skipping to change at page 11, line 27 | skipping to change at page 11, line 27 | |||

Add the ear towards Y to the ADAG | Add the ear towards Y to the ADAG | |||

Figure 6: Generic Algorithm to find ears and their direction in | Figure 6: Generic Algorithm to find ears and their direction in | |||

2-connected graph | 2-connected graph | |||

Algorithm Figure 6 merely requires that a cycle or ear be selected | Algorithm Figure 6 merely requires that a cycle or ear be selected | |||

without specifying how. Regardless of the way of selecting the path, | without specifying how. Regardless of the way of selecting the path, | |||

we will get an ADAG. The method used for finding and selecting the | we will get an ADAG. The method used for finding and selecting the | |||

ears is important; shorter ears result in shorter paths along the | ears is important; shorter ears result in shorter paths along the | |||

MRTs. The MRT Lowpoint algorithm's method using Low-Point | MRTs. The MRT Lowpoint algorithm's method using Low-Point | |||

Inheritance is defined in Section 5.4. Other methods are described | Inheritance is defined in Section 5.5. Other methods are described | |||

in the Appendices (Appendix A and Appendix B). | in the Appendices (Appendix A and Appendix B). | |||

As an example, consider Figure 5 again. First, we select the | As an example, consider Figure 5 again. First, we select the | |||

shortest cycle containing R, which can be R-A-B-F-D-E (uniform link | shortest cycle containing R, which can be R-A-B-F-D-E (uniform link | |||

costs were assumed), so we get to the situation depicted in Figure 5 | costs were assumed), so we get to the situation depicted in Figure 5 | |||

(b). Finally, we find a node next to a ready node; that must be node | (b). Finally, we find a node next to a ready node; that must be node | |||

C and assume we reached it from ready node B. We search a path from | C and assume we reached it from ready node B. We search a path from | |||

C to R without B in the original graph. The first ready node along | C to R without B in the original graph. The first ready node along | |||

this is node D, so the open ear is B-C-D. Since B<<D, we add arc | this is node D, so the open ear is B-C-D. Since B<<D, we add arc | |||

B->C and C->D to the ADAG. Since all the nodes are ready, we stop at | B->C and C->D to the ADAG. Since all the nodes are ready, we stop at | |||

skipping to change at page 13, line 12 | skipping to change at page 13, line 12 | |||

Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to | Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to | |||

a example graph. | a example graph. | |||

global_variable: dfs_number | global_variable: dfs_number | |||

Lowpoint_Visit(node x, node parent, interface p_to_x) | Lowpoint_Visit(node x, node parent, interface p_to_x) | |||

D(x) = dfs_number | D(x) = dfs_number | |||

L(x) = D(x) | L(x) = D(x) | |||

dfs_number += 1 | dfs_number += 1 | |||

x.dfs_parent = parent | x.dfs_parent = parent | |||

x.dfs_parent_intf = p_to_x | x.dfs_parent_intf = p_to_x.remote_intf | |||

x.lowpoint_parent = NONE | x.lowpoint_parent = NONE | |||

for each interface intf of x | for each interface intf of x | |||

if D(intf.remote_node) is not set | if D(intf.remote_node) is not set | |||

Lowpoint_Visit(intf.remote_node, x, intf) | Lowpoint_Visit(intf.remote_node, x, intf) | |||

if L(intf.remote_node) < L(x) | if L(intf.remote_node) < L(x) | |||

L(x) = L(intf.remote_node) | L(x) = L(intf.remote_node) | |||

x.lowpoint_parent = intf.remote_node | x.lowpoint_parent = intf.remote_node | |||

x.lowpoint_parent_intf = intf | x.lowpoint_parent_intf = intf | |||

else if intf.remote_node is not parent | else if intf.remote_node is not parent | |||

if D(intf.remote_node) < L(x) | if D(intf.remote_node) < L(x) | |||

skipping to change at page 14, line 33 | skipping to change at page 14, line 33 | |||

[A]---------[B] [G]----| [L]------[M] | [A]---------[B] [G]----| [L]------[M] | |||

(1, ) (2, ) (7, ) (12, ) (13, ) | (1, ) (2, ) (7, ) (12, ) (13, ) | |||

(b) with DFS values assigned (D(x), L(x)) | (b) with DFS values assigned (D(x), L(x)) | |||

[E]----| [J]---------[I] [P]------[O] | [E]----| [J]---------[I] [P]------[O] | |||

(5,0) | (10,3) (9,3) (16,11) (15,11) | (5,0) | (10,3) (9,3) (16,11) (15,11) | |||

| | | | | | | | | | | | | | |||

| | | | | | | | | | | | | | |||

[R] [D]---[C]---[F] [H]----[K] [N] | [R] [D]---[C]---[F] [H]----[K] [N] | |||

(0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) | (0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) | |||

| | | | | | | | | | | | | | |||

| | | | | | | | | | | | | | |||

[A]---------[B] [G]----| [L]------[M] | [A]---------[B] [G]----| [L]------[M] | |||

(1,0) (2,0) (7,3) (12,11) (13,11) | (1,0) (2,0) (7,3) (12,11) (13,11) | |||

(c) with low-point values assigned (D(x), L(x)) | (c) with low-point values assigned (D(x), L(x)) | |||

Figure 9: Example lowpoint value computation | Figure 9: Example lowpoint value computation | |||

From the low-point value and lowpoint parent, there are three very | From the low-point value and lowpoint parent, there are three very | |||

useful things which motivate our computation. | useful things which motivate our computation. | |||

First, if there is a child c of x such that L(c) >= D(x), then there | First, if there is a child c of x such that L(c) >= D(x), then there | |||

are no paths in the network graph that go from c or its descendants | are no paths in the network graph that go from c or its descendants | |||

to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, | to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, | |||

this can be seen by looking at the DFS children of C. C has two | this can be seen by looking at the DFS children of C. C has two | |||

children - D and F and L(F) = 3 = D(C) so it is clear that C is a | children - D and F and L(F) = 3 = D(C) so it is clear that C is a | |||

cut-vertex and F is in a block where C is the block's root. L(D) = 0 | cut-vertex and F is in a block where C is the block's root. L(D) = 0 | |||

> 3 = D(C) so D has a path to the ancestors of C; in this case, D can | < 3 = D(C) so D has a path to the ancestors of C; in this case, D can | |||

go via E to reach R. Comparing the low-point values of all a node's | go via E to reach R. Comparing the low-point values of all a node's | |||

DFS-children with the node's DFS-value is very useful because it | DFS-children with the node's DFS-value is very useful because it | |||

allows identification of the cut-vertices and thus the blocks. | allows identification of the cut-vertices and thus the blocks. | |||

Second, by repeatedly following the path given by lowpoint_parent, | Second, by repeatedly following the path given by lowpoint_parent, | |||

there is a path from x back to an ancestor of x that does not use the | there is a path from x back to an ancestor of x that does not use the | |||

link [x, x.dfs_parent] in either direction. The full path need not | link [x, x.dfs_parent] in either direction. The full path need not | |||

be taken, but this gives a way of finding an initial cycle and then | be taken, but this gives a way of finding an initial cycle and then | |||

ears. | ears. | |||

skipping to change at page 16, line 5 | skipping to change at page 16, line 5 | |||

block. | block. | |||

4.4. Blocks in a Graph | 4.4. Blocks in a Graph | |||

A key idea for an MRT algorithm is that any non-2-connected graph is | A key idea for an MRT algorithm is that any non-2-connected graph is | |||

made up by blocks (e.g. 2-connected clusters, cut-links, and/or | made up by blocks (e.g. 2-connected clusters, cut-links, and/or | |||

isolated nodes). To compute GADAGs and thus MRTs, computation is | isolated nodes). To compute GADAGs and thus MRTs, computation is | |||

done in each block to compute ADAGs or Redundant Trees and then those | done in each block to compute ADAGs or Redundant Trees and then those | |||

ADAGs or Redundant Trees are combined into a GADAG or MRT. | ADAGs or Redundant Trees are combined into a GADAG or MRT. | |||

[E]---| [J]-------[I] [P]---[O] | [E]---| [J]-------[I] [P]---[O] | |||

| | | | | | | | | | | | | | |||

| | | | | | | | | | | | | | |||

[R] [D]---[C]--[F] [H]---[K] [N] | [R] [D]---[C]--[F] [H]---[K] [N] | |||

| | | | | | | | | | | | | | |||

| | | | | | | | | | | | | | |||

[A]--------[B] [G]---| [L]---[M] | [A]--------[B] [G]---| [L]---[M] | |||

(a) A graph with four blocks that are: | (a) A graph with four blocks that are: | |||

3 2-connected clusters and a cut-link | three 2-connected clusters | |||

and one cut-link | ||||

[E]<--| [J]<------[I] [P]<--[O] | [E]<--| [J]<------[I] [P]<--[O] | |||

| | | ^ | ^ | | | | ^ | ^ | |||

V | V | V | | V | V | V | | |||

[R] [D]<--[C] [F] [H]<---[K] [N] | [R] [D]<--[C] [F] [H]<---[K] [N] | |||

^ | ^ ^ | ^ | ^ ^ | |||

| V | | | | V | | | |||

[A]------->[B] [G]---| [L]-->[M] | [A]------->[B] [G]---| [L]-->[M] | |||

(b) MRT-Blue | (b) MRT-Blue for destination R | |||

[E]---| [J]-------->[I] [P]-->[O] | [E]---| [J]-------->[I] [P]-->[O] | |||

| | | | | | | | |||

V V V | V V V | |||

[R] [D]-->[C]<---[F] [H]<---[K] [N] | [R] [D]-->[C]<---[F] [H]<---[K] [N] | |||

^ | ^ | ^ | | ^ | ^ | ^ | | |||

| V | | | V | | V | | | V | |||

[A]<-------[B] [G]<--| [L]<--[M] | [A]<-------[B] [G]<--| [L]<--[M] | |||

(c) MRT-Red | (c) MRT-Red for destionation R | |||

Figure 10 | Figure 10 | |||

Consider the example depicted in Figure 10 (a). In this figure, a | Consider the example depicted in Figure 10 (a). In this figure, a | |||

special graph is presented, showing us all the ways 2-connected | special graph is presented, showing us all the ways 2-connected | |||

clusters can be connected. It has four blocks: block 1 contains R, | clusters can be connected. It has four blocks: block 1 contains R, | |||

A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, | A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, | |||

L, M, N, O, P, and block 4 is a cut-link containing H and K. As can | L, M, N, O, P, and block 4 is a cut-link containing H and K. As can | |||

be observed, the first two blocks have one common node (node C) and | be observed, the first two blocks have one common node (node C) and | |||

blocks 2 and 3 do not have any common node, but they are connected | blocks 2 and 3 do not have any common node, but they are connected | |||

through a cut-link that is block 4. No two blocks can have more than | through a cut-link that is block 4. No two blocks can have more than | |||

one common node, since two blocks with at least 2 common nodes would | one common node, since two blocks with at least two common nodes | |||

qualify as a single 2-connected cluster. | would qualify as a single 2-connected cluster. | |||

Moreover, observe that if we want to get from one block to another, | Moreover, observe that if we want to get from one block to another, | |||

we must use a cut-vertex (the cut-vertices in this graph are C, H, | we must use a cut-vertex (the cut-vertices in this graph are C, H, | |||

K), regardless of the path selected, so we can say that all the paths | K), regardless of the path selected, so we can say that all the paths | |||

from block 3 along the MRTs rooted at R will cross K first. This | from block 3 along the MRTs rooted at R will cross K first. This | |||

observation means that if we want to find a pair of MRTs rooted at R, | observation means that if we want to find a pair of MRTs rooted at R, | |||

then we need to build up a pair of RTs in block 3 with K as a root. | then we need to build up a pair of RTs in block 3 with K as a root. | |||

Similarly, we need to find another pair of RTs in block 2 with C as a | Similarly, we need to find another pair of RTs in block 2 with C as a | |||

root, and finally, we need the last pair of RTs in block 1 with R as | root, and finally, we need the last pair of RTs in block 1 with R as | |||

a root. When all the trees are selected, we can simply combine them; | a root. When all the trees are selected, we can simply combine them; | |||

skipping to change at page 17, line 33 | skipping to change at page 17, line 33 | |||

4.5. Determining Local-Root and Assigning Block-ID | 4.5. Determining Local-Root and Assigning Block-ID | |||

Each node in a network graph has a local-root, which is the cut- | Each node in a network graph has a local-root, which is the cut- | |||

vertex (or root) in the same block that is closest to the root. The | vertex (or root) in the same block that is closest to the root. The | |||

local-root is used to determine whether two nodes share a common | local-root is used to determine whether two nodes share a common | |||

block. | block. | |||

Compute_Localroot(node x, node localroot) | Compute_Localroot(node x, node localroot) | |||

x.localroot = localroot | x.localroot = localroot | |||

for each DFS child c | for each DFS child node c of x | |||

if L(c) < D(x) //x is not a cut-vertex | if L(c) < D(x) //x is not a cut-vertex | |||

Compute_Localroot(c, x.localroot) | Compute_Localroot(c, x.localroot) | |||

else | else | |||

mark x as cut-vertex | mark x as cut-vertex | |||

Compute_Localroot(c, x) | Compute_Localroot(c, x) | |||

Compute_Localroot(root, root) | Compute_Localroot(root, root) | |||

Figure 11: A method for computing local-roots | Figure 11: A method for computing local-roots | |||

There are two different ways of computing the local-root for each | There are two different ways of computing the local-root for each | |||

node. The stand-alone method is given in Figure 11 and better | node. The stand-alone method is given in Figure 11 and better | |||

illustrates the concept; it is used by the MRT algorithms given in | illustrates the concept; it is used by the MRT algorithms given in | |||

the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm | the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm | |||

computes the local-root for a block as part of computing the GADAG | computes the local-root for a block as part of computing the GADAG | |||

using lowpoint inheritance; the essence of this computation is given | using lowpoint inheritance; the essence of this computation is given | |||

in Figure 12. | in Figure 12. Both methods for computing the local-root produce the | |||

same results. | ||||

Get the current node, s. | Get the current node, s. | |||

Compute an ear(either through lowpoint inheritance | Compute an ear(either through lowpoint inheritance | |||

or by following dfs parents) from s to a ready node e. | or by following dfs parents) from s to a ready node e. | |||

(Thus, s is not e, if there is such ear.) | (Thus, s is not e, if there is such ear.) | |||

if s is e | if s is e | |||

for each node x in the ear that is not s | for each node x in the ear that is not s | |||

x.localroot = s | x.localroot = s | |||

else | else | |||

for each node x in the ear that is not s or e | for each node x in the ear that is not s or e | |||

skipping to change at page 19, line 15 | skipping to change at page 19, line 15 | |||

5. Algorithm Sections | 5. Algorithm Sections | |||

This algorithm computes one GADAG that is then used by a router to | This algorithm computes one GADAG that is then used by a router to | |||

determine its MRT-Blue and MRT-Red next-hops to all destinations. | determine its MRT-Blue and MRT-Red next-hops to all destinations. | |||

Finally, based upon that information, alternates are selected for | Finally, based upon that information, alternates are selected for | |||

each next-hop to each destination. The different parts of this | each next-hop to each destination. The different parts of this | |||

algorithm are described below. These work on a network graph after | algorithm are described below. These work on a network graph after | |||

its interfaces have been ordered as per Figure 14. | its interfaces have been ordered as per Figure 14. | |||

1. Compute the local MRT Island for the particular MRT Profile. | 1. Compute the local MRT Island for the particular MRT Profile. | |||

[See Section 5.1.] | [See Section 5.2.] | |||

2. Select the root to use for the GADAG. [See Section 5.2.] | 2. Select the root to use for the GADAG. [See Section 5.3.] | |||

3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.] | 3. Initialize all interfaces to UNDIRECTED. [See Section 5.4.] | |||

4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See | 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See | |||

Figure 8.] | Figure 8.] | |||

5. Construct the GADAG. [See Section 5.4] | 5. Construct the GADAG. [See Section 5.5] | |||

6. Assign directions to all interfaces that are still UNDIRECTED. | 6. Assign directions to all interfaces that are still UNDIRECTED. | |||

[See Section 5.5.] | [See Section 5.6.] | |||

7. From the computing router x, compute the next-hops for the MRT- | 7. From the computing router x, compute the next-hops for the MRT- | |||

Blue and MRT-Red. [See Section 5.6.] | Blue and MRT-Red. [See Section 5.7.] | |||

8. Identify alternates for each next-hop to each destination by | 8. Identify alternates for each next-hop to each destination by | |||

determining which one of the blue MRT and the red MRT the | determining which one of the blue MRT and the red MRT the | |||

computing router x should select. [See Section 5.7.] | computing router x should select. [See Section 5.8.] | |||

5.1. Interface Ordering | ||||

To ensure consistency in computation, all routers MUST order | To ensure consistency in computation, all routers MUST order | |||

interfaces identically down to the set of links with the same metric | interfaces identically down to the set of links with the same metric | |||

to the same neighboring node. This is necessary for the DFS, where | to the same neighboring node. This is necessary for the DFS, where | |||

the selection order of the interfaces to explore results in different | the selection order of the interfaces to explore results in different | |||

trees, and for computing the GADAG, where the selection order of the | trees, and for computing the GADAG, where the selection order of the | |||

interfaces to use to form ears can result in different GADAGs. The | interfaces to use to form ears can result in different GADAGs. The | |||

required ordering between two interfaces from the same router x is | required ordering between two interfaces from the same router x is | |||

given in Figure 14. | given in Figure 14. | |||

Interface_Compare(interface a, interface b) | Interface_Compare(interface a, interface b) | |||

if a.metric < b.metric | if a.metric < b.metric | |||

return A_LESS_THAN_B | return A_LESS_THAN_B | |||

if b.metric < a.metric | if b.metric < a.metric | |||

return B_LESS_THAN_A | return B_LESS_THAN_A | |||

if a.neighbor.loopback_addr < b.neighbor.loopback_addr | if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id | |||

return A_LESS_THAN_B | return A_LESS_THAN_B | |||

if b.neighbor.loopback_addr < a.neighbor.loopback_addr | if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id | |||

return B_LESS_THAN_A | return B_LESS_THAN_A | |||

// Same metric to same node, so the order doesn't matter anymore for | // Same metric to same node, so the order doesn't matter for | |||

// interoperability. | // interoperability. | |||

// To have a unique, consistent total order, | return A_EQUAL_TO_B | |||

// tie-break in OSPF based on the link's linkData as | ||||

// distributed in an OSPF Router-LSA | ||||

if a.link_data < b.link_data | ||||

return A_LESS_THAN_B | ||||

return B_LESS_THAN_A | ||||

Figure 14: Rules for ranking multiple interfaces. Order is from low | Figure 14: Rules for ranking multiple interfaces. Order is from low | |||

to high. | to high. | |||

5.1. MRT Island Identification | In Figure 14, if two interfaces on a router connect to the same | |||

remote router with the same metric, the Interface_Compare function | ||||

returns A_EQUAL_TO_B. This is because the order in which those | ||||

interfaces are initially explored does not affect the final GADAG | ||||

produced by the algorithm described here. While only one of the | ||||

links will be added to the GADAG in the initial traversal, the other | ||||

parallel links will be added to the GADAG with the same direction | ||||

assigned during the procedure for assigning direction to UNDIRECTED | ||||

links described in Section 5.6. An implementation is free to apply | ||||

some additional criteria to break ties in interface ordering in this | ||||

situation, but that criteria is not specified here since it will not | ||||

affect the final GADAG produced by the algorithm. | ||||

The Interface_Compare function in Figure 14 relies on the | ||||

interface.metric and the interface.neighbor.mrt_node_id values to | ||||

order interfaces. The exact source of these values for different | ||||

IGPs (or flooding protocol in the case of ISIS-PCR | ||||

[I-D.farkas-isis-pcr]) and applications is specified in Figure 15. | ||||

The metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS | ||||

provided here is normative. The metric and mrt_node_id values for | ||||

ISIS-PCR should be considered informational. | ||||

+--------------+-----------------------+-----------------------------+ | ||||

| IGP/flooding | mrt_node_id | metric of | | ||||

| protocol | of neighbor | interface | | ||||

| and | on interface | | | ||||

| application | | | | ||||

+--------------+-----------------------+-----------------------------+ | ||||

| OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | | ||||

| IP/LDP FRR | Router ID in | for corresponding | | ||||

| | Link ID field for | point-to-point link | | ||||

| | corresponding | in Router-LSA | | ||||

| | point-to-point link | | | ||||

| | in Router-LSA | | | ||||

+--------------+-----------------------+-----------------------------+ | ||||

| OSPFv3 for | 4 octet Neighbor | 2 octet Metric field | | ||||

| IP/LDP FRR | Router ID field | for corresponding | | ||||

| | for corresponding | point-to-point link | | ||||

| | point-to-point link | in Router-LSA | | ||||

| | in Router-LSA | | | ||||

+--------------+-----------------------+-----------------------------+ | ||||

| IS-IS for | 7 octet neighbor | 3 octet metric field | | ||||

| IP/LDP FRR | system ID and | in Extended IS | | ||||

| | pseudonode number | Reachability TLV #22 | | ||||

| | in Extended IS | or Multi-Topology | | ||||

| | Reachability TLV #22 | IS Neighbor TLV #222 | | ||||

| | or Multi-Topology | | | ||||

| | IS Neighbor TLV #222 | | | ||||

+--------------+-----------------------+-----------------------------+ | ||||

| ISIS-PCR for | 8 octet Bridge ID | 3 octet SPB-LINK-METRIC in | | ||||

| protection | created from 2 octet | SPB-Metric sub-TLV (type 29)| | ||||

| of traffic | Bridge Priority in | in Extended IS Reachability | | ||||

| in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology | | ||||

| networks | (type 1) carried in | Intermediate Systems | | ||||

| | MT-Capability TLV | TLV #222. In the case | | ||||

| | #144 and 6 octet | of asymmetric link metrics, | | ||||

| | neighbor system ID in | the larger link metric | | ||||

| | Extended IS | is used for both link | | ||||

| | Reachability TLV #22 | directions. | | ||||

| | or Multi-Topology | (informational) | | ||||

| | Intermediate Systems | | | ||||

| | TLV #222 | | | ||||

| | (informational) | | | ||||

+--------------+-----------------------+-----------------------------+ | ||||

Figure 15: value of interface.neighbor.mrt_node_id and | ||||

interface.metric to be used for ranking interfaces, for different | ||||

flooding protocols and applications | ||||

The metrics are unsigned integers and MUST be compared as unsigned | ||||

integers. The results of mrt_node_id comparisons MUST be the same as | ||||

would be obtained by converting the mrt_node_ids to unsigned integers | ||||

using network byte order and performing the comparison as unsigned | ||||

integers. Also note that these values are only specified in the case | ||||

of point-to-point links. Therefore, in the case of IS-IS for IP/LDP | ||||

FRR, the pseudonode number (the 7th octet) will always be zero. | ||||

In the case of IS-IS for IP/LDP FRR, this specification allows for | ||||

the use of Multi-Topology routing. [RFC5120] requires that | ||||

information related to the standard/default topology (MT-ID = 0) be | ||||

carried in the Extended IS Reachability TLV #22, while it requires | ||||

that the Multi-Topology IS Neighbor TLV #222 only be used to carry | ||||

topology information related to non-default topologies (with non-zero | ||||

MT-IDs). [RFC5120] enforces this by requiring an implementation to | ||||

ignore TLV#222 with MT-ID = 0. The current document also requires | ||||

that TLV#222 with MT-ID = 0 MUST be ignored. | ||||

5.2. MRT Island Identification | ||||

The local MRT Island for a particular MRT profile can be determined | The local MRT Island for a particular MRT profile can be determined | |||

by starting from the computing router in the network graph and doing | by starting from the computing router in the network graph and doing | |||

a breadth-first-search (BFS). The BFS explores only links that are | a breadth-first-search (BFS). The BFS explores only links that are | |||

in the same area/level, are not IGP-excluded, and are not MRT- | in the same area/level, are not IGP-excluded, and are not MRT- | |||

ineligible. The BFS explores only nodes that are are not IGP- | ineligible. The BFS explores only nodes that are are not IGP- | |||

excluded, and that support the particular MRT profile. See section 7 | excluded, and that support the particular MRT profile. See section 7 | |||

of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions | of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions | |||

of these criteria. | of these criteria. | |||

skipping to change at page 20, line 52 | skipping to change at page 22, line 49 | |||

while (explore_list is not empty) | while (explore_list is not empty) | |||

next_rtr = remove_head(explore_list) | next_rtr = remove_head(explore_list) | |||

for each interface in next_rtr | for each interface in next_rtr | |||

if interface is (not MRT-ineligible and not IGP-excluded | if interface is (not MRT-ineligible and not IGP-excluded | |||

and in area) | and in area) | |||

if ((interface.remote_node supports profile_id) and | if ((interface.remote_node supports profile_id) and | |||

(interface.remote_node.IN_MRT_ISLAND is FALSE)) | (interface.remote_node.IN_MRT_ISLAND is FALSE)) | |||

interface.remote_node.IN_MRT_ISLAND = TRUE | interface.remote_node.IN_MRT_ISLAND = TRUE | |||

add_to_tail(explore_list, interface.remote_node) | add_to_tail(explore_list, interface.remote_node) | |||

Figure 15: MRT Island Identification | Figure 16: MRT Island Identification | |||

5.2. GADAG Root Selection | 5.3. GADAG Root Selection | |||

In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG | In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG | |||

Root Selection Policy is described for the MRT default profile. In | Root Selection Policy is described for the MRT default profile. In | |||

[I-D.atlas-ospf-mrt] and [I-D.li-isis-mrt], a mechanism is given for | [I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt], a mechanism is given for | |||

routers to advertise the GADAG Root Selection Priority and | routers to advertise the GADAG Root Selection Priority and | |||

consistently select a GADAG Root inside the local MRT Island. The | consistently select a GADAG Root inside the local MRT Island. The | |||

MRT Lowpoint algorithm simply requires that all routers in the MRT | MRT Lowpoint algorithm simply requires that all routers in the MRT | |||

Island MUST select the same GADAG Root; the mechanism can vary based | Island MUST select the same GADAG Root; the mechanism can vary based | |||

upon the MRT profile description. Before beginning computation, the | upon the MRT profile description. Before beginning computation, the | |||

network graph is reduced to contain only the set of routers that | network graph is reduced to contain only the set of routers that | |||

support the specific MRT profile whose MRTs are being computed. | support the specific MRT profile whose MRTs are being computed. | |||

Analysis has shown that the centrality of a router can have a | Analysis has shown that the centrality of a router can have a | |||

significant impact on the lengths of the alternate paths computed. | significant impact on the lengths of the alternate paths computed. | |||

Therefore, it is RECOMMENDED that off-line analysis that considers | Therefore, it is RECOMMENDED that off-line analysis that considers | |||

the centrality of a router be used to help determine how good a | the centrality of a router be used to help determine how good a | |||

choice a particular router is for the role of GADAG root. | choice a particular router is for the role of GADAG root. | |||

5.3. Initialization | 5.4. Initialization | |||

Before running the algorithm, there is the standard type of | Before running the algorithm, there is the standard type of | |||

initialization to be done, such as clearing any computed DFS-values, | initialization to be done, such as clearing any computed DFS-values, | |||

lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed | lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed | |||

next-hops, and flags associated with algorithm. | next-hops, and flags associated with algorithm. | |||

It is assumed that a regular SPF computation has been run so that the | It is assumed that a regular SPF computation has been run so that the | |||

primary next-hops from the computing router to each destination are | primary next-hops from the computing router to each destination are | |||

known. This is required for determining alternates at the last step. | known. This is required for determining alternates at the last step. | |||

Initially, all interfaces MUST be initialized to UNDIRECTED. Whether | Initially, all interfaces MUST be initialized to UNDIRECTED. Whether | |||

they are OUTGOING, INCOMING or both is determined when the GADAG is | they are OUTGOING, INCOMING or both is determined when the GADAG is | |||

constructed and augmented. | constructed and augmented. | |||

It is possible that some links and nodes will be marked as unusable | It is possible that some links and nodes will be marked as unusable | |||

using standard IGP mechanisms (see section 7 of | using standard IGP mechanisms (see section 7 of | |||

[I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability | [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability | |||

considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be | considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be | |||

desirable to administratively configure some interfaces as ineligible | desirable to administratively configure some interfaces as ineligible | |||

to carry MRT FRR traffic. This constraint MUST be consistently | to carry MRT FRR traffic. This constraint MUST be consistently | |||

flooded via the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] by the | flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-isis-mrt] by the | |||

owner of the interface, so that links are clearly known to be MRT- | owner of the interface, so that links are clearly known to be MRT- | |||

ineligible and not explored or used in the MRT algorithm. In the | ineligible and not explored or used in the MRT algorithm. In the | |||

algorithm description, it is assumed that such links and nodes will | algorithm description, it is assumed that such links and nodes will | |||

not be explored or used, and no more discussion is given of this | not be explored or used, and no more discussion is given of this | |||

restriction. | restriction. | |||

5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance | 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance | |||

As discussed in Section 4.2, it is necessary to find ears from a node | As discussed in Section 4.2, it is necessary to find ears from a node | |||

x that is already in the GADAG (known as IN_GADAG). Two different | x that is already in the GADAG (known as IN_GADAG). Two different | |||

methods are used to find ears in the algorithm. The first is by | methods are used to find ears in the algorithm. The first is by | |||

going to a not IN_GADAG DFS-child and then following the chain of | going to a not IN_GADAG DFS-child and then following the chain of | |||

low-point parents until an IN_GADAG node is found. The second is by | low-point parents until an IN_GADAG node is found. The second is by | |||

going to a not IN_GADAG neighbor and then following the chain of DFS | going to a not IN_GADAG neighbor and then following the chain of DFS | |||

parents until an IN_GADAG node is found. As an ear is found, the | parents until an IN_GADAG node is found. As an ear is found, the | |||

associated interfaces are marked based on the direction taken. The | associated interfaces are marked based on the direction taken. The | |||

nodes in the ear are marked as IN_GADAG. In the algorithm, first the | nodes in the ear are marked as IN_GADAG. In the algorithm, first the | |||

skipping to change at page 23, line 9 | skipping to change at page 25, line 9 | |||

the ear unless the end of the ear is x itself, in which case the | the ear unless the end of the ear is x itself, in which case the | |||

local-root for all the nodes in the ear would be x. This is because | local-root for all the nodes in the ear would be x. This is because | |||

whenever the first cycle is found in a block, or an ear involving a | whenever the first cycle is found in a block, or an ear involving a | |||

bridge is computed, the cut-vertex closest to the root would be x | bridge is computed, the cut-vertex closest to the root would be x | |||

itself. In all other scenarios, the properties of lowpoint/dfs | itself. In all other scenarios, the properties of lowpoint/dfs | |||

parents ensure that the end of the ear will be in the same block, and | parents ensure that the end of the ear will be in the same block, and | |||

thus inheriting its local-root would be the correct local-root for | thus inheriting its local-root would be the correct local-root for | |||

all newly added nodes. | all newly added nodes. | |||

The pseudo-code for the GADAG algorithm (assuming that the adjustment | The pseudo-code for the GADAG algorithm (assuming that the adjustment | |||

of lowpoint for cut-vertices has been made) is shown in Figure 16. | of lowpoint for cut-vertices has been made) is shown in Figure 17. | |||

Construct_Ear(x, Stack, intf, type) | Construct_Ear(x, Stack, intf, ear_type) | |||

ear_list = empty | ear_list = empty | |||

cur_node = intf.remote_node | cur_node = intf.remote_node | |||

cur_intf = intf | cur_intf = intf | |||

not_done = true | not_done = true | |||

while not_done | while not_done | |||

cur_intf.UNDIRECTED = false | cur_intf.UNDIRECTED = false | |||

cur_intf.OUTGOING = true | cur_intf.OUTGOING = true | |||

cur_intf.remote_intf.UNDIRECTED = false | cur_intf.remote_intf.UNDIRECTED = false | |||

cur_intf.remote_intf.INCOMING = true | cur_intf.remote_intf.INCOMING = true | |||

if cur_node.IN_GADAG is false | if cur_node.IN_GADAG is false | |||

cur_node.IN_GADAG = true | cur_node.IN_GADAG = true | |||

add_to_list_end(ear_list, cur_node) | add_to_list_end(ear_list, cur_node) | |||

if type is CHILD | if ear_type is CHILD | |||

cur_intf = cur_node.lowpoint_parent_intf | cur_intf = cur_node.lowpoint_parent_intf | |||

cur_node = cur_node.lowpoint_parent | cur_node = cur_node.lowpoint_parent | |||

else type must be NEIGHBOR | else // ear_type must be NEIGHBOR | |||

cur_intf = cur_node.dfs_parent_intf | cur_intf = cur_node.dfs_parent_intf | |||

cur_node = cur_node.dfs_parent | cur_node = cur_node.dfs_parent | |||

else | else | |||

not_done = false | not_done = false | |||

if (type is CHILD) and (cur_node is x) | if (ear_type is CHILD) and (cur_node is x) | |||

//x is a cut-vertex and the local root for | // x is a cut-vertex and the local root for | |||

//the block in which the ear is computed | // the block in which the ear is computed | |||

localroot = x | localroot = x | |||

else | else | |||

// Inherit local-root from the end of the ear | // Inherit local-root from the end of the ear | |||

localroot = cur_node.localroot | localroot = cur_node.localroot | |||

while ear_list is not empty | while ear_list is not empty | |||

y = remove_end_item_from_list(ear_list) | y = remove_end_item_from_list(ear_list) | |||

y.localroot = localroot | y.localroot = localroot | |||

push(Stack, y) | push(Stack, y) | |||

Construct_GADAG_via_Lowpoint(topology, root) | Construct_GADAG_via_Lowpoint(topology, root) | |||

root.IN_GADAG = true | root.IN_GADAG = true | |||

root.localroot = root | root.localroot = None | |||

Initialize Stack to empty | Initialize Stack to empty | |||

push root onto Stack | push root onto Stack | |||

while (Stack is not empty) | while (Stack is not empty) | |||

x = pop(Stack) | x = pop(Stack) | |||

foreach interface intf of x | foreach interface intf of x | |||

if ((intf.remote_node.IN_GADAG == false) and | if ((intf.remote_node.IN_GADAG == false) and | |||

(intf.remote_node.dfs_parent is x)) | (intf.remote_node.dfs_parent is x)) | |||

Construct_Ear(x, Stack, intf, CHILD) | Construct_Ear(x, Stack, intf, CHILD) | |||

foreach interface intf of x | foreach interface intf of x | |||

if ((intf.remote_node.IN_GADAG == false) and | if ((intf.remote_node.IN_GADAG == false) and | |||

(intf.remote_node.dfs_parent is not x)) | (intf.remote_node.dfs_parent is not x)) | |||

Construct_Ear(x, Stack, intf, NEIGHBOR) | Construct_Ear(x, Stack, intf, NEIGHBOR) | |||

Construct_GADAG_via_Lowpoint(topology, root) | Construct_GADAG_via_Lowpoint(topology, root) | |||

Figure 16: Low-point Inheritance GADAG algorithm | Figure 17: Low-point Inheritance GADAG algorithm | |||

5.5. Augmenting the GADAG by directing all links | 5.6. Augmenting the GADAG by directing all links | |||

The GADAG, regardless of the algorithm used to construct it, at this | The GADAG, regardless of the algorithm used to construct it, at this | |||

point could be used to find MRTs but the topology does not include | point could be used to find MRTs but the topology does not include | |||

all links in the network graph. That has two impacts. First, there | all links in the network graph. That has two impacts. First, there | |||

might be shorter paths that respect the GADAG partial ordering and so | might be shorter paths that respect the GADAG partial ordering and so | |||

the alternate paths would not be as short as possible. Second, there | the alternate paths would not be as short as possible. Second, there | |||

may be additional paths between a router x and the root that are not | may be additional paths between a router x and the root that are not | |||

included in the GADAG. Including those provides potentially more | included in the GADAG. Including those provides potentially more | |||

bandwidth to traffic flowing on the alternates and may reduce | bandwidth to traffic flowing on the alternates and may reduce | |||

congestion compared to just using the GADAG as currently constructed. | congestion compared to just using the GADAG as currently constructed. | |||

skipping to change at page 24, line 50 | skipping to change at page 26, line 50 | |||

the topological sort is that it works on DAGs and not ADAGs or | the topological sort is that it works on DAGs and not ADAGs or | |||

GADAGs. | GADAGs. | |||

To convert a GADAG to a DAG, it is necessary to remove all links that | To convert a GADAG to a DAG, it is necessary to remove all links that | |||

point to a root of block from within that block. That provides the | point to a root of block from within that block. That provides the | |||

necessary conversion to a DAG and then a topological sort can be | necessary conversion to a DAG and then a topological sort can be | |||

done. Finally, all UNDIRECTED links are assigned a direction based | done. Finally, all UNDIRECTED links are assigned a direction based | |||

upon the total ordering. Any UNDIRECTED links that connect to a root | upon the total ordering. Any UNDIRECTED links that connect to a root | |||

of a block from within that block are assigned a direction INCOMING | of a block from within that block are assigned a direction INCOMING | |||

to that root. The exact details of this whole process are captured | to that root. The exact details of this whole process are captured | |||

in Figure 17 | in Figure 18 | |||

Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) | Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) | |||

foreach node x in topo | foreach node x in topo | |||

if node x is a cut-vertex or root | if node x is a cut-vertex or root | |||

foreach interface i of x | foreach interface i of x | |||

if (i.remote_node.localroot is x) | if (i.remote_node.localroot is x) | |||

if i.UNDIRECTED | if i.UNDIRECTED | |||

i.OUTGOING = true | i.OUTGOING = true | |||

i.remote_intf.INCOMING = true | i.remote_intf.INCOMING = true | |||

i.UNDIRECTED = false | i.UNDIRECTED = false | |||

i.remote_intf.UNDIRECTED = false | i.remote_intf.UNDIRECTED = false | |||

skipping to change at page 25, line 35 | skipping to change at page 27, line 35 | |||

i.remote_intf.TEMP_UNUSABLE = false | i.remote_intf.TEMP_UNUSABLE = false | |||

if i.STORE_INCOMING and (mark_or_clear is CLEAR) | if i.STORE_INCOMING and (mark_or_clear is CLEAR) | |||

i.INCOMING = true | i.INCOMING = true | |||

i.STORE_INCOMING = false | i.STORE_INCOMING = false | |||

i.remote_intf.OUTGOING = true | i.remote_intf.OUTGOING = true | |||

i.remote_intf.STORE_OUTGOING = false | i.remote_intf.STORE_OUTGOING = false | |||

Run_Topological_Sort_GADAG(topo, root) | Run_Topological_Sort_GADAG(topo, root) | |||

Set_Block_Root_Incoming_Links(topo, root, MARK) | Set_Block_Root_Incoming_Links(topo, root, MARK) | |||

foreach node x | foreach node x | |||

set x.unvisited to the count of x's incoming interfaces | set x.unvisited to the count of x's incoming interfaces | |||

that aren't marked TEMP_UNUSABLE | that aren't marked TEMP_UNUSABLE | |||

Initialize working_list to empty | Initialize working_list to empty | |||

Initialize topo_order_list to empty | Initialize topo_order_list to empty | |||

add_to_list_end(working_list, root) | add_to_list_end(working_list, root) | |||

while working_list is not empty | while working_list is not empty | |||

y = remove_start_item_from_list(working_list) | y = remove_start_item_from_list(working_list) | |||

add_to_list_end(topo_order_list, y) | add_to_list_end(topo_order_list, y) | |||

foreach interface i of y | foreach interface i of y | |||

if (i.OUTGOING) and (not i.TEMP_UNUSABLE) | if (i.OUTGOING) and (not i.TEMP_UNUSABLE) | |||

i.remote_node.unvisited -= 1 | i.remote_node.unvisited -= 1 | |||

if i.remote_node.unvisited is 0 | if i.remote_node.unvisited is 0 | |||

add_to_list_end(working_list, i.remote_node) | add_to_list_end(working_list, i.remote_node) | |||

next_topo_order = 1 | next_topo_order = 1 | |||

while topo_order_list is not empty | while topo_order_list is not empty | |||

y = remove_start_item_from_list(topo_order_list) | y = remove_start_item_from_list(topo_order_list) | |||

y.topo_order = next_topo_order | y.topo_order = next_topo_order | |||

next_topo_order += 1 | next_topo_order += 1 | |||

Set_Block_Root_Incoming_Links(topo, root, CLEAR) | Set_Block_Root_Incoming_Links(topo, root, CLEAR) | |||

Add_Undirected_Links(topo, root) | Add_Undirected_Links(topo, root) | |||

Run_Topological_Sort_GADAG(topo, root) | Run_Topological_Sort_GADAG(topo, root) | |||

foreach node x in topo | foreach node x in topo | |||

foreach interface i of x | foreach interface i of x | |||

if i.UNDIRECTED | if i.UNDIRECTED | |||

if x.topo_order < i.remote_node.topo_order | if x.topo_order < i.remote_node.topo_order | |||

i.OUTGOING = true | i.OUTGOING = true | |||

i.UNDIRECTED = false | i.UNDIRECTED = false | |||

i.remote_intf.INCOMING = true | i.remote_intf.INCOMING = true | |||

i.remote_intf.UNDIRECTED = false | i.remote_intf.UNDIRECTED = false | |||

else | else | |||

i.INCOMING = true | i.INCOMING = true | |||

i.UNDIRECTED = false | i.UNDIRECTED = false | |||

i.remote_intf.OUTGOING = true | i.remote_intf.OUTGOING = true | |||

i.remote_intf.UNDIRECTED = false | i.remote_intf.UNDIRECTED = false | |||

Add_Undirected_Links(topo, root) | Add_Undirected_Links(topo, root) | |||

Figure 17: Assigning direction to UNDIRECTED links | Figure 18: Assigning direction to UNDIRECTED links | |||

Proxy-nodes do not need to be added to the network graph. They | Proxy-nodes do not need to be added to the network graph. They | |||

cannot be transited and do not affect the MRTs that are computed. | cannot be transited and do not affect the MRTs that are computed. | |||

The details of how the MRT-Blue and MRT-Red next-hops are computed | The details of how the MRT-Blue and MRT-Red next-hops are computed | |||

for proxy-nodes and how the appropriate alternate next-hops are | for proxy-nodes and how the appropriate alternate next-hops are | |||

selected is given in Section 5.8. | selected is given in Section 5.9. | |||

5.6. Compute MRT next-hops | 5.7. Compute MRT next-hops | |||

As was discussed in Section 4.1, once a ADAG is found, it is | As was discussed in Section 4.1, once a ADAG is found, it is | |||

straightforward to find the next-hops from any node X to the ADAG | straightforward to find the next-hops from any node X to the ADAG | |||

root. However, in this algorithm, we will reuse the common GADAG and | root. However, in this algorithm, we will reuse the common GADAG and | |||

find not only the one pair of MRTs rooted at the GADAG root with it, | find not only the one pair of MRTs rooted at the GADAG root with it, | |||

but find a pair rooted at each node. This is useful since it is | but find a pair rooted at each node. This is useful since it is | |||

significantly faster to compute. | significantly faster to compute. | |||

The method for computing differently rooted MRTs from the common | The method for computing differently rooted MRTs from the common | |||

GADAG is based on two ideas. First, if two nodes X and Y are ordered | GADAG is based on two ideas. First, if two nodes X and Y are ordered | |||

with respect to each other in the partial order, then an SPF along | with respect to each other in the partial order, then an SPF along | |||

OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a | OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a | |||

decreasing-SPF) can be used to find the increasing and decreasing | decreasing-SPF) can be used to find the increasing and decreasing | |||

paths. Second, if two nodes X and Y aren't ordered with respect to | paths. Second, if two nodes X and Y aren't ordered with respect to | |||

each other in the partial order, then intermediary nodes can be used | each other in the partial order, then intermediary nodes can be used | |||

to create the paths by increasing/decreasing to the intermediary and | to create the paths by increasing/decreasing to the intermediary and | |||

then decreasing/increasing to reach Y. | then decreasing/increasing to reach Y. | |||

As usual, the two basic ideas will be discussed assuming the network | As usual, the two basic ideas will be discussed assuming the network | |||

is two-connected. The generalization to multiple blocks is discussed | is two-connected. The generalization to multiple blocks is discussed | |||

in Section 5.6.4. The full algorithm is given in Section 5.6.5. | in Section 5.7.4. The full algorithm is given in Section 5.7.5. | |||

5.6.1. MRT next-hops to all nodes partially ordered with respect to the | 5.7.1. MRT next-hops to all nodes partially ordered with respect to the | |||

computing node | computing node | |||

To find two node-disjoint paths from the computing router X to any | To find two node-disjoint paths from the computing router X to any | |||

node Y, depends upon whether Y >> X or Y << X. As shown in | node Y, depends upon whether Y >> X or Y << X. As shown in | |||

Figure 18, if Y >> X, then there is an increasing path that goes from | Figure 19, if Y >> X, then there is an increasing path that goes from | |||

X to Y without crossing R; this contains nodes in the interval [X,Y]. | X to Y without crossing R; this contains nodes in the interval [X,Y]. | |||

There is also a decreasing path that decreases towards R and then | There is also a decreasing path that decreases towards R and then | |||

decreases from R to Y; this contains nodes in the interval | decreases from R to Y; this contains nodes in the interval | |||

[X,R-small] or [R-great,Y]. The two paths cannot have common nodes | [X,R-small] or [R-great,Y]. The two paths cannot have common nodes | |||

other than X and Y. | other than X and Y. | |||

[Y]<---(Cloud 2)<--- [X] | [Y]<---(Cloud 2)<--- [X] | |||

| ^ | | ^ | |||

| | | | | | |||

V | | V | | |||

(Cloud 3)--->[R]--->(Cloud 1) | (Cloud 3)--->[R]--->(Cloud 1) | |||

MRT-Blue path: X->Cloud 2->Y | MRT-Blue path: X->Cloud 2->Y | |||

MRT-Red path: X->Cloud 1->R->Cloud 3->Y | MRT-Red path: X->Cloud 1->R->Cloud 3->Y | |||

Figure 18: Y >> X | Figure 19: Y >> X | |||

Similar logic applies if Y << X, as shown in Figure 19. In this | Similar logic applies if Y << X, as shown in Figure 20. In this | |||

case, the increasing path from X increases to R and then increases | case, the increasing path from X increases to R and then increases | |||

from R to Y to use nodes in the intervals [X,R-great] and [R-small, | from R to Y to use nodes in the intervals [X,R-great] and [R-small, | |||

Y]. The decreasing path from X reaches Y without crossing R and uses | Y]. The decreasing path from X reaches Y without crossing R and uses | |||

nodes in the interval [Y,X]. | nodes in the interval [Y,X]. | |||

[X]<---(Cloud 2)<--- [Y] | [X]<---(Cloud 2)<--- [Y] | |||

| ^ | | ^ | |||

| | | | | | |||

V | | V | | |||

(Cloud 3)--->[R]--->(Cloud 1) | (Cloud 3)--->[R]--->(Cloud 1) | |||

MRT-Blue path: X->Cloud 3->R->Cloud 1->Y | MRT-Blue path: X->Cloud 3->R->Cloud 1->Y | |||

MRT-Red path: X->Cloud 2->Y | MRT-Red path: X->Cloud 2->Y | |||

Figure 19: Y << X | Figure 20: Y << X | |||

5.6.2. MRT next-hops to all nodes not partially ordered with respect to | 5.7.2. MRT next-hops to all nodes not partially ordered with respect to | |||

the computing node | the computing node | |||

When X and Y are not ordered, the first path should increase until we | When X and Y are not ordered, the first path should increase until we | |||

get to a node G, where G >> Y. At G, we need to decrease to Y. The | get to a node G, where G >> Y. At G, we need to decrease to Y. The | |||

other path should be just the opposite: we must decrease until we get | other path should be just the opposite: we must decrease until we get | |||

to a node H, where H << Y, and then increase. Since R is smaller and | to a node H, where H << Y, and then increase. Since R is smaller and | |||

greater than Y, such G and H must exist. It is also easy to see that | greater than Y, such G and H must exist. It is also easy to see that | |||

these two paths must be node disjoint: the first path contains nodes | these two paths must be node disjoint: the first path contains nodes | |||

in interval [X,G] and [Y,G], while the second path contains nodes in | in interval [X,G] and [Y,G], while the second path contains nodes in | |||

interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is | interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is | |||

necessary to decrease and then increase for the MRT-Blue and increase | necessary to decrease and then increase for the MRT-Blue and increase | |||

and then decrease for the MRT-Red; if one simply increased for one | and then decrease for the MRT-Red; if one simply increased for one | |||

and decreased for the other, then both paths would go through the | and decreased for the other, then both paths would go through the | |||

root R. | root R. | |||

(Cloud 6)<---[Y]<---(Cloud 5)<------------| | (Cloud 6)<---[Y]<---(Cloud 5)<------------| | |||

| | | | | | |||

| | | | | | |||

V | | V | | |||

[G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] | [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] | |||

^ | | ^ | | |||

| | | | | | |||

| | | | | | |||

(Cloud 3)<---[X]<---(Cloud 2)<-----------| | (Cloud 3)<---[X]<---(Cloud 2)<-----------| | |||

MRT-Blue path: decrease to H and increase to Y | MRT-Blue path: decrease to H and increase to Y | |||

X->Cloud 2->H->Cloud 5->Y | X->Cloud 2->H->Cloud 5->Y | |||

MRT-Red path: increase to G and decrease to Y | MRT-Red path: increase to G and decrease to Y | |||

X->Cloud 3->G->Cloud 6->Y | X->Cloud 3->G->Cloud 6->Y | |||

Figure 20: X and Y unordered | Figure 21: X and Y unordered | |||

This gives disjoint paths as long as G and H are not the same node. | This gives disjoint paths as long as G and H are not the same node. | |||

Since G >> Y and H << Y, if G and H could be the same node, that | Since G >> Y and H << Y, if G and H could be the same node, that | |||

would have to be the root R. This is not possible because there is | would have to be the root R. This is not possible because there is | |||

only one incoming interface to the root R which is created when the | only one incoming interface to the root R which is created when the | |||

initial cycle is found. Recall from Figure 6 that whenever an ear | initial cycle is found. Recall from Figure 6 that whenever an ear | |||

was found to have an end that was the root R, the ear was directed | was found to have an end that was the root R, the ear was directed | |||

from R so that the associated interface on R is outgoing and not | from R so that the associated interface on R is outgoing and not | |||

incoming. Therefore, there must be exactly one node M which is the | incoming. Therefore, there must be exactly one node M which is the | |||

largest one before R, so the MRT-Red path will never reach R; it will | largest one before R, so the MRT-Red path will never reach R; it will | |||

turn at M and decrease to Y. | turn at M and decrease to Y. | |||

5.6.3. Computing Redundant Tree next-hops in a 2-connected Graph | 5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph | |||

The basic ideas for computing RT next-hops in a 2-connected graph | The basic ideas for computing RT next-hops in a 2-connected graph | |||

were given in Section 5.6.1 and Section 5.6.2. Given these two | were given in Section 5.7.1 and Section 5.7.2. Given these two | |||

ideas, how can we find the trees? | ideas, how can we find the trees? | |||

If some node X only wants to find the next-hops (which is usually the | If some node X only wants to find the next-hops (which is usually the | |||

case for IP networks), it is enough to find which nodes are greater | case for IP networks), it is enough to find which nodes are greater | |||

and less than X, and which are not ordered; this can be done by | and less than X, and which are not ordered; this can be done by | |||

running an increasing-SPF and a decreasing-SPF rooted at X and not | running an increasing-SPF and a decreasing-SPF rooted at X and not | |||

exploring any links from the ADAG root. ( Traversal algorithms other | exploring any links from the ADAG root. | |||

than SPF could safely be used instead where one traversal takes the | ||||

links in their given directions and the other reverses the links' | In principle, an traversal method other than SPF could be used to | |||

directions.) | traverse the GADAG in the process of determining blue and red next- | |||

hops that result in maximally redundant trees. This will be the case | ||||

as long as one traversal uses the links in the direction specified by | ||||

the GADAG and the other traversal uses the links in the direction | ||||

opposite of that specified by the GADAG. However, a different | ||||

traversal algorithm will generally result in different blue and red | ||||

next-hops. Therefore, the algorithm specified here requires the use | ||||

of SPF to traverse the GADAG to generate MRT blue and red next-hops, | ||||

as described below. | ||||

An increasing-SPF rooted at X and not exploring links from the root | An increasing-SPF rooted at X and not exploring links from the root | |||

will find the increasing next-hops to all Y >> X. Those increasing | will find the increasing next-hops to all Y >> X. Those increasing | |||

next-hops are X's next-hops on the MRT-Blue to reach Y. A | next-hops are X's next-hops on the MRT-Blue to reach Y. A | |||

decreasing-SPF rooted at X and not exploring links from the root will | decreasing-SPF rooted at X and not exploring links from the root will | |||

find the decreasing next-hops to all Z << X. Those decreasing next- | find the decreasing next-hops to all Z << X. Those decreasing next- | |||

hops are X's next-hops on the MRT-Red to reach Z. Since the root R | hops are X's next-hops on the MRT-Red to reach Z. Since the root R | |||

is both greater than and less than X, after this increasing-SPF and | is both greater than and less than X, after this increasing-SPF and | |||

decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to | decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to | |||

reach R are known. For every node Y >> X, X's next-hops on the MRT- | reach R are known. For every node Y >> X, X's next-hops on the MRT- | |||

skipping to change at page 30, line 16 | skipping to change at page 32, line 24 | |||

| | | | ^ | | | | | | ^ | | |||

| | | V | | | | | | V | | | |||

R F C R F C | R F C R F C | |||

| | | | ^ ^ | | | | | ^ ^ | |||

| | | V | | | | | | V | | | |||

A---B---| A-->B---| | A---B---| A-->B---| | |||

(a) (b) | (a) (b) | |||

A 2-connected graph A spanning ADAG rooted at R | A 2-connected graph A spanning ADAG rooted at R | |||

Figure 21 | Figure 22 | |||

As an example consider the situation depicted in Figure 21. Node C | As an example consider the situation depicted in Figure 22. Node C | |||

runs an increasing-SPF and a decreasing-SPF on the ADAG. The | runs an increasing-SPF and a decreasing-SPF on the ADAG. The | |||

increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A | increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A | |||

and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was | and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was | |||

reached on the increasing path through D. And the MRT-Red next-hop | reached on the increasing path through D. And the MRT-Red next-hop | |||

towards E is B, since R was reached on the decreasing path through B. | towards E is B, since R was reached on the decreasing path through B. | |||

Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, | Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, | |||

ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R | ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R | |||

will similarly compute the MRT-Red next-hops towards E (which is | will similarly compute the MRT-Red next-hops towards E (which is | |||

ordered less than B, A and R), ensuring that a packet on MRT-Red will | ordered less than B, A and R), ensuring that a packet on MRT-Red will | |||

use path C-B-A-R-E. | use path C-B-A-R-E. | |||

C can determine the next-hops towards F as well. Since F is not | C can determine the next-hops towards F as well. Since F is not | |||

ordered with respect to C, the MRT-Blue next-hop is the decreasing | ordered with respect to C, the MRT-Blue next-hop is the decreasing | |||

one towards R (which is B) and the MRT-Red next-hop is the increasing | one towards R (which is B) and the MRT-Red next-hop is the increasing | |||

one towards R (which is D). Since F>>B, for its MRT-Blue next-hop | one towards R (which is D). Since F>>B, for its MRT-Blue next-hop | |||

towards F, B will use the real increasing next-hop towards F. So a | towards F, B will use the real increasing next-hop towards F. So a | |||

packet forwarded to B on MRT-Blue will get to F on path C-B-F. | packet forwarded to B on MRT-Blue will get to F on path C-B-F. | |||

Similarly, D will use the real decreasing next-hop towards F as its | Similarly, D will use the real decreasing next-hop towards F as its | |||

MRT-Red next-hop, an packet on MRT-Red will use path C-D-F. | MRT-Red next-hop, a packet on MRT-Red will use path C-D-F. | |||

5.6.4. Generalizing for a graph that isn't 2-connected | 5.7.4. Generalizing for a graph that isn't 2-connected | |||

If a graph isn't 2-connected, then the basic approach given in | If a graph isn't 2-connected, then the basic approach given in | |||

Section 5.6.3 needs some extensions to determine the appropriate MRT | Section 5.7.3 needs some extensions to determine the appropriate MRT | |||

next-hops to use for destinations outside the computing router X's | next-hops to use for destinations outside the computing router X's | |||

blocks. In order to find a pair of maximally redundant trees in that | blocks. In order to find a pair of maximally redundant trees in that | |||

graph we need to find a pair of RTs in each of the blocks (the root | graph we need to find a pair of RTs in each of the blocks (the root | |||

of these trees will be discussed later), and combine them. | of these trees will be discussed later), and combine them. | |||

When computing the MRT next-hops from a router X, there are three | When computing the MRT next-hops from a router X, there are three | |||

basic differences: | basic differences: | |||

1. Only nodes in a common block with X should be explored in the | 1. Only nodes in a common block with X should be explored in the | |||

increasing-SPF and decreasing-SPF. | increasing-SPF and decreasing-SPF. | |||

skipping to change at page 31, line 27 | skipping to change at page 33, line 35 | |||

increasing-SPF or decreasing-SPF, then W is unordered with | increasing-SPF or decreasing-SPF, then W is unordered with | |||

respect to X. X's MRT-Blue next-hops to W are X's decreasing | respect to X. X's MRT-Blue next-hops to W are X's decreasing | |||

(aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- | (aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- | |||

hops to W are X's increasing (aka MRT-Blue) next-hops to X's | hops to W are X's increasing (aka MRT-Blue) next-hops to X's | |||

local-root. | local-root. | |||

3. For nodes in different blocks, the next-hops must be inherited | 3. For nodes in different blocks, the next-hops must be inherited | |||

via the relevant cut-vertex. | via the relevant cut-vertex. | |||

These are all captured in the detailed algorithm given in | These are all captured in the detailed algorithm given in | |||

Section 5.6.5. | Section 5.7.5. | |||

5.6.5. Complete Algorithm to Compute MRT Next-Hops | 5.7.5. Complete Algorithm to Compute MRT Next-Hops | |||

The complete algorithm to compute MRT Next-Hops for a particular | The complete algorithm to compute MRT Next-Hops for a particular | |||

router X is given in Figure 22. In addition to computing the MRT- | router X is given in Figure 23. In addition to computing the MRT- | |||

Blue next-hops and MRT-Red next-hops used by X to reach each node Y, | Blue next-hops and MRT-Red next-hops used by X to reach each node Y, | |||

the algorithm also stores an "order_proxy", which is the proper cut- | the algorithm also stores an "order_proxy", which is the proper cut- | |||

vertex to reach Y if it is outside the block, and which is used later | vertex to reach Y if it is outside the block, and which is used later | |||

in deciding whether the MRT-Blue or the MRT-Red can provide an | in deciding whether the MRT-Blue or the MRT-Red can provide an | |||

acceptable alternate for a particular primary next-hop. | acceptable alternate for a particular primary next-hop. | |||

In_Common_Block(x, y) | In_Common_Block(x, y) | |||

if (((x.localroot is y.localroot) and (x.block_id is y.block_id)) | if ( (x.block_id is y.block_id)) | |||

or (x is y.localroot) or (y is x.localroot)) | or (x is y.localroot) or (y is x.localroot) ) | |||

return true | return true | |||

return false | return false | |||

Store_Results(y, direction, spf_root, store_nhs) | Store_Results(y, direction) | |||

if direction is FORWARD | if direction is FORWARD | |||

y.higher = true | y.higher = true | |||

if store_nhs | y.blue_next_hops = y.next_hops | |||

y.blue_next_hops = y.next_hops | if direction is REVERSE | |||

if direction is REVERSE | y.lower = true | |||

y.lower = true | y.red_next_hops = y.next_hops | |||

if store_nhs | ||||

y.red_next_hops = y.next_hops | ||||

SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs) | SPF_No_Traverse_Root(spf_root, block_root, direction) | |||

Initialize spf_heap to empty | Initialize spf_heap to empty | |||

Initialize nodes' spf_metric to infinity and next_hops to empty | Initialize nodes' spf_metric to infinity and next_hops to empty | |||

spf_root.spf_metric = 0 | spf_root.spf_metric = 0 | |||

insert(spf_heap, spf_root) | insert(spf_heap, spf_root) | |||

while (spf_heap is not empty) | while (spf_heap is not empty) | |||

min_node = remove_lowest(spf_heap) | min_node = remove_lowest(spf_heap) | |||

Store_Results(min_node, direction, spf_root, store_nhs) | Store_Results(min_node, direction) | |||

if ((min_node is spf_root) or (min_node is not block_root)) | if ((min_node is spf_root) or (min_node is not block_root)) | |||

foreach interface intf of min_node | foreach interface intf of min_node | |||

if (((direction is FORWARD) and intf.OUTGOING) or | if ( ( ((direction is FORWARD) and intf.OUTGOING) or | |||

((direction is REVERSE) and intf.INCOMING) and | ((direction is REVERSE) and intf.INCOMING) ) | |||

In_Common_Block(spf_root, intf.remote_node)) | and In_Common_Block(spf_root, intf.remote_node) ) | |||

path_metric = min_node.spf_metric + intf.metric | path_metric = min_node.spf_metric + intf.metric | |||

if path_metric < intf.remote_node.spf_metric | if path_metric < intf.remote_node.spf_metric | |||

intf.remote_node.spf_metric = path_metric | intf.remote_node.spf_metric = path_metric | |||

if min_node is spf_root | if min_node is spf_root | |||

intf.remote_node.next_hops = make_list(intf) | intf.remote_node.next_hops = make_list(intf) | |||

else | else | |||

intf.remote_node.next_hops = min_node.next_hops | intf.remote_node.next_hops = min_node.next_hops | |||

insert_or_update(spf_heap, intf.remote_node) | insert_or_update(spf_heap, intf.remote_node) | |||

else if path_metric is intf.remote_node.spf_metric | else if path_metric is intf.remote_node.spf_metric | |||

if min_node is spf_root | if min_node is spf_root | |||

add_to_list(intf.remote_node.next_hops, intf) | add_to_list(intf.remote_node.next_hops, intf) | |||

else | else | |||

add_list_to_list(intf.remote_node.next_hops, | add_list_to_list(intf.remote_node.next_hops, | |||

min_node.next_hops) | min_node.next_hops) | |||

SetEdge(y) | SetEdge(y) | |||

if y.blue_next_hops is empty and y.red_next_hops is empty | if y.blue_next_hops is empty and y.red_next_hops is empty | |||

if (y.local_root != y) { | if (y.localroot != y) | |||

SetEdge(y.localroot) | SetEdge(y.localroot) | |||

} | y.blue_next_hops = y.localroot.blue_next_hops | |||

y.blue_next_hops = y.localroot.blue_next_hops | y.red_next_hops = y.localroot.red_next_hops | |||

y.red_next_hops = y.localroot.red_next_hops | y.order_proxy = y.localroot.order_proxy | |||

y.order_proxy = y.localroot.order_proxy | ||||

Compute_MRT_NextHops(x, root) | Compute_MRT_NextHops(x, root) | |||

foreach node y | foreach node y | |||

y.higher = y.lower = false | y.higher = y.lower = false | |||

clear y.red_next_hops and y.blue_next_hops | clear y.red_next_hops and y.blue_next_hops | |||

y.order_proxy = y | y.order_proxy = y | |||

SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE) | SPF_No_Traverse_Root(x, x.localroot, FORWARD) | |||

SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE) | SPF_No_Traverse_Root(x, x.localroot, REVERSE) | |||

// red and blue next-hops are stored to x.localroot as different | // red and blue next-hops are stored to x.localroot as different | |||

// paths are found via the SPF and reverse-SPF. | // paths are found via the SPF and reverse-SPF. | |||

// Similarly any nodes whose local-root is x will have their | // Similarly any nodes whose local-root is x will have their | |||

// red_next_hops and blue_next_hops already set. | // red_next_hops and blue_next_hops already set. | |||

// Handle nodes in the same block that aren't the local-root | // Handle nodes in the same block that aren't the local-root | |||

foreach node y | foreach node y | |||

if (y.IN_MRT_ISLAND and (y is not x) and | if (y.IN_MRT_ISLAND and (y is not x) and | |||

(y.localroot is x.localroot) and | (y.block_id is x.block_id) ) | |||

((y is x.localroot) or (x is y.localroot) or | if y.higher | |||

(y.block_id is x.block_id))) | y.red_next_hops = x.localroot.red_next_hops | |||

if y.higher | else if y.lower | |||

y.red_next_hops = x.localroot.red_next_hops | y.blue_next_hops = x.localroot.blue_next_hops | |||

else if y.lower | else | |||

y.blue_next_hops = x.localroot.blue_next_hops | y.blue_next_hops = x.localroot.red_next_hops | |||

else | y.red_next_hops = x.localroot.blue_next_hops | |||

y.blue_next_hops = x.localroot.red_next_hops | ||||

y.red_next_hops = x.localroot.blue_next_hops | ||||

// Inherit next-hops and order_proxies to other components | // Inherit next-hops and order_proxies to other components | |||

if x is not root | if x is not root | |||

root.blue_next_hops = x.localroot.blue_next_hops | root.blue_next_hops = x.localroot.blue_next_hops | |||

root.red_next_hops = x.localroot.red_next_hops | root.red_next_hops = x.localroot.red_next_hops | |||

root.order_proxy = x.localroot | root.order_proxy = x.localroot | |||

foreach node y | foreach node y | |||

if (y is not root) and (y is not x) and y.IN_MRT_ISLAND | if (y is not root) and (y is not x) and y.IN_MRT_ISLAND | |||

SetEdge(y) | SetEdge(y) | |||

max_block_id = 0 | max_block_id = 0 | |||

Assign_Block_ID(root, max_block_id) | Assign_Block_ID(root, max_block_id) | |||

Compute_MRT_NextHops(x, root) | Compute_MRT_NextHops(x, root) | |||

Figure 22 | Figure 23 | |||

5.7. Identify MRT alternates | 5.8. Identify MRT alternates | |||

At this point, a computing router S knows its MRT-Blue next-hops and | At this point, a computing router S knows its MRT-Blue next-hops and | |||

MRT-Red next-hops for each destination in the MRT Island. The | MRT-Red next-hops for each destination in the MRT Island. The | |||

primary next-hops along the SPT are also known. It remains to | primary next-hops along the SPT are also known. It remains to | |||

determine for each primary next-hop to a destination D, which of the | determine for each primary next-hop to a destination D, which of the | |||

MRTs avoids the primary next-hop node F. This computation depends | MRTs avoids the primary next-hop node F. This computation depends | |||

upon data set in Compute_MRT_NextHops such as each node y's | upon data set in Compute_MRT_NextHops such as each node y's | |||

y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower | y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower | |||

and topo_orders. Recall that any router knows only which are the | and topo_orders. Recall that any router knows only which are the | |||

nodes greater and lesser than itself, but it cannot decide the | nodes greater and lesser than itself, but it cannot decide the | |||

relation between any two given nodes easily; that is why we need | relation between any two given nodes easily; that is why we need | |||

topological ordering. | topological ordering. | |||

For each primary next-hop node F to each destination D, S can call | For each primary next-hop node F to each destination D, S can call | |||

Select_Alternates(S, D, F, primary_intf) to determine whether to use | Select_Alternates(S, D, F, primary_intf) to determine whether to use | |||

the MRT-Blue next-hops as the alternate next-hop(s) for that primary | the MRT-Blue next-hops as the alternate next-hop(s) for that primary | |||

next hop or to use the MRT-Red next-hops. The algorithm is given in | next hop or to use the MRT-Red next-hops. The algorithm is given in | |||

Figure 23 and discussed afterwards. | Figure 24 and discussed afterwards. | |||

Select_Alternates_Internal(S, D, F, primary_intf, | Select_Alternates_Internal(S, D, F, primary_intf, | |||

D_lower, D_higher, D_topo_order) | D_lower, D_higher, D_topo_order) | |||

//When D==F, we can do only link protection | //When D==F, we can do only link protection | |||

if ((D is F) or (D.order_proxy is F)) | if ((D is F) or (D.order_proxy is F)) | |||

if an MRT doesn't use primary_intf | if an MRT doesn't use primary_intf | |||

indicate alternate is not node-protecting | indicate alternate is not node-protecting | |||

return that MRT color | return that MRT color | |||

else // parallel links are cut-links | else // parallel links are cut-links | |||

skipping to change at page 34, line 42 | skipping to change at page 36, line 44 | |||

return USE_BLUE | return USE_BLUE | |||

if (F.lower and F.higher) | if (F.lower and F.higher) | |||

if D_lower | if D_lower | |||

return USE_RED | return USE_RED | |||

else if D_higher | else if D_higher | |||

return USE_BLUE | return USE_BLUE | |||

else | else | |||

if primary_intf.OUTGOING and primary_intf.INCOMING | if primary_intf.OUTGOING and primary_intf.INCOMING | |||

return AVOID_LINK_ON_BLUE | return AVOID_LINK_ON_BLUE | |||

if primary_intf.OUTGOING is true | if primary_intf.OUTGOING | |||

return USE_BLUE | return USE_BLUE | |||

if primary_intf.INCOMING is true | if primary_intf.INCOMING | |||

return USE_RED | return USE_RED | |||

if D_higher | if D_higher | |||

if F.higher | if F.higher | |||

if F.topo_order < D_topo_order | if F.topo_order < D_topo_order | |||

return USE_RED | return USE_RED | |||

else | else | |||

return USE_BLUE | return USE_BLUE | |||

else if F.lower | else if F.lower | |||

return USE_BLUE | return USE_BLUE | |||

else | else | |||

// F and S are neighbors so either F << S or F >> S | // F and S are neighbors so either F << S or F >> S | |||

else if D_lower | else if D_lower | |||

if F.higher | if F.higher | |||

return USE_RED | return USE_RED | |||

else if F.lower | else if F.lower | |||

if F.topo_order < D_topo_order | if F.topo_order < D_topo_order | |||

return USE_RED | return USE_RED | |||

else | else | |||

return USE_BLUE | return USE_BLUE | |||

else | else | |||

// F and S are neighbors so either F << S or F >> S | // F and S are neighbors so either F << S or F >> S | |||

else // D and S not ordered | else // D and S not ordered | |||

if F.lower | if F.lower | |||

return USE_RED | return USE_RED | |||

else if F.higher | else if F.higher | |||

return USE_BLUE | return USE_BLUE | |||

else | else | |||

// F and S are neighbors so either F << S or F >> S | // F and S are neighbors so either F << S or F >> S | |||

Select_Alternates(S, D, F, primary_intf) | Select_Alternates(S, D, F, primary_intf) | |||

if D.order_proxy is not D | if D.order_proxy is not D | |||

D_lower = D.order_proxy.lower | D_lower = D.order_proxy.lower | |||

D_higher = D.order_proxy.higher | D_higher = D.order_proxy.higher | |||

D_topo_order = D.order_proxy.topo_order | D_topo_order = D.order_proxy.topo_order | |||

else | else | |||

D_lower = D.lower | D_lower = D.lower | |||

D_higher = D.higher | D_higher = D.higher | |||

D_topo_order = D.topo_order | D_topo_order = D.topo_order | |||

return Select_Alternates_Internal(S, D, F, primary_intf, | return Select_Alternates_Internal(S, D, F, primary_intf, | |||

D_lower, D_higher, D_topo_order) | D_lower, D_higher, D_topo_order) | |||

Figure 23 | Figure 24 | |||

If either D>>S>>F or D<<S<<F holds true, the situation is simple: in | If either D>>S>>F or D<<S<<F holds true, the situation is simple: in | |||

the first case we should choose the increasing Blue next-hop, in the | the first case we should choose the increasing Blue next-hop, in the | |||

second case, the decreasing Red next-hop is the right choice. | second case, the decreasing Red next-hop is the right choice. | |||

However, when both D and F are greater than S the situation is not so | However, when both D and F are greater than S the situation is not so | |||

simple, there can be three possibilities: (i) F>>D (ii) F<<D or (iii) | simple, there can be three possibilities: (i) F>>D (ii) F<<D or (iii) | |||

F and D are not ordered. In the first case, we should choose the | F and D are not ordered. In the first case, we should choose the | |||

path towards D along the Blue tree. In contrast, in case (ii) the | path towards D along the Blue tree. In contrast, in case (ii) the | |||

Red path towards the root and then to D would be the solution. | Red path towards the root and then to D would be the solution. | |||

skipping to change at page 36, line 47 | skipping to change at page 38, line 50 | |||

situation, they are probably already ECMP. | situation, they are probably already ECMP. | |||

Finally, there is the case where D is also F. In this case, only | Finally, there is the case where D is also F. In this case, only | |||

link protection is possible. The MRT that doesn't use the indicated | link protection is possible. The MRT that doesn't use the indicated | |||

primary next-hop is used. If both MRTs use the primary next-hop, | primary next-hop is used. If both MRTs use the primary next-hop, | |||

then the primary next-hop must be a cut-link so either MRT could be | then the primary next-hop must be a cut-link so either MRT could be | |||

used but the set of MRT next-hops must be pruned to avoid that | used but the set of MRT next-hops must be pruned to avoid that | |||

primary next-hop. To indicate this case, Select_Alternates returns | primary next-hop. To indicate this case, Select_Alternates returns | |||

AVOID_LINK_ON_BLUE. | AVOID_LINK_ON_BLUE. | |||

As an example, consider the ADAG depicted in Figure 24 and first | As an example, consider the ADAG depicted in Figure 25 and first | |||

suppose that G is the source, D is the destination and H is the | suppose that G is the source, D is the destination and H is the | |||

failed next-hop. Since D>>G, we need to compare H.topo_order and | failed next-hop. Since D>>G, we need to compare H.topo_order and | |||

D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller | D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller | |||

than H, so we should select the decreasing path towards the root. | than H, so we should select the decreasing path towards the root. | |||

If, however, the destination were instead J, we must find that | If, however, the destination were instead J, we must find that | |||

H.topo_order>J.topo_order, so we must choose the increasing Blue | H.topo_order>J.topo_order, so we must choose the increasing Blue | |||

next-hop to J, which is I. In the case, when instead the destination | next-hop to J, which is I. In the case, when instead the destination | |||

is C, we find that we need to first decrease to avoid using H, so the | is C, we find that we need to first decrease to avoid using H, so the | |||

Blue, first decreasing then increasing, path is selected. | Blue, first decreasing then increasing, path is selected. | |||

[E]<-[D]<-[H]<-[J] | [E]<-[D]<-[H]<-[J] | |||

| ^ ^ ^ | | ^ ^ ^ | |||

V | | | | V | | | | |||

[R] [C] [G]->[I] | [R] [C] [G]->[I] | |||

skipping to change at page 37, line 19 | skipping to change at page 39, line 21 | |||

Blue, first decreasing then increasing, path is selected. | Blue, first decreasing then increasing, path is selected. | |||

[E]<-[D]<-[H]<-[J] | [E]<-[D]<-[H]<-[J] | |||

| ^ ^ ^ | | ^ ^ ^ | |||

V | | | | V | | | | |||

[R] [C] [G]->[I] | [R] [C] [G]->[I] | |||

| ^ ^ ^ | | ^ ^ ^ | |||

V | | | | V | | | | |||

[A]->[B]->[F]---| | [A]->[B]->[F]---| | |||

(a) | (a)ADAG rooted at R for | |||

a 2-connected graph | a 2-connected graph | |||

Figure 24 | Figure 25 | |||

5.8. Finding FRR Next-Hops for Proxy-Nodes | 5.9. Finding FRR Next-Hops for Proxy-Nodes | |||

As discussed in Section 10.2 of | As discussed in Section 10.2 of | |||

[I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- | [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- | |||

Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- | Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- | |||

nodes. An example case is for a router that is not part of that | nodes. An example case is for a router that is not part of that | |||

local MRT Island, when there is only partial MRT support in the | local MRT Island, when there is only partial MRT support in the | |||

domain. | domain. | |||

A first incorrect and naive approach to handling proxy-nodes, which | A first incorrect and naive approach to handling proxy-nodes, which | |||

cannot be transited, is to simply add these proxy-nodes to the graph | cannot be transited, is to simply add these proxy-nodes to the graph | |||

skipping to change at page 39, line 6 | skipping to change at page 41, line 6 | |||

4 A<<S<<B Red to A Blue to B | 4 A<<S<<B Red to A Blue to B | |||

5 A<<S Red to A Blue to R S not ordered w/ B | 5 A<<S Red to A Blue to R S not ordered w/ B | |||

6 S<<B Red to R Blue to B S not ordered w/ A | 6 S<<B Red to R Blue to B S not ordered w/ A | |||

7 Otherwise Red to R Blue to R S not ordered w/ A+B | 7 Otherwise Red to R Blue to R S not ordered w/ A+B | |||

These rules are realized in the following pseudocode where P is the | These rules are realized in the following pseudocode where P is the | |||

proxy-node, X and Y are the nodes that P is attached to, and S is the | proxy-node, X and Y are the nodes that P is attached to, and S is the | |||

computing router: | computing router: | |||

Select_Proxy_Node_NHs(P, S, X, Y) | Select_Proxy_Node_NHs(P, S, X, Y) | |||

if (X.order_proxy.topo_order < Y.order_proxy.topo_order) | if (X.order_proxy.topo_order < Y.order_proxy.topo_order) | |||

//This fits even if X.order_proxy=S.local_root | //This fits even if X.order_proxy=S.local_root | |||

A=X.order_proxy | A=X.order_proxy | |||

B=Y.order_proxy | B=Y.order_proxy | |||

else | else | |||

A=Y.order_proxy | A=Y.order_proxy | |||

B=X.order_proxy | B=X.order_proxy | |||

if (S==A.local_root) | if (S==A.local_root) | |||

P.blue_next_hops = A.blue_next_hops | P.blue_next_hops = A.blue_next_hops | |||

P.red_next_hops = B.red_next_hops | P.red_next_hops = B.red_next_hops | |||

return | return | |||

if (A.higher) | if (A.higher) | |||

P.blue_next_hops = A.blue_next_hops | P.blue_next_hops = A.blue_next_hops | |||

P.red_next_hops = R.red_next_hops | P.red_next_hops = R.red_next_hops | |||

return | return | |||

if (B.lower) | if (B.lower) | |||

P.blue_next_hops = R.blue_next_hops | P.blue_next_hops = R.blue_next_hops | |||

P.red_next_hops = B.red_next_hops | P.red_next_hops = B.red_next_hops | |||

return | return | |||

if (A.lower && B.higher) | if (A.lower && B.higher) | |||

P.blue_next_hops = A.red_next_hops | P.blue_next_hops = A.red_next_hops | |||

P.red_next_hops = B.blue_next_hops | P.red_next_hops = B.blue_next_hops | |||

return | return | |||

if (A.lower) | if (A.lower) | |||

P.blue_next_hops = R.red_next_hops | ||||

P.red_next_hops = B.blue_next_hops | ||||

return | ||||

if (B.higher) | ||||

P.blue_next_hops = A.red_next_hops | ||||

P.red_next_hops = R.blue_next_hops | ||||

return | ||||

P.blue_next_hops = R.red_next_hops | P.blue_next_hops = R.red_next_hops | |||

P.red_next_hops = B.blue_next_hops | ||||

return | ||||

if (B.higher) | ||||

P.blue_next_hops = A.red_next_hops | ||||

P.red_next_hops = R.blue_next_hops | P.red_next_hops = R.blue_next_hops | |||

return | return | |||

P.blue_next_hops = R.red_next_hops | ||||

P.red_next_hops = R.blue_next_hops | ||||

return | ||||

After finding the the red and the blue next-hops, it is necessary to | After finding the the red and the blue next-hops, it is necessary to | |||

know which one of these to use in the case of failure. This can be | know which one of these to use in the case of failure. This can be | |||

done by Select_Alternates_Inner(). In order to use | done by Select_Alternates_Inner(). In order to use | |||

Select_Alternates_Internal(), we need to know if P is greater, less | Select_Alternates_Internal(), we need to know if P is greater, less | |||

or unordered with S, and P.topo_order. P.lower = B.lower, P.higher = | or unordered with S, and P.topo_order. P.lower = B.lower, P.higher = | |||

A.higher, and any value is OK for P.topo_order, as long as | A.higher, and any value is OK for P.topo_order, as long as | |||

A.topo_order<=P.topo_order<=B.topo_order and P.topo_order is not | A.topo_order<=P.topo_order<=B.topo_order and P.topo_order is not | |||

equal to the topo_order of the failed node. So for simplicity let | equal to the topo_order of the failed node. So for simplicity let | |||

P.topo_order=A.topo_order when the next-hop is not A, and | P.topo_order=A.topo_order when the next-hop is not A, and | |||

skipping to change at page 40, line 19 | skipping to change at page 42, line 19 | |||

return Select_Alternates_Internal(S, P, F, primary_intf, | return Select_Alternates_Internal(S, P, F, primary_intf, | |||

P.neighbor_B.lower, | P.neighbor_B.lower, | |||

P.neighbor_A.higher, | P.neighbor_A.higher, | |||

P.neighbor_A.topo_order) | P.neighbor_A.topo_order) | |||

else | else | |||

return Select_Alternates_Internal(S, P, F, primary_intf, | return Select_Alternates_Internal(S, P, F, primary_intf, | |||

P.neighbor_B.lower, | P.neighbor_B.lower, | |||

P.neighbor_A.higher, | P.neighbor_A.higher, | |||

P.neighbor_B.topo_order) | P.neighbor_B.topo_order) | |||

Figure 25 | Figure 26 | |||

6. MRT Lowpoint Algorithm: Next-hop conformance | 6. MRT Lowpoint Algorithm: Next-hop conformance | |||

This specification defines the MRT Lowpoint Algorithm, which include | This specification defines the MRT Lowpoint Algorithm, which include | |||

the construction of a common GADAG and the computation of MRT-Red and | the construction of a common GADAG and the computation of MRT-Red and | |||

MRT-Blue next-hops to each node in the graph. An implementation MAY | MRT-Blue next-hops to each node in the graph. An implementation MAY | |||

select any subset of next-hops for MRT-Red and MRT-Blue that respect | select any subset of next-hops for MRT-Red and MRT-Blue that respect | |||

the available nodes that are described in Section 5.6 for each of the | the available nodes that are described in Section 5.7 for each of the | |||

MRT-Red and MRT-Blue and the selected next-hops are further along in | MRT-Red and MRT-Blue and the selected next-hops are further along in | |||

the interval of allowed nodes towards the destination. | the interval of allowed nodes towards the destination. | |||

For example, the MRT-Blue next-hops used when the destination Y >> X, | For example, the MRT-Blue next-hops used when the destination Y >> X, | |||

the computing router, MUST be one or more nodes, T, whose topo_order | the computing router, MUST be one or more nodes, T, whose topo_order | |||

is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y | is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y | |||

is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in | is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in | |||

the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, | the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, | |||

R-big.topo_order]. | R-big.topo_order]. | |||

skipping to change at page 41, line 23 | skipping to change at page 43, line 23 | |||

they did not provide significant differences in the path lenghts for | they did not provide significant differences in the path lenghts for | |||

the alternatives. This section does not focus on that analysis or | the alternatives. This section does not focus on that analysis or | |||

the decision to use the MRT Lowpoint algorithm as the default MRT | the decision to use the MRT Lowpoint algorithm as the default MRT | |||

algorithm; it has the lowest computational and storage requirements | algorithm; it has the lowest computational and storage requirements | |||

and gave comparable results. | and gave comparable results. | |||

Since this document defines the MRT Lowpoint algorithm for use in | Since this document defines the MRT Lowpoint algorithm for use in | |||

fast-reroute applications, it is useful to compare MRT and Remote LFA | fast-reroute applications, it is useful to compare MRT and Remote LFA | |||

[I-D.ietf-rtgwg-remote-lfa]. This section compares MRT and remote | [I-D.ietf-rtgwg-remote-lfa]. This section compares MRT and remote | |||

LFA for IP Fast Reroute in 19 service provider network topologies, | LFA for IP Fast Reroute in 19 service provider network topologies, | |||

focusing on coverage and alternate path length. Figure 26 shows the | focusing on coverage and alternate path length. Figure 27 shows the | |||

node-protecting coverage provided by local LFA (LLFA), remote LFA | node-protecting coverage provided by local LFA (LLFA), remote LFA | |||

(RLFA), and MRT against different failure scenarios in these | (RLFA), and MRT against different failure scenarios in these | |||

topologies. The coverage values are calculated as the percentage of | topologies. The coverage values are calculated as the percentage of | |||

source-destination pairs protected by the given IPFRR method relative | source-destination pairs protected by the given IPFRR method relative | |||

to those protectable by optimal routing, against the same failure | to those protectable by optimal routing, against the same failure | |||

modes. More details on alternate selection policies used for this | modes. More details on alternate selection policies used for this | |||

analysis are described later in this section. | analysis are described later in this section. | |||

+------------+-----------------------------+ | +------------+-----------------------------+ | |||

| Topology | percentage of failure | | | Topology | percentage of failure | | |||

skipping to change at page 42, line 33 | skipping to change at page 44, line 33 | |||

| T212 | 59 | 63 | 100 | | | T212 | 59 | 63 | 100 | | |||

| T213 | 84 | 84 | 100 | | | T213 | 84 | 84 | 100 | | |||

| T214 | 68 | 78 | 100 | | | T214 | 68 | 78 | 100 | | |||

| T215 | 84 | 88 | 100 | | | T215 | 84 | 88 | 100 | | |||

| T216 | 43 | 59 | 100 | | | T216 | 43 | 59 | 100 | | |||

| T217 | 78 | 88 | 100 | | | T217 | 78 | 88 | 100 | | |||

| T218 | 72 | 75 | 100 | | | T218 | 72 | 75 | 100 | | |||

| T219 | 78 | 84 | 100 | | | T219 | 78 | 84 | 100 | | |||

+------------+---------+---------+---------+ | +------------+---------+---------+---------+ | |||

Figure 26 | Figure 27 | |||

For the topologies analyzed here, LLFA is able to provide node- | For the topologies analyzed here, LLFA is able to provide node- | |||

protecting coverage ranging from 37% to 95% of the source-destination | protecting coverage ranging from 37% to 95% of the source-destination | |||

pairs, as seen in the column labeled NP_LLFA. The use of RLFA in | pairs, as seen in the column labeled NP_LLFA. The use of RLFA in | |||

addition to LLFA is generally able to increase the node-protecting | addition to LLFA is generally able to increase the node-protecting | |||

coverage. The percentage of node-protecting coverage with RLFA is | coverage. The percentage of node-protecting coverage with RLFA is | |||

provided in the column labeled NP_RLFA, ranges from 59% to 98% for | provided in the column labeled NP_RLFA, ranges from 59% to 98% for | |||

these topologies. The node-protecting coverage provided by MRT is | these topologies. The node-protecting coverage provided by MRT is | |||

100% since MRT is able to provide protection for any source- | 100% since MRT is able to provide protection for any source- | |||

destination pair for which a path still exists after the failure. | destination pair for which a path still exists after the failure. | |||

We would also like to measure the quality of the alternate paths | We would also like to measure the quality of the alternate paths | |||

produced by these different IPFRR methods. An obvious approach is to | produced by these different IPFRR methods. An obvious approach is to | |||

take an average of the alternate path costs over all source- | take an average of the alternate path costs over all source- | |||

destination pairs and failure modes. However, this presents a | destination pairs and failure modes. However, this presents a | |||

problem, which we will illustrate by presenting an example of results | problem, which we will illustrate by presenting an example of results | |||

for one topology using this approach ( Figure 27). In this table, | for one topology using this approach ( Figure 28). In this table, | |||

the average relative path length is the alternate path length for the | the average relative path length is the alternate path length for the | |||

IPFRR method divided by the optimal alternate path length, averaged | IPFRR method divided by the optimal alternate path length, averaged | |||

over all source-destination pairs and failure modes. The first three | over all source-destination pairs and failure modes. The first three | |||

columns of data in the table give the path length calculated from the | columns of data in the table give the path length calculated from the | |||

sum of IGP metrics of the links in the path. The results for | sum of IGP metrics of the links in the path. The results for | |||

topology T208 show that the metric-based path lengths for NP_LLFA and | topology T208 show that the metric-based path lengths for NP_LLFA and | |||

NP_RLFA alternates are on average 78 and 66 times longer than the | NP_RLFA alternates are on average 78 and 66 times longer than the | |||

path lengths for optimal alternates. The metric-based path lengths | path lengths for optimal alternates. The metric-based path lengths | |||

for MRT alternates are on average 14 times longer than for optimal | for MRT alternates are on average 14 times longer than for optimal | |||

alternates. | alternates. | |||

skipping to change at page 43, line 23 | skipping to change at page 45, line 23 | |||

+--------+------------------------------------------------+ | +--------+------------------------------------------------+ | |||

| | average relative alternate path length | | | | average relative alternate path length | | |||

| |-----------------------+------------------------+ | | |-----------------------+------------------------+ | |||

|Topology| IGP metric | hopcount | | |Topology| IGP metric | hopcount | | |||

| |-----------------------+------------------------+ | | |-----------------------+------------------------+ | |||

| |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | | | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | | |||

+--------+--------+--------+-----+--------+--------+------+ | +--------+--------+--------+-----+--------+--------+------+ | |||

| T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | | | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | | |||

+--------+--------+--------+-----+--------+--------+------+ | +--------+--------+--------+-----+--------+--------+------+ | |||

Figure 27 | Figure 28 | |||

The network topology represented by T208 uses values of 10, 100, and | The network topology represented by T208 uses values of 10, 100, and | |||

1000 as IGP costs, so small deviations from the optimal alternate | 1000 as IGP costs, so small deviations from the optimal alternate | |||

path can result in large differences in relative path length. LLFA, | path can result in large differences in relative path length. LLFA, | |||

RLFA, and MRT all allow for at least one hop in the alterate path to | RLFA, and MRT all allow for at least one hop in the alterate path to | |||

be chosen independent of the cost of the link. This can easily | be chosen independent of the cost of the link. This can easily | |||

result in an alternate using a link with cost 1000, which introduces | result in an alternate using a link with cost 1000, which introduces | |||

noise into the path length measurement. In the case of T208, the | noise into the path length measurement. In the case of T208, the | |||

adverse effects of using metric-based path lengths is obvious. | adverse effects of using metric-based path lengths is obvious. | |||

However, we have observed that the metric-based path length | However, we have observed that the metric-based path length | |||

introduces noise into alternate path length measurements in several | introduces noise into alternate path length measurements in several | |||

other topologies as well. For this reason, we have opted to measure | other topologies as well. For this reason, we have opted to measure | |||

the alternate path length using hopcount. While IGP metrics may be | the alternate path length using hopcount. While IGP metrics may be | |||

adjusted by the network operator for a number of reasons (e.g. | adjusted by the network operator for a number of reasons (e.g. | |||

traffic engineering), the hopcount is a fairly stable measurement of | traffic engineering), the hopcount is a fairly stable measurement of | |||

path length. As shown in the last three columns of Figure 27, the | path length. As shown in the last three columns of Figure 28, the | |||

hopcount-based alternate path lengths for topology T208 are fairly | hopcount-based alternate path lengths for topology T208 are fairly | |||

well-behaved. | well-behaved. | |||

Figure 28, Figure 29, Figure 30, and Figure 31 present the hopcount- | Figure 29, Figure 30, Figure 31, and Figure 32 present the hopcount- | |||

based path length results for the 19 topologies examined. The | based path length results for the 19 topologies examined. The | |||

topologies in the four tables are grouped based on the size of the | topologies in the four tables are grouped based on the size of the | |||

topologies, as measured by the number of nodes, with Figure 28 having | topologies, as measured by the number of nodes, with Figure 29 having | |||

the smallest topologies and Figure 31 having the largest topologies. | the smallest topologies and Figure 32 having the largest topologies. | |||

Instead of trying to represent the path lengths of a large set of | Instead of trying to represent the path lengths of a large set of | |||

alternates with a single number, we have chosen to present a | alternates with a single number, we have chosen to present a | |||

histogram of the path lengths for each IPFRR method and alternate | histogram of the path lengths for each IPFRR method and alternate | |||

selection policy studied. The first eight colums of data represent | selection policy studied. The first eight colums of data represent | |||

the percentage of failure scenarios protected by an alternate N hops | the percentage of failure scenarios protected by an alternate N hops | |||

longer than the primary path, with the first column representing an | longer than the primary path, with the first column representing an | |||

alternate 0 or 1 hops longer than the primary path, all the way up | alternate 0 or 1 hops longer than the primary path, all the way up | |||

through the eighth column respresenting an alternate 14 or 15 hops | through the eighth column respresenting an alternate 14 or 15 hops | |||

longer than the primary path. The last column in the table gives the | longer than the primary path. The last column in the table gives the | |||

percentage of failure scenarios for which there is no alternate less | percentage of failure scenarios for which there is no alternate less | |||

skipping to change at page 45, line 50 | skipping to change at page 47, line 50 | |||

| MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | | | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

| T205(avg primary hops=3.4) | | | | | | | | | | | | T205(avg primary hops=3.4) | | | | | | | | | | | |||

| OPTIMAL | 92| 8| | | | | | | | | | OPTIMAL | 92| 8| | | | | | | | | |||

| NP_LLFA | 89| 3| | | | | | | 8| | | NP_LLFA | 89| 3| | | | | | | 8| | |||

| NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| | | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| | |||

| NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | | | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | | |||

| MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | | | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

Figure 28 | Figure 29 | |||

+-------------------------------------------------------------------+ | +-------------------------------------------------------------------+ | |||

| | percentage of failure scenarios | | | | percentage of failure scenarios | | |||

| Topology name | protected by an alternate N hops | | | Topology name | protected by an alternate N hops | | |||

| and | longer than the primary path | | | and | longer than the primary path | | |||

| alternate selection +------------------------------------+ | | alternate selection +------------------------------------+ | |||

| policy evaluated | | | | | | | | | no | | | policy evaluated | | | | | | | | | no | | |||

| | | | | | |10 |12 |14 | alt| | | | | | | | |10 |12 |14 | alt| | |||

| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

skipping to change at page 46, line 50 | skipping to change at page 48, line 50 | |||

| MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | | | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

| T210(avg primary hops=2.5) | | | | | | | | | | | | T210(avg primary hops=2.5) | | | | | | | | | | | |||

| OPTIMAL | 95| 4| 1| | | | | | | | | OPTIMAL | 95| 4| 1| | | | | | | | |||

| NP_LLFA | 94| 1| | | | | | | 5| | | NP_LLFA | 94| 1| | | | | | | 5| | |||

| NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| | | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| | |||

| NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | | | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | | |||

| MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | | | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

Figure 29 | Figure 30 | |||

+-------------------------------------------------------------------+ | +-------------------------------------------------------------------+ | |||

| | percentage of failure scenarios | | | | percentage of failure scenarios | | |||

| Topology name | protected by an alternate N hops | | | Topology name | protected by an alternate N hops | | |||

| and | longer than the primary path | | | and | longer than the primary path | | |||

| alternate selection +------------------------------------+ | | alternate selection +------------------------------------+ | |||

| policy evaluated | | | | | | | | | no | | | policy evaluated | | | | | | | | | no | | |||

| | | | | | |10 |12 |14 | alt| | | | | | | | |10 |12 |14 | alt| | |||

| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

skipping to change at page 47, line 50 | skipping to change at page 49, line 50 | |||

| MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| | | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

| T215(avg primary hops=4.8) | | | | | | | | | | | | T215(avg primary hops=4.8) | | | | | | | | | | | |||

| OPTIMAL | 73| 27| | | | | | | | | | OPTIMAL | 73| 27| | | | | | | | | |||

| NP_LLFA | 73| 11| | | | | | | 16| | | NP_LLFA | 73| 11| | | | | | | 16| | |||

| NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| | | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| | |||

| NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | | | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | | |||

| MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | | | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

Figure 30 | Figure 31 | |||

+-------------------------------------------------------------------+ | +-------------------------------------------------------------------+ | |||

| | percentage of failure scenarios | | | | percentage of failure scenarios | | |||

| Topology name | protected by an alternate N hops | | | Topology name | protected by an alternate N hops | | |||

| and | longer than the primary path | | | and | longer than the primary path | | |||

| alternate selection +------------------------------------+ | | alternate selection +------------------------------------+ | |||

| policy evaluated | | | | | | | | | no | | | policy evaluated | | | | | | | | | no | | |||

| | | | | | |10 |12 |14 | alt| | | | | | | | |10 |12 |14 | alt| | |||

| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

skipping to change at page 48, line 43 | skipping to change at page 50, line 43 | |||

| MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | | | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

| T219(avg primary hops=7.7) | | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | | | |||

| OPTIMAL | 77| 15| 5| 1| 1| | | | | | | OPTIMAL | 77| 15| 5| 1| 1| | | | | | |||

| NP_LLFA | 72| 5| | | | | | | 22| | | NP_LLFA | 72| 5| | | | | | | 22| | |||

| NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| | | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| | |||

| NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| | | NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| | |||

| MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| | | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

Figure 31 | Figure 32 | |||

In the preceding analysis, the following procedure for selecting an | In the preceding analysis, the following procedure for selecting an | |||

RLFA was used. Nodes were ordered with respect to distance from the | RLFA was used. Nodes were ordered with respect to distance from the | |||

source and checked for membership in Q and P-space. The first node | source and checked for membership in Q and P-space. The first node | |||

to satisfy this condition was selected as the RLFA. More | to satisfy this condition was selected as the RLFA. More | |||

sophisticated methods to select node-protecting RLFAs is an area of | sophisticated methods to select node-protecting RLFAs is an area of | |||

active research. | active research. | |||

The analysis presented above uses the MRT Lowpoint Algorithm defined | The analysis presented above uses the MRT Lowpoint Algorithm defined | |||

in this specification with a common GADAG root. The particular | in this specification with a common GADAG root. The particular | |||

skipping to change at page 49, line 24 | skipping to change at page 51, line 24 | |||

chosen based on the GADAG Root Selection Priority advertised by each | chosen based on the GADAG Root Selection Priority advertised by each | |||

router, the values of which would be determined off-line. | router, the values of which would be determined off-line. | |||

In order to measure how sensitive the MRT alternate path lengths are | In order to measure how sensitive the MRT alternate path lengths are | |||

to the choice of common GADAG root, we performed the same analysis | to the choice of common GADAG root, we performed the same analysis | |||

using different choices of GADAG root. All of the nodes in the | using different choices of GADAG root. All of the nodes in the | |||

network were ordered with respect to the node centrality as computed | network were ordered with respect to the node centrality as computed | |||

above. Nodes were chosen at the 0th, 25th, and 50th percentile with | above. Nodes were chosen at the 0th, 25th, and 50th percentile with | |||

respect to the centrality ordering, with 0th percentile being the | respect to the centrality ordering, with 0th percentile being the | |||

most central node. The distribution of alternate path lengths for | most central node. The distribution of alternate path lengths for | |||

those three choices of GADAG root are shown in Figure 32 for a subset | those three choices of GADAG root are shown in Figure 33 for a subset | |||

of the 19 topologies (chosen arbitrarily). The third row for each | of the 19 topologies (chosen arbitrarily). The third row for each | |||

topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the | topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the | |||

results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth | results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth | |||

rows show the alternate path length distibution for the 25th and 50th | rows show the alternate path length distibution for the 25th and 50th | |||

percentile choice for GADAG root. One can see some impact on the | percentile choice for GADAG root. One can see some impact on the | |||

path length distribution with the less central choice of GADAG root | path length distribution with the less central choice of GADAG root | |||

resulting in longer path lenghths. | resulting in longer path lenghths. | |||

We also looked at the impact of MRT algorithm variant on the | We also looked at the impact of MRT algorithm variant on the | |||

alternate path lengths. The first two rows for each topology present | alternate path lengths. The first two rows for each topology present | |||

skipping to change at page 50, line 50 | skipping to change at page 52, line 50 | |||

| MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| | | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

| T219(avg primary hops=7.7) | | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | | | |||

| MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| | | MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| | |||

| MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | | | MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | | |||

| MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| | | MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| | |||

| MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| | | MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| | |||

| MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| | | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| | |||

+------------------------------+---+---+---+---+---+---+---+---+----+ | +------------------------------+---+---+---+---+---+---+---+---+----+ | |||

Figure 32 | Figure 33 | |||

8. Implementation Status | 8. Implementation Status | |||

[RFC Editor: please remove this section prior to publication.] | [RFC Editor: please remove this section prior to publication.] | |||

Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on | Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on | |||

implementation status. | implementation status. | |||

9. Algorithm Work to Be Done | 9. Algorithm Work to Be Done | |||

skipping to change at page 51, line 39 | skipping to change at page 53, line 39 | |||

12. Security Considerations | 12. Security Considerations | |||

This architecture is not currently believed to introduce new security | This architecture is not currently believed to introduce new security | |||

concerns. | concerns. | |||

13. References | 13. References | |||

13.1. Normative References | 13.1. Normative References | |||

[I-D.ietf-rtgwg-mrt-frr-architecture] | [I-D.ietf-rtgwg-mrt-frr-architecture] | |||

Atlas, A., Kebler, R., Bowers, C., Enyedi, G., Csaszar, | Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, | |||

A., Tantsura, J., Konstantynowicz, M., and R. White, "An | A., Tantsura, J., and R. White, "An Architecture for IP/ | |||

Architecture for IP/LDP Fast-Reroute Using Maximally | LDP Fast-Reroute Using Maximally Redundant Trees", draft- | |||

Redundant Trees", draft-rtgwg-mrt-frr-architecture-04 | ietf-rtgwg-mrt-frr-architecture-05 (work in progress), | |||

(work in progress), July 2014. | January 2015. | |||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||

Requirement Levels", BCP 14, RFC 2119, March 1997. | Requirement Levels", BCP 14, RFC 2119, March 1997. | |||

13.2. Informative References | 13.2. Informative References | |||

[EnyediThesis] | [EnyediThesis] | |||

Enyedi, G., "Novel Algorithms for IP Fast Reroute", | Enyedi, G., "Novel Algorithms for IP Fast Reroute", | |||

Department of Telecommunications and Media Informatics, | Department of Telecommunications and Media Informatics, | |||

Budapest University of Technology and Economics Ph.D. | Budapest University of Technology and Economics Ph.D. | |||

Thesis, February 2011, <http://www.omikk.bme.hu/collection | Thesis, February 2011, <http://www.omikk.bme.hu/collection | |||

s/phd/Villamosmernoki_es_Informatikai_Kar/2011/ | s/phd/Villamosmernoki_es_Informatikai_Kar/2011/ | |||

Enyedi_Gabor/ertekezes.pdf>. | Enyedi_Gabor/ertekezes.pdf>. | |||

[I-D.atlas-mpls-ldp-mrt] | [I-D.farkas-isis-pcr] | |||

Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ. | Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., and P. | |||

Wijnands, "LDP Extensions to Support Maximally Redundant | Ashwood-Smith, "IS-IS Path Computation and Reservation", | |||

Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress), | draft-farkas-isis-pcr-01 (work in progress), December | |||

July 2014. | 2014. | |||

[I-D.atlas-ospf-mrt] | [I-D.ietf-isis-mrt] | |||

Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF | Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. | |||

Extensions to Support Maximally Redundant Trees", draft- | Tantsura, "Intermediate System to Intermediate System (IS- | |||

atlas-ospf-mrt-02 (work in progress), July 2014. | IS) Extensions for Maximally Redundant Trees (MRT)", | |||

draft-ietf-isis-mrt-00 (work in progress), February 2015. | ||||

[I-D.ietf-mpls-ldp-mrt] | ||||

Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and | ||||

I. Wijnands, "LDP Extensions to Support Maximally | ||||

Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in | ||||

progress), January 2015. | ||||

[I-D.ietf-ospf-mrt] | ||||

Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, | ||||

"OSPF Extensions to Support Maximally Redundant Trees", | ||||

draft-ietf-ospf-mrt-00 (work in progress), January 2015. | ||||

[I-D.ietf-rtgwg-ipfrr-notvia-addresses] | [I-D.ietf-rtgwg-ipfrr-notvia-addresses] | |||

Bryant, S., Previdi, S., and M. Shand, "A Framework for IP | Bryant, S., Previdi, S., and M. Shand, "A Framework for IP | |||

and MPLS Fast Reroute Using Not-via Addresses", draft- | and MPLS Fast Reroute Using Not-via Addresses", draft- | |||

ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), | ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), | |||

May 2013. | May 2013. | |||

[I-D.ietf-rtgwg-lfa-manageability] | [I-D.ietf-rtgwg-lfa-manageability] | |||

Litkowski, S., Decraene, B., Filsfils, C., Raza, K., | Litkowski, S., Decraene, B., Filsfils, C., Raza, K., | |||

Horneffer, M., and P. Sarkar, "Operational management of | Horneffer, M., and P. Sarkar, "Operational management of | |||

Loop Free Alternates", draft-ietf-rtgwg-lfa- | Loop Free Alternates", draft-ietf-rtgwg-lfa- | |||

manageability-07 (work in progress), January 2015. | manageability-08 (work in progress), March 2015. | |||

[I-D.ietf-rtgwg-remote-lfa] | [I-D.ietf-rtgwg-remote-lfa] | |||

Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. | Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. | |||

So, "Remote Loop-Free Alternate Fast Re-Route", draft- | So, "Remote Loop-Free Alternate (LFA) Fast Re-Route | |||

ietf-rtgwg-remote-lfa-10 (work in progress), January 2015. | (FRR)", draft-ietf-rtgwg-remote-lfa-11 (work in progress), | |||

January 2015. | ||||

[I-D.li-isis-mrt] | ||||

Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. | ||||

Tantsura, "Intermediate System to Intermediate System (IS- | ||||

IS) Extensions for Maximally Redundant Trees(MRT)", draft- | ||||

li-isis-mrt-01 (work in progress), July 2014. | ||||

[Kahn_1962_topo_sort] | [Kahn_1962_topo_sort] | |||

Kahn, A., "Topological sorting of large networks", | Kahn, A., "Topological sorting of large networks", | |||

Communications of the ACM, Volume 5, Issue 11 , Nov 1962, | Communications of the ACM, Volume 5, Issue 11 , Nov 1962, | |||

<http://dl.acm.org/citation.cfm?doid=368996.369025>. | <http://dl.acm.org/citation.cfm?doid=368996.369025>. | |||

[LFARevisited] | [LFARevisited] | |||

Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP | Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP | |||

Fast ReRoute: Loop Free Alternates Revisited", Proceedings | Fast ReRoute: Loop Free Alternates Revisited", Proceedings | |||

of IEEE INFOCOM , 2011, | of IEEE INFOCOM , 2011, | |||

skipping to change at page 53, line 29 | skipping to change at page 55, line 34 | |||

Enyedi, G., Retvari, G., and A. Csaszar, "On Finding | Enyedi, G., Retvari, G., and A. Csaszar, "On Finding | |||

Maximally Redundant Trees in Strictly Linear Time", IEEE | Maximally Redundant Trees in Strictly Linear Time", IEEE | |||

Symposium on Computers and Comunications (ISCC) , 2009, | Symposium on Computers and Comunications (ISCC) , 2009, | |||

<http://opti.tmit.bme.hu/~enyedi/ipfrr/ | <http://opti.tmit.bme.hu/~enyedi/ipfrr/ | |||

distMaxRedTree.pdf>. | distMaxRedTree.pdf>. | |||

[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. | [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. | |||

McPherson, "OSPF Stub Router Advertisement", RFC 3137, | McPherson, "OSPF Stub Router Advertisement", RFC 3137, | |||

June 2001. | June 2001. | |||

[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi | ||||

Topology (MT) Routing in Intermediate System to | ||||

Intermediate Systems (IS-ISs)", RFC 5120, February 2008. | ||||

[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast | [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast | |||

Reroute: Loop-Free Alternates", RFC 5286, September 2008. | Reroute: Loop-Free Alternates", RFC 5286, September 2008. | |||

[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC | [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC | |||

5714, January 2010. | 5714, January 2010. | |||

[RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., | [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., | |||

Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free | Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free | |||

Alternate (LFA) Applicability in Service Provider (SP) | Alternate (LFA) Applicability in Service Provider (SP) | |||

Networks", RFC 6571, June 2012. | Networks", RFC 6571, June 2012. | |||

skipping to change at page 54, line 35 | skipping to change at page 56, line 48 | |||

UNDIRECTED) already specified for each interface. | UNDIRECTED) already specified for each interface. | |||

Mod_SPF(spf_root, block_root) | Mod_SPF(spf_root, block_root) | |||

Initialize spf_heap to empty | Initialize spf_heap to empty | |||

Initialize nodes' spf_metric to infinity | Initialize nodes' spf_metric to infinity | |||

spf_root.spf_metric = 0 | spf_root.spf_metric = 0 | |||

insert(spf_heap, spf_root) | insert(spf_heap, spf_root) | |||

found_in_gadag = false | found_in_gadag = false | |||

while (spf_heap is not empty) and (found_in_gadag is false) | while (spf_heap is not empty) and (found_in_gadag is false) | |||

min_node = remove_lowest(spf_heap) | min_node = remove_lowest(spf_heap) | |||

if min_node.IN_GADAG is true | if min_node.IN_GADAG | |||

found_in_gadag = true | found_in_gadag = true | |||

else | else | |||

foreach interface intf of min_node | foreach interface intf of min_node | |||

if ((intf.OUTGOING or intf.UNDIRECTED) and | if ((intf.OUTGOING or intf.UNDIRECTED) and | |||

((intf.remote_node.localroot is block_root) or | ((intf.remote_node.localroot is block_root) or | |||

(intf.remote_node is block_root)) and | (intf.remote_node is block_root)) and | |||

(intf.remote_node is not TEMP_UNUSABLE) and | (intf.remote_node is not TEMP_UNUSABLE) and | |||

(intf is not TEMP_UNUSABLE)) | (intf is not TEMP_UNUSABLE)) | |||

path_metric = min_node.spf_metric + intf.metric | path_metric = min_node.spf_metric + intf.metric | |||

if path_metric < intf.remote_node.spf_metric | if path_metric < intf.remote_node.spf_metric | |||

intf.remote_node.spf_metric = path_metric | intf.remote_node.spf_metric = path_metric | |||

intf.remote_node.spf_prev_intf = intf | intf.remote_node.spf_prev_intf = intf | |||

insert_or_update(spf_heap, intf.remote_node) | insert_or_update(spf_heap, intf.remote_node) | |||

return min_node | return min_node | |||

SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, | SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, | |||

method) | method) | |||

Mark all interfaces between cand_intf.remote_node | Mark all interfaces between cand_intf.remote_node | |||

and cand_intf.local_node as TEMP_UNUSABLE | and cand_intf.local_node as TEMP_UNUSABLE | |||

if cand_intf.local_node is not block_root | if cand_intf.local_node is not block_root | |||

Mark cand_intf.local_node as TEMP_UNUSABLE | Mark cand_intf.local_node as TEMP_UNUSABLE | |||

Initialize ear_list to empty | Initialize ear_list to empty | |||

end_ear = Mod_SPF(spf_root, block_root) | end_ear = Mod_SPF(spf_root, block_root) | |||

y = end_ear.spf_prev_hop | y = end_ear.spf_prev_hop | |||

while y.local_node is not spf_root | while y.local_node is not spf_root | |||

add_to_list_start(ear_list, y) | add_to_list_start(ear_list, y) | |||

y.local_node.IN_GADAG = true | y.local_node.IN_GADAG = true | |||

y = y.local_node.spf_prev_intf | y = y.local_node.spf_prev_intf | |||

if(method is not hybrid) | if(method is not hybrid) | |||

Set_Ear_Direction(ear_list, cand_intf.local_node, | Set_Ear_Direction(ear_list, cand_intf.local_node, | |||

end_ear,block_root) | end_ear,block_root) | |||

Clear TEMP_UNUSABLE from all interfaces between | Clear TEMP_UNUSABLE from all interfaces between | |||

cand_intf.remote_node and cand_intf.local_node | cand_intf.remote_node and cand_intf.local_node | |||

Clear TEMP_UNUSABLE from cand_intf.local_node | Clear TEMP_UNUSABLE from cand_intf.local_node | |||

return end_ear | return end_ear | |||

Figure 33: Modified SPF for GADAG computation | Figure 34: Modified SPF for GADAG computation | |||

Assume that an ear is found by going from y to x and then running an | Assume that an ear is found by going from y to x and then running an | |||

SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is | SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is | |||

necessary to determine the direction of the ear; if y << z, then the | necessary to determine the direction of the ear; if y << z, then the | |||

path should be y->x...q->z but if y >> z, then the path should be y<- | path should be y->x...q->z but if y >> z, then the path should be y<- | |||

x...q<-z. In Section 5.4, the same problem was handled by finding | x...q<-z. In Section 5.5, the same problem was handled by finding | |||

all ears that started at a node before looking at ears starting at | all ears that started at a node before looking at ears starting at | |||

nodes higher in the partial order. In this algorithm, using that | nodes higher in the partial order. In this algorithm, using that | |||

approach could mean that new ears aren't added in order of their | approach could mean that new ears aren't added in order of their | |||

total cost since all ears connected to a node would need to be found | total cost since all ears connected to a node would need to be found | |||

before additional nodes could be found. | before additional nodes could be found. | |||

The alternative is to track the order relationship of each node with | The alternative is to track the order relationship of each node with | |||

respect to every other node. This can be accomplished by maintaining | respect to every other node. This can be accomplished by maintaining | |||

two sets of nodes at each node. The first set, Higher_Nodes, | two sets of nodes at each node. The first set, Higher_Nodes, | |||

contains all nodes that are known to be ordered above the node. The | contains all nodes that are known to be ordered above the node. The | |||

skipping to change at page 56, line 48 | skipping to change at page 59, line 48 | |||

add i.local_node to x.Higher_Nodes | add i.local_node to x.Higher_Nodes | |||

else | else | |||

foreach node x where x.localroot is block_root | foreach node x where x.localroot is block_root | |||

if end_b is in x.Lower_Nodes | if end_b is in x.Lower_Nodes | |||

foreach interface i in ear_list | foreach interface i in ear_list | |||

add i.local_node to x.Lower_Nodes | add i.local_node to x.Lower_Nodes | |||

if end_a is in x.Higher_Nodes | if end_a is in x.Higher_Nodes | |||

foreach interface i in ear_list | foreach interface i in ear_list | |||

add i.remote_node to x.Higher_Nodes | add i.remote_node to x.Higher_Nodes | |||

Figure 34: Algorithm to assign links of an ear direction | Figure 35: Algorithm to assign links of an ear direction | |||

A goal of the algorithm is to find the shortest cycles and ears. An | A goal of the algorithm is to find the shortest cycles and ears. An | |||

ear is started by going to a neighbor x of an IN_GADAG node y. The | ear is started by going to a neighbor x of an IN_GADAG node y. The | |||

path from x to an IN_GADAG node is minimal, since it is computed via | path from x to an IN_GADAG node is minimal, since it is computed via | |||

SPF. Since a shortest path is made of shortest paths, to find the | SPF. Since a shortest path is made of shortest paths, to find the | |||

shortest ears requires reaching from the set of IN_GADAG nodes to the | shortest ears requires reaching from the set of IN_GADAG nodes to the | |||

closest node that isn't IN_GADAG. Therefore, an ordered tree is | closest node that isn't IN_GADAG. Therefore, an ordered tree is | |||

maintained of interfaces that could be explored from the IN_GADAG | maintained of interfaces that could be explored from the IN_GADAG | |||

nodes. The interfaces are ordered by their characteristics of | nodes. The interfaces are ordered by their characteristics of | |||

metric, local loopback address, remote loopback address, and ifindex, | metric, local loopback address, remote loopback address, and ifindex, | |||

as in the algorithm previously described in Figure 14. | as in the algorithm previously described in Figure 14. | |||

The algorithm ignores interfaces picked from the ordered tree that | The algorithm ignores interfaces picked from the ordered tree that | |||

belong to the block root if the block in which the interface is | belong to the block root if the block in which the interface is | |||

present already has an ear that has been computed. This is necessary | present already has an ear that has been computed. This is necessary | |||

since we allow at most one incoming interface to a block root in each | since we allow at most one incoming interface to a block root in each | |||

block. This requirement stems from the way next-hops are computed as | block. This requirement stems from the way next-hops are computed as | |||

was seen in Section 5.6. After any ear gets computed, we traverse | was seen in Section 5.7. After any ear gets computed, we traverse | |||

the newly added nodes to the GADAG and insert interfaces whose far | the newly added nodes to the GADAG and insert interfaces whose far | |||

end is not yet on the GADAG to the ordered tree for later processing. | end is not yet on the GADAG to the ordered tree for later processing. | |||

Finally, cut-links are a special case because there is no point in | Finally, cut-links are a special case because there is no point in | |||

doing an SPF on a block of 2 nodes. The algorithm identifies cut- | doing an SPF on a block of 2 nodes. The algorithm identifies cut- | |||

links simply as links where both ends of the link are cut-vertices. | links simply as links where both ends of the link are cut-vertices. | |||

Cut-links can simply be added to the GADAG with both OUTGOING and | Cut-links can simply be added to the GADAG with both OUTGOING and | |||

INCOMING specified on their interfaces. | INCOMING specified on their interfaces. | |||

add_eligible_interfaces_of_node(ordered_intfs_tree,node) | add_eligible_interfaces_of_node(ordered_intfs_tree,node) | |||

for each interface of node | for each interface of node | |||

if intf.remote_node.IN_GADAG is false | if intf.remote_node.IN_GADAG is false | |||

insert(intf,ordered_intfs_tree) | insert(intf,ordered_intfs_tree) | |||

check_if_block_has_ear(x,block_id) | check_if_block_has_ear(x,block_id) | |||

block_has_ear = false | block_has_ear = false | |||

for all interfaces of x | for all interfaces of x | |||

if (intf.remote_node.block_id == block_id) && | if ( (intf.remote_node.block_id == block_id) && | |||

(intf.remote_node.IN_GADAG is true) | intf.remote_node.IN_GADAG ) | |||

block_has_ear = true | block_has_ear = true | |||

return block_has_ear | return block_has_ear | |||

Construct_GADAG_via_SPF(topology, root) | Construct_GADAG_via_SPF(topology, root) | |||

Compute_Localroot (root,root) | Compute_Localroot (root,root) | |||

Assign_Block_ID(root,0) | Assign_Block_ID(root,0) | |||

root.IN_GADAG = true | root.IN_GADAG = true | |||

add_eligible_interfaces_of_node(ordered_intfs_tree,root) | add_eligible_interfaces_of_node(ordered_intfs_tree,root) | |||

while ordered_intfs_tree is not empty | while ordered_intfs_tree is not empty | |||

cand_intf = remove_lowest(ordered_intfs_tree) | cand_intf = remove_lowest(ordered_intfs_tree) | |||

if cand_intf.remote_node.IN_GADAG is false | if cand_intf.remote_node.IN_GADAG is false | |||

if L(cand_intf.remote_node) == D(cand_intf.remote_node) | if L(cand_intf.remote_node) == D(cand_intf.remote_node) | |||

// Special case for cut-links | // Special case for cut-links | |||

cand_intf.UNDIRECTED = false | cand_intf.UNDIRECTED = false | |||

cand_intf.remote_intf.UNDIRECTED = false | cand_intf.remote_intf.UNDIRECTED = false | |||

cand_intf.OUTGOING = true | cand_intf.OUTGOING = true | |||

cand_intf.INCOMING = true | cand_intf.INCOMING = true | |||

cand_intf.remote_intf.OUTGOING = true | cand_intf.remote_intf.OUTGOING = true | |||

cand_intf.remote_intf.INCOMING = true | cand_intf.remote_intf.INCOMING = true | |||

cand_intf.remote_node.IN_GADAG = true | cand_intf.remote_node.IN_GADAG = true | |||

add_eligible_interfaces_of_node( | add_eligible_interfaces_of_node( | |||

ordered_intfs_tree,cand_intf.remote_node) | ordered_intfs_tree,cand_intf.remote_node) | |||

else | ||||

if (cand_intf.remote_node.local_root == | ||||

cand_intf.local_node) && | ||||

check_if_block_has_ear | ||||

(cand_intf.local_node, | ||||

cand_intf.remote_node.block_id)) | ||||

/* Skip the interface since the block root | ||||

already has an incoming interface in the | ||||

block */ | ||||

else | else | |||

ear_end = SPF_for_Ear(cand_intf.local_node, | if (cand_intf.remote_node.local_root == | |||

cand_intf.remote_node, | cand_intf.local_node) && | |||

cand_intf.remote_node.localroot, | check_if_block_has_ear | |||

SPF method) | (cand_intf.local_node, | |||

y = ear_end.spf_prev_hop | cand_intf.remote_node.block_id)) | |||

while y.local_node is not cand_intf.local_node | /* Skip the interface since the block root | |||

add_eligible_interfaces_of_node( | already has an incoming interface in the | |||

ordered_intfs_tree, | block */ | |||

y.local_node) | else | |||

y = y.local_node.spf_prev_intf | ear_end = SPF_for_Ear(cand_intf.local_node, | |||

cand_intf.remote_node, | ||||

cand_intf.remote_node.localroot, | ||||

SPF method) | ||||

y = ear_end.spf_prev_hop | ||||

while y.local_node is not cand_intf.local_node | ||||

add_eligible_interfaces_of_node( | ||||

ordered_intfs_tree, | ||||

y.local_node) | ||||

y = y.local_node.spf_prev_intf | ||||

Figure 35: SPF-based GADAG algorithm | Figure 36: SPF-based GADAG algorithm | |||

Appendix B. Option 3: Computing GADAG using a hybrid method | Appendix B. Option 3: Computing GADAG using a hybrid method | |||

In this option, the idea is to combine the salient features of the | In this option, the idea is to combine the salient features of the | |||

lowpoint inheritance and SPF methods. To this end, we process nodes | lowpoint inheritance and SPF methods. To this end, we process nodes | |||

as they get added to the GADAG just like in the lowpoint inheritance | as they get added to the GADAG just like in the lowpoint inheritance | |||

by maintaining a stack of nodes. This ensures that we do not need to | by maintaining a stack of nodes. This ensures that we do not need to | |||

maintain lower and higher sets at each node to ascertain ear | maintain lower and higher sets at each node to ascertain ear | |||

directions since the ears will always be directed from the node being | directions since the ears will always be directed from the node being | |||

processed towards the end of the ear. To compute the ear however, we | processed towards the end of the ear. To compute the ear however, we | |||

skipping to change at page 59, line 14 | skipping to change at page 62, line 14 | |||

of an ear is pre-determined. Thus, whenever the block already has an | of an ear is pre-determined. Thus, whenever the block already has an | |||

ear computed, and we are processing an interface of the block root, | ear computed, and we are processing an interface of the block root, | |||

we mark the block root as unusable before the SPF run that computes | we mark the block root as unusable before the SPF run that computes | |||

the ear. This ensures that the SPF terminates at some node other | the ear. This ensures that the SPF terminates at some node other | |||

than the block-root. This in turn guarantees that the block-root has | than the block-root. This in turn guarantees that the block-root has | |||

only one incoming interface in each block, which is necessary for | only one incoming interface in each block, which is necessary for | |||

correctly computing the next-hops on the GADAG. | correctly computing the next-hops on the GADAG. | |||

As in the SPF gadag, bridge ears are handled as a special case. | As in the SPF gadag, bridge ears are handled as a special case. | |||

The entire algorithm is shown below in Figure 36 | The entire algorithm is shown below in Figure 37 | |||

find_spf_stack_ear(stack, x, y, xy_intf, block_root) | find_spf_stack_ear(stack, x, y, xy_intf, block_root) | |||

if L(y) == D(y) | if L(y) == D(y) | |||

// Special case for cut-links | // Special case for cut-links | |||

xy_intf.UNDIRECTED = false | xy_intf.UNDIRECTED = false | |||

xy_intf.remote_intf.UNDIRECTED = false | xy_intf.remote_intf.UNDIRECTED = false | |||

xy_intf.OUTGOING = true | xy_intf.OUTGOING = true | |||

xy_intf.INCOMING = true | xy_intf.INCOMING = true | |||

xy_intf.remote_intf.OUTGOING = true | xy_intf.remote_intf.OUTGOING = true | |||

xy_intf.remote_intf.INCOMING = true | xy_intf.remote_intf.INCOMING = true | |||

skipping to change at page 59, line 44 | skipping to change at page 62, line 44 | |||

If x was set as TEMP_UNUSABLE, clear it | If x was set as TEMP_UNUSABLE, clear it | |||

cur = end_ear | cur = end_ear | |||

while (cur != y) | while (cur != y) | |||

intf = cur.spf_prev_hop | intf = cur.spf_prev_hop | |||

prev = intf.local_node | prev = intf.local_node | |||

intf.UNDIRECTED = false | intf.UNDIRECTED = false | |||

intf.remote_intf.UNDIRECTED = false | intf.remote_intf.UNDIRECTED = false | |||

intf.OUTGOING = true | intf.OUTGOING = true | |||

intf.remote_intf.INCOMING = true | intf.remote_intf.INCOMING = true | |||

push prev onto stack | push prev onto stack | |||

cur = prev | cur = prev | |||

xy_intf.UNDIRECTED = false | xy_intf.UNDIRECTED = false | |||

xy_intf.remote_intf.UNDIRECTED = false | xy_intf.remote_intf.UNDIRECTED = false | |||

xy_intf.OUTGOING = true | xy_intf.OUTGOING = true | |||

xy_intf.remote_intf.INCOMING = true | xy_intf.remote_intf.INCOMING = true | |||

return | return | |||

Construct_GADAG_via_hybrid(topology,root) | Construct_GADAG_via_hybrid(topology,root) | |||

Compute_Localroot (root,root) | Compute_Localroot (root,root) | |||

Assign_Block_ID(root,0) | Assign_Block_ID(root,0) | |||

root.IN_GADAG = true | root.IN_GADAG = true | |||

Initialize Stack to empty | Initialize Stack to empty | |||

push root onto Stack | push root onto Stack | |||

while (Stack is not empty) | while (Stack is not empty) | |||

x = pop(Stack) | x = pop(Stack) | |||

for each interface intf of x | for each interface intf of x | |||

y = intf.remote_node | y = intf.remote_node | |||

if y.IN_GADAG is false | if y.IN_GADAG is false | |||

find_spf_stack_ear(stack, x, y, intf, y.block_root) | find_spf_stack_ear(stack, x, y, intf, y.block_root) | |||

Figure 36: Hybrid GADAG algorithm | Figure 37: Hybrid GADAG algorithm | |||

Authors' Addresses | Authors' Addresses | |||

Gabor Sandor Enyedi (editor) | Gabor Sandor Enyedi (editor) | |||

Ericsson | Ericsson | |||

Konyves Kalman krt 11 | Konyves Kalman krt 11 | |||

Budapest 1097 | Budapest 1097 | |||

Hungary | Hungary | |||

Email: Gabor.Sandor.Enyedi@ericsson.com | Email: Gabor.Sandor.Enyedi@ericsson.com | |||

End of changes. 130 change blocks. | ||||

374 lines changed or deleted | | 473 lines changed or added | ||

This html diff was produced by rfcdiff 1.42. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |