draft-ietf-rtgwg-rlfa-node-protection-09.txt | draft-ietf-rtgwg-rlfa-node-protection-10.txt | |||
---|---|---|---|---|

Routing Area Working Group P. Sarkar, Ed. | Routing Area Working Group P. Sarkar, Ed. | |||

Internet-Draft Individual Contributor | Internet-Draft Individual Contributor | |||

Intended status: Standards Track S. Hegde | Intended status: Standards Track S. Hegde | |||

Expires: June 26, 2017 C. Bowers | Expires: July 3, 2017 C. Bowers | |||

Juniper Networks, Inc. | Juniper Networks, Inc. | |||

H. Gredler | H. Gredler | |||

RtBrick, Inc. | RtBrick, Inc. | |||

S. Litkowski | S. Litkowski | |||

Orange | Orange | |||

December 23, 2016 | December 30, 2016 | |||

Remote-LFA Node Protection and Manageability | Remote-LFA Node Protection and Manageability | |||

draft-ietf-rtgwg-rlfa-node-protection-09 | draft-ietf-rtgwg-rlfa-node-protection-10 | |||

Abstract | Abstract | |||

The loop-free alternates computed following the current Remote-LFA | The loop-free alternates computed following the current Remote-LFA | |||

specification guarantees only link-protection. The resulting Remote- | specification guarantees only link-protection. The resulting Remote- | |||

LFA nexthops (also called PQ-nodes), may not guarantee node- | LFA nexthops (also called PQ-nodes), may not guarantee node- | |||

protection for all destinations being protected by it. | protection for all destinations being protected by it. | |||

This document describes an extension to the Remote Loop-Free based IP | This document describes an extension to the Remote Loop-Free based IP | |||

fast reroute mechanisms described in [RFC7490], that describes | fast reroute mechanisms described in [RFC7490], that describes | |||

procedures for determining if a given PQ-node provides node- | procedures for determining if a given PQ-node provides node- | |||

protection for a specific destination or not. The document also | protection for a specific destination or not. The document also | |||

shows how the same procedure can be utilised for collection of | shows how the same procedure can be uitilized for collection of | |||

complete characteristics for alternate paths. Knowledge about the | complete characteristics for alternate paths. Knowledge about the | |||

characteristics of all alternate path is precursory to apply operator | characteristics of all alternate path is precursory to apply operator | |||

defined policy for eliminating paths not fitting constraints. | defined policy for eliminating paths not fitting constraints. | |||

Requirements Language | 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 [RFC2119]. | document are to be interpreted as described in RFC2119 [RFC2119]. | |||

skipping to change at page 2, line 10 ¶ | skipping to change at page 2, line 10 ¶ | |||

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

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

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

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

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

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

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

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

This Internet-Draft will expire on June 26, 2017. | This Internet-Draft will expire on July 3, 2017. | |||

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 50 ¶ | skipping to change at page 2, line 50 ¶ | |||

2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 7 | 2.2.6.2. Node-Protecting Extended P-Space . . . . . . . . 7 | |||

2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 8 | 2.2.6.3. Q-Space . . . . . . . . . . . . . . . . . . . . . 8 | |||

2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9 | 2.3. Computing Node-protecting R-LFA Path . . . . . . . . . . 9 | |||

2.3.1. Computing Candidate Node-protecting PQ-Nodes for | 2.3.1. Computing Candidate Node-protecting PQ-Nodes for | |||

Primary nexthops . . . . . . . . . . . . . . . . . . 9 | Primary nexthops . . . . . . . . . . . . . . . . . . 9 | |||

2.3.2. Computing node-protecting paths from PQ-nodes to | 2.3.2. Computing node-protecting paths from PQ-nodes to | |||

destinations . . . . . . . . . . . . . . . . . . . . 11 | destinations . . . . . . . . . . . . . . . . . . . . 11 | |||

2.3.3. Computing Node-Protecting R-LFA Paths for | 2.3.3. Computing Node-Protecting R-LFA Paths for | |||

Destinations with ECMP primary nexthop nodes . . . . 13 | Destinations with ECMP primary nexthop nodes . . . . 13 | |||

2.3.4. Limiting extra computational overhead . . . . . . . . 17 | 2.3.4. Limiting extra computational overhead . . . . . . . . 17 | |||

3. Manageabilty of Remote-LFA Alternate Paths . . . . . . . . . 18 | 3. Manageability of Remote-LFA Alternate Paths . . . . . . . . . 18 | |||

3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 | 3.1. The Problem . . . . . . . . . . . . . . . . . . . . . . . 18 | |||

3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 18 | 3.2. The Solution . . . . . . . . . . . . . . . . . . . . . . 18 | |||

4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 | 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 | |||

5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 | 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 | |||

6. Security Considerations . . . . . . . . . . . . . . . . . . . 19 | 6. Security Considerations . . . . . . . . . . . . . . . . . . . 19 | |||

7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 | 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 | |||

7.1. Normative References . . . . . . . . . . . . . . . . . . 19 | 7.1. Normative References . . . . . . . . . . . . . . . . . . 19 | |||

