Internet Draft
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]