draft-ietf-rtgwg-mrt-frr-algorithm-00.txt | draft-ietf-rtgwg-mrt-frr-algorithm-01.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: August 18, 2014 A. Atlas, Ed. | Expires: January 5, 2015 A. Atlas, Ed. | |||

C. Bowers | C. Bowers | |||

Juniper Networks | Juniper Networks | |||

A. Gopalan | A. Gopalan | |||

University of Arizona | University of Arizona | |||

February 14, 2014 | July 4, 2014 | |||

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-00 | draft-ietf-rtgwg-mrt-frr-algorithm-01 | |||

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 August 18, 2014. | This Internet-Draft will expire on January 5, 2015. | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2014 IETF Trust and the persons identified as the | Copyright (c) 2014 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 25 | skipping to change at page 2, line 25 | |||

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. MRT Island Identification . . . . . . . . . . . . . . . . 20 | |||

5.2. Root Selection . . . . . . . . . . . . . . . . . . . . . 21 | 5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 | |||

5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21 | 5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21 | |||

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

inheritance . . . . . . . . . . . . . . . . . . . . . . . 22 | inheritance . . . . . . . . . . . . . . . . . . . . . . . 22 | |||

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

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

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

respect to the computing node . . . . . . . . . . . . 27 | respect to the computing node . . . . . . . . . . . . 27 | |||

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

respect to the computing node . . . . . . . . . . . . 28 | respect to the computing node . . . . . . . . . . . . 28 | |||

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

Graph . . . . . . . . . . . . . . . . . . . . . . . . 29 | Graph . . . . . . . . . . . . . . . . . . . . . . . . 29 | |||

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

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

5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33 | 5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33 | |||

5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37 | 5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37 | |||

6. MRT Lowpoint Algorithm: Complete Specification . . . . . . . 40 | 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 40 | |||

7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 | 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 | |||

7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 | 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 | |||

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

9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 | 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51 | |||

10. Security Considerations . . . . . . . . . . . . . . . . . . . 51 | 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51 | |||

11. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 | 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 | |||

11.1. Normative References . . . . . . . . . . . . . . . . . . 51 | 12. Security Considerations . . . . . . . . . . . . . . . . . . . 51 | |||

11.2. Informative References . . . . . . . . . . . . . . . . . 51 | 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 | |||

13.1. Normative References . . . . . . . . . . . . . . . . . . 51 | ||||

13.2. Informative References . . . . . . . . . . . . . . . . . 51 | ||||

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

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

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

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

skipping to change at page 3, line 39 | skipping to change at page 3, line 42 | |||

received traffic on the MRT-Blue and primary next-hops for the MRT- | received traffic on the MRT-Blue and primary next-hops for the MRT- | |||

Red for forwarding received traffic on the MRT-Red. | Red for forwarding received traffic on the MRT-Red. | |||

What alternate next-hops a point-of-local-repair (PLR) selects need | What alternate next-hops a point-of-local-repair (PLR) selects need | |||

not be consistent - but loops must be prevented. To reduce | not be consistent - but loops must be prevented. To reduce | |||

congestion, it is possible for multiple alternate next-hops to be | congestion, it is possible for multiple alternate next-hops to be | |||

selected; in the context of MRT alternates, each of those alternate | selected; in the context of MRT alternates, each of those alternate | |||

next-hops would be equal-cost paths. | next-hops would be equal-cost paths. | |||

This document defines an algorithm for selecting an appropriate MRT | This document defines an algorithm for selecting an appropriate MRT | |||

alternate for consideration. Other alternates, e.g. LFAs that are | alternate for consideration. Other alternates, e.g. LFAs that are | |||

downstream paths, may be prefered when available and that policy- | downstream paths, may be prefered when available and that policy- | |||

based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] | based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] | |||

is not captured in this document. | is not captured in this document. | |||

[E]---[D]---| [E]<--[D]<--| [E]-->[D] | [E]---[D]---| [E]<--[D]<--| [E]-->[D] | |||

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

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

[R] [F] [C] [R] [F] [C] [R] [F] [C] | [R] [F] [C] [R] [F] [C] [R] [F] [C] | |||

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

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

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

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

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

precisely, if we remove root R, the remaining DAG describes a partial | precisely, if we remove root R, the remaining DAG describes a partial | |||

order of the nodes. If we suppose that neither X nor Y is the root, | order of the nodes. If we suppose that neither X nor Y is the root, | |||

we may be able to compare them. If one of them is definitely lesser | we may be able to compare them. If one of them is definitely lesser | |||

with respect to our partial order (say X<<Y), we can add the new path | with respect to our partial order (say X<<Y), we can add the new path | |||

to the ADAG in a direction from X to Y. As an example consider | to the ADAG in a direction from X to Y. As an example consider | |||

Figure 5. | Figure 5. | |||

E---D---| E<--D---| E<--D<--| | E---D---| E<--D---| E<--D<--| | |||

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

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

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

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

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

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

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

(a) A 2-connected graph | (a) A 2-connected graph | |||