7.2. Informative References . . . . . . . . . . . . . . . . . 20 | 7.2. Informative References . . . . . . . . . . . . . . . . . 20 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 | |||

skipping to change at page 5, line 50 ¶ | skipping to change at page 5, line 50 ¶ | |||

Table 2: Remote-LFA backup paths via PQ-node R3 | Table 2: Remote-LFA backup paths via PQ-node R3 | |||

Again a closer look at Table 2 shows that, unlike Table 1, where the | Again a closer look at Table 2 shows that, unlike Table 1, where the | |||

single PQ-node R2 provided node-protection for destinations R3 and | single PQ-node R2 provided node-protection for destinations R3 and | |||

D2, if we choose R3 as the R-LFA nexthop, it does not provide node- | D2, if we choose R3 as the R-LFA nexthop, it does not provide node- | |||

protection for R3 and D2 anymore. If S chooses R3 as the R-LFA | protection for R3 and D2 anymore. If S chooses R3 as the R-LFA | |||

nexthop, in the event of the node-failure on primary nexthop E, on | nexthop, in the event of the node-failure on primary nexthop E, on | |||

the alternate path from S to R-LFA nexthop R3, one of parallel ECMP | the alternate path from S to R-LFA nexthop R3, one of parallel ECMP | |||

path between N and R3 also becomes unavailable. So for a Remote-LFA | path between N and R3 also becomes unavailable. So for a Remote-LFA | |||

nexthop to provide node-protection for a given destination, it is | nexthop to provide node-protection for a given destination, it is | |||

also mandatory that, the shortest path from S to the chosen PQ-node | also mandatory that, the shortest paths from S to the chosen PQ-node | |||

MUST NOT traverse the primary nexthop node. | MUST NOT traverse the primary nexthop node. | |||

2.2. Additional Definitions | 2.2. Additional Definitions | |||

This document adds and enhances the following definitions extending | This document adds and enhances the following definitions extending | |||

the ones mentioned in Remote-LFA [RFC7490] specification. | the ones mentioned in Remote-LFA [RFC7490] specification. | |||

2.2.1. Link-Protecting Extended P-Space | 2.2.1. Link-Protecting Extended P-Space | |||

The Remote-LFA [RFC7490] specification already defines this. The | The Remote-LFA [RFC7490] specification already defines this. The | |||

link-protecting extended P-space for a link S-E being protected is | link-protecting extended P-space for a link S-E being protected is | |||

the set of routers that are reachable from one or more direct | the set of routers that are reachable from one or more direct | |||

neighbors of S, except primary node E, without traversing the S-E | neighbors of S, except primary node E, without traversing the S-E | |||

link on any of the shortest path from the direct neighbor to the | link on any of the shortest paths from the direct neighbor to the | |||

router. This MUST exclude any direct neighbor for which there is at | router. This MUST exclude any direct neighbor for which there is at | |||

least one ECMP path from the direct neighbor traversing the link(S-E) | least one ECMP path from the direct neighbor traversing the link(S-E) | |||

being protected. | being protected. | |||

For a cost-based definition for Link-protecting Extended P-Space | For a cost-based definition for Link-protecting Extended P-Space | |||

refer to Section 2.2.6.1. | refer to Section 2.2.6.1. | |||

2.2.2. Node-Protecting Extended P-Space | 2.2.2. Node-Protecting Extended P-Space | |||

The node-protecting extended P-space for a primary nexthop node E | The node-protecting extended P-space for a primary nexthop node E | |||

skipping to change at page 6, line 39 ¶ | skipping to change at page 6, line 39 ¶ | |||

the node E. This MUST exclude any direct neighbors for which there | the node E. This MUST exclude any direct neighbors for which there | |||

is at least one ECMP path from the direct neighbor traversing the | is at least one ECMP path from the direct neighbor traversing the | |||

node E being protected. | node E being protected. | |||

For a cost-based definition for Node-protecting Extended P-Space | For a cost-based definition for Node-protecting Extended P-Space | |||

refer to Section 2.2.6.2. | refer to Section 2.2.6.2. | |||

2.2.3. Q-Space | 2.2.3. Q-Space | |||

The Remote-LFA [RFC7490] draft already defines this. The Q-space for | The Remote-LFA [RFC7490] draft already defines this. The Q-space for | |||

a link S-E being protected is the set of routers that can reach | a link S-E being protected is the set of nodes that can reach primary | |||

primary node E, without traversing the S-E link on any of the | node E, without traversing the S-E link on any of the shortest paths | |||

shortest path from the node Y to primary nexthop E. This MUST | from the node itself to primary nexthop E. This MUST exclude any | |||

exclude any destination for which there is at least one ECMP path | node for which there is at least one ECMP path from the node to the | |||

from the node Y to the primary nexthop E traversing the link(S-E) | primary nexthop E traversing the link(S-E) being protected. | |||

being protected. | ||||

For a cost-based definition for Q-Space refer to Section 2.2.6.3. | For a cost-based definition for Q-Space refer to Section 2.2.6.3. | |||

2.2.4. Link-Protecting PQ Space | 2.2.4. Link-Protecting PQ Space | |||

