Internet Draft A. DÆAchille (CoRiTel) Expiration Date: July 2004 M. Listanti (La Sapienza) U. Monaco (La Sapienza) F. Ricciato (CoRiTel) V. Sharma, Ed. (Metanoia, Inc.) January 2004 Inter-Area MPLS Path Protection 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-00.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-00.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-00.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-00.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-00.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-00.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-00.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. Both limitations were already mentioned in [VASSEUR], which proposed as an alternative the joint selection of the working and backup paths in a centralized route server. 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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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-00.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; GLSP: Generalized LSP; more details can be found in [GMPLS]; TE: Traffic Engineering; DÆAchille et al. Internet draftûexpires July 2004 Page 23 of 25 draft-dachille-inter-area-path-protection-00.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-00.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