Network Working Group Kireeti Kompella Internet Draft Juniper Networks Expiration Date: August 2001 February 2001 Carrying Constraints in RSVP draft-kompella-mpls-rsvp-constraints-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 RFC2026 except that the right to produce derivative works is not granted. 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. 2. Abstract Constraint-based routing is the computation of a path through a network that satisfies some constraints. Typically, some device A obtains the constraints (perhaps through configuration), and also knows the network topology and resources, and thereby computes the path. However, in certain cases, the device A that knows the constraints cannot compute the full path. In such cases, it is useful for A to be able to communicate the constraints to some other device B that can carry out or complete the computation, and moreover, to communicate these constraints in an extensible, interoperable fashion, and such that A's semantics are understood by B. This document suggests one such means of constraint communication: use a signalling mechanism (such as RSVP) for carrying the constraints, and carry the constraints as a program. Kompella, Kireeti [Page 1] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 3. Carrying Constraints in RSVP There are several cases where it is useful to carry a Label-Switched Path's (LSP) constraints in RSVP/TE, specifically, in the Path message used to set up that LSP [RSVP-TE]. However, the problem is that the head-end Label Switching Router (LSR) for the LSP, where the LSP's constraints are configured, may have different notions of constraint semantics from the transit LSRs. The solution is to define an extensible, interoperable means for the head-end LSR communicate its semantics to the other LSRs. The approach taken in this paper is to define constraint semantics by means of a program. Note that this method can be trivially adapted for use with CR-LDP. The following subsections contain some example scenarios where this feature may be useful. Futhermore, the application of an expressive constraint programming language need not be limited to carrying constraints from LSR to LSR; one can easily visualize offering a versatile (higher level) language for constraint specification of LSPs, and a "compiler" that translates these specifications to the constraint language given below. 3.1. Multi-area Constrained Routes Currently, path computation of LSP paths is limited to an IGP area, because the relevant information for computing paths is only available in that area. One approach for computing LSPs across multiple IGP areas is to have the head-end of the LSP compute a constrained route to an area-border Label Switching Router (ABLSR), then signal to that ABLSR, and include the LSP's constraints as part of the signalling. The ABLSR can then compute a constrained route across its area to another ABLSR, and so on until the tail-end of the LSP is reached. There are several open issues with this approach, but nevertheless, it seems a viable and scalable way of dealing with inter-area constraint-based routing. Several scenarios for doing multi-area path computation are given in [MULTI-AREA]. 3.2. Proxy Path Computation A head-end LSR may for several reasons decide to delegate path computation to one or more path computation servers (e.g., an ABLSR) by sending the information about an LSP (including constraints) and tell the servers to compute the path. The reasons for such "proxy path computation" may be that the head-end does not have adequate Kompella, Kireeti [Page 2] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 computational resources; the head-end does not have enough information (for example, this approach can be used for multi-area path computation; in this case, the path computation server would have to have knowledge about multiple areas); the head-end does not know how to evaluate and apply certain constraints (for example, optical constraints in path computation of optical trails). The mechanisms by which the head-end LSR communicates to the path computation server, and by which the results are returned are outside the scope of this document; however, a variant of the mechanism described here can be used to communicate the constraints. Note that the proxy path servers can in turn send the path computation request (or portions of it) to other path computation servers. When the path is computed, the servers return results to the head-end, which then can compare all returned paths and create an ERO with the best path. 3.3. Admission Control Finally, an LSR can apply the constraints as part of its admission control. This is of limited value, as most constraints (apart from bandwidth) change rarely, but may be useful in some contexts. 4. Constraint Semantics In the context of Constraint-based Routing, a constraint is a restriction on path selection. Constraints can be Boolean or quantitative. Boolean constraints present a pass/fail criterion to paths. Quantitative constraints assign numerical preferences to paths; a path that minimizes (or maximizes, depending on the constraint) the preference value is chosen above the rest. The constraints defined for Constraint-based Routing for MPLS LSPs include bandwidth, administrative groups (or colors) [ISIS-TE, OSPF- TE], and hop count. Others under consideration include delay. In GMPLS, Link Descriptor and Link Multiplex Capability as well as optical performance parameters can also constrain path selection. Note that currently, all constraints apply to link properties; in general, there may also be constraints that apply to nodes in the path. Note too that RSVP/TE signalling already carries the bandwidth, and a basic version of administrative group constraints. Kompella, Kireeti [Page 3] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 5. Constraint Object This object is an optional subobject of the Path Message. It has a Class-num of [TBD] and a C-Type of [TBD]. A node that receives a constraint object MUST pass it to the next node, even if it doesn't understand the object. How constraint objects are used depends on the next hop in the ERO. If the LSR receiving the constraint object is the tail-end of the LSP, the constraint object is ignored. If the next hop is strict, the constraint object MAY be applied to the link specified by the next hop as an extended admission control; if the link fails, the LSR MAY reject the LSP setup and send a PathErr back to the head-end LSR indicating an error. If the next hop is loose, the node SHOULD perform a Constrained Path Computation using the constraints specified by the constraint object. 5.1. Object Description A Constraint object includes an optional Endpoint subobject, an optional Initial Path Preference Values subobject, an optional Initial Path Attributes subobject, zero or more Set Value subobjects, and a Program subobject. The Endpoint subobject specifies the start and destination nodes for constraint-based routing. If this subobject is absent, the start node for computation is the LSR doing the computation (say C) and the destination node is derived from the next node X in the ERO as follows. If C has TE information about X (e.g., C and X are in the same TE domain (link state area)), then X is the destination node. Otherwise, C must determine (using means outside the scope of this document) an intermediate LSR I towards X; I is then the destination node. Note that there may be multiple choices for the intermediate LSR; it is outside the scope of this document how LSR C determines in what order the choices are tried, and how and when to choose another intermediate LSR. If the Initial Path Preference Values subobject is present, it defines the path preference values for the initial null path (see below). Otherwise, the path preference values for the initial path are set to 0. If the Initial Path Attributes subobject is present, it defines the path attribute values for the initial null path. Otherwise, the path attributes for the initial path are set to 0. Kompella, Kireeti [Page 4] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 A Set Value subobject consists of an index value between 1 and 255 by which the set is referred to, and a set of 32-bit integers. By "set", we mean an ordered set with no repeated elements. Zero or more Set Value subobjects may be present; each MUST have a unique index value. One use of a Set Value object is to communicate SRLG values. A Program subobject specifies a program, that is, a series of instructions. 5.2. Operation It is assumed that each LSR has some algorithm to compute constraint based routes from start node S to destination node D, and that this algorithm initially has a null path from S, and at each stage extends an existing path by one link until it finds one or more feasible paths to D. If none are found, the algorithm fails; if more than one path are found, the algorithm must pick one. It is also assumed that each path has a set preference values and a set of attributes. The initial null path gets its preference values and attributes from the Initial Path Preference Values and Attributes objects, if any; otherwise, the values are set to 0. In the inductive step above, the algorithm takes a path P from S to some node M and a link L from M to N, and attempts to build from P and L a new path P' from S to N; in doing so, it must determine whether P' is feasible (i.e., whether it meets the constraints), and it must also determine the preference values and path attributes for P' from those of P and from the link properties of L. Herein lies the purpose of the constraint program: to determine whether constraints are met, and to determine new values for the preference values and path attributes. The constraint program implicitly also provides a means of choosing among multiple feasible paths. At the point that the algorithm chooses the path P and link L, the following is done. The P's preference values and path attributes are loaded into their respective sets of registers; also, node M and link L's TE properties are loaded into their set of registers. Then the constraint program is run. The constraint program has three outputs: first, whether path P' is feasible; second, the preference values for P'; and third, the path attribute values for P'. Note that the same constraint program is run for every candidate link. The difference is the initial values loaded into the various registers. Kompella, Kireeti [Page 5] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 5.3. Registers There are 16 banks of 256 registers each. Bank 0 consists of general purpose registers, used for computing and storing intermediate values. Bank 1 consists of Path Preference Values. Bank 2 consists of Path Attributes. Bank 15 consists of TE Property registers. The other banks will be defined in a later version. 5.3.1. Path Preference Values Each path is associated with an indexed set of preference values. Smaller preference values are better. Path P to a node is preferred over path Q to that node if there is a k >= 0 such that P and Q have identical preference values for all indices < k, and the k'th preference value of P is less than that of Q. Path preference values do not have a pre-assigned meaning; the semantics are assigned by the constraint program. Before the constraint program is run, Bank 1 registers are initialized with the preference values of path P (as defined in the Operation section). 5.3.2. Path Attributes Each path is also associated with a set of attribute values. Before the constraint program is run, Bank 2 registers are initialized with the path attributes of path P (as defined in the Operation section). Path attribute values do not have a pre-assigned meaning; the semantics are assigned by the constraint program. 5.3.3. TE Properties Registers These registers are read-only. If a link L from node M is being considered as a candidate for the path, the attributes of link L and node M are loaded into the TE Properties Registers. Let the priority of the constraint-based path being computed be p. Register Type TE Property Name 0 uint Link TE Metric 1 vec Link Administrative Groups 2 flt Link Unreserved Bandwidth (at priority p) 3 flt Link Maximum LSP Bandwidth (at priority p) 3 flt Link Reservable Bandwidth Kompella, Kireeti [Page 6] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 5 uint Link Mux Capability 6 uint Link Protection Type 7 uint Link Delay 8 set Link SRLG others -- Reserved 5.4. Instructions A Program object is a sequence of instructions of the following format (other instruction formats will be added as needed): 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | OpCode | Bank | Register y | Register x | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Immediate Operand (Optional) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The following list defines the valid OpCodes, their semantics, and types for this format. & denotes bit-wise AND, | bit-wise OR, ^ bit- wise XOR, and ~ bit-wise inversion (unary operation). && denotes Boolean AND, || denotes Boolean OR, ^^ denotes Boolean XOR, and ! denotes Boolean negation (unary operation). x {} y is the intersection operator; x and y must be sets, and the result is the set of common elements. x # y refers to the union operation; x and y must be sets, and the result is the ordered union of x and y, with no repetitions. If x is a set, x == 0 (x != 0) means x is empty (non- empty, respectively). Arithmetic operations are either integer or floating point. Operand types include bit vector (bit), signed and unsigned integer (int/uint), floating point (flt) and set. If the type can be any of signed or unsigned integer or floating point, the type is denoted as "arith". OpCode Semantics x's type y's type Result type 0 No-op - - - 1 x <- y - any same as y 2 y <- x - any same as x 3 x <- x + y arith same as x same as x 4 x <- x - y arith same as x same as x 5 x <- x * y arith same as x same as x 6 x <- x / y arith same as x same as x 7 x <- x % y int same as x same as x 8 x <- min(x, y) arith same as x same as x 9 x <- max(x, y) arith same as x same as x Kompella, Kireeti [Page 7] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 10 x <- y == 0 - arith/set Boolean 11 x <- y != 0 - arith/set Boolean 12 x <- y >= 0 - arith Boolean 13 x <- y > 0 - arith Boolean 14 x <- x == y arith same as x Boolean 15 x <- x != y arith same as x Boolean 16 x <- x >= y arith same as x Boolean 17 x <- x > y arith same as x Boolean 18 x <- x && y Boolean Boolean Boolean 19 x <- x || y Boolean Boolean Boolean 20 x <- x ^^ y Boolean Boolean Boolean 21 x <- !y - Boolean Boolean 22 x <- x & y bit bit bit 23 x <- x | y bit bit bit 24 x <- x ^ y bit bit bit 25 x <- ~y - bit bit 26 x <- x {} y set set set 27 x <- x # y set set set 28 Check - Boolean - 29 End - - - Register x is always from bank 0. Register y is from the bank denoted by "Bank". If Register y is 255 from bank 0, the actual value is taken from the following word (Immediate Operand). The instruction Check works as follows: if the value of register y is False, the program ends: the link L under consideration does not meet the constraints. Otherwise, the program continues as usual. The instruction End ends the program. At this point, the preference values in Bank 1 are assigned to path P'; also, the path attribute values in Bank 2 are assigned to path P'. 5.4.1. Design Note At present, the instruction set does not include branches, loops or conditional statements. If needed, these can be added; however, note that the addition of backward branches or loops introduces the possibility that the constraint program can take a long time to execute, or indeed, loop forever. Thus, the design goal here is to add these features only if absolutely needed; and if at all possible, loops should be bounded (i.e., loop N times, where N is a compile- time constant). Kompella, Kireeti [Page 8] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 6. Examples Some simple examples of constraint programs follow. 6.1. Include/exclude One semantic for administrative groups is as follows. An LSP is configured with an "include" set (represented as a bit vector inc) and an "exclude" set (represented as a bit vector exc). A link with administrative groups ag is acceptable if it has at least one administrative group from the "include" set inc, and none of the administrative groups from the "exclude" set exc. That is: ((ag & inc) != 0) && ((ag & exc) == 0) Here is a constraint program to encode the above. # Instr x y Bank Comment 1 1 0 1 15 x <- Link Administrative Groups (ag) 2 22 0 255 0 x <- (ag & inc) immediate operand: inc 3 11 0 0 0 x <- ((ag & inc) != 0) 4 1 1 1 15 x' <- Link Administrative Groups (ag) 5 22 0 255 0 x' <- (ag & exc) immediate operand: exc 6 10 1 1 0 x' <- ((ag & exc) == 0) 7 18 0 1 0 x <- (x && x') 8 28 - 0 0 Fail if x is not True 9 29 - - - 6.2. Affinities and Mask Another semantic for using administrative groups is as follows. An LSP has an "affinity" and a "mask", both of which are 32-bit vectors. A link with administrative groups ag is acceptable for the LSP if for the subset of administrative groups in the mask, the link's administrative groups and the affinity match exactly. In other words: ((ag ^ affinity) & mask) == 0 Here is a constraint program to encode the above. # Instr x y Bank Comment 1 1 0 1 15 x <- Link Administrative Groups (ag) 2 24 0 255 0 x <- (ag ^ affinity) Kompella, Kireeti [Page 9] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 immediate operand: affinity 3 22 0 255 0 x <- (ag ^ affinity) & mask immediate operand: mask 4 10 1 0 0 x <- ((ag ^ affinity) & mask) == 0 5 28 - 1 0 Fail if above is non-zero 6 29 - - - 7. Security Considerations Compromising constraint objects requires tampering with RSVP Path Messages. The result of such tampering affects LSP setup. Such tampering can be mitigated by authenticating the Path Messages. Furthermore, as noted above in the "Design Note", the introduction of loops and backward branches means that constraint programs can run for a long time (or forever), opening new avenues for denial-of- service attacks. 8. Acknowledgements Many thanks to Yakov Rekhter, who pointed me at this problem, and offered many helpful comments. Thanks too to Robert Raszuk for his review and comments. 9. References [ISIS-TE] Smit, H., Li, T., "IS-IS Extensions for Traffic Engineering", draft-ietf-isis-traffic-02.txt (work in progress) [MULTI-AREA] Kompella, K., and Rekhter, Y., "Multi-area MPLS Traffic Engineering", draft-kompella-mpls-multiarea-te-00.txt (work in progress) [OSPF-TE] Katz, D., Yeung, D., Kompella, K., "Traffic Engineering Extensions to OSPF", draft-katz-yeung-ospf-traffic-03.txt (work in progress) [RSVP-TE] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., and Swallow, G., "RSVP-TE: Extensions to RSVP for LSP Tunnels", draft-ietf-mpls-rsvp-lsp-tunnel-07.txt (work in progress) Kompella, Kireeti [Page 10] Internet Draft draft-kompella-mpls-rsvp-constraints-00.txt February 2001 10. Intellectual Property Considerations Juniper Networks may seek patent or other intellectual property protection for some of all of the technologies disclosed in this document. If any standards arising from this document are or become protected by one or more patents assigned to Juniper Networks, Juniper intends to disclose those patents and license them on reasonable and non-discriminatory terms. 11. Full Copyright Statement Copyright (C) The Internet Society (2001). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 12. Author Information Kireeti Kompella Juniper Networks, Inc. 1194 N. Mathilda Ave, Sunnyvale, CA 94089 email: kireeti@juniper.net Kompella, Kireeti [Page 11]