draft-ietf-rtgwg-mrt-frr-algorithm-09.txt | rfc7811.txt | |||
---|---|---|---|---|

Routing Area Working Group G. Enyedi | Internet Engineering Task Force (IETF) G. Enyedi | |||

Internet-Draft A. Csaszar | Request for Comments: 7811 A. Csaszar | |||

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

Expires: August 19, 2016 A. Atlas | ISSN: 2070-1721 A. Atlas | |||

C. Bowers | C. Bowers | |||

Juniper Networks | Juniper Networks | |||

A. Gopalan | A. Gopalan | |||

University of Arizona | University of Arizona | |||

February 16, 2016 | June 2016 | |||

An Algorithm for Computing Maximally Redundant Trees for IP/LDP Fast- | An Algorithm for Computing IP/LDP Fast Reroute | |||

Reroute | Using Maximally Redundant Trees (MRT-FRR) | |||

draft-ietf-rtgwg-mrt-frr-algorithm-09 | ||||

Abstract | Abstract | |||

A solution for IP and LDP Fast-Reroute using Maximally Redundant | This document supports the solution put forth in "An Architecture for | |||

Trees is presented in draft-ietf-rtgwg-mrt-frr-architecture. This | IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)" | |||

document defines the associated MRT Lowpoint algorithm that is used | (RFC 7812) by defining the associated MRT Lowpoint algorithm that is | |||

in the Default MRT profile to compute both the necessary Maximally | used in the Default MRT Profile to compute both the necessary | |||

Redundant Trees with their associated next-hops and the alternates to | Maximally Redundant Trees with their associated next hops and the | |||

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

Status of This Memo | Status of This Memo | |||

This Internet-Draft is submitted in full conformance with the | This is an Internet Standards Track document. | |||

provisions of BCP 78 and BCP 79. | ||||

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

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

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

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

Internet-Drafts are draft documents valid for a maximum of six months | This document is a product of the Internet Engineering Task Force | |||

and may be updated, replaced, or obsoleted by other documents at any | (IETF). It represents the consensus of the IETF community. It has | |||

time. It is inappropriate to use Internet-Drafts as reference | received public review and has been approved for publication by the | |||

material or to cite them other than as "work in progress." | Internet Engineering Steering Group (IESG). Further information on | |||

Internet Standards is available in Section 2 of RFC 7841. | ||||

This Internet-Draft will expire on August 19, 2016. | Information about the current status of this document, any errata, | |||

and how to provide feedback on it may be obtained at | ||||

http://www.rfc-editor.org/info/rfc7811. | ||||

Copyright Notice | Copyright Notice | |||

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

described in the Simplified BSD License. | described in the Simplified BSD License. | |||

Table of Contents | Table of Contents | |||

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

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

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

4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6 | 4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6 | |||

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 . . . . . . . . 8 | 4.2. Finding an Ear and the Correct Direction . . . . . . . . 8 | |||

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

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

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

5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18 | 5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18 | |||

5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18 | 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18 | |||

5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21 | 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21 | |||

5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 | 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 | |||

5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22 | 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22 | |||

5.5. Constructing the GADAG using lowpoint inheritance . . . . 23 | 5.5. Constructing the GADAG Using Lowpoint Inheritance . . . . 23 | |||

5.6. Augmenting the GADAG by directing all links . . . . . . . 25 | 5.6. Augmenting the GADAG by Directing All Links . . . . . . . 25 | |||

5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 29 | 5.7. Compute MRT Next Hops . . . . . . . . . . . . . . . . . . 29 | |||

5.7.1. MRT next-hops to all nodes ordered with respect to | 5.7.1. MRT Next Hops to All Nodes Ordered with Respect to | |||

the computing node . . . . . . . . . . . . . . . . . 29 | the Computing Node . . . . . . . . . . . . . . . . . 29 | |||

5.7.2. MRT next-hops to all nodes not ordered with respect | 5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect | |||

to the computing node . . . . . . . . . . . . . . . . 30 | to the Computing Node . . . . . . . . . . . . . . . . 30 | |||

5.7.3. Computing Redundant Tree next-hops in a 2-connected | 5.7.3. Computing Redundant Tree Next Hops in a 2-Connected | |||

Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 | Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 | |||

5.7.4. Generalizing for a graph that isn't 2-connected . . . 33 | 5.7.4. Generalizing for a Graph That Isn't 2-Connected . . . 33 | |||

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

5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 36 | 5.8. Identify MRT Alternates . . . . . . . . . . . . . . . . . 36 | |||

5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 43 | 5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44 | |||

5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 43 | 5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 45 | |||

5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 44 | 5.9.2. Computing If an Island Neighbor (IN) Is Loop-Free . . 45 | |||

5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 46 | 5.9.3. Computing MRT Next Hops for Proxy-Nodes . . . . . . . 47 | |||

5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 52 | 5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53 | |||

6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 60 | ||||

7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 60 | 6. MRT Lowpoint Algorithm: Next-Hop Conformance . . . . . . . . 61 | |||

7.1. Computing MRT next-hops on broadcast networks . . . . . . 61 | 7. Broadcast Interfaces . . . . . . . . . . . . . . . . . . . . 61 | |||

7.2. Using MRT next-hops as alternates in the event of | 7.1. Computing MRT Next Hops on Broadcast Networks . . . . . . 62 | |||

failures on broadcast networks . . . . . . . . . . . . . 62 | 7.2. Using MRT Next Hops as Alternates in the Event of | |||

8. Evaluation of Alternative Methods for Constructing GADAGs . . 63 | Failures on Broadcast Networks . . . . . . . . . . . . . 63 | |||

9. Implementation Status . . . . . . . . . . . . . . . . . . . . 64 | 8. Evaluation of Alternative Methods for Constructing GADAGs . . 64 | |||

10. Operational Considerations . . . . . . . . . . . . . . . . . 65 | 9. Operational Considerations . . . . . . . . . . . . . . . . . 66 | |||

10.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 65 | 9.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 67 | |||

10.2. Destination-rooted GADAGs . . . . . . . . . . . . . . . 65 | 9.2. Destination-Rooted GADAGs . . . . . . . . . . . . . . . . 67 | |||

11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 66 | 10. Security Considerations . . . . . . . . . . . . . . . . . . . 67 | |||

12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 66 | 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 68 | |||

13. Security Considerations . . . . . . . . . . . . . . . . . . . 66 | 11.1. Normative References . . . . . . . . . . . . . . . . . . 68 | |||

14. References . . . . . . . . . . . . . . . . . . . . . . . . . 66 | 11.2. Informative References . . . . . . . . . . . . . . . . . 68 | |||

14.1. Normative References . . . . . . . . . . . . . . . . . . 66 | Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 70 | |||

14.2. Informative References . . . . . . . . . . . . . . . . . 66 | Appendix B. Constructing a GADAG Using SPFs . . . . . . . . . . 110 | |||

Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 67 | Appendix C. Constructing a GADAG Using a Hybrid Method . . . . . 115 | |||

Appendix B. Constructing a GADAG using SPFs . . . . . . . . . . 108 | Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 117 | |||

Appendix C. Constructing a GADAG using a hybrid method . . . . . 113 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 118 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 115 | ||||

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

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

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

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

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

in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint | in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint | |||

algorithm is required for implementation when the Default MRT profile | algorithm is required for implementation when the Default MRT Profile | |||

is implemented. | is implemented. | |||

The MRT Lowpoint Algorithm defined in this document, when used for | ||||

MRT Fast-Reroute as described in [RFC7812], guarantees 100% recovery | ||||

for single failures when the network is 2-connected. This guaranteed | ||||

coverage does not depend on the link metrics, which an operator may | ||||

be using to traffic-engineer the IP network. Thus, the link metrics | ||||

and general network topology are largely decoupled from the | ||||

guaranteed coverage. | ||||

Just as packets routed on a hop-by-hop basis require that each router | Just as packets routed on a hop-by-hop basis require that each router | |||

compute a shortest-path tree which is consistent, it is necessary for | compute a shortest-path tree that is consistent, it is necessary for | |||

each router to compute the MRT-Blue next-hops and MRT-Red next-hops | each router to compute the MRT-Blue next hops and MRT-Red next hops | |||

in a consistent fashion. This document defines the MRT Lowpoint | in a consistent fashion. This document defines the MRT Lowpoint | |||

algorithm to be used as a standard in the default MRT profile for | algorithm to be used as a standard in the Default MRT Profile for | |||

MRT-FRR. | MRT-FRR. | |||

As now, a router's FIB will contain primary next-hops for the current | A router's Forwarding Information Base (FIB) will continue to contain | |||

shortest-path tree for forwarding traffic. In addition, a router's | primary next hops for the current shortest-path tree for forwarding | |||

FIB will contain primary next-hops for the MRT-Blue for forwarding | traffic. In addition, a router's FIB will contain primary next hops | |||

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

Red for forwarding received traffic on the MRT-Red. | primary next hops for the MRT-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., Loop-Free | |||

downstream paths, may be preferred when available. See the | Alternates (LFAs) that are downstream paths, may be preferred when | |||

Operational Considerations section of | available. See the "Operational Considerations" section of [RFC7812] | |||

[I-D.ietf-rtgwg-mrt-frr-architecture] for a more detailed discussion | for a more detailed discussion of combining MRT alternates with those | |||

of combining MRT alternates with those produced by other FRR | produced by other FRR technologies. | |||

technologies. | ||||

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

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

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

[R] [F] [C] [R] [F] [C] [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) (b) (c) | (a) (b) (c) | |||

a 2-connected graph MRT-Blue towards R MRT-Red towards R | A 2-connected graph MRT-Blue towards R MRT-Red towards R | |||

Figure 1 | Figure 1 | |||

The MRT Lowpoint algorithm can handle arbitrary network topologies | The MRT Lowpoint algorithm can handle arbitrary network topologies | |||

where the whole network graph is not 2-connected, as in Figure 2, as | where the whole network graph is not 2-connected, as in Figure 2, as | |||

well as the easier case where the network graph is 2-connected | well as the easier case where the network graph is 2-connected | |||