(b) Partial ADAG (C is not included) | (b) Partial ADAG (C is not included) | |||

(c) Resulting ADAG after adding path (or ear) B-C-D | (c) Resulting ADAG after adding path (or ear) B-C-D | |||

Figure 5 | Figure 5 | |||

In this partial ADAG, node C is not yet included. However, we can | In this partial ADAG, node C is not yet included. However, we can | |||

find path B-C-D, where both endpoints are contained by this partial | find path B-C-D, where both endpoints are contained by this partial | |||

ADAG (we say those nodes are *ready* in the sequel), and the | ADAG (we say those nodes are "ready" in the following text), and the | |||

remaining node (node C) is not contained yet. If we remove R, the | remaining node (node C) is not contained yet. If we remove R, the | |||

remaining DAG defines a partial order, and with respect to this | remaining DAG defines a partial order, and with respect to this | |||

partial order we can say that B<<D, so we can add the path to the | partial order we can say that B<<D, so we can add the path to the | |||

ADAG in the direction from B to D (arcs B->C and C->D are added). If | ADAG in the direction from B to D (arcs B->C and C->D are added). If | |||

B >> D, we would add the same path in reverse direction. | B >> D, we would add the same path in reverse direction. | |||

If in the partial order where an ear's two ends are X and Y, X << Y, | If in the partial order where an ear's two ends are X and Y, X << Y, | |||

then there must already be a directed path from X to Y in the ADAG. | then there must already be a directed path from X to Y in the ADAG. | |||

The ear must be added in a direction such that it doesn't create a | The ear must be added in a direction such that it doesn't create a | |||

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

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

of a ready node Q, such that Q is not the root R, find a path from N | of a ready node Q, such that Q is not the root R, find a path from N | |||

to the root R in the graph with Q removed. This path is an ear where | to the root R in the graph with Q removed. This path is an ear where | |||

the first node of the ear is Q, the next is N, then the path until | the first node of the ear is Q, the next is N, then the path until | |||

the first ready node the path reached (that second ready node is the | the first ready node the path reached (that ready node is the other | |||

other endpoint of the path). Since the graph is 2-connected, there | endpoint of the path). Since the graph is 2-connected, there must be | |||

must be a path from N to R without Q. | a path from N to R without Q. | |||

It is always possible to select a non-ready neighbor N of a ready | It is always possible to select a non-ready neighbor N of a ready | |||

node Q so that Q is not the root R. Because the network is | node Q so that Q is not the root R. Because the network is | |||

2-connected, N must be connected to two different nodes and only one | 2-connected, N must be connected to two different nodes and only one | |||

can be R. Because the initial cycle has already been added to the | can be R. Because the initial cycle has already been added to the | |||

ADAG, there are ready nodes that are not R. Since the graph is | ADAG, there are ready nodes that are not R. Since the graph is | |||

2-connected, while there are non-ready nodes, there must be a non- | 2-connected, while there are non-ready nodes, there must be a non- | |||

ready neighbor N of a ready node that is not R. | ready neighbor N of a ready node that is not R. | |||

Generic_Find_Ears_ADAG(root) | Generic_Find_Ears_ADAG(root) | |||

Create an empty ADAG. Add root to the ADAG. | Create an empty ADAG. Add root to the ADAG. | |||

Mark root as IN_GADAG. | Mark root as IN_GADAG. | |||

Select an arbitrary cycle containing root. | Select an arbitrary cycle containing root. | |||

Add the arbitrary cycle to the ADAG. | Add the arbitrary cycle to the ADAG. | |||

Mark cycle's nodes as IN_GADAG. | Mark cycle's nodes as IN_GADAG. | |||

Add cycle's non-root nodes to process_list. | Add cycle's non-root nodes to process_list. | |||

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

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.4. 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 | C and assume we reached it from ready node B. We search a path from | |||

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 B->C | this is node D, so the open ear is B-C-D. Since B<<D, we add arc | |||

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

point. | this point. | |||

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

A basic way of computing a spanning tree on a network graph is to run | A basic way of computing a spanning tree on a network graph is to run | |||

a depth-first-search, such as given in Figure 7. This tree has the | a depth-first-search, such as given in Figure 7. This tree has the | |||

important property that if there is a link (x, n), then either n is a | important property that if there is a link (x, n), then either n is a | |||

DFS ancestor of x or n is a DFS descendant of x. In other words, | DFS ancestor of x or n is a DFS descendant of x. In other words, | |||

either n is on the path from the root to x or x is on the path from | either n is on the path from the root to x or x is on the path from | |||

the root to n. | the root to n. | |||

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

DFS_Visit(w, x) | DFS_Visit(w, x) | |||

Run_DFS(node root) | Run_DFS(node root) | |||

dfs_number = 0 | dfs_number = 0 | |||

DFS_Visit(root, NONE) | DFS_Visit(root, NONE) | |||

Figure 7: Basic Depth-First Search algorithm | Figure 7: Basic Depth-First Search algorithm | |||