A node Y is in link-protecting PQ space w.r.t to the link (S-E) being | A node Y is in link-protecting PQ space w.r.t the link (S-E) being | |||

protected, if and only if, Y is present in both link-protecting | protected, if and only if, Y is present in both link-protecting | |||

extended P-space and the Q-space for the link being protected. | extended P-space and the Q-space for the link being protected. | |||

2.2.5. Candidate Node-Protecting PQ Space | 2.2.5. Candidate Node-Protecting PQ Space | |||

A node Y is in candidate node-protecting PQ space w.r.t to the node | A node Y is in candidate node-protecting PQ space w.r.t the node (E) | |||

(E) being protected, if and only if, Y is present in both node- | being protected, if and only if, Y is present in both node-protecting | |||

protecting extended P-space and the Q-space for the link being | extended P-space and the Q-space for the link being protected. | |||

protected. | ||||

Please note, that a node Y being in candidate node-protecting PQ- | Please note, that a node Y being in candidate node-protecting PQ- | |||

space, does not guarantee that the R-LFA alternate path via the same, | space, does not guarantee that the R-LFA alternate path via the same, | |||

in entirety, is unaffected in the event of a node failure of primary | in entirety, is unaffected in the event of a node failure of primary | |||

nexthop node E. It only guarantees that the path segment from S to | nexthop node E. It only guarantees that the path segment from S to | |||

PQ-node Y is unaffected by the same failure event. The PQ-nodes in | PQ-node Y is unaffected by the same failure event. The PQ-nodes in | |||

the candidate node-protecting PQ space may provide node protection | the candidate node-protecting PQ space may provide node protection | |||

for only a subset of destinations that are reachable through the | for only a subset of destinations that are reachable through the | |||

corresponding primary link. | corresponding primary link. | |||

2.2.6. Cost-Based Definitions | 2.2.6. Cost-Based Definitions | |||

This section provides cost-based definitions for some of the terms | This section provides cost-based definitions for some of the terms | |||

introduced in Section 2.2 of this document. | introduced in Section 2.2 of this document. | |||

2.2.6.1. Link-Protecting Extended P-Space | 2.2.6.1. Link-Protecting Extended P-Space | |||

Please refer to Section 2.2.1 for a formal definition for Link- | Please refer to Section 2.2.1 for a formal definition for Link- | |||

protecting Extended P-Space. | protecting Extended P-Space. | |||

A node Y is in link-protecting extended P-space w.r.t to the link | A node Y is in link-protecting extended P-space w.r.t the link (S-E) | |||

(S-E) being protected, if and only if, there exists at least one | being protected, if and only if, there exists at least one direct | |||

direct neighbor of S, Ni, other than primary nexthop E, that | neighbor of S, Ni, other than primary nexthop E, that satisfies the | |||

satisfies the following condition. | following condition. | |||

D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) | D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y) | |||

Where, | Where, | |||

D_opt(A,B) : Distance on most optimum path from A to B. | D_opt(A,B) : Distance on most optimum path from A to B. | |||

Ni : A direct neighbor of S other than primary | Ni : A direct neighbor of S other than primary | |||

nexthop E. | nexthop E. | |||

Y : The node being evaluated for link-protecting | Y : The node being evaluated for link-protecting | |||

extended P-Space. | extended P-Space. | |||

Figure 3: Link-Protecting Ext-P-Space Condition | Figure 3: Link-Protecting Ext-P-Space Condition | |||

2.2.6.2. Node-Protecting Extended P-Space | 2.2.6.2. Node-Protecting Extended P-Space | |||

Please refer to Section 2.2.2 for a formal definition for Node- | Please refer to Section 2.2.2 for a formal definition for Node- | |||

protecting Extended P-Space. | protecting Extended P-Space. | |||

A node Y is in node-protecting extended P-space w.r.t to the node E | A node Y is in node-protecting extended P-space w.r.t the node E | |||

being protected, if and only if, there exists at least one direct | being protected, if and only if, there exists at least one direct | |||

neighbor of S, Ni, other than primary nexthop E, that satisfies the | neighbor of S, Ni, other than primary nexthop E, that satisfies the | |||

following condition. | following condition. | |||

D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) | D_opt(Ni,Y) < D_opt(Ni,E) + D_opt(E,Y) | |||

Where, | Where, | |||

D_opt(A,B) : Distance on most optimum path from A to B. | D_opt(A,B) : Distance on most optimum path from A to B. | |||

E : The primary nexthop on shortest path from S | E : The primary nexthop on shortest path from S | |||

to destination. | to destination. | |||

skipping to change at page 8, line 34 ¶ | skipping to change at page 8, line 34 ¶ | |||

only guarantees that the R-LFA alternate path segment from S via | only guarantees that the R-LFA alternate path segment from S via | |||

direct neighbor Ni to the node Y is not affected in the event of a | direct neighbor Ni to the node Y is not affected in the event of a | |||

node failure of E. It does not yet guarantee that the path segment | node failure of E. It does not yet guarantee that the path segment | |||

from node Y to the destination is also unaffected by the same failure | from node Y to the destination is also unaffected by the same failure | |||

event. | event. | |||