(Figure 1). Each MRT is a spanning tree. The pair of MRTs provide | (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide | |||

two paths from every node X to the root of the MRTs. Those paths | two paths from every node X to the root of the MRTs. Those paths | |||

share the minimum number of nodes and the minimum number of links. | share the minimum number of nodes and the minimum number of links. | |||

Each such shared node is a cut-vertex. Any shared links are cut- | Each such shared node is a cut-vertex. Any shared links are cut- | |||

links. | links. | |||

[E]---[D]---| |---[J] | [E]---[D]---| |---[J] | |||

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

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

[R] [F] [C]---[G] | | [R] [F] [C]---[G] | | |||

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

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

[A]---[B]---| |---[H] | [A]---[B]---| |---[H] | |||

(a) a graph that isn't 2-connected | (a) a graph that is not 2-connected | |||

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

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

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

[R] [F] [C]<--[G] | [R] [F] [C]<--[G] | | [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | | |||

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

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

[A]-->[B]---| |---[H] [A]<--[B]<--| [H] | [A]-->[B]---| |---[H] [A]<--[B]<--| [H] | |||

(b) MRT-Blue towards R (c) MRT-Red towards R | (b) MRT-Blue towards R (c) MRT-Red towards R | |||

Figure 2 | Figure 2: A Network That Is Not 2-Connected | |||

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

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||

"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | |||

document are to be interpreted as described in [RFC2119]. | document are to be interpreted as described in [RFC2119]. | |||

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

Please see the Terminology section of | Please see the Terminology section of [RFC7812] for a complete list | |||

[I-D.ietf-rtgwg-mrt-frr-architecture] for a complete list of | of terminology relevant to this document. The list below does not | |||

terminology relevant to this draft. The list below does not repeat | repeat terminology introduced in that RFC. | |||

terminology introduced in that draft. | ||||

spanning tree: A tree containing links that connects all nodes in | spanning tree: A tree that contains links and that connects all | |||

the network graph. | nodes in the network graph. | |||

back-edge: In the context of a spanning tree computed via a depth- | back-edge: In the context of a spanning tree computed via a depth- | |||

first search, a back-edge is a link that connects a descendant of | first search, a back-edge is a link that connects a descendant of | |||

a node x with an ancestor of x. | a node x with an ancestor of x. | |||

partial ADAG: A subset of an ADAG that doesn't yet contain all the | partial ADAG: A subset of an Almost Directed Acyclic Graph (ADAG) | |||

nodes in the block. A partial ADAG is created during the MRT | that doesn't yet contain all the nodes in the block. A partial | |||

algorithm and then expanded until all nodes in the block are | ADAG is created during the MRT Lowpoint algorithm and then | |||

included and it is an ADAG. | expanded until all nodes in the block are included and it becomes | |||

an ADAG. | ||||

DFS: Depth-First Search | DFS: Depth-First Search | |||

DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- | DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- | |||

tree path from the DFS root to x. | tree path from the DFS root to x. | |||

DFS descendant: A node n is a DFS descendant of x if x is on the | DFS descendant: A node n is a DFS descendant of x if x is on the | |||

DFS-tree path from the DFS root to n. | DFS-tree path from the DFS root to n. | |||

ear: A path along not-yet-included-in-the-GADAG nodes that starts | ear: A path along nodes that are not yet included in the Generalized | |||

at a node that is already-included-in-the-GADAG and that ends at a | ADAG (GADAG) that starts at a node that is already included in the | |||

node that is already-included-in-the-GADAG. The starting and | GADAG and that ends at a node that is already included in the | |||

ending nodes may be the same node if it is a cut-vertex. | GADAG. The starting and ending nodes may be the same node if it | |||

is a cut-vertex. | ||||

X >> Y or Y << X: Indicates the relationship between X and Y in a | X>>Y or Y<<X: Indicates the relationship between X and Y in a | |||

partial order, such as found in a GADAG. X >> Y means that X is | partial order, such as found in a GADAG. X>>Y means that X is | |||

higher in the partial order than Y. Y << X means that Y is lower | higher in the partial order than Y. Y<<X means that Y is lower in | |||

in the partial order than X. | the partial order than X. | |||

X > Y or Y < X: Indicates the relationship between X and Y in the | X>Y or Y<X: Indicates the relationship between X and Y in the total | |||

total order, such as found via a topological sort. X > Y means | order, such as found via a topological sort. X>Y means that X is | |||

that X is higher in the total order than Y. Y < X means that Y is | higher in the total order than Y. Y<X means that Y is lower in | |||

lower in the total order than X. | the total order than X. | |||

X ?? Y: Indicates that X is unordered with respect to Y in the | X ?? Y: Indicates that X is unordered with respect to Y in the | |||

partial order. | partial order. | |||

UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING | UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING, | |||

or both. Until the directionality of the link is determined, the | or both. Until the directionality of the link is determined, the | |||

link is marked as UNDIRECTED to indicate that its direction hasn't | link is marked as UNDIRECTED to indicate that its direction hasn't | |||

been determined. | been determined. | |||

OUTGOING: A link marked as OUTGOING has direction in the GADAG from | OUTGOING: A link marked as OUTGOING has direction in the GADAG from | |||

the interface's router to the remote end. | the interface's router to the remote end. | |||

INCOMING: A link marked as INCOMING has direction in the GADAG from | INCOMING: A link marked as INCOMING has direction in the GADAG from | |||

the remote end to the interface's router. | the remote end to the interface's router. | |||

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

There are five key concepts that are critical for understanding the | There are five key concepts that are critical for understanding the | |||

MRT Lowpoint algorithm. The first is the idea of partially ordering | MRT Lowpoint algorithm. The first is the idea of partially ordering | |||

the nodes in a network graph with regard to each other and to the | the nodes in a network graph with regard to each other and to the | |||

GADAG root. The second is the idea of finding an ear of nodes and | GADAG root. The second is the idea of finding an ear of nodes and | |||

adding them in the correct direction. The third is the idea of a | adding them in the correct direction. The third is the idea of a | |||

Low-Point value and how it can be used to identify cut-vertices and | Lowpoint value and how it can be used to identify cut-vertices and to | |||

to find a second path towards the root. The fourth is the idea that | find a second path towards the root. The fourth is the idea that a | |||

a non-2-connected graph is made up of blocks, where a block is a | non-2-connected graph is made up of blocks, where a block is a | |||

2-connected cluster, a cut-link or an isolated node. The fifth is | 2-connected cluster, a cut-link or an isolated node. The fifth is | |||

the idea of a local-root for each node; this is used to compute ADAGs | the idea of a localroot for each node; this is used to compute ADAGs | |||

in each block. | in each block. | |||

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

Given any two nodes X and Y in a graph, a particular total order | Given any two nodes X and Y in a graph, a particular total order | |||

means that either X < Y or X > Y in that total order. An example | means that either X<Y or X>Y in that total order. An example would | |||

would be a graph where the nodes are ranked based upon their unique | be a graph where the nodes are ranked based upon their unique IP | |||

IP loopback addresses. In a partial order, there may be some nodes | loopback addresses. In a partial order, there may be some nodes for | |||

for which it can't be determined whether X << Y or X >> Y. A partial | which it can't be determined whether X<<Y or X>>Y. A partial order | |||

order can be captured in a directed graph, as shown in Figure 3. In | can be captured in a directed graph, as shown in Figure 3. In a | |||

a graphical representation, a link directed from X to Y indicates | graphical representation, a link directed from X to Y indicates that | |||

that X is a neighbor of Y in the network graph and X << Y. | X is a neighbor of Y in the network graph and X<<Y. | |||

[A]<---[R] [E] R << A << B << C << D << E | [A]<---[R] [E] R << A << B << C << D << E | |||

| ^ R << A << B << F << G << H << D << E | | ^ R << A << B << F << G << H << D << E | |||

| | | | | | |||

V | Unspecified Relationships: | V | Unspecified Relationships: | |||

[B]--->[C]--->[D] C and F | [B]--->[C]--->[D] C and F | |||

| ^ C and G | | ^ C and G | |||

| | C and H | | | C and H | |||

V | | V | | |||

[F]--->[G]--->[H] | [F]--->[G]--->[H] | |||

Figure 3: Directed Graph showing a Partial Order | Figure 3: Directed Graph Showing a Partial Order | |||

To compute MRTs, the root of the MRTs is at both the very bottom and | To compute MRTs, the root of the MRTs is at both the very bottom and | |||

the very top of the partial ordering. This means that from any node | the very top of the partial ordering. This means that from any node | |||

X, one can pick nodes higher in the order until the root is reached. | X, one can pick nodes higher in the order until the root is reached. | |||

Similarly, from any node X, one can pick nodes lower in the order | Similarly, from any node X, one can pick nodes lower in the order | |||

until the root is reached. For instance, in Figure 4, from G the | until the root is reached. For instance, in Figure 4, from G the | |||

higher nodes picked can be traced by following the directed links and | higher nodes picked can be traced by following the directed links and | |||

are H, D, E and R. Similarly, from G the lower nodes picked can be | are H, D, E, and R. Similarly, from G the lower nodes picked can be | |||

traced by reversing the directed links and are F, B, A, and R. A | traced by reversing the directed links and are F, B, A, and R. A | |||

graph that represents this modified partial order is no longer a DAG; | graph that represents this modified partial order is no longer a DAG; | |||

it is termed an Almost DAG (ADAG) because if the links directed to | it is termed an Almost DAG (ADAG) because if the links directed to | |||

the root were removed, it would be a DAG. | the root were removed, it would be a DAG. | |||

[A]<---[R]<---[E] R << A << B << C << R | [A]<---[R]<---[E] R << A << B << C << R | |||

| ^ ^ R << A << B << C << D << E << R | | ^ ^ R << A << B << C << D << E << R | |||

| | | R << A << B << F << G << H << D << E << R | | | | R << A << B << F << G << H << D << E << R | |||

V | | | V | | | |||

[B]--->[C]--->[D] Unspecified Relationships: | [B]--->[C]--->[D] Unspecified Relationships: | |||

| ^ C and F | | ^ C and F | |||

| | C and G | | | C and G | |||

V | C and H | V | C and H | |||

[F]--->[G]--->[H] | [F]--->[G]--->[H] | |||

Figure 4: ADAG showing a Partial Order with R lowest and highest | Figure 4: ADAG Showing a Partial Order with R Lowest and Highest | |||

Most importantly, if a node Y >> X, then Y can only appear on the | Most importantly, if a node Y>>X, then Y can only appear on the | |||

increasing path from X to the root and never on the decreasing path. | increasing path from X to the root and never on the decreasing path. | |||

Similarly, if a node Z << X, then Z can only appear on the decreasing | Similarly, if a node Z<<X, then Z can only appear on the decreasing | |||

path from X to the root and never on the inceasing path. | path from X to the root and never on the increasing path. | |||

When following the increasing paths, it is possible to pick multiple | When following the increasing paths, it is possible to pick multiple | |||

higher nodes and still have the certainty that those paths will be | higher nodes and still have the certainty that those paths will be | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 following text), 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.7 | explained in Section 5.7 | |||

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

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

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

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

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

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

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

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

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

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

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

the first ready node the path reached (that ready node is the other | then the path until the first ready node the path reached (that ready | |||

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

a path from N to R without Q. | 2-connected, there must be 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. | |||

while there exists connected nodes in graph that are not IN_GADAG | While there exist connected nodes in graph that are not IN_GADAG | |||

Select a new ear. Let its endpoints be X and Y. | Select a new ear. Let its endpoints be X and Y. | |||

if Y is root or (Y << X) | If Y is root or (Y<<X) | |||

add the ear towards X to the ADAG | Add the ear towards X to the ADAG | |||

else // (a) X is root or (b)X << Y or (c) X, Y not ordered | Else // (a) X is root, or (b) X<<Y, or (c) X, Y not ordered | |||

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

Figure 6: Generic Algorithm to find ears and their direction in | Figure 6: Generic Algorithm to Find Ears and Their Direction in | |||

2-connected graph | 2-Connected Graph | |||

The algorithm in Figure 6 merely requires that a cycle or ear be | The algorithm in Figure 6 merely requires that a cycle or ear be | |||

selected without specifying how. Regardless of the method for | selected without specifying how. Regardless of the method for | |||

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

and selecting the ears is important; shorter ears result in shorter | and selecting the ears is important; shorter ears result in shorter | |||

paths along the MRTs. The MRT Lowpoint algorithm uses the Low-Point | paths along the MRTs. The MRT Lowpoint algorithm uses the Lowpoint | |||

Inheritance method for constructing an ADAG (and ultimately a GADAG). | Inheritance method for constructing an ADAG (and ultimately a GADAG). | |||

This method is defined in Section 5.5. Other methods for | This method is defined in Section 5.5. Other methods for | |||

constructing GADAGs are described in Appendix B and Appendix C. An | constructing GADAGs are described in Appendices B and C. An | |||

evaluation of these different methods is given in Section 8 | evaluation of these different methods is given in Section 8. | |||

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

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

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

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

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

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

this point. | stop at this point. | |||

4.3. Low-Point Values and Their Uses | 4.3. Lowpoint 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 DFS, such as given in Figure 7. This tree has the important | |||

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

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

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

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

global_variable: dfs_number | global_variable: dfs_number | |||

DFS_Visit(node x, node parent) | DFS_Visit(node x, node parent) | |||

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

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

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

for each link (x, w) | for each link (x, w) | |||

if D(w) is not set | if D(w) is not set | |||

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

Run_DFS(node gadag_root) | Run_DFS(node gadag_root) | |||

dfs_number = 0 | dfs_number = 0 | |||

DFS_Visit(gadag_root, NONE) | DFS_Visit(gadag_root, NONE) | |||

Figure 7: Basic Depth-First Search algorithm | Figure 7: Basic DFS 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 | neighbors of x, i.e., min( D(w) if (x,w) is a link). This gives the | |||

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

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

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

value. | ||||

In order to compute the low point value, the network is traversed | 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 | 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 | 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 | already-visited nodes during DFS walk are back-edges. The back-edges | |||

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

node via another path. | node via another path. | |||

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

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

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

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

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

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

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

global_variable: dfs_number | global_variable: dfs_number | |||

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

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

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

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

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

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

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

skipping to change at page 12, line 36 ¶ | skipping to change at page 12, line 41 ¶ | |||

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

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

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

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

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

Run_Lowpoint(node gadag_root) | Run_Lowpoint(node gadag_root) | |||

dfs_number = 0 | dfs_number = 0 | |||

Lowpoint_Visit(gadag_root, NONE, NONE) | Lowpoint_Visit(gadag_root, NONE, NONE) | |||

Figure 8: Computing Low-Point value | Figure 8: Computing Lowpoint 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 39 ¶ | skipping to change at page 13, line 39 ¶ | |||

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

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

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

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

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

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

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

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

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

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

Figure 9: Example lowpoint value computation | Figure 9: Example Lowpoint Value Computation | |||

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

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

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

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

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

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

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

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

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

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

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

allows identification of the cut-vertices and thus the blocks. | 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 9, 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 the MRT Lowpoint algorithm is that any non-2-connected | A key idea for the MRT Lowpoint algorithm is that any non-2-connected | |||

graph is made up by blocks (e.g. 2-connected clusters, cut-links, | graph is made up by blocks (e.g., 2-connected clusters, cut-links, | |||

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

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

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

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

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

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

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

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

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

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

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

three 2-connected clusters | three 2-connected clusters | |||

and one cut-link | and one cut-link | |||

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

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

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

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

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

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

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

skipping to change at page 15, line 42 ¶ | skipping to change at page 15, line 42 ¶ | |||

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

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

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

Figure 10 | Figure 10 | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

skipping to change at page 16, line 22 ¶ | skipping to change at page 16, line 22 ¶ | |||

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

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

when a block is a cut-link (as in block 4), that cut-link is added in | when a block is a cut-link (as in block 4), that cut-link is added in | |||

the same direction to both of the trees. The resulting trees are | the same direction to both of the trees. The resulting trees are | |||

depicted in Figure 10 (b) and (c). | depicted in Figure 10 (b) and (c). | |||

Similarly, to create a GADAG it is sufficient to compute ADAGs in | Similarly, to create a GADAG it is sufficient to compute ADAGs in | |||

each block and connect them. | each block and connect them. | |||

It is necessary, therefore, to identify the cut-vertices, the blocks | It is necessary, therefore, to identify the cut-vertices, the blocks | |||

and identify the appropriate local-root to use for each block. | and identify the appropriate localroot to use for each block. | |||

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

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

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

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

block. | block. | |||

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

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

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

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

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

else | else | |||

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

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

Compute_Localroot(gadag_root, gadag_root) | Compute_Localroot(gadag_root, gadag_root) | |||

Figure 11: A method for computing local-roots | Figure 11: A Method for Computing Localroots | |||

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

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

illustrates the concept; it is used by the GADAG construction methods | illustrates the concept; it is used by the GADAG construction methods | |||

given in Appendix B and Appendix C. The MRT Lowpoint algorithm | given in Appendices B and C. The MRT Lowpoint algorithm computes the | |||

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

using lowpoint inheritance; the essence of this computation is given | inheritance; the essence of this computation is given in Figure 12. | |||

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

same results. | ||||

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

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

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

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

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

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

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

else | else | |||

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

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

Figure 12: Ear-based method for computing local-roots | Figure 12: Ear-Based Method for Computing Localroots | |||

Once the local-roots are known, two nodes X and Y are in a common | Once the localroots are known, two nodes X and Y are in a common | |||

block if and only if one of the following three conditions apply. | block if and only if one of the following three conditions apply. | |||

o Y's local-root is X's local-root : They are in the same block and | o Y's localroot is X's localroot : They are in the same block and | |||

neither is the cut-vertex closest to the root. | neither is the cut-vertex closest to the root. | |||

o Y's local-root is X: X is the cut-vertex closest to the root for | o Y's localroot is X: X is the cut-vertex closest to the root for | |||

Y's block | Y's block | |||

o Y is X's local-root: Y is the cut-vertex closest to the root for | o Y is X's localroot: Y is the cut-vertex closest to the root for | |||

X's block | X's block | |||

Once we have computed the local-root for each node in the network | Once we have computed the localroot for each node in the network | |||

graph, we can assign for each node, a block id that represents the | graph, we can assign for each node, a Block-ID that represents the | |||

block in which the node is present. This computation is shown in | block in which the node is present. This computation is shown in | |||

Figure 13. | Figure 13. | |||

global_var: max_block_id | global_var: max_block_id | |||

Assign_Block_ID(x, cur_block_id) | Assign_Block_ID(x, cur_block_id) | |||

x.block_id = cur_block_id | x.block_id = cur_block_id | |||

foreach DFS child c of x | foreach DFS child c of x | |||

if (c.local_root is x) | if (c.local_root is x) | |||

max_block_id += 1 | max_block_id += 1 | |||

Assign_Block_ID(c, max_block_id) | Assign_Block_ID(c, max_block_id) | |||

else | else | |||

Assign_Block_ID(c, cur_block_id) | Assign_Block_ID(c, cur_block_id) | |||

max_block_id = 0 | max_block_id = 0 | |||

Assign_Block_ID(gadag_root, max_block_id) | Assign_Block_ID(gadag_root, max_block_id) | |||

Figure 13: Assigning block id to identify blocks | Figure 13: Assigning Block-ID to Identify Blocks | |||

5. MRT Lowpoint Algorithm Specification | 5. MRT Lowpoint Algorithm Specification | |||

The MRT Lowpoint algorithm computes one GADAG that is then used by a | The MRT Lowpoint algorithm computes one GADAG that is then used by a | |||

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

destinations. Finally, based upon that information, alternates are | destinations. Finally, based upon that information, alternates are | |||

selected for each next-hop to each destination. The different parts | selected for each next hop to each destination. The different parts | |||

of this algorithm are described below. | of this algorithm are described below. | |||

o Order the interfaces in the network graph. [See Section 5.1] | o Order the interfaces in the network graph. See Section 5.1. | |||

o Compute the local MRT Island for the particular MRT Profile. [See | o Compute the local MRT Island for the particular MRT Profile. See | |||

Section 5.2] | Section 5.2. | |||

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

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

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

Figure 8] | Figure 8. | |||

o Construct the GADAG. [See Section 5.5] | o Construct the GADAG. See Section 5.5. | |||

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

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

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

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

o Identify alternates for each next-hop to each destination by | o Identify alternates for each next hop to each destination by | |||

determining which one of the blue MRT and the red MRT the | determining which one of the MRT-Blue and the MRT-Red the | |||

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

A Python implementation of this algorithm is given in Appendix A. | A Python implementation of this algorithm is given in Appendix A. | |||

5.1. Interface Ordering | 5.1. Interface Ordering | |||

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

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

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

Lowpoint_Visit in Section 4.3, where the selection order of the | Lowpoint_Visit in Section 4.3, where the selection order of the | |||

interfaces to explore results in different trees. Consistent | interfaces to explore results in different trees. Consistent | |||

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

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

return B_LESS_THAN_A | return B_LESS_THAN_A | |||

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

return A_LESS_THAN_B | return A_LESS_THAN_B | |||

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

return B_LESS_THAN_A | return B_LESS_THAN_A | |||

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

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

return A_EQUAL_TO_B | return A_EQUAL_TO_B | |||

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

In Figure 14, if two interfaces on a router connect to the same | In Figure 14, if two interfaces on a router connect to the same | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

IGPs and applications is specified in Figure 15. The metric and | IGPs and applications is specified in Figure 15. The metric and | |||

mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is | mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is | |||

normative. The metric and mrt_node_id values for ISIS-PCR in this | normative. The metric and mrt_node_id values for IS-IS Path Control | |||

table should be considered informational. The normative values are | and Reservation (PCR) in this table should be considered | |||

specified in [IEEE8021Qca] . | informational. The normative values are specified in [IEEE8021Qca]. | |||

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

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

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

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

| application | | | | | application | | | | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

| | pseudonode number | Reachability TLV #22 | | | | pseudonode number | Reachability TLV (type 22) | | |||

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

| | Reachability TLV #22 | IS Neighbor TLV #222 | | | | Reachability TLV (type| IS Neighbor TLV (type 222) | | |||

| | or Multi-Topology | | | | | 22) or Multi-Topology | | | |||

| | IS Neighbor TLV #222 | | | | | IS Neighbor TLV (type | | | |||

| | 222) | | | ||||

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

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

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

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

| in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology | | | in bridged | Shortest Path Bridging| TLV (type 22) or | | |||

| |SPB Instance sub-TLV | Multi-Topology | | ||||

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

| | MT-Capability TLV | TLV #222. In the case | | | | MT-Capability TLV | TLV (type 222). In the case| | |||

| | #144 and 6 octet | of asymmetric link metrics, | | | | (type 144) and 6-octet| of asymmetric link metrics, | | |||

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

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

| | Reachability TLV #22 | directions. | | | | Reachability TLV (type| directions. | | |||

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

| | Intermediate Systems | | | | | Intermediate Systems | | | |||

| | TLV #222 | | | | | TLV (type 222) | | | |||

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

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

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

interface.metric to be used for ranking interfaces, for different | interface.metric to Be Used for Ranking Interfaces, for Different | |||

flooding protocols and applications | Flooding Protocols and Applications | |||

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

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

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

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

integers. In the case of IS-IS for IP/LDP FRR with point-to-point | integers. In the case of IS-IS for IP/LDP FRR with point-to-point | |||

links, the pseudonode number (the 7th octet) is zero. Broadcast | links, the pseudonode number (the 7th octet) is zero. Broadcast | |||

interfaces will be discussed in Section 7. | interfaces will be discussed in Section 7. | |||

5.2. MRT Island Identification | 5.2. MRT Island Identification | |||

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

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

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

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

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

excluded, and that support the particular MRT profile. See section 7 | MRT profile. See Section 7 of [RFC7812] for more-precise definitions | |||

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

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

MRT_Island_Identification(topology, computing_rtr, profile_id, area) | 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 intf in next_rtr | for each intf in next_rtr | |||

if (not intf.MRT-ineligible | if (not intf.IN_MRT_ISLAND | |||

and not intf.MRT-ineligible | ||||

and not intf.remote_intf.MRT-ineligible | and not intf.remote_intf.MRT-ineligible | |||

and not intf.IGP-excluded and (intf in area) | and not intf.IGP-excluded and (intf in area) | |||

and (intf.remote_node supports profile_id) ) | and (intf.remote_node supports profile_id) ) | |||

intf.IN_MRT_ISLAND = TRUE | intf.IN_MRT_ISLAND = TRUE | |||

intf.remote_node.IN_MRT_ISLAND = TRUE | intf.remote_intf.IN_MRT_ISLAND = TRUE | |||

if (not intf.remote_node.IN_MRT_ISLAND)) | if (not intf.remote_node.IN_MRT_ISLAND)) | |||

intf.remote_node.IN_MRT_ISLAND = TRUE | intf.remote_node.IN_MRT_ISLAND = TRUE | |||

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

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

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

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

Root Selection Policy is described for the MRT default profile. This | described for the Default MRT Profile. This selection policy allows | |||

selection policy allows routers to consistently select a common GADAG | routers to consistently select a common GADAG Root inside the local | |||

Root inside the local MRT Island, based on advertised priority | MRT Island, based on advertised priority values. The MRT Lowpoint | |||

values. The MRT Lowpoint algorithm simply requires that all routers | algorithm simply requires that all routers in the MRT Island MUST | |||

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

vary based upon the MRT profile description. Before beginning | profile description. Before beginning computation, the network graph | |||

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

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

computed. | ||||

As noted in Section 7, pseudonodes MUST NOT be considered for GADAG | As noted in Section 7, pseudonodes MUST NOT be considered for GADAG | |||

root selection. | root selection. | |||

It is expected that an operator will designate a set of routers as | It is expected that an operator will designate a set of routers as | |||

good choices for selection as GADAG root by setting the GADAG Root | good choices for selection as GADAG root by setting the GADAG Root | |||

Selection Priority for that set of routers to lower (more preferred) | Selection Priority for that set of routers to lower (more preferred) | |||

numerical values. For guidance on setting the GADAG Root Selection | numerical values. For guidance on setting the GADAG Root Selection | |||

Priority values, refer to Section 10.1. | Priority values, refer to Section 9.1. | |||

5.4. Initialization | 5.4. Initialization | |||

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

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

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

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

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

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

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

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

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

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

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

standard IGP mechanisms to discourage or prevent transit traffic. | standard IGP mechanisms to discourage or prevent transit traffic. | |||

Section 7.3.1 of [I-D.ietf-rtgwg-mrt-frr-architecture] describes how | Section 7.3.1 of [RFC7812] describes how those links and nodes are | |||

those links and nodes are excluded from MRT Island formation. | excluded from MRT Island formation. | |||

MRT-FRR also has the ability to advertise links MRT-Ineligible, as | MRT-FRR also has the ability to advertise links MRT-Ineligible, as | |||

described in Section 7.3.2 of [I-D.ietf-rtgwg-mrt-frr-architecture]. | described in Section 7.3.2 of [RFC7812]. These links are excluded | |||

These links are excluded from the MRT Island and the GADAG. | from the MRT Island and the GADAG. Computation of MRT next hops will | |||

Computation of MRT next-hops will therefore not use any MRT- | therefore not use any MRT-ineligible links. The MRT Lowpoint | |||

ineligible links. The MRT algorithm does still need to consider MRT- | algorithm does still need to consider MRT-ineligible links when | |||

ineligible links when computing FRR alternates, because an MRT- | computing FRR alternates, because an MRT-ineligible link can still be | |||

ineligible link can still be the shortest-path next-hop to reach a | the shortest-path next hop to reach a destination. | |||

destination. | ||||

When a broadcast interface is advertised as MRT-ineligible, then the | When a broadcast interface is advertised as MRT-ineligible, then the | |||

pseudo-node representing the entire broadcast network MUST NOT be | pseudonode representing the entire broadcast network MUST NOT be | |||

included in the MRT Island. This is equivalent to excluding all of | included in the MRT Island. This is equivalent to excluding all of | |||

the broadcast interfaces on that broadcast network from the MRT | the broadcast interfaces on that broadcast network from the MRT | |||

Island. | Island. | |||

5.5. Constructing the GADAG using lowpoint inheritance | 5.5. Constructing the 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 DFS-child that is not IN_GADAG and then following the | |||

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

going to a not IN_GADAG neighbor and then following the chain of DFS | second is by going to a neighbor that is not IN_GADAG and then | |||

parents until an IN_GADAG node is found. As an ear is found, the | following the chain of DFS parents until an IN_GADAG node is found. | |||

associated interfaces are marked based on the direction taken. The | As an ear is found, the associated interfaces are marked based on the | |||

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

ears via DFS-children are found and then the ears via DFS-neighbors | the algorithm, first the ears via DFS-children are found and then the | |||

are found. | ears via DFS-neighbors are found. | |||

By adding both types of ears when an IN_GADAG node is processed, all | By adding both types of ears when an IN_GADAG node is processed, all | |||

ears that connect to that node are found. The order in which the | ears that connect to that node are found. The order in which the | |||

IN_GADAG nodes is processed is, of course, key to the algorithm. The | IN_GADAG nodes are processed is, of course, key to the algorithm. | |||

order is a stack of ears so the most recent ear is found at the top | The order is a stack of ears so the most recent ear is found at the | |||

of the stack. Of course, the stack stores nodes and not ears, so an | top of the stack. Of course, the stack stores nodes and not ears, so | |||

ordered list of nodes, from the first node in the ear to the last | an ordered list of nodes, from the first node in the ear to the last | |||

node in the ear, is created as the ear is explored and then that list | node in the ear, is created as the ear is explored and then that list | |||

is pushed onto the stack. | is pushed onto the stack. | |||

Each ear represents a partial order (see Figure 4) and processing the | Each ear represents a partial order (see Figure 4) and processing the | |||

nodes in order along each ear ensures that all ears connecting to a | nodes in order along each ear ensures that all ears connecting to a | |||

node are found before a node higher in the partial order has its ears | node are found before a node higher in the partial order has its ears | |||

explored. This means that the direction of the links in the ear is | explored. This means that the direction of the links in the ear is | |||

always from the node x being processed towards the other end of the | always from the node x being processed towards the other end of the | |||

ear. Additionally, by using a stack of ears, this means that any | ear. Additionally, by using a stack of ears, this means that any | |||

unprocessed nodes in previous ears can only be ordered higher than | unprocessed nodes in previous ears can only be ordered higher than | |||

nodes in the ears below it on the stack. | nodes in the ears below it on the stack. | |||

In this algorithm that depends upon Low-Point inheritance, it is | In this algorithm that depends upon Lowpoint inheritance, it is | |||

necessary that every node have a low-point parent that is not itself. | necessary that every node has a lowpoint parent that is not itself. | |||

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 lowpoint parent will have their lowpoint parent | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ear_list = empty | ear_list = empty | |||

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

cur_intf = intf | cur_intf = intf | |||

not_done = true | not_done = true | |||

while not_done | while not_done | |||

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

skipping to change at page 24, line 41 ¶ | skipping to change at page 24, line 41 ¶ | |||

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

else | else | |||

not_done = false | not_done = false | |||

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

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

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

x.IS_CUT_VERTEX = true | x.IS_CUT_VERTEX = true | |||

localroot = x | localroot = x | |||

else | else | |||

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

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

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

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

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

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

Construct_GADAG_via_Lowpoint(topology, gadag_root) | Construct_GADAG_via_Lowpoint(topology, gadag_root) | |||

gadag_root.IN_GADAG = true | gadag_root.IN_GADAG = true | |||

gadag_root.localroot = None | gadag_root.localroot = None | |||

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

skipping to change at page 25, line 18 ¶ | skipping to change at page 25, line 18 ¶ | |||

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

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

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

foreach ordered_interface intf of x | foreach ordered_interface intf of x | |||

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

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

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

Construct_GADAG_via_Lowpoint(topology, gadag_root) | Construct_GADAG_via_Lowpoint(topology, gadag_root) | |||

