< draft-thubert-rtgwg-arc-01.txt   draft-thubert-rtgwg-arc-02.txt >
RTGWG P. Thubert, Ed. RTGWG P. Thubert, Ed.
Internet-Draft Cisco Internet-Draft Cisco
Intended status: Standards Track P. Bellagamba Intended status: Standards Track P. Bellagamba
Expires: April 19, 2014 Cisco Systems Expires: January 3, 2015 Cisco Systems
October 18, 2013 July 2, 2014
Available Routing Constructs Available Routing Constructs
draft-thubert-rtgwg-arc-01 draft-thubert-rtgwg-arc-02
Abstract Abstract
This draft introduces the concept of ARC, a two-edged routing This draft introduces the concept of ARC, a two-edged routing
construct that forms its own fault isolation and recovery domain. construct that forms its own fault isolation and recovery domain.
The new paradigm can be leveraged to improve the network utilization The new paradigm can be leveraged to improve the network utilization
and resiliency for unicast and multicast traffic in multiple and resiliency for unicast and multicast traffic in multiple
environments. environments.
Requirements Language Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC "OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119]. 2119 [RFC2119].
Status of this Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 19, 2014. This Internet-Draft will expire on January 3, 2015.
Copyright Notice Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (http://trustee.ietf.org/ Provisions Relating to IETF Documents
license-info) in effect on the date of publication of this document. (http://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. Code Components carefully, as they describe your rights and restrictions with respect
extracted from this document must include Simplified BSD License text to this document. Code Components extracted from this document must
as described in Section 4.e of the Trust Legal Provisions and are include Simplified BSD License text as described in Section 4.e of
provided without warranty as described in the Simplified BSD License. the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. ARC Set representations . . . . . . . . . . . . . . . . . . . 6 3. ARC Set representations . . . . . . . . . . . . . . . . . . . 7
4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 16 4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1. Load Balancing . . . . . . . . . . . . . . . . . . . . . . 16 4.1. Load Balancing . . . . . . . . . . . . . . . . . . . . . 9
4.1.1. Routing Hierarchies . . . . . . . . . . . . . . . . . 16 4.1.1. Routing Hierarchies . . . . . . . . . . . . . . . . . 10
5. Lowest ARC First . . . . . . . . . . . . . . . . . . . . . . . 16 5. Lowest ARC First . . . . . . . . . . . . . . . . . . . . . . 10
5.1. Init . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.1. Init . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2. Growing Trees . . . . . . . . . . . . . . . . . . . . . . 17 5.2. Growing Trees . . . . . . . . . . . . . . . . . . . . . . 11
5.3. Being Safe . . . . . . . . . . . . . . . . . . . . . . . . 17 5.3. Being Safe . . . . . . . . . . . . . . . . . . . . . . . 11
5.4. Bending An ARC . . . . . . . . . . . . . . . . . . . . . . 18 5.4. Bending An ARC . . . . . . . . . . . . . . . . . . . . . 12
5.5. Orienting Links . . . . . . . . . . . . . . . . . . . . . 19 5.5. Orienting Links . . . . . . . . . . . . . . . . . . . . . 13
5.6. Looping or recursing . . . . . . . . . . . . . . . . . . . 19 5.6. Looping or recursing . . . . . . . . . . . . . . . . . . 13
6. Forwarding Along An ARC Set . . . . . . . . . . . . . . . . . 20 6. Forwarding Along An ARC Set . . . . . . . . . . . . . . . . . 14
6.1. Control Plane Recovery . . . . . . . . . . . . . . . . . . 20 6.1. Control Plane Recovery . . . . . . . . . . . . . . . . . 14
6.2. Data Plane Recovery . . . . . . . . . . . . . . . . . . . 21 6.2. Data Plane Recovery . . . . . . . . . . . . . . . . . . . 15
7. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 22 7. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 16
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
9. Security Considerations . . . . . . . . . . . . . . . . . . . 22 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 16
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 16
11.1. Normative References . . . . . . . . . . . . . . . . . . 22 11.1. Normative References . . . . . . . . . . . . . . . . . . 16
11.2. Informative References . . . . . . . . . . . . . . . . . 22 11.2. Informative References . . . . . . . . . . . . . . . . . 17
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17
1. Introduction 1. Introduction
Traditional routing and forwarding uses the concept of path as the Traditional routing and forwarding uses the concept of path as the
basic routing paradigm to get a packet from a source to a destination basic routing paradigm to get a packet from a source to a destination
by following an ordered sequence of arrows between intermediate by following an ordered sequence of arrows between intermediate
nodes. In this serial design, a path is broken as soon as a single nodes. In this serial design, a path is broken as soon as a single
arrow is, and getting around a breakage can require path arrow is, and getting around a breakage can require path
recomputation, network reconvergence, and incur delays to till recomputation, network reconvergence, and incur delays to till
service is restored. service is restored.
skipping to change at page 3, line 25 skipping to change at page 3, line 31
This draft introduces the concept of an Available Routing Construct This draft introduces the concept of an Available Routing Construct
(ARC) as a routing construct made of a bidirectional sequence of (ARC) as a routing construct made of a bidirectional sequence of
nodes and links with 2 outgoing edges, so that, upon a single nodes and links with 2 outgoing edges, so that, upon a single
breakage, each lively node in along ARC can still reach one of the breakage, each lively node in along ARC can still reach one of the
outgoing edges. outgoing edges.
The routing graph to reach a certain destination is expressed as a The routing graph to reach a certain destination is expressed as a
cascade of ARCs, each ARC providing its own independent domain of cascade of ARCs, each ARC providing its own independent domain of
fault isolation and recovery. Unicast traffic may enter an ARC via fault isolation and recovery. Unicast traffic may enter an ARC via
any node but it may only leave the ARC through one of its two edges. any node but it may only leave the ARC through one of its two edges.
One node along the ARC is designated as the cursor. In normal One node along the ARC is designated as the Cursor. In normal
unicast operations, the traffic inside an ARC flows away from the unicast operations, the traffic inside an ARC flows away from the
cursor towards an edge. Upon a failure, packets may bounce on the Cursor towards an edge. Upon a failure, packets may bounce on the
breakage point and flow the other way along the ARC to take the other breakage point and flow the other way along the ARC to take the other
exit. exit.
Aa a result an ARC is resilient to any single failure, and the Aa a result an ARC is resilient to any single failure, and the
recovery can be driven either from the data plane or the control recovery can be driven either from the data plane or the control
plane. A second failure occurring within a same ARC will isolate an plane. A second failure occurring within a same ARC will isolate an
ARC segment. This can be further corrected from the control plane by ARC segment. This can be further corrected from the control plane by
reversing all the incoming Edges in a process that might recurse till reversing all the incoming Edges in a process that might recurse till
an exit is found. When ARC reversal is applied, an ARC topology is an exit is found. When ARC reversal is applied, an ARC topology is
resilient to some cases of Shared Risk Link Group (SRLG) failures. resilient to some cases of Shared Risk Link Group (SRLG) failures.
skipping to change at page 3, line 49 skipping to change at page 4, line 6
This draft presents the concept and provides an intuition of how ARCs This draft presents the concept and provides an intuition of how ARCs
can simplify the operation and improve the network utilization and can simplify the operation and improve the network utilization and
resiliency for all sorts of traffic in multiple environments, but resiliency for all sorts of traffic in multiple environments, but
defers to further documents to elaborate on the algorithms and defers to further documents to elaborate on the algorithms and
optimizations in the different application domains. optimizations in the different application domains.
For instance, ARCs can also be used in datacenters for the purpose of For instance, ARCs can also be used in datacenters for the purpose of
fast-reroute, or within a service provider network to simplify load fast-reroute, or within a service provider network to simplify load
balancing operations or leverage optimally the ring topologies balancing operations or leverage optimally the ring topologies
[RFC5921]. An ARC topology can be flooded over itself and serve as a [RFC5921]. An ARC topology can be flooded over itself and serve as a
backbone for reliable multicasting operations. backbone for bicasted [I-D.thubert-rtgwg-arc-bicast] and reliable
multicasted operations.
2. Terminology 2. Terminology
The definition of the constituent parts of the "OAM" term is found in
[RFC6291].
The draft uses the following terminology: The draft uses the following terminology:
ARC: Available Routing Construct. An ARC is a loopless ordered set ARC: Available Routing Construct. An ARC is a loopless ordered set
of nodes and links whereby traffic may enter via any node in the of nodes and links whereby traffic may enter via any node in the
ARC but may only leave the ARC through either one of the ARC ARC but may only leave the ARC through either one of the ARC
edges. edges.
Comb: An ARC generalization: a Comb is a n-edged loopless set of Comb: An ARC generalization: a Comb is a n-edged loopless set of
nodes and links with n >= 2; traffic may enter via any node in the nodes and links with n >= 2; traffic may enter via any node in the
Comb but may only exit the Comb through one of its n edges. A Comb but may only exit the Comb through one of its n edges. A
Comb comes with a walk operation that enables to attempt to exit Comb comes with a walk operation that enables to attempt to exit
via every edge and to discover when all have been tried. via every edge and to discover when all have been tried.
Cursor: A virtual point along an ARC that can be located on a node or Cursor: A virtual point along an ARC that can be located on a node
on a link between 2 nodes. In normal operations, the traffic or on a link between 2 nodes. In normal operations, the traffic
along the ARC flows away from its Cursor. If the cursor is a along the ARC flows away from its Cursor. If the Cursor is a
node, then traffic can be distributed on both sides. The Cursor node, then traffic can be distributed on both sides. The Cursor
may be moved to change the way traffic is load balanced along an may be moved to change the way traffic is load balanced along an
ARC. It may also be placed at the location of a failure to direct ARC. It may also be placed at the location of a failure to direct
traffic away from that point. traffic away from that point.
ARC Node: A Node that belongs to an ARC. ARC Node: A Node that belongs to an ARC.
Edge ARC Node: An ARC Node at an edge of its ARC. An Edge ARC Node Edge ARC Node: An ARC Node at an edge of its ARC. An Edge ARC Node
is a node via wich traffic can exit the ARC. is a node via wich traffic can exit the ARC.
Edge Link: A directed link outgoing from an Edge ARC Node. Traffic Edge Link: A directed link outgoing from an Edge ARC Node. Traffic
can only exit from an ARC via an Edge Link. An Edge Link does not can only exit from an ARC via an Edge Link. An Edge Link does not
accept traffic into an ARC. accept traffic into an ARC.
Intermediate ARC Node: A node that is not at an edge of an ARC. A Intermediate ARC Node: A node that is not at an edge of an ARC. A
Intermediate ARC Node node that can receive traffic and forward Intermediate ARC Node node that can receive traffic and forward
traffic between its adjacent nodes. traffic between its adjacent nodes.
Intermediate Link: A link between two Intermediate ARC Nodes. An Intermediate Link: A link between two Intermediate ARC Nodes. An
Intermediate Link is reversible, meaning that traffic is allowed Intermediate Link is reversible, meaning that traffic is allowed
in both directions though an individual packet is constrained in in both directions though an individual packet is constrained in
the way its direction is reversed. For stable links such as wired the way its direction is reversed. For stable links such as wired
links, the typical constraint is that the direction of a packet links, the typical constraint is that the direction of a packet
may be reversed at most once along a given ARC. may be reversed at most once along a given ARC.
Collapsed ARC: An ARC that is formed of a single node. This node is Collapsed ARC: An ARC that is formed of a single node. This node is
altogether the cursor and both Edge Nodes. This implies that the altogether the Cursor and both Edge Nodes. This implies that the
node has at least 2 outgoing links to 2 different Safe Nodes. node has at least 2 outgoing links to 2 different Safe Nodes.
| |
| |
V V
C+EAN C+EAN
/|\ /|\
/ | \ / | \
| V | | V |
V V V V
E: Edge ARC Node -| collapsed in a single node E: Edge ARC Node -| collapsed in a single node
C: Cursor -| C: Cursor -|
Infrastructure ARC: An ARC that is formed of more than one node, Figure 1: Collapsed ARC
Infrastructure ARC: An ARC that is formed of more than one node,
which also means that the Edge Nodes are different nodes. which also means that the Edge Nodes are different nodes.
| \ | | | \ | |
| \ | | | | \ | | |
V V V | V V V |
_->IAN<---->IAN<---->IAN<---->IAN<-_ | _->IAN<---->IAN<---->IAN<---->IAN<-_ |
/ + C \ | / + C \ |
/ \| / \|
V V V V
EAN EAN EAN EAN
| /|\ | /|\
| / | \ | / | \
| | V | | | V |
V V V V V V
IAN: Intermediate ARC Node -| IAN: Intermediate ARC Node -|
EAN: Edge ARC Node |- All are Safe Nodes EAN: Edge ARC Node |- All are Safe Nodes
C: Cursor -| C: Cursor -|
DAG: Directed Acyclic Graph. Figure 2: Infrastructure ARC
ARC Set (or Cascade): A DAG with ARCs as vertices. In the DAG, an DAG: Directed Acyclic Graph.
ARC Set (or Cascade): A DAG with ARCs as vertices. In the DAG, an
edge between ARC A and ARC B corresponds to a link from an Edge edge between ARC A and ARC B corresponds to a link from an Edge
ARC Node in ARC A and an arbitrary ARC Node in ARC B. Note that by ARC Node in ARC A and an arbitrary ARC Node in ARC B. Note that
definition, an ARC has at least 2 outgoing Edge Links, one per by definition, an ARC has at least 2 outgoing Edge Links, one per
Edge Node, and maybe more if an Edge Node has multiple outgoing Edge Node, and maybe more if an Edge Node has multiple outgoing
Edge Links. All vertices in the DAG have 2 forwarding solutions, Edge Links. All vertices in the DAG have 2 forwarding solutions,
even the ARC closest to the destination. even the ARC closest to the destination.
Omega: the abstract destination (== root) of an ARC Set. Omega: the abstract destination (== root) of an ARC Set.
ARC Height: An arbitrary distance from Omega that is associated to an ARC Height: An arbitrary distance from Omega that is associated to
ARC. The Height of an ARC must be more than the Height of any of an ARC. The Height of an ARC must be more than the Height of any
the ARCs it terminates into. The order of ARC formation by a of the ARCs it terminates into. The order of ARC formation by a
given algorithm can be used as a Height whereby an ARC is always given algorithm can be used as a Height whereby an ARC is always
strictly higher or lower than another. strictly higher or lower than another.
Buttressing ARC: A split ARC that is merged into another ARC at one Buttressing ARC: A split ARC that is merged into another ARC at one
edge. An ARC and one or more Buttressing ARCs form a Comb edge. An ARC and one or more Buttressing ARCs form a Comb
construct that is resilient to additional breakages. A construct that is resilient to additional breakages. A
Buttressing ARC may be applied to an ARC or a Comb iff traffic Buttressing ARC may be applied to an ARC or a Comb iff traffic
outgoing the Buttressing ARC Edge always reaches in an ARC that is outgoing the Buttressing ARC Edge always reaches in an ARC that is
lower than this ARC, or Omega. lower than this ARC, or Omega.
| \ | | | \ | |
| \ | | | | \ | | |
V V V | V V V |
_->IAN<---->IAN<---->IAN<---->IAN<-_----->IAN<-_ _->IAN<---->IAN<---->IAN<---->IAN<-_----->IAN<-_
/ + C \ | \ / + C \ | \
/ \| \ / \| \
V V V V V V
EAN EAN EAN EAN EAN EAN
| /|\ | | /|\ |
| / | \ | | / | \ |
| | V | | | | V | |
V V V V V V V V
Safe Node: A node is Safe if there is no single point of failure - Figure 3: Comb with Buttressing ARC
Safe Node: A node is Safe if there is no single point of failure -
apart from the node itself - on its way to Omega. From this apart from the node itself - on its way to Omega. From this
definition, a node is Safe if it has at least two non-congruent definition, a node is Safe if it has at least two non-congruent
paths to two different other Safe Nodes. It results that a Safe paths to two different other Safe Nodes. It results that a Safe
node that is not Omega has at least two completely disjunct paths node that is not Omega has at least two completely disjunct paths
to Omega. When an ARC has been successfully constructed, all its to Omega. When an ARC has been successfully constructed, all its
nodes become safe with respect to the Omega for which the ARC was nodes become safe with respect to the Omega for which the ARC was
constructed. By extension for a collapsed path Omega is deemed to constructed. By extension for a collapsed path Omega is deemed to
be Safe, that is any node that pertains in Omega is a Safe Node. be Safe, that is any node that pertains in Omega is a Safe Node.
?-S: A node N is deemed dependent on a node S or S-dependent (denoted ?-S: A node N is deemed dependent on a node S or S-dependent
as ?-S) if S is the last single point of failure along N's (denoted as ?-S) if S is the last single point of failure along
shortest path to Omega. N's shortest path to Omega.
3. ARC Set representations 3. ARC Set representations
An ARC Set can be represented in a number of fashions: An ARC Set can be represented in a number of fashions:
Graph View: Graph View:
H2<==>H<==>H1<---I--->J1<==>J--->K1<===>K H2<==>H<==>H1<---I--->J1<==>J--->K1<===>K
| | | | | | | | | |
| | | | | | | | | |
skipping to change at page 9, line 19 skipping to change at page 7, line 39
D1<==>D<==>D3 E1<==>E F1<==>F<==>F2 G D1<==>D<==>D3 E1<==>E F1<==>F<==>F2 G
| | | | | | / \ | | | | | | / \
| | | | | | / \ | | | | | | / \
V V V V V V V V V V V V V V V V
B1<==>B2<==>B3<==>B--->A<==>A1<------C2<==>C<==>C4 B1<==>B2<==>B3<==>B--->A<==>A1<------C2<==>C<==>C4
| | | | | | | |
| | | | | | | |
| V V | | V V |
+--------------------> Omega <-------------------+ +--------------------> Omega <-------------------+
Figure 4: Routing Graph View
This representation is similar to a classical routing graph with This representation is similar to a classical routing graph with
the pecularity that some Links are marked reversible. An ARC is the pecularity that some Links are marked reversible. An ARC is
represented as a sequence of reversible links. The node that represented as a sequence of reversible links. The node that
holds the cursor is also indicated somehow. holds the Cursor is also indicated somehow.
ARC View: ARC View:
+========I========+ +========I========+
| | | |
| +====J====+ | +====J====+
| | | | | |
+====H====+ | +=====K=====+ +====H====+ | +=====K=====+
| | | | | | | | | |
+====D====+ +====E====+ +====F====+ +====G====+ +====D====+ +====E====+ +====F====+ +====G====+
| | | | | | | | | | | | | | | |
+=========B=========+ | | +=========C=========+ +=========B=========+ | | +=========C=========+
| | | | | | | | | | | |
| +======A=======+ | | +======A=======+ |
| | | | | | | |
------------------------------------------------------------------Omega ------------------------------------------------------------------Omega
Figure 5: ARC Representation
This representation is similar to a classical routing graph with This representation is similar to a classical routing graph with
the pecularity that some Links are marked reversible. An ARC is the pecularity that some Links are marked reversible. An ARC is
represented as a sequence of reversible links. represented as a sequence of reversible links.
Collapsed DAG view: Collapsed DAG view:
+====+ +====+ +====+ +====+ +====+ +====+ +====+ +====+
| H | <--- | I | ---> | J | ---> | K | | H | <--- | I | ---> | J | ---> | K |
| \__ | ___/ | | \__ | ___/ |
| \ | / | | \ | / |
V _| V |_ V V _| V |_ V
+====+ +====+ +====+ +====+ +====+ +====+ +====+ +====+
| D | | E | | F | <--- | G | | D | | E | | F | <--- | G |
\ \ __/ \__ __/ \__ / / \ \ __/ \__ __/ \__ / /
\ \ / \ / \ / / \ \ / \ / \ / /
_| _| |_ _| |_ _| |_ |_ _| _| |_ _| |_ _| |_ |_
+====+ +====+ +====+ +====+ +====+ +====+
| B | ---> | A | <--- | C | | B | ---> | A | <--- | C |
| | | | | | | |
V V V V V V V V
------------------------------------------------------------------Omega ------------------------------------------------------------------Omega
Figure 6: ARC DAG
A DAG representation whereby an ARC is abstracted as a vertice and A DAG representation whereby an ARC is abstracted as a vertice and
links between ARCs are shown as directed edges. This way, the links between ARCs are shown as directed edges. This way, the
reversible links are omitted and the graph is simplified. It can reversible links are omitted and the graph is simplified. It can
be noted that even the vertice closest to Omega has 2 non- be noted that even the vertice closest to Omega has 2 non-
congruent forwarding solutions, that is Heir Links to Omega. congruent forwarding solutions, that is Heir Links to Omega.
4. Applicability 4. Applicability
This section has to be refined. ARCs probably apply to both unicast This section has to be refined. ARCs probably apply to both unicast
and multicast and the authors expect further documents to explain how and multicast and the authors expect further documents to explain how
that is done. The examples below are provided as an indication but that is done. The examples below are provided as an indication but
is not limiting the field of applications. is not limiting the field of applications.
4.1. Load Balancing 4.1. Load Balancing
In normal conditions, only the cursor may distribute its traffic In normal conditions, only the Cursor may distribute its traffic
between the two Edge Nodes. If an Edge Node is still congested after between the two Edge Nodes. If an Edge Node is still congested after
the cursor forwards all its traffic towards the other Edge Node, then the Cursor forwards all its traffic towards the other Edge Node, then
the cursor can be moved towards the congested Edge in order to derive the Cursor can be moved towards the congested Edge in order to derive
even more traffic towards the other Edge. If both Edges are even more traffic towards the other Edge. If both Edges are
congested, then a backpressure can be applied on the incoming ARCs so congested, then a back-pressure can be applied on the incoming ARCs
that they move their own traffic towards their own alternate Edge. so that they move their own traffic towards their own alternate Edge.
The process may recurse. The process may recurse.
It is expected that control frames similar to those defined for MPLS
Fault Management Operations, Administration, and Maintenance (OAM)
[RFC6291] will echo from Edge Node to Edge Node provide information
such as liveliness and load. In order to establish a control loop
between the Edge Nodes and the Cursor, the OAM frame would carry at
least a logical information whether:
The Edge Node is capable of forwarding data down to the next ARC
the load may be increased (e.g. rate below threshold including
hysteresis)
the load should be decreased (e.g. congestion observed as
increased latency or buffer bloat)
If the load should be decreased towards of congested Edge Node and
the load may be increased towards the other then the Cursor may
adjust its balancing of the load, or move Cursor ownership towards
the congested Edge if it is already redirecting all the traffic
towards the non-congested Edge.
If the Cursor is balancing traffic away from the default position due
to a past congestion notification and the Edge that was congested now
reports that the load may be increased, then the reverse operation
can happen and the Cursor may rebalance the load back to the original
position taking the reverse steps as above.
If the OAM can not be forwarded due to a link or a node failure, then
the last node towards the broken Edge becomes Cursor and echoes the
OAM frames advertising that it is an Edge node that is blocked, not
capable of forwarding data down to the next ARC.
If both Edges are experiencing a congestion then the condition should
be reported to the Edge Nodes of all incoming ARCs. Same goes when
both Edges are blocked.
4.1.1. Routing Hierarchies 4.1.1. Routing Hierarchies
The ARC methods may be used to build and/or leverage routing The ARC methods may be used to build and/or leverage routing
hierarchies, allowing high availability at multiple hierarchical hierarchies, allowing high availability at multiple hierarchical
levels. In one hand, the view of an ARC Set can be simplified by levels. In one hand, the view of an ARC Set can be simplified by
abstracting an ARC as a node in a DAG. The view of the routing abstracting an ARC as a node in a DAG. The view of the routing
topology is thus simplified, as illustrated in Figure 6. In the topology is thus simplified, as illustrated in Figure 6. In the
other hand, ARCs may be used inside a subtopology, such as a ring, to other hand, ARCs may be used inside a sub-topology, such as a ring,
enable forwarding inside a ring towards a next ring. Then, to enable forwarding inside a ring towards a next ring. Then,
abstracting a full ring as a node, ARCs can be applied to a graph of abstracting a full ring as a node, ARCs can be applied to a graph of
rings, providing another level of redundancy and an abstract end to rings, providing another level of redundancy and an abstract end to
end path computation that is represented as a cascade of ARCs of end path computation that is represented as a cascade of ARCs of
rings. rings.
5. Lowest ARC First 5. Lowest ARC First
The open Lowest ARC First(oLAF) algorithm is presented below in such The open Lowest ARC First(oLAF) algorithm is presented below in such
a way as to help the reader figure how an ARC Set can be obtained but a way as to help the reader figure how an ARC Set can be obtained but
not in a computer-optimized fashion that is left to be determined. not in a computer-optimized fashion that is left to be determined.
skipping to change at page 18, line 51 skipping to change at page 12, line 51
that is higher than the other end, then this ARC may be merged at that is higher than the other end, then this ARC may be merged at
the Safe Node with its original ARC, in order to form a Comb the Safe Node with its original ARC, in order to form a Comb
construct whereby this ARC is a Buttressing ARC of the Comb. The construct whereby this ARC is a Buttressing ARC of the Comb. The
resulting Comb conserves the height on the original ARC or Comb resulting Comb conserves the height on the original ARC or Comb
that it extends. that it extends.
o The ARC is built by adjoining the two non-congruent paths that we o The ARC is built by adjoining the two non-congruent paths that we
isolated for the selected node. isolated for the selected node.
o The selected node is the node farthest from Omega in the resulting o The selected node is the node farthest from Omega in the resulting
ARC, so we make it the cursor. ARC, so we make it the Cursor.
o The link between the selected node and the selected neighbor would o The link between the selected node and the selected neighbor would
not have been used in a classical reverse SPF tree. Here, we have not have been used in a classical reverse SPF tree. Here, we have
determined that this link is in fact critical to connect 2 zones determined that this link is in fact critical to connect 2 zones
of the network (the DSets) that can act as a back up for one of the network (the DSets) that can act as a back up for one
another in case of the failure of their respective single points another in case of the failure of their respective single points
of failure (the Safe Nodes). of failure (the Safe Nodes).
o Because the ARC can be used in both directions, each AN along the o Because the ARC can be used in both directions, each AN along the
ARC has two non-congruent paths to the Safe Nodes that the ARC ARC has two non-congruent paths to the Safe Nodes that the ARC
terminates into. So it is a Safe Node. We create individual terminates into. So it is a Safe Node. We create individual
DSets for each AN and we move the AN to its own DSet. DSets for each AN and we move the AN to its own DSet.
5.5. Orienting Links 5.5. Orienting Links
For each ARC Node along the ARC: For each ARC Node along the ARC:
o any link (there can be zero for a collapsed ARC, one for an Edge o any link (there can be zero for a collapsed ARC, one for an Edge
AN or two of them for a Intermediate AN) between this AN and a AN or two of them for a Intermediate AN) between this AN and a
next AN along this ARC is made an Intermediate Link, that is, next AN along this ARC is made an Intermediate Link, that is,
reversible. The normal direction, away from the cursor, preserves reversible. The normal direction, away from the Cursor, preserves
the shortest path. the shortest path.
o If this AN is an Edge AN for this ARC, than all links off this o If this AN is an Edge AN for this ARC, than all links off this
node that terminate in a Safe Node are made Edge Links, that is, node that terminate in a Safe Node are made Edge Links, that is,
outgoing but not reversible. outgoing but not reversible.
o All the other links left undertermined. o All the other links left undertermined.
The nodes left in the Dependent Sets but the owner Safe Node are The nodes left in the Dependent Sets but the owner Safe Node are
still not Safe. They are moved back to the original Set of Nodes to still not Safe. They are moved back to the original Set of Nodes to
skipping to change at page 19, line 55 skipping to change at page 14, line 6
consider the Dependent Sets that we have put together. In a consider the Dependent Sets that we have put together. In a
biconnected graph, there should be one set per node and one node per biconnected graph, there should be one set per node and one node per
set, denoting that every node is a Safe Node. set, denoting that every node is a Safe Node.
If some portion of the graph is monoconnected, then each If some portion of the graph is monoconnected, then each
monoconnected portion forms the Dependent Set of the Safe Node that monoconnected portion forms the Dependent Set of the Safe Node that
is its single point of failure. In order to be maximally redundant, is its single point of failure. In order to be maximally redundant,
we need to form the ARCs again, within the Dependent Set. we need to form the ARCs again, within the Dependent Set.
To do so, we remove the Safe Node from the Dependent set and make it To do so, we remove the Safe Node from the Dependent set and make it
Omega. We make the resulting DSet our Set of Nodes and run the Omega. We make the resulting DSet our Set of Nodes and run the
algorithm again. algorithm again.
This may recurse a number of times if the graph has monoconnected This may recurse a number of times if the graph has monoconnected
zones within others. zones within others.
6. Forwarding Along An ARC Set 6. Forwarding Along An ARC Set
Under normal conditions, the traffic flows away from the cursor of Under normal conditions, the traffic flows away from the Cursor of
the current ARC and cascades into the next ARC on that side of the the current ARC and cascades into the next ARC on that side of the
cursor, with the Height of the current ARC decreasing monotonically Cursor, with the Height of the current ARC decreasing monotonically
from ARC to ARC till Omega is reached. from ARC to ARC till Omega is reached.
The same goes for a generic Comb construct. When Buttressing ARCs The same goes for a generic Comb construct. When Buttressing ARCs
are applied on a main ARC or other Buttressing ARCs, the final are applied on a main ARC or other Buttressing ARCs, the final
construct assumes the shape of a tree. The tree may be walked in construct assumes the shape of a tree. The tree may be walked in
different manners but the shortest path requires to start going down different manners but the shortest path requires to start going down
the current ARC or Buttressing ARC to its Edge. the current ARC or Buttressing ARC to its Edge.
In case of Label forwarding, the same recursivity is applied and a In case of Label forwarding, the same recursivity is applied and a
multiple ARC label path is constructed. Each ARC has is own set of multiple ARC label path is constructed. Each ARC has is own set of
label path per Omega, each ARC Set label path being merged into the label path per Omega, each ARC Set label path being merged into the
lower ARC label set, thus at the interconnection point. At minimum, lower ARC label set, thus at the interconnection point. At minimum,
ARC label path should be built from the cursor toward each edge, but ARC label path should be built from the Cursor toward each edge, but
this would require label path recompilation upon cursor move, the this would require label path recompilation upon Cursor move, the
proposed approach is then to build for the normal flow to an Omega proposed approach is then to build for the normal flow to an Omega
one pair of label path from edge to edge. one pair of label path from edge to edge.
As this label construct maps the ARC topology with local significant As this label construct maps the ARC topology with local significant
label, the Label Distribution Protocol (LDP) could be reused to label, the Label Distribution Protocol (LDP) could be reused to
announce label association to neighbors on the ARC. announce label association to neighbors on the ARC.
Upon a breakage inside an ARC, until a corrective action takes place, Upon a breakage inside an ARC, until a corrective action takes place,
some traffic will be lost. The corrective action might be either some traffic will be lost. The corrective action might be either
operated at the control plane or the data plane, if immediate action operated at the control plane or the data plane, if immediate action
and near-zero packet loss is required. and near-zero packet loss is required.
6.1. Control Plane Recovery 6.1. Control Plane Recovery
Upon a first breakage in an ARC, the cursor is moved to the breakage Upon a first breakage in an ARC, the Cursor is moved to the breakage
point, either a node or a link, so that traffic flows away from the point, either a node or a link, so that traffic flows away from the
cursor again. Cursor again.
Upon a second breakage within a same ARC, a segment of the ARC is now Upon a second breakage within a same ARC, a segment of the ARC is now
isolated. Both breakage points become sinks till an additional isolated. Both breakage points become sinks till an additional
corrective action, such as modifying the ARC Set, takes place. All corrective action, such as modifying the ARC Set, takes place. All
incoming links in the isolated segment are blocked , causing the incoming links in the isolated segment are blocked , causing the
traffic to exit at the other end of the incoming ARCs. traffic to exit at the other end of the incoming ARCs.
Blocking an Edge Link in the incoming ARC may create an isolated Blocking an Edge Link in the incoming ARC may create an isolated
segment in the incoming ARC as well if it is a second breakage there segment in the incoming ARC as well if it is a second breakage there
too, or if both edges of the incoming ARC tterminate in the broken too, or if both edges of the incoming ARC tterminate in the broken
skipping to change at page 21, line 26 skipping to change at page 15, line 34
6.2. Data Plane Recovery 6.2. Data Plane Recovery
Upon a breakage inside an ARC, it is possible in the data plane to Upon a breakage inside an ARC, it is possible in the data plane to
reverse the direction of -to turn- a given packet once along the ARC reverse the direction of -to turn- a given packet once along the ARC
so the packets exits over the other Edge Link. But in order to avoid so the packets exits over the other Edge Link. But in order to avoid
loops, it is undesirable to reverse the direction of a given packet a loops, it is undesirable to reverse the direction of a given packet a
second time. second time.
Note that once a given packet leaves an ARC to enter the next, it is Note that once a given packet leaves an ARC to enter the next, it is
free to bounce again in the next ARC. In other Words, the domain that free to bounce again in the next ARC. In other Words, the domain
is impacted by a turn is limited to the current ARC itself; the ARC that is impacted by a turn is limited to the current ARC itself; the
forms the event horizon wherein the notion that a turn happened may ARC forms the event horizon wherein the notion that a turn happened
cause a loop. may cause a loop.
So a local strategy must be put in place inside an ARC to allow a So a local strategy must be put in place inside an ARC to allow a
given packet to bounce once upon a breakage, and get dropped upon a given packet to bounce once upon a breakage, and get dropped upon a
second breakage. second breakage.
In the case of IP packet forwarding, a packet can be tagged when it In the case of IP packet forwarding, a packet can be tagged when it
bounces inside an ARC, or when it passes the cursor, for instance by bounces inside an ARC, or when it passes the Cursor, for instance by
reserving a TOS bit for that purpose. When the packet bounces, the reserving a TOS bit for that purpose. When the packet bounces, the
bit is set and when the packet leaves the ARC, the bit is reset and bit is set and when the packet leaves the ARC, the bit is reset and
may be used again in the next ARC. In the generic case of a Comb, a may be used again in the next ARC. In the generic case of a Comb, a
strategy must be put in place to walk the structure and drop a packet strategy must be put in place to walk the structure and drop a packet
that tries all the Edges. it attempts to pass the cursor twice in a that tries all the Edges. it attempts to pass the Cursor twice in a
same direction, meaning that more than a full walk was already same direction, meaning that more than a full walk was already
accomplished. accomplished.
In the case of MPLS forwarding, the same result can be achieved with In the case of MPLS forwarding, the same result can be achieved with
either 3 or 4 Labels Switched Paths (LSPs) along the ARC. either 3 or 4 Labels Switched Paths (LSPs) along the ARC.
3-Labels method: In this case we lay a primary LSP from the cursoo to 3-Labels method: In this case we lay a primary LSP from the cursoo
the Edge in each direction, and a backup LSP Edge to Edge in each to the Edge in each direction, and a backup LSP Edge to Edge in
direction. So a node along the way has three labels, one primary each direction. So a node along the way has three labels, one
and two backup, one in each direction. Should the primary path primary and two backup, one in each direction. Should the primary
fail, the packet can be placed along the backup LSP in the other path fail, the packet can be placed along the backup LSP in the
direction. We'll note that this method contrains the location of other direction. We'll note that this method contrains the
the cursor. Should the cursor move, The primary LSPs have to be location of the Cursor. Should the Cursor move, The primary LSPs
recomputed, at a minimum between the old and the new location of have to be recomputed, at a minimum between the old and the new
the cursor where the direction is reversed. location of the Cursor where the direction is reversed.
4-Labels method: In this case we have two primary and two backup LSPs 4-Labels method: In this case we have two primary and two backup
Edge to Edge in each direction. The labels are independent of the LSPs Edge to Edge in each direction. The labels are independent
location of the cursor, so the cursor can be moved in control of the location of the Cursor, so the Cursor can be moved in
plane with no impact on labels. control plane with no impact on labels.
7. Manageability 7. Manageability
This specification describes a generic model. Protocols and This specification describes a generic model. Protocols and
management will come later management will come later
8. IANA Considerations 8. IANA Considerations
This specification does not require IANA action. This specification does not require IANA action.
skipping to change at page 22, line 37 skipping to change at page 16, line 50
Levy-Abegnoli for their participation and continuous support to the Levy-Abegnoli for their participation and continuous support to the
work presented here. work presented here.
11. References 11. References
11.1. Normative References 11.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6291] Andersson, L., van Helvoort, H., Bonica, R., Romascanu,
D., and S. Mansfield, "Guidelines for the Use of the "OAM"
Acronym in the IETF", BCP 161, RFC 6291, June 2011.
11.2. Informative References 11.2. Informative References
[RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L. and L. [I-D.thubert-rtgwg-arc-bicast]
Thubert, P. and I. Wijnands, "Applying Available Routing
Constructs to bicasting", draft-thubert-rtgwg-arc-
bicast-01 (work in progress), October 2013.
[RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L., and L.
Berger, "A Framework for MPLS in Transport Networks", RFC Berger, "A Framework for MPLS in Transport Networks", RFC
5921, July 2010. 5921, July 2010.
Authors' Addresses Authors' Addresses
Pascal Thubert, editor Pascal Thubert (editor)
Cisco Systems, Inc Cisco Systems, Inc
Building D Building D
45 Allee des Ormes - BP1200 45 Allee des Ormes - BP1200
MOUGINS - Sophia Antipolis, 06254 MOUGINS - Sophia Antipolis 06254
FRANCE FRANCE
Phone: +33 497 23 26 34 Phone: +33 497 23 26 34
Email: pthubert@cisco.com Email: pthubert@cisco.com
Patrice Bellagamba Patrice Bellagamba
Cisco Systems Cisco Systems
214 Avenue des fleurs 214 Avenue des fleurs
Saint-Raphael, 83700 Saint-Raphael 83700
FRANCE FRANCE
Phone: +33.6.1998.4346 Phone: +33.6.1998.4346
Email: pbellaga@cisco.com Email: pbellaga@cisco.com
 End of changes. 59 change blocks. 
137 lines changed or deleted 201 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/