2.2.6.3. Q-Space | 2.2.6.3. Q-Space | |||

Please refer to Section 2.2.3 for a formal definition for Q-Space. | Please refer to Section 2.2.3 for a formal definition for Q-Space. | |||

A node Y is in Q-space w.r.t to the link (S-E) being protected, if | A node Y is in Q-space w.r.t the link (S-E) being protected, if and | |||

and only if, the following condition is satisfied. | only if, the following condition is satisfied. | |||

D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) | D_opt(Y,E) < D_opt(S,E) + D_opt(Y,S) | |||

Where, | Where, | |||

D_opt(A,B) : Distance on most optimum path from A to B. | D_opt(A,B) : Distance on most optimum path from A to B. | |||

E : The primary nexthop on shortest path from S | E : The primary nexthop on shortest path from S | |||

to destination. | to destination. | |||

Y : The node being evaluated for Q-Space. | Y : The node being evaluated for Q-Space. | |||

Figure 5: Q-Space Condition | Figure 5: Q-Space Condition | |||

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

destination is comprised of two path segments as follows. | destination is comprised of two path segments as follows. | |||

1. Path segment from the computing router to the PQ-node (Remote-LFA | 1. Path segment from the computing router to the PQ-node (Remote-LFA | |||

alternate nexthop), and | alternate nexthop), and | |||

2. Path segment from the PQ-node to the destination being protected. | 2. Path segment from the PQ-node to the destination being protected. | |||

So to ensure a R-LFA alternate path for a given destination provides | So to ensure a R-LFA alternate path for a given destination provides | |||

node-protection we need to ensure that none of the above path | node-protection we need to ensure that none of the above path | |||

segments are affected in the event of failure of the primary nexthop | segments are affected in the event of failure of the primary nexthop | |||

node. Sections Section 2.3.1 and Section 2.3.2 shows how this can be | node. Sections Section 2.3.1 and Section 2.3.2 show how this can be | |||

ensured. | ensured. | |||

2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary | 2.3.1. Computing Candidate Node-protecting PQ-Nodes for Primary | |||

nexthops | nexthops | |||

To choose a node-protecting R-LFA nexthop for a destination R3, | To choose a node-protecting R-LFA nexthop for a destination R3, | |||

router S needs to consider a PQ-node from the candidate node- | router S needs to consider a PQ-node from the candidate node- | |||

protecting PQ-space for the primary nexthop E on shortest path from S | protecting PQ-space for the primary nexthop E on shortest path from S | |||

to R3. As mentioned in Section 2.2.2, to consider a PQ-node as | to R3. As mentioned in Section 2.2.2, to consider a PQ-node as | |||

candidate node-protecting PQ-node, there must be at least one direct | candidate node-protecting PQ-node, there must be at least one direct | |||

skipping to change at page 10, line 33 ¶ | skipping to change at page 10, line 33 ¶ | |||

Some SPF implementations may also produce a list of links and nodes | Some SPF implementations may also produce a list of links and nodes | |||

traversed on the shortest path(s) from a given root to others. In | traversed on the shortest path(s) from a given root to others. In | |||

such implementations, router S may have executed a forward SPF with | such implementations, router S may have executed a forward SPF with | |||

each of its direct neighbors as the SPF root, executed as part of the | each of its direct neighbors as the SPF root, executed as part of the | |||

standard LFA [RFC5286] computations. So S may re-use the list of | standard LFA [RFC5286] computations. So S may re-use the list of | |||

links and nodes collected from the same SPF computations, to decide | links and nodes collected from the same SPF computations, to decide | |||

whether a node Y is a candidate node-protecting PQ-node or not. A | whether a node Y is a candidate node-protecting PQ-node or not. A | |||

node Y shall be considered as a node-protecting PQ-node, if and only | node Y shall be considered as a node-protecting PQ-node, if and only | |||

if, there is at least one direct neighbor of S, other than the | if, there is at least one direct neighbor of S, other than the | |||

primary nexthop E, for which, the primary nexthop node E does not | primary nexthop E, for which, the primary nexthop node E does not | |||

exist on the list of nodes traversed on any of the shortest path(s) | exist on the list of nodes traversed on any of the shortest paths | |||

from the direct neighbor to the PQ-node. Table 4 below is an | from the direct neighbor to the PQ-node. Table 4 below is an | |||

illustration of the mechanism with the topology in Figure 2. | illustration of the mechanism with the topology in Figure 2. | |||

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

| Candidate | Repair Tunnel | Link-Protection | Node-Protection | | | Candidate | Repair Tunnel | Link-Protection | Node-Protection | | |||

| PQ-node | Path(Repairing | | | | | PQ-node | Path(Repairing | | | | |||

| | router to PQ- | | | | | | router to PQ- | | | | |||

| | node) | | | | | | node) | | | | |||

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

| R2 | S->N->R1->R2 | Yes | Yes | | | R2 | S->N->R1->R2 | Yes | Yes | | |||

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

nodes for a given directly attached primary link, it shall follow the | nodes for a given directly attached primary link, it shall follow the | |||

procedure as proposed in this section, to choose one or more node- | procedure as proposed in this section, to choose one or more node- | |||

