Internet DRAFT - draft-enyedi-rtgwg-mrt-local-detour
draft-enyedi-rtgwg-mrt-local-detour
Routing Area Working Group G. Enyedi, Ed.
Internet-Draft Ericsson
Intended status: Standards Track October 21, 2013
Expires: April 24, 2014
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.
Enyedi Expires April 24, 2014 [Page 1]
Internet-Draft Abbreviated Title October 2013
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology and Definitions . . . . . . . . . . . . . . . . . 2
3. Problem Description . . . . . . . . . . . . . . . . . . . . . 3
4. Artificial Islands . . . . . . . . . . . . . . . . . . . . . 4
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
6. Security Considerations . . . . . . . . . . . . . . . . . . . 7
7. Normative References . . . . . . . . . . . . . . . . . . . . 7
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 8
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.
Enyedi Expires April 24, 2014 [Page 2]
Internet-Draft Abbreviated Title October 2013
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
Network with GADAG rooted at R.
Figure 1
Enyedi Expires April 24, 2014 [Page 3]
Internet-Draft Abbreviated Title October 2013
There are already possibilities to mitigate the problem presented
above. First, there are heuristics that can be applied in order to
decrease path lengths, thus paths in real networks are usually using
detours not much longer than the shortest paths. Even when
heuristics cannot help (like in the network above), there is still
some room for optimization by selecting the GADAG root better. E.g.
in the previous example selecting node D as a GADAG root can solve
the problem (however it cannot solve anything if we add one more ring
connected to A and R). Finally, note that congestion can be caused
only while IGP is doing the recovery, which is quite fast in most of
the cases, in this way reducing the severity of this situation.
This document describes a mechanism to give strict guarantees that
detour does not get far from the failure. This can be applied for
special situations, when detours would be too long otherwise or in
networks, where bandwidth guarantees are needed to be fulfilled in
all cases.
4. Artificial Islands
MRT-FRR capable routers can handle multiple MRT profiles. MRT
profiles was introduced for handling routers with different
capabilities, even those, which do not support MRT-FRR at all.
Routers supporting the same profile create an MRT-FRR island in the
IGP area.
Each such island has its GADAG and its own redundant trees, which are
only valid in that island. If a packet gets out from an island, it
gets back to the shortest path. If the destination (or the area/AS
border router) is inside the island where the failure happened, it is
guaranteed that packet will never leave the island. Basically
islands are subareas with their own protection.
Currently, islands are there only for handling capability differences
between routers. In this document, we introduce artificial islands,
which are limiting packet detours to a part of the network. In order
to define such an island, operator needs only to configure routers in
the desired subarea to advertise one more profile, which is is not
supported by any other router in the network. Naturally, this
profile does not need to describe new capabilities, but it can differ
from other profiles just in some extra ID field. Therefore profile
descriptor must be extended with such ID field.
Operators may define islands arbitrary; the only restriction is that
such islands must be connected, otherwise they would be considered as
multiple connected islands. Similarly, if an island is split into
disjunct parts due to some failure, such parts can be handled as
disjunct islands. As an example, operators can define one island
Enyedi Expires April 24, 2014 [Page 4]
Internet-Draft Abbreviated Title October 2013
containing the whole IGP area, and some smaller ones for keeping up
local failure handled when needed. When a failure can be handled
locally, a "small" island is used, while there is still the "big"
island containing the whole area for the remaining cases.
As an example of this scheme, consider the the previous network, and
define artificial islands in it in order to keep packets inside the
ring where the failure has happened. The network and the two islands
defined are depicted below. Note that there should be a third island
that contains all the nodes to handle failures that cannot be handled
locally; this third island is not depicted in Figure 2. Also note
that having this third island is not mandatory, it can be not
configured, if operator wants to disable global protection for some
reason.
************ ************
* * * *
* ----F * * J---- *
* | | * | | *
* | | * * | | *
* R -------E------- I *
* | * | * | *
* | * | * | *
* | * D * | *
* | * | * | *
* | * | * | *
* A -------C------- H *
* | | * * | | *
* | | * | | *
* ----B * * G---- *
* * * *
* Island1 * * Island2 *
* * * *
************* *************
A network made up by two islands
Figure 2
Observe that Island1 and Island2 are not disjunct, instead both of
them are containing node C, D and E, in this way making both islands
2-connected. This overlapping is the main difference compared to the
situation when an area is split into two using MRT-ineligible links;
if we would only disable the MRT capability for some links in this
network, at least one of the resulting "subareas" (islands) would be
not 2-connected, thus protection would be impossible in at least one
of them. Moreover thanks to overlapping, it is possible to define
Enyedi Expires April 24, 2014 [Page 5]
Internet-Draft Abbreviated Title October 2013
the third island and use it to provide protection when the PLR and
the destination are not in the same ring (i.e. there is no local
detour).
Although it is useful for protection, note that operator do not
always need to find 2-connected artificial islands, if there are
considerations other than maximum protection. Consider Figure 3 and
suppose that in this network link L-F is not wanted to be used for
local protection for some reason. In this case, the two artificial
islands for local protection are selected as depicted below. If node
M is going down, Island2 is split into two, so no local protection is
possible in this case. (Naturally, selecting Island2 is not
pointless, if any link or any other node than M is going down, there
is still local protection.)
************
--------------L--K *
| * | / *
*******|**** * M *
* | * * | *
* ----F * * J---- *
* | | * | | *
* | | * * | | *
* R -------E------- I *
* | * | * | *
* | * | * | *
* | * D * | *
* | * | * | *
* | * | * | *
* A -------C------- H *
* | | * * | | *
* | | * | | *
* ----B * * G---- *
* * * *
* Island1 * * Island2 *
* * * *
************* *************
A network made up by two islands and a cut-node
Figure 3
If a router is in multiple islands, selecting one for a concrete
failure case is a local decision of the node and not defined in this
document. Vendors may make it possible to assign priority at each
router for the artificial islands created. Moreover, routers may
take other differences into consideration as well, e.g. if there is
Enyedi Expires April 24, 2014 [Page 6]
Internet-Draft Abbreviated Title October 2013
node protecting path in one island but only link protecting in
another one.
Selecting the endpoint of detour is a local decision of MRT-FRR
capable routers, it is not needed to select always the destination/
border router as the endpoint, especially when not all the routers
are supporting MRT-FRR and islands are formed (for details see
[I-D.ietf-rtgwg-mrt-frr-architecture]). If there are artificial
islands the only difference is that a router may belong to multiple
islands, so it may take into consideration all of those islands and
select the best for that failure with respect to arbitrary local
preference.
For MRT-FRR, each router must have two extra addresses/labels per
profile it supports. The situation is the same if there are
artificial islands applied, since a router in multiple islands must
compute the MRTs for each of those islands, and it must be able to
decide which of these trees is used.
5. IANA Considerations
This document includes no request to IANA.
6. Security Considerations
This architecture is not currently believed to introduce new security
concerns.
7. Normative References
[I-D.enyedi-rtgwg-mrt-frr-algorithm]
Envedi, G., Csaszar, A., Atlas, A., cbowers@juniper.net,
c., and A. Gopalan, "Algorithms for computing Maximally
Redundant Trees for IP/LDP Fast- Reroute", draft-enyedi-
rtgwg-mrt-frr-algorithm-03 (work in progress), July 2013.
[I-D.ietf-rtgwg-mrt-frr-architecture]
Atlas, A., Kebler, R., Envedi, G., Csaszar, A., Tantsura,
J., Konstantynowicz, M., and R. White, "An Architecture
for IP/LDP Fast-Reroute Using Maximally Redundant Trees",
draft-ietf-rtgwg-mrt-frr-architecture-03 (work in
progress), July 2013.
Enyedi Expires April 24, 2014 [Page 7]
Internet-Draft Abbreviated Title October 2013
Author's Address
Gabor Sandor Enyedi (editor)
Ericsson
Konyves Kalman krt 11
Budapest 1097
Hungary
Email: Gabor.Sandor.Enyedi@ericsson.com
Enyedi Expires April 24, 2014 [Page 8]