Figure 17: Low-point Inheritance GADAG algorithm | Figure 17: Lowpoint Inheritance GADAG Algorithm | |||

5.6. Augmenting the GADAG by directing all links | 5.6. Augmenting the GADAG by Directing All Links | |||

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

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

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

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

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

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

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

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

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

The goal is thus to assign direction to every remaining link marked | The goal is thus to assign direction to every remaining link marked | |||

as UNDIRECTED to improve the paths and number of paths found when the | as UNDIRECTED to improve the paths and number of paths found when the | |||

MRTs are computed. | MRTs are computed. | |||

To do this, we need to establish a total order that respects the | To do this, we need to establish a total order that respects the | |||

partial order described by the GADAG. This can be done using Kahn's | partial order described by the GADAG. This can be done using Kahn's | |||

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. When adding undirected links to the GADAG, links connecting | done. When adding undirected links to the GADAG, links connecting | |||

the block root to other nodes in that block need special handling | the block root to other nodes in that block need special handling | |||

because the topological order will not always give the right answer | because the topological order will not always give the right answer | |||

for those links. There are three cases to consider. If the | for those links. There are three cases to consider. If the | |||

undirected link in question has another parallel link between the | undirected link in question has another parallel link between the | |||

same two nodes that is already directed, then the direction of the | same two nodes that is already directed, then the direction of the | |||

undirected link can be inherited from the previously directed link. | undirected link can be inherited from the previously directed link. | |||

In the case of parallel cut links, we set all of the parallel links | In the case of parallel cut links, we set all of the parallel links | |||

to both INCOMING and OUTGOING. Otherwise, the undirected link in | to both INCOMING and OUTGOING. Otherwise, the undirected link in | |||

question is set to OUTGOING from the block root node. A cut-link can | question is set to OUTGOING from the block root node. A cut-link can | |||

then be identified by the fact that it will be directed both INCOMING | then be identified by the fact that it will be directed both INCOMING | |||

and OUTGOING in the GADAG. The exact details of this whole process | and OUTGOING in the GADAG. The exact details of this whole process | |||

are captured in Figure 18 | are captured in Figure 18. | |||

Add_Undirected_Block_Root_Links(topo, gadag_root) | Add_Undirected_Block_Root_Links(topo, gadag_root) | |||

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

if x.IS_CUT_VERTEX or x is gadag_root | if x.IS_CUT_VERTEX or x is gadag_root | |||

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

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

or i.PROCESSED ) | or i.PROCESSED ) | |||

continue | continue | |||

Initialize bundle_list to empty | Initialize bundle_list to empty | |||

bundle.UNDIRECTED = true | bundle.UNDIRECTED = true | |||

skipping to change at page 28, line 42 ¶ | skipping to change at page 28, line 42 ¶ | |||

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

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

Add_Undirected_Links(topo, gadag_root) | Add_Undirected_Links(topo, gadag_root) | |||

Add_Undirected_Block_Root_Links(topo, gadag_root) | Add_Undirected_Block_Root_Links(topo, gadag_root) | |||

Run_Topological_Sort_GADAG(topo, gadag_root) | Run_Topological_Sort_GADAG(topo, gadag_root) | |||

Set_Other_Undirected_Links_Based_On_Topo_Order(topo) | Set_Other_Undirected_Links_Based_On_Topo_Order(topo) | |||

Add_Undirected_Links(topo, gadag_root) | Add_Undirected_Links(topo, gadag_root) | |||

Figure 18: Assigning direction to UNDIRECTED links | Figure 18: Assigning Direction to UNDIRECTED Links | |||

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

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

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

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

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

5.7. Compute MRT next-hops | 5.7. Compute MRT Next Hops | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.7.1. MRT next-hops to all nodes ordered with respect to the computing | 5.7.1. MRT Next Hops to All Nodes Ordered with Respect to the Computing | |||

node | Node | |||

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

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

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

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

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

decreases from R to Y; this contains nodes in the interval | to Y; this contains nodes in the interval [X,R-small] or [R-great,Y]. | |||

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

other than X and Y. | ||||

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

| ^ | | ^ | |||

| | | | | | |||

V | | V | | |||

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

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

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

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

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

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

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

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

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

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

| ^ | | ^ | |||

| | | | | | |||

V | | V | | |||

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

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

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

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

5.7.2. MRT next-hops to all nodes not ordered with respect to the | 5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect to the | |||

computing node | 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 21. It is | interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is | |||

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

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

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

root R. | root R. | |||

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

skipping to change at page 31, line 20 ¶ | skipping to change at page 31, line 20 ¶ | |||

^ | | ^ | | |||

| | | | | | |||

| | | | | | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph | 5.7.3. Computing Redundant Tree Next Hops in a 2-Connected Graph | |||

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

were given in Section 5.7.1 and Section 5.7.2. Given these two | were given in Sections 5.7.1 and 5.7.2. Given these two ideas, how | |||

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

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

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

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

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

exploring any links from the ADAG root. | exploring any links from the ADAG root. | |||

In principle, an traversal method other than SPF could be used to | In principle, a traversal method other than SPF could be used to | |||

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

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

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

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

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

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

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

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

as described below. | as described below. | |||

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

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

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

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

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

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

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

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

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

Red to reach Y are set to those on the MRT-Red to reach R. For every | 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 | |||

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

For those nodes which were not reached by either the increasing-SPF | For those nodes that were not reached by either the increasing-SPF or | |||

or the decreasing-SPF, we can determine the next-hops as well. The | the decreasing-SPF, we can determine the next hops as well. The | |||

increasing MRT-Blue next-hop for a node which is not ordered with | increasing MRT-Blue next hop for a node that is not ordered with | |||

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

and the decreasing MRT-Red next-hop is the next-hop along the | and the decreasing MRT-Red next hop is the next hop along the | |||

increasing MRT-Blue towards R. Naturally, since R is ordered with | increasing MRT-Blue towards R. Naturally, since R is ordered with | |||

respect to all the nodes, there will always be an increasing and a | respect to all the nodes, there will always be an increasing and a | |||

decreasing path towards it. This algorithm does not provide the | decreasing path towards it. This algorithm does not provide the | |||

complete specific path taken but just the appropriate next-hops to | complete specific path taken but just the appropriate next hops to | |||

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

node X. | node X. | |||

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

next-hops. Since the GADAG root R is << all other nodes, running an | next hops. Since the GADAG 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 GADAG root R is >> all other nodes, running a decreasing-SPF | the GADAG root R is >> all other nodes, running a decreasing-SPF | |||

rooted at R will reach all other nodes; the MRT-Red next-hops are | rooted at R will reach all other nodes; the MRT-Red next hops are | |||

those found with this decreasing-SPF. | those found with this decreasing-SPF. | |||

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

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

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

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

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

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

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

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

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

Figure 22 | Figure 22 | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.7.4. Generalizing for a graph that isn't 2-connected | 5.7.4. Generalizing for a Graph That Isn't 2-Connected | |||

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

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

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

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

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

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

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

basic differences: | basic differences: | |||

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

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

2. Instead of using the GADAG root, X's local-root should be used. | 2. Instead of using the GADAG root, X's localroot should be used. | |||

This has the following implications: | This has the following implications: | |||

A. The links from X's local-root should not be explored. | A. The links from X's localroot should not be explored. | |||

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 localroot and if Z<<X, then X's MRT-Blue next hops | |||

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

local-root. | localroot. | |||

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 localroot. X's MRT-Red next | |||

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

local-root. | localroot. | |||

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.7.5. | Section 5.7.5. | |||

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

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

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

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

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

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

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

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

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

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

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

return true | return true | |||

return false | return false | |||

Store_Results(y, direction) | Store_Results(y, direction) | |||

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

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

skipping to change at page 34, line 52 ¶ | skipping to change at page 35, line 29 ¶ | |||

SPF_No_Traverse_Block_Root(spf_root, block_root, direction) | SPF_No_Traverse_Block_Root(spf_root, block_root, direction) | |||

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

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

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

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

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

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

Store_Results(min_node, direction) | Store_Results(min_node, direction) | |||

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

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

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

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

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

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

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

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

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

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

else | else | |||

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

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

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

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

skipping to change at page 35, line 36 ¶ | skipping to change at page 36, line 13 ¶ | |||

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

Compute_MRT_NextHops(x, gadag_root) | Compute_MRT_NextHops(x, gadag_root) | |||

foreach node y | foreach node y | |||

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

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

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

SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD) | SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD) | |||

SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE) | SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE) | |||

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

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

// Similarly any nodes whose local-root is x will have their | // Similarly, any node whose localroot is x will have its | |||

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

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

foreach node y | foreach node y | |||

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

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

if y.higher | if y.higher | |||

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

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

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

else | else | |||

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

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

// Inherit next-hops and order_proxies to other components | // Inherit next hops and order_proxies to other components | |||

if (x is not gadag_root) and (x.localroot is not gadag_root) | if (x is not gadag_root) and (x.localroot is not gadag_root) | |||

gadag_root.blue_next_hops = x.localroot.blue_next_hops | gadag_root.blue_next_hops = x.localroot.blue_next_hops | |||

gadag_root.red_next_hops = x.localroot.red_next_hops | gadag_root.red_next_hops = x.localroot.red_next_hops | |||

gadag_root.order_proxy = x.localroot | gadag_root.order_proxy = x.localroot | |||

foreach node y | foreach node y | |||

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

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

max_block_id = 0 | max_block_id = 0 | |||

Assign_Block_ID(gadag_root, max_block_id) | Assign_Block_ID(gadag_root, max_block_id) | |||

Compute_MRT_NextHops(x, gadag_root) | Compute_MRT_NextHops(x, gadag_root) | |||

Figure 23 | Figure 23: Complete Algorithm to Compute MRT Next Hops | |||

5.8. Identify MRT alternates | 5.8. Identify MRT Alternates | |||

At this point, a computing router S knows its MRT-Blue next-hops and | At this point, a computing router S knows its MRT-Blue next hops and | |||

MRT-Red next-hops for each destination in the MRT Island. The | MRT-Red next hops for each destination in the MRT Island. The | |||

primary next-hops along the SPT are also known. It remains to | primary next hops along the SPT are also known. It remains to | |||

determine for each primary next-hop to a destination D, which of the | determine for each primary next hop to a destination D, which MRT | |||

MRTs avoids the primary next-hop node F. This computation depends | avoids the primary next-hop node F. This computation depends upon | |||

upon data set in Compute_MRT_NextHops such as each node y's | 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 or MRT-Red next-hops as the alternate next-hop(s) for | the MRT-Blue or MRT-Red next hops as the alternate next hop(s) for | |||

that primary next hop. The algorithm is given in Figure 24 and | that primary next hop. The algorithm is given in Figure 24 and | |||

discussed afterwards. | discussed afterwards. | |||

Select_Alternates_Internal(D, F, primary_intf, | Select_Alternates_Internal(D, F, primary_intf, | |||

D_lower, D_higher, D_topo_order): | D_lower, D_higher, D_topo_order): | |||

if D_higher and D_lower | if D_higher and D_lower | |||

if F.HIGHER and F.LOWER | if F.HIGHER and F.LOWER | |||

if F.topo_order < D_topo_order | if F.topo_order < D_topo_order | |||

return USE_RED | return USE_RED | |||

else | else | |||

skipping to change at page 38, line 18 ¶ | skipping to change at page 38, line 43 ¶ | |||

if (D is F) or (D.order_proxy is F) | if (D is F) or (D.order_proxy is F) | |||

return PRIM_NH_IS_D_OR_OP_FOR_D | return PRIM_NH_IS_D_OR_OP_FOR_D | |||

D_lower = D.order_proxy.LOWER | D_lower = D.order_proxy.LOWER | |||

D_higher = D.order_proxy.HIGHER | D_higher = D.order_proxy.HIGHER | |||

D_topo_order = D.order_proxy.topo_order | D_topo_order = D.order_proxy.topo_order | |||

return Select_Alternates_Internal(D, F, primary_intf, | return Select_Alternates_Internal(D, F, primary_intf, | |||

D_lower, D_higher, D_topo_order) | D_lower, D_higher, D_topo_order) | |||

Figure 24: Select_Alternates() and Select_Alternates_Internal() | Figure 24: Select_Alternates() and Select_Alternates_Internal() | |||

It is useful to first handle the case where where F is also D, or F | It is useful to first handle the case where F is also D, or F is the | |||

is the order proxy for D. In this case, only link protection is | order proxy for D. In this case, only link protection is possible. | |||

possible. The MRT that doesn't use the failed primary next-hop is | The MRT that doesn't use the failed primary next hop is used. If | |||

used. If both MRTs use the primary next-hop, then the primary next- | both MRTs use the primary next hop, then the primary next hop must be | |||

hop must be a cut-link, so either MRT could be used but the set of | a cut-link, so either MRT could be used but the set of MRT next hops | |||

MRT next-hops must be pruned to avoid the failed primary next-hop | must be pruned to avoid the failed primary next-hop interface. To | |||

interface. To indicate this case, Select_Alternates returns | indicate this case, Select_Alternates returns | |||

PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudo-code to handle the three | PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudocode to handle the three | |||

sub-cases above is not provided. | sub-cases above is not provided. | |||

The logic behind Select_Alternates_Internal is described in | The logic behind Select_Alternates_Internal() is described in | |||

Figure 25. As an example, consider the first case described in the | Figure 25. As an example, consider the first case described in the | |||

table, where the D>>S and D<<S. If this is true, then either S or D | table, where the D>>S and D<<S. If this is true, then either S or D | |||

must be the block root, R. If F>>S and F<<S, then S is the block | must be the block root, R. If F>>S and F<<S, then S is the block | |||

root. So the blue path from S to D is the increasing path to D, and | root. So the blue path from S to D is the increasing path to D, and | |||

the red path S to D is the decreasing path to D. If the | the red path S to D is the decreasing path to D. If the | |||

F.topo_order<D.topo_order, then either F is ordered higher than D or | F.topo_order>D.topo_order, then either F is ordered higher than D or | |||

F is unordered with respect to D. Therefore, F is either on a | F is unordered with respect to D. Therefore, F is either on a | |||

decreasing path from S to D, or it is on neither an increasing nor a | decreasing path from S to D, or it is on neither an increasing nor a | |||

decreasing path from S to D. In either case, it is safe to take an | decreasing path from S to D. In either case, it is safe to take an | |||

increasing path from S to D to avoid F. We know that when S is R, | increasing path from S to D to avoid F. We know that when S is R, | |||

the increasing path is the blue path, so it is safe to use the blue | the increasing path is the blue path, so it is safe to use the blue | |||

path to avoid F. | path to avoid F. | |||

If instead F.topo_order>D.topo_order, then either F is ordered lower | If instead F.topo_order<D.topo_order, then either F is ordered lower | |||

than D, or F is unordered with respect to D. Therefore, F is either | than D, or F is unordered with respect to D. Therefore, F is either | |||

on an increasing path from S to D, or it is on neither an increasing | on an increasing path from S to D, or it is on neither an increasing | |||

nor a decreasing path from S to D. In either case, it is safe to | nor a decreasing path from S to D. In either case, it is safe to | |||

take a decreasing path from S to D to avoid F. We know that when S | take a decreasing path from S to D to avoid F. We know that when S | |||

is R, the decreasing path is the red path, so it is safe to use the | is R, the decreasing path is the red path, so it is safe to use the | |||

red path to avoid F. | red path to avoid F. | |||

If F>>S or F<<S (but not both), then D is the block root. We then | If F>>S or F<<S (but not both), then D is the block root. We then | |||

know that the blue path from S to D is the increasing path to R, and | know that the blue path from S to D is the increasing path to R, and | |||

the red path is the decreasing path to R. When F>>S, we deduce that | the red path is the decreasing path to R. When F>>S, we deduce that | |||

skipping to change at page 39, line 32 ¶ | skipping to change at page 40, line 24 ¶ | |||

| D is | Red path: | | | S to R | | | | D is | Red path: | | | S to R | | | |||

| R, | Decreasing +------+-----------------+------------+------------+ | | R, | Decreasing +------+-----------------+------------+------------+ | |||

| | path to R. | F<<S | additional | F on a | Use Blue | | | | path to R. | F<<S | additional | F on a | Use Blue | | |||

| | | only | criteria | decreasing | to avoid | | | | | only | criteria | decreasing | to avoid | | |||

| | | | not needed | path from | F | | | | | | not needed | path from | F | | |||

| or | | | | S to R | | | | or | | | | S to R | | | |||

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

| | | F>>S | topo(F)>topo(D) | F on a | Use Blue | | | | | F>>S | topo(F)>topo(D) | F on a | Use Blue | | |||

| S is | Blue path: | and | implies that | decreasing | to avoid | | | S is | Blue path: | and | implies that | decreasing | to avoid | | |||

| R | Increasing | F<<S,| F>>D or F??D | path from | F | | | R | Increasing | F<<S,| F>>D or F??D | path from | F | | |||

| | path to D. | F is | | S to D or | | | | | path to D. | | | S to D or | | | |||

| | Red path: | R | | neither | | | | | Red path: | | | neither | | | |||

| | Decreasing | +-----------------+------------+------------+ | | | Decreasing | +-----------------+------------+------------+ | |||

| | path to D. | | topo(F)<topo(D) | F on an | Use Red | | | | path to D. | | topo(F)<topo(D) | F on an | Use Red | | |||

| | | | implies that | increasing | to avoid | | | | | | implies that | increasing | to avoid | | |||

| | | | F<<D or F??D | path from | F | | | | | | F<<D or F??D | path from | F | | |||

| | | | | S to D or | | | | | | | | S to D or | | | |||

| | | | | neither | | | | | | | | neither | | | |||

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

| | | F??S | Can only occur | F is on | Use Red | | | | | F??S | Can only occur | F is on | Use Red | | |||

| | | | when link | neither | or Blue | | | | | | when link | neither | or Blue | | |||

| | | | between | increasing | to avoid | | | | | | between | increasing | to avoid | | |||

skipping to change at page 41, line 28 ¶ | skipping to change at page 43, line 5 ¶ | |||

| | S to first | | not needed | path from | F | | | | S to first | | not needed | path from | F | | |||

| | node K<<D, | | | S to K. | | | | | node K<<D, | | | S to K. | | | |||

| | then incr. +------+-----------------+------------+------------+ | | | then incr. +------+-----------------+------------+------------+ | |||

| | to D. | F>>S | additional | F on an | Use Blue | | | | to D. | F>>S | additional | F on an | Use Blue | | |||

| | Red path: | only | criteria | increasing | to avoid | | | | Red path: | only | criteria | increasing | to avoid | | |||

| | Incr. from | | not needed | path from | F | | | | Incr. from | | not needed | path from | F | | |||

| | S to first | | | S to L | | | | | S to first | | | S to L | | | |||

| | node L>>D, | | | | | | | | node L>>D, | | | | | | |||

| | then decr. | | | | | | | | then decr. | | | | | | |||

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

| | | F??S | F<-->S link is | | | | | | | F??S | topo(F)>topo(D) | F on decr. | Use Blue | | |||

| | | | MRT_INELIGIBLE | | | | ||||

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

| | | | topo(F)>topo(D) | F on decr. | Use Blue | | ||||

| | | | implies that | path from | to avoid | | | | | | implies that | path from | to avoid | | |||

| | | | F>>D or F??D | L to D or | F | | | | | | F>>D or F??D | L to D or | F | | |||

| | | | | neither | | | | | | | | neither | | | |||

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

| | | | topo(F)<topo(D) | F on incr. | Use Red | | | | | | topo(F)<topo(D) | F on incr. | Use Red | | |||

| | | | implies that | path from | to avoid | | | | | | implies that | path from | to avoid | | |||

| | | | F<<D or F??D | K to D or | F | | | | | | F<<D or F??D | K to D or | F | | |||

| | | | | neither | | | | | | | | neither | | | |||

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

| | | F>>S | GADAG link | F on an | Use Blue | | | | | F>>S | GADAG link | F on an | Use Blue | | |||

skipping to change at page 42, line 15 ¶ | skipping to change at page 43, line 37 ¶ | |||

| | | | | from F, in which case | | | | | | | from F, in which case | | |||

| | | | | Red or Blue avoids F | | | | | | | Red or Blue avoids F | | |||

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

| | | | S-F link not | Relies on special | | | | | | S-F link not | Relies on special | | |||

| | | | in GADAG, | construction of GADAG | | | | | | in GADAG, | construction of GADAG | | |||

| | | | only when | to demonstrate that | | | | | | only when | to demonstrate that | | |||

| | | | S-F link is | using Red avoids F | | | | | | S-F link is | using Red avoids F | | |||

| | | | MRT_INELIGIBLE | (see text) | | | | | | MRT_INELIGIBLE | (see text) | | |||

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

Figure 25: determining MRT next-hops and alternates based on the | Determining MRT next hops and alternates based on the partial order | |||

partial order and topological sort relationships between the | and topological sort relationships between the source(S), | |||

source(S), destination(D), primary next-hop(F), and block root(R). | destination(D), primary next hop(F), and block root(R). topo(N) | |||

