Network Working Group Manayya KB INTERNET-DRAFT Wipro Technologies Intended status:Proposed Standard Apr 17, 2009 Expires: Oct 16, 2009 Constrained Shortest Path First draft-manayya-constrained-shortest-path-first-01.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. 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. This Internet-Draft will expire on Oct 16, 2009. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Abstract Constrained Shortest Path First (CSPF) is an advanced version of shortest path algorithms used in OSPF and IS-IS route computations. It is used in computing shortest path for label-switched paths (LSPs) based upon multiple constraints. While computing path for LSPs it considers topology of network, attributes of LSP and links. The path is computed using traffic engineering database which takes the extensions of OSPF(open shortest path first) and IS-IS (Intermediate system to Intermediate system) as input. Manayya KB Expires October 16, 2009 [Page 1] Table of Contents 1. Introduction..................................................2 2. Constraints...................................................3 3. CSPF algorithm................................................3 4. CSPF Process..................................................4 5. CSPF path selection procedure.................................5 6. Session attribute.............................................5 7. Administrative CSPF LSP events................................6 8. Event Triggers................................................7 9. IANA Considerations...........................................8 10. Security Considerations.......................................8 11. References....................................................8 1. Introduction OSPF and IS-IS extensions [3630] enable each router to flood extra information about each of its link attributes (Refer section 2). When the above information is flooded, each LSR stores the information in a database called the traffic engineering database. The ingress LSR then runs a special version of SPF called Constrained Shortest Path First (CSPF) which takes both the information in the traffic engineering database and the constraints configured as an input. After pruning paths that do not meet the configured constraints from the shortest-path-first (SPF) tree, CSPF derives the best available path based on the information in the traffic engineering database (TED). Based on the best available path, CSPF produces a strict Explicit Route Object (ERO) which the Resource Reservation Protocol (RSVP)[2205] uses to signal the LSP. Ingress LSP sends PATH messages to the egress to reserve resources for the LSP, the egress LSP sends RESV messages back to the ingress to distribute the labels, this sets up the LSP. After this process, RSVP makes entries into the unicast routing table. Manayya KB Expires October 16, 2009 [Page 2] 2. Constraints: CSPF considers the following constraints while performing shortest path computation. LSP attributes: Bandwidth requirements Hop limitations Administrative groups (link colors) Priority (setup and hold) Explicit route Link attributes Reservable bandwidth of the links (static bandwidth minus the currently reserved bandwidth) 3. The CSPF algorithm: a.Collect attribute information of the link to which each node is connected b.Flood the collected attribute information to other nodes using ISIS or OSPF extensions. c.Combine each node according to the information of the entities to which each link respectively belongs and forming the topology structure of each protection entity of whole network and related link attribute information d.Calculate constrained paths for the network. The CSPF algorithm applies two databases: 1.PATHS 2.TENT. The PATHS stores the information of the shortest path tree while the TENT stores the information of tentative nodes which have been attempted before finding the shorted path. The information of the node is added to the PATHS database only when the shorted path to a node has been found. 1) Put a node doing the calculation on PATHS, and TENT is pre-loaded from the local adjacency database. 2) While putting the node on PATHS, examine links from the node to each of its neighbor nodes. If a neighbor node is already in PATHS, this new path will be longer and thus ignored. If a neighbor node is in TENT and the new path is shorter, the old path is replaced with the new one. If the new path is the same length as the one in TENT, then the neighbor node has an equivalent path. If a neighbor node is not in TENT, then links and nodes that do not satisfy the LSP constraint conditions are deleted and nodes corresponding to links which satisfy the LSP constraint conditions are put on TENT. Manayya KB Expires October 16, 2009 [Page 3] 3) Put the nodes with least-cost from TENT to PATHS. 4) When TENT is empty or the destination node is already existed in PATHS, then the routing calculation is completed. 5) If there are equal-cost paths, then the most appropriate path is selected based on a certain policy; if there are several equal-cost paths to the same destination, one appropriate path needs to be selected as output of the calculation. There are three selection policies: random selection, maximum remaining bandwidth rate of path first and minimum remaining bandwidth rate of path first. Random: One of the remaining paths is picked at random. This rule places an equal number of LSPs on each link, regardless of the available bandwidth ratio. Least fill: The path with the largest minimum available bandwidth ratio is preferred. This rule tries to equalize the reservation on each link. Most fill: The path with the smallest minimum available bandwidth ratio is preferred. This rule tries to fill a link before moving on to alternative links. 4. CSPF process: 1. CSPF process begins at ingress router with parameters of bandwidth, setup priority, hold priority and method used incase of equal cost multipath such as random, least fill or most-fill. It determines the final destination (Egress router). 2. It checks for maximum hop count, include and exclude constraints configured. 3. Check each node for metric and hop count starting with Ingress. 4. For each node check if endpoint is already visited ,if yes then Skip the verification. if not check the link for metric, color and bandwidth (for constraints) . The information on each node includes administrative groups (Color), metrics, static bandwidth, reservable bandwidth, and available bandwidth priority level. The information contained in the traffic engineering database should be the same across all routers in the same traffic engineering domain. 5. If it fails then remove this link. 6. If it passes then select the link with shortest path to neighbor router, go to next link and repeat the step 4. 7. Repeat the steps 3 to 5 for all nodes 8. The result of the CSPF algorithm is formed into a strict-hop ERO (Explicit Route Object) 9. When the ERO is completed, the ERO is passed to the RSVP (Resource Reservation Protocol) process, where it is used for signaling and establishing the LSP in the network. 10. If it is not possible to find the path then indicate about not finding a route then retry after retry interval. Manayya KB Expires October 16, 2009 [Page 4] 5. CSPF path selection procedure: - Compute LSPs one at a time, beginning with the highest priority LSP (the one with the lowest setup priority value). IF LSPs have equal priority, CSPF starts with those that have the highest bandwidth requirement. - Prune the topology database (TED) of all the links that are not full duplex and do not have sufficient reservable bandwidth. - If the LSP configuration includes the include statement, prune all links that do not share any included colors. - If the LSP configuration includes the exclude statement, prune all links that contain excluded colors and do not contain a color. - Find the shortest path towards the LSP's egress router, taking into account explicit-path constraints. - If several paths have equal cost, choose the one whose last hop address is the same as the LSP's destination. - If several equal-cost paths remain, select the one with the fewest number of hops. - If several equal-cost paths remain, apply the CSPF load-balancing rule configured on the LSP (least-fill, most-fill, or random). The result of the above steps is a strict-hop ERO that details each hop along the calculated path. The ERO is passed to the RSVP protocol process, where it is used to signal and establish the LSP in the network. 6. Session attribute: Option 1: Retry_limit_counter Description: retry limit of CSPF path computations for a particular path Value: positive integer 7. Administrative CSPF LSP events: An administrative event is an event in which the operator interface and CSPF engine signal the CSPF -finite state machine to start or stop the CSPF state machine. Event 1: NoRoute Definition: CSPF calculation failed to find a route to the destination on the ingress router. This event must include an address it cannot reach. The listed address in this event may be the LSP egress address, an ERO address or an intermediate address. Status: Mandatory Manayya KB Expires October 16, 2009 [Page 5] Event 2: LinkDown Definition: Traffic engineering database does not include the link. Status: Mandatory Event 3: ComputationResultAccepted Definition: CSPF pruned the traffic engineering database of noncompliant links and found a shortest path. CSPF generated an ERO, which was then passed to the RSVP. Status: Mandatory Event 4 : ComputationResultIgnored Definition: during reoptimization, a CSPF path computation for a potential optimal path is performed. Various checks are performed to evaluate whether the new path is better than the existing one. If the new path is not better, the CSPF computation results for the new path are ignored and the new path is not signaled. Status: Mandatory Event 5 : CouldNotDetermineSelf Definition: the traffic engineering database cannot determine the address of the local router Status: Mandatory Event 6 : CantFindNon_OverlappingPath Definition: CSPF needed to compute an alternate path that did not intersect any other path. Status: Mandatory Event 7 : Reroute due to re-optimization Definition: CSPF switched over to the new path after finding an optimal path for LSP traffic Status: Mandatory Manayya KB Expires October 16, 2009 [Page 6] Event 8: RetryLimitExceeded Definition: the number of CSPF path computations for a particular path exceeded a configured retry limit. After this, the path is not recomputed or signaled, unless the user intervenes. Status: Mandatory Event 9: EmptyRouteEvent Definition: destination route for the LSP is not correct Status: Mandatory 8. Event Triggers: 1. The following actions triggers the NoRoute event. - when CSPF calculation is failed on the ingress router to find a route to the destination - A downstream node is not configured for the Resource Reservation Protocol (RSVP) or Multiprotocol Label Switching (MPLS) or - The loopback interface is not configured on the ingress/ egress routers or - A faulty Explicit Route Object (ERO) that causes a loop or contains a invalid address. 2. If traffic engineering database does not include the link due to link failure, then LinkDown event is triggered. 3. After generating an ERO and passed to the RSVP, ComputationResultAccepted event should occur. 4. The event ComputationResultIgnored should occur when - The optimization is purely metric based, so switching to the new path could increase bandwidth congestion on links. - Switching to the new path could cause preemption. - The metric of the new path is higher than that of the existing path. - The metric is the same on the new and existing paths, but the number of hops in the new path is higher than on the existing path. Manayya KB Expires October 16, 2009 [page 7] 5. The event CouldNotDetermineSelf should occur when traffic engineering is not configured for OSPF or ISIS. 6. The event CantFindNon-OverlappingPath should occur when error appears while running the adaptive feature to run shared explicit (SE)-style reservations, where no nonoverlapping paths are possible. 7. When the Retry_Limit_Counter expires then RetryLimitExceeded event must be triggered. 8. when destination route for the LSP is incorrect, EmptyRoute Event must be triggered. 9 IANA Considerations This memo includes no request to IANA. 10 Security Considerations The security considerations listed in OSPF [2328] and RSVP [2205] are applicable 11. References: [3630] D. Katz, K. Kompella, D. Yeung, "Traffic Engineering (TE) Extensions to OSPF Version 2" RFC 3630, September 2003. [2205] R. Braden, Ed, L. Zhang, S. Berson, S. Herzog, S. Jamin "Resource ReSerVation Protocol (RSVP) -- Version 1 Fun" RFC 2205, Sep 1997 [2328] J. Moy, "OSPF Version 2" RFC 2328, April 1998 Authors' Addresses Manayya KB Wipro Technologies Bangalore 560 100 India Email: manayya.kbm@wipro.com Comments are solicited and should be addressed to manayya.kbm@wipro.com Manayya KB Expires October 16, 2009 [Page 8]