Given a node x, one can compute the minimal DFS number of the | Given a node x, one can compute the minimal DFS number of the | |||

neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the | neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the | |||

highest attachment point neighbouring x. What is interesting, | earliest attachment point neighbouring x. What is interesting, | |||

though, is what is the highest attachment point from x and x's | though, is what is the earliest attachment point from x and x's | |||

descendants. This is what is determined by computing the Low-Point | descendants. This is what is determined by computing the Low-Point | |||

value, as given in Algorithm Figure 9 and illustrated on a graph in | value. | |||

Figure 8. | ||||

In order to compute the low point value, the network is traversed | ||||

using DFS and the vertices are numbered based on the DFS walk. Let | ||||

this number be represented as DFS(x). All the edges that lead to | ||||

already visited nodes during DFS walk are back-edges. The back-edges | ||||

are important because they give information about reachability of a | ||||

node via another path. | ||||

The low point number is calculated by finding: | ||||

Low(x) = Minimum of ( (DFS(x), | ||||

Lowest DFS(n, x->n is a back-edge), | ||||

Lowest Low(n, x->n is tree edge in DFS walk) ). | ||||

A detailed algorithm for computing the low-point value is given in | ||||

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

a example graph. | ||||

global_variable: dfs_number | ||||

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

D(x) = dfs_number | ||||

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

dfs_number += 1 | ||||

x.dfs_parent = parent | ||||

x.dfs_parent_intf = p_to_x | ||||

x.lowpoint_parent = NONE | ||||

for each interface intf of x | ||||

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

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

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

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

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

x.lowpoint_parent_intf = intf | ||||

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

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

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

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

x.lowpoint_parent_intf = intf | ||||

Run_Lowpoint(node root) | ||||

dfs_number = 0 | ||||

Lowpoint_Visit(root, NONE, NONE) | ||||

Figure 8: Computing Low-Point value | ||||

[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 non-2-connected graph | (a) a non-2-connected graph | |||

skipping to change at page 13, line 41 | skipping to change at page 14, line 41 | |||

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

[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, ) (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 8 | Figure 9: Example lowpoint value computation | |||

global_variable: dfs_number | ||||

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

D(x) = dfs_number | ||||

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

dfs_number += 1 | ||||

x.dfs_parent = parent | ||||

x.dfs_parent_intf = p_to_x | ||||

x.lowpoint_parent = NONE | ||||

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

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

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

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

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

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

x.lowpoint_parent_intf = intf | ||||

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

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

L(x) = D(intf.remote) | ||||

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

x.lowpoint_parent_intf = intf | ||||

Run_Lowpoint(node root) | ||||

dfs_number = 0 | ||||

Lowpoint_Visit(root, NONE, NONE) | ||||

Figure 9: Computing Low-Point value | ||||

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

Third, as seen in Figure 8, even if L(x) < D(x), there may be a block | Third, as seen in Figure 9, even if L(x) < D(x), there may be a block | |||

that contains both the root and a DFS-child of a node while other | that contains both the root and a DFS-child of a node while other | |||

DFS-children might be in different blocks. In this example, C's | DFS-children might be in different blocks. In this example, C's | |||

child D is in the same block as R while F is not. It is important to | child D is in the same block as R while F is not. It is important to | |||

realize that the root of a block may also be the root of another | realize that the root of a block may also be the root of another | |||

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

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

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

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

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

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 9.] | Figure 8.] | |||

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

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

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

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

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

return A_LESS_THAN_B | return A_LESS_THAN_B | |||

return B_LESS_THAN_A | 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 | 5.1. 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), exploring only links that aren't MRT- | a breadth-first-search (BFS). The BFS explores only links that are | |||

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

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

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

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

of these criteria. | ||||

MRT_Island_Identification(topology, computing_rtr, profile_id) | MRT_Island_Identification(topology, computing_rtr, profile_id, area) | |||

for all routers in topology | for all routers in topology | |||

rtr.IN_MRT_ISLAND = FALSE | rtr.IN_MRT_ISLAND = FALSE | |||

computing_rtr.IN_MRT_ISLAND = TRUE | computing_rtr.IN_MRT_ISLAND = TRUE | |||