topo(N) indicates the topological sort value of node N. X??Y | indicates the topological sort value of node N. X??Y indicates that | |||

indicates that node X is unordered with respect to node Y. It is | node X is unordered with respect to node Y. It is assumed that the | |||

assumed that the case where F is D, or where F is the order proxy for | case where F is D, or where F is the order proxy for D, has already | |||

D, has already been handled. | been handled. | |||

Figure 25: Determining MRT Next Hops and Alternates | ||||

The last case in Figure 25 requires additional explanation. The fact | The last case in Figure 25 requires additional explanation. The fact | |||

that the red path from S to D in this case avoids F relies on a | that the red path from S to D in this case avoids F relies on a | |||

special property of the GADAGs that we have constructed in this | special property of the GADAGs that we have constructed in this | |||

algorithm, a property not shared by all GADAGs in general. When D is | algorithm, a property not shared by all GADAGs in general. When D is | |||

unordered with respect to S, and F is the localroot for S, it can | unordered with respect to S, and F is the localroot for S, it can | |||

occur that the link between S and F is not in the GADAG only when | occur that the link between S and F is not in the GADAG only when | |||

that link has been marked MRT_INELIGIBLE. For an arbitrary GADAG, S | that link has been marked MRT_INELIGIBLE. For an arbitrary GADAG, S | |||

doesn't have enough information based on the computed order | doesn't have enough information based on the computed order | |||

relationships to determine if the red path or blue path will hit F | relationships to determine if the red path or blue path will hit F | |||

(which is also the localroot) before hitting K or L, and making it | (which is also the localroot) before hitting K or L, and making it | |||

safely to D. However, the GADAGs that we construct using the | safely to D. However, the GADAGs that we construct using the | |||

algorithm in this document are not arbitrary GADAGs. They have the | algorithm in this document are not arbitrary GADAGs. They have the | |||

additional property that incoming links to a localroot come from only | additional property that incoming links to a localroot come from only | |||

one other node in the same block. This is a result of the method of | one other node in the same block. This is a result of the method of | |||

construction. This additional property guarantees that the red path | construction. This additional property guarantees that the red path | |||

from S to D will never pass through the localroot of S. (That would | from S to D will never pass through the localroot of S. (That would | |||

require the localroot to play the role of L, the first node in the | require the localroot to play the role of L, the first node in the | |||

path ordered higher than D, which would in turn require the localroot | path ordered higher than D, which would in turn require the localroot | |||

to have two incoming links in the GADAG, which cannot happen.) | to have two incoming links in the GADAG, which cannot happen.) | |||

Therefore it is safe to use the red path to avoid F with these | Therefore, it is safe to use the red path to avoid F with these | |||

specially constructed GADAGs. | specially constructed GADAGs. | |||

As an example of how Select_Alternates_Internal() operates, consider | As an example of how Select_Alternates_Internal() operates, consider | |||

the ADAG depicted in Figure 26 and first suppose that G is the | the ADAG depicted in Figure 26 and first suppose that G is the | |||

source, D is the destination and H is the failed next-hop. Since | source, D is the destination, and H is the failed next hop. Since | |||

D>>G, we need to compare H.topo_order and D.topo_order. Since | D>>G, we need to compare H.topo_order and D.topo_order. Since | |||

D.topo_order>H.topo_order, D must be either higher than H or | D.topo_order>H.topo_order, D must be either higher than H or | |||

unordered with respect to H, so we should select the decreasing path | unordered with respect to H, so we should select the decreasing path | |||

towards the root. If, however, the destination were instead J, we | towards the root. If, however, the destination were instead J, we | |||

must find that H.topo_order>J.topo_order, so we must choose the | must find that H.topo_order>J.topo_order, so we must choose the | |||

increasing Blue next-hop to J, which is I. In the case, when instead | increasing Blue next hop to J, which is I. In the case, when instead | |||

the destination is C, we find that we need to first decrease to avoid | the destination is C, we find that we need to first decrease to avoid | |||

using H, so the Blue, first decreasing then increasing, path is | using H, so the Blue, first decreasing then increasing, path is | |||

selected. | selected. | |||

[E]<-[D]<-[H]<-[J] | [E]<-[D]<-[H]<-[J] | |||

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

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

[R] [C] [G]->[I] | [R] [C] [G]->[I] | |||

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

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

[A]->[B]->[F]---| | [A]->[B]->[F]---| | |||

(a)ADAG rooted at R for | ||||

a 2-connected graph | ||||

Figure 26 | Figure 26: ADAG Rooted at R for a 2-Connected Graph | |||

5.9. Named Proxy-Nodes | 5.9. Named Proxy-Nodes | |||

As discussed in Section 11.2 of | As discussed in Section 11.2 of [RFC7812], it is necessary to find | |||

[I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- | MRT-Blue and MRT-Red next hops and MRT-FRR alternates for named | |||

Blue and MRT-Red next-hops and MRT-FRR alternates for named proxy- | proxy-nodes. An example use case is for a router that is not part of | |||

nodes. An example use case is for a router that is not part of that | that local MRT Island, when there is only partial MRT support in the | |||

local MRT Island, when there is only partial MRT support in the | ||||

domain. | domain. | |||

5.9.1. Determining Proxy-Node Attachment Routers | 5.9.1. Determining Proxy-Node Attachment Routers | |||

Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] discusses | Section 11.2 of [RFC7812] discusses general considerations for | |||

general considerations for determining the two proxy-node attachment | determining the two proxy-node attachment routers for a given proxy- | |||

routers for a given proxy-node, corresponding to a prefix. A router | node, corresponding to a prefix. A router in the MRT Island that | |||

in the MRT Island that advertises the prefix is a candidate for being | advertises the prefix is a candidate for being a proxy-node | |||

a proxy-node attachment router, with the associated named-proxy-cost | attachment router, with the associated named-proxy-cost equal to the | |||

equal to the advertised cost to the prefix. | advertised cost to the prefix. | |||

An Island Border Router (IBR) is a router in the MRT Island that is | An Island Border Router (IBR) is a router in the MRT Island that is | |||

connected to an Island Neighbor(IN), which is a router not in the MRT | connected to an Island Neighbor (IN), which is a router not in the | |||

Island but in the same area/level. An (IBR,IN) pair is a candidate | MRT Island but in the same area/level. An (IBR,IN) pair is a | |||

for being a proxy-node attachment router, if the shortest path from | candidate for being a proxy-node attachment router, if the shortest | |||

the IN to the prefix does not enter the MRT Island. A method for | path from the IN to the prefix does not enter the MRT Island. A | |||

identifying such loop-free Island Neighbors(LFINs) is given below. | method for identifying such Loop-Free Island Neighbors (LFINs) is | |||

The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) | given below. The named-proxy-cost assigned to each (IBR, IN) pair is | |||

+ D_opt(IN, prefix). | cost(IBR, IN) + D_opt(IN, prefix). | |||

From the set of prefix-advertising routers and the set of IBRs with | From the set of prefix-advertising routers and the set of IBRs with | |||

at least one LFIN, the two routers with the lowest named-proxy-cost | at least one LFIN, the two routers with the lowest named-proxy-cost | |||

are selected. Ties are broken based upon the lowest Router ID. For | are selected. Ties are broken based upon the lowest Router ID. For | |||

ease of discussion, the two selected routers will be referred to as | ease of discussion, the two selected routers will be referred to as | |||

proxy-node attachment routers. | proxy-node attachment routers. | |||

5.9.2. Computing if an Island Neighbor (IN) is loop-free | 5.9.2. Computing If an Island Neighbor (IN) Is Loop-Free | |||

As discussed above, the Island Neighbor needs to be loop-free with | As discussed above, the IN needs to be loop-free with respect to the | |||

respect to the whole MRT Island for the destination. This can be | whole MRT Island for the destination. This can be accomplished by | |||

accomplished by running the usual SPF algorithm while keeping track | running the usual SPF algorithm while keeping track of which shortest | |||

of which shortest paths have passed through the MRT island. Pseudo- | paths have passed through the MRT island. Pseudocode for this is | |||

code for this is shown in Figure 27. The Island_Marking_SPF() is run | shown in Figure 27. The Island_Marking_SPF() is run for each IN that | |||

for each IN that needs to be evaluated for the loop-free condition, | needs to be evaluated for the loop-free condition, with the IN as the | |||

with the IN as the spf_root. Whether or not an IN is loop-free with | spf_root. Whether or not an IN is loop-free with respect to the MRT | |||

respect to the MRT island can then be determined by evaluating | island can then be determined by evaluating node.PATH_HITS_ISLAND for | |||

node.PATH_HITS_ISLAND for each destination of interest. | each destination of interest. | |||

Island_Marking_SPF(spf_root) | Island_Marking_SPF(spf_root) | |||

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

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

and PATH_HITS_ISLAND to false | and PATH_HITS_ISLAND to false | |||

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

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

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

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

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

skipping to change at page 45, line 39 ¶ | skipping to change at page 46, line 39 ¶ | |||

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

else | else | |||

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

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

if intf.remote_node.IN_MRT_ISLAND | if intf.remote_node.IN_MRT_ISLAND | |||

intf.remote_node.PATH_HITS_ISLAND = true | intf.remote_node.PATH_HITS_ISLAND = true | |||

else | else | |||

intf.remote_node.PATH_HITS_ISLAND = | intf.remote_node.PATH_HITS_ISLAND = | |||

min_node.PATH_HITS_ISLAND | min_node.PATH_HITS_ISLAND | |||

Figure 27: Island_Marking_SPF for determining if an Island Neighbor | Figure 27: Island_Marking_SPF() for Determining If an Island Neighbor | |||

is loop-free | Is Loop-Free | |||

It is also possible that a given prefix is originated by a | It is also possible that a given prefix is originated by a | |||

combination of non-island routers and island routers. The results of | combination of non-island routers and island routers. The results of | |||

the Island_Marking_SPF computation can be used to determine if the | the Island_Marking_SPF() computation can be used to determine if the | |||

shortest path from an IN to reach that prefix hits the MRT island. | shortest path from an IN to reach that prefix hits the MRT Island. | |||

The shortest path for the IN to reach prefix P is determined by the | The shortest path for the IN to reach prefix P is determined by the | |||

total cost to reach prefix P, which is the sum of the cost for the IN | total cost to reach prefix P, which is the sum of the cost for the IN | |||

to reach a prefix-advertising node and the cost with which that node | to reach a prefix-advertising node and the cost with which that node | |||

advertises the prefix. The path with the minimum total cost to | advertises the prefix. The path with the minimum total cost to | |||

prefix P is chosen. If the prefix-advertising node for that minimum | prefix P is chosen. If the prefix-advertising node for that minimum | |||

total cost path has PATH_HITS_ISLAND set to True, then the IN is not | total cost path has PATH_HITS_ISLAND set to True, then the IN is not | |||

loop-free with respect to the MRT Island for reaching prefix P. If | loop-free with respect to the MRT Island for reaching prefix P. If | |||

there multiple minimum total cost paths to reach prefix P, then all | there are multiple minimum total cost paths to reach prefix P, then | |||

of the prefix-advertising routers involved in the minimum total cost | all of the prefix-advertising routers involved in the minimum total | |||

paths MUST have PATH_HITS_ISLAND set to False for the IN to be | cost paths MUST have PATH_HITS_ISLAND set to False for the IN to be | |||

considered loop-free to reach P. | considered loop-free to reach P. | |||

Note that there are other computations that could be used to | Note that there are other computations that could be used to | |||

determine if paths from a given IN _might_ pass through the MRT | determine if paths from a given IN _might_ pass through the MRT | |||

Island for a given prefix or destination. For example, a previous | Island for a given prefix or destination. For example, a previous | |||

version of this draft specified running the SPF algorithm on modified | draft version of this document specified running the SPF algorithm on | |||

topology which treats the MRT island as a single node (with intra- | modified topology that treats the MRT Island as a single node (with | |||

island links set to zero cost) in order to provide input to | intra-island links set to zero cost) in order to provide input to | |||

computations to determine if the path from IN to non-island | computations to determine if the path from IN to non-island | |||

destination hits the MRT island in this modified topology. This | destination hits the MRT Island in this modified topology. This | |||

computation is enough to guarantee that a path will not hit the MRT | computation is enough to guarantee that a path will not hit the MRT | |||

island in the original topology. However, it is possible that a path | Island in the original topology. However, it is possible that a path | |||

which is disqualified for hitting the MRT island in the modified | that is disqualified for hitting the MRT Island in the modified | |||

topology will not actually hit the MRT Island in the original | topology will not actually hit the MRT Island in the original | |||

topology. The algorithm described in Island_Marking_SPF() above does | topology. The algorithm described in Island_Marking_SPF() above does | |||

not modify the original topology, and will only disqualify a path if | not modify the original topology, and will only disqualify a path if | |||

the actual path does in fact hit the MRT island. | the actual path does in fact hit the MRT Island. | |||

Since all routers need to come to the same conclusion about which | Since all routers need to come to the same conclusion about which | |||

routers qualify as LFINs, this specification requires that all | routers qualify as LFINs, this specification requires that all | |||

routers computing LFINs MUST use an algorithm whose result is | routers computing LFINs MUST use an algorithm whose result is | |||

identical to that of the Island_Marking_SPF() in Figure 27. | identical to that of the Island_Marking_SPF() in Figure 27. | |||

5.9.3. Computing MRT Next-Hops for Proxy-Nodes | 5.9.3. Computing MRT Next Hops for Proxy-Nodes | |||

Determining the MRT next-hops for a proxy-node in the degenerate case | Determining the MRT next hops for a proxy-node in the degenerate case | |||

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

trivial, as all needed information can be derived from that proxy | trivial, as all needed information can be derived from that proxy- | |||

node attachment router. If there are multiple interfaces connecting | node attachment router. If there are multiple interfaces connecting | |||

the proxy node to the single proxy node attachment router, then some | the proxy-node to the single proxy-node attachment router, then some | |||

can be assigned to MRT-Red and others to MRT_Blue. | can be assigned to MRT-Red and others to MRT_Blue. | |||

Now, consider the proxy-node P that is attached to two proxy-node | Now, consider the proxy-node P that is attached to two proxy-node | |||

attachment routers. The pseudo-code for Select_Proxy_Node_NHs(P,S) | attachment routers. The pseudocode for Select_Proxy_Node_NHs(P,S) in | |||

in Figure 28 specifies how a computing-router S MUST compute the MRT | Figure 28 specifies how a computing-router S MUST compute the MRT red | |||

red and blue next-hops to reach proxy-node P. The proxy-node | and blue next hops to reach proxy-node P. The proxy-node attachment | |||

attachment router with the lower value of mrt_node_id (as defined in | router with the lower value of mrt_node_id (as defined in Figure 15) | |||

Figure 15) is assigned to X, and the other proxy-node attachment | is assigned to X, and the other proxy-node attachment router is | |||

router is assigned to Y. We will be using the relative order of X,Y, | assigned to Y. We will be using the relative order of X,Y, and S in | |||

and S in the partial order defined by the GADAG to determine the MRT | the partial order defined by the GADAG to determine the MRT red and | |||

red and blue next-hops to reach P, so we also define A and B as the | blue next hops to reach P, so we also define A and B as the order | |||

order proxies for X and Y, respectively, with respect to S. The | proxies for X and Y, respectively, with respect to S. The order | |||

order proxies for all nodes with respect to S were already computed | proxies for all nodes with respect to S were already computed in | |||

in Compute_MRT_NextHops(). | Compute_MRT_NextHops(). | |||

def Select_Proxy_Node_NHs(P,S): | def Select_Proxy_Node_NHs(P,S): | |||

if P.pnar1.node.node_id < P.pnar2.node.node_id: | if P.pnar1.node.node_id < P.pnar2.node.node_id: | |||

X = P.pnar1.node | X = P.pnar1.node | |||

Y = P.pnar2.node | Y = P.pnar2.node | |||

else: | else: | |||

X = P.pnar2.node | X = P.pnar2.node | |||

Y = P.pnar1.node | Y = P.pnar1.node | |||

P.pnar_X = X | P.pnar_X = X | |||

P.pnar_Y = Y | P.pnar_Y = Y | |||

skipping to change at page 49, line 43 ¶ | skipping to change at page 51, line 4 ¶ | |||

Copy_List_Items(P.blue_next_hops, X.blue_next_hops) | Copy_List_Items(P.blue_next_hops, X.blue_next_hops) | |||

Copy_List_Items(P.red_next_hops, Y.blue_next_hops) | Copy_List_Items(P.red_next_hops, Y.blue_next_hops) | |||

return | return | |||

else: | else: | |||

// case 4.3.3 | // case 4.3.3 | |||

if A.topo_order < B.topo_order: | if A.topo_order < B.topo_order: | |||

// case 4.3.3.1 | // case 4.3.3.1 | |||

Copy_List_Items(P.blue_next_hops, X.blue_next_hops) | Copy_List_Items(P.blue_next_hops, X.blue_next_hops) | |||

Copy_List_Items(P.red_next_hops, Y.red_next_hops) | Copy_List_Items(P.red_next_hops, Y.red_next_hops) | |||

return | return | |||

else: | else: | |||

// case 4.3.3.2 | // case 4.3.3.2 | |||

Copy_List_Items(P.blue_next_hops, X.red_next_hops) | Copy_List_Items(P.blue_next_hops, X.red_next_hops) | |||

Copy_List_Items(P.red_next_hops, Y.blue_next_hops) | Copy_List_Items(P.red_next_hops, Y.blue_next_hops) | |||

return | return | |||

assert(False) | assert(False) | |||

Figure 28: Select_Proxy_Node_NHs() | Figure 28: Select_Proxy_Node_NHs() | |||

It is useful to understand up front that the blue next-hops to reach | It is useful to understand up front that the blue next hops to reach | |||

proxy-node P produced by Select_Proxy_Node_NHs() will always be the | proxy-node P produced by Select_Proxy_Node_NHs() will always be the | |||

next-hops that reach proxy-node attachment router X, while the red | next hops that reach proxy-node attachment router X, while the red | |||

next-hops to reach proxy-node P will always be the next-hops that | next hops to reach proxy-node P will always be the next hops that | |||

reach proxy-node attachment router Y. This is different from the red | reach proxy-node attachment router Y. This is different from the red | |||

and blue next-hops produced by Compute_MRT_NextHops() where, for | and blue next hops produced by Compute_MRT_NextHops() where, for | |||

example, blue next-hops to a destination that is ordered with respect | example, blue next hops to a destination that is ordered with respect | |||

to the source will always correspond to an INCREASING next-hop on the | to the source will always correspond to an INCREASING next hop on the | |||

GADAG. The exact choice of which next-hops chosen by | GADAG. The exact choice of which next hops chosen by | |||

Select_Proxy_Node_NHs() as the blue next-hops to reach P (which will | Select_Proxy_Node_NHs() as the blue next hops to reach P (which will | |||

necessarily go through X on its way to P) does depend on the GADAG, | necessarily go through X on its way to P) does depend on the GADAG, | |||

but the relationship is more complex than was the case with | but the relationship is more complex than was the case with | |||

Compute_MRT_NextHops(). | Compute_MRT_NextHops(). | |||

There are twenty-one different relative order relationships between | There are 21 different relative order relationships between A, B, and | |||

A, B and S that Select_Proxy_Node_NHs() uses to determine red and | S that Select_Proxy_Node_NHs() uses to determine red and blue next | |||

blue next-hops to P. This document does not attempt to provide an | hops to P. This document does not attempt to provide an exhaustive | |||

exhaustive description of each case considered in | description of each case considered in Select_Proxy_Node_NHs(). | |||

Select_Proxy_Node_NHs(). Instead we provide a high level overview of | Instead, we provide a high-level overview of the different cases, and | |||

the different cases, and we consider a few cases in detail to give an | we consider a few cases in detail to give an example of the reasoning | |||

example of the reasoning that can be used to understand each case. | that can be used to understand each case. | |||

At the highest level, Select_Proxy_Node_NHs() distinguishes between | At the highest level, Select_Proxy_Node_NHs() distinguishes between | |||

four different cases depending on whether or not A or B is the | four different cases depending on whether or not A or B is the | |||

localroot for S. For example, for case 4.0, neither A nor B is the | localroot for S. For example, for case 4.0, neither A nor B is the | |||

localroot for S. Case 4.05 addresses the case where S is the | localroot for S. Case 4.05 addresses the case where S is the | |||

localroot for either A or B, while cases 4.1, 4.2, and 4.3 address | localroot for either A or B, while cases 4.1, 4.2, and 4.3 address | |||

the cases where A is ordered lower than S, A is ordered higher than | the cases where A is ordered lower than S, A is ordered higher than | |||

S, or A is unordered with respect to S on the GADAG. In general, | S, or A is unordered with respect to S on the GADAG. In general, | |||

each of these cases is then further subdivided into whether or not B | each of these cases is then further subdivided into whether or not B | |||

is ordered lower than S, B is ordered higher than S, or B is | is ordered lower than S, B is ordered higher than S, or B is | |||

unordered with respect to S. In some cases we also need a further | unordered with respect to S. In some cases, we also need a further | |||

