Network Working Group Kireeti Kompella Internet Draft Juniper Networks Expiration Date: January 2001 Daniel O. Awduche UUNET (MCI Worldcom) Notes on Path Computation in Constraint-Based Routing draft-kompella-te-pathcomp-00.txt 1. Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Distribution of this memo is unlimited. 2. Abstract This draft presents some notes on Constraint-Based Routing. The main purpose is to standardize the terminology used, and define the semantics of the various constructs used in Constraint-Based Routing so that implementations from a wide variety of vendors will have (at least to the first order) similar results in path selection. A secondary goal is to define the semantics of optimization, which we define as the recalculation of routes that have already been computed and established. Kompella/Awduche [Page 1] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 3. Introduction Traffic Engineering is of increasing interest in today's networks. One of the objectives of Traffic Engineering is to obtain more control over the path packets take: to be able to specify explicitly the path that a certain class of packets takes [TE-REQ]. Constrained-Based Routing takes this one step further. Instead of specifying the path explicitly, link by link, one specifies a route in terms of the constraints that it should satisfy. The route specification is then automatically converted into an explicit path. This frees network administrators from the tedium of maintaining detailed path specifications, and allows them to view the network at a higher level of abstraction (i.e., in terms of resources and constraints rather than nodes and links), resulting in more scalable network operation. If the path computation and set up can be done dynamically (by a router), there are further advantages. One is resilience: if a node or link in an explicit path fails, the router that set up the path can attempt to compute an alternate acceptable path. If the explicit path in use becomes sub-optimal, the router can compute a better path and switch to the new path. For the purposes of this paper, we define a "route specification" (or simply "route") to be source IP address and a non-empty sequence of loose and strict hops (per [IP]) plus a set of constraints. We define a "path" to mean a sequence of strict hops. By Constraint- Based Routing, we mean the elaboration of a route specification into a path whereby each loose hop in the route is transformed into a sequence of strict hops such that the last strict hop is identical to the loose hop and the transformation is subject to the route's constraints. A route's sequence is thus a subsequence of the elaborated path. We call the process of transforming a loose hop into a sequence of strict hops a "path computation". If a route is successfully elaborated into a path, the path can then be instantiated, that is, signalled and used for forwarding traffic; we call the route "operational". By "optimization" of a route, we mean the recomputation of a path for an operational route. Path computation requires that one has topological information about the network (in order to elaborate loose hops into paths), as well as the relevant resource information at each network element (in order to meet the constraints). Link state protocols distribute the topology of a network; there are currently standards-track drafts that specify how link state protocols can distribute the additional information needed for the computation of Constraint-Based Routes [ISIS-TE, OSPF-TE]. However, the semantics of such information, as well as details of path selection are less clearly (or indeed, not at all) specified. This leads to the raison d'etre for this paper: what Kompella/Awduche [Page 2] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 kinds of constraints are there, and what does it mean to satisfy them? If there are several acceptable paths for a route, how does one decide when one is better than another? A second objective is to specify when a path resulting from the optimization of a route should be preferred over the existing path. The issue here is that switching from an existing path to a new one could be service disruptive and cause some packet loss. Thus, one would like to specify the criteria to use to judge that a newly computed path is sufficiently better than the current path so that a switch-over is warranted. This paper does NOT specify how to implement Constraint-Based Routing. However, the Dijkstra Shortest Path First algorithm is easily adapted to path computation, based on the semantics presented. 4. Constraints and Resources Constraints and resources are counterparts to one another: routes have constraints, network elements have resources. As one explores paths, one checks the constraints for the route against the resources along the path to see that the constraints are met. The set of resource information available during computation thus determines the meaningful constraints that one can specify on a route. In this section, we list constraints, their corresponding resources, and a proposed semantics for each, where by 'semantics' we mean how the constraint is to be measured up against the resource. Constraints can be divided into Boolean and quantitative; some constraints can be of both types. Boolean constraints say whether or not a path is feasible. Quantitative constraints assign numerical values to paths, so that one has a means of choosing among feasible paths. Resources can be divided into configurable, dynamic and topological. Configurable resources are those assigned by an administrator, for example, administrative groups and metrics for links. Dynamic resources are those that depend on the state of the network, and vary with time, for example, available bandwidth on a link. Topological "resources" are those that are enforced by the topology of the network, for example, path length. This categorization of resources measures the degree of control that an administrator has over the path computation process. Note that Constraint-Based Routing can easily become intractable if the constraints and their semantics are not carefully chosen. A seemingly simple problem to compute the shortest path subject to a Kompella/Awduche [Page 3] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 fixed delay bound is NP-complete. The set of constraints and methodology described here can indeed be implemented efficiently; care must be taken when adding new resources, constraints and semantics that Constraint-Based Routing is still computationally efficient. The methodology here is an adaptation of Dijkstra's Shortest Path First algorithm. With each constraint is associated an attribute. Each node has a set of attribute values that reflect the properties of the current best path to that node (in Dijkstra's algorithm, the analog is the current shortest distance to this node). Each attribute has an associated accumulator function and either an acceptor function or a comparator function. The inductive step in Dijkstra's algorithm is to extend a best path P to a node S by one link L = (S, E) to a best path P' to a neighboring node E. An accumulator function is applied at this stage. An accumulator function for attribute X with associated resource R takes as input S.X and L.R and produces a candidate value for E.X. The analog in Dijkstra's algorithm is extending the shortest distance to a node to a candidate shortest distance to a neighboring node. An acceptor function says whether the path P' resulting from the inductive step above satisfies a Boolean constraint (this has no analog in Dijkstra's algorithm). An acceptor function takes a node's candidate attribute and a Boolean constraint and outputs ACCept or REJect. A comparator function says whether a node's candidate attribute is better than the node's current attribute (the analog is distance comparison). It takes as input a node's candidate and current attribute values, and outputs ACCept, REJect or CONTinue. The next two subsections describe the semantics of Boolean and quantitative constraints, as well as accumulator and comparator functions for the associated attributes. Some terminology: if L is a directed link from node A to node B (often denoted L = (A, B)), we denote by S(L) the start node A, and by E(L) the end node B. Resources are values associated with network elements; each node in the network computes the values of all its own resources as well as those of each outgoing link, then distributes all the resource values through extensions to a link state protocol. Currently, resources are defined only for links; however, in the future, nodes may also have resources. L. denotes the value of the resource at link L. Attributes are values associated with nodes; they are initialized at the beginning of a path computation, updated during the computation, and discarded at the end of the path computation. An attribute value Kompella/Awduche [Page 4] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 to node N depends on the path taken to N (for example, distance from the start is a node attribute). N. denotes the value of the attribute at node N. Also, when a candidate alternative path to N is considered, the attribute of the candidate path at N is denoted N.cand. 4.1. Boolean Constraints and their Resources Boolean constraints include: administrative group constraints, bandwidth availability, delay bounds, and hop count bounds. The resources corresponding to the Boolean constraints are: administrative groups configured on links, available bandwidth on links, configured delay on links and nodes, and path length. (Note that delay is not carried by the current set of extensions to link state protocols.) It is important to note that, in principle, Boolean constraints should be link-local, i.e., deciding whether or not a link is acceptable should depend only on the link resources and the constraints, not on the path so far or other context. If this is not satisfied, computing constrained routes can easily become an NP- complete problem. For example, computing a shortest path with bounded delay is in fact NP-complete. However, delay and hop count are useful constraints, so we allow them. The downside is that a modified Dijkstra will not always find the optimal path, and may fail to find a path even though one exists. 4.1.1. Administrative Groups Every link in the network can be associated with a set of up to 32 administrative groups, represented as a 32-bit integer. A route can have administrative group constraints on the links that the path can traverse. Current implementations have at least two ways of describing administrative group constraints. One method is to specify 'include' and 'exclude' sets; the other is to specify an 'affinity' and 'mask'. Let the set of administrative groups associated with link L be L.AG, with bit representation ag. Let a route have an include set of INC (bit representation = inc) and an exclude set of EXC (bit representation = exc). If INC (respectively, EXC) is empty, the include (respectively, exclude) constraint is defined to be trivially satisfied. Otherwise, link L satisfies the include constraint iff L.AG includes at least one Kompella/Awduche [Page 5] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 administrative group from INC; L satisfies the exclude constraint iff L.AG excludes all administrative groups from EXC. L satisfies the administrative group constraint iff L satisfies both the include and the exclude constraints. Equivalently, link L is acceptable iff: (inc & ag) != 0 && (exc & ag) == 0 where & is bit-wise AND. If a link does not have a set of administrative groups (as opposed to having an empty set), by definition, it fails all non-trivial include and exclude constraints. Let a route have an affinity with bit representation aff, and a mask with bit representation m. The above link satisfies the affinity- mask constraint iff: (mask & ag) == aff The two methods of specifying administrative group constraints are close, but not equivalent. Here, equivalent means that given an include and exclude set, one can produce an affinity and mask that accept exactly the same set of links, and vice versa. In the interests of interoperability, it would be good to either converge on equivalent semantics or provide knobs to choose the semantics. Service providers and other users should provide guidance here. Attribute: none Acceptor: if appropriate conditional is TRUE then ACC else REJ 4.1.2. Bandwidth Availability A route can specify a required bandwidth RB and a priority p. A link has three types of bandwidth information: available bandwidth at each of several priority levels, AB[p]; maximum bandwidth for a route, MB; and total reservable bandwidth, TB. A link satisfies the bandwidth constraint iff both its available bandwidth at priority p (AB[p]) and the maximum bandwidth are at least as much as the specified bandwidth. If the final computed path includes this link, preemption will be required if RB > LB[q] for some priority q lower than p. L.AB[p] is initially the reservable bandwidth of link L; this value changes as reservations are made and withdrawn. Attribute: none Acceptor: if RB <= L.AB[p] && RB <= L.MB then ACC else REJ Kompella/Awduche [Page 6] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 4.1.3. Delay Bounds A route can specify the maximum delay Dmax it can tolerate. A link L is acceptable for this route if the accumulated delay at the start node for the link (S(L).ND) plus the link delay (L.D) plus is at most D. L.D is either configured or derived from the link characteristics of link L. Attribute: ND Initial value: 0 Accumulator: E(L).NDcand = S(L).ND + L.D Acceptor: if E(L).NDcand <= Dmax then ACC else REJ 4.1.4. Hop Count A route can specify that it can have at most HCmax hops. Attribute: HC Initial value: 0 Accumulator: E(L).HCcand = S(L).HC + 1 Acceptor: if E(L).HCcand <= HCmax then ACC else REJ 4.2. Quantitative Constraints and their Resources Quantitative constraints include residual bandwidth ratio, path metric, 'resilience' (see below) and hop count. The resources corresponding to quantitative constraints are: residual bandwidth, metric, penalty and path length. Each route specifies the list of qualitative constraints that should be enforced, and in what order (see section 3). 4.2.1. Path Metric Path metric (distance) is just the sum of the metrics on all the links in a path. Each node tracks the current shortest distance to it in the attribute PM; each link has a resource M which is the link's configured metric. Attribute: PM Kompella/Awduche [Page 7] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 Initial value: 0 Accumulator: PMcand = S(L).PM + L.M Comparator(PMcand, PM): if (PMcand == PM) then CONT else if (PMcand < PM) then ACC else REJ 4.2.2. Residual Bandwidth Ratio As we saw in the description of Available Bandwidth, a route can specify a required bandwidth RB and a priority p. The residual bandwidth of a link L is the available bandwidth of L at priority p if the route were to go through L, i.e., L.AB[p] - RB. The residual bandwidth ratio is a measure of the "fullness" of a link, given by the ratio of the residual bandwidth to the total reservable bandwidth on a link: (L.AB[p] - RB)/L.TB. Each node has an attribute that is an array of k RBRs, sorted from smallest to largest, where k is the number of elements in the array. Thus, for each path, the k smallest RBRs are tracked. Attribute: a sorted array AR of k RBRs, smallest to largest. We suggest that k, the number of elements in the array, be at least 4. Initial value: AR[i] = 1.0, 0 <= i < k. Accumulator: E(L).ARcand = S(L).AR + L.RBR, where AR + RBR is a new array with RBR inserted into AR in sorted order, keeping only k elements. Comparator(ARcand, AR): Let i be the smallest index such that ARcand[i] != AR[i]. If ARcand and AR are identical, set i = k. if i == k, then CONT else if ARcand[i] < AR[i] then ACC else REJ. 4.2.3. Resilience As mentioned earlier, the purpose of a constrained route is to specify the path over which some class of traffic is carried. Many implementations allow the specification of multiple paths for a given traffic class: a primary path and zero or more backup paths. The idea is to provide some degree of resilience: if the current operational path fails for any reason, traffic can be switched to a backup path. Kompella/Awduche [Page 8] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 The usual reason for path failure is that some network element (node or link) that it is using fails. That being the case, it is preferable that backup paths do not have network elements in common with the primary path. This constraint attempts to accomplish this. Note that this constraint only applies to backup path computation. Since the primary is the preferred path, it is not subject to this constraint; any previously set up backup path that shares a network element with the primary should be torn down and recomputed: i.e., the primary path should have a free run (subject to its own constraints), and the backup paths adjust themselves to stay away from the primary. The notion of Shared Risk Link Group (SRLG) takes this one step further: it identifies links that are disjoint from a layer 2 perspective, but share a common risk (e.g., they may be in the same fiber bundle). In a later version, we will describe how SRLG can be taken into account when computing backup paths. 5. Path Selection It is well-known that the shortest path problem with two or more independent metrics is NP-complete [NPC]. Now, path computation has multiple metrics, namely, each quantitative constraint. To make path computation tractable, we enforce an order among the quantitative constraints. Ideally, this order should be configurable by the network administrator. As a default ordering of the constraints, we suggest: path metric, resilience, residual bandwidth ratio and hop count, in that order. 5.1. Link Acceptance Suppose we are given a route R with an ordering of its quantitative constraints, and a loose hop for which we are trying to compute a path. Suppose further that we have a best path from the starting point to some node N. We attempt to extend this path to a best path to each neighbor of N as follows. Let L be a link from N to a node M. For each attribute of N, apply the appropriate accumulator function on the pair (N, L) to obtain candidate attribute values for M. For each Boolean constraint for R, apply the appropriate acceptor function on the candidate attribute and constraint. If the output is REJ, the link L is unacceptable for R. That is, all acceptor Kompella/Awduche [Page 9] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 functions must return ACC for a link to be acceptable for a route. 5.2. Path Selection Continuing the scenario in the previous section, suppose that a link L is deemed acceptable. For each quantitative constraint, in order, the corresponding comparator function is applied on the candidate and current attribute of M: If the result is ACC, we have a new best path to node M. If the result is REJ, the old best path to M is better. If the result is CONT, the two paths are tied on this constraint: go on to the next constraint. If we have a new best path to node M, all of M's attributes are changed to the candidate values computed by the accumulator functions. 6. Optimization This will be described in a future revision. 7. References [IP] Postel, J., "Internet Protocol", RFC 791, September 1981. [TE-REQ] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. McManus, "Requirements for Traffic Engineering Over MPLS", RFC 2702, September 1999. [ISIS-TE] Smit, H., Li, T., "IS-IS extensions for Traffic Engineering", draft-ietf-isis-traffic-01.txt (work in progress) [OSPF-TE] Katz, D., Yeung, D., "Traffic Engineering Extensions to OSPF", draft-katz-yeung-ospf-traffic-01.txt (work in progress) Kompella/Awduche [Page 10] Internet Draft draft-kompella-te-pathcomp-00.txt July 2000 8. Security Considerations Security considerations are not discussed in this memo. 9. Authors' Addresses: Daniel O. Awduche UUNET (MCI Worldcom) 22001 Loudoun County Parkway Ashburn, VA 20147 Phone: 703-886-5277 Email: awduche@uu.net Kireeti Kompella Juniper Networks, Inc. 1194 N. Mathilda Ave Sunnyvale, CA 94089 Email: kireeti@juniper.net Kompella/Awduche [Page 11]