Subject: RE: WGLC for draft-rtgwg-mrt-frr-architecture

From: Chris Bowers <[email-masked]>
Date: Sun, 10 Jan 2016 18:43:26 +0000

Stewart and Rob,

I published a new revision of this draft at:

https://www.ietf.org/internet-drafts/draft-ietf-rtgwg-mrt-frr-architecture-09.txt

The introduction has quite a few changes where I tried to address several of the issues you raised including the table and text comparing different IP/LDP FRR methods.   The new text is copied below.

Thanks,

Chris

====================

1.  Introduction

   This document describes a solution for IP/LDP fast-reroute [RFC5714].

   MRT-FRR creates two alternate trees separate from the primary next-

   hop forwarding used during stable operation.  These two trees are

   maximally diverse from each other, providing link and node protection

   for 100% of paths and failures as long as the failure does not cut

   the network into multiple pieces.  This document defines the

   architecture for IP/LDP fast-reroute with MRT.

   [I-D.ietf-rtgwg-mrt-frr-algorithm] describes how to compute maximally

   redundant trees using a specific algorithm, the MRT Lowpoint

   algorithm.  The MRT Lowpoint algorithm is used by a router that

   IP/LDP Fast-Reroute with MRT (MRT-FRR) uses two maximally diverse

   forwarding topologies to provide alternates.  A primary next-hop

   should be on only one of the diverse forwarding topologies; thus, the

   other can be used to provide an alternate.  Once traffic has been

   moved to one of the MRTs by one point of local repair (PLR), that

   traffic is not subject to further repair actions by another PLR, even

   in the event of multiple simultaneous failures.  Therefore, traffic

   repaired by MRT-FRR will not loop between different PLRs responding

   to different simultaneous failures.

   While MRT provides 100% protection for a single link or node failure,

   it may not protect traffic in the event of multiple simultaneous

   failures, nor does take into account Shared Risk Link Groups (SRLGs).

   Also, while the MRT Lowpoint algorithm is computationally efficient,

   it is also new.  In order for MRT-FRR to function properly, all of

   the other nodes in the network that support MRT must correctly

   compute next-hops based on the same algorithm, and install the

   corresponding forwarding state.  This is in contrast to other FRR

   methods where the calculation of backup paths generally involves

   repeated application of the simpler and widely-deployed SPF

   algorithm, and backup paths themselves re-use the forwarding state

   used for shortest path forwarding of normal traffic.  Section 14

   provides operational guidance related to verification of MRT

   forwarding paths.

  In addition to supporting IP and LDP unicast fast-reroute, the

   diverse forwarding topologies and guarantee of 100% coverage permit

   fast-reroute technology to be applied to multicast traffic as

   described in [I-D.atlas-rtgwg-mrt-mc-arch].  However, the current

   document does not address the multicast applications of MRTs.

   Figure 1 compares different methods of providing FRR for IP and LDP

   traffic, illustrating some of the trade-offs between the different

   approaches.  For several methods, the methods are separated into

   link-protecting (LP) and node-protecting (NP) variants.  The first

   column indicates whether the method provides 100% protection coverage

   (when topologically feasible).  The second column indicates whether

   or not traffic traversing alternate path can loop when multiple

   failures occur.

   The third column gives an estimate of the amount of computation

   required at each node to support the FRR method, in addition to the

   usual SPF computation rooted at the computing node itself.  This

   metric of comparison is important for implementations that seek to

   quickly recompute repair paths following their initial use after a

   topology change, without reliance on an external system, in order to

   minimize the risk of a new failure occurring before the new repair

   paths are in place.

   The fourth column indicates the maximum number of additional labels

   that need to be applied to packets to support the FRR method, while

  the fifth column gives the size of the MPLS label table needed to

   support the FRR method.  These two metrics may be useful for

   evaluating requirements placed on hardware to support the different

   FRR methods.

   The last column indicates the additional requirements placed on the

   control plane by the FRR method, beyond what is required for IGP

   shortest path forwarding with LDP.

+---------+-----+------+-------------+-------+-------------+----------+

| Method  |100% | Alt. | Additional  | Max.  | Label table | Control  |

|         |prot.| can  | computation | addit.|    size     | plane    |

|         |cov. | loop?| at each     | labels|(relative to | reqs.    |

|         |     |      | node        |       | SPF labels) |          |

+---------+-----+------+-------------+-------+-------------+----------+

| MRT-FRR | Yes | No   | equivalent  | 0(LDP)|     3x      | MRT-     |

| LP and  |     |      | of less     | 1(IP) |             | specific |

| NP      |     |      | than        |       |             | protocol |

|         |     |      | 3 SPFs      |       |             | extens.  |

+---------+-----+------+-------------+-------+-------------+----------+

| LFA LP  | No  | Yes  |  SPF per    |   0   |     1x      | None     |

| and NP  |     |      |  neighbor   |       |             |          |

+---------+-----+------+-------------+-------+-------------+----------+

| Remote  | No  | Yes  |  SPF per    |   1   |     1x      | T-LDP    |

| LFA LP  |     |      |  neighbor   |       |             | session  |