level of discrimination, where we use the topological sort order of A | level of discrimination, where we use the topological sort order of A | |||

with respect to B. | with respect to B. | |||

As a detailed example, let's consider case 4.1 and all of its sub- | As a detailed example, let's consider case 4.1 and all of its sub- | |||

cases, and explain why the red and blue next-hops to reach P are | cases, and explain why the red and blue next hops to reach P are | |||

chosen as they are in Select_Proxy_Node_NHs(). In case 4.1, neither | chosen as they are in Select_Proxy_Node_NHs(). In case 4.1, neither | |||

A nor B is the localroot for S, S is not the localroot for A or B, | A nor B is the localroot for S, S is not the localroot for A or B, | |||

and A is ordered lower than S on the GADAG. In this situation, we | and A is ordered lower than S on the GADAG. In this situation, we | |||

know that the red path to reach X (as computed in | know that the red path to reach X (as computed in | |||

Compute_MRT_NextHops()) will follow DECREASING next-hops towards A, | Compute_MRT_NextHops()) will follow DECREASING next hops towards A, | |||

while the blue path to reach X will follow INCREASING next-hops to | while the blue path to reach X will follow INCREASING next hops to | |||

the localroot, and then INCREASING next-hops to A. | the localroot, and then INCREASING next hops to A. | |||

Now consider sub-case 4.1.1 where B is ordered higher than S. In | Now consider sub-case 4.1.1 where B is ordered higher than S. In | |||

this situation, we know that the blue path to reach Y will follow | this situation, we know that the blue path to reach Y will follow | |||

INCREASING next-hops towards B, while the red next-hops to reach Y | INCREASING next hops towards B, while the red next hops to reach Y | |||

will follow DECREASING next-hops to the localroot, and then | will follow DECREASING next hops to the localroot, and then | |||

DECREASING next-hops to B. So to reach X and Y by two disjoint | DECREASING next hops to B. So, to reach X and Y by two disjoint | |||

paths, we can choose the red next-hops to X and the blue next-hops to | paths, we can choose the red next hops to X and the blue next hops to | |||

Y. We have chosen the convention that blue next-hops to P are those | Y. We have chosen the convention that blue next hops to P are those | |||

that pass through X, and red next-hops to P are those that pass | that pass through X, and red next hops to P are those that pass | |||

through Y, so we can see that case 4.1.1 produces the desired result. | through Y, so we can see that case 4.1.1 produces the desired result. | |||

Choosing blue to X and red to Y does not produce disjoint paths | Choosing blue to X and red to Y does not produce disjoint paths | |||

because the paths intersect at least at the localroot. | because the paths intersect at least at the localroot. | |||

Now consider sub-case 4.1.2 where B is ordered lower than S. In this | Now consider sub-case 4.1.2 where B is ordered lower than S. In this | |||

situation, we know that the red path to reach Y will follow | situation, we know that the red path to reach Y will follow | |||

DECREASING next-hops towards B, while the BLUE next-hops to reach Y | DECREASING next hops towards B, while the BLUE next hops to reach Y | |||

will follow INCREASING next-hops to the localroot, and then | will follow INCREASING next hops to the localroot, and then | |||

INCREASING next-hops to A. The choice here is more difficult than in | INCREASING next hops to A. The choice here is more difficult than in | |||

4.1.1 because A and B are both on the DECREASING path from S towards | 4.1.1 because A and B are both on the DECREASING path from S towards | |||

the localroot. We want to use the direct DECREASING(red) path to the | the localroot. We want to use the direct DECREASING(red) path to the | |||

one that is nearer to S on the GADAG. We get this extra information | one that is nearer to S on the GADAG. We get this extra information | |||

by comparing the topological sort order of A and B. If | by comparing the topological sort order of A and B. If | |||

A.topo_order<B.topo_order, then we use red to Y and blue to X, since | A.topo_order<B.topo_order, then we use red to Y and blue to X, since | |||

the red path to Y will DECREASE to B without hitting A, and the blue | the red path to Y will DECREASE to B without hitting A, and the blue | |||

path to X will INCREASE to A without hitting B. Instead, if | path to X will INCREASE to A without hitting B. Instead, if | |||

A.topo_order>B.topo_order, then we use red to X and blue to Y. | A.topo_order>B.topo_order, then we use red to X and blue to Y. | |||

Note that when A is unordered with respect to B, the result of | Note that when A is unordered with respect to B, the result of | |||

comparing A.topo_order with B.topo_order could be greater than or | comparing A.topo_order with B.topo_order could be greater than or | |||

less than. In this case, the result doesn't matter because either | less than. In this case, the result doesn't matter because either | |||

choice (red to Y and blue to X or red to X and blue to Y) would work. | choice (red to Y and blue to X or red to X and blue to Y) would work. | |||

What is required is that all nodes in the network give the same | What is required is that all nodes in the network give the same | |||

result when comparing A.topo_order with B.topo_order. This is | result when comparing A.topo_order with B.topo_order. This is | |||

guarantee by having all nodes run the same algorithm | guaranteed by having all nodes run the same algorithm | |||

(Run_Topological_Sort_GADAG()) to compute the topological sort order. | (Run_Topological_Sort_GADAG()) to compute the topological sort order. | |||

Finally we consider case 4.1.3, where B is unordered with respect to | Finally, we consider case 4.1.3, where B is unordered with respect to | |||

S. In this case, the blue path to reach Y will follow the DECREASING | S. In this case, the blue path to reach Y will follow the DECREASING | |||

next-hops towards the localroot until it reaches some node (K) which | next hops towards the localroot until it reaches some node (K) which | |||

is ordered less than B, after which it will take INCREASING next-hops | is ordered less than B, after which it will take INCREASING next hops | |||

to B. The red path to reach Y will follow the INCREASING next-hops | to B. The red path to reach Y will follow the INCREASING next hops | |||

towards the localroot until it reaches some node (L) which is ordered | towards the localroot until it reaches some node (L) which is ordered | |||

greater than B, after which it will take DECREASING next-hops to B. | greater than B, after which it will take DECREASING next hops to B. | |||

Both K and A are reached by DECREASING from S, but we don't have | Both K and A are reached by DECREASING from S, but we don't have | |||

information about whether or not that DECREASING path will hit K or A | information about whether or not that DECREASING path will hit K or A | |||

first. Instead, we do know that the INCREASING path from S will hit | first. Instead, we do know that the INCREASING path from S will hit | |||

L before reaching A. Therefore, we use the red path to reach Y and | L before reaching A. Therefore, we use the red path to reach Y and | |||

the red path to reach X. | the red path to reach X. | |||

Similar reasoning can be applied to understand the other seventeen | Similar reasoning can be applied to understand the other 17 cases | |||

cases used in Select_Proxy_Node_NHs(). However, cases 2.3 and 3.3 | used in Select_Proxy_Node_NHs(). However, cases 2.3 and 3.3 deserve | |||

deserve special attention because the correctness of the solution for | special attention because the correctness of the solution for these | |||

these two cases relies on a special property of the GADAGs that we | two cases relies on a special property of the GADAGs that we have | |||

have constructed in this algorithm, a property not shared by all | constructed in this algorithm, a property not shared by all GADAGs in | |||

GADAGs in general. Focusing on case 2.3, we consider the case where | general. Focusing on case 2.3, we consider the case where A is the | |||

A is the localroot for S, while B is not, and B is unordered with | localroot for S, while B is not, and B is unordered with respect to | |||

respect to S. The red path to X DECREASES from S to the localroot A, | S. The red path to X DECREASES from S to the localroot A, while the | |||

while the blue path to X INCREASES from S to the localroot A. The | blue path to X INCREASES from S to the localroot A. The blue path to | |||

blue path to Y DECREASES towards the localroot A until it reaches | Y DECREASES towards the localroot A until it reaches some node (K) | |||

some node (K) which is ordered less than B, after which the path | which is ordered less than B, after which the path INCREASES to B. | |||

INCREASES to B. The red path to Y INCREASES towards the localroot A | The red path to Y INCREASES towards the localroot A until it reaches | |||

until it reaches some node (L) which is ordered greater than B, after | some node (L) which is ordered greater than B, after which the path | |||

which the path DECREASES to B. It can be shown that for an arbitrary | DECREASES to B. It can be shown that for an arbitrary GADAG, with | |||

GADAG, with only the ordering relationships computed so far, we don't | only the ordering relationships computed so far, we don't have enough | |||

have enough information to choose a pair of paths to reach X and Y | information to choose a pair of paths to reach X and Y that are | |||

that are guaranteed to be disjoint. In some topologies, A will play | guaranteed to be disjoint. In some topologies, A will play the role | |||

the role of K, the first node ordered less than B on the blue path to | of K, the first node ordered less than B on the blue path to Y. In | |||

Y. In other topologies, A will play the role of L, the first node | other topologies, A will play the role of L, the first node ordered | |||

ordered greater than B on the red path to Y. The basic problem is | greater than B on the red path to Y. The basic problem is that we | |||

that we cannot distinguish between these two cases based on the | cannot distinguish between these two cases based on the ordering | |||

ordering relationships. | relationships. | |||

As discussed Section 5.8, the GADAGs that we construct using the | As discussed Section 5.8, the GADAGs that we construct using the | |||

algorithm in this document are not arbitrary GADAGs. They have the | algorithm in this document are not arbitrary GADAGs. They have the | |||

additional property that incoming links to a localroot come from only | additional property that incoming links to a localroot come from only | |||

one other node in the same block. This is a result of the method of | one other node in the same block. This is a result of the method of | |||

construction. This additional property guarantees that localroot A | construction. This additional property guarantees that localroot A | |||

will never play the role of L in the red path to Y, since L must have | will never play the role of L in the red path to Y, since L must have | |||

at least two incoming links from different nodes in the same block in | at least two incoming links from different nodes in the same block in | |||

the GADAG. This in turn allows Select_Proxy_Node_NHs() to choose the | the GADAG. This, in turn, allows Select_Proxy_Node_NHs() to choose | |||

red path to Y and the red path to X as the disjoint MRT paths to | the red path to Y and the red path to X as the disjoint MRT paths to | |||

reach P. | reach P. | |||

5.9.4. Computing MRT Alternates for Proxy-Nodes | 5.9.4. Computing MRT Alternates for Proxy-Nodes | |||

After finding the red and the blue next-hops for a given proxy-node | After finding the red and the blue next hops for a given proxy-node | |||

P, it is necessary to know which one of these to use in the case of | P, it is necessary to know which one of these to use in the case of | |||

failure. This can be done by Select_Alternates_Proxy_Node(), as | failure. This can be done by Select_Alternates_Proxy_Node(), as | |||

shown in the pseudo-code in Figure 29. | shown in the pseudocode in Figure 29. | |||

def Select_Alternates_Proxy_Node(P,F,primary_intf): | def Select_Alternates_Proxy_Node(P,F,primary_intf): | |||

S = primary_intf.local_node | S = primary_intf.local_node | |||

X = P.pnar_X | X = P.pnar_X | |||

Y = P.pnar_Y | Y = P.pnar_Y | |||

A = X.order_proxy | A = X.order_proxy | |||

B = Y.order_proxy | B = Y.order_proxy | |||

if F is A and F is B: | if F is A and F is B: | |||

return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' | return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' | |||

if F is A: | if F is A: | |||

skipping to change at page 58, line 21 ¶ | skipping to change at page 59, line 34 ¶ | |||

Select_Alternates(Y,F,primary_intf) to determine which of the two MRT | Select_Alternates(Y,F,primary_intf) to determine which of the two MRT | |||

paths to X and which of the two MRT paths to Y is safe to use in the | paths to X and which of the two MRT paths to Y is safe to use in the | |||

event of the failure of F. In general, we will find that if it is | event of the failure of F. In general, we will find that if it is | |||

safe to use a particular path to X or Y when F fails, and | safe to use a particular path to X or Y when F fails, and | |||

Select_Proxy_Node_NHs() used that path when constructing the red or | Select_Proxy_Node_NHs() used that path when constructing the red or | |||

blue path to reach P, then it will also be safe to use that path to | blue path to reach P, then it will also be safe to use that path to | |||

reach P when F fails. This rule has one exception which is covered | reach P when F fails. This rule has one exception which is covered | |||

below. First, we give a concrete example of how | below. First, we give a concrete example of how | |||

Select_Alternates_Proxy_Node() works in the common case. | Select_Alternates_Proxy_Node() works in the common case. | |||

The twenty one ordering relationships used in Select_Proxy_Node_NHs() | The 21 ordering relationships used in Select_Proxy_Node_NHs() are | |||

are repeated in Select_Alternates_Proxy_Node(). We focus on case | repeated in Select_Alternates_Proxy_Node(). We focus on case 4.1.1 | |||

4.1.1 to give give a detailed example of the reasoning used in | to give a detailed example of the reasoning used in | |||

Select_Alternates_Proxy_Node(). In Select_Proxy_Node_NHs(), we | Select_Alternates_Proxy_Node(). In Select_Proxy_Node_NHs(), we | |||

determined for case 4.1.1 that the red next-hops to X and the blue | determined for case 4.1.1 that the red next hops to X and the blue | |||

next-hops to Y allow us to reach X and Y by disjoint paths, and are | next hops to Y allow us to reach X and Y by disjoint paths, and are | |||

thus the blue and red next-hops to reach P. Therefore, if we run | thus the blue and red next hops to reach P. Therefore, if | |||

Select_Alternates(X, F, primary_intf) and we find that it is safe to | Select_Alternates(X, F, primary_intf) is run and we find that it is | |||

USE_RED to reach X, then we also conclude that it is safe to use the | safe to USE_RED to reach X, then we also conclude that it is safe to | |||

MRT path through X to reach P (the blue path to P) when F fails. | use the MRT path through X to reach P (the blue path to P) when F | |||

Similarly, if run Select_Alternates(X, F, primary_intf) and we find | fails. Similarly, if we run Select_Alternates(Y, F, primary_intf) | |||

that it is safe to USE_BLUE to reach Y, then we also conclude that it | and we find that it is safe to USE_BLUE to reach Y, then we also | |||

is safe to use the MRT path through Y to reach P (the red path to P) | conclude that it is safe to use the MRT path through Y to reach P | |||

when F fails. If both of the paths that were used in | (the red path to P) when F fails. If both of the paths that were | |||

Select_Proxy_Node_NHs() to construct the blue and red paths to P are | used in Select_Proxy_Node_NHs() to construct the blue and red paths | |||

found to be safe to use to use to reach X and Y, t then we conclude | to P are found to be safe to use to use to reach X and Y, t then we | |||

that we can use either the red or the blue path to P. | conclude that we can use either the red or the blue path to P. | |||

This simple reasoning gives the correct answer in most of the cases. | This simple reasoning gives the correct answer in most of the cases. | |||

However, additional logic is needed when either A or B (but not both | However, additional logic is needed when either A or B (but not both | |||

A and B) is unordered with respect to S. This applies to cases | A and B) is unordered with respect to S. This applies to cases | |||

4.1.3, 4.2.3, 4.3.1, and 4.3.2. Looking at case 4.1.3 in more | 4.1.3, 4.2.3, 4.3.1, and 4.3.2. Looking at case 4.1.3 in more | |||

detail, A is ordered less than S, but B is unordered with respect to | detail, A is ordered less than S, but B is unordered with respect to | |||

S. In the discussion of case 4.1.3 above, we saw that | S. In the discussion of case 4.1.3 above, we saw that | |||

Select_Proxy_Node_NHs() chose the red path to reach Y and the red | Select_Proxy_Node_NHs() chose the red path to reach Y and the red | |||

path to reach X. We also saw that the red path to reach Y will | path to reach X. We also saw that the red path to reach Y will | |||

follow the INCREASING next-hops towards the localroot until it | follow the INCREASING next hops towards the localroot until it | |||

reaches some node (L) which is ordered greater than B, after which it | reaches some node (L) which is ordered greater than B, after which it | |||

will take DECREASING next-hops to B. The problem is that the red | will take DECREASING next hops to B. The problem is that the red | |||

path to reach P (the one that goes through Y) won't necessarily be | path to reach P (the one that goes through Y) won't necessarily be | |||

the same as the red path to reach Y. This is because the next-hop | the same as the red path to reach Y. This is because the next hop | |||

that node L computes for its red next-hop to reach P may be different | that node L computes for its red next hop to reach P may be different | |||

from the next-hop it computes for its red next-hop to reach Y. This | from the next hop it computes for its red next hop to reach Y. This | |||

is because B is ordered lower than L, so L applies case 4.1.2 of | is because B is ordered lower than L, so L applies case 4.1.2 of | |||

Select_Proxy_Node_NHs() in order to determine its next-hops to reach | Select_Proxy_Node_NHs() in order to determine its next hops to reach | |||

P. If A.topo_order<B.topo_order (case 4.1.2.1), then L will choose | P. If A.topo_order<B.topo_order (case 4.1.2.1), then L will choose | |||

DECREASING next-hops directly to B, which is the same result that L | DECREASING next hops directly to B, which is the same result that L | |||

computes in Compute_MRT_NextHops() to reach Y. However, if | computes in Compute_MRT_NextHops() to reach Y. However, if | |||

A.topo_order>B.topo_order (case 4.1.2.2), then L will choose | A.topo_order>B.topo_order (case 4.1.2.2), then L will choose | |||

INCREASING next-hops to reach B, which is different from what L | INCREASING next hops to reach B, which is different from what L | |||

computes in Compute_MRT_NextHops() to reach Y. So testing the safety | computes in Compute_MRT_NextHops() to reach Y. So, testing the | |||

of the path for S to reach Y on failure of F as a surrogate for the | safety of the path for S to reach Y on failure of F as a surrogate | |||

safety of using the red path to reach P is not reliable in this case. | for the safety of using the red path to reach P is not reliable in | |||

It is possible construct topologies where the red path to P hits F | this case. It is possible construct topologies where the red path to | |||

even though the red path to Y does not hit F. | P hits F even though the red path to Y does not hit F. | |||

Fortunately there is enough information in the order relationships | Fortunately, there is enough information in the order relationships | |||

that we have already computed to still figure out which alternate to | that we have already computed to still figure out which alternate to | |||

choose in these four cases. The basic idea is to always choose the | choose in these four cases. The basic idea is to always choose the | |||

path involving the ordered node, unless that path would hit F. | path involving the ordered node, unless that path would hit F. | |||

Returning to case 4.1.3, we see that since A is ordered lower than S, | Returning to case 4.1.3, we see that since A is ordered lower than S, | |||

the only way for S to hit F using a simple DECREASING path to A is | the only way for S to hit F using a simple DECREASING path to A is | |||

for F to lie between A and S on the GADAG. This scenario is covered | for F to lie between A and S on the GADAG. This scenario is covered | |||

by requiring that F be lower than S (but not also higher than S) and | by requiring that F be lower than S (but not also higher than S) and | |||

that F.topo_order>A.topo_order in case 4.1.3.1. | that F.topo_order>A.topo_order in case 4.1.3.1. | |||

We just need to confirm that it is safe to use the path involving B | We just need to confirm that it is safe to use the path involving B | |||

in this scenario. In case 4.1.3.1, either F is between A and S on | in this scenario. In case 4.1.3.1, either F is between A and S on | |||

the GADAG, or F is unordered with respect to A and lies on the | the GADAG, or F is unordered with respect to A and lies on the | |||

DECREASING path from S to the localroot. When F is between A and S | DECREASING path from S to the localroot. When F is between A and S | |||

on the GADAG, then the path through B chosen to avoid A in | on the GADAG, then the path through B chosen to avoid A in | |||

Select_Proxy_Node_NHs() will also avoid F. When F is unordered with | Select_Proxy_Node_NHs() will also avoid F. When F is unordered with | |||

respect to A and lies on the DECREASING path from S to the localroot, | respect to A and lies on the DECREASING path from S to the localroot, | |||

then we consider two cases. Either F.topo_order<B.topo_order or | then we consider two cases. Either F.topo_order<B.topo_order or | |||

F.topo_order>B.topo_order. In the first case, since | F.topo_order>B.topo_order. In the first case, since | |||

F.topo_order<B.topo_order and F.topo_order>A.topo_order, it must be | F.topo_order<B.topo_order and F.topo_order>A.topo_order, it must be | |||

the case that A.topo_order<B.topo_order. Therefore, L will choose | the case that A.topo_order<B.topo_order. Therefore, L will choose | |||

DECREASING next-hops directly to B (case 4.1.2.1), which cannot hit F | DECREASING next hops directly to B (case 4.1.2.1), which cannot hit F | |||

since F.topo_order<B.topo_order. In the second case, where | since F.topo_order<B.topo_order. In the second case, where | |||

F.topo_order>B.topo_order, the only way for the path involving B to | F.topo_order>B.topo_order, the only way for the path involving B to | |||

hit F is if it DECREASES from L to B through F , ie. it must be that | hit F is if it DECREASES from L to B through F, i.e., it must be that | |||

L>>F>>B. However, since S>>F, this would imply that S>>B. However, | L>>F>>B. However, since S>>F, this would imply that S>>B. However, | |||

