An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)
RFC 7811
|
| Document |
Type |
|
RFC - Proposed Standard
(June 2016; No errata)
|
|
Last updated |
|
2016-06-16
|
|
Replaces |
|
draft-enyedi-rtgwg-mrt-frr-algorithm
|
|
Stream |
|
IETF
|
|
Formats |
|
plain text
pdf
html
bibtex
|
|
Reviews |
|
|
| Stream |
WG state
|
|
Submitted to IESG for Publication
(wg milestone:
Jul 2015 - Submit specification...
)
|
|
Document shepherd |
|
Janos Farkas
|
|
Shepherd write-up |
|
Show
(last changed 2015-12-10)
|
| IESG |
IESG state |
|
RFC 7811 (Proposed Standard)
|
|
Consensus Boilerplate |
|
Yes
|
|
Telechat date |
|
|
|
Responsible AD |
|
Alvaro Retana
|
|
Send notices to |
|
"Janos Farkas" <janos.farkas@ericsson.com>,aretana@cisco.com
|
| IANA |
IANA review state |
|
Version Changed - Review Needed
|
|
IANA action state |
|
In Progress
|
Internet Engineering Task Force (IETF) G. Enyedi
Request for Comments: 7811 A. Csaszar
Category: Standards Track Ericsson
ISSN: 2070-1721 A. Atlas
C. Bowers
Juniper Networks
A. Gopalan
University of Arizona
June 2016
An Algorithm for Computing IP/LDP Fast Reroute
Using Maximally Redundant Trees (MRT-FRR)
Abstract
This document supports the solution put forth in "An Architecture for
IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)"
(RFC 7812) by defining the associated MRT Lowpoint algorithm that is
used in the Default MRT Profile to compute both the necessary
Maximally Redundant Trees with their associated next hops and the
alternates to select for MRT-FRR.
Status of This Memo
This is an Internet Standards Track document.
This document is a product of the Internet Engineering Task Force
(IETF). It represents the consensus of the IETF community. It has
received public review and has been approved for publication by the
Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 7841.
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.
Enyedi, et al. Standards Track [Page 1]
RFC 7811 MRT-FRR Algorithm June 2016
Copyright Notice
Copyright (c) 2016 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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5
3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5
4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6
4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7
4.2. Finding an Ear and the Correct Direction . . . . . . . . 8
4.3. Lowpoint Values and Their Uses . . . . . . . . . . . . . 11
4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14
4.5. Determining Localroot and Assigning Block-ID . . . . . . 16
5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18
5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18
5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21
5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22
5.5. Constructing the GADAG Using Lowpoint Inheritance . . . . 23
5.6. Augmenting the GADAG by Directing All Links . . . . . . . 25
5.7. Compute MRT Next Hops . . . . . . . . . . . . . . . . . . 29
5.7.1. MRT Next Hops to All Nodes Ordered with Respect to
the Computing Node . . . . . . . . . . . . . . . . . 29
5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect
to the Computing Node . . . . . . . . . . . . . . . . 30
5.7.3. Computing Redundant Tree Next Hops in a 2-Connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 31
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.8. Identify MRT Alternates . . . . . . . . . . . . . . . . . 36
5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44
5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 45
5.9.2. Computing If an Island Neighbor (IN) Is Loop-Free . . 45
5.9.3. Computing MRT Next Hops for Proxy-Nodes . . . . . . . 47
5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53
Enyedi, et al. Standards Track [Page 2]
RFC 7811 MRT-FRR Algorithm June 2016
Show full document text