|         |     |      |             |       |             | for each |

|         |     |      |             |       |             | selected |

|         |     |      |             |       |             | PQ node  |

+---------+-----+------+-------------+-------+-------------+----------+

| Remote  | No  | Yes  | SPF per nbr |   1   |     1x      | T-LDP    |

| LFA NP  |     |      | and SPF per |       |             | session  |

|         |     |      | per PQ node |       |             | for each |

|         |     |      | evaluated   |       |             | selected |

|         |     |      |             |       |             | PQ node  |

+---------+-----+------+-------------+-------+-------------+----------+

| Not-Via | Yes | No   | SPF per     |   1   |  (average   | T-LDP    |

| LP and  |     |      | link and    |       |  number of  | session  |

| NP      |     |      | per node    |       |  neighbors) | for each |

|         |     |      | in topology |       |      x      | nbr's nbr|

+---------+-----+------+-------------+-------+-------------+----------+

| TI-LFA  | Yes | Yes  | SPF per     |   2   |     1x      | uses     |

| LP with |     |      | neighbor    |       |             | SPRING   |

| symm.   |     |      |             |       |             | for      |

| metrics |     |      |             |       |             | label    |

|         |     |      |             |       |             | dist.    |

+---------+-----+------+-------------+-------+-------------+----------+

| TI-LFA  | Yes | Yes  | # of SPFs   |depth  |     1x      | uses     |

| NP or   |     |      | dependent   |depend-|             | SPRING   |

| LP with |     |      | on topology |ent on |             | for      |

| asymm.  |     |      |             |topo.  |             | label    |

| metrics |     |      |             |       |             | dist.    |

+---------+-----+------+-------------+-------+-------------+----------+

                Figure 1: Comparison of IP/LDP FRR Methods

   MRT:   MRT provides 100% coverage for link and node protection, and

      traffic on the alternate paths will not loop.  The computation

      required on each node is equivalent to less than 3 additional SPFs

      in terms of computational complexity.  For IP traffic, MRT

      requires one additional label, while for LDP traffic, no

      additional labels are needed.  However, the size of the MPLS label

      table is three times what would normally be required for shortest

      path LDP forwarding, due to the presence of additional red and

      blue labels for each FEC.  MRT requires protocol extensions in

      order to allow a node to advertise support for MRT as well as a

      value for the GADAG Root Selection Priority.  It also requires

      support for multi-topology LDP extensions.

   Loop-Free Alternates (LFA):   LFAs [RFC5286] provide limited

      topology-dependent coverage for link and node protection.

      Restrictions on choice of alternates can be relaxed to improve

      coverage, but this can cause forwarding loops if a worse failure

      is experienced than protected against.  [RFC6571] discusses the

      applicability of LFA to different topologies with a focus on

      common PoP architectures.  The computation required is one SPF per

      neighbor.  LFA imposes no additional labels imposed, has no impact

      on the label table size, and has no additional control plane

      requirements.

  Remote LFA:   Remote LFA [RFC7490] improves coverage over LFA for

      both link and node protection, but it does not guarantee 100%

      coverage.  The alternates can also loop with worse than expected

      failures.  Computation for link protection is one SPF per

      neighbor, while computation for node protection requires an

      additional SPF per PQ node [I-D.ietf-rtgwg-rlfa-node-protection].

      Remote LFA can impose up to one additional label on the packet,

      but does not increase the size of the label table.  It requires a

      T-LDP session for each selected PQ node.

   Not-Via:   Not-Via [RFC6981] provides 100% coverage for link and node

      failures and does not have potential looping among alternates.

      The computation is high with an SPF per potential failure point

      (all links and nodes in the topology).  When implemented with LDP,

      Not-Via adds one additional label to a tunnelled packet.  It

      significantly increases the size of the label table, multiplying

      it by roughly the average number of neighbors.  Not-Via also

      requires targeted LDP sessions to each neighbor's neighbor.

   TI-LFA:   Topology Independent Loop-free Alternate Fast Re-route (TI-

      LFA) [I-D.francois-rtgwg-segment-routing-ti-lfa] aims to provide

      link and node protection of node and adjacency segments within the

      Segment Routing (SR) framework.  It guarantees complete coverage.

      The TI-LFA computation for link-protection is fairly

      straightforward, while the computation for node-protection is more

      complex.  For link-protection with symmetric link costs, TI-LFA

      can provide complete coverage by pushing up to two additional

      labels.  For node protection on arbitrary topologies, the label

      stack size can grow significantly based on repair path.  Note that

      TI-LFA requires shortest path forwarding based on SR Node-SIDs, as

      opposed to LDP labels, in order to construct label stacks for

      backups paths without relying on a large number of targeted LDP

      sessions to learn remote FEC-label bindings.  It also requires the

      use of Adj-SIDs to achieve 100% coverage.

-----Original Message-----

From: Stewart Bryant [mailto:[email-masked]]

Sent: Wednesday, December 23, 2015 6:29 AM

To: Chris Bowers <[email-masked]>; [email-masked]; [email-masked]; Alvaro Retana <[email-masked]>