we know that S is unordered with respect to B, so the second case | we know that S is unordered with respect to B, so the second case | |||

cannot occur. So we have demonstrated that the red path to P (which | cannot occur. So we have demonstrated that the red path to P (which | |||

goes via B and Y) is safe to use under the conditions of 4.1.3.1. | goes via B and Y) is safe to use under the conditions of 4.1.3.1. | |||

Similar reasoning can be applied to the other three special cases | Similar reasoning can be applied to the other three special cases | |||

where either A or B is unordered with respect to S. | where either A or B is unordered with respect to S. | |||

6. MRT Lowpoint Algorithm: Next-hop conformance | 6. MRT Lowpoint Algorithm: Next-Hop Conformance | |||

This specification defines the MRT Lowpoint Algorithm, which include | This specification defines the MRT Lowpoint algorithm, which includes | |||

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.7 for each of the | the available nodes that are described in Section 5.7 for each of the | |||

MRT-Red and MRT-Blue and the selected next-hops are further along in | MRT-Red and MRT-Blue and the selected next hops are further along in | |||

the interval of allowed nodes towards the destination. | the interval of allowed nodes towards the destination. | |||

For example, the MRT-Blue next-hops used when the destination Y >> X, | For example, the MRT-Blue next hops used when the destination Y >> X, | |||

the computing router, MUST be one or more nodes, T, whose topo_order | the computing router, MUST be one or more nodes, T, whose topo_order | |||

is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y | is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y | |||

is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in | is T. Similarly, the MRT-Red next hops MUST be have a topo_order in | |||

the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, | the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, | |||

R-big.topo_order]. | R-big.topo_order]. | |||

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

7. Broadcast interfaces | 7. Broadcast Interfaces | |||

When broadcast interfaces are used to connect nodes, the broadcast | When broadcast interfaces are used to connect nodes, the broadcast | |||

network MUST be represented as a pseudonode, where each real node | network MUST be represented as a pseudonode, where each real node | |||

connects to the pseudonode. The interface metric in the direction | connects to the pseudonode. The interface metric in the direction | |||

from real node to pseudonode is the non-zero interface metric, while | from real node to pseudonode is the non-zero interface metric, while | |||

the interface metric in the direction from the pseudonode to the real | the interface metric in the direction from the pseudonode to the real | |||

node is set to zero. This is consistent with the way that broadcast | node is set to zero. This is consistent with the way that broadcast | |||

interfaces are represented as pseudonodes in IS-IS and OSPF. | interfaces are represented as pseudonodes in IS-IS and OSPF. | |||

Pseudonodes MUST be treated as equivalent to real nodes in the | Pseudonodes MUST be treated as equivalent to real nodes in the | |||

network graph used in the MRT algorithm with a few exceptions | network graph used in the MRT Lowpoint algorithm with a few | |||

detailed below. | exceptions detailed below. | |||

The pseudonodes MUST be included in the computation of the GADAG. | The pseudonodes MUST be included in the computation of the GADAG. | |||

The neighbors of the pseudonode need to know the mrt_node_id of the | The neighbors of the pseudonode need to know the mrt_node_id of the | |||

pseudonode in order to consistently order interfaces, which is needed | pseudonode in order to consistently order interfaces, which is needed | |||

to compute the GADAG. The mrt_node_id for IS-IS is the 7 octet | to compute the GADAG. The mrt_node_id for IS-IS is the 7-octet | |||

neighbor system ID and pseudonode number in TLV #22 or TLV#222. The | neighbor system ID and pseudonode number in TLV 22 or TLV 222. The | |||

mrt_node_id for OSPFv2 is the 4 octet interface address of the | mrt_node_id for OSPFv2 is the 4-octet interface address of the | |||

Designated Router found in the Link ID field for the link type 2 | Designated Router found in the Link ID field for the link type 2 | |||

(transit network) in the Router-LSA. The mrt_node_id for OSPFv3 is | (transit network) in the Router-LSA. The mrt_node_id for OSPFv3 is | |||

the 4 octet interface address of the Designated Router found in the | the 4 octet interface address of the Designated Router found in the | |||

Neighbor Interface ID field for the link type 2 (transit network) in | Neighbor Interface ID field for the link type 2 (transit network) in | |||

the Router-LSA. pseudonodes MUST NOT be considered as candidates for | the Router-LSA. Note that this is different from the Neighbor Router | |||

GADAG root selection. Note that this is different from the Neighbor | ID field used for the mrt_node_id for point-to-point links in OSPFv3 | |||

Router ID field used for the mrt_node_id for point-to-point links in | Router-LSAs given in Figure 15. | |||

OSPFv3 Router-LSAs given in Figure 15. | ||||

Pseudonodes MUST NOT be considered as candidates for selection as | Pseudonodes MUST NOT be considered candidates for selection as GADAG | |||

GADAG root. This rule is intended to result in a more stable | root. This rule is intended to result in a more stable network-wide | |||

network- wide selection of GADAG root by removing the possibility | selection of GADAG root by removing the possibility that the change | |||

that the change of Designated Router or Designated Intermediate | of Designated Router or Designated Intermediate System on a broadcast | |||

System on a broadcast network can result in a change of GADAG root. | network can result in a change of GADAG root. | |||

7.1. Computing MRT next-hops on broadcast networks | 7.1. Computing MRT Next Hops on Broadcast Networks | |||

The pseudonode does not correspond to an real node, so it is not | The pseudonode does not correspond to a real node, so it is not | |||

actually involved in forwarding. A real node on a broadcast network | actually involved in forwarding. A real node on a broadcast network | |||

cannot simply forward traffic to the broadcast network. It must | cannot simply forward traffic to the broadcast network. It must | |||

specify another real node on the broadcast network as the next-hop. | specify another real node on the broadcast network as the next hop. | |||

On a network graph where a broadcast network is represented by a | On a network graph where a broadcast network is represented by a | |||

pseudonode, this means that if a real node determines that the next- | pseudonode, this means that if a real node determines that the next | |||

hop to reach a given destination is a pseudonode, it must also | hop to reach a given destination is a pseudonode, it must also | |||

determine the next-next-hop for that destination in the network | determine the next-next-hop for that destination in the network | |||

graph, which corresponds to a real node attached to the broadcast | graph, which corresponds to a real node attached to the broadcast | |||

network. | network. | |||

It is interesting to note that this issue is not unique to the MRT | It is interesting to note that this issue is not unique to the MRT | |||

algorithm, but is also encountered in normal SPF computations for | algorithm, but is also encountered in normal SPF computations for | |||

IGPs. Section 16.1.1 of [RFC2328] describes how this is done for | IGPs. Section 16.1.1 of [RFC2328] describes how this is done for | |||

OSPF. As OSPF runs Dijkstra's algorithm, whenever a shorter path is | OSPF. When OSPF runs its shortest-path tree calculation, it deals | |||

found reach a real destination node, and the shorter path is one hop | with pseudonodes in the following manner. Whenever the calculating | |||

from the computing routing, and that one hop is a pseudonode, then | router finds a shorter path to reach a real destination node and the | |||

the next-hop for that destination is taken from the interface IP | shorter path to the destination is a single pseudonode hop, then the | |||

address in the Router-LSA correspond to the link to the real | next hop for that destination is taken from the interface IP address | |||

destination node | in the Router-LSA correspond to the link to the real destination | |||

node. | ||||

For IS-IS, in the example pseudo-code implementation of Dijkstra's | For IS-IS, in the example pseudocode implementation of Dijkstra's | |||

algorithm in Annex C of [ISO10589-Second-Edition] whenever the | algorithm in Annex C of [ISO10589-Second-Edition], whenever the | |||

algorithm encounters an adjacency from a real node to a pseudonode, | algorithm encounters an adjacency from a real node to a pseudonode, | |||

it gets converted to a set of adjacencies from the real node to the | it gets converted to a set of adjacencies from the real node to the | |||

neighbors of the pseudonode. In this way, the computed next-hops | neighbors of the pseudonode. In this way, the computed next hops | |||

point all the way to the real node, and not the pseudonode. | point all the way to the real node, and not the pseudonode. | |||

We could avoid the problem of determining next-hops across | We could avoid the problem of determining next hops across | |||

pseudonodes in MRT by converting the pseudonode representation of | pseudonodes in MRT by converting the pseudonode representation of | |||

broadcast networks to a full mesh of links between real nodes on the | broadcast networks to a full mesh of links between real nodes on the | |||

same network. However, if we make that conversion before computing | same network. However, if we make that conversion before computing | |||

the GADAG, we lose information about which links actually correspond | the GADAG, we lose information about which links actually correspond | |||

to a single physical interface into the broadcast network. This | to a single physical interface into the broadcast network. This | |||

could result computing red and blue next-hops that use the same | could result computing red and blue next hops that use the same | |||

broadcast interface, in which case neither the red nor the blue next- | broadcast interface, in which case neither the red nor the blue next | |||

hop would be usable as an alternate on failure of the broadcast | hop would be usable as an alternate on failure of the broadcast | |||

interface. | interface. | |||

Instead, we take the following approach, which maintains the property | Instead, we take the following approach, which maintains the property | |||

that either the red and blue next-hop will avoid the broadcast | that either the red and blue next hop will avoid the broadcast | |||

network, if topologically allowed. We run the MRT algorithm treating | network, if topologically allowed. We run the MRT Lowpoint algorithm | |||

the pseudonodes as equivalent to real nodes in the network graph, | treating the pseudonodes as equivalent to real nodes in the network | |||

with the exceptions noted above. In addition to running the MRT | graph, with the exceptions noted above. In addition to running the | |||

algorithm from the point of view of itself, a computing router | MRT Lowpoint algorithm from the point of view of itself, a computing | |||

connected to a pseudonode MUST also run the MRT algorithm from the | router connected to a pseudonode MUST also run the MRT Lowpoint | |||

point of view of each of its pseudonode neighbors. For example, if a | algorithm from the point of view of each of its pseudonode neighbors. | |||

computing router S determines that its MRT red next-hop to reach a | For example, if a computing router S determines that its MRT red next | |||

destination D is a pseudonode P, S looks at its MRT algorithm | hop to reach a destination D is a pseudonode P, S looks at its MRT | |||

computation from P's point of view to determine P's red next-hop to | Lowpoint algorithm computation from P's point of view to determine | |||

reach D, say interface 1 on node X. S now knows that its real red | P's red next hop to reach D, say interface 1 on node X. S now knows | |||

next-hop to reach D is interface 1 on node X on the broadcast network | that its real red next hop to reach D is interface 1 on node X on the | |||

represented by P, and can install the corresponding entry in its FIB. | broadcast network represented by P, and it can install the | |||

corresponding entry in its FIB. | ||||

7.2. Using MRT next-hops as alternates in the event of failures on | 7.2. Using MRT Next Hops as Alternates in the Event of Failures on | |||

broadcast networks | Broadcast Networks | |||

In the previous section, we specified how to compute MRT next-hops | In the previous section, we specified how to compute MRT next hops | |||

when broadcast networks are involved. In this section, we discuss | when broadcast networks are involved. In this section, we discuss | |||

how a PLR can use those MRT next-hops in the event of failures | how a PLR can use those MRT next hops in the event of failures | |||

involving broadcast networks. | involving broadcast networks. | |||

A PLR attached to a broadcast network running only OSPF or IS-IS with | A PLR attached to a broadcast network running only OSPF or IS-IS with | |||

large Hello intervals has limited ability to quickly detect failures | large Hello intervals has limited ability to quickly detect failures | |||

on a broadcast network. The only failure mode that can be quickly | on a broadcast network. The only failure mode that can be quickly | |||

detected is the failure of the physical interface connecting the PLR | detected is the failure of the physical interface connecting the PLR | |||

to the broadcast network. For the failure of the interface | to the broadcast network. For the failure of the interface | |||

connecting the PLR to the broadcast network, the alternate that | connecting the PLR to the broadcast network, the alternate that | |||

avoids the broadcast network can be computed by using the broadcast | avoids the broadcast network can be computed by using the broadcast | |||

network pseudonode as F, the primary next-hop node, in | network pseudonode as F, the primary next-hop node, in | |||

skipping to change at page 63, line 4 ¶ | skipping to change at page 64, line 16 ¶ | |||

broadcast network. This is the best that we can hope to do if | broadcast network. This is the best that we can hope to do if | |||

failure of the broadcast interface is the only failure mode that the | failure of the broadcast interface is the only failure mode that the | |||

PLR can respond to. | PLR can respond to. | |||

We can improve on this if the PLR also has the ability to quickly | We can improve on this if the PLR also has the ability to quickly | |||

detect a lack of connectivity across the broadcast network to a given | detect a lack of connectivity across the broadcast network to a given | |||

IP-layer node. This can be accomplished by running BFD between all | IP-layer node. This can be accomplished by running BFD between all | |||

pairs of IGP neighbors on the broadcast network. Note that in the | pairs of IGP neighbors on the broadcast network. Note that in the | |||

case of OSPF, this would require establishing BFD sessions between | case of OSPF, this would require establishing BFD sessions between | |||

all pairs of neighbors in the 2-WAY state. When the PLR can quickly | all pairs of neighbors in the 2-WAY state. When the PLR can quickly | |||

detect the failure of a particular next-hop across a broadcast | detect the failure of a particular next hop across a broadcast | |||

network, then the PLR can be more selective in its choice of | network, the PLR can be more selective in its choice of alternates. | |||

alternates. For example, when the PLR observes that connectivity to | For example, when the PLR observes that connectivity to an IP-layer | |||

an IP-layer node on a broadcast network has failed, the PLR may | node on a broadcast network has failed, the PLR may choose to still | |||

choose to still use the broadcast network to reach other IP-layer | use the broadcast network to reach other IP-layer nodes that are | |||

nodes which are still reachable. Or if the PLR observes that | still reachable. Or, if the PLR observes that connectivity has | |||

connectivity has failed to several IP-layer nodes on the same | failed to several IP-layer nodes on the same broadcast network, it | |||

broadcast network, it may choose to treat the entire broadcast | may choose to treat the entire broadcast network as failed. The | |||

network as failed. The choice of MRT alternates by a PLR for a | choice of MRT alternates by a PLR for a particular set of failure | |||

particular set of failure conditions is a local decision, since it | conditions is a local decision, since it does not require | |||

does not require coordination with other nodes. | coordination with other nodes. | |||

8. Evaluation of Alternative Methods for Constructing GADAGs | 8. Evaluation of Alternative Methods for Constructing GADAGs | |||

This document specifies the MRT Lowpoint algorithm. One component of | This document specifies the MRT Lowpoint algorithm. One component of | |||

the algorithm involves constructing a common GADAG based on the | the algorithm involves constructing a common GADAG based on the | |||

network topology. The MRT Lowpoint algorithm computes the GADAG | network topology. The MRT Lowpoint algorithm computes the GADAG | |||

using the method described in Section 5.5. This method aims to | using the method described in Section 5.5. This method aims to | |||

minimize the amount of computation required to compute the GADAG. In | minimize the amount of computation required to compute the GADAG. In | |||

the process of developing the MRT Lowpoint algorithm, two alternative | the process of developing the MRT Lowpoint algorithm, two alternative | |||

methods for constructing GADAGs were also considered. These | methods for constructing GADAGs were also considered. These | |||

alternative methods are described in Appendix B and Appendix C. In | alternative methods are described in Appendices B and C. In general, | |||

general, these other two methods require more computation to compute | these other two methods require more computation to compute the | |||

the GADAG. The analysis below was performed to determine if the | GADAG. The analysis below was performed to determine if the | |||

alternative GADAG construction methods produce shorter MRT alternate | alternative GADAG construction methods produce shorter MRT alternate | |||

paths in real network topologies, and if so, to what extent. | paths in real network topologies, and if so, to what extent. | |||

Figure 30 compares results obtained using the three different methods | Figure 30 compares results obtained using the three different methods | |||

for constructing GADAGs on five different service provider network | for constructing GADAGs on five different service provider network | |||

topologies. MRT_LOWPOINT indicates the method specified in | topologies. MRT_LOWPOINT indicates the method specified in | |||

Section 5.5, while MRT_SPF and MRT_HYBRID indicate the methods | Section 5.5, while MRT_SPF and MRT_HYBRID indicate the methods | |||

specified in Appendix B and Appendix C, respectively. The columns on | specified in Appendices B and C, respectively. The columns on the | |||

the right present the distribution of alternate path lengths for each | right present the distribution of alternate path lengths for each | |||

GADAG construction method. Each MRT computation was performed using | GADAG construction method. Each MRT computation was performed using | |||

a same GADAG root chosen based on centrality. | a same GADAG root chosen based on centrality. | |||

For three of the topologies analyzed (T201, T206, and T211), the use | For three of the topologies analyzed (T201, T206, and T211), the use | |||

of MRT_SPF or MRT_HYBRID methods does not appear to provide a | of MRT_SPF or MRT_HYBRID methods does not appear to provide a | |||

significantly shorter alternate path lengths compared to the | significantly shorter alternate path lengths compared to the | |||

MRT_LOWPOINT method. However, for two of the topologies (T216 and | MRT_LOWPOINT method. However, for two of the topologies (T216 and | |||

T219), the use of the MRT_SPF method resulted in noticeably shorter | T219), the use of the MRT_SPF method resulted in noticeably shorter | |||

alternate path lengths than the use of the MRT_LOWPOINT or MRT_HYBRID | alternate path lengths than the use of the MRT_LOWPOINT or MRT_HYBRID | |||

methods. | methods. | |||

It was decided to use the MRT_LOWPOINT method to construct the GADAG | It was decided to use the MRT_LOWPOINT method to construct the GADAG | |||

in the algorithm specified in this draft, in order to initially offer | in the algorithm specified in this document, in order to initially | |||

an algorithm with lower computational requirements. These results | offer an algorithm with lower computational requirements. These | |||

indicate that in the future it may be useful to evaluate and | results indicate that in the future it may be useful to evaluate and | |||

potentially specify other MRT algorithm variants that use different | potentially specify other MRT Lowpoint algorithm variants that use | |||

GADAG construction methods. | different GADAG construction methods. | |||

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

| Topology name | percentage of failure scenarios | | | Topology name | percentage of failure scenarios | | |||

| | protected by an alternate N hops | | | | protected by an alternate N hops | | |||

| GADAG construction | longer than the primary path | | | GADAG construction | longer than the primary path | | |||

| method +------------------------------------+ | | method +------------------------------------+ | |||

| | | | | | | | | | no | | | | | | | | | | | | no | | |||

| | | | | | |10 |12 |14 | alt| | | | | | | | |10 |12 |14 | alt| | |||

| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |||

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

skipping to change at page 64, line 42 ¶ | skipping to change at page 66, line 40 ¶ | |||

| MRT_HYBRID | 23| 22| 18| 13| 10| 7| 4| 2| 2| | | MRT_HYBRID | 23| 22| 18| 13| 10| 7| 4| 2| 2| | |||

| MRT_SPF | 35| 32| 19| 9| 3| 1| | | | | | MRT_SPF | 35| 32| 19| 9| 3| 1| | | | | |||

| MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| | | MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| | |||

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

| T219(avg primary hops=7.7) | | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | | | |||

| MRT_HYBRID | 20| 16| 13| 10| 7| 5| 5| 5| 3| | | MRT_HYBRID | 20| 16| 13| 10| 7| 5| 5| 5| 3| | |||

| MRT_SPF | 31| 23| 19| 12| 7| 4| 2| 1| | | | MRT_SPF | 31| 23| 19| 12| 7| 4| 2| 1| | | |||

| MRT_LOWPOINT | 19| 14| 15| 12| 10| 8| 7| 6| 10| | | MRT_LOWPOINT | 19| 14| 15| 12| 10| 8| 7| 6| 10| | |||

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

Figure 30 | Figure 30: The Length of Alternate Paths for Various GADAG | |||

Construction Methods | ||||

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

10. Operational Considerations | 9. Operational Considerations | |||

This sections discusses operational considerations related to the the | This section discusses operational considerations related to the MRT | |||

MRT Lowpoint algorithm and other potential MRT algorithm variants. | Lowpoint algorithm and other potential MRT algorithm variants. For a | |||

For a discussion of operational considerations related to MRT-FRR in | discussion of operational considerations related to MRT-FRR in | |||

general, see the Operational Considerations section of | general, see the "Operational Considerations" section of [RFC7812]. | |||

[I-D.ietf-rtgwg-mrt-frr-architecture]. | ||||

10.1. GADAG Root Selection | 9.1. GADAG Root Selection | |||

The Default MRT Profile uses the GADAG Root Selection Priority | The Default MRT Profile uses the GADAG Root Selection Priority | |||

advertised by routers as the primary criterion for selecting the | advertised by routers as the primary criterion for selecting the | |||

GADAG root. It is RECOMMENDED that an operator designate a set of | GADAG root. It is RECOMMENDED that an operator designate a set of | |||

routers as good choices for selection as GADAG root by setting the | routers as good choices for selection as GADAG root by setting the | |||

