| Network Working Group | Z. Li |
| Internet-Draft | N. Wu |
| Intended status: Standards Track | Q. Zhao |
| Expires: April 21, 2016 | Huawei Technologies |
| A. Atlas | |
| C. Bowers | |
| Juniper Networks | |
| J. Tantsura | |
| Ericsson | |
| October 19, 2015 |
Intermediate System to Intermediate System (IS-IS) Extensions for Maximally Redundant Trees (MRT)
draft-ietf-isis-mrt-01
This document describes extensions to IS-IS to support the distributed computation of Maximally Redundant Trees (MRT). Example uses of MRT include IP/LDP Fast-Reroute and global protection or live-live for multicast traffic. The extensions indicate what MRT profile(s) each router supports. Different MRT profiles can be defined to support different uses and to allow transition of capabilities. An extension is introduced to flood MRT-Ineligible links, due to administrative policy. This document also defines the Controlled Convergence sub-TLV, which is useful for MRT FRR as well as other applications.
This Internet-Draft is submitted in full conformance with the 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 and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 21, 2016.
Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
The IS-IS protocol is specified in [ISO10589], with extensions for supporting IPv4 and IPv6 specified in [RFC1195] and [RFC5308]. Each Intermediate System (IS) (router) advertises one or more IS-IS Link State Protocol Data Units (LSPs) with routing information. Each LSP is composed of a fixed header and a number of tuples, each consisting of a Type, a Length, and a Value. Such tuples are commonly known as TLVs, and are a good way of encoding information in a flexible and extensible format.
[I-D.ietf-rtgwg-mrt-frr-architecture] gives a complete solution for IP/LDP fast-reroute using Maximally Redundant Trees (MRT) to provide alternates. This document describes signalling extensions for supporting MRT-FRR in an IS-IS routing domain.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].
Redundant Trees (RT): A pair of trees where the path from any node X to the root R along the first tree is node-disjoint with the path from the same node X to the root R along the second tree. These can be computed in 2-connected graphs.
Maximally Redundant Trees (MRT): A pair of trees where the path from any node X to the root R along the first tree and the path from the same node X to the root R along the second tree 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-links. Any RT is an MRT but many MRTs are not RTs.
MRT Island: From the computing router, the set of routers that support a particular MRT profile and are connected via MRT- eligible links.
GADAG: Generalized Almost Directed Acyclic Graph - a graph which is the combination of the ADAGs of all blocks. Transforming a network graph into a GADAG is part of the MRT algorithm.
MRT-Red: MRT-Red is used to describe one of the two MRTs; it is used to describe the associated forwarding topology and MT-ID. Specifically, MRT-Red is the decreasing MRT where links in the GADAG are taken in the direction from a higher topologically ordered node to a lower one.
MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is used to describe the associated forwarding topology and MT-ID. Specifically, MRT-Blue is the increasing MRT where links in the GADAG are taken in the direction from a lower topologically ordered node to a higher one.
As stated in [I-D.ietf-rtgwg-mrt-frr-algorithm], it is necessary for each MRT-Capable router to compute MRT next hops in a consistent fashion. This is achieved by using the same MRT profile and selecting a common and unique GADAG root in the MRT Island which is connected by MRT-Eligible links. Each of these issues will be discussed in the following sections separately.
The contents and requirements of an MRT profile has been defined in [I-D.ietf-rtgwg-mrt-frr-architecture]. The parameters and behavioral rules contained in an MRT profile define one router's MRT capabilities. Based on common capabilities, one unified MRT Island is built.
The MRT-Capable router MUST advertise its corresponding MRT profiles by IS-IS protocol extension within IS-IS routing domain. The capabilities of the advertiser MUST completely conform to the profile it claimed, including the MT-IDs, the algorithm and the corresponding forwarding mechanism. This advertisement MUST have level scope. A given router MAY support multiple MRT profiles. If so, it MUST advertise each of these profiles in the corresponding IS-IS level.
The default MRT Profile is defined in [I-D.ietf-rtgwg-mrt-frr-architecture]. Its behavior is intended to support IP/LDP unicast and multicast Fast-Reroute. MRT-Capable routers SHOULD support the default MRT profile.
As per [I-D.ietf-rtgwg-mrt-frr-algorithm], a GADAG root MUST be selected for one MRT Island. An unique GADAG root in common among MRT Island routers is a necessity to do MRT computation. Since the selection of the GADAG root can affect the quality of paths for traffic sent over MRT Red and Blue trees, the GADAG Root Selection Priority and the GADAG Root Selection Policy gives a network operator the ability to influence the selection of the GADAG root.
Each MRT-Capable router MUST advertise its priority for GADAG root selection. A router can only have one priority in a given MRT Island. It can have multiple priorities for different MRT Islands it supports. Routers that are marked as overloaded([RFC3787]) are not qualified as candidate for root selection.
The GADAG Root Selection Policy (defined as part of an MRT profile) may make use of the GADAG Root Selection Priority value advertised in the MRT Profile in the IS-IS Router CAPABILITY TLV. For example, the GADAG Root Selection Policy for the default MRT profile is the following: Among the routers in the MRT Island and with the highest priority advertised, an implementation MUST pick the router with the highest Router ID to be the GADAG root.
When the current root is out of service or new router with higher priority joined into the MRT Island, the GADAG root MUST be re-selected. A new MRT computation will be triggered because of such a topology change.
For administrative or management reasons, it may be desirable to exclude some links from the MRT computation. In this scenario, MRT-Capable router MUST claim those MRT-Ineligible links are out of MRT Island scope. If such claim splits current MRT Island then MRT computation has to be done inside the modified MRT Island which the computing router belongs to.
A MRT Computation can be triggered through topology changes or MRT capability changes of any router in the MRT Island. It is always triggered for a given MRT Profile in the corresponding level. First, the associated MRT Island is determined. Then, the GADAG Root is selected. Finally, the actual MRT algorithm is run to compute the transit MRT-Red and MRT-Blue topologies. Additionally, the router MAY choose to compute MRT-FRR alternates or make other use of the MRT computation results.
Prefixes can be attached and detached and have their associated MRT- Red and MRT-Blue next-hops computed without requiring a new MRT computation.
An MRT-Capable router MUST identify its MRT capabilities through IS-IS Link State Packets(LSPs) in level scope.
A new MRT Profile sub-TLV is introduced into the IS-IS Router CAPABILITY TLV (TLV #242 defined in [RFC4971]) to advertise MRT capabilities. Since MRT has per level scope, the S-bit and D-bit of IS-IS Router CAPABILITY TLV MUST be set to zero. The structure of the MRT Profile sub-TLV is shown below:
TYPE: TBA-MRT-ISIS-1 (To Be Allocated by IANA)
LENGTH: 4
VALUE:
MT-ID (2 octets with 4 bits reserved)
MRT Profile ID (1 octet)
GADAG Root Selection Priority (1 octet)
Number of octets
+-------------------------------+
|R |R |R |R | MT-ID | 2
+-------------------------------+
| MRT Profile ID | 1
+-------------------------------+
| GADAG Root Selection Priority | 1
+-------------------------------+
MT-ID is a 12-bit field containing the multi-topology ID. As discussed in Section 5.3, this document specifies that the MT-ID field MUST be set to zero.
The MRT Profile ID represents the MRT profile this router supports.
The GADAG Root Selection Priority is the priority for selection as GADAG root. A router advertising the MRT Profile sub-TLV MUST specify a GADAG Root Selection Priority. The range of this priority is [0, 255]. The RECOMMENDED default value of the GADAG Root Selection Priority is 128. The GADAG Root Selection Policy defined as part of a given MRT profile determines how the GADAG Root Selection Priority value is used.
This sub-TLV can occur multiple times if a router supports multiple MRT profiles. This can happen during a network transition. Or it can be used to support different uses of MRT within the same network which may perform better with different profiles.
A given router SHOULD NOT advertise multiple MRT Profile sub-TLVs with the same MRT profile ID. If a router receives multiple MRT Profile sub-TLVs with the same MRT profile ID from the same originator, it MUST use one with the lowest value of GADAG Root Selection Priority.
[I-D.ietf-ospf-mrt] defines MRT signalling extensions for OSPF. In addition to the OSPF version of MRT Profile sub-TLV (which is carried in the OSPF Router Information LSA), it also defines the M-bit (which is carried in the OSPF Router-LSA.) As discussed in [I-D.ietf-ospf-mrt], the M-bit in the Router-LSA ensures that all routers in the area have up-to-date information if a router is downgraded to a software version that does not support MRT and the Router Information LSA.
The problematic scenario that requires the M-bit in the OSPF Router-LSA does not occur in IS-IS. The presence or absence of an IS-IS Router CAPABILITY TLV containing a given MRT Profile sub-TLV in the IS-IS Link State PDU provides enough information for all routers to determine which remote routers support MRT, even after a software version downgrade of remote routers. Therefore, this document does not define a corresponding M-bit for IS-IS.
As a matter of policy, an operator may choose to mark some links as ineligible for carrying MRT traffic. For instance, policy can be made to prevent fast-rerouted traffic from taking those links.
For a link to be marked as ineligible for use in the MRT calculation, it MUST be advertised including the MRT-Ineligible Link sub-TLV in the Extended IS Reachability TLV (TLV #22 defined in [RFC5305] ) corresponding to the ineligible link. The MRT-Ineligible Link sub-TLV is a zero-length sub-TLV as shown below:
TYPE: TBA-MRT-ISIS-2 (To Be Allocated by IANA)
LENGTH: 0
VALUE: None
The presence of the zero-length MRT-Ineligible Link sub-TLV in the Extended IS Reachability TLV indicates that the associated link MUST NOT be used in the MRT calculation for the default topology for all profiles.
[RFC5120] specifies how to support multi-topology routing in IS-IS. The current document specifies how to signal support for MRT in the default routing topology only. The format of the extensions in this document allows the MRT Profile sub-TLV and the MRT-Ineligible Link sub-TLV to be scoped to topologies with non-zero MT-ID at some point in future. However, this document restricts these extensions to apply only to the default topology. The MRT Profile sub-TLV is restricting by explicitly requiring the MT-ID field to be set to zero. The MRT-Ineligible Link sub-TLV is restricted by only allowing it to be included in the Extended IS Reachability TLV (TLV#22) which is scoped to the default topology, and not allowing it to appear TLV#222 (the topology-scoped version of the Extended IS Reachability TLV).
Lifting these restrictions is for further study. Note that the MRT signalling extensions in this document can co-exist with IS-IS multi-topology routing, with the limitation that MRT Red and Blue forwarding trees can only be built for the default topology.
The format of the Controlled Convergence sub-TLV (discussed below) also contains an MT-ID field, allowing a Controlled Convergence sub-TLV to be scoped to a particular topology. This document does not place restrictions on the MT-ID field in the Controlled Convergence sub-TLV. The Controlled Convergence sub-TLV has potential applications that are not limited to MRT, and a topology-scoped FIB compute/install time makes sense on its own.
Section 12.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] describes the need to wait for a configured or advertised period after a network failure to insure that all routers are using their new shortest path trees. Similarly, avoiding micro-forwarding loops during convergence [RFC5715] requires determining the maximum among all routers in the area of the worst-case route computation and FIB installation time. More details on the specific reasoning and need for flooding this value are given in [I-D.atlas-bryant-shand-lf-timers].
A new Controlled Convergence sub-TLV is introduced into the IS-IS Router CAPABILITY TLV (TLV #242 defined in [RFC4971]) to advertise the worst-case time for a router to compute and install all IS-IS routes in the level after a change to a stable network. This advertisement has per level scope, so the S-bit and D-bit of IS-IS Router CAPABILITY TLV MUST be set to zero. The advertisement is scoped by MT-ID, allowing a router supporting multi-topology routing to advertise a different worst-case FIB compute/install time for each topology. This makes sense as the SPF computations and FIB installations for each IGP topology can potentially be done independently of one another, and may have different worst-case compute and install times.
The structure of the Controlled Convergence sub-TLV is shown below:
TYPE: TBA-MRT-ISIS-3 (To Be Allocated by IANA)
LENGTH: 3
VALUE:
MT-ID (2 octets with 4 bits reserved)
FIB compute/install time (1 octet)
Number of octets
+-------------------------------+
|R |R |R |R | MT-ID | 2
+-------------------------------+
| FIB compute/install time | 1
+-------------------------------+
MT-ID is a 12-bit field containing the multi-topology ID.
The FIB compute/install time is the worst-case time the router may take to compute and install all IS-IS routes in the level after a change to a stable network. The value is an unsigned integer in units of milliseconds.
The FIB compute/install time value sent by a router SHOULD be an estimate taking into account network scale or real-time measurements, or both. Advertisements SHOULD be dampened to avoid frequent communication of small changes in the FIB compute/install time.
A router receiving the Controlled Convergence sub-TLV SHOULD estimate the network convergence time as the maximum of the FIB compute/install times advertised by the routers in a level for a given MT-ID, including itself. In order to account for routers that do not advertise the Controlled Convergence sub-TLV, a router MAY use a locally configured minimum network convergence time as a lower bound on the computed network convergence time. A router MAY use a locally configured maximum network convergence time as an upper bound on the computed network convergence time.
MRT sub-TLVs are encapsulated in the Router Capability TLV and advertised using the LS-PDU with level-wide scope. MRT sub-TLVs are optional. If one router does not support MRT, it MUST NOT advertise those sub-TLVs.
Since the advertisement scope of the MRT sub-TLV is level-wide, the D-Bit and S-Bit of the Router Capability TLV MUST be set as 0 when it is advertised. If other sub-TLVs in the Router Capability TLV need different values for those two bits, then the router MUST originate multiple Router Capability TLVs with different bit values.
When MRT-related information is changed for the router or existing IS-IS LSP mechanisms are triggered for refreshing or updating, MRT sub-TLVs MUST be advertised if the router is MRT-Capable.
Based on administrative policy, it may be desirable to exclude certain links from the MRT computation. The MRT-Ineligible sub-TLV is used to advertise which links should be excluded. Note that an interface advertised as MRT-Ineligible by a router is ineligible with respect to all profiles advertised by that router.
The processing associated with MRT extensions SHOULD NOT significantly degrade IS-IS adjacency formation and maintenance or the routing calculation for normal shortest path routes.
MRT sub-TLVs SHOULD be validated like other sub-TLVs when received. MRT sub-TLVs SHOULD also be taken into account for checksum calculations and authentication.
Links advertised as MRT-ineligible using the MRT-Ineligible sub-TLV MUST be excluded from the MRT computation. The removal of individual links from the MRT Island can partition an MRT Island or it can significantly modify the construction of the GADAG and the result MRT Red and Blue trees. Therefore, all routers must perform the same computation using the same set of links.
The MRT Profile sub-TLV, the MRT-Ineligible Link sub-TLV, and the Controlled Convergence sub-TLV defined in this document are compatible with existing implementations of IS-IS. Routers that do not support these extensions are expected to silently ignore them. Router that do support these extensions have mechanisms to recognize routers that don't support these extensions (or are not configured to participate in MRT) and behave accordingly.
[RFC Editor: please remove this section prior to publication.]
Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on implementation status.
The IS-IS extensions in this document do not introduce new security concerns.
The authors would like to thank Shraddha Hegde for her useful suggestions.
IANA is requested to allocate values for the following sub-TLVs types in the IS-IS Router CAPABILITY TLV defined in [RFC4971]: the MRT Profile sub-TLV (TBA-MRT-ISIS-1) and Controlled Convergence sub-TLV (TBA-MRT-ISIS-3). The IANA registry for these sub-TLV types is displayed as "sub-TLVs for TLV 242" (http://www.iana.org/assignments/isis-tlv-codepoints/isis-tlv-codepoints.xhtml#isis-tlv-codepoints-242). The new entries in this registry are shown below.
Value Description Reference -------------- ------------------------------ ------------ TBA-MRT-ISIS-1 MRT Profile sub-TLV [This draft] TBA-MRT-ISIS-3 Controlled Convergence sub-TLV [This draft]
IANA is requested to allocate a value for the following sub-TLVs type in the Extended IS Reachability TLV defined in [RFC5305]: MRT-Ineligible Link sub-TLV (TBA-MRT-ISIS-2). The IANA registry for these sub-TLV types is displayed as "Sub-TLVs for TLVs 22, 23, 141, 222, and 223" (http://www.iana.org/assignments/isis-tlv-codepoints/isis-tlv-codepoints.xhtml#isis-tlv-codepoints-22-23-141-222-223). The new entry in this registry is shown below.
Type Description 22 23 141 222 223 Ref.
-------------- --------------------------- -- -- --- --- --- --------
TBA-MRT-ISIS-2 MRT-Ineligible Link sub-TLV y y n n n [This
draft]
| [I-D.ietf-rtgwg-mrt-frr-algorithm] | Envedi, G., Csaszar, A., Atlas, A., Bowers, C. and A. Gopalan, "Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Reroute", Internet-Draft draft-ietf-rtgwg-mrt-frr-algorithm-06, October 2015. |
| [I-D.ietf-rtgwg-mrt-frr-architecture] | 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", Internet-Draft draft-ietf-rtgwg-mrt-frr-architecture-07, October 2015. |
| [RFC3787] | Parker, J., "Recommendations for Interoperable IP Networks using Intermediate System to Intermediate System (IS-IS)", RFC 3787, DOI 10.17487/RFC3787, May 2004. |
| [RFC5305] | Li, T. and H. Smit, "IS-IS Extensions for Traffic Engineering", RFC 5305, DOI 10.17487/RFC5305, October 2008. |