MPLS Working Group, S.Venkatachalam Internet Traffic Engineering Working Group Alcatel USA Internet Draft Document: S.Dharanikota draft-venkatachalam-interarea-mpls-te-01.txt Nayna Networks Expiration Date: April 2001 A Framework for the LSP Setup Across IGP Areas for MPLS Traffic Engineering Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 except that the right to produce derivative works is not granted. This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft 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. 1. Abstract In this draft, we propose an architecture for the inter-area LSP setup based on criteria (combination of constraints). We derive the architectural requirements for the routing protocols, signaling protocols and the MIBs to support such an idea. We also demonstrate how such a mechanism will reduce the crankback during LSP setup. A possible outline of the modifications to the CSPF algorithm and examples are presented. In the companion document [INTER_AREA_EXT] we elaborate on the extensions required for such architecture. 2. Acronyms ABR Area Border Router AS Autonomous System ASBR Autonomous System Border Router CR-LDP Constraint Based Routing LDP CSPF Constraint-based Shortest Path First IGP Interior Gateway Protocol ISP Internet Service Provider LDP Label Distribution Protocol LER Label Edge Router LSA Link State Attribute LSR Label Switch Router LSP Label Switched Path MIB Management Information Base MPLS Multi Protocol Label Switching RSVP Resource Reservation Protocol TE Traffic Engineering The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [RFC2119]. 3. Introduction Current work in the MPLS traffic engineering group (such as [TE_FRAMEWORK], [QOS_CONST]) focuses only on the intra-area LSP setup issues. In this work we propose an architecture to extend the traffic engineering capability across IGP areas and recommend relevant modifications to the routing protocols, signaling protocols and MIBs. The ISP's networks are divided into Autonomous Systems (ASs), where each AS is divided into IGP areas to allow the hiding and aggregating of routing information. Although this concept of hierarchical routing by an IGP makes sense from the routing perspective, it is a bottleneck for traffic engineering as it hides the path taken by a packet to destinations in the other routing areas. Hence, from the TE perspective, requirements such as path selection and crankback need different architectural additions to the existing IGPs and signaling protocols for inter-area LSP setup. Traffic engineering practice currently involves the setup and use of Label Switched Paths (LSPs) as dedicated bandwidth pipes between two end points. LSPs can be setup across several routers, either through the use of manually specified routes, or routes that are computed. The routes can be computed offline through the use of a dedicated tool, or through the use of online constraint based routing using an IGP [IGP_REQ, RSVP_EXT]. The offline tool will be centralized, and has the advantage of being able to consider the traffic pattern history over a large period of time, and hence will be efficient in optimizing the resources over time, not just the particular instant when the request is received. The offline traffic engineering tool, if also used for LSP setup in addition to routing, may be able to optimize the resources across LSPs. This would include mechanisms to tear down LSP segments and reroute them when better resources become available or when new requests arrive. The online constraint based routing model [IGP_REQ] requires (1) a constraint based routing process implemented on certain LSRs that serve as LERs to the LSPs, and (2) a set of mechanisms to flood out and maintain the TE characteristics of the topology. From [TOOL_VS_RP] discussion, it is clear that traffic engineering can be implemented with the help of tools and routing protocol extensions, as initiated by [IGP_REQ]. Although there has been some work in the area of realizing some of the issues such as TE crankback [CRANKBACK] and DiffServ realizations [QOS_CONST], [QOS_TE_EXT], no work has been performed that is either directly related to the inter-area extensions or a framework for such in the TE working group. In our solution, we propose to send across IGP areas, the summary routes containing criteria-based route attributes, which will be used at the ASBRs in their TE path computation. Since an off-line TE tool cannot compute the complete explicit path from ASBR to ASBR unless it knows the complete routing table of the AS, we expect to have loose path specification, which can be translated into explicit path in-steps at the intermediate ABRs. The solutions we are providing in this draft are applicable to the destination networks inside the AS or outside the AS. For the sake of simplicity we consider the customer networks inside an autonomous system. In section 4, we present the outline of the architecture, which will be used to derive the routing and signaling requirements in section 5. We present examples in section 6 to consolidate the ideas presented in this document. Scalability issues of these solutions are discussed in section 7. Security considerations, acknowledgements and references follow in sections 8, 9 and 10 respectively. 4. Architecture 4.1. Definitions LSP section: An LSP section is that part of the inter-area LSP, that which lies completely inside an IGP area; the inter-area LSP is a sequence of LSP sections, connected at the ABRs. Each LSP section lies in a different area. Head node of the LSP section: The head node of an LSP section is either the originating node or transit ABR depending on whether the LSP section is the first or a subsequent LSP section. Criteria: A criteria is a combination of the constraints (as specified in the works in progress, such as [CR_ROUTING], [QOS_CONST]), which will provide a path setup mechanism to choose between different paths available between two end-points of the LSP. 4.2. Approach The current inter-area approaches try to setup an LSP across areas without prior knowledge of the resources available across the area boundaries. If the required constraints on the resources are not met, crankback schemes [CRANCKBACK] are used to backtrack to the previous nodes and take an alternate path. This may turn out to be expensive in terms of the time needed to compute a new alternate path, and resources needed to maintain the state information to determine an alternate path (which is different from the current path kept as state information in memory). This draft presents an approach to solving the problem of LSP setup across IGP areas, through the use of the following components: - IGP intra-area TE advertisements [INTRA_AREA, IGP_REQ] - IGP inter-area TE summary advertisements [INTER_TE_OSPF, INTER_TE_EXT] and - Extensions to the signaling protocols [INTER_TE_EXT] Our approach relies on the inter-area summary TE resource availability information to determine efficiently whether an inter-area path to the destination is at all possible with the constraints given. This inter- area TE resource availability information is obtained from the link state IGPs based on TE extensions [INTER_TE_OSPF, INTER_TE_EXT]. These extensions provide a means to summarize the TE resource availability attributes of destinations outside an area and advertise these summaries into the target area by its ABR. Our solution is independent of the TE attributes that need to be summarized with some restrictions as discussed in the following sections. Since these summaries provide a clear picture of the resources available across areas, the probability of encountering a node (in another area) where resources cannot be allocated to the LSP, is minimized. The summary TE resource availability information also helps in determining the ABR that is "closest" to the destination in terms of the resources required for the LSP section. This determination is similar to the route calculation based on summarized routes across areas in the link state IGPs. Our draft presents a two criteria approach when selecting the ABR. At the originating node of the LSP, the ABR that is in the path to the destination with the most resources is determined using the TE summary LSAs. The originating node will then compute an intra-area path to this ABR based on the constraints. Such an intra-area path computation will be based on the intra-area TE LSAs [INTRA_AREA][IGP_REQ]. Once a path to the ABR is determined, an LSP is setup from the originating node to the ABR using the MPLS signaling mechanisms of RVSP-TE or CR-LDP. The signaling mechanisms of RSVP-TE and CR-LDP will be extended to carry the constraints of the LSP. Hence at the transit ABR, the original constraints are available for any further routing calculations. Once the first LSP section is setup up from the originating node of the LSP to the ABR (say ABR1), ABR1 will try to setup the next LSP section. If the final destination (of the inter-area LSP) is in one of ABR1's directly connected areas, the next LSP section is the last LSP section and terminates at the final destination of the inter-area LSP. Else, if the final destination (of the inter-area LSP) is in an area that can only be reached through another ABR (say ABR2), the next LSP section is a transit LSP section between ABR1 and ABR2. ABR1 will perform an intra-area route computation to determine a path for the next LSP section based on the constraints. ABR1 will then perform the signaling to setup this next LSP section. If the LSP section just setup is the last LSP section, the constraint based LSP setup process is complete. Else, if the LSP section just setup is a transit LSP section to ABR2, the process of setting up an new LSP section toward the destination continues at ABR2, just like at ABR1. This process of setting up LSP sections is iterative, till the destination node is reached. If at any point in the LSP setup process an LSP setup is a failure, due to unavailability of resources, the LSP setup cranks back to the immediately preceding ABR. In an OSPF domain with no virtual links, a maximum of three LSP sections are possible (when the originating node and destination nodes are in different areas, neither of which is the backbone area). 4.3. Concept of criteria The LSP path setup mechanisms will use the criteria to determine the best possible path for the LSPs. We introduce the concept of primary and secondary criteria to determine the possible alternative paths for the LSPs. The application, which is requesting for an LSP setup, should be able to request for both the criteria, which will be used by the transit ABRs to determine the alternative path in case of a path with the primary criteria is not available. The concept of primary and secondary criteria is useful in the following cases: - The resources to satisfy the primary criteria are not available in the intermediate areas - use the secondary instead of the primary criteria to reduce the crankback, - The LSAs propagated by the IGP are not up-to-date and hence a failure occurs at the intermediate routers, and - The intermediate ABRs make their own decisions based on the secondary criteria to reduce LSP setup time during crankback. The following are the guidelines for the proper operation of this concept: - The Secondary criteria SHOULD be a subset of the primary criteria or at least SHOULD be lower/inferior in terms of the resource requirements. - Both the primary and the secondary criteria SHOULD consist of TE attributes that are derivable from the summary information which is allowed to propagate across the ABRs, according to the proposed MIB requirements in the following sections. - The LSP constraints for the inter-area LSP can be a combination of several TE attributes, which can be satisfied during intra-area path computation. However, the primary criteria (and hence the secondary criteria) used for inter-area computations SHOULD be a subset of these LSP constraints so that the inter-area computations are not expensive. - Once a secondary criteria section is setup during path establishment, the remaining path computation SHOULD be performed based on the secondary criteria. - (Primary/secondary criteria, Primary LSP) SHOULD be complimentary to (Primary/Secondary criteria, Backup LSP), i.e., the primary and backup LSPs SHOULD not have any intersecting path. 4.3.1. Example for the selection of criteria Consider the following TE constraints: - Class types [QOS_CONST], - Available bandwidth [TE_FRAMEWORK], - Color [TE_FRAMEWORK], - TE metric [TE_FRAMEWORK], - Delay, - Number of hops, etc. A criteria can be a combination of the above constraints, such as (Class type 1, Available bandwidth = 10, Red color). If this is the primary criteria, then the secondary criteria should be a subset of the primary, such as (Class type 2, Color Red) where Class type 2 is inferior to Class type 1 in terms of "some" requirements. Also note that the available bandwidth requirement is also relaxed in the secondary criteria. Although it is not recommended that a summary LSA should advertise all the above constraints into other areas (from scalability point-of- view), note that for a criteria to be accepted (either primary or secondary) for LSP setup, the criteria should be derivable from the summary LSA TE constraints. This poses the MIB requirements as mentioned in the above subsection on the guidelines. 4.4. The LSP setup process The process of setting up an LSP across areas is as follows. For each LSP section: 1. At the source, a trigger to setup the primary and the secondary paths is received by the LSP setup module. 2. This module requests the routing module for a route to setup the primary or secondary path. 3. The routing module determines the closest ABR that has the best possible route based on the constraints, to the inter-area destination, 4. The routing module calculates an intra-area route from the head node of the LSP section to the transit ABR that satisfies the constraints, 5. The signaling module performs signaling and sets up the LSP section (intra-area) from the head node of the LSP section to the transit ABR. 6. At the transit ABR, the signaling module transfers the constraints to the routing module and requests a route for the next LSP section 7. If the final destination is not in this area, repeat the setup process of 3, 4, 5 and 6 for the next LSP section, with the transit ABR at the head of the next LSP section. 8. If the final destination is in this area, calculate an intra-area route from the transit ABR to the destination that satisfies the constraints, then signal and setup the final LSP section completing the inter-area LSP setup. 9. If the setup of any LSP section is a failure, then crankback to the immediately preceding ABR and perform a new LSP section setup, up to a maximum of certain number of attempts. 4.5 Routing algorithm The routing process at the head node of each LSP section performs the following calculation: 1. If the destination is in the same area, perform a complete intra- area route calculation based on all the constraints. If such a path is found, go to 4. 2. If the destination is outside the area, do the following computation: 2.1 ABR-list = {list of all ABRs in the area} - {list of ABRs notified as ineligible via crankback} 2.2 While (ABR-list != {}) /* do while ABR-list is not empty */ { 2.2.1 Use the inter-area TE summary LSAs to determine the ABR with the greatest resources that satisfies the primary criteria 2.2.2 If no such ABR, break to 2.3. 2.2.3 Use the intra-area TE LSAs to determine a path to the selected ABR that satisfies all the constraints of the LSP 2.2.4 If such a path is found, goto 4 and start the signaling process to setup the LSP section to the selected ABR. 2.2.5 Else, ABR-list = ABR-list - {selected ABR} } 2.3 ABR-list = {list of all ABRs in the area} - {list of ABRs notified as ineligible via crankback} 2.4 While (ABR-list != {}) /* do while ABR-list is not empty */ { 2.4.1 Use the inter-area TE summary LSAs to determine the ABR with the greatest resources that satisfies the secondary criteria 2.4.2 If no such ABR, break to 3. 2.4.3 Use the intra-area TE LSAs to determine a path to the selected ABR that satisfies all the constraints of the LSP 2.4.4 If such a path is found, goto 4 and start the signaling process to setup the LSP section to the selected ABR. 2.4.5 Else, ABR-list = ABR-list - {selected ABR} } 3. No suitable route was found and the LSP setup is a failure -signal back the error. 4. A route was found, start the signaling process. In the case of backup LSP computation, the above algorithm applies with the following changes: 1. In 2.1 and 2.3: ABR-list = {list of all ABRs in the area} {list of ABRs notified as ineligible via crankback} - {list of ABRs in the primary LSP} 2. In 2.2.3 and 2.4.3, calculate the inter-area path that doesn't include any nodes in the primary path The following sections detail the requirements for the routing and signaling components, crankback and general applicability. 5. Requirements of the solution The requirements of criteria-based inter-area routing are separated into routing protocol requirements, signaling protocol requirements and other requirements. 5.1. Requirements for the IGP 5.1.1. Intra-area requirements The IGP SHOULD support [INTRA_TE] to advertise and distribute the TE information of the interfaces of the area. When there is a request for the setup of a constraint based LSP within the area, the IGP will determine the best path that satisfies the constraints by performing a CSPF computation on the TE resources of the area, as specified by the intra-area TE-LSAs. With respect to the setup of LSPs within an area, the constraints on the LSP can be one or more of the TE attributes flooded by the IGP in the intra-area TE LSA. 5.1.2. Inter-area requirements The Inter-area TE summary information is used by the route computation process: - to determine if a path to the inter-area destination that satisfies the constraints does exist, and - to determine the ABR to reach the next area. To do such a computation, the IGP SHOULD be able to support TE attribute summarization across areas, such as in [INTER_TE_OSPF] and [INTER_TE_EXT]. To allow traffic engineering across areas, the ABRs of the IGP SHOULD perform TE attribute summarization; similar to the route summarization that is already a part of the link state IGPs. In the general case of TE attribute summarization, any number of TE attributes such as bandwidth, delay to a destination can be summarized. These attributes can be summarized through the use of a dijkstra or dijkstra-like algorithm depending on whether the TE attribute is an additive metric, or Max-Min metric, or some other type. The value of the TE summary attribute to a destination advertised by an ABR represents the TE resources of the best path available from the ABR to that destination based on that TE attribute alone. For example, the value of the summarized unreserved bandwidth attribute may be defined as in [INTER_TE_OSPF]: "The unreserved bandwidth to the summary destination is the largest of all path-unreserved bandwidths, each associated with a possible path to the destination. The path-unreserved bandwidth is the smallest unreserved bandwidth of all the links in the path. Hence, the unreserved bandwidth is the maximum amount of traffic that can currently be sent to that destination, the other traffic on the links being steady." The summarized TE attributes will be distributed inside the areas by the use of new link state messages for the purpose in OSPF and ISIS as defined in [INTER_TE_OSPF] and [INTER_TE_EXT]. 5.1.3. Virtual links (TBD) 5.2. Signaling requirements The signaling requirements are divided into setting up the initial LSP (both primary and backup) and usage of the crankback facility during LSP setup. 5.2.1. LSP setup 5.2.1.1. Primary LSP setup Signaling SHOULD be extended to carry the criteria based elements, such as: - Primary criteria (Attribute 1, ... , Attribute N) - Secondary criteria (Attribute 1, ... , Attribute N) Signaling SHOULD trigger IGP computation for the explicit route in an area at the transit ABRs. If a path which satisfies the primary criteria is not available, then it should trigger an IGP computation for a path that satisfies the secondary criteria. It MAY inform the initiating node about the change in the criteria for the path set up in the intermediate path. This deliberate notification can also be derived when the actual setup is completed. 5.2.1.2. Setting up the backup LSP As this architecture distributes the LSP setup decisions, the intermediate ABRs SHOULD know the path taken by the primary and the backup LSPs. This enables the signaling component to request for a backup path that's different from the path taken by the primary LSP, during backup LSP setup. Hence, signaling SHOULD be extended to carry the complete path of the primary LSP when setting up the backup LSP. The same mechanisms used for the primary LSP setup SHOULD be used for the backup LSP setup also. During the computation of the backup LSP, the algorithm SHOULD consider the guidelines proposed in section 4.3. 5.2.2. Crankback during LSP setup Crankback in an area SHOULD always be performed from the upstream ABR of that LSP section. The mechanisms defined in section 5.2.1 will be used for the setting up of the primary or the backup LSP. If the path is not available, the information will be sent to the immediately preceding ABR to retry the setup. If the node that returns the error is itself an ABR, this node should not be tried in the following attempts. Hence, at the preceding ABR the routing process will determine a new route after pruning the previously selected but unsuccessful ABRs from the computation. 5.2.3. LSP section repair An interesting bi-product for this draft is the section repair. This draft considers repair of LSPs within a certain area - i.e., when the failure is in a certain an LSP section is detected (during the data transfer phase), an LSP section-level repair can be initiated. The error information is sent back to the immediately preceding ABR where a different path to the destination of the LSP section is determined, and a new LSP section setup is attempted. If successful, then the new LSP section is spliced in to repair the LSP. 5.3. MIB requirements The configuration requirements for such an architecture can be divided into: - Routing configuration, such as criteria filtering, criteria- constraint mapping etc. - LSP Setup configuration, such as primary criteria and backup criteria etc. - Signaling configuration, such as the criteria change in the intermediate segment notification, crankback in-progress notification required etc. These configuration items are further elaborated in the extensions to the inter-area draft for the signaling and routing [INTER_AREA_EXT]. 6. Examples for the criteria-based route advertisement Let us assume that, as shown in Figure 1, an autonomous system has three areas, Area 1 with network N1, and area border routers ABR1, ABR3 with area 0; and Area 2 with network N2, with area border routers ABR 2 and ABR 4 with area 0. Consider the case when a router on N1 wishes to setup a criteria-based LSP to N2 with the primary criteria being: (required bandwidth = 10 Mbps and required interfaces = color red) and the secondary criteria being: (required interfaces = color red). 6.1. Example for basic inter-area LSP setup Single Autonomous System Area 1 Area 0 Area 2 -------------------- ------------------ ------------------------ | | | | | | | |N1 PPS1 ------- PPS3 -------- PPS5 |N2 | | |-------------- |ABR1 |--------X-----|ABR 2 |----------------| | | | | |-----| | | | | | |-------| ------- | PSS7 -------- |------| | | PSS2 | ------- ---------------- | PSS6 | | --------|ABR 3 |--------------|ABR 4 |--------- | | ------- PSS4 -------- | | | | | | | -------------------- ------------------- ------------------------- Legend: N# - Network (Note: This could be outside or inside the AS) PPS# - Primary LSP, Primary Criteria Section Number PSS# - Primary LSP, Secondary Criteria Section Number Figure 1: An example for basic LSP setup across areas in an autonomous system The originating router and the area border routers calculate the primary LSP, primary criteria sections in their area. As shown in Figure 1, the sections PPS1, PPS3, PPS5 may represent the desired path. Similarly, the secondary path from N1 to N2 is PSS2, PSS4, PSS6. During the computation of the primary path, as a fallback when the primary criteria is not available (as on PPS3) the setup mechanism can take sections from secondary path (such as PSS7). Note that once the secondary criteria is used in a section, the later sections should also use the secondary criteria and convert the previous sections with primary criteria into secondary during the reservation phase. 6.2. Backup LSP creation example The same logic used in the previous case needs to be used except that the path selected for the backup should be non-intersecting with the above path. This can be done in a distributed manner if the primary LSP path is known. 6.3. Example for crankback during LSP setup Single Autonomous System Area 1 Area 0 Area 2 -------------------- ------------------ ------------------------ | | | | | | | |N1 PPS1 ------- PPS3 -------- PPS5 |N2 | | |-------------- |ABR1 |--------------|ABR 2 |--------X-------| | | |-------| ------- -------- --|PPS7 |------| | | PSS2 | ------- PSS4 -------- |-----| PSS6 | | --------|ABR 3 |--------------|ABR 4 |--------- | | ------- -------- | | | | | | | -------------------- ------------------- ------------------------- Legend: N# - Network (Note: This could be outside or inside the AS) Figure 2: An example for crankback LSP setup in an autonomous system If PPS5 fails, as shown in Figure 2, the crankback can be done from ABR2 to by pass PPS5. 7. Scalability (TBD) 8. Security considerations Security issues will be considered in the later versions of the document. 9. Acknowledgements The authors thank Darek Skalecki on his insightful comments on the draft. 10. References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997 [CRANKBACK] A. Iwata, N. Fujita, G. Ash, "Crankback Routing Extensions for CR-LDP," <draft-fujita-mpls-crldp-crankback-01.txt> [IGP_REQ] T. Li, G. Swallow, D. Awduche, "IGP Requirements for Traffic Engineering with MPLS," <draft-li-mpls-igp-00.txt> [INTER_AREA_EXT] S. Dharanikota, S. Venkatachalam, "OSPF, IS-IS, RSVP, CR-LDP extensions to support inter-area traffic engineering using MPLS TE," <draft-dharanikota-interarea-te-ext-00.txt> [INTRA_AREA] D. Katz, D. Yeung, "Traffic Engineering Extensions to OSPF," <draft-katz-yeung-ospf-traffic-01.txt> [INTER_TE_OSPF] S. Venkatachalam, and B. Abarbanel, "OSPF Extensions to Support Inter-Area Traffic Engineering," <draft-venkatachalam-ospf- traffic-00.txt > [QOS_CONST] F. Le Faucheur et al., "Requirements for support of DiffServ-aware MPLS Traffic Engineering," <draft-lefaucheur-diff-te- reqts-00.txt> [QOS_TE_EXT] F. Le Faucheur et al., "Extensions to IS-IS, OSPF, RSVP and CR-LDP for support of DiffServ-aware MPLS Traffic Engineering," <draft-lefaucheur-diff-te-ext-00.txt> [RSVP_EXT] D. Awduche et al., "Extensions to RSVP for LSP Tunnels," <draft-ietf-mpls-rsvp-lsp-tunnel-04.txt> [TE_FRAMEWORK] D. O. Awduche, et al., "A Framework for internet Traffic Engineering," <draft-ietf-tewg-framework-02.txt> [TOOL_VS_RP] "Internet Traffic Engineering working group mailing list discussion on centralized tool based TE versus constraint-based routing protocol extensions," ftp://ftpext.eng.uu.net/tewg 11. Authors' addresses Senthil K. Venkatachalam Alcatel USA 45195 Business Court, Suite 400 Dulles, VA 20166 Email: Senthil.Venkatachalam@usa.alcatel.com Phone: (703)654-8635 Sudheer Dharanikota Nayna Networks 157 Topaz Drive Milpitas, CA 95035 Email: sudheer@nayna.com Phone: (408)-956-8000 x357