MPLS Working Group, S.Venkatachalam Internet Traffic Engineering Working Group D. Papadimitriou Internet Draft Alcatel Document: draft-venkatachalam-interarea-mpls-te-02.txt S.Dharanikota Expiration Date: June 2002 Nayna Networks 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 a 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 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]. 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]. This draft describes a framework for inter-area LSP setup. Inter-area routing is one of the main mechanisms used today to provide scalability within a IGP routing domain. Refer to RFC2329 for details regarding the usage of inter-area OSPF routing. In our solution, we propose to send across IGP areas, the summary routes containing TE route attributes, which will be used at both the ABRs, and the ASBRs in their TE path computation. Since an off-line TE tool cannot compute the complete explicit path from ASBR to ASBR (end to end within the AS domain) 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 LER performing the CSPF inside a given 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. The head node could also be another LSP tunnel previously setup (allowing LSP hierarchy) or forwarding adjacencies (FAs). 4.2. Approach 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]. The TE summary information propagated into an area could be that of forwarding adjacencies (FAs), in addition to networks. The TE summary values may need to be propagated only for a limited number of important exit points (LERs) in an area. 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. 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. 4.3. 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 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 route computation is performed based on the LSP constraints received via the LSP setup message 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.4 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 constraints 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} 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 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 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 LSP setup constraints [INTER_AREA_EXT], such as: - constraint list (TE Attribute 1, ... , TE Attribute N) Signaling SHOULD trigger IGP computation for the explicit route in an area at the transit ABRs. 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 constraint filtering - LSP Setup configuration, such as constraints - Signaling configuration, such as 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 inter-area LSP setup 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 an LSP to N2 with constraints: 6.1. Example for basic inter-area LSP setup Single Autonomous System Area 1 Area 0 Area 2 -------------------- ------------------ ------------------------ | | | | | | | |N1 PS1 ------- -------- PS3 |N2 | | |-------------- |ABR1 |\ |ABR 2 | -------| | | | ------- \ PS2 -------- / | | | ------- \ -------- / | | |ABR 3 | -----------|ABR 4 |-----/ | | ------- -------- | | | | | | | -------------------- ------------------- ------------------------- Legend: N# - Network (Note: This could be outside or inside the AS) PS# - Primary LSP Section Number Figure 1: An example for basic LSP setup across areas in an autonomous system The originating router router determines the ABR to go through as ABR1 based on the TE summary LSA, and calculates the primary LSP section in its area, Area 1. ABR1 performs a similar inter-area computation to pick ABR4, and an intra-area computation to determine the path of the LSP section PS2. At ABR4, similar route computations are performed followed by the signaling setup of the section PS3, completing the setup of the desired LSP. 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 PS1 ------- PS2 -------- PS3 |N2 | | |-------------- |ABR1 |--------------|ABR 2 |--------X-------| | | | ------- -------- --|PS4 |------| | | ------- -------- |-----| | | |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 PS3 fails, as shown in Figure 2, the crankback can be done from ABR2 to by pass PS3. 7. Scalability The architecture is scalable in terms of the TE summarized routing information to be propagated since the most important LERs that need the inter-area LSPs are the ASBRs and their associate networks. Also, the use of FAs for the destination LERs/networks will further reduce the TE summary information, allowing even better scalability. The architecture proposed distributes the computation across various routers in the network, avoiding the bottleneck due to the use of designated path computation servers, and hence scales well for a large number of LSPs. 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, et. al., "Crankback Routing Extensions for CR-LDP," [IGP_REQ] T. Li, G. Swallow, D. Awduche, "IGP Requirements for Traffic Engineering with MPLS," [INTER_AREA_EXT] S. Dharanikota, S. Venkatachalam, "OSPF, IS-IS, RSVP, CR-LDP extensions to support inter-area traffic engineering using MPLS TE," [INTRA_AREA] D. Katz, D. Yeung, "Traffic Engineering Extensions to OSPF," [INTER_TE_OSPF] S. Venkatachalam, and B. Abarbanel, "OSPF Extensions to Support Inter-Area Traffic Engineering," [QOS_CONST] F. Le Faucheur et al., "Requirements for support of DiffServ-aware MPLS Traffic Engineering," [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," [RSVP_EXT] D. Awduche et al., "Extensions to RSVP for LSP Tunnels," [TE_FRAMEWORK] D. O. Awduche, et al., "A Framework for internet Traffic Engineering," [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 15036 Conference Center Drive Chantilly, VA 20151 Email: senthil_v@lycos.com Phone: (703)679-6435 Sudheer Dharanikota Nayna Networks 157 Topaz Drive Milpitas, CA 95035 Email: sudheer@nayna.com Phone: (408)-956-8000 x357 Papadimitriou Dimitri Alcatel “ IPO NSG-NA Francis Wellesplein 1, B-2018 Antwerpen, Belgium Phone: +32 3 240-8491 Email: dimitri.papadimitriou@alcatel.be