Subject: Re: WGLC for draft-rtgwg-mrt-frr-architecture

Hi Chris

Thanks for addressing my comments.

I will trim the email to just the areas that need fur

On 21/12/2015 14:47, Chris Bowers wrote:

> ===========

>   1.  Introduction

> SB> The text should start with the invariants and assumptions to

> SB> correctly scope the claims in the introduction.

> [CB] Changed the text to read:

> This document describes a solution for IP/LDP fast-reroute    [RFC5714].

SB> I think the assumptions are for example:

- Single link or node failure

- Can't remember if you have the means to deal with SRLG

- LF technique is in place

- method of detecting situation outside your assumptions is in place

In other words, you need to describe assumptions you are making making about the environment in which this solution works. Whilst

RFC5714 talks around the problem, a solution needs to be quite specific about when it breaks, (a) to alert the operator, and

(b) to make sure that the solution considers the consequences of operating outside the specified envelope.

[CB] The 3rd paragraph of the revised introduction was added to address this.

> SB> I think you have to say where the trees are routed since only two

> SB> mean you need a root, and you need to note that this is different

> SB> from the underlying IGP in which there is a tree per node.

> [CB]  I don’t understand the distinction that you suggest noting.  The MRT computation run at each source node produces a distinct red and blue tree for each destination node with each tree rooted at and directed towards the destination node.  The end result is similar to way that the forward SPF computation run at each source node produces a shortest path tree for each destination node with each tree rooted at and directed towards the destination node.

SB> Maybe I am confused. As I recall you need to determine a single

lowpoint as the starting

point for your repair topologies. Doesn't that mean that effectively become the root of a pair of repair trees?

Also the low point can move under certain circumstances, and I thing that will impact the repair topology.

[CB] The algorithm in draft-ietf-rtgwg-mrt-frr-algorithm uses lowpoint values  to identify ears and blocks when doing a depth-first-search traversal of the network graph.  This is covered in Section 4.3 of that doc.  The DFS traversal starts at the GADAG root, and the choice of GADAG root will generally affect the GADAG and the red and blue trees.  I added text in the latest revision that addresses the concern of having the GADAG root change too often.

>                   Summary Comparison of IP/LDP FRR Methods

>     +---------+-------------+-------------+-----------------------------+

>     |  Method |   Coverage  |  Alternate  |    Computation (in SPFs)    |

>     |         |             |   Looping?  |                             |

>     +---------+-------------+-------------+-----------------------------+

>     | MRT-FRR |     100%    |     None    |         less than 3         |

>     |         |  Link/Node  |             |                             |

>     |         |             |             |                             |

>     |   LFA   |   Partial   |   Possible  |         per neighbor        |

>     |         |  Link/Node  |             |                             |

>     |         |             |             |                             |

>     |  Remote |   Partial   |   Possible  |    per neighbor (link) or   |

>     |   LFA   |  Link/Node  |             |  neighbor's neighbor (node) |

>     |         |             |             |                             |

>     | Not-Via |     100%    |     None    |      per link and node      |

>     |         |  Link/Node  |             |                             |

>     |         |             |             |                             |

>     |  TI-LFA |     100%    |   Possible  |    per neighbor (link) or   |

>     |         |  Link/Node  |             |  neighbor's neighbor (node) |

> +---------+-------------+-------------+-----------------------------+

> SB> I really wonder how important the computational complexity is

> SB> given that we are moving to an SDN world where these calculations

> SB> can be offloaded?

> SB>

> SB> I think that it is fair to note that the other method use the

> SB> existing routing protocol and calculate alternate paths using the

> SB> methods of that routing protocol. Whereas with MRT you really have

> SB> a new routing protocol with all of the associated operations overhead.

SB> I think this deserves consideration. The route computational world

has moved

on since this work was started.

[CB]  The latest revision tries to provide more context for when reducing computation time may be useful.

> 6.1.1.1.  Topology-scoped FEC encoded using a single label (Option 1A)

>     [RFC7307] provides a mechanism to distribute FEC-Label bindings

>     scoped to a given MPLS topology (represented by MPLS MT-ID).  To use

>     multi-topology LDP to create MRT forwarding topologies, we associate

>     two MPLS MT-IDs with the MRT-Red and MRT-Blue forwarding topologies,

>     in addition to the default shortest path forwarding topology with MT-

>     ID=0.

> SB> Presumably you could MRT a topology other than default?

> [CB] It could be done, but we focused on supporting the use case using the default IGP topology.  There is existing text in section 7 explaining this.

>   Deployment scenarios using multi-topology OSPF or IS-IS, or running

>     both ISIS and OSPF on the same routers is out of scope for this

>     specification.

> SB> To be clear - you need 3 * the number of delivery labels in the

> SB> network, and in some cases these labels identify prefix or a VPN

> SB> exit point.

> SB> This is a lot more labels than some of the competing schemes and

> SB> so I think we really need a label table size comparison in the

> SB> comparison section earlier in the document.

SB> No comment on the above?

[CB] This is included in the table and discussion in the latest revision.