One document matched: draft-kompella-mpls-rsvp-constraints-01.txt
Differences from draft-kompella-mpls-rsvp-constraints-00.txt
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]
| PAFTECH AB 2003-2026 | 2026-04-21 03:25:22 |