protecting R-LFA paths, for destinations reachable through the same | protecting R-LFA paths, for destinations reachable through the same | |||

primary link in the primary SPF graph. | primary link in the primary SPF graph. | |||

To find a node-protecting R-LFA path for a given destination, the | To find a node-protecting R-LFA path for a given destination, the | |||

computing router needs to pick a subset of PQ-nodes from the | computing router needs to pick a subset of PQ-nodes from the | |||

candidate node-protecting PQ-space for the corresponding primary | candidate node-protecting PQ-space for the corresponding primary | |||

nexthop, such that all the path(s) from the PQ-node(s) to the given | nexthop, such that all the path(s) from the PQ-node(s) to the given | |||

destination remain unaffected in the event of a node failure of the | destination remain unaffected in the event of a node failure of the | |||

primary nexthop node. To determine wether a given PQ-node belongs to | primary nexthop node. To determine whether a given PQ-node belongs | |||

such a subset of PQ-nodes, the computing router MUST ensure that none | to such a subset of PQ-nodes, the computing router MUST ensure that | |||

of the primary nexthop node are found on any of the shortest paths | none of the primary nexthop node are found on any of the shortest | |||

from the PQ-node to the given destination. | paths from the PQ-node to the given destination. | |||

This document proposes an additional forward SPF computation for each | This document proposes an additional forward SPF computation for each | |||

of the PQ-nodes, to discover all shortest paths from the PQ-nodes to | of the PQ-nodes, to discover all shortest paths from the PQ-nodes to | |||

the destination. This will help determine, if a given primary | the destination. This will help determine, if a given primary | |||

nexthop node is on the shortest paths from the PQ-node to the given | nexthop node is on the shortest paths from the PQ-node to the given | |||

destination or not. To determine if a given candidate node- | destination or not. To determine if a given candidate node- | |||

protecting PQ-node provides node-protecting alternate for a given | protecting PQ-node provides node-protecting alternate for a given | |||

destination, or not, all the shortest paths from the PQ-node to the | destination, or not, all the shortest paths from the PQ-node to the | |||

given destination has to be inspected, to check if the primary | given destination has to be inspected, to check if the primary | |||

nexthop node is found on any of these shortest paths. To compute all | nexthop node is found on any of these shortest paths. To compute all | |||

skipping to change at page 13, line 43 ¶ | skipping to change at page 13, line 43 ¶ | |||

2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP | 2.3.3. Computing Node-Protecting R-LFA Paths for Destinations with ECMP | |||

primary nexthop nodes | primary nexthop nodes | |||

In certain scenarios, when one or more destinations maybe reachable | In certain scenarios, when one or more destinations maybe reachable | |||

via multiple ECMP (equal-cost-multi-path) nexthop nodes, and only | via multiple ECMP (equal-cost-multi-path) nexthop nodes, and only | |||

link-protection is required, there is no need to compute any | link-protection is required, there is no need to compute any | |||

alternate paths for such destinations. In the event of failure of | alternate paths for such destinations. In the event of failure of | |||

one of the nexthop links, the remaining primary nexthops shall always | one of the nexthop links, the remaining primary nexthops shall always | |||

provide link-protection. However, if node-protection is required, | provide link-protection. However, if node-protection is required, | |||

the rest of the primary nexthops may not gaurantee node-protection. | the rest of the primary nexthops may not guarantee node-protection. | |||

Figure 7 below shows one such example topology. | Figure 7 below shows one such example topology. | |||

D1 | D1 | |||

2 / | 2 / | |||

S---x---E1 | S---x---E1 | |||

/ \ / \ | / \ / \ | |||

/ x / \ | / x / \ | |||

/ \ / \ | / \ / \ | |||

N-------E2 R3--D2 | N-------E2 R3--D2 | |||

\ 2 / | \ 2 / | |||

\ / | \ / | |||

\ / | \ / | |||

R1-------R2 | R1-------R2 | |||

2 | 2 | |||

Primary Nexthops: | Primary Nexthops: | |||

Destination D1 = [{ S-E1, E1}, {S-E2, E2}] | Destination D1 = [{ S-E1, E1}, {S-E2, E2}] | |||

Destination D2 = [{ S-E1, E1}, {S-E2, E2}] | Destination D2 = [{ S-E1, E1}, {S-E2, E2}] | |||

Figure 7: Toplogy with multiple ECMP primary nexthops | Figure 7: Topology with multiple ECMP primary nexthops | |||

In the above example topology, costs of all links are 1, except the | In the above example topology, costs of all links are 1, except the | |||

following links: | following links: | |||

Link: S-E1, Cost: 2 | Link: S-E1, Cost: 2 | |||

Link: N-E2: Cost: 2 | Link: N-E2: Cost: 2 | |||

Link: R1-R2: Cost: 2 | Link: R1-R2: Cost: 2 | |||

In the above topology, on computing router S, destinations D1 and D2 | In the above topology, on computing router S, destinations D1 and D2 | |||

are reachable via two ECMP nexthop nodes E1 and E2. However the | are reachable via two ECMP nexthop nodes E1 and E2. However the | |||