GADAG Root Selection Priority for that set of routers to lower (more | GADAG Root Selection Priority for that set of routers to lower (more | |||

preferred) numerical values. Criteria for making this designation | preferred) numerical values. Criteria for making this designation | |||

are discussed below. | are discussed below. | |||

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

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

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

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

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

If the router currently selected as GADAG root becomes unreachable in | If the router currently selected as GADAG root becomes unreachable in | |||

the IGP topology, then a new GADAG root will be selected. Changing | the IGP topology, then a new GADAG root will be selected. Changing | |||

the GADAG root can change the overall structure of the GADAG as well | the GADAG root can change the overall structure of the GADAG as well | |||

the paths of the red and blue MRT trees built using that GADAG. In | the paths of the red and MRT-Blue trees built using that GADAG. In | |||

order to minimize change in the associated red and blue MRT | order to minimize change in the associated red and MRT-Blue | |||

forwarding entries that can result from changing the GADAG root, it | forwarding entries that can result from changing the GADAG root, it | |||

is RECOMMENDED that operators prioritize for selection as GADAG root | is RECOMMENDED that operators prioritize for selection as GADAG root | |||

those routers that are expected to consistently remain part of the | those routers that are expected to consistently remain part of the | |||

IGP topology. | IGP topology. | |||

10.2. Destination-rooted GADAGs | 9.2. Destination-Rooted GADAGs | |||

The MRT Lowpoint algorithm constructs a single GADAG rooted at a | The MRT Lowpoint algorithm constructs a single GADAG rooted at a | |||

single node selected as the GADAG root. It is also possible to | single node selected as the GADAG root. It is also possible to | |||

construct a different GADAG for each destination, with the GADAG | construct a different GADAG for each destination, with the GADAG | |||

rooted at the destination. A router can compute the MRT-Red and MRT- | rooted at the destination. A router can compute the MRT-Red and MRT- | |||

Blue next-hops for that destination based on the GADAG rooted at that | Blue next hops for that destination based on the GADAG rooted at that | |||

destination. Building a different GADAG for each destination is | destination. Building a different GADAG for each destination is | |||

computationally more expensive, but it may give somewhat shorter | computationally more expensive, but it may give somewhat shorter | |||

alternate paths. Using destination-rooted GADAGs would require a new | alternate paths. Using destination-rooted GADAGs would require a new | |||

MRT profile to be created with a new MRT algorithm specification, | MRT profile to be created with a new MRT algorithm specification, | |||

since all routers in the MRT Island would need to use destination- | since all routers in the MRT Island would need to use destination- | |||

rooted GADAGs. | rooted GADAGs. | |||

11. Acknowledgements | 10. Security Considerations | |||

The authors would like to thank Shraddha Hegde, Eric Wu, Janos | ||||

Farkas, Stewart Bryant, and Alvaro Retana for their suggestions and | ||||

review. We would also like to thank Anil Kumar SN for his assistance | ||||

in clarifying the algorithm description and pseudo-code. | ||||

12. IANA Considerations | ||||

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

13. Security Considerations | ||||

The algorithm described in this document does not introduce new | The algorithm described in this document does not introduce new | |||

security concerns beyond those already discussed in the document | security concerns beyond those already discussed in the document | |||

describing the MRT FRR architecture | describing the MRT FRR architecture [RFC7812]. | |||

[I-D.ietf-rtgwg-mrt-frr-architecture]. | ||||

14. References | ||||

14.1. Normative References | 11. References | |||

[I-D.ietf-rtgwg-mrt-frr-architecture] | 11.1. Normative References | |||

Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, | ||||

A., Tantsura, J., and R. White, "An Architecture for IP/ | ||||

LDP Fast-Reroute Using Maximally Redundant Trees", draft- | ||||

ietf-rtgwg-mrt-frr-architecture-07 (work in progress), | ||||

October 2015. | ||||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | |||

Requirement Levels", BCP 14, RFC 2119, | Requirement Levels", BCP 14, RFC 2119, | |||

DOI 10.17487/RFC2119, March 1997, | DOI 10.17487/RFC2119, March 1997, | |||

<http://www.rfc-editor.org/info/rfc2119>. | <http://www.rfc-editor.org/info/rfc2119>. | |||

14.2. Informative References | [RFC7812] Atlas, A., Bowers, C., and G. Enyedi, "An Architecture for | |||

IP/LDP Fast Reroute Using Maximally Redundant Trees | ||||

(MRT-FRR)", RFC 7812, DOI 10.17487/RFC7812, June 2016, | ||||

<http://www.rfc-editor.org/info/rfc7812>. | ||||

11.2. Informative References | ||||

[EnyediThesis] | [EnyediThesis] | |||

Enyedi, G., "Novel Algorithms for IP Fast Reroute", | Enyedi, G., "Novel Algorithms for IP Fast Reroute", | |||

Department of Telecommunications and Media Informatics, | Department of Telecommunications and Media Informatics, | |||

Budapest University of Technology and Economics Ph.D. | Budapest University of Technology and Economics Ph.D. | |||

Thesis, February 2011, <http://www.omikk.bme.hu/collection | Thesis, February 2011, | |||

s/phd/Villamosmernoki_es_Informatikai_Kar/2011/ | <https://repozitorium.omikk.bme.hu/bitstream/ | |||

Enyedi_Gabor/ertekezes.pdf>. | handle/10890/1040/ertekezes.pdf>. | |||

[IEEE8021Qca] | [IEEE8021Qca] | |||

IEEE 802.1, "IEEE 802.1Qca Bridges and Bridged Networks - | IEEE, "IEEE Standard for Local and metropolitan area | |||

Amendment: Path Control and Reservation - Draft 2.1", | networks - Bridges and Bridged Networks - Amendment 24: | |||

(work in progress), June 24, 2015, | Path Control and Reservation", IEEE 802.1Qca-2015, | |||

<http://www.ieee802.org/1/pages/802.1ca.html>. | DOI 10.1109/IEEESTD.2016.7434544, 2016, | |||

<https://standards.ieee.org/findstds/ | ||||

standard/802.1Qca-2015.html>. | ||||

[ISO10589-Second-Edition] | [ISO10589-Second-Edition] | |||

International Organization for Standardization, | International Organization for Standardization, | |||

"Intermediate system to Intermediate system intra-domain | "Intermediate system to Intermediate system intra-domain | |||

routeing information exchange protocol for use in | routeing information exchange protocol for use in | |||

conjunction with the protocol for providing the | conjunction with the protocol for providing the | |||

connectionless-mode Network Service (ISO 8473)", ISO/ | connectionless-mode Network Service (ISO 8473)", ISO/ | |||

IEC 10589:2002, Second Edition, Nov. 2002. | IEC 10589:2002, Second Edition, November 2002. | |||

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

10.1145/368996.369025, November 1962, | ||||

<http://dl.acm.org/citation.cfm?doid=368996.369025>. | <http://dl.acm.org/citation.cfm?doid=368996.369025>. | |||

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

Symposium on Computers and Comunications (ISCC) , 2009, | Symposium on Computers and Communications (ISCC), 2009, | |||

<http://opti.tmit.bme.hu/~enyedi/ipfrr/ | <http://opti.tmit.bme.hu/~enyedi/ipfrr/ | |||

distMaxRedTree.pdf>. | distMaxRedTree.pdf>. | |||

[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, | [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, | |||

DOI 10.17487/RFC2328, April 1998, | DOI 10.17487/RFC2328, April 1998, | |||

<http://www.rfc-editor.org/info/rfc2328>. | <http://www.rfc-editor.org/info/rfc2328>. | |||

[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi | ||||

Topology (MT) Routing in Intermediate System to | ||||

Intermediate Systems (IS-ISs)", RFC 5120, | ||||

DOI 10.17487/RFC5120, February 2008, | ||||

<http://www.rfc-editor.org/info/rfc5120>. | ||||

[RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. | ||||

So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", | ||||

RFC 7490, DOI 10.17487/RFC7490, April 2015, | ||||

<http://www.rfc-editor.org/info/rfc7490>. | ||||

Appendix A. Python Implementation of MRT Lowpoint Algorithm | Appendix A. Python Implementation of MRT Lowpoint Algorithm | |||

Below is Python code implementing the MRT Lowpoint algorithm | Below is Python code implementing the MRT Lowpoint algorithm | |||

specified in this document. In order to avoid the page breaks in the | specified in this document. The code is also posted on GitHub | |||

.txt version of the draft, one can cut and paste the Python code from | <https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr- | |||

the .xml version. The code is also posted on Github. | algorithm/blob/python_code_RFC7811/src/mrt_lowpoint_draft_text.py>. | |||

While this Python code is believed to correctly implement the pseudo- | While this Python code is believed to correctly implement the | |||

code description of the algorithm, in the event of a difference, the | pseudocode description of the algorithm, in the event of a | |||

pseudo-code description should be considered normative. | difference, the pseudocode description should be considered | |||

normative. | ||||

<CODE BEGINS> | <CODE BEGINS> | |||

# This program has been tested to run on Python 2.6 and 2.7 | # This program has been tested to run on Python 2.6 and 2.7 | |||

# (specifically Python 2.6.6 and 2.7.8 were tested). | # (specifically Python 2.6.6 and 2.7.8 were tested). | |||

# The program has known incompatibilities with Python 3.X. | # The program has known incompatibilities with Python 3.X. | |||

# When executed, this program will generate a text file describing | # When executed, this program will generate a text file describing | |||

# an example topology. It then reads that text file back in as input | # an example topology. It then reads that text file back in as input | |||

# to create the example topology, and runs the MRT algorithm.This | # to create the example topology, and runs the MRT Lowpoint algorithm. | |||

# was done to simplify the inclusion of the program as a single text | # This was done to simplify the inclusion of the program as a single | |||

# file that can be extracted from the IETF draft. | # text file that can be extracted from the RFC. | |||

# The output of the program is four text files containing a description | # The output of the program is four text files containing a description | |||

# of the GADAG, the blue and red MRTs for all destinations, and the | # of the GADAG, the blue and MRT-Reds for all destinations, and the | |||

# MRT alternates for all failures. | # MRT alternates for all failures. | |||

import random | import random | |||

import os.path | import os.path | |||

import heapq | import heapq | |||

# simple Class definitions allow structure-like dot notation for | # simple Class definitions allow structure-like dot notation for | |||

# variables and a convenient place to initialize those variables. | # variables and a convenient place to initialize those variables. | |||

class Topology: | class Topology: | |||

def __init__(self): | def __init__(self): | |||

skipping to change at page 72, line 27 ¶ | skipping to change at page 74, line 36 ¶ | |||

nodeb_intf.remote_node = nodea | nodeb_intf.remote_node = nodea | |||

nodea_intf.local_node = nodea | nodea_intf.local_node = nodea | |||

nodeb_intf.local_node = nodeb | nodeb_intf.local_node = nodeb | |||

nodea_intf.link_data = len(nodea.intf_list) | nodea_intf.link_data = len(nodea.intf_list) | |||

nodeb_intf.link_data = len(nodeb.intf_list) | nodeb_intf.link_data = len(nodeb.intf_list) | |||

nodea.intf_list.append(nodea_intf) | nodea.intf_list.append(nodea_intf) | |||

nodeb.intf_list.append(nodeb_intf) | nodeb.intf_list.append(nodeb_intf) | |||

return topo | return topo | |||

def MRT_Island_Identification(topo, computing_rtr, profile_id, area): | def MRT_Island_Identification(topo, computing_rtr, profile_id, area): | |||

if profile_id in computing_rtr.profile_id_list: | if profile_id in computing_rtr.profile_id_list: | |||

computing_rtr.IN_MRT_ISLAND = True | computing_rtr.IN_MRT_ISLAND = True | |||

explore_list = [computing_rtr] | explore_list = [computing_rtr] | |||

else: | else: | |||

return | return | |||

while explore_list != []: | while explore_list != []: | |||

next_rtr = explore_list.pop() | next_rtr = explore_list.pop() | |||

for intf in next_rtr.intf_list: | for intf in next_rtr.intf_list: | |||

if ( (not intf.MRT_INELIGIBLE) | if ( (not intf.IN_MRT_ISLAND) | |||

and (not intf.remote_intf.MRT_INELIGIBLE) | and (not intf.MRT_INELIGIBLE) | |||

and (not intf.IGP_EXCLUDED) and intf.area == area | and (not intf.remote_intf.MRT_INELIGIBLE) | |||

and (profile_id in intf.remote_node.profile_id_list)): | and (not intf.IGP_EXCLUDED) and intf.area == area | |||

and (profile_id in intf.remote_node.profile_id_list)): | ||||

intf.IN_MRT_ISLAND = True | intf.IN_MRT_ISLAND = True | |||

intf.remote_intf.IN_MRT_ISLAND = True | intf.remote_intf.IN_MRT_ISLAND = True | |||

if (not intf.remote_node.IN_MRT_ISLAND): | if (not intf.remote_node.IN_MRT_ISLAND): | |||

intf.remote_node.IN_MRT_ISLAND = True | ||||

intf.remote_INTF.IN_MRT_ISLAND = True | ||||

explore_list.append(intf.remote_node) | explore_list.append(intf.remote_node) | |||

def Compute_Island_Node_List_For_Test_GR(topo, test_gr): | def Compute_Island_Node_List_For_Test_GR(topo, test_gr): | |||

Reset_Computed_Node_and_Intf_Values(topo) | Reset_Computed_Node_and_Intf_Values(topo) | |||

topo.test_gr = topo.node_dict[test_gr] | topo.test_gr = topo.node_dict[test_gr] | |||

MRT_Island_Identification(topo, topo.test_gr, 0, 0) | MRT_Island_Identification(topo, topo.test_gr, 0, 0) | |||

for node in topo.node_list: | for node in topo.node_list: | |||

if node.IN_MRT_ISLAND: | if node.IN_MRT_ISLAND: | |||

topo.island_node_list_for_test_gr.append(node) | topo.island_node_list_for_test_gr.append(node) | |||

skipping to change at page 78, line 42 ¶ | skipping to change at page 81, line 5 ¶ | |||

Copy_List_Items(y.red_next_hops, y.next_hops) | Copy_List_Items(y.red_next_hops, y.next_hops) | |||

if direction == 'NORMAL_SPF': | if direction == 'NORMAL_SPF': | |||

y.primary_spf_metric = y.spf_metric | y.primary_spf_metric = y.spf_metric | |||

Copy_List_Items(y.primary_next_hops, y.next_hops) | Copy_List_Items(y.primary_next_hops, y.next_hops) | |||

if direction == 'MRT_ISLAND_SPF': | if direction == 'MRT_ISLAND_SPF': | |||

Copy_List_Items(y.mrt_island_next_hops, y.next_hops) | Copy_List_Items(y.mrt_island_next_hops, y.next_hops) | |||

if direction == 'COLLAPSED_SPF': | if direction == 'COLLAPSED_SPF': | |||

y.collapsed_metric = y.spf_metric | y.collapsed_metric = y.spf_metric | |||

Copy_List_Items(y.collapsed_next_hops, y.next_hops) | Copy_List_Items(y.collapsed_next_hops, y.next_hops) | |||

# Note that the Python heapq fucntion allows for duplicate items, | # Note that the Python heapq function allows for duplicate items, | |||

# so we use the 'spf_visited' property to only consider a node | # so we use the 'spf_visited' property to only consider a node | |||

# as min_node the first time it gets removed from the heap. | # as min_node the first time it gets removed from the heap. | |||

def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction): | def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction): | |||

spf_heap = [] | spf_heap = [] | |||

for y in topo.island_node_list: | for y in topo.island_node_list: | |||

y.spf_metric = 2147483647 # 2^31-1 | y.spf_metric = 2147483647 # 2^31-1 | |||

y.next_hops = [] | y.next_hops = [] | |||

y.spf_visited = False | y.spf_visited = False | |||

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

heapq.heappush(spf_heap, | heapq.heappush(spf_heap, | |||

skipping to change at page 81, line 14 ¶ | skipping to change at page 83, line 25 ¶ | |||

x.localroot.red_next_hops) | x.localroot.red_next_hops) | |||

elif y.LOWER == True: | elif y.LOWER == True: | |||

Copy_List_Items(y.blue_next_hops, | Copy_List_Items(y.blue_next_hops, | |||

x.localroot.blue_next_hops) | x.localroot.blue_next_hops) | |||

else: | else: | |||

Copy_List_Items(y.blue_next_hops, | Copy_List_Items(y.blue_next_hops, | |||

x.localroot.red_next_hops) | x.localroot.red_next_hops) | |||

Copy_List_Items(y.red_next_hops, | Copy_List_Items(y.red_next_hops, | |||

x.localroot.blue_next_hops) | x.localroot.blue_next_hops) | |||

# Inherit x's MRT next-hops to reach the GADAG root | # Inherit x's MRT next hops to reach the GADAG root | |||

# from x's MRT next-hops to reach its local root, | # from x's MRT next hops to reach its local root, | |||

# but first check if x is the gadag_root (in which case | # but first check if x is the gadag_root (in which case | |||

# x does not have a local root) or if x's local root | # x does not have a local root) or if x's local root | |||

# is the gadag root (in which case we already have the | # is the gadag root (in which case we already have the | |||

# x's MRT next-hops to reach the gadag root) | # x's MRT next hops to reach the gadag root) | |||

if x is not topo.gadag_root and x.localroot is not topo.gadag_root: | if x is not topo.gadag_root and x.localroot is not topo.gadag_root: | |||

Copy_List_Items(topo.gadag_root.blue_next_hops, | Copy_List_Items(topo.gadag_root.blue_next_hops, | |||

x.localroot.blue_next_hops) | x.localroot.blue_next_hops) | |||

Copy_List_Items(topo.gadag_root.red_next_hops, | Copy_List_Items(topo.gadag_root.red_next_hops, | |||

x.localroot.red_next_hops) | x.localroot.red_next_hops) | |||

topo.gadag_root.order_proxy = x.localroot | topo.gadag_root.order_proxy = x.localroot | |||

# Inherit next-hops and order_proxies to other blocks | # Inherit next hops and order_proxies to other blocks | |||

for y in topo.island_node_list: | for y in topo.island_node_list: | |||

if (y is not topo.gadag_root and y is not x ): | if (y is not topo.gadag_root and y is not x ): | |||

Set_Edge(y) | Set_Edge(y) | |||

def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x): | def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x): | |||

for y in topo.island_node_list: | for y in topo.island_node_list: | |||

if y is x: | if y is x: | |||

continue | continue | |||

x.blue_next_hops_dict[y.node_id] = [] | x.blue_next_hops_dict[y.node_id] = [] | |||

x.red_next_hops_dict[y.node_id] = [] | x.red_next_hops_dict[y.node_id] = [] | |||

skipping to change at page 84, line 40 ¶ | skipping to change at page 87, line 4 ¶ | |||

continue | continue | |||

for failed_intf in D.primary_next_hops: | for failed_intf in D.primary_next_hops: | |||

alt = Alternate() | alt = Alternate() | |||

alt.failed_intf = failed_intf | alt.failed_intf = failed_intf | |||

cand_alt_list = [] | cand_alt_list = [] | |||

F = failed_intf.remote_node | F = failed_intf.remote_node | |||

#We need to test if F is in the island, as opposed | #We need to test if F is in the island, as opposed | |||

#to just testing if failed_intf is in island_intf_list, | #to just testing if failed_intf is in island_intf_list, | |||

#because failed_intf could be marked as MRT_INELIGIBLE. | #because failed_intf could be marked as MRT_INELIGIBLE. | |||

if F in topo.island_node_list: | if F in topo.island_node_list: | |||

alt.info = Select_Alternates(D, F, failed_intf) | alt.info = Select_Alternates(D, F, failed_intf) | |||

else: | else: | |||

#The primary next-hop is not in the MRT Island. | #The primary next hop is not in the MRT Island. | |||

#Either red or blue will avoid the primary next-hop, | #Either red or blue will avoid the primary next hop, | |||

#because the primary next-hop is not even in the | #because the primary next hop is not even in the | |||

#GADAG. | #GADAG. | |||

alt.info = 'USE_RED_OR_BLUE' | alt.info = 'USE_RED_OR_BLUE' | |||

if (alt.info == 'USE_RED_OR_BLUE'): | if (alt.info == 'USE_RED_OR_BLUE'): | |||

alt.red_or_blue = random.choice(['USE_RED','USE_BLUE']) | alt.red_or_blue = random.choice(['USE_RED','USE_BLUE']) | |||

if (alt.info == 'USE_BLUE' | if (alt.info == 'USE_BLUE' | |||

or alt.red_or_blue == 'USE_BLUE'): | or alt.red_or_blue == 'USE_BLUE'): | |||

Copy_List_Items(alt.nh_list, D.blue_next_hops) | Copy_List_Items(alt.nh_list, D.blue_next_hops) | |||

alt.fec = 'BLUE' | alt.fec = 'BLUE' | |||

alt.prot = 'NODE_PROTECTION' | alt.prot = 'NODE_PROTECTION' | |||

