Routing Area Working Group G. Enyedi, Ed.
Internet-Draft A. Csaszar
Intended status: Informational Ericsson
Expires: April 24, 2014 A. Atlas, Ed.
C. Bowers
Juniper Networks
A. Gopalan
University of Arizona
October 21, 2013
Algorithms for computing Maximally Redundant Trees for IP/LDP Fast-
Reroute
draft-enyedi-rtgwg-mrt-frr-algorithm-04
Abstract
A complete solution for IP and LDP Fast-Reroute using Maximally
Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr-
architecture]. This document defines 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 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 24, 2014.
Copyright Notice
Copyright (c) 2013 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
Enyedi, et al. Expires April 24, 2014 [Page 1]Internet-Draft MRT FRR Algorithm October 2013
(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. Terminology and Definitions . . . . . . . . . . . . . . . . . 4
3. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6
3.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 6
3.2. Finding an Ear and the Correct Direction . . . . . . . . 8
3.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11
3.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 13
3.5. Determining Local-Root and Assigning Block-ID . . . . . . 15
4. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 16
4.1. MRT Island Identification . . . . . . . . . . . . . . . . 17
4.2. Root Selection . . . . . . . . . . . . . . . . . . . . . 18
4.3. Initialization . . . . . . . . . . . . . . . . . . . . . 18
4.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
inheritance . . . . . . . . . . . . . . . . . . . . . . . 19
4.5. Augmenting the GADAG by directing all links . . . . . . . 21
4.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 23
4.6.1. MRT next-hops to all nodes partially ordered with
respect to the computing node . . . . . . . . . . . . 24
4.6.2. MRT next-hops to all nodes not partially ordered with
respect to the computing node . . . . . . . . . . . . 24
4.6.3. Computing Redundant Tree next-hops in a 2-connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 25
4.6.4. Generalizing for graph that isn't 2-connected . . . . 27
4.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 28
4.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 30
4.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 34
5. MRT Lowpoint Algorithm: Complete Specification . . . . . . . 36
6. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 37
6.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 37
datatracker.ietf.org