< draft-thubert-rtgwg-arc-00.txt   draft-thubert-rtgwg-arc-01.txt >
RTGWG P. Thubert, Ed. RTGWG P. Thubert, Ed.
Internet-Draft P. Bellagamba Internet-Draft Cisco
Intended status: Standards Track Cisco Systems Intended status: Standards Track P. Bellagamba
Expires: April 5, 2013 October 2, 2012 Expires: April 19, 2014 Cisco Systems
October 18, 2013
Available Routing Constructs Available Routing Constructs
draft-thubert-rtgwg-arc-00 draft-thubert-rtgwg-arc-01
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
skipping to change at page 1, line 41 skipping to change at page 1, line 42
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 5, 2013. This Internet-Draft will expire on April 19, 2014.
Copyright Notice Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the Copyright (c) 2013 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 Provisions Relating to IETF Documents (http://trustee.ietf.org/
(http://trustee.ietf.org/license-info) in effect on the date of license-info) in effect on the date of publication of this document.
publication of this document. Please review these documents Please review these documents carefully, as they describe your rights
carefully, as they describe your rights and restrictions with respect and restrictions with respect to this document. Code Components
to this document. Code Components extracted from this document must extracted from this document must include Simplified BSD License text
include Simplified BSD License text as described in Section 4.e of as described in Section 4.e of the Trust Legal Provisions and are
the Trust Legal Provisions and are provided without warranty as provided without warranty as described in the Simplified BSD License.
described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. ARC Set representations . . . . . . . . . . . . . . . . . . . 7 3. ARC Set representations . . . . . . . . . . . . . . . . . . . 6
4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 11 4. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1. Load Balancing . . . . . . . . . . . . . . . . . . . . . . 11 4.1. Load Balancing . . . . . . . . . . . . . . . . . . . . . . 16
4.1.1. Routing Hierarchies . . . . . . . . . . . . . . . . . 11 4.1.1. Routing Hierarchies . . . . . . . . . . . . . . . . . 16
5. Lowest ARC First . . . . . . . . . . . . . . . . . . . . . . . 11 5. Lowest ARC First . . . . . . . . . . . . . . . . . . . . . . . 16
5.1. Init . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.1. Init . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2. Growing Trees . . . . . . . . . . . . . . . . . . . . . . 12 5.2. Growing Trees . . . . . . . . . . . . . . . . . . . . . . 17
5.3. Being Safe . . . . . . . . . . . . . . . . . . . . . . . . 12 5.3. Being Safe . . . . . . . . . . . . . . . . . . . . . . . . 17
5.4. Bending An ARC . . . . . . . . . . . . . . . . . . . . . . 13 5.4. Bending An ARC . . . . . . . . . . . . . . . . . . . . . . 18
5.5. Orienting Links . . . . . . . . . . . . . . . . . . . . . 14 5.5. Orienting Links . . . . . . . . . . . . . . . . . . . . . 19
5.6. Looping or recursing . . . . . . . . . . . . . . . . . . . 14 5.6. Looping or recursing . . . . . . . . . . . . . . . . . . . 19
6. Forwarding Along An ARC Set . . . . . . . . . . . . . . . . . 15 6. Forwarding Along An ARC Set . . . . . . . . . . . . . . . . . 20
6.1. Control Plane Recovery . . . . . . . . . . . . . . . . . . 16 6.1. Control Plane Recovery . . . . . . . . . . . . . . . . . . 20
6.2. Data Plane Recovery . . . . . . . . . . . . . . . . . . . 16 6.2. Data Plane Recovery . . . . . . . . . . . . . . . . . . . 21
7. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 17 7. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 22
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
9. Security Considerations . . . . . . . . . . . . . . . . . . . 17 9. Security Considerations . . . . . . . . . . . . . . . . . . . 22
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 17 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.1. Normative References . . . . . . . . . . . . . . . . . . . 18 11.1. Normative References . . . . . . . . . . . . . . . . . . 22
11.2. Informative References . . . . . . . . . . . . . . . . . . 18 11.2. Informative References . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
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 32 skipping to change at page 3, line 16
It is also possible to compute an alternate routing topology for fast It is also possible to compute an alternate routing topology for fast
rerouting to a given destination, in which case some signalling, rerouting to a given destination, in which case some signalling,
tagging or labelling can be put in place to indicate whether a packet tagging or labelling can be put in place to indicate whether a packet
follows the normal path or was rerouted over an alternate topology. follows the normal path or was rerouted over an alternate topology.
Once a packet is rerouted, it is bound to the alternate topology so Once a packet is rerouted, it is bound to the alternate topology so
only one breakage can be handled with looplessness guarantees in most only one breakage can be handled with looplessness guarantees in most
practical situations. practical situations.
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 sequence of nodes and links (ARC) as a routing construct made of a bidirectional sequence of
with 2 outgoing edges, so that, upon a single breakage, each lively nodes and links with 2 outgoing edges, so that, upon a single
node in along ARC can still reach one of the outgoing edges. As a breakage, each lively node in along ARC can still reach one of the
result, an ARC is this resilient to one breakage as opposed to an outgoing edges.
arrow that has only one outgoing edge, and an ARC topology is
resilient to one breakage per ARC.
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.
skipping to change at page 4, line 18 skipping to change at page 3, line 49
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 reliable multicasting operations.
2. Terminology 2. Terminology
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 Cursor: A virtual point along an ARC that can be located on a node or
or on a link between 2 nodes. In normal operations, the traffic 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 -|
Figure 1: Collapsed ARC Infrastructure ARC: An ARC that is formed of more than one node,
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 -|
Figure 2: Infrastructure ARC DAG: Directed Acyclic Graph.
DAG: Directed Acyclic Graph.
ARC Set (or Cascade): A DAG with ARCs as vertices. In the DAG, an 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 by
definition, an ARC has at least 2 outgoing Edge Links, one per 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 ARC Height: An arbitrary distance from Omega that is associated to an
an ARC. The Height of an ARC must be more than the Height of any ARC. The Height of an ARC must be more than the Height of any of
of the ARCs it terminates into. The order of ARC formation by a 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
Figure 3: Comb with Buttressing ARC Safe Node: A node is Safe if there is no single point of failure -
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 ?-S: A node N is deemed dependent on a node S or S-dependent (denoted
(denoted as ?-S) if S is the last single point of failure along as ?-S) if S is the last single point of failure along N's
N's shortest path to Omega. 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 8, line 21 skipping to change at page 9, line 19
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 probbaly 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 backpressure can be applied on the incoming ARCs so
that they move their own traffic towards their own alternate Edge. that they move their own traffic towards their own alternate Edge.
The process may recurse. The process may recurse.
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 subtopology, such as a ring, to
enable forwarding inside a ring towards a next ring. Then, 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.
oLAF is based on Dijkstra's algorithm for Shortest Path First (SPF) oLAF is based on Dijkstra's algorithm for Shortest Path First (SPF)
computation, and is designed in such a fashion that the reverse SPF computation, and is designed in such a fashion that the reverse SPF
tree towards a destination is conserved and preferred for forwarding tree towards a destination is conserved and preferred for forwarding
along the resulting ARC Set. along the resulting ARC Set.
We make the computation on behalf of Omega, that is an abstraction, We make the computation on behalf of Omega, that is an abstraction,
but could represent the node or the set of nodes that we want to but could represent the node or the set of nodes that we want to
reach with an ARC Set. If Omega is instantiated as an actual reach with an ARC Set. If Omega is instantiated as an actual
destination node, then that node may be a fine location for an ARC destination node, then that node may be a fine location for an ARC
Computing Engine. Computing Engine.
5.1. Init 5.1. Init
So we start with an proverbial Initial Set of Nodes that are So we start with an proverbial Initial Set of Nodes that are
interconnected by Links, and Omega that is the destination that we interconnected by Links, and Omega that is the destination that we
want to reach with an ARC Set. want to reach with an ARC Set.
If there is no Heir, we're done. If there is a single Heir then the If there is no Heir, we're done. If there is a single Heir then the
graph is monoconnected, so we restart the computation taking that graph is monoconnected, so we restart the computation taking that
Heir off the Set of Nodes and making it Omega. Heir off the Set of Nodes and making it Omega.
Else, if Omega is a single Node, or if Omega is composed of multiple Else, if Omega is a single Node, or if Omega is composed of multiple
nodes but we are willing to accept that both ends of an ARC terminate nodes but we are willing to accept that both ends of an ARC terminate
skipping to change at page 15, line 14 skipping to change at page 19, line 55
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
skipping to change at page 16, line 44 skipping to change at page 21, line 26
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 free to bounce again in the next ARC. In other Words, the domain that
that is impacted by a turn is limited to the current ARC itself; the is impacted by a turn is limited to the current ARC itself; the ARC
ARC forms the event horizon wherein the notion that a turn happened forms the event horizon wherein the notion that a turn happened may
may cause a loop. 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 3-Labels method: In this case we lay a primary LSP from the cursoo to
to the Edge in each direction, and a backup LSP Edge to Edge in the Edge in each direction, and a backup LSP Edge to Edge in each
each direction. So a node along the way has three labels, one direction. So a node along the way has three labels, one primary
primary and two backup, one in each direction. Should the primary and two backup, one in each direction. Should the primary path
path fail, the packet can be placed along the backup LSP in the fail, the packet can be placed along the backup LSP in the other
other direction. We'll note that this method contrains the direction. We'll note that this method contrains the location of
location of the cursor. Should the cursor move, The primary LSPs the cursor. Should the cursor move, The primary LSPs have to be
have to be recomputed, at a minimum between the old and the new recomputed, at a minimum between the old and the new location of
location of the cursor where the direction is reversed. the cursor where the direction is reversed.
4-Labels method: In this case we have two primary and two backup 4-Labels method: In this case we have two primary and two backup LSPs
LSPs Edge to Edge in each direction. The labels are independent Edge to Edge in each direction. The labels are independent of the
of the location of the cursor, so the cursor can be moved in location of the cursor, so the cursor can be moved in control
control plane with no impact on labels. 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 18, line 15 skipping to change at page 22, line 37
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.
[RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 4291, February 2006.
[RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
September 2007.
[RFC4862] Thomson, S., Narten, T., and T. Jinmei, "IPv6 Stateless
Address Autoconfiguration", RFC 4862, September 2007.
11.2. Informative References 11.2. Informative References
[I-D.phinney-roll-rpl-industrial-applicability] [RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L. and L.
Phinney, T., Thubert, P., and R. Assimiti, "RPL Berger, "A Framework for MPLS in Transport Networks", RFC
applicability in industrial networks", 5921, July 2010.
draft-phinney-roll-rpl-industrial-applicability-00 (work
in progress), October 2011.
[I-D.thubert-lowpan-backbone-router]
Thubert, P., "LoWPAN Backbone Router",
draft-thubert-lowpan-backbone-router-00 (work in
progress), November 2007.
[RFC4191] Draves, R. and D. Thaler, "Default Router Preferences and
More-Specific Routes", RFC 4191, November 2005.
[RFC4541] Christensen, M., Kimball, K., and F. Solensky,
"Considerations for Internet Group Management Protocol
(IGMP) and Multicast Listener Discovery (MLD) Snooping
Switches", RFC 4541, May 2006.
[RFC5213] Gundavelli, S., Leung, K., Devarapalli, V., Chowdhury, K.,
and B. Patil, "Proxy Mobile IPv6", RFC 5213, August 2008.
[RFC5415] Calhoun, P., Montemurro, M., and D. Stanley, "Control And
Provisioning of Wireless Access Points (CAPWAP) Protocol
Specification", RFC 5415, March 2009.
[RFC5865] Baker, F., Polk, J., and M. Dolly, "A Differentiated
Services Code Point (DSCP) for Capacity-Admitted Traffic",
RFC 5865, May 2010.
[RFC5921] Bocci, M., Bryant, S., Frost, D., Levrau, L., and L.
Berger, "A Framework for MPLS in Transport Networks",
RFC 5921, July 2010.
[RFC6275] Perkins, C., Johnson, D., and J. Arkko, "Mobility Support
in IPv6", RFC 6275, July 2011.
[RFC6550] Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R.,
Levis, P., Pister, K., Struik, R., Vasseur, JP., and R.
Alexander, "RPL: IPv6 Routing Protocol for Low-Power and
Lossy Networks", RFC 6550, March 2012.
Authors' Addresses Authors' Addresses
Pascal Thubert (editor) Pascal Thubert, editor
Cisco Systems Cisco Systems, Inc
Village d'Entreprises Green Side Building D
400, Avenue de Roumanille 45 Allee des Ormes - BP1200
Batiment T3 MOUGINS - Sophia Antipolis, 06254
Biot - Sophia Antipolis 06410
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. 43 change blocks. 
192 lines changed or deleted 126 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/