Network Working Group K. Kompella Internet Draft Juniper Networks Category: Standards Track June 2003 Expires: December 2003 Carrying Constraints in RSVP draft-kompella-mpls-rsvp-constraints-01.txt 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. Copyright Notice Copyright (C) The Internet Society (2003). All Rights Reserved. Kompella Standards Track [Page 1] Internet Draft Carrying Constraints in RSVP June 2003 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. Conventions used in this document 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 [KEYWORDS]. 1. 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. 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. Kompella Standards Track [Page 2] Internet Draft Carrying Constraints in RSVP June 2003 1.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]. 1.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 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. 1.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. Kompella Standards Track [Page 3] Internet Draft Carrying Constraints in RSVP June 2003 2. 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. 3. 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. 3.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 Kompella Standards Track [Page 4] Internet Draft Carrying Constraints in RSVP June 2003 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. 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. 3.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 Kompella Standards Track [Page 5] Internet Draft Carrying Constraints in RSVP June 2003 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. 3.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. 3.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). Kompella Standards Track [Page 6] Internet Draft Carrying Constraints in RSVP June 2003 3.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. 3.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 5 uint Link Mux Capability 6 uint Link Protection Type 7 uint Link Delay 8 set Link SRLG others -- Reserved 3.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 Kompella Standards Track [Page 7] Internet Draft Carrying Constraints in RSVP June 2003 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 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. Kompella Standards Track [Page 8] Internet Draft Carrying Constraints in RSVP June 2003 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'. 3.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). 4. Examples Some simple examples of constraint programs follow. 4.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 - - - Kompella Standards Track [Page 9] Internet Draft Carrying Constraints in RSVP June 2003 4.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) 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 - - - Normative References [KEYWORDS] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997 [MULTI-AREA] Kompella, K., and Rekhter, Y., "Multi-area MPLS Traffic Engineering", (work in progress) [OSPF-TE] Katz, D., Yeung, D., and Kompella, K., "Traffic Engineering Extensions to OSPF", (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", RFC 3209, December 2001 Kompella Standards Track [Page 10] Internet Draft Carrying Constraints in RSVP June 2003 Informative References [ISIS-TE] Smit, H., and Li, T., "IS-IS Extensions for Traffic Engineering", (work in progress) 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 RSVP 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. 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. Authors' Addresses Kireeti Kompella Juniper Networks, Inc. 1194 N. Mathilda Ave, Sunnyvale, CA 94089 email: kireeti@juniper.net IPR Notice The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can Kompella Standards Track [Page 11] Internet Draft Carrying Constraints in RSVP June 2003 be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. Full Copyright Notice Copyright (C) The Internet Society (2003). 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." Kompella Standards Track [Page 12] Internet Draft Carrying Constraints in RSVP June 2003 Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society. Kompella Standards Track [Page 13]