explore_list = { computing_rtr } | explore_list = { computing_rtr } | |||

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 | if interface is (not MRT-ineligible and not IGP-excluded | |||

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

(interface.remote_node.IN_MRT_ISLAND is FALSE)) | if ((interface.remote_node supports profile_id) and | |||

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

add_to_tail(explore_list, interface.remote_node) | interface.remote_node.IN_MRT_ISLAND = TRUE | |||

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

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

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

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

Selection 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.atlas-ospf-mrt] and [I-D.li-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 | |||

skipping to change at page 21, line 39 | skipping to change at page 21, line 39 | |||

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

Due to manageability consideration | It is possible that some links and nodes will be marked as unusable | |||

[I-D.ietf-rtgwg-lfa-manageability], overload, or a transient cause | using standard IGP mechanisms (see section 7 of | |||

such as [RFC3137], it is possible that some links and nodes will be | [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability | |||

marked as unusable. This constraint must be consistently flooded via | considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be | |||

the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] so that links are | desirable to administratively configure some interfaces as ineligible | |||

clearly known to be MRT-ineligible and not explored or used in the | to carry MRT FRR traffic. This constraint MUST be consistently | |||

MRT algorithm. In the algorithm description, it is assumed that such | flooded via the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] by the | |||

links and nodes will not be explored or used and no more discussion | owner of the interface, so that links are clearly known to be MRT- | |||

is given of this restriction. | ineligible and not explored or used in the MRT algorithm. In the | |||

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

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

restriction. | ||||

5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance | 5.4. 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 | |||

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

If a node is a cut-vertex, that may not yet be the case. Therefore, | If a node is a cut-vertex, that may not yet be the case. Therefore, | |||

any nodes without a low-point parent will have their low-point parent | any nodes without a low-point parent will have their low-point parent | |||

set to their DFS parent and their low-point value set to the DFS- | set to their DFS parent and their low-point value set to the DFS- | |||

value of their parent. This assignment also properly allows an ear | value of their parent. This assignment also properly allows an ear | |||

between two cut-vertices. | between two cut-vertices. | |||

Finally, the algorithm simultaneously computes each node's local- | Finally, the algorithm simultaneously computes each node's local- | |||

root, as described in Figure 12. This is further elaborated as | root, as described in Figure 12. This is further elaborated as | |||

follows. The local-root can be inherited from the node at the end of | follows. The local-root can be inherited from the node at the end of | |||

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

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

topological sort[Kahn_1962_topo_sort] which essentially assigns a | topological sort[Kahn_1962_topo_sort] which essentially assigns a | |||

number to a node x only after all nodes before it (e.g. with a link | number to a node x only after all nodes before it (e.g. with a link | |||

incoming to x) have had their numbers assigned. The only issue with | incoming to x) have had their numbers assigned. The only issue with | |||

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 partial ordering. Any UNDIRECTED links that connect to a | upon the total ordering. Any UNDIRECTED links that connect to a root | |||

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

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

captured in Figure 17 | in Figure 17 | |||

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

if i.INCOMING | if i.INCOMING | |||

if mark_or_clear is mark | if mark_or_clear is MARK | |||

if i.OUTGOING // a cut-link | if i.OUTGOING // a cut-link | |||

i.STORE_INCOMING = true | i.STORE_INCOMING = true | |||

i.INCOMING = false | i.INCOMING = false | |||

i.remote_intf.STORE_OUTGOING = true | i.remote_intf.STORE_OUTGOING = true | |||

i.remote_intf.OUTGOING = false | i.remote_intf.OUTGOING = false | |||

i.TEMP_UNUSABLE = true | i.TEMP_UNUSABLE = true | |||

i.remote_intf.TEMP_UNUSABLE = true | i.remote_intf.TEMP_UNUSABLE = true | |||

else | else | |||

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

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

skipping to change at page 26, line 30 | skipping to change at page 26, line 30 | |||

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 17: 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 | |||

and how the appropriate alternate next-hops are selected is given in | for proxy-nodes and how the appropriate alternate next-hops are | |||

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

5.6. Compute MRT next-hops | 5.6. 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 want to reuse the common GADAG | root. However, in this algorithm, we will reuse the common GADAG and | |||

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

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. It may also provide easier | significantly faster to compute. | |||

troubleshooting of the MRT-Red and MRT-Blue. | ||||

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

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

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 19: Y << X | |||

5.6.2. MRT next-hops to all nodes not partially ordered with respect to | 5.6.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 20. 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. | |||

skipping to change at page 28, line 40 | skipping to change at page 28, line 40 | |||

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 20: 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.6.3. Computing Redundant Tree next-hops in a 2-connected Graph | |||

skipping to change at page 29, line 22 | skipping to change at page 29, line 22 | |||

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. ( Traversal algorithms other | |||

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

links in their given directions and the other reverses the links' | links in their given directions and the other reverses the links' | |||

directions.) | directions.) | |||

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

Red to reach Y are set to those on the MRT-Red to reach R. For every | Red to reach Y are set to those on the MRT-Red to reach R. For every | |||

node Z << X, X's next-hops on the MRT-Blue to reach Z are set to | node Z << X, X's next-hops on the MRT-Blue to reach Z are set to | |||

those on the MRT-Blue to reach R. | those on the MRT-Blue to reach R. | |||

For those nodes, which were not reached, we have the next-hops as | For those nodes which were not reached by either the increasing-SPF | |||

well. The increasing MRT-Blue next-hop for a node, which is not | or the decreasing-SPF, we can determine the next-hops as well. The | |||

ordered, is the next-hop along the decreasing MRT-Red towards R and | increasing MRT-Blue next-hop for a node which is not ordered with | |||

the decreasing MRT-Red next-hop is the next-hop along the increasing | respect to X is the next-hop along the decreasing MRT-Red towards R, | |||

MRT-Blue towards R. Naturally, since R is ordered with respect to all | and the decreasing MRT-Red next-hop is the next-hop along the | |||