if (alt.info == 'USE_RED' or alt.red_or_blue == 'USE_RED'): | if (alt.info == 'USE_RED' or alt.red_or_blue == 'USE_RED'): | |||

Copy_List_Items(alt.nh_list, D.red_next_hops) | Copy_List_Items(alt.nh_list, D.red_next_hops) | |||

alt.fec = 'RED' | alt.fec = 'RED' | |||

alt.prot = 'NODE_PROTECTION' | alt.prot = 'NODE_PROTECTION' | |||

if (alt.info == 'PRIM_NH_IN_DIFFERENT_BLOCK'): | if (alt.info == 'PRIM_NH_IN_DIFFERENT_BLOCK'): | |||

alt.fec = 'NO_ALTERNATE' | alt.fec = 'NO_ALTERNATE' | |||

alt.prot = 'NO_PROTECTION' | alt.prot = 'NO_PROTECTION' | |||

skipping to change at page 96, line 31 ¶ | skipping to change at page 98, line 46 ¶ | |||

Copy_List_Items(P.blue_next_hops, X.red_next_hops) | Copy_List_Items(P.blue_next_hops, X.red_next_hops) | |||

Copy_List_Items(P.red_next_hops, Y.blue_next_hops) | Copy_List_Items(P.red_next_hops, Y.blue_next_hops) | |||

return | return | |||

assert(False) | assert(False) | |||

def Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,S): | def Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,S): | |||

for prefix in topo.named_proxy_dict: | for prefix in topo.named_proxy_dict: | |||

P = topo.named_proxy_dict[prefix] | P = topo.named_proxy_dict[prefix] | |||

if P.pnar2 == None: | if P.pnar2 == None: | |||

if S is P.pnar1.node: | if S is P.pnar1.node: | |||

# set the MRT next-hops for the PNAR to | # set the MRT next hops for the PNAR to | |||

# reach the LFIN and change FEC to green | # reach the LFIN and change FEC to green | |||

Copy_List_Items(P.blue_next_hops, | Copy_List_Items(P.blue_next_hops, | |||

P.pnar1.nh_intf_list) | P.pnar1.nh_intf_list) | |||

S.blue_to_green_nh_dict[P.node_id] = True | S.blue_to_green_nh_dict[P.node_id] = True | |||

Copy_List_Items(P.red_next_hops, | Copy_List_Items(P.red_next_hops, | |||

P.pnar1.nh_intf_list) | P.pnar1.nh_intf_list) | |||

S.red_to_green_nh_dict[P.node_id] = True | S.red_to_green_nh_dict[P.node_id] = True | |||

else: | else: | |||

# inherit MRT NHs for P from pnar1 | # inherit MRT NHs for P from pnar1 | |||

Copy_List_Items(P.blue_next_hops, | Copy_List_Items(P.blue_next_hops, | |||

P.pnar1.node.blue_next_hops) | P.pnar1.node.blue_next_hops) | |||

Copy_List_Items(P.red_next_hops, | Copy_List_Items(P.red_next_hops, | |||

P.pnar1.node.red_next_hops) | P.pnar1.node.red_next_hops) | |||

else: | else: | |||

Select_Proxy_Node_NHs(P,S) | Select_Proxy_Node_NHs(P,S) | |||

# set the MRT next-hops for the PNAR to reach the LFIN | # set the MRT next hops for the PNAR to reach the LFIN | |||

# and change FEC to green rely on the red or blue | # and change FEC to green rely on the red or blue | |||

# next-hops being empty to figure out which one needs | # next hops being empty to figure out which one needs | |||

# to point to the LFIN. | # to point to the LFIN. | |||

if S is P.pnar1.node: | if S is P.pnar1.node: | |||

this_pnar = P.pnar1 | this_pnar = P.pnar1 | |||

elif S is P.pnar2.node: | elif S is P.pnar2.node: | |||

this_pnar = P.pnar2 | this_pnar = P.pnar2 | |||

else: | else: | |||

continue | continue | |||

if P.blue_next_hops == []: | if P.blue_next_hops == []: | |||

Copy_List_Items(P.blue_next_hops, | Copy_List_Items(P.blue_next_hops, | |||

this_pnar.nh_intf_list) | this_pnar.nh_intf_list) | |||

S.blue_to_green_nh_dict[P.node_id] = True | S.blue_to_green_nh_dict[P.node_id] = True | |||

if P.red_next_hops == []: | if P.red_next_hops == []: | |||

skipping to change at page 104, line 4 ¶ | skipping to change at page 106, line 20 ¶ | |||

(intf.remote_node is | (intf.remote_node is | |||

failed_intf.remote_node)): | failed_intf.remote_node)): | |||

if intf.metric < min_metric: | if intf.metric < min_metric: | |||

cand_alt_list = [intf] | cand_alt_list = [intf] | |||

min_metric = intf.metric | min_metric = intf.metric | |||

elif intf.metric == min_metric: | elif intf.metric == min_metric: | |||

cand_alt_list.append(intf) | cand_alt_list.append(intf) | |||

if cand_alt_list != [None]: | if cand_alt_list != [None]: | |||

alt.fec = 'GREEN' | alt.fec = 'GREEN' | |||

alt.prot = 'PARALLEL_CUTLINK' | alt.prot = 'PARALLEL_CUTLINK' | |||

else: | else: | |||

alt.fec = 'NO_ALTERNATE' | alt.fec = 'NO_ALTERNATE' | |||

alt.prot = 'NO_PROTECTION' | alt.prot = 'NO_PROTECTION' | |||

Copy_List_Items(alt.nh_list, cand_alt_list) | Copy_List_Items(alt.nh_list, cand_alt_list) | |||

else: | else: | |||

# set Z as the node to inherit blue next-hops from | # set Z as the node to inherit blue next hops from | |||

if alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D': | if alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D': | |||

Z = P.pnar1.node | Z = P.pnar1.node | |||

else: | else: | |||

Z = P | Z = P | |||

if failed_intf in Z.red_next_hops: | if failed_intf in Z.red_next_hops: | |||

Copy_List_Items(alt.nh_list, Z.blue_next_hops) | Copy_List_Items(alt.nh_list, Z.blue_next_hops) | |||

alt.fec = 'BLUE' | alt.fec = 'BLUE' | |||

alt.prot = 'LINK_PROTECTION' | alt.prot = 'LINK_PROTECTION' | |||

else: | else: | |||

assert(failed_intf in Z.blue_next_hops) | assert(failed_intf in Z.blue_next_hops) | |||

skipping to change at page 108, line 20 ¶ | skipping to change at page 110, line 40 ¶ | |||

Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) | Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) | |||

Run_MRT_for_All_Sources(topo) | Run_MRT_for_All_Sources(topo) | |||

Write_Output_To_Files(topo, res_file_base) | Write_Output_To_Files(topo, res_file_base) | |||

Generate_Basic_Topology_and_Run_MRT() | Generate_Basic_Topology_and_Run_MRT() | |||

Generate_Complex_Topology_and_Run_MRT() | Generate_Complex_Topology_and_Run_MRT() | |||

<CODE ENDS> | <CODE ENDS> | |||

Appendix B. Constructing a GADAG using SPFs | Appendix B. Constructing a GADAG Using SPFs | |||

The basic idea in this method for constructing a GADAG is to use | The basic idea in this method for constructing a GADAG is to use | |||

slightly-modified SPF computations to find ears. In every block, an | slightly modified SPF computations to find ears. In every block, an | |||

SPF computation is first done to find a cycle from the local root and | SPF computation is first done to find a cycle from the local root and | |||

then SPF computations in that block find ears until there are no more | then SPF computations in that block find ears until there are no more | |||

interfaces to be explored. The used result from the SPF computation | interfaces to be explored. The used result from the SPF computation | |||

is the path of interfaces indicated by following the previous hops | is the path of interfaces indicated by following the previous hops | |||

from the mininized IN_GADAG node back to the SPF root. | from the minimized IN_GADAG node back to the SPF root. | |||

To do this, first all cut-vertices must be identified and local-roots | To do this, first all cut-vertices must be identified and localroots | |||

assigned as specified in Figure 12. | assigned as specified in Figure 12. | |||

The slight modifications to the SPF are as follows. The root of the | The slight modifications to the SPF are as follows. The root of the | |||

block is referred to as the block-root; it is either the GADAG root | block is referred to as the block-root; it is either the GADAG root | |||

or a cut-vertex. | or a cut-vertex. | |||

a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All | a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All | |||

links between y and x are marked as TEMP_UNUSABLE. They should | links between y and x are marked as TEMP_UNUSABLE. They should | |||

not be used during the SPF computation. | not be used during the SPF computation. | |||

b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It | b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It | |||

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 localroot 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 110, line 4 ¶ | skipping to change at page 112, line 23 ¶ | |||

y = end_ear.spf_prev_hop | y = end_ear.spf_prev_hop | |||

while y.local_node is not spf_root | while y.local_node is not spf_root | |||

add_to_list_start(ear_list, y) | add_to_list_start(ear_list, y) | |||

y.local_node.IN_GADAG = true | y.local_node.IN_GADAG = true | |||

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

if(method is not hybrid) | if(method is not hybrid) | |||

Set_Ear_Direction(ear_list, cand_intf.local_node, | Set_Ear_Direction(ear_list, cand_intf.local_node, | |||

end_ear,block_root) | end_ear,block_root) | |||

Clear TEMP_UNUSABLE from all interfaces between | Clear TEMP_UNUSABLE from all interfaces between | |||

cand_intf.remote_node and cand_intf.local_node | cand_intf.remote_node and cand_intf.local_node | |||

Clear TEMP_UNUSABLE from cand_intf.local_node | Clear TEMP_UNUSABLE from cand_intf.local_node | |||

return end_ear | return end_ear | |||

Figure 31: Modified SPF for GADAG construction | Figure 31: Modified SPF for GADAG Construction | |||

Assume that an ear is found by going from y to x and then running an | Assume that an ear is found by going from y to x and then running an | |||

SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is | SPF that terminates by minimizing z (e.g., y<->x...q<->z). Now it is | |||

necessary to determine the direction of the ear; if y << z, then the | necessary to determine the direction of the ear; if y<<z, then the | |||

path should be y->x...q->z but if y >> z, then the path should be y<- | path should be y->x...q->z; but if y>>z, then the path should be | |||

x...q<-z. In Section 5.5, the same problem was handled by finding | y<-x...q<-z. In Section 5.5, the same problem was handled by finding | |||

all ears that started at a node before looking at ears starting at | all ears that started at a node before looking at ears starting at | |||

nodes higher in the partial order. In this GADAG construction | nodes higher in the partial order. In this GADAG construction | |||

method, using that approach could mean that new ears aren't added in | method, using that approach could mean that new ears aren't added in | |||

order of their total cost since all ears connected to a node would | order of their total cost since all ears connected to a node would | |||

need to be found before additional nodes could be found. | need to 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 111, line 48 ¶ | skipping to change at page 113, line 48 ¶ | |||

add i.local_node to x.Higher_Nodes | add i.local_node to x.Higher_Nodes | |||

else | else | |||

foreach node x where x.localroot is block_root | foreach node x where x.localroot is block_root | |||

if end_b is in x.Lower_Nodes | if end_b is in x.Lower_Nodes | |||

foreach interface i in ear_list | foreach interface i in ear_list | |||

add i.local_node to x.Lower_Nodes | add i.local_node to x.Lower_Nodes | |||

if end_a is in x.Higher_Nodes | if end_a is in x.Higher_Nodes | |||

foreach interface i in ear_list | foreach interface i in ear_list | |||

add i.remote_node to x.Higher_Nodes | add i.remote_node to x.Higher_Nodes | |||

Figure 32: Algorithm to assign links of an ear direction | Figure 32: Algorithm to Assign Links of an Ear Direction | |||

A goal of this GADAG construction method is to find the shortest | A goal of this GADAG construction method is to find the shortest | |||

cycles and ears. An ear is started by going to a neighbor x of an | cycles and ears. An ear is started by going to a neighbor x of an | |||

IN_GADAG node y. The path from x to an IN_GADAG node is minimal, | IN_GADAG node y. The path from x to an IN_GADAG node is minimal, | |||

since it is computed via SPF. Since a shortest path is made of | since it is computed via SPF. Since a shortest path is made of | |||

shortest paths, to find the shortest ears requires reaching from the | shortest paths, to find the shortest ears requires reaching from the | |||

set of IN_GADAG nodes to the closest node that isn't IN_GADAG. | set of IN_GADAG nodes to the closest node that isn't IN_GADAG. | |||

Therefore, an ordered tree is maintained of interfaces that could be | Therefore, an ordered tree is maintained of interfaces that could be | |||

explored from the IN_GADAG nodes. The interfaces are ordered by | explored from the IN_GADAG nodes. The interfaces are ordered by | |||

their characteristics of metric, local loopback address, remote | their characteristics of metric, local loopback address, remote | |||

loopback address, and ifindex, based on the Interface_Compare | loopback address, and ifindex, based on the Interface_Compare | |||

function defined in Figure 14. | function defined in Figure 14. | |||

This GADAG construction method ignores interfaces picked from the | This GADAG construction method ignores interfaces picked from the | |||

ordered list that belong to the block root if the block in which the | ordered list that belong to the block root if the block in which the | |||

interface is present already has an ear that has been computed. This | interface is present already has an ear that has been computed. This | |||

is necessary since we allow at most one incoming interface to a block | is necessary since we allow at most one incoming interface to a block | |||

root in each block. This requirement stems from the way next-hops | root in each block. This requirement stems from the way next hops | |||

are computed as was seen in Section 5.7. After any ear gets | are computed as was seen in Section 5.7. After any ear gets | |||

computed, we traverse the newly added nodes to the GADAG and insert | computed, we traverse the newly added nodes to the GADAG and insert | |||

interfaces whose far end is not yet on the GADAG to the ordered tree | interfaces whose far end is not yet on the GADAG to the ordered tree | |||

for later processing. | for later processing. | |||

Finally, cut-links are a special case because there is no point in | Finally, cut-links are a special case because there is no point in | |||

doing an SPF on a block of 2 nodes. The algorithm identifies cut- | doing an SPF on a block of two nodes. The algorithm identifies cut- | |||

links simply as links where both ends of the link are cut-vertices. | links simply as links where both ends of the link are cut-vertices. | |||

Cut-links can simply be added to the GADAG with both OUTGOING and | Cut-links can simply be added to the GADAG with both OUTGOING and | |||

INCOMING specified on their interfaces. | INCOMING specified on their interfaces. | |||

add_eligible_interfaces_of_node(ordered_intfs_tree,node) | add_eligible_interfaces_of_node(ordered_intfs_tree,node) | |||

for each interface of node | for each interface of node | |||

if intf.remote_node.IN_GADAG is false | if intf.remote_node.IN_GADAG is false | |||

insert(intf,ordered_intfs_tree) | insert(intf,ordered_intfs_tree) | |||

check_if_block_has_ear(x,block_id) | check_if_block_has_ear(x,block_id) | |||

skipping to change at page 113, line 32 ¶ | skipping to change at page 115, line 32 ¶ | |||

ear_end = SPF_for_Ear(cand_intf.local_node, | ear_end = SPF_for_Ear(cand_intf.local_node, | |||

cand_intf.remote_node, | cand_intf.remote_node, | |||

cand_intf.remote_node.localroot, | cand_intf.remote_node.localroot, | |||

SPF method) | SPF method) | |||

y = ear_end.spf_prev_hop | y = ear_end.spf_prev_hop | |||

while y.local_node is not cand_intf.local_node | while y.local_node is not cand_intf.local_node | |||

add_eligible_interfaces_of_node( | add_eligible_interfaces_of_node( | |||

ordered_intfs_tree, y.local_node) | ordered_intfs_tree, y.local_node) | |||

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

Figure 33: SPF-based method for GADAG construction | Figure 33: SPF-Based Method for GADAG Construction | |||

Appendix C. Constructing a GADAG using a hybrid method | Appendix C. Constructing a GADAG Using a Hybrid Method | |||

The idea of this method is to combine the salient features of the | The idea of this method is to combine the salient features of the | |||

lowpoint inheritance and SPF methods. To this end, we process nodes | lowpoint inheritance and SPF methods. To this end, we process nodes | |||

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

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

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

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

processed towards the end of the ear. To compute the ear however, we | processed towards the end of the ear. To compute the ear however, we | |||

resort to an SPF to have the possibility of better ears (path | resort to an SPF to have the possibility of better ears (path | |||

lentghs) thus giving more flexibility than the restricted use of | lengths) thus giving more flexibility than the restricted use of | |||

lowpoint/dfs parents. | 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 predetermined. Thus, whenever the block already has an | |||

ear computed, and we are processing an interface of the block root, | ear computed, and we are processing an interface of the block root, | |||

we mark the block root as unusable before the SPF run that computes | we mark the block root as unusable before the SPF run that computes | |||

the ear. This ensures that the SPF terminates at some node other | the ear. This ensures that the SPF terminates at some node other | |||

than the block-root. This in turn guarantees that the block-root has | than the block-root. This in turn guarantees that the block-root has | |||

only one incoming interface in each block, which is necessary for | only one incoming interface in each block, which is necessary for | |||

correctly computing the next-hops on the GADAG. | correctly computing the next hops on the GADAG. | |||

As in the SPF gadag, bridge ears are handled as a special case. | As in the SPF GADAG, bridge ears are handled as a special case. | |||

The entire algorithm is shown below in Figure 34 | The entire algorithm is shown below in Figure 34. | |||

find_spf_stack_ear(stack, x, y, xy_intf, block_root) | find_spf_stack_ear(stack, x, y, xy_intf, block_root) | |||

if L(y) == D(y) | if L(y) == D(y) | |||

// Special case for cut-links | // Special case for cut-links | |||

xy_intf.UNDIRECTED = false | xy_intf.UNDIRECTED = false | |||

xy_intf.remote_intf.UNDIRECTED = false | xy_intf.remote_intf.UNDIRECTED = false | |||

xy_intf.OUTGOING = true | xy_intf.OUTGOING = true | |||

xy_intf.INCOMING = true | xy_intf.INCOMING = true | |||

xy_intf.remote_intf.OUTGOING = true | xy_intf.remote_intf.OUTGOING = true | |||

xy_intf.remote_intf.INCOMING = true | xy_intf.remote_intf.INCOMING = true | |||

skipping to change at page 115, line 16 ¶ | skipping to change at page 117, line 18 ¶ | |||

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

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

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

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

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

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

y = intf.remote_node | y = intf.remote_node | |||

if y.IN_GADAG is false | if y.IN_GADAG is false | |||

find_spf_stack_ear(stack, x, y, intf, y.block_root) | find_spf_stack_ear(stack, x, y, intf, y.block_root) | |||

Figure 34: Hybrid GADAG construction method | Figure 34: Hybrid GADAG Construction Method | |||

Acknowledgements | ||||

The authors would like to thank Shraddha Hegde, Eric Wu, Janos | ||||

Farkas, Stewart Bryant, Alvaro Retana, and Deccan (Shaofu Peng) for | ||||

their suggestions and review. We would also like to thank Anil Kumar | ||||

SN for his assistance in clarifying the algorithm description and | ||||

pseudocode. | ||||

Authors' Addresses | Authors' Addresses | |||

Gabor Sandor Enyedi | Gabor Sandor Enyedi | |||

Ericsson | Ericsson | |||

Konyves Kalman krt 11 | Konyves Kalman krt 11 | |||

Budapest 1097 | Budapest 1097 | |||

Hungary | Hungary | |||

Email: Gabor.Sandor.Enyedi@ericsson.com | Email: Gabor.Sandor.Enyedi@ericsson.com | |||

skipping to change at page 115, line 40 ¶ | skipping to change at page 118, line 27 ¶ | |||

Konyves Kalman krt 11 | Konyves Kalman krt 11 | |||

Budapest 1097 | Budapest 1097 | |||

Hungary | Hungary | |||

Email: Andras.Csaszar@ericsson.com | Email: Andras.Csaszar@ericsson.com | |||

Alia Atlas | Alia Atlas | |||

Juniper Networks | Juniper Networks | |||

10 Technology Park Drive | 10 Technology Park Drive | |||

Westford, MA 01886 | Westford, MA 01886 | |||

USA | United States | |||

Email: akatlas@juniper.net | Email: akatlas@juniper.net | |||

Chris Bowers | Chris Bowers | |||

Juniper Networks | Juniper Networks | |||

1194 N. Mathilda Ave. | 1194 N. Mathilda Ave. | |||

Sunnyvale, CA 94089 | Sunnyvale, CA 94089 | |||

USA | United States | |||

Email: cbowers@juniper.net | Email: cbowers@juniper.net | |||

Abishek Gopalan | Abishek Gopalan | |||

University of Arizona | University of Arizona | |||

1230 E Speedway Blvd. | 1230 E Speedway Blvd. | |||

Tucson, AZ 85721 | Tucson, AZ 85721 | |||

USA | United States | |||

Email: abishek@ece.arizona.edu | Email: abishek@ece.arizona.edu | |||

End of changes. 343 change blocks. | ||||

860 lines changed or deleted | | 840 lines changed or added | ||

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