primary paths via nexthop node E2 also traverses via the nexthop node | primary paths via nexthop node E2 also traverses via the nexthop node | |||

E1. So in the event of node failure of nexthop node E1, both primary | E1. So in the event of node failure of nexthop node E1, both primary | |||

paths (via E1 and E2) becomes unavailable. Hence if node-protection | paths (via E1 and E2) becomes unavailable. Hence if node-protection | |||

is desired for destinations D1 and D2, alternate paths that does not | is desired for destinations D1 and D2, alternate paths that does not | |||

traverse any of the primary nexthop nodes E1 and E2, need to be | traverse any of the primary nexthop nodes E1 and E2, need to be | |||

computed. In the above topology the only alternate neighbor N does | computed. In the above topology the only alternate neighbor N does | |||

not provide such a LFA alternate path. Hence one (or more) R-LFA | not provide such a LFA alternate path. Hence one (or more) R-LFA | |||

node-proecting alternate paths for destinations D1 and D2, needs to | node-protecting alternate paths for destinations D1 and D2, needs to | |||

be computed. | be computed. | |||

In the above topology, following are the link-protecting PQ-nodes. | In the above topology, following are the link-protecting PQ-nodes. | |||

Primary Nexthop: E1, Link-Protecting PQ-Node: { R2 } | Primary Nexthop: E1, Link-Protecting PQ-Node: { R2 } | |||

Primary Nexthop: E2, Link-Protecting PQ-Node: { R2 } | Primary Nexthop: E2, Link-Protecting PQ-Node: { R2 } | |||

To find one (or more) node-protecting R-LFA paths for destinations D1 | To find one (or more) node-protecting R-LFA paths for destinations D1 | |||

and D2, one (or more) node-protecting PQ-node(s) needs to be | and D2, one (or more) node-protecting PQ-node(s) needs to be | |||

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

Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2 | Table 7: Computing Node-protected PQ-nodes for nexthop E1 and E2 | |||

In SPF implementations that also produce a list of links and nodes | In SPF implementations that also produce a list of links and nodes | |||

traversed on the shortest path(s) from a given root to others, the | traversed on the shortest path(s) from a given root to others, the | |||

tunnel-repair paths from the computing router to candidate PQ-node | tunnel-repair paths from the computing router to candidate PQ-node | |||

can be examined to ensure that none of the primary nexthop nodes is | can be examined to ensure that none of the primary nexthop nodes is | |||

traversed. PQ-nodes that provide one (or more) Tunnel-repair | traversed. PQ-nodes that provide one (or more) Tunnel-repair | |||

paths(s) that does not traverse any of the primary nexthop nodes, are | paths(s) that does not traverse any of the primary nexthop nodes, are | |||

to be considered as node-protecting PQ-nodes. Table 8 below shows | to be considered as node-protecting PQ-nodes. Table 8 below shows | |||

the possible tunnel-repair paths tp PQ-node R2. | the possible tunnel-repair paths to PQ-node R2. | |||

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

| Primary-NH | PQ-Node | Tunnel-Repair | Exclude All | | | Primary-NH | PQ-Node | Tunnel-Repair | Exclude All | | |||

| (E) | (Y) | Paths | Primary-NH | | | (E) | (Y) | Paths | Primary-NH | | |||

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

| E1, E2 | R2 | S==>N==>R1==>R2 | Yes | | | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | | |||

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

Table 8: Tunnel-Repair paths to PQ-node R2 | Table 8: Tunnel-Repair paths to PQ-node R2 | |||

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

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

Table 9: Finding node-protecting R-LFA path for destinations D1 and | Table 9: Finding node-protecting R-LFA path for destinations D1 and | |||

D2 | D2 | |||

In SPF implementations that also produce a list of links and nodes | In SPF implementations that also produce a list of links and nodes | |||

traversed on the shortest path(s) from a given root to others, the | traversed on the shortest path(s) from a given root to others, the | |||

R-LFA paths via node-protecting PQ-node to final destination can be | R-LFA paths via node-protecting PQ-node to final destination can be | |||

examined to ensure that none of the primary nexthop nodes is | examined to ensure that none of the primary nexthop nodes is | |||

traversed. R-LFA path(s) that does not traverse any of the primary | traversed. R-LFA path(s) that does not traverse any of the primary | |||

nexthop nodes, gaurantees node-protection in the event of failure of | nexthop nodes, guarantees node-protection in the event of failure of | |||

any of the primary nexthop nodes. Table 10 below shows the possible | any of the primary nexthop nodes. Table 10 below shows the possible | |||

R-LFA-paths for destinations D1 and D2 via the node-protecting PQ- | R-LFA-paths for destinations D1 and D2 via the node-protecting PQ- | |||

node R2. | node R2. | |||

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

| Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude | | | Destination | Primary-NH | PQ-Node | R-LFA Paths | Exclude | | |||

| (D) | (E) | (Y) | | All | | | (D) | (E) | (Y) | | All | | |||

| | | | | Primary-NH | | | | | | | Primary-NH | | |||

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

| D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No | | | D1 | E1, E2 | R2 | S==>N==>R1==>R2 | No | | |||