the nodes, there will always be an increasing and a decreasing path | increasing MRT-Blue towards R. Naturally, since R is ordered with | |||

towards it. This algorithm does not provide the complete specific | respect to all the nodes, there will always be an increasing and a | |||

path taken but just the appropriate next-hops to use. The identity | decreasing path towards it. This algorithm does not provide the | |||

of G and H is not determined. | complete specific path taken but just the appropriate next-hops to | |||

use. The identities of G and H are not determined by the computing | ||||

node X. | ||||

The final case to considered is when the root R computes its own | The final case to considered is when the root R computes its own | |||

next-hops. Since the root R is << all other nodes, running an | next-hops. Since the root R is << all other nodes, running an | |||

increasing-SPF rooted at R will reach all other nodes; the MRT-Blue | increasing-SPF rooted at R will reach all other nodes; the MRT-Blue | |||

next-hops are those found with this increasing-SPF. Similarly, since | next-hops are those found with this increasing-SPF. Similarly, since | |||

the root R is >> all other nodes, running a decreasing-SPF rooted at | the root R is >> all other nodes, running a decreasing-SPF rooted at | |||

R will reach all other nodes; the MRT-Red next-hops are those found | R will reach all other nodes; the MRT-Red next-hops are those found | |||

with this decreasing-SPF. | with this decreasing-SPF. | |||

E---D---| E<--D<--| | E---D---| E<--D<--| | |||

skipping to change at page 30, line 18 | skipping to change at page 30, line 18 | |||

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

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

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

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

towards E the increasing next-hop is D (it was reached though D), and | and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was | |||

the decreasing next-hop is B (since R was reached though B). Since | reached on the increasing path through D. And the MRT-Red next-hop | |||

both D and B, A and R will compute the next hops similarly, the | towards E is B, since R was reached on the decreasing path through B. | |||

packets will reach 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 | ||||

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

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

We have the next-hops towards F as well: since F is not ordered with | C can determine the next-hops towards F as well. Since F is not | |||

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

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

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

Blue, a real increasing next-hop, so packet forwarded to B will get | towards F, B will use the real increasing next-hop towards F. So a | |||

to F on path C-B-F. Similarly, D will have, for its MRT-Red, a real | packet forwarded to B on MRT-Blue will get to F on path C-B-F. | |||

decreasing next-hop, and the packet will use path C-D-F. | 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. | ||||

5.6.4. Generalizing for graph that isn't 2-connected | 5.6.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.6.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: | |||

skipping to change at page 31, line 14 | skipping to change at page 31, line 19 | |||

B. If a node is explored in the outgoing SPF so Y >> X, then X's | B. If a node is explored in the outgoing SPF so Y >> X, then X's | |||

MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to | MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to | |||

reach X's local-root and if Z << X, then X's MRT-Blue next- | reach X's local-root and if Z << X, then X's MRT-Blue next- | |||

hops to reach Z uses X's MRT-Blue next-hops to reach X's | hops to reach Z uses X's MRT-Blue next-hops to reach X's | |||

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

C. If a node W in a common block with X was not reached in the | C. If a node W in a common block with X was not reached in the | |||

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 Blue MRT 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.6.5. | |||

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

skipping to change at page 33, line 38 | skipping to change at page 33, line 43 | |||

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

Figure 22 | Figure 22 | |||

5.7. Identify MRT alternates | 5.7. 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 | |||

skipping to change at page 36, line 10 | skipping to change at page 36, line 15 | |||

case (iii) holds true, which means that selecting the Blue next-hop | case (iii) holds true, which means that selecting the Blue next-hop | |||

is safe. Similarly, if F.topo_order<D.topo_order, we should select | is safe. Similarly, if F.topo_order<D.topo_order, we should select | |||

the Red next-hop. The situation is almost the same if both F and D | the Red next-hop. The situation is almost the same if both F and D | |||

are less than S. | are less than S. | |||

Recall that we have added each link to the GADAG in some direction, | Recall that we have added each link to the GADAG in some direction, | |||

so it is impossible that S and F are not ordered. But it is possible | so it is impossible that S and F are not ordered. But it is possible | |||

that S and D are not ordered, so we need to deal with this case as | that S and D are not ordered, so we need to deal with this case as | |||

well. If F<<S, we can use the Red next-hop, because that path is | well. If F<<S, we can use the Red next-hop, because that path is | |||

first increasing until a node definitely greater than D is reached, | first increasing until a node definitely greater than D is reached, | |||

than decreasing; this path must avoid using F. Similarly, if F>>S, we | then decreasing; this path must avoid using F. Similarly, if F>>S, | |||

should use the Blue next-hop. | we should use the Blue next-hop. | |||

Additionally, the cases where either F or D is ordered both higher | Additionally, the cases where either F or D is ordered both higher | |||

and lower must be considered; this can happen when one is a block- | and lower must be considered; this can happen when one is a block- | |||

root or its order_proxy is. If D is both higher and lower than S, | root or its order_proxy is. If D is both higher and lower than S, | |||

