Internet DRAFT - draft-dachille-inter-area-path-protection
draft-dachille-inter-area-path-protection
Internet Draft A. DÆAchille, Ed. (CoRiTel)
Expiration Date: July 2004 M. Listanti, Ed. (La Sapienza)
U. Monaco, Ed. (La Sapienza)
F. Ricciato, Ed. (CoRiTel)
V. Sharma (Metanoia, Inc.)
January 2004
Inter-Area MPLS Path Protection
<draft-dachille-inter-area-path-protection-01.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet
Engineering Task Force (IETF), its areas, and its working groups.
Note that other groups may also distribute working documents as
Internet-Drafts.
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ö.
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed
at
http://www.ietf.org/shadow.html.
Copyright Notice
Copyright (C) The Internet Society (2003). All Rights Reserved.
DÆAchille et al. Internet draftûexpires July 2004 Page 1 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
Abstract
This document describes a mechanism to establish end-to-end disjoint
LSPs in a multiple area domain, as required for inter-area end-to-end
protection.
This mechanism relies on the joint computation of the working and
backup LSPs segments in each area.
A new RSVP-TE object called the Associated Route Object, ARO, is
defined and used in the signaling messages in support of this scheme.
Contents
1. Introduction..................................................pag. 3
2. Network Model.................................................pag. 3
3. Previous Proposal: Iterated Shortest-Path (ISPA)..............pag. 4
3.1 High-level Description..................................pag. 4
3.2 Limitations of the ISPA.................................pag. 6
4. A novel proposal: Joint Selection Approach (JSA)..............pag. 8
4.1 Linear Inter-area Topology..............................pag.11
4.2 General Inter-Area Mesh Topology........................pag.13
4.3 ARO Object..............................................pag.18
4.3.1 ARO semantics and format.........................pag.18
4.3.2 ARO Sub-objects..................................pag.18
4.3.3 Processing of the ARO............................pag.21
5.Possible Refinements...........................................pag.23
6.Terminology....................................................pag.23
7.Security Considerations........................................pag.24
8.References.....................................................pag.24
9.AuthorsÆ Addresses.............................................pag.25
DÆAchille et al. Internet draftûexpires July 2004 Page 2 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
1. Introduction
End-to-end protection in a MPLS network requires the establishment of
two disjoint LSPs, a working LSP and a backup LSP, and the adoption
of a notification mechanism to inform the head-end of a fault on the
working path so that it may switch the traffic onto the backup LSP.
In this document we assume that the two LSP must be node-disjoint.
Extensions to handle different disjointedness constraints (e.g. link-
or SRLG-disjoint paths) are left for further development of this
draft.
The main problem we address here is the joint and distributed
computation of the working and backup paths in a multi-area network,
where each node has limited knowledge of the network topology. The
reference network model is described in Section 2.
A solution to this problem has been previously proposed in [EXCLUDE-
ROUTE], where a new RSVP-TE object, the XRO, is introduced.
In Section 3 we review this proposal, highlighting some of its
limitations.
In section 4 we propose an alternative approach, based on the joint
computation of the two paths in a distributed manner, which overcomes
the above mentioned limitations. We also introduce a new RSVP-TE
object alternative to the XRO in support of our scheme, and call it
the Associated Route Object (ARO).
Finally, in Section 5 we briefely discuss some points for further
development of the proposed scheme.
2. Network Model
We assume that the network can be modeled as a conglomerate of
interconnected sub-domains, hereafter called ôareasö. Within each
area we distinguish between border nodes and internal nodes. A border
node is placed at the boundary of one or more areas, while an
internal node is completely embedded within a single area. Note that
an area might include only border nodes, with no internal nodes. We
assume that while each border node has complete knowledge of the
intra-area topology, it has only a summarized view of the inter-area
connectivity. That is, while each border node knows about of the
nodes and links included in the area(s) that it is connected to,
along with their associated TE attributes (e.g. available capacity,
degree of reliability), it only has an inter-area connectivity map,
similar to the information that BGP already distributes at inter-AS
level.
As a working hypothesis, we will assume that every inter-area
connection is duplicated. In other words, it is realized by
interconnecting at least two different border nodes on each side.
This assumption is required to enforce node-disjointedness, and
DÆAchille et al. Internet draftûexpires July 2004 Page 3 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
corresponds to the usual way in which inter-AS connections are
arranged in pratice.
Any possible extensions to this scheme to cope with a network where
the duplicated inter-area connection hypothesis does not apply are
considered as a point for further studies.
In the rest of this draft, we will assume a MPLS control plane
[MPLS], involving RSVP-TE signaling and OSPF-TE/ISIS-TE intra-domain
routing. However the proposal here can be easily extended to a GMPLS
control plane, as needed for instance in case of optical networks.
Within the assumptions made above, the concepts and mechanisms
proposed here could apply to several scenarios. For example, the term
of ôareaö might refer to an:
- OSPF area, in case we are implementing TE in a large multi-area IGP
domain. In this case, the inter-area routing protocol is still the
OSPF-TE. The same applies to ISIS-TE;
- Autonomous System (AS), in case we are implementing TE in a
multi-AS context; in this case, the inter-area routing protocol is
BGP or BGP with its Traffic Engineering extensions;
- Optical island, in case we are implementing TE in an optical
network, composed of several inter-connected optical islands. In
this case, the message definitions and processing given in section
4 would need to be adapted for a GMPLS control plane. This point
has been left for further development.
3. Previous Proposal: The Iterated Shortest-Path Approach (ISPA)
A first solution to the problem of distributed establishment of
disjoint LSP was proposed in [EXCLUDE-ROUTE], which utilized a RSVP-
TE object called XRO (eXclude Route Object) introduced in the same
document. We will refer to such a method as the ôiterated shortest-
path approachö (ISPA). In this section, we provide a brief
description of the ISPA approach and outline some of its limitations.
3.1. High-Level Description
The ISPA foresees two steps, which we describe in the following
with reference to the exemplary network in Fig. 1, where a protected
LSP from node A to node H must be installed:
- Step 1: The working LSP is setup along the shortest end-to-end
path, which is computed in a distributed manner through
ERO expansion (see [EXCLUDE-ROUTE]). During the setup
signaling procedure, each node along P1 must process the
PATH message as described in [RSVP] and [RSVP-TE]. With
reference to the sample network in Fig. 1, the actions
realizing this step are as follows:
DÆAchille et al. Internet draftûexpires July 2004 Page 4 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
-Step 1a: Node A computes the segment of P1 through area
1 and initiates the signaling procedure to
install it;
-Step 1b: PATH message arrives at node C, and node C
computes the segment of P1 through area 2,
which is done via ERO expansion, and continues
the signaling procedure;
-Step 1c: Same as step 1b, but node E and area 3 are
involved;
-Step 1d: PATH message arrives at node H, which sends
back to node A the RESV message to allocate
P1, as described in [RSVP] and [RSVP-TE].
Through the RRO included in the RESV message,
node A becomes aware of exactly which nodes
are included in P1;
- Step 2: Node A computes the backup path P2 with the additional
constraint of excluding all nodes that were included in
P1. These nodes are later included in the XRO object of
the PATH message that is sent along P2. With reference
to the examplary network in Fig. 1, this step is
particularized as follows:
-Step 2a: Node A computes the segment of P2 through area
1, pruning node C from the topology, and starts
the signaling procedure to install it;
-Step 2b: PATH message arrives at node D, and node D
computes the segment of P2 through area 2
through ERO expansion, by first pruning nodes C
and E, and next node D continues the signaling
procedure;
-Step 2c: Same as step 2b, but node F now computes the
segment of P2 through area 3;
-Step 2d: Same as step 1d;
DÆAchille et al. Internet draftûexpires July 2004 Page 5 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
area 1 area 2 area 3
/-----------\ /------------\ /-------------\
/ \ / \ / \
--/-- --\-- --\-- --\--
| |***********| |************| |*************| |
| A |~~~~~~~~~~~| C |~*~~~~~~~~~~| E |~~~~~~~~~~~~~| G |
| | | | * | | | |
----- ----- * ----- -----
|*$ *| * |* ~*|
|*$ *| * |* ~*|
|*$ *| * |* ~*|
|*$ *| * |* ~*|
----- ----- * ----- -----
| |$$$$$$$$$$$| |$$$$$$$$$$$$| |$$$$$$$$$$$$$| |
| B | | D | * | F | | H |
| |***********| |************| |*************| |
--\-- --/-- --/-- --/--
\ / \ / \ /
\-----------/ \------------/ \-------------/
****** = Link
~~~~~~ = LSP P1 (between A and H)
$$$$$$ = LSP P2 (between A and H)
Fig.1
3.2. Limitations of the Iterated Shortest-Path Approach (ISPA)
The ISPA has two main limitations:
- Trapping
- Sub-optimal route selection
In this section we briefly discuss these problems.
The trapping problem is described in [DOVERSPIKE] and in [TRAP-
AVOID]; it arises whenever a trap topology is present in the network.
Fig. 2 shows a network that is subject to trapping problem.
DÆAchille et al. Internet draftûexpires July 2004 Page 6 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
area 1 area 2 area 3
/-----------\ /------------\ /-------------\
/ \ / \ / \
--/-- --\-- --\-- --\--
| |***********| |*********** | |*************| |
| A | | C | * | E | | G |
| | | | * | | | |
----- ----- * ----- -----
| * | * | *|
| * | * | *|
| * | * | *|
| * | * | *|
----- ----- * ----- -----
| | | | * | | | |
| B | | D | * | F | | H |
| |***********| |************| |*************| |
--\-- --/-- --/-- --/--
\ / \ / \ /
\-----------/ \------------/ \-------------/
****** = Link
Fig.2
In this example we consider a network consisting of three areas,
namely area 1 (nodes A,B,C,D), area 2 (nodes C,D,E,F), and area 3
(nodes E,F,G,H), as depicted in Fig. 2. We suppose that node A
requests two node-disjoint paths between itself and node H and we
assume that every link has the same cost, say X; in this scenario, in
the first step, path A-C-F-H will be selected as the working path.
After pruning nodes C and F from the topology (in ISPA this is done
by adding them to the XRO), however, it is no longer possible to find
another path between A and H (even though two node-disjoint paths
from node A to node H do exist in this setting). In [TRAP-AVOID] is
stated that this problem may occur with a probability as high as 30%
in a typical mesh network when node-disjoint paths are required.
JSA overcomes this limitation, because the working and the backup
paths are computed jointly. Thus, if the backup path shares a node
with the working one, both are modified to avoid trapping. In this
example, the paths JSA would find are: A-B-D-F-H as the working path
and A-C-E-G-H as the backup path.
The second limitation is that the ISPA may lead to sub-optimal path
selection. That is, once the working path is selected at a minimum
cost, the backup path has to be selected at a cost greater than the
one obtainable with a joint computation of the two paths; we discuss
this in the context of the exemplary network in Fig. 3, where the
numbers over each link represent its weight.
DÆAchille et al. Internet draftûexpires July 2004 Page 7 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
area 1 area 2 area 3
/-----------\ /------------\ /-------------\
/ \ / \ / \
--/-- 1 --\-- 3 --\-- 2 --\--
| |***********| |************| |*************| |
| A | | C | * * | E | | G |
| | | | * 2 * | | | |
----- ----- * * ----- -----
| * | * * | * |
| * 4 | ** | 4 * |
| * | ** | * |
| * | * * | * |
----- ----- * * ----- -----
| | | | * 6 * | | | |
| B | 4 | D | * * | F | 3 | H |
| |***********| |************| |*************| |
--\-- --/-- 2 --/-- --/--
\ / \ / \ /
\-----------/ \------------/ \-------------/
****** = Link (weighted)
Fig. 3
If ISPA is adopted to compute two node-disjoint paths, node A will
choose A-C-F-H as the working path, and A-B-D-E-G-H as the backup
one; the costs are 6 for the working path and 20 for the backup one.
If JSA is adopted instead, node A will choose A-C-E-G-H as the
working path and A-B-D-F-H as the backup one, with a cost of 10 for
the working path and 13 for the backup one. The difference here is
that while the first approach selects the shortest possible working
path, it can lead to situations where the backup path has a high
cost. On the other hand, the second approach selects them with the
constraint that both must be the shortest possible, obtaining a more
balanced result.
In the following, we propose a different approch, where the joint
selection of disjoint paths is done in a distributed manner.
4. A Novel Proposal: The Joint Selection approach (JSA)
Here we propose a novel scheme, called ôJoint Selection Approachö,
based on the joint selection of both working and backup LSPs. This
mechanism assumes that a disjoint route selection algorithm is
implemented in the border nodes, such as for example the Suurballe
algorithm [SUURBALLE] or the Bhandari algorithm [BHANDARI] or one of
their extensions.
Similarly to ISPA, also in JSA the two LSP are installed in two
separate steps. However, differently from ISPA, the route
DÆAchille et al. Internet draftûexpires July 2004 Page 8 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
selection of both LSPs is done jointly in the first phase. While the
path of the first LSP - that is, the one being installed during the
first phase - is included in the ERO, the route of the second LSP -
which will be installed in the second phase û will be collected in
the ARO during the first phase itself. At the end of the first phase,
the ARO collecting the e2e route of the second LSP is returned to the
head-end node, which can then install it as an ER-LSP.
Next we will provide a detailed description of the JSA operation.
For sake of simplicity, we will first consider a special case, where
the inter-area connectivity is linear, therefore the inter-area path
for both LSP is fixed. Then, in section 4.2, we will describe the JSA
mechanism in the case of general mesh inter-area connectivity. The
difference between the two cases is that in the linear topology the
inter-area routes for both LSP are the same, so that full ARO
expansion occurs. Instead, in the more general case, the inter-area
routes of the two LSP may be partially (and not completely)
overlapping, requiring partial ARO expansion.
In the following we will assume that every border router, say B1,
that is directly attached to area X maintains a summarized
topological view consisting of the exact intra-area topology of X
plus several so called ôvirtual linksö. Virtual link are present
between the border routers of area X, say B2 B3 etc., and the
possible destinations: they merely represent external paths to remote
destinations that are reachable through some inter-area path. Virtual
link might be assigned a cost (see section 5). As an example, Fig.
4a, 4b, and 4c report the topological views of border nodes in the
sample network of Fig. 1.
area 1
/-----------\
/ \
--/-- --\--
| | | |++
| A |***********| C | +++
| | | | +++
----- ----- +++
|* | +++
|* | + E,F,G,H
|* | +
|* | +++
----- ----- +++
| | | | +++
| B |***********| D | +++
| | | |++
--\-- --/--
\ /
\-----------/
****** = Link
DÆAchille et al. Internet draftûexpires July 2004 Page 9 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
++++++ = Virtual Link
Fig. 4a
area 2
/-----------\
/ \
--/-- --\--
++| | | |++
+++ | C |***********| E | +++
+++ | | * | | +++
+++ ----- * ----- +++
+++ |* * *| +++
A,B + |* * *| + G,H
+ |* * *| +
+++ |* * *| +++
+++ ----- * ----- +++
+++ | | * | | +++
+++ | D |***********| F | +++
++| | | |++
--\-- --/--
\ /
\-----------/
****** = Link
++++++ = Virtual Link
Fig. 4b
area 3
/-----------\
/ \
--/-- --\--
++| | | |
+++ | E |***********| G |
+++ | | | |
+++ ----- -----
+++ |* *|
A,B,C,D + |* *|
+ |* *|
+++ |* *|
+++ ----- -----
+++ | | | |
+++ | F |***********| H |
++| | | |
--\-- --/--
\ /
\-----------/
****** = Link
DÆAchille et al. Internet draftûexpires July 2004 Page 10 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
++++++ = Virtual Link
Fig. 4c
Fig. 4a-4b-4c: (topological view of nodes in area i)......[i=1,2,3]
4.1. Linear inter-area topology
Here we assume that inter-area connectivity between source and
destination is linear (as example, see Fig. 1). Note that the case of
a multi-area OSPF network falls in this case; in fact, OSPF areas are
organized in a star topology, with a central area 0, the backbone,
and all other areas connected to it. If we assume that each
destination is connected to a single area, we can exclude stub areas
that do not include source nor destination, so we end up with a chain
of length 3.
We will describe JSA in this case with reference to the topology
shown in Fig. 1. Suppose that node A requests two node-disjoint LSP
between nodes A and H; JSA foresees two steps:
-Step 1: Joint and distributed computation of the two LSPs and
installation of the first one. This step is divided in the
following phases:
- Step 1a: Node A MUST compute two node-disjoint paths between
itself and H, based on the virtual topology shown in
Fig. 4a. This computation is performed through a
disjoint route selection algorithm, e.g. [SUURBALLE] and
[BHANDARI]. In this example the computed paths are A-C
and A-B-D, which are LSP segments in area 1(one of which
will form a segment of the first LSP while the other
will form a segment of the second LSP). _
- Step 1b: Node A start the signaling procedure to establish the
first LSP, for example A-C; the PATH message sent by
node A includes, among the others, these objects:
-ERO specifying the route C(Strict)-A2(Loose)-A3(Loose)-
H(Loose). A2 and A3 are Area_ID of area 2 and 3,
see section 4.3;
-ARO specifying the route A-B-D-A2-A3, while the tail-end
node will be added later;
- Step 1c: Node C receives PATH message and computes two node-
disjoint paths between nodes A and H, based on the
virtual topology shown in Fig. 4b. In this way, node C
obtains the LSP segments in area 2. This computation is
triggered by the presence of an ARO in the PATH message
and by the fact that node H does not belong to area 2;
- Step 1d: Node C performs ARO and ERO expansion and continues the
signaling procedure; the PATH message sent by node C
includes, among the others, these objects:
DÆAchille et al. Internet draftûexpires July 2004 Page 11 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
-ERO specifying the route E(Strict)-A3(Loose)-H(Loose);
-ARO specifying the route A-B-D-F-A3, since A2 has been
expanded to the route(D-F) through area 2;
- Step 1e: As in step 1c, but the border node involved is E and the
virtual topology used is the one shown in Fig. 4c, and
then step 1d is performed by node E; PATH message sent
by node E toward node H includes, among the others,
these objects:
-ERO specifying the route G(Strict)-H(Strict) and
-ARO specifying the route A-B-D-F-H; the tail-end node
H is added by E, i.e. the first border node
connected to tail-end area;
- Step 1f: Upon receiving the PATH message, node H sends back a
RESV message along the first path to install that
path. The ARO is copied into the RESV to communicate
the second route to node A. The first step thus ends
with the establishment of the first LSP; note that here
ARO expansion had to be performed in every area;
-Step 2: Establishment of the second LSP computed in the first step;
this step is divided into the following phases:
- Step 2a: Node A starts the signaling procedure to establish the
second LSP by sending a PATH message towards node H;
the ERO object contained in PATH now includes all the
nodes described in the ARO (see step 1), marked as
Strict. Thus the second LSP will be installed as an ER-
LSP.
- Step 2b: Nodes B,D, and F forward the PATH message along the
route described in ERO;
- Step 2c: The PATH message arrives at the tail-end node H, which
sends back RESV message to establish the second LSP;
- Step 2d: The RESV message arrives at node A, establishing the
second LSP; from this moment on, node A can begin
generating traffic along one of the LSPs (i.e. the
working one). If the second LSP cannot be established,
the first LSP must be torn down;
If one of these steps is unsuccessful, a PATH-ERR message will be
sent back and the entire procedure must be restarted, with a maximum
of N tries (parameter N may be optimized to minimize signaling
overhead on the network).
DÆAchille et al. Internet draftûexpires July 2004 Page 12 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
4.2. General Inter-area Mesh Topology
In this section we will describe JSA operations on a generally
inter-area mesh topology, in particular we will refer to the network
shown in Fig. 5, which can model a multi-AS network.
We assume that the head-end node A requests two node-disjoint LSPs
towards the tail-end node B; JSA minimizes the number of areas that
the two LSPs share, and if two area-disjoint paths are present in the
network, JSA can compute them; however the two LSPs will necessarily
share head-end and tail-end areas, so the minimum number of areas
that the two LSPs share, in a generic topology, is 2. We now describe
JSA with reference to Fig. 5, assuming that A computes the following
inter-area routes for the two LSP: A1-A4-A5-A6 and A1-A2-A5-A6. The
JSA mechanism proceeds as follows:
-Step 1: Joint and distributed computation of the two LSPs and setup
of the first one. This step is performed in the following
phases:
- Step 1a: Node A computes two disjoint paths between itself and B,
within area 1, with a inter-area topological view as
shown in Fig. 5b; in this case, node A MUST prune all
the border nodes, except one for every area connected to
area 1, before the disjoint route selection algorithm is
performed; as a result, the two LSPs will not cross the
same next area, and will follow the computed inter-area
path. Assume that nodes B2 and B4 are pruned. Pruning
MUST NOT be performed if area 1 has only one neighbour
area.
- Step 1b: Node A starts the signaling procedure, sending the PATH
message along the first LSP, for example through areas
1-4-5-6, including the objects:
-ERO specifying all the nodes between node A and node
B3, marked as Strict, A4(Loose)-A5(Loose)-
A6(Loose)-node B(Loose);
-ARO specifying all the nodes between node A and node
B1, then A2, A5, A6. A2, A5, and A6 are the
Area_IDs, described in Section 4.3, of the second
LSP inter-area route;
- Step 1c: Upon receiving the PATH message, node B3 controls if A4
(ID of area 4, through which B is reachable) is included
in ARO; it is not, then only first LSP crosses area 4;
node B3 performs an ERO expansion, as described in
[EXCLUDE-ROUTE], while ARO is not be processed, and then
B3 continues the signaling procedure. Assume that nodes
B3 and B6 are chosen as edge nodes of the segment of the
first LSP through area 4 by the disjoint route selection
algorithm performed by node B3;
DÆAchille et al. Internet draftûexpires July 2004 Page 13 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
- Step 1d: Node B6 controls if A5 is included in ARO; it is, then
the two LSP must share area 5. Node B6 MUST perform the
disjoint route selection algorithm, since the two LSPs
MUST be node-disjoint in area 5. In this computation
node B6 MUST prune node B5 from topology, since B6 is
the last node of the segment of the first LSP in area 4,
and must be the first node of the segment of the first
LSP in area 5 (see Fig. 5c). Assume that nodes B6 and
B10 are chosen as edge nodes of the segment of the first
LSP through area 5 by the disjoint route selection
algorithm, and that nodes B7 and B9 as edge node of the
segment of the second LSP through the same area.
- Step 1e: Node B6 continues the signaling procedure, sending a
PATH message to node B10 containing these objects:
-ERO specifying all the nodes between node B6 and node
B10, marked as Strict, A6(Loose)-B(Loose). This
route has been obtained through ERO expansion;
-ARO specifying all the nodes between nodes A and B1, A2,
all the nodes between B7 and B9, then A6. Here A5
has been expanded to obtain the second LSP route
through area 5 (ARO expansion);
- Step 1f: A6 is included in ARO, so node B10 must perform the
disjoint route selection algorithm, based on the
topology shown in Fig. 5d and perform ERO and ARO
expansion as described in steps 1d and 1e.
- Step 1g: Node B sends RESV message to install the first LSP,
copying the ARO in it, so A will become aware of the
route of the second LSP. This ends the first step.
-Step 2: Establishment of the second LSP computed in step 1. This
step is divided in the following phases:
-Step 2a: Node A starts the signaling procedure to install the
second LSP, sending a PATH message including the ERO
specifying the route obtained by node A via the ARO it
received as part of the RESV message at the end of Step 1;
all nodes are marked as Strict, while Area_ID are
substituted by type 32 Loose sub-objects (see [RSVP-TE]);
- Step 2b: The second LSP is established as described in [EXCLUDE-
ROUTE], with the usual ERO expansion.
DÆAchille et al. Internet draftûexpires July 2004 Page 14 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
****
** **
* *
* area 2 *
B1--------* *
| * *
| | ** **
| | ****
| | | |
**** | | | ****
** **------B2 | ----- B7---------- ** **
* * | | * *
* area 1 * | | * area 6 *
* * | | * *
* * ---------B8-------| | / * *
** **------B4 | | / ** **
# **** | | | B9 ****
# | | | | / / #
# | | ****-----B5-------**** / / #
# | | ** ** ** ** /B10 #
# | |* * * * / #
# | * area 4 * * area 5 */ #
# B3--------* * * * #
# * * * * #
# ** ** ** ** #
----- ****-----B6-------**** -----
| | | |
| A | | B |
| | | |
----- -----
--------- = Inter-area Link
######### = Intra-area Link
Bi = Border nodes "i"
Fig. 5
DÆAchille et al. Internet draftûexpires July 2004 Page 15 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
B1::::::::::::::
| :
| :
| :
| :
| /B2p:::: :
******* | / : :
** ** / : :
----- * */ : :
| | * * : :
| A |####* area 1 * node B
| | * * : :
----- * * : :
* *\ : :
** **| \ : :
******* | \ : :
| \B4p:::: :
| :
| :
| :
B3::::::::::::
::::::::: = Virtual Link
######### = Intra-area Link
--------- = Inter-area Link
Bi = Border Node "i"
Bip = Border Node "i" pruned
Fig. 5b
DÆAchille et al. Internet draftûexpires July 2004 Page 16 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
::::::::::::B8
: \
: \
: ::::::::::B7 \
: : \ \ B9
: : \ \ area 5 / :
: : \ \******* / :
: : \** ** / :
: : ::::::B5-----* * / :
: : : * */ :
node A * * node B
: * * :
: * *\ :
::::::B6-----* * \ :
** ** \ :
******* \ :
\ :
\:
B10
::::::::: = Virtual Link
--------- = Inter-area Link
Bi = Border Node "i"
Fig. 5c
to area 5
\
\
:B9
: \ ******
: \ ** **
:: * * -----
: * * | |
: * area 6 *#####| B |
node A * * | |
: * * -----
:: * *
: /** **
: / ******
::B10
/
/
/
to area 5
Bi = Border node ôiö
DÆAchille et al. Internet draftûexpires July 2004 Page 17 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
######### = Intra-area Link
--------- = Inter-area Link
::::::::: = Virtul Link
Fig. 5d
4.3. ARO Object
This is a novel RSVP-TE object used in JSA.
4.3.1. ARO Semantics and format
The route of the backup path associated to a working path is
advertised by means of the Associated Route Object (ARO). Class value
and C_Type value are [TBD]. The ARO Object has the following format
(Fig. 6a):
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
-----------------------------------------------------------------
| |
// SUB-OBJECTS //
| |
-----------------------------------------------------------------
Fig. 6a
It is easy to notice that this format is very similar to that of
ERO object [RSVP-TE]. Indeed it is in fact the same, except for Class
and C_Type. We can think of this object as playing the role of the
ôfuture ERO of the backup pathö, and this explains why it is so
similar to the ERO object.
As happens with ERO, the sub-objects represent an abstract node,
i.e. a group of real nodes, which may consist even of a single
physical node (this concept is well described in [RSVP-TE]).
4.3.2. ARO Sub-Objects
The ARO object is a collection of variable length sub-objects, as
defined for ERO object; each sub-object has the following format:
DÆAchille et al. Internet draftûexpires July 2004 Page 18 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
------------------------------------------------------------------
| | | |
| Type | Length | SUB-OBJECTS Contents //
| | | |
------------------------------------------------------------------
Fig. 6b
Type: the Type field specifies the type of the information
included in the ôsub-object contentsö field; in fact it
is necessary to distinguish not only between IP addresses
and Area_IDs, but also among different kind of IP
addresses and Area_IDs; the possible values are:
-IPv4 address (Type = 1)
-IPv6 address (Type = 2)
-Autonomous System ID (Type = 32)
-OSPF Area_ID (Type = 33)
-Optical island ID (Type = 34)
These last three ID are the so called ôArea_IDö.
Length: the length field specifies the total length of the sub-
objects in bytes, including the Type and Length fields;
it must be a multiple of 4 and its value must be at least
4.
4.3.2.1. Sub-object 1: IPv4 address
The format of this sub-object is shown in Fig. 7a:
DÆAchille et al. Internet draftûexpires July 2004 Page 19 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
------------------------------------------------------------------
| | | |
| Type = 1 | Length | IPv4 Address (4 Bytes) |
| | | |
------------------------------------------------------------------
| | | |
| IPv4 Address (continued) | Addr_len | Resvd |
| | | |
------------------------------------------------------------------
Fig. 7a
In this case, Type = 1, Length = 8;
IPv4 address: an IPv4 address treated as a prefix, based
on the value of the field Addr_len. Bits
beyond this prefix should be ignored on
receipt.
4.3.2.2. Sub-object 2 : IPv6 address
The format of this sub-object is shown in Fig. 7b
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
------------------------------------------------------------------
| | | |
| Type = 2 | Length | IPv6 Address (16 Bytes) |
| | | |
------------------------------------------------------------------
| |
| IPv6 Address (continued) |
| |
------------------------------------------------------------------
| |
| IPv6 Address (continued) |
| |
------------------------------------------------------------------
| |
| IPv6 Address (continued) |
| |
------------------------------------------------------------------
| | | |
| IPv6 Address (continued) | Addr_len | Resvd |
| | | |
------------------------------------------------------------------
DÆAchille et al. Internet draftûexpires July 2004 Page 20 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
Fig. 7b
In this case, Type = 2, Length = 20;
IPv6 address: an IPv6 address treated as a prefix, based
on the value of the field Addr.len. Bits
beyond this prefix should be ignored on
receipt.
4.3.2.3. Sub-object 3-4-5: Area_ID
These three sub-objects have the same format, but differ one from
the other in, obviously, the Type field, and also by the structure of
the identifiers whether they identify AS, OSPF areas, or optical
islands; we decided to use the same format for these sub-objects
because they are processed in the same manner. This format is shown
in Fig. 7c
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
------------------------------------------------------------------
| | | |
|Type = 3,4 or 5| Length | Area_ID |
| | | |
------------------------------------------------------------------
Fig. 7c
In this case, Type = 3,4 or 5, Length = 4
Area_ID: An identifier that specifies an AS (Type=3),
an OSPF area in a large IGP network (Type =
4) or an optical island (Type = 5).
4.3.3. Processing of the ARO
In this section we explain how ARO object is processed.
Since the purpose of the ARO is to keep track of the nodes along
the second path, only reading or adding sub-objects operations will
be performed on it.
When a PATH message arrives at a node, the node first checks
whether the received PATH message contains an ARO; if no ARO is
present, the requested path is unprotected, and the procedure
explained in [EXCLUDE-ROUTE] can be followed, see Section 4.2; on
DÆAchille et al. Internet draftûexpires July 2004 Page 21 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
the other hand, if the requested path is protected, the ARO is
included in the PATH message sent along the first LSP and processed
as follows.
A border node receiving a PATH message relative to the first LSP
MUST check if Area_ID of the next area towards the tail-end node, say
area X, is included in one of the ARO sub-objects (e.g. in the
example of Section 4.2, node B3 checks if Area_ID A4 is included in
the ARO).
- If area X ID is included, working and backup LSPs will share the
area X and the border node MUST perform disjoint route selection
algorithm on the virtual topology obtained pruning the following
nodes, depending on the ARO content:
- If the previous sub-object in the ARO is an Area_ID sub-object,
first and second LSPs do not share the previous area as a
common one; all border nodes connecting to areas either not
included in the ARO, or included in the ERO, MUST be pruned.
This operation guarantees edge continuity and disjointedness of
the two LSPs within the area X.
- Otherwise the ARO includes the IPv4/IPv6 sub-object relative to
last computed border node along the second route; this means
that first and second LSPs share the previous area. All border
nodes, except the above referred one, connecting to areas
either not included in the ARO, or not included in the ERO,
MUST be pruned. As example, focus on Fig. 5 and Fig. 5c and
assume that the two LSPs share area 4 and area 5 (area X = area
5), so that nodes B6 and B5 are the last nodes along the two
LSP in area 4; when node B6 performs disjoint route selection
algorithm, only nodes B6, B5, B9, B10, MUST NOT be pruned in
order to guarantee the right selection of the two routes.
- In both the previous cases, border nodes connecting to next
areas included in the ERO and in the ARO MUST also be pruned,
except one border node per area, so that the two LSPs will
follow the computed paths. As example, in Section 4, B2 and B4
have been pruned, so the two LSPs will follow the computed
inter-area paths. If the two LSPs will share the next areas,
this step MUST not be performed.
- If area X ID is not included in the ARO, only the first LSP will
cross area X; since the second LSP does not share area X with the
first LSP, the border node, MUST only perform an ERO expansion as
described in [EXCLUDE-ROUTE] and no ARO processing is required.
When a PATH message containing ERO and ARO objects arrives at the
tail-end node, the ARO object is copied into the RESV message that
the tail-end sends back to the head-end node. Likewise, the ARO will
not be processed by intermediate nodes, but only by the head-end
node, since it provides the route of the second path. When such a
RESV message arrives at the head-end node, the ARO must be used
DÆAchille et al. Internet draftûexpires July 2004 Page 22 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
to create the ERO object included in the PATH message sent along the
second LSP, with these constraints:
- Every node included in the ARO is copied into ERO and marked as
Strict; in the example of section 4.1, the ERO created by node A
and included in the PATH message is: B(Strict)-D(Strict)-
F(Strict)-H(Strict).
- If ARO contains Area_IDs (note that this can only occur in the
General Mesh Topology case, since it foresees the partial ARO
expansion), a proper Type-32 ERO subobject is added to ERO; in
the example of section 4.2, the ERO created by node A and
included in the PATH message is: B1(Strict)-A2(Loose)-
B7(Strict)-B9(Strict)-B(Strict).
When the head-end node sends a PATH including such an ERO (and no
ARO), it is processed as in [EXCLUDE-ROUTE] or in [VASSEUR], with ERO
expansion when the next hop is marked as Loose. If this step is
successful, the tail-end will send back a RESV, which will allocate
resources for the backup path, but if there is a problem and the
backup one canÆt be allocated, then the working path previously
installed must be pulled down.
5. Possible Refinements
There are some issues not contemplated in this document which have
been left to future developments:
- Assign costs to virtual links to push toward area-disjoint path
selection to possible extent. For example, a possibility would
be to set the cost of a virtual link from border node A to
destination D to W=H*K, where H is the maximum intra-area
diameter throughout the whole network, and K is the number of
areas between two areas in the shortest path between A and D;
- When the head-end node creates the PATH message, it may
immediately select which path would be the working one and which
the backup one, or it may await the two paths to be established
before selecting the working one; only in the latter case it is
possible to guarantee that the shortest path is selected as the
working one. This point may require further analysis;
- Possibility to implement bandwidth sharing exploiting the ARO
object;
- Extensions to SRLG- and link-disjoint paths;
- Extensions to dual-fault protection.
6. Terminology
SRLG: A group of links that may be affected by the same fault;
LSP: Label Switched Path; more details can be found in [MPLS];
TE: Traffic Engineering;
DÆAchille et al. Internet draftûexpires July 2004 Page 23 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
ERO: Explicit Route Object, see [RSVP-TE];
XRO: eXclude Route Object, see [EXCLUDE-ROUTE];
RRO: Record Route Object, see [RSVP-TE];
ARO: Associated Route Object. Defined in this document;
Area_ID: An area identifier, see section 4.3;
PATH: Downstream RSVP message, see [RSVP];
RESV: Upstream RSVP message, see [RSVP];
7. Security Considerations
None
8. References
[TRAP-AVOID] -Dahai Xu, Yizhi Xiong, et al., ôTrap
avoidance and protection schemes in networks
with shared risk link groupsö, IEEE Journal
of Lightwave Technology, November 2003
[EXCLUDE-ROUTE] -CY Lee, A. Farrel, S. De Cnodder, ôExclude
routes û extension to RSVP-TEö, draft-ietf-
ccamp-rsvp-te-exclude-route-01, work in
progress
[VASSEUR] -J.P. Vasseur ôInter-AS MPLS Traffic
Engineeringö, draft-vasseur-inter-as-te-01,
work in progress
[RSVP-TE] -RSVP-TE: Extensions to RSVP for LSP Tunnels,
RFC3209
[RSVP] -Resource ReserVation Protocol, vers.1,
RFC2205
[DOVERSPIKE] -B.Doverspike, Guanzhi Li, C Kalmanek, ôFiber
Span Protection in mesh optical networksö, AT&T
Labs, Optical Network Magazines vol.3, No.3,
May/June 2002.
[SUURBALLE] -J.W. Suurballe, ôDisjoint paths in a
networkö, Networks, pp.125-145, 1974
[BHANDARI] -R. Bhandari, ôSurvivable Networks ûAlgorithms
for Diverse Routingö, AT&T Labs, Norwood, MA:
Kluwer, 1999.
[FAULT-NOTIFY] -R. Rabbat, V. Sharma, ôFault notification
protocol for GMPLS-based recoveryö, draft-
rabbat-fault-notification-protocol-03, work
in progress
[MPLS] -Multi Protocol Label Switching Architecture,
RFC3031
[GMPLS] -Generalized Multi Protocol Label Switching,
RFC3471
DÆAchille et al. Internet draftûexpires July 2004 Page 24 of 25
draft-dachille-inter-area-path-protection-01.txt January 2004
9. AuthorsÆ Addresses
Alessio DÆAchille CoRiTel (Consorzio di Ricerca sulle
Telecomunicazioni), V. Cavour 256, Rome, Italy
Email: dachille@coritel.it
Marco Listanti Full Professor University of Rome,
"La Sapienza", Italy
Email: listanti@infocom.uniroma1.it
Ugo Monaco PhD Student University of Rome,
"La SApienza", Italy
Email: monaco@infocom.uniroma.it
Fabio Ricciato CoRiTel (Consorzio di Rcerca sulle
Telecomunicazioni), V. Cavour 256, Rome, Italy
Email: ricciato@coritel.it
Vishal Sharma Metanoia, Inc.
1600 Villa Street, Unit 352
Mtn. View, CA 94041
Email: v.sharma@ieee.org
DÆAchille et al. Internet draftûexpires July 2004 Page 25 of 25