| | | | -->R3-->E1-->D1 | | | | | | | -->R3-->E1-->D1 | | | |||

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

| D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | | | D2 | E1, E2 | R2 | S==>N==>R1==>R2 | Yes | | |||

| | | | -->R3-->D2 | | | | | | | -->R3-->D2 | | | |||

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

Table 10: R-LFA paths for destinations D1 and D2 | Table 10: R-LFA paths for destinations D1 and D2 | |||

From Table 9 and Table 10, in the above example above, the R-LFA path | From Table 9 and Table 10, in the example above, the R-LFA path from | |||

from R2 does not meet the node-protecting inequality for destination | R2 does not meet the node-protecting inequality for destination D1, | |||

D1, while it does meet the same inequality for destination D2. And | while it does meet the same inequality for destination D2. And so, | |||

so, while R2 provides node-protecting R-LFA alternate for D2, it | while R2 provides node-protecting R-LFA alternate for D2, it fails to | |||

fails to provide node-protection for destination D1. Finally, while | provide node-protection for destination D1. Finally, while it is | |||

it is possible to get a node-protecting R-LFA path for D2, no such | possible to get a node-protecting R-LFA path for D2, no such node- | |||

node-protecting R-LFA path can be found for D1. | protecting R-LFA path can be found for D1. | |||

2.3.4. Limiting extra computational overhead | 2.3.4. Limiting extra computational overhead | |||

In addition to the extra reverse SPF computations suggested by the | In addition to the extra reverse SPF computations suggested by the | |||

Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly | Remote-LFA [RFC7490] draft (one reverse SPF for each of the directly | |||

connected neighbors), this document proposes a forward SPF | connected neighbors), this document proposes a forward SPF | |||

computations for each PQ-node discovered in the network. Since the | computations for each PQ-node discovered in the network. Since the | |||

average number of PQ-nodes found in any network is considerably more | average number of PQ-nodes found in any network is considerably more | |||

than the number of direct neighbors of the computing router, the | than the number of direct neighbors of the computing router, the | |||

proposal of running one forward SPF per PQ-node may add considerably | proposal of running one forward SPF per PQ-node may add considerably | |||

to the overall SPF computation time. | to the overall SPF computation time. | |||

To limit the computational overhead of the approach proposed, this | To limit the computational overhead of the approach proposed, this | |||

document proposes that implementations MUST choose a subset from the | document proposes that implementations MUST choose a subset from the | |||

entire set of PQ-nodes computed in the network, with a finite limit | entire set of PQ-nodes computed in the network, with a finite limit | |||

on the number of PQ-nodes in the subset. Implementations MUST choose | on the number of PQ-nodes in the subset. Implementations MUST choose | |||

a default value for this limit and may provide user with a | a default value for this limit and may provide user with a | |||

configuration knob to override the default limit. Implementations | configuration knob to override the default limit. Implementations | |||

MUST also evaluate some default preference criteria while considering | MUST also evaluate some default preference criteria while considering | |||

a PQ-node in this subset. Finally, implementations MAY also allow | a PQ-node in this subset. Finally, implementations MAY also allow | |||

user to override the default preference criteria, by providing a | the user to override the default preference criteria, by providing a | |||

policy configuration for the same. | policy configuration for the same. | |||

This document proposes that implementations SHOULD use a default | This document proposes that implementations SHOULD use a default | |||

preference criteria for PQ-node selection which will put a score on | preference criteria for PQ-node selection which will put a score on | |||

each PQ-node, proportional to the number of primary interfaces for | each PQ-node, proportional to the number of primary interfaces for | |||

which it provides coverage, its distance from the computing router, | which it provides coverage, its distance from the computing router, | |||

and its router-id (or system-id in case of IS-IS). PQ-nodes that | and its router-id (or system-id in case of IS-IS). PQ-nodes that | |||

cover more primary interfaces SHOULD be preferred over PQ-nodes that | cover more primary interfaces SHOULD be preferred over PQ-nodes that | |||

cover fewer primary interfaces. When two or more PQ-nodes cover the | cover fewer primary interfaces. When two or more PQ-nodes cover the | |||

same number of primary interfaces, PQ-nodes which are closer (based | same number of primary interfaces, PQ-nodes which are closer (based | |||

on metric) to the computing router SHOULD be preferred over PQ-nodes | on metric) to the computing router SHOULD be preferred over PQ-nodes | |||

farther away from it. For PQ-nodes that cover the same number of | farther away from it. For PQ-nodes that cover the same number of | |||

primary interfaces and are the same distance from the the computing | primary interfaces and are the same distance from the computing | |||

router, the PQ-node with smaller router-id (or system-id in case of | router, the PQ-node with smaller router-id (or system-id in case of | |||

IS-IS) SHOULD be preferred. | IS-IS) SHOULD be preferred. | |||

Once a subset of PQ-nodes is found, computing router shall run a | Once a subset of PQ-nodes is found, computing router shall run a | |||

forward SPF on each of the PQ-nodes in the subset to continue with | forward SPF on each of the PQ-nodes in the subset to continue with | |||