then the MRT to use is the one that avoids F so if F is higher, then | then the MRT to use is the one that avoids F so if F is higher, then | |||

the MRT-Red should be used and if F is lower, then the MRT-Blue | the MRT-Red should be used and if F is lower, then the MRT-Blue | |||

should be used; F and S must be ordered because they are neighbors. | should be used; F and S must be ordered because they are neighbors. | |||

If F is both higher and lower, then if D is lower, using the MRT-Red | If F is both higher and lower, then if D is lower, using the MRT-Red | |||

to decrease reaches D and if D is higher, using the Blue MRT to | to decrease reaches D and if D is higher, using the Blue MRT to | |||

increase reaches D; if D is unordered compared to S, then the | increase reaches D; if D is unordered compared to S, then the | |||

skipping to change at page 36, line 34 | skipping to change at page 36, line 39 | |||

In the case where F<<S<<F and D and S are unordered, the direction of | In the case where F<<S<<F and D and S are unordered, the direction of | |||

the link in the GADAG between S and F should be examined. If the | the link in the GADAG between S and F should be examined. If the | |||

link is directed S -> F, then use the MRT-Blue (decrease to avoid | link is directed S -> F, then use the MRT-Blue (decrease to avoid | |||

that link and then increase). If the link is directed S <- F, then | that link and then increase). If the link is directed S <- F, then | |||

use the MRT-Red (increase to avoid that link and then decrease). If | use the MRT-Red (increase to avoid that link and then decrease). If | |||

the link is S <--> F, then the link must be a cut-link and there is | the link is S <--> F, then the link must be a cut-link and there is | |||

no node-protecting alternate. If there are multiple links between S | no node-protecting alternate. If there are multiple links between S | |||

and F, then they can protect against each other; of course, in this | and F, then they can protect against each other; of course, in this | |||

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 link | Finally, there is the case where D is also F. In this case, only | |||

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

skipping to change at page 37, line 47 | skipping to change at page 38, line 6 | |||

individual proxy-node can be individually added to the GADAG. The | individual proxy-node can be individually added to the GADAG. The | |||

proxy-node is connected to at most two nodes in the GADAG. | proxy-node is connected to at most two nodes in the GADAG. | |||

Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the | Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the | |||

proxy-node attachments MUST be determined. The degenerate case where | proxy-node attachments MUST be determined. The degenerate case where | |||

the proxy-node is attached to only one node in the GADAG is trivial | the proxy-node is attached to only one node in the GADAG is trivial | |||

as all needed information can be derived from that attachment node; | as all needed information can be derived from that attachment node; | |||

if there are different interfaces, then some can be assigned to MRT- | if there are different interfaces, then some can be assigned to MRT- | |||

Red and others to MRT_Blue. | Red and others to MRT_Blue. | |||

Now, consider the proxy-node that is attached to exactly two nodes in | Now, consider the proxy-node that is attached to exactly two nodes in | |||

the GADAG. Let the order_proxies of these nodes be A and B. Let the | the GADAG. Let the order_proxies of these nodes be A and B. Let the | |||

current node, where next-hop is just being calculated, be S. If one | current node, where next-hop is just being calculated, be S. If one | |||

of these two nodes A and B is the local root of S, let A=S.local_root | of these two nodes A and B is the local root of S, let A=S.local_root | |||

and the other one be B. Otherwise, let A.topo_order < B.topo_order. | and the other one be B. Otherwise, let A.topo_order < B.topo_order. | |||

A valid GADAG was constructed. Instead doing an increasing-SPF and a | A valid GADAG was constructed. Instead doing an increasing-SPF and a | |||

decreasing-SPF to find ordering for the proxy-nodes, the following | decreasing-SPF to find ordering for the proxy-nodes, the following | |||

simple rules, providing the same result, can be used independently | simple rules, providing the same result, can be used independently | |||

for each different proxy-node. For the following rules, let | for each different proxy-node. For the following rules, let | |||

X=A.local_root, and if A is the local root, let that be strictly | X=A.local_root, and if A is the local root, let that be strictly | |||

lower than any other node. Always take the first rule that matches. | lower than any other node. Always take the first rule that matches. | |||

Rule Condition Blue NH Red NH Notes | Rule Condition Blue NH Red NH Notes | |||

1 S=X Blue to A Red to B | 1 S=X Blue to A Red to B | |||

skipping to change at page 39, line 47 | skipping to change at page 39, line 47 | |||

return | return | |||

P.blue_next_hops = R.red_next_hops | P.blue_next_hops = R.red_next_hops | |||

P.red_next_hops = R.blue_next_hops | P.red_next_hops = R.blue_next_hops | |||

return | 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, until | 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 | |||

P.topo_order=B.topo_order otherwise. This gives the following | P.topo_order=B.topo_order otherwise. This gives the following | |||

pseudo-code: | pseudo-code: | |||

Select_Alternates_Proxy_Node(S, P, F, primary_intf) | Select_Alternates_Proxy_Node(S, P, F, primary_intf) | |||

