Artificial MRT Islands for Keeping Detours Local
draft-enyedi-rtgwg-mrt-local-detour-00

Abstract

IP and LDP Fast ReRoute using Maximally Redundant trees was defined in [I-D.ietf-rtgwg-mrt-frr-architecture]. In this document we add a simple extension to that technique, which can guarantee to keep detours in the part of the network, where the failure happened.

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 (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
• 2. Terminology and Definitions
• 3. Problem Description
• 4. Artificial Islands
• 5. IANA Considerations
• 6. Security Considerations
• 7. Normative References
• Author's Address

1. Introduction

In the case of failure, Fast ReRoute using Maximally Redundant Trees (MRT-FRR) [I-D.ietf-rtgwg-mrt-frr-architecture] use detours defined by two maximally redundant trees, which are not related to shortest paths at all. Although there are heuristics for decreasing path lengths, which are sufficient in almost all situations, there is no strict guarantee to keep failure handling local. This means that detours may cause temporal congestion even in those parts of the network, which are far from the original failure.

This document defines a possible solution by using multiple pairs of maximally redundant trees in an IGP area. Our solution introduce artificial "subareas", each having its own recovery, and use them to provide the best possible protection. If both the Point of Local Repair (PLR) and the destination are in the same subarea, the detour can simply use one of the trees of that subarea, in this way never leaving the surroundings of the failure.

2. Terminology and Definitions

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 along the second tree share the minimum number of nodes and the minimum number of links. Each such shared node is a cut-node. Any shared links are cut-links.

2-connected:

A graph that has no cut-nodes. This is a graph that requires at least two nodes to be removed before gets partitioned.

block:

Either a maximally 2-connected (induced) subgraph, a cut-link with with its endpoints, or an isolated node.

DAG:

Directed Acyclic Graph - a digraph containing no directed cycle.

ADAG:

Almost Directed Acyclic Graph - a digraph that can be transformed into a DAG whith removing a single node (the root node).

GADAG:

Generalized ADAG - a digraph, which has only ADAGs as all of its blocks.

PLR:

Point of Local Repair - the node neighboring the failed resource (which can be a node or a link), and which do the rerouting.

Cut-node:

A node is a cut-node, if removing it partitions the network.

Cut-link:

A link is a cut-link, if removing it partitions the network.

3. Problem Description

Consider the network and GADAG depicted in Figure 1 (for GADAG computation and finding FRR paths using a GADAG consult [I-D.enyedi-rtgwg-mrt-frr-algorithm]). Suppose that node H wants to send some packets to node I, but the link between them went down. Since node H is definitely lesser than node I, the detour must be the one that goes through R, i.e. H->G->C->B->A->R->F->E->J->I, even if there was a much shorter one through node D. The problem here is not that such path is long, but that the traffic may get far away from the failure, thus congestion may occur in any part of the network.

----F   J----         ----F    J<---
|   |   |   |         |   ^    |   |
|   |   |   |         V   |    |   |
R   --E--   I         R   --E<--   I
|     |     |         |     ^      ^
|     |     |         |     |      |
|     D     |         |     D      |
|     |     |         |     ^      |
|     |     |         V     |      |
A   --C--   H         A   ->C--    H
|   |   |   |         |   |   |    ^
|   |   |   |         |   |   V    |
----B   G----         --->B   G-----
  
  A network       The GADAG rooted at R
            

************     ************
*           *   *           *
*  ----F     * *     J----  *
*  |   |      *      |   |  *
*  |   |     * *     |   |  *
*  R   -------E-------   I  *
*  |        * | *        |  *
*  |        * | *        |  *
*  |        * D *        |  *
*  |        * | *        |  *
*  |        * | *        |  *
*  A   -------C-------   H  *
*  |   |     * *     |   |  *
*  |   |      *      |   |  *
*  ----B     * *     G----  *
*           *   *           *
*  Island1  *   *  Island2  *
*           *   *           *
*************   *************
  
            

		         ************
       --------------L--K   *
       |         *   | /    *
*******|****     *   M      *
*      |    *   *    |      *
*  ----F     * *     J----  *
*  |   |      *      |   |  *
*  |   |     * *     |   |  *
*  R   -------E-------   I  *
*  |        * | *        |  *
*  |        * | *        |  *
*  |        * D *        |  *
*  |        * | *        |  *
*  |        * | *        |  *
*  A   -------C-------   H  *
*  |   |     * *     |   |  *
*  |   |      *      |   |  *
*  ----B     * *     G----  *
*           *   *           *
*  Island1  *   *  Island2  *
*           *   *           *
*************   *************