procedures proposed in section Section 2.3.2. | procedures proposed in Section 2.3.2. | |||

3. Manageabilty of Remote-LFA Alternate Paths | 3. Manageability of Remote-LFA Alternate Paths | |||

3.1. The Problem | 3.1. The Problem | |||

With the regular Remote-LFA [RFC7490] functionality the computing | With the regular Remote-LFA [RFC7490] functionality the computing | |||

router may compute more than one PQ-node as usable Remote-LFA | router may compute more than one PQ-node as usable Remote-LFA | |||

alternate nexthops. Additionally an alternate selection policy may | alternate nexthops. Additionally an alternate selection policy may | |||

be configured to enable the network operator to choose one of them as | be configured to enable the network operator to choose one of them as | |||

the most appropriate Remote-LFA alternate. For such policy-based | the most appropriate Remote-LFA alternate. For such policy-based | |||

alternate selection to run, all the relevant path characteristics for | alternate selection to run, all the relevant path characteristics for | |||

each the alternate paths (one through each of the PQ-nodes), needs to | each the alternate paths (one through each of the PQ-nodes), needs to | |||

be collected. As mentioned before in section Section 2.3 the R-LFA | be collected. As mentioned before in Section 2.3 the R-LFA alternate | |||

alternate path through a given PQ-node to a given destination is | path through a given PQ-node to a given destination is comprised of | |||

comprised of two path segments. | two path segments. | |||

The first path segment (i.e. from the computing router to the PQ- | The first path segment (i.e. from the computing router to the PQ- | |||

node) can be calculated from the regular forward SPF done as part of | node) can be calculated from the regular forward SPF done as part of | |||

standard and remote LFA computations. However without the mechanism | standard and remote LFA computations. However without the mechanism | |||

proposed in section Section 2.3.2 of this document, there is no way | proposed in section Section 2.3.2 of this document, there is no way | |||

to determine the path characteristics for the second path segment | to determine the path characteristics for the second path segment | |||

(i.e from the PQ-node to the destination). In the absence of the | (i.e. from the PQ-node to the destination). In the absence of the | |||

path characteristics for the second path segment, two Remote-LFA | path characteristics for the second path segment, two Remote-LFA | |||

alternate path may be equally preferred based on the first path | alternate paths may be equally preferred based on the first path | |||

segments characteristics only, although the second path segment | segments characteristics only, although the second path segment | |||

attributes may be different. | attributes may be different. | |||

3.2. The Solution | 3.2. The Solution | |||

The additional forward SPF computation proposed in Section 2.3.2 | The additional forward SPF computation proposed in Section 2.3.2 | |||

document shall also collect links, nodes and path characteristics | document shall also collect links, nodes and path characteristics | |||

along the second path segment. This shall enable collection of | along the second path segment. This shall enable collection of | |||

complete path characteristics for a given Remote-LFA alternate path | complete path characteristics for a given Remote-LFA alternate path | |||

to a given destination. The complete alternate path characteristics | to a given destination. The complete alternate path characteristics | |||

shall then facilitate more accurate alternate path selection while | shall then facilitate more accurate alternate path selection while | |||

running the alternate selection policy. | running the alternate selection policy. | |||

As already specified in Section 2.3.4 to limit the computational | As already specified in Section 2.3.4 to limit the computational | |||

overhead of the approach proposed, forward SPF computations MUST be | overhead of the proposed approach, forward SPF computations MUST be | |||

run on a selected subset from the entire set of PQ-nodes computed in | run on a selected subset from the entire set of PQ-nodes computed in | |||

the network, with a finite limit on the number of PQ-nodes in the | the network, with a finite limit on the number of PQ-nodes in the | |||

subset. The detailed suggestion on how to select this subset is | subset. The detailed suggestion on how to select this subset is | |||

specified in the same section. While this limits the number of | specified in the same section. While this limits the number of | |||

possible alternate paths provided to the alternate-selection policy, | possible alternate paths provided to the alternate-selection policy, | |||

this is needed keep the computational complexity within affordable | this is needed to keep the computational complexity within affordable | |||

limits. However if the alternate-selection policy is very | limits. However if the alternate-selection policy is very | |||

restrictive this may leave few destinations in the entire toplogy | restrictive this may leave few destinations in the entire topology | |||

without protection. Yet this limitation provides a necessary | without protection. Yet this limitation provides a necessary | |||

tradeoff between extensive coverage and immense computational | tradeoff between extensive coverage and immense computational | |||

overhead. | overhead. | |||

4. Acknowledgements | 4. Acknowledgements | |||

Many thanks to Bruno Decraene for providing his useful comments. We | Many thanks to Bruno Decraene for providing his useful comments. We | |||

would also like to thank Uma Chunduri for reviewing this document and | would also like to thank Uma Chunduri for reviewing this document and | |||

providing valuable feedback. Also, many thanks to Harish Raghuveer | providing valuable feedback. Also, many thanks to Harish Raghuveer | |||

for his review and comments on the initial versions of this document. | for his review and comments on the initial versions of this document. | |||

End of changes. 33 change blocks. | ||||

56 lines changed or deleted | | 54 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/ |