if (F is not P.neighbor_A) | if (F is not P.neighbor_A) | |||

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

6. MRT Lowpoint Algorithm: Complete Specification | 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.6 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 >> S, | 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]. | |||

Implementations SHOULD implement the Select_Alternates() function to | Implementations SHOULD implement the Select_Alternates() function to | |||

pick an MRT-FRR alternate. | pick an MRT-FRR alternate. | |||

In a future version, this section will include pseudo-code describing | ||||

the full code path through the pseudo-code given earlier in the | ||||

draft. | ||||

7. Algorithm Alternatives and Evaluation | 7. Algorithm Alternatives and Evaluation | |||

This specification defines the MRT Lowpoint Algorithm, which is one | This specification defines the MRT Lowpoint Algorithm, which is one | |||

option among several possible MRT algorithms. Other alternatives are | option among several possible MRT algorithms. Other alternatives are | |||

described in the appendices. | described in the appendices. | |||

In addition, it is possible to calculate Destination-Rooted GADAG, | In addition, it is possible to calculate Destination-Rooted GADAG, | |||

where for each destination, a GADAG rooted at that destination is | where for each destination, a GADAG rooted at that destination is | |||

computed. Then a router can compute the blue MRT and red MRT next- | computed. Then a router can compute the blue MRT and red MRT next- | |||

hops to that destination. Building GADAGs per destination is | hops to that destination. Building GADAGs per destination is | |||

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

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

8. Algorithm Work to Be Done | 8. Implementation Status | |||

[RFC Editor: please remove this section prior to publication.] | ||||

Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on | ||||

implementation status. | ||||

9. Algorithm Work to Be Done | ||||

Broadcast Interfaces: The algorithm assumes that broadcast | Broadcast Interfaces: The algorithm assumes that broadcast | |||

interfaces are already represented as pseudo-nodes in the network | interfaces are already represented as pseudo-nodes in the network | |||

graph. Given maximal redundancy, one of the MRT will try to avoid | graph. Given maximal redundancy, one of the MRT will try to avoid | |||

both the pseudo-node and the next hop. The exact rules need to be | both the pseudo-node and the next hop. The exact rules need to be | |||

fully specified. | fully specified. | |||

9. IANA Considerations | 10. Acknowledgements | |||

This doument includes no request to IANA. | The authors would like to thank Shraddha Hegde for her suggestions | |||

and review. | ||||

10. Security Considerations | 11. IANA Considerations | |||

This document includes no request to IANA. | ||||

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

11. References | 13. References | |||

11.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., Envedi, G., Csaszar, A., Tantsura, | Atlas, A., Kebler, R., Bowers, C., Enyedi, G., Csaszar, | |||

J., Konstantynowicz, M., and R. White, "An Architecture | A., Tantsura, J., Konstantynowicz, M., and R. White, "An | |||

for IP/LDP Fast-Reroute Using Maximally Redundant Trees", | Architecture for IP/LDP Fast-Reroute Using Maximally | |||

draft-ietf-rtgwg-mrt-frr-architecture-03 (work in | Redundant Trees", draft-rtgwg-mrt-frr-architecture-04 | |||

progress), July 2013. | (work in progress), July 2014. | |||

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

11.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/ | Thesis, February 2011, <http://www.omikk.bme.hu/collection | |||

collections/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.atlas-mpls-ldp-mrt] | |||

Atlas, A., Tiruveedhula, K., Tantsura, J., and I. | Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ. | |||

Wijnands, "LDP Extensions to Support Maximally Redundant | Wijnands, "LDP Extensions to Support Maximally Redundant | |||

Trees", draft-atlas-mpls-ldp-mrt-00 (work in progress), | Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress), | |||

July 2013. | July 2014. | |||

[I-D.atlas-ospf-mrt] | [I-D.atlas-ospf-mrt] | |||

Atlas, A., Hegde, S., cbowers@juniper.net, c., and J. | Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF | |||

Tantsura, "OSPF Extensions to Support Maximally Redundant | Extensions to Support Maximally Redundant Trees", draft- | |||

Trees", draft-atlas-ospf-mrt-01 (work in progress), | atlas-ospf-mrt-02 (work in progress), July 2014. | |||

October 2013. | ||||

[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. psarkar@juniper.net, "Operational | Horneffer, M., and p. psarkar@juniper.net, "Operational | |||

management of Loop Free Alternates", draft-ietf-rtgwg-lfa- | management of Loop Free Alternates", draft-ietf-rtgwg-lfa- | |||

manageability-03 (work in progress), February 2014. | manageability-03 (work in progress), February 2014. | |||

[I-D.ietf-rtgwg-remote-lfa] | [I-D.ietf-rtgwg-remote-lfa] | |||

Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. | Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. | |||

Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-04 | Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-06 | |||

(work in progress), November 2013. | (work in progress), May 2014. | |||

[I-D.li-isis-mrt] | [I-D.li-isis-mrt] | |||

Li, Z., Wu, N., Zhao, Q., Atlas, A., cbowers@juniper.net, | Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. | |||

c., and J. Tantsura, "Intermediate System to Intermediate | Tantsura, "Intermediate System to Intermediate System (IS- | |||

System (IS-IS) Extensions for Maximally Redundant Trees | IS) Extensions for Maximally Redundant Trees(MRT)", draft- | |||

(MRT)", draft-li-isis-mrt-00 (work in progress), October | li-isis-mrt-01 (work in progress), July 2014. | |||

2013. | ||||

[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, <http://opti.tmit.bme.hu/~tapolcai | of IEEE INFOCOM , 2011, | |||

/papers/retvari2011lfa_infocom.pdf>. | <http://opti.tmit.bme.hu/~tapolcai/papers/ | |||

retvari2011lfa_infocom.pdf>. | ||||

[LightweightNotVia] | [LightweightNotVia] | |||

Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP | Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP | |||

Fast ReRoute: Lightweight Not-Via without Additional | Fast ReRoute: Lightweight Not-Via without Additional | |||

Addresses", Proceedings of IEEE INFOCOM , 2009, | Addresses", Proceedings of IEEE INFOCOM , 2009, | |||

<http://mycite.omikk.bme.hu/doc/71691.pdf>. | <http://mycite.omikk.bme.hu/doc/71691.pdf>. | |||

[MRTLinear] | [MRTLinear] | |||

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

skipping to change at page 54, line 10 | skipping to change at page 54, line 24 | |||

should not be used during the SPF computation. This prevents | should not be used during the SPF computation. This prevents | |||

ears from starting and ending at the same node and avoids cycles; | ears from starting and ending at the same node and avoids cycles; | |||

the exception is because cycles to/from the block-root are | the exception is because cycles to/from the block-root are | |||

acceptable and expected. | acceptable and expected. | |||

c. Do not explore links to nodes whose local-root is not the block- | c. Do not explore links to nodes whose local-root is not the block- | |||

root. This keeps the SPF confined to the particular block. | root. This keeps the SPF confined to the particular block. | |||

d. Terminate when the first IN_GADAG node z is minimized. | d. Terminate when the first IN_GADAG node z is minimized. | |||

e. Respect the existing directions (e.g. INCOMING, OUTGOING, | e. Respect the existing directions (e.g. INCOMING, OUTGOING, | |||

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

skipping to change at page 55, line 18 | skipping to change at page 55, line 31 | |||

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 33: 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 | path should be y->x...q->z but if y >> z, then the path should be y<- | |||

y<-x...q<-z. In Section 5.4, the same problem was handled by finding | x...q<-z. In Section 5.4, 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 57, line 17 | skipping to change at page 57, line 17 | |||

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

will be seen in Section 5.6. After any ear gets computed, we | was seen in Section 5.6. After any ear gets computed, we traverse | |||

traverse the newly added nodes to the GADAG and insert interfaces | the newly added nodes to the GADAG and insert interfaces whose far | |||

whose far end is not yet on the GADAG to the ordered tree for later | end is not yet on the GADAG to the ordered tree for later processing. | |||

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

skipping to change at page 58, line 38 | skipping to change at page 58, line 37 | |||

add_eligible_interfaces_of_node( | add_eligible_interfaces_of_node( | |||

ordered_intfs_tree, | ordered_intfs_tree, | |||

y.local_node) | y.local_node) | |||

y = y.local_node.spf_prev_intf | y = y.local_node.spf_prev_intf | |||

Figure 35: SPF-based GADAG algorithm | Figure 35: 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 | |||

above two options. To this end, we process nodes as they get added | lowpoint inheritance and SPF methods. To this end, we process nodes | |||

to the GADAG just like in the lowpoint inheritance by maintaining a | as they get added to the GADAG just like in the lowpoint inheritance | |||

stack of nodes. This ensures that we do not need to maintain lower | by maintaining a stack of nodes. This ensures that we do not need to | |||

and higher sets at each node to ascertain ear directions since the | maintain lower and higher sets at each node to ascertain ear | |||

ears will always be directed from the node being processed towards | directions since the ears will always be directed from the node being | |||

the end of the ear. To compute the ear however, we resort to an SPF | processed towards the end of the ear. To compute the ear however, we | |||

to have the possibility of better ears (path lentghs) thus giving | resort to an SPF to have the possibility of better ears (path | |||

more flexibility than the restricted use of lowpoint/dfs parents. | lentghs) thus giving more flexibility than the restricted use of | |||

lowpoint/dfs parents. | ||||

Regarding ears involving a block root, unlike the SPF method which | Regarding ears involving a block root, unlike the SPF method which | |||

ignored interfaces of the block root after the first ear, in the | ignored interfaces of the block root after the first ear, in the | |||

hybrid method we would have to process all interfaces of the block | hybrid method we would have to process all interfaces of the block | |||

root before moving on to other nodes in the block since the direction | root before moving on to other nodes in the block since the direction | |||

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

End of changes. 69 change blocks. | ||||

193 lines changed or deleted | | 233 lines changed or added | ||

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |