Internet Engineering Task Force R. Guerin/A. Orda/D. Williams
INTERNET DRAFT IBM/Technion/IBM
5 November 1996
QoS Routing Mechanisms and OSPF Extensions
draft-guerin-qos-routing-ospf-00.txt
Status of This Memo
This document is an Internet-Draft. 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 not appropriate to use Internet Drafts as
reference material, or to cite them other than as a ``working draft''
or ``work in progress.''
To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the internet-drafts
Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net
(Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific
Rim).
Abstract
This memo describes extensions to the OSPF protocol to support QoS
routes. The focus of the document is on the algorithms used to
compute QoS routes and on the necessary modifications to OSPF to
support this function, e.g., the information needed, its format,
how it is distributed, and how it is used by the QoS path selection
process. Aspects related to how QoS routes are established and
managed are also briefly discussed, but the development of detailed
specifications is left for further study. The goal of this
document is to identify a framework and possible approaches to allow
deployment of QoS routing capabilities with the minimum possible
impact to the existing routing infrastructure.
Guerin,Orda,Williams Expires 10 May 1997 [Page i]
Internet Draft QoS Routing Mechanisms 5 November 1996
Contents
Status of This Memo i
Abstract i
1. Introduction 1
1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 1
1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 2
2. Path Selection Information and Algorithms 3
2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2. Advertisement of Link State Information . . . . . . . . . 5
2.3. Path Selection Algorithms . . . . . . . . . . . . . . . . 6
2.3.1. Algorithm for exact pre-computed QoS paths . . . 7
2.3.2. Algorithm for on-demand computation of QoS paths 10
2.3.3. Algorithm for approximate pre-computed QoS paths 11
3. Establishment and Maintenance of QoS Routes 14
4. OSPF Protocol Enhancements 15
4.1. QoS -- Optional Capabilities . . . . . . . . . . . . . . 15
4.2. Packet Formats . . . . . . . . . . . . . . . . . . . . . 16
4.2.1. Router Links Advertisements . . . . . . . . . . . 16
4.2.2. Summary Link Advertisement . . . . . . . . . . . 17
4.3. Calculating the inter-area routes . . . . . . . . . . . . 18
4.4. Open Issues . . . . . . . . . . . . . . . . . . . . . . . 18
A. Construction of Path Information 19
A.1. Source routed paths . . . . . . . . . . . . . . . . . . . 19
A.2. Hop-by-Hop Routing . . . . . . . . . . . . . . . . . . . 21
B. Computational Complexity 21
C. Extension: Handling Propagation Delays 22
D. Zero-Hop Edges 23
E. Sample Path Establishment Scenario 24
F. Pseudocode for BF Algorithm 26
Guerin,Orda,Williams Expires 10 May 1997 [Page ii]
Internet Draft QoS Routing Mechanisms 5 November 1996
1. Introduction
In this document we describe a set of proposed additions to the
OSPF routing protocol (the additions are built on top of OSPF V2)
to support Quality-of-Service (QoS) routing in IP. In particular we
discuss the metrics required to support QoS, the associated link
advertisement mechanisms, the path selection algorithm, as well
as aspects of route establishment (pinning and unpinning). Our
goals are to define an approach which while achieving the goals of
improving performance for QoS flows (likelihood to be routed on a
path capable of providing the requested QoS), does so with the least
possible impact on the existing OSPF protocol. Given the inherent
complexity of QoS routing, achieving this goal obviously implies
trading-off ``optimality'' for ``simplicity'', but we believe this
to be required in order to facilitate deployment of QoS routing
capabilities.
1.1. Overall Framework
We consider a network (1) that supports both best-effort packets
and packets with QoS guarantees. The way in which the network
resources are split between the two classes is irrelevant to our
proposal, except for the assumption that each QoS capable router in
the network is able to dedicate some of its resources to satisfy the
requirements of QoS packets. QoS capable routers are also assumed
able to identify and advertise the amount of their resources that
remain available for additional QoS flows. In addition, we limit
ourselves to the case where all the routers involved support the QoS
extensions described in this document, i.e., we do not consider the
problem of establishing a route in an heterogeneous environment with
routers that are QoS-capable and others that are not. Furthermore,
in this document we focus on the case of unicast flows, although many
of the additions we define are applicable to multicast flows as well.
We assume that a flow with QoS requirements will specify them
in some fashion that is accessible to the routing protocol. For
example, this could correspond to the arrival of an RSVP [RZB+96]
PATH message, whose TSpec is passed to routing together with the
destination address. After processing such a request, the routing
protocol returns a path that it deems the most suitable given the
flow's requirements. Depending on the scope of the path selection
----------------------------
1. In this document we commit the abuse of notation of calling a
``network'' the interconnection of routers and networks through which
we attempt to acompute a QoS path.
Guerin,Orda,Williams Expires 10 May 1997 [Page 1]
Internet Draft QoS Routing Mechanisms 5 November 1996
process, this returned path could range from simply identifying the
best next hop, i.e., a traditional hop-by-hop routing, to specifying
all intermediate nodes to the destination, i.e., a source route.
Note that this decision impacts the operation of the path selection
algorithm as it translates into different requirements in order to
construct and return the appropriate path information. Note also
that extension to multicast paths will impact differently a source
routed and a hop-by-hop approach.
Once a suitable path has been identified, the flow is assigned to
it (pinning) and remains assigned to it until it either releases
the path (unpinning) or deems that it has become unsuitable, e.g.,
because of link failure or unavailability of the necessary resources.
Note that resources reservation and/or accounting should help limit
the frequency of the latter.
In this document, we focus on the aspect of selecting an appropriate
path based on information on link metrics and flow requirements.
There are obviously many other aspects that need to be specified in
order to define a complete proposal for QoS routing. Issues such as
those mentioned above on the scope of the path selection process and
when/how paths are pinned and unpinned, must certainly be addressed
and they are briefly discussed in this draft during the exposition of
the path selection algorithms and then more specifically in Section
3. The discussion of a complete solution to these problems is,
however, deferred to [GOW96].
1.2. Simplifying Assumptions
In order to achieve our goal of a minimum impact to the existing
protocol, we impose certain restrictions on the range of requirements
the QoS path selection algorithm needs to deal with directly.
Specifically, a policy scheme is used to a priori prune from
the network, those portions that would be unsuitable given the
requirements of the flow. This limits the ``optimization'' performed
by the path selection to a containable set of parameters, which helps
keep complexity at an acceptable level. Specifically, the path
selection algorithm will focus on selecting a path that is capable of
satisfying the bandwidth requirement of the flow, while at the same
time trying to minimize the amount of network resources that need to
be allocated to support the flow, i.e., minimize the number of hops
used.
This focus on bandwidth is adequate in most instances, but does not
fully capture the complete range of potential QoS requirements. For
example, a delay-sensitive flow of an interactive application could
be put on a path using a satellite link, if that link provided a
Guerin,Orda,Williams Expires 10 May 1997 [Page 2]
Internet Draft QoS Routing Mechanisms 5 November 1996
direct path and had plenty of unused bandwidth. This would clearly
not be a desirable choice. Our approach to preventing such poor
choices, is to assign delay-sensitive flows to a policy that would
eliminate from the network all links with high propagation delay,
e.g., satellite links, before invoking the path selection algorithm.
In general, each existing policy would present to the path selection
algorithm its correspondingly pruned network topology, and the same
algorithm would then be used to generate an appropriate path.
Another important aspect in minimizing the impact of QoS routing
is to develop a solution that has the smallest possible computing
overhead. Additional computations are unavoidable, but it is
desirable to keep the total cost of QoS routing at a level comparable
to that of traditional routing algorithms. In this document, we
describe several alternatives to the path selection algorithm,
that represent different trade-offs between simplicity, accuracy,
and computational cost. In particular, we specify algorithms
that generate exact solutions based either on pre-computations or
on-demand computations. We also describe algorithms that allow
pre-computations at the cost of some loss in accuracy, but with
possibly lower complexity or greater ease of implementation. It
should be mentioned, that while several alternative algorithms are
described in this document, the same algorithm needs to be used
consistently within a given routing domain. This requirement can be
relaxed when a source routed approach is used as the responsibility
of selecting a QoS path lies with a single entity, the origin of
the request, which ensures consistency. Hence, it may then be
possible for each router to use a different path selection algorithm.
However, in general, the use of a common path selection algorithm is
recommended, if not necessary, for proper operation.
The rest of this document is structured as follows. In Section 2,
we describe the path computation process and the information that it
relies on. In Section 3 we briefly review some issues associated
with path management and their implications. As mentioned earlier,
detailed discussions on these topics is deferred to [GOW96]. In
Section 4, we go over the extensions to OSPF that are needed in order
to support the path selection process of Section 2. Finally, several
appendices provide details on the different path selection algorithms
described in Section 2, and outline several additional work items.
2. Path Selection Information and Algorithms
This section describes several path selection algorithms that
can be used to generate QoS capable routes based on different
trade-offs between accuracy, computational complexity, and ease of
implementation. In addition, the section also covers aspects related
Guerin,Orda,Williams Expires 10 May 1997 [Page 3]
Internet Draft QoS Routing Mechanisms 5 November 1996
to the type of information, i.e., metrics, on which the algorithms
operate, and how that information is made available, i.e., link state
advertisements. The discussion on these topics is of a generic
nature, and OSPF specific details are provided in Section 4.
2.1. Metrics
As stated earlier, the process of selecting a path that can satisfy
the QoS requirements of a new flow relies on both the knowledge of
the flow's requirements and characteristics, and information about
the availability of resources in the network. In addition, for
purposes of efficiency, it is also important for the algorithm to
account for the amount of resources the network has to allocate in
order to support a new flow. In general, the network prefers to
select the ``cheapest'' among all paths suitable for a new flow.
Furthermore, the network may also decide not to accept a new flow
for which it identified a feasible path, if it deems the cost of the
path to be too high. Accounting for these aspects involves several
metrics on which the path selection process is based. They include:
- Link available bandwidth: As mentioned earlier, we assume that
most QoS requirements are derivable from a rate-related quantity,
termed ``bandwidth''. We further assume that associated with
each link is a maximal bandwidth value, e.g., the link physical
bandwidth or some fraction thereof that has been set aside for
QoS flows. Since for a link to be capable of accepting a new
flow with given bandwidth requirements, at least that much
bandwidth must be still available on the link, the relevant link
metric is, therefore, the (current) amount of available (i.e.,
unallocated) bandwidth.
- Hop-count: This quantity is used as a measure of the path cost
to the network. A path with a smaller number of hops (that can
support a requested connection) is preferable, since it consumes
less network resources. While as a general rule each edge in the
graph on which the path is computed should be counted as one hop,
some edges, specifically those that connect a transit network to
a router, should not be taken into account. (See Appendix D for
a detailed explanation.)
- Policy: As previously discussed, policies are used to identify
the set of links in the network that need to be considered when
running the path selection algorithm. In particular, policies
are used to prune from the network links that are incompatible,
performance or characteristics wise, with the requirements of
a flow. A specific policy example of special importance, is
the elimination of high latency links when considering path
Guerin,Orda,Williams Expires 10 May 1997 [Page 4]
Internet Draft QoS Routing Mechanisms 5 November 1996
selection for delay sensitive flows. The use of policies to
handle specific requirements allows considerable simplification
in the optimization task to be performed by the path selection
algorithm.
2.2. Advertisement of Link State Information
It is assumed that each router maintains an updated database of the
network topology, including the current state (available bandwidth)
of each link. As described in Section 4, the distribution of link
state (metrics) information is based on extending OSPF mechanisms.
However, in addition to how link state information is distributed,
another important aspect is when such distribution is to take place.
Ideally, one would want routers to have the most current view
of the bandwidth available on all links in the network, so that
they can make the most accurate decision on which path to select.
Unfortunately, this then calls for very frequent updates, e.g.,
close to every time the available bandwidth of a link changes, which
is neither scalable nor practical. Alternatively, one may opt for
a simple mechanism based on periodic updates, where the period of
updates is determined based on a tolerable corresponding load on the
network and the routers. The main disadvantage of such an approach
is that major changes in the bandwidth available on a link could
remain unknown for a full period and, therefore, result in many
incorrect routing decisions.
As a result, we propose to use a simple hybrid update mechanism, that
attempts to reconcile accuracy of link state information with the
need for the smallest possible overhead. Periodic updates are used,
say every T seconds, to notify nodes of any change of more than ffi
in the available bandwidth of a link, and event-driven updates are
generated immediately whenever the change in available link bandwidth
since the last update exceeds . The values for T, ffi, and depend
on network size, link speed, processing capabilities, and overall
traffic patterns, but typical values would be: T 30sec, ffi 10%,
40%. Note that implicit in the above description is the the
fact that regardless of bandwidth changes, we also impose a minimum
interval between consecutive updates, e.g., we do not allow any
particular LSA to get updated more than once every MinLSInterval (5)
seconds, in order to prevent the possibility of overload.
Guerin,Orda,Williams Expires 10 May 1997 [Page 5]
Internet Draft QoS Routing Mechanisms 5 November 1996
2.3. Path Selection Algorithms
There are several aspects to the path selection algorithms. The
main ones include the optimization criteria it relies on, the exact
topology on which it is run, and when it is invoked.
As mentioned before, invocation of the path selection algorithm can
be either per flow, or when warranted by changes in link states when
the algorithm used allows precomputation of paths (more on this
below).
The topology on which the algorithm is run is, as with the standard
OSPF path selection, a directed graph where vertices (2) consist of
routers and networks (transit vertices) as well as stub networks
(non-transit vertices). When computing a path, stub networks are
added as a post-processing step, which is essentially similar to
what is done with the current OSPF routing protocol. In addition,
for each policy supported on a router, the topology used by the
path selection algorithm is correspondingly pruned to reflect the
constraints imposed by the policy, and in some instances the flow
requirements.
The optimization criteria used by the path selection are reflected
in the costs associated with each interface in the topology and how
those costs are accounted for in the algorithm itself. As mentioned
before, the cost of a path is a function of both its hop count and
the amount of available bandwidth. As a result, each interface
has associated with it a metric, that corresponds to the amount of
bandwidth which remains available on this interface. This metric
is combined with hop count information to provide a cost value,
in a manner that depends on the exact form of the path selection
algorithm. It will, therefore, be detailed in the corresponding
sections below, but all the different alternatives that are described
share a common goal. That is, they all aim at picking a path with
the minimum possible number of hops among those that can support
the requested bandwidth. When several such paths are available,
the preference is for the path whose available bandwidth (i.e., the
smallest value on any of the links in the path) is maximal. The
rationale for the above rule is the following: we focus on feasible
paths (as accounted by the available bandwidth metric) that consume
a minimal amount of network resources (as accounted by the hop-count
metric); and the rule for selecting among these paths aims at
balancing load as well as maximizing the likelihood that the required
bandwidth will indeed be available.
----------------------------
2. In this document, we use the terms node and vertex interchangeably.
Guerin,Orda,Williams Expires 10 May 1997 [Page 6]
Internet Draft QoS Routing Mechanisms 5 November 1996
It should be noted that standard routing algorithms are typically
single objective optimizations, i.e., they may minimize the
hop-count, or maximize the path bandwidth, but not both. Double
objective path optimization is a more complex task, and, in
general, it is an intractable problem [GJ79]. Nevertheless, as
we will see, because of the specific nature of the two objectives
being optimized (bandwidth and hop count), the complexity of our
proposed algorithm(s) is competitive with even that of standard
single-objective algorithms.
2.3.1. Algorithm for exact pre-computed QoS paths
In this section, we describe a path selection algorithm, that for a
given network topology and link metrics (available bandwidth) allows
us to pre-compute all possible QoS paths, and also has a reasonably
low computational complexity. Specifically, the algorithm allows
us to pre-compute for any destination a minimum hop count path with
maximum bandwidth, and has a computational complexity comparable to
that of a standard shortest path algorithm (3).
The path selection algorithm is based on a Bellman-Ford (BF)
shortest path algorithm, which is adapted to compute paths of maximum
available bandwidth for all hop counts. It is a property of the BF
algorithm that, at its h-th iteration, it identifies the optimal (in
our context: maximal bandwidth) path between the source and each
destination, among paths of at most h hops. In other words, the
cost of a path is a function of its available bandwidth, i.e., the
smallest available bandwidth on all links of the path, and finding
a minimum cost path amounts to finding a maximum bandwidth path.
However, we also take advantage of the fact that the BF algorithm
progresses by increasing hop count, to essentially get for free the
hop count of a path as a second optimization criteria.
Specifically, at the kth (hop count) iteration of the algorithm,
the maximum bandwidth available to all destinations on a path of
no more than k hops is recorded (together with the corresponding
routing information). After the algorithm terminates, this
information enables us to identify for all destinations and bandwidth
requirements, the path with the smallest possible number of hops and
sufficient bandwidth to accommodate the new request. Furthermore,
this path is also the one with the maximal available bandwidth among
all the feasible paths with this minimum number of hops. This is
----------------------------
3. See Appendix B for a more comprehensive discussion on the aspect of
computational complexity.
Guerin,Orda,Williams Expires 10 May 1997 [Page 7]
Internet Draft QoS Routing Mechanisms 5 November 1996
because for any hop count, the algorithm always selects the one with
maximum available bandwidth.
We now proceed with a more detailed description of the algorithm
and the data structure used to record routing information, i.e.,
the QoS routing table that gets built as the algorithm progresses
(pseudo-code for the algorithm can be found in Appendix F). As
mentioned before, the algorithm operates on a directed graph
consisting only of transit vertices (routers and networks), with
stub-networks subsequently added to the path(s) generated by the
algorithm. The metric associated with each edge in the graph is the
bandwidth available on the corresponding interface. Let us denote
by bn;mthe available bandwidth on the edge between vertices n and
m. The vertex corresponding to the router where the algorithm is
being run, i.e., the computing router, is denoted as the ``source
node'' for the purpose of path selection. The algorithm proceeds to
pre-compute paths from this source node to all possible destination
networks and for all possible bandwidth values. At each (hop count)
iteration, intermediate results are recorded in a QoS routing table,
which has the following structure:
The QoS routing table:
- a Kx H matrix, where K is the number of destinations (vertices
in the graph) and H is the maximal allowed (or possible) number
of hops for a path.
- The (n;h) entry is built during the hth iteration (hop count
value) of the algorithm, and consists of two fields:
* bw: the maximum available bandwidth, on a path of at most h
hops between the source node (router) and destination node
n;
* neighbor: this is the routing information associated with
the h (or less) hops path to destination node n, whose
available bandwidth is bw. The specific nature of this
information depends on the scope of the path being selected,
i.e., is it simply a next hop or is a complete source
route being specified. In both cases, this information is
constructed and recorded at each iteration of the algorithm,
but it is obtained and used differently.
+ When the scope of the path being selected is simply
the next hop, i.e., hop-by-hop path selection, the
neighbor information is simply the identity of the node
adjacent to the source node on that path. As a rule, the
``neighbor'' node must be a router and not a network (see
Guerin,Orda,Williams Expires 10 May 1997 [Page 8]
Internet Draft QoS Routing Mechanisms 5 November 1996
Appendix D), the only exception being the case that the
network is the destination node (and the selected path is
the single edge interconnecting the source to it).
+ When the path being selected is a complete source route,
the neighbor information is the previous router (4),
i.e., preceding the destination node n, on that path.
Next, we provide additional details on the operation of the algorithm
and how the entries in the routing table are being updated as the
algorithm proceeds. For simplicity, we first describe the simpler
case where all edges count as ``hops'', and later explain how
zero-hop edges (see Appendix D) are handled.
When the algorithm is invoked, the routing table is first initialized
with all bw fields set to 0 and neighbor fields cleared. Next, the
entries in the first column (which corresponds to one-hop paths) of
the neighbors of the computing router are modified in the following
way: the bw field is set to the value of the available bandwidth on
the direct edge from the source. Modification of the neighbor field
depends on the scope of path selection. For next-hop routing, it is
set to the identity of the neighbor of the computing router, i.e.,
the next router on the selected path. For source-routing, it is set
to the identity of the computing router itself.
Afterwards, the algorithm iterates for at most H iterations
(considering the above initial iteration as the first). H can be
either the maximum possible hop count of any path, i.e., an implicit
value, or it can be set explicitly in order to limit path lengths to
some maximum value (5) to better control worst case complexity.
At iteration h, we first copy column h - 1 into column h. In
addition, the algorithm keeps a list of nodes that changed their bw
value in the previous iteration, i.e., during the h- 1-st iteration.
The algorithm then looks at each link (n;m) and checks the maximal
available bandwidth on an h-hop path to node m whose final hop is
that link. This amounts to taking the minimum between the bw field
in entry (n;h -1) and the link metric value bn;m kept in the topology
database. If this value is higher than the present value of the bw
field in entry (m;h), then a better (larger bw value) path has been
found for destination m and with h hops. The bw field of entry
----------------------------
4. See Appendix A for details on how the complete source route is
constructed based on the neighbor information kept in the table.
5. This maximum value should be larger than the length of the minimum
hop-count path to any node in the graph.
Guerin,Orda,Williams Expires 10 May 1997 [Page 9]
Internet Draft QoS Routing Mechanisms 5 November 1996
(m;h) is then updated to reflect this new value. In the case of
next-hop routing, the neighbor field of entry (m;h) is set to the
same value as in entry (n;h - 1). This records the identity of the
first hop (next hop from the source) on the best path identified
thus far for destination m and with h (or less) hops. In the case
of source routing, the neighbor field of entry (m;h) is set to the
identity of node n. This records the identity of the previous hop
on the best path identified thus far for destination m and with h
(or less) hops. As described in Appendix A, this allows recursive
construction of the complete source route simply by back-tracking
from entry to entry in the table.
We conclude by describing how zero-hop edges are handled. At each
iteration h (starting with the first), whenever an entry (m;h) is
modified, it is checked whether there are zero-cost edges (m;k)
emerging from node m, which is the case when m is a transit network
(see Appendix D). In that case, we attempt to improve the entry of
node k that corresponds to the h-th hop, i.e., entry (k;h) (rather
than entry (k;h + 1)), since the edge (m;k) should not count as an
additional hop. As with the regular operation of the algorithm, this
amounts to taking the minimum between the bw field in entry (m;h)
and the link metric value bm;kkept in the topology database. If
this value is higher than the present value of the bw field in entry
(k;h), then the bw field of entry (k;h) is updated to this new value.
In the case of next-hop routing, the neighbor field of entry (k;h)
is set, as usual, to the same value as in entry (m;h) (which is also
the value in entry (n;h - 1)). In the case of source routing, the
neighbor field of entry (k;h) is set to the identity of node n. This
records the identity of the previous router on the identified path.
Note that while for simplicity of the exposition, the issue of equal
cost, i.e., same hop count and available bandwidth, is not detailed
in the above description, it is straightforward to add this support.
It only requires that the neighbor field be expanded to record the
list of next (previous) hops, when multiple equal cost paths are
present.
2.3.2. Algorithm for on-demand computation of QoS paths
In the previous section, we described an algorithm that allows
pre-computation of QoS routes. However, it may be feasible in
some instances, e.g., limited number of requests for QoS routes,
to instead perform such computations on-demand, i.e., upon receipt
of a request for a QoS route. The benefit of such an approach is
that depending on how often recomputation of pre-computed routes is
triggered, on-demand route computation can yield better routes by
using the most recent link metrics available. Another benefit of
Guerin,Orda,Williams Expires 10 May 1997 [Page 10]
Internet Draft QoS Routing Mechanisms 5 November 1996
on-demand path computation is the associated storage saving, i.e.,
there is no need for a QoS routing table. This is essentially the
standard trade-off between memory and processing cycles.
In this section, we briefly describe how a standard Dijkstra
algorithm can, for a given destination and bandwidth requirement,
generate a minimum hop path that can accommodate the required
bandwidth and also has maximum bandwidth. Because the Dijkstra
algorithm is already used in the current OSPF route computation, only
differences from the standard algorithm are described. Also, while
for simplicity we do not consider here zero-hop edges (see Appendix
D), the modification required for supporting them is straightforward.
The algorithm essentially performs a minimum hop path computation,
on a graph from which all edges, whose available bandwidth is less
than that requested by the flow triggering the computation, have been
removed. This can be performed either through a pre-processing step,
or while running the algorithm by checking the available bandwidth
value for any edge that is being considered. Another modification
to a standard Dijkstra based minimum hop count path computation, is
that the list of equal cost next (previous) hops which is maintained
as the algorithm proceeds, needs to be sorted according to available
bandwidth. This is to allow selection of the minimum hop path with
maximum available bandwidth. Alternatively, the algorithm could also
be modified to, at each step, only keep among equal hop count paths
the one with maximum available bandwidth. This would essentially
amount to considering a cost that is function of both hop count and
available bandwidth.
2.3.3. Algorithm for approximate pre-computed QoS paths
This section outlines a Dijkstra-based algorithm that allows
pre-computation of QoS routes for all destinations and bandwidth
values. The benefit of using a Dijkstra-based algorithm is a greater
synergy with existing OSPF implementations. The cost is, however, a
loss in the ``accuracy'' of the pre-computed paths, i.e., the paths
being generated may be of a larger hop count than needed. This
loss in accuracy comes from the need to rely on quantized bandwidth
values, that are used when computing a minimum hop count path. In
other words, the range of possible bandwidth values that can be
requested by a new flow is mapped into a fixed number of quantized
values, and minimum hop count paths are generated for each quantized
value. For example, one could assume that bandwidth values are
quantized as low, medium, and high, and minimum hop count paths are
computed for each of these three values. A new flow is then assigned
to the minimum hop path that can carry the smallest quantized
Guerin,Orda,Williams Expires 10 May 1997 [Page 11]
Internet Draft QoS Routing Mechanisms 5 November 1996
value, i.e., low, medium, or high, larger than or equal to what it
requested.
Here too, we discuss the elementary case where all edges count as
``hops'', and note that the modification required for supporting
zero-hop edges is straightforward.
As with the BF algorithm, the algorithm relies on a routing table
that gets built as the algorithm progresses. The structure of the
routing table is as follows:
The QoS routing table:
- a K x Q matrix, where K is the number of vertices and Q is the
number of quantized bandwidth values.
- The (n;q) entry contains information that identifies the
minimum hop count path to destination n, that is capable of
accommodating a bandwidth request of at least bw[q] (the qth
quantized bandwidth value). It consists of two fields:
* hops: the minimal number of hops on a path between the
source node and destination n, that can accommodate a
request of at least bw[q] units of bandwidth.
* neighbor: this is again the routing information associated
with the minimum hop count path to destination node n,
whose available bandwidth is at least bw[q]. As before, the
specific nature of this information depends on the scope of
the path being selected.
+ When the scope of the path being selected is simply the
next hop, i.e., hop-by-hop path selection, the neighbor
information is simply the identity of the node adjacent
to the source node on that path.
+ When the path being selected is a complete source route,
the neighbor information is the previous node (6), i.e.,
preceding the destination node n, on that path.
The algorithm operates again on a directed graph where vertices
correspond to routers and transit networks. The metric associated
with each edge in the graph is as before the bandwidth available on
----------------------------
6. See Appendix A for details on how the complete source route is
constructed based on the neighbor information kept in the table.
Guerin,Orda,Williams Expires 10 May 1997 [Page 12]
Internet Draft QoS Routing Mechanisms 5 November 1996
the corresponding interface, where bn;mis the available bandwidth
on the edge between vertices n and m. The vertex corresponding to
the router where the algorithm is being run is selected as the source
node for the purpose of path selection, and the algorithm proceeds to
compute paths to all other nodes (destinations).
Starting with the highest quantization index, Q, the algorithm
considers the indices consecutively, in decreasing order. For each
index q, the algorithm deletes from the original network topology
all links (n;m) for which bn;m< bw[q], and then runs on the remaining
topology a Dijkstra-based minimum hop count algorithm (7) between
the source node and all other nodes (vertices) in the graph. Note
that as with the Dijkstra used for on-demand path computation, the
elimination of links such that bn;m < bw[q] could also be performed
while running the algorithm.
After the algorithm terminates, the q-th column in the routing table
is updated. This amounts to recording in the hops field the hop
count value of the path that was generated by the algorithm, and by
updating the neighbor field. As before, the update of the neighbor
field depends on the scope of the path computation. In the case
of a hop-by-hop routing decision, the neighbor field is set to the
identity of the node adjacent to the source node (next hop) on the
path returned by the algorithm. Conversely, if the algorithm is
expected to generate a complete source route, the neighbor field is
set to the predecessor of the destination node on the path returned
by the algorithm. However, note that in order to ensure that the
path with the maximal available bandwidth is always chosen among all
minimum hop paths that can accommodate a given quantized bandwidth,
a slightly different update mechanism of the neighbor field needs
to be used in some instances. Specifically, when for a given row,
i.e., destination node n, the value of the hops field in column q is
found equal to the value in column q+1 (here we assume q <Q), i.e.,
paths that can accommodate bw[q] and bw[q+ 1] have the same hop count,
then the algorithm copies the value of the neighbor field from entry
(n;q+ 1) into that of entry (n;q).
----------------------------
7. Note that a Breadth-First-Search (BFS) algorithm
[CLR90] could also be used. It has a lower complexity, but would not
allow reuse of existing code in an OSPF implementation.
Guerin,Orda,Williams Expires 10 May 1997 [Page 13]
Internet Draft QoS Routing Mechanisms 5 November 1996
3. Establishment and Maintenance of QoS Routes
In this section, we briefly review issues related to how QoS paths
are established and maintained. For both, there are functional and
protocol aspects that need to be covered.
One important aspect is whether the selection of a QoS path is
distributed, e.g., a hop-by-hop model where each router on the path
makes its own decision on what the appropriate next hop should be, or
centralized as in a source-route model where the router from which
the flow originates specifies the full (8) path to be followed.
Which approach is followed has implications in terms of how to ensure
consistency of QoS paths and how and what information is to be
distributed to achieve this. In particular, aspects related to what
checks are needed when selecting (pinning a path), which criteria are
used to determine when a path needs to be changed (unpinned), and who
is responsible for initiating such a change, raise different problems
depending on how distributed the path selection process is.
For example, in the case of a distributed hop-by-hop path selection
process, special care must be exercised to prevent the formation
of loops that could occur when routers use inconsistent metrics
information. This can occur because of the finite time in which
updates propagate between routers. Preventing loops would typically
require the presence of a ``route trace'' mechanism in the message
used to carry the request for a QoS route from node to node. For
example, if this message was an RSVP PATH message, a ROUTE_OBJECT
could be defined that would carry the identity of the routers that
the message has traversed so far. Conversely, in the case of a
source route type path selection process, the same ROUTE_OBJECT could
be used to carry the identity of the routers on the path computed by
the origin router.
Another important aspect to consider is how QoS paths are pinned
and unpinned. Pinning of a QoS path is needed in order to avoid
changes whenever link metrics are updated. This is important as the
selection of a path is typically followed by a resource reservation
phase, that would then have to be repeated every time the path would
change. This would in turn affect the level of service provided
to the flow. Unpinning is needed whenever the flow terminates, or
network conditions change that affect the ability of the path to
deliver the requested QoS, e.g., a link failure, or in instances
where adequate resources can ultimately not be allocated to the flow.
----------------------------
8. Loose source routes are also possible.
Guerin,Orda,Williams Expires 10 May 1997 [Page 14]
Internet Draft QoS Routing Mechanisms 5 November 1996
The latter can occur if the actual resource reservation takes place
significantly later after the path was selected, or simply because
of the unavailability of resources. For example, this may be the
case for an RSVP flow where the selection of the path is triggered
by the receipt of a PATH message, but the corresponding RESV message
responsible for the actual reservation arrives much later. In such a
case as well as in instances when resources are simply not available
on any path, the issue that arises is how to decide when to unpin a
path. Unpinning is warranted if a better alternative exists, but
this may not always be easy to determine. For example, unpinning at
a given node may not seem to offer any better alternative, but a much
better path might be available if the unpinning propagates all the
way back to the origin. Control of this process may require specific
support in the protocol used to request QoS paths, e.g., adding
message types to the RSVP protocol. Appendix E outlines possible
directions to address some of these issues.
4. OSPF Protocol Enhancements
As stated above, a goal of this work is limit the additions to the
existing OSPF V2 protocol, while still providing the required level
of support for QoS based routing. To this end, all of the existing
OSPF mechanisms, data structures, advertisements, and data formats
remain in place. The purpose of this section of the document is to
list the enhancements to the OSPF protocol to support QoS as outlined
in the previous sections.
4.1. QoS -- Optional Capabilities
The OSPF Options field is present in OSPF Hello packets, Database
Description packets and all LSAs. The Options field enables OSPF
routers to support (or not support) optional capabilities, and to
communicate their capability level to other OSPF routers. Through
this mechanism, routers of differing capabilities can be mixed with
an OSPF routing domain.
This document describes one of the Option bits: the Q-bit (for QoS
capability). The Q-bit is set in router, network, and summary links
advertisements, and is used to identify routers and networks that
support (or do not support) QoS routing as defined in this document.
When the Q-bit is set in a router or summary links link state
advertisement, it means that there are QoS fields to process in the
packet. When the Q-bit is set in a network link state advertisement
it means that the network described in the advertisement is not delay
sensitive as described in this document.
Guerin,Orda,Williams Expires 10 May 1997 [Page 15]
Internet Draft QoS Routing Mechanisms 5 November 1996
-------------------------------
| * | Q | DC| EA|N/P| MC| E | T |
-------------------------------
4.2. Packet Formats
To support QoS, there are additions to two Link State Advertisements,
the Router Links Advertisement and the Summary Links Advertisement.
As stated above, a router identifies itself as support QoS by setting
the Q-bit in the options field of the Link State Header. When a
router that supports QoS receives either the Router Links or Summary
Links Advertisement, it should parse the received Advertisement using
the following packet formats.
4.2.1. Router Links Advertisements
0 8 16 24 32
| | |
---------------------------------
| |
|-- --|
| |
|-- --|
| Link State Header |
|-- --|
| |
|-- --|
| |
|---------------------------------|
| 0 |VEB| 0 | # Links |
|---------------------------------|
| Link ID |
|---------------------------------|
| Link Data |
|---------------------------------|
| Type | # TOS | TOS 0 Metric |
|---------------------------------|
| Available Bandwidth |
|---------------------------------|
.
. # link times
.
|---------------------------------|
| Link ID |
Guerin,Orda,Williams Expires 10 May 1997 [Page 16]
Internet Draft QoS Routing Mechanisms 5 November 1996
|---------------------------------|
| Link Data |
|---------------------------------|
| Type | 0 | TOS 0 Metric |
|---------------------------------|
| Available Bandwidth |
|---------------------------------|
Where:
-- Available Bandwidth is an integer in kbit/sec.
-- All other fields remain unchanged.
4.2.2. Summary Link Advertisement
0 8 16 24 32
| | |
---------------------------------
| | 3 |
|-- ---------|
| |
|-- --|
| Link State Header |
|-- --|
| |
|-- --|
| |
|---------------------------------|
| Network Mask |
|---------------------------------|
| Available Bandwidth |
|---------------------------------|
| # Hops |
|---------------------------------|
.
. # hop times
.
|---------------------------------|
| Available Bandwidth |
|---------------------------------|
| # Hops |
|---------------------------------|
Where:
-- Available Bandwidth is an integer in kbit/sec.
Guerin,Orda,Williams Expires 10 May 1997 [Page 17]
Internet Draft QoS Routing Mechanisms 5 November 1996
-- Hops is the number of hops from the advertising area border router
to the network.
-- All other fields remain unchanged.
4.3. Calculating the inter-area routes
This document proposes a very limited use of OSPF areas, that is, it
is assumed that summary links advertisements exist for all networks
in the area. This document does not discuss the problem of providing
support for area address ranges and QoS metric aggregation.
4.4. Open Issues
Support for AS External Links, Virtual Links, and incremental updates
for summary link advertisements are not addressed in this document
and are left for further study. For Virtual Links that do exist, it
is assumed for path selection that this links are non-QoS capable
even if the router advertises QoS capability. Also, as stated
earlier, this document does not address the issue of non-QoS routers
within a QoS domain.
Acknowledgements
We would like to thank the many people who have helped shape various
aspects of this document and the approaches it describes, either
through discussions or explicit suggestions. In particular, we would
like to acknowledge the help and inputs of John Moy, Sanjay Kamat,
Dilip Kandlur, and Dimitrios Pendarakis.
Guerin,Orda,Williams Expires 10 May 1997 [Page 18]
Internet Draft QoS Routing Mechanisms 5 November 1996
APPENDICES
A. Construction of Path Information
As mentioned before, the scope of the path selection process can
range from simply returning the next hop on the QoS path selected for
the flow, to specifying the complete path that was computed, i.e., a
source route. Obviously, the information being returned by the path
selection algorithm differs in these two cases, and constructing it
imposes different requirements on the path selection algorithm and
the data structures it relies on. Some of these issues were briefly
alluded to in Section 2.3. Here, we provide additional details on
how paths are constructed from the information in the QoS routing
tables, for both the hop-by-hop and source route cases.
A.1. Source routed paths
In the case of source routed paths, the path selection algorithm
needs to return the complete list of vertices (routers) on the path
that has just been identified. Note that this also extends readily
to the case of loose source routes. The issue is how to generate
the list of vertices making up the path with minimal impact on the
path computation process. Specifically, this means how to use the
neighbor information in the QoS routing table to construct the list
of vertices on the path. Recall that the rows of the QoS routing
table are indexed using the corresponding indices of vertices in
the graph. We focus here on the case of pre-computed paths, but
a similar issue clearly exists when paths are computed on-demand.
However, the same approach is essentially applicable in both cases so
that only the case of pre-computed paths is covered.
The basic approach used to extract the complete list of vertices on
a path from the neighbor information in the QoS routing table is to
proceed recursively from the destination to the origin vertex. The
path is extracted by stepping through the precomputed QoS routing
table from vertex to vertex, and identifying at each step the
correspond neighbor (precursor) information. Once the source router
is reached, the concatenation of all the neighbor fields that have
been extracted forms the desired source route. This applies to the
source-routed versions of both algorithms of Sections 2.3.1 and
2.3.3.
Specifically, assume a new request to destination, say, d, and with
bandwidth requirements B. The index of the destination vertex
identifies the row in the QoS routing table that needs to be checked
to generate a path. How the row is searched to identify a suitable
Guerin,Orda,Williams Expires 10 May 1997 [Page 19]
Internet Draft QoS Routing Mechanisms 5 November 1996
path depends on which algorithm was used to construct the QoS routing
table. If the Bellman-Ford algorithm of Section 2.3.1 is used, the
search proceeds by increasing index (hop) count until an entry is
found, say at hop count or column index of h, with a value of the
bw field which is greater than or larger than B. This entry points
to the initial information identifying the selected path. If the
Dijkstra algorithm of Section 2.3.3 is used, the first quantized
value bBsuch that Bb B is first identified, and the associated
column then determines the first entry in the QoS routing table that
identifies the selected path.
Once this first entry has been identified, reconstruction of the
complete list of vertices on the path proceeds similarly, whether
the table was built using the algorithm of Sections 2.3.1 or 2.3.3.
Specifically, in both cases, the neighbor field in each entry
points to the previous node on the path to the node and bandwidth
value associated with the current entry. The complete path is
reconstructed by following the pointers provided by the neighbor
field of successive entries.
In the case of the Bellman-Ford algorithm of Section 2.3.1, this
means moving backwards in the table from column to column, using at
each step the row index pointed to by the neighbor field of the entry
in the previous column. Each time, the corresponding vertex index
specified in the neighbor field is pre-pended to the list of vertices
constructed so far. Since we start at column h, the process ends
when first column is reached, i.e., after h steps, at which point
the list of vertices making up the path has been reconstructed.
In the case of the Dijkstra algorithm of Section 2.3.3, the
backtracking process is similar although slightly different because
of the different relation between paths and columns in the routing
table, i.e., a column now corresponds to a quantized bandwidth value
instead of a hop count. The backtracking now proceeds along the
column corresponding to the quantized bandwidth value needed to
satisfy the bandwidth requirements of the flow. At each step, the
vertex index specified in the neighbor field is pre-pended to the
list of vertices constructed so far, and is used to identify the next
row index to move to. The process ends when an entry is reached
whose neighbor field specifies the origin vertex of the flow. Note
that since there are as many rows in the table as there are vertices
in the graph, i.e., N, it could take up to N steps before the
process terminates.
Guerin,Orda,Williams Expires 10 May 1997 [Page 20]
Internet Draft QoS Routing Mechanisms 5 November 1996
A.2. Hop-by-Hop Routing
The case of hop-by-hop routing is much simpler as far as the
construction of path information is concerned. This is because
only the next hop needs to be returned instead of a complete source
route. The next hop information is then directly retrieved from the
neighbor information of the first entry pointed to in the QoS routing
table. The identification of this first entry is identical to what
was described for the source routed case. However, note that as
described in Sections 2.3.1 and 2.3.3, the update of the neighbor
fields while constructing the QoS routing tables, is being performed
differently in the source and hop-by-hop routing cases. Note that
both types of updates could certainly be performed jointly, and two
neighbor fields kept in each entry, with each corresponding to either
the source routed or hop-by-hop routing modes.
B. Computational Complexity
One generic aspect of the algorithmic complexity of computing
QoS paths is the efficiency of the shortest path algorithm used.
Specifically, in this document, we have described approaches based on
both Bellman-Ford and Dijkstra shortest paths algorithms. Dijkstra's
algorithm has traditionally been considered more efficient for
standard shortest path computations because of its lower worst case
complexity. However, the answer is not as simple as may appear, and
in this section we briefly review a number of considerations, in
particular in the context of multi-criteria QoS paths, which indicate
that a BF approach may often provide a lower complexity solution.
The asymptotic worst-case complexity of the Dijkstra algorithm is
O(NlogN + M), where N is the number of vertices in the graph,
and M the number of edges. However, this bound is obtained
under the assumption of a Fibonnaci heap implementation of the
Dijkstra algorithm, which is impractical due to the large constants
involved [CLR90]. In practice, the Dijkstra algorithm is typically
implemented using binary heaps, for which the asymptotic worst-case
bound is O(MlogN).
The asymptotic worst-case bound for the BF algorithm is O(H . M),
where M is again the number of edges in the graph, and H, which is
the maximum number of iterations of the algorithm, is an upper-bound
on the number of hops in a shortest path. Although, theoretically,
H can be as large as N - 1, in practice it is usually considerably
smallercthan N. Moreover, in some network scenarios an upper-bound
H of small size (i.e., cH << N) is imposed on the allowed number
of hops; for example, it might be decided to exclude paths that
have more than, say, 16 hops, as part of a call admission scheme.
Guerin,Orda,Williams Expires 10 May 1997 [Page 21]
Internet Draft QoS Routing Mechanisms 5 November 1996
In such cases, the number of iterations of the BF algorithm can be
limited to cH, thus bounding the number of operations to O(cH . M),
i.e., effectively to O(M). As a consequence, as noted in [BG92],
in practical networking scenarios, the BF algorithm can offer an
efficient solution to the shortest path problem, one that often
outperforms the Dijkstra algorithm. (9)
In the context of QoS path selection, the potential benefits of the
BF algorithm are even stronger. As mentioned before, efficient
selection of a suitable path for flows with QoS requirements cannot
usually be handled using a single-objective optimization criterion.
While multi-objective path selection is known to be an intractable
problem [GJ79], the BF algorithm allows us to handle a second
objective, namely the hop-count, which is reflective of network
resources, at no additional cost in terms of complexity. The
Dijkstra algorithm requires some modifications (or approximations,
e.g., bandwidth quantization) in order to be able to deal with hop
count as a second objective.
Therefore, in the context of a QoS path selection algorithm,
where one objective is some QoS-oriented metric, such as available
bandwidth, whereas the second is a hop-count metric, a BF-based
algorithm provides an efficient scheme for pre-computing paths,
i.e., one with a worst case asymptotic complexity of O(H . M).
Alternatively, if QoS paths are pre-computed using a Dijkstra
algorithm with Q quantized bandwidth values, the corresponding worst
case asymptotic complexity is O(Q . (M logN)). Both approaches
provide solutions of comparable orders of complexity, whose exact
merits depend on the respective values of H, Q and N. If on-demand
computations of QoS paths are practical, then a standard Dijkstra
algorithm provides a solution of complexity O(MlogN).
C. Extension: Handling Propagation Delays
In general, the framework proposed for path selection does not allow
us to explicitly account for link propagation delays. As mentioned,
this aspect is dealt with through a policy mechanism, which for
delay-sensitive connections deletes from the topology database links
----------------------------
9. For example, in the experimental comparison reported in [CGR94], the
BF algorithm outperformed the Dijkstra algorithm in about one third
of the studied types of topology, and in several of the other
topologies it outperformed the Dijkstra algorithm for networks of up
to about 16;000 nodes. It should be noted that in those experiments
no upper bound on the number of hops in a shortest path was set.
Guerin,Orda,Williams Expires 10 May 1997 [Page 22]
Internet Draft QoS Routing Mechanisms 5 November 1996
with high propagation delays, such as satellite links. However, it
is worth pointing out that a simple extension to the proposed path
selection algorithm allows us to directly account for delay in a
number of special cases. We proceed to describe next this extension
and the cases where it applies.
A common way to map delay guarantees into bandwidth guarantees
(e.g., consistent with the schedulers and corresponding delay
bounds presented in [GGPS96, PG94]) is according to the following
expression:
D(p) =A(h(p))/b +sum_(l in p) d_l (1)
where p is the path traversed, D(p) is the guaranteed (upper-bound)
end to end delay, h(p) is the number of hops, b is the reserved
bandwidth, dlis the (fixed) propagation delay of a link l, and ff(h)
is a parameter that grows with h (a typical value is ff(h) = oe+ h. c,
where oe is the burst size and c is the maximum packet size).
Since we deal with intra-domain routing, and since links with
prohibitively high propagation delays are assumed to be filtered out
by policing, it can be assumed that typically there is some value
d which is a reasonable upper bound on the propagation delays dlof
all links. Expression (1) then implies that an end to end delay
requirement D can be translated into a bandwidth requirement b(h) by
the following expression:
b(h)= A(h)/(D-h.d) (2)
where h is the number of hops on the path established for the
connection.
D. Zero-Hop Edges
The need to handle zero-hop edges is due to the potential presence
of multiple access networks, e.g., T/R, E/N, or ATM, to interconnect
routers. Such entities are also represented by means of a vertex
in the current OSPF operation. Clearly, in such cases a network
connecting two routers should be considered as a single hop path
rather than a two hop path. For example, consider three routers
A, B, and C connected over an Ethernet network N, which the OSPF
topology represents as:
A----N----B
Guerin,Orda,Williams Expires 10 May 1997 [Page 23]
Internet Draft QoS Routing Mechanisms 5 November 1996
|
|
C
In the above example, although there are directed edges in both
directions, an edge from the network to any of the three routers
must have zero ``cost'', so that it is not counted twice. It should
be noted that when considering such environments in the context
of QoS routing, it is assumed that some entity is responsible
for determining the ``available bandwidth'' on the network. The
specification of the operation of such an entity is beyond the scope
of this document.
E. Sample Path Establishment Scenario
In this section, we briefly illustrate the use of the QoS path
selection approach described in this document, for a unicast RSVP
flow. We assume that the receipt of the first PATH message serves
as the trigger for invoking the QoS path selection algorithm. In
other words, upon receipt of a PATH message, RSVP would query the
QoS routing entity for a suitable path. We further assume a source
routed path selection approach, and only outline at the end of the
section some of the modifications needed to support a hop-by-hop
routing mode.
After the first PATH message has been received at the first router
of the area to which the QoS path computation applies, the IP
destination address specified in the PATH message is translated into
the destination vertex needed as input to path selection. The other
input to the path selection process, i.e., the required bandwidth,
is derived from the TSpec contained in the PATH message. Assuming
that the QoS routing table was pre-computed, a complete source route
is returned as described in Appendix A. At this point, the selected
path (source route) is returned by the QoS routing to RSVP, and
QoS Routing pins this path for the corresponding RSVP flow. This
ensures that the same path is returned whenever RSVP queries again
QoS routing for the same flow (10).
In order to carry the returned source route information, we assume
the existing of a new, opaque object carried by RSVP, i.e., a
----------------------------
10. Alternatively, this responsibility could be left to RSVP, and this
document makes no claims as to what the preferred approach should be.
As mentioned earlier, this, together with other path management
aspects, requires further investigation.
Guerin,Orda,Williams Expires 10 May 1997 [Page 24]
Internet Draft QoS Routing Mechanisms 5 November 1996
QOS_ROUTE object. Such an object would be similar in structure to
the Policy object of [Her96], and would contain the source route
generated by the origin router. At intermediate routers, RSVP would
pass the QOS_ROUTE object to the QoS routing process, so that it can
both validate the path, return the appropriate next hop forwarding
information, and also locally pin the path for the flow. When the
PATH message reaches its destination (or exits the area), a QoS
path has been pinned down for the associated flow. Maintenance of
this path would rely on the RSVP PATH refreshes and existing state
maintenance capabilities.
When a RESV message is subsequently received at a router, its
processing is unchanged from what is currently done. If the
reservation fails, a RESV_ERROR message will be sent to the receiver
which originated the reservation request, while the RESV messages
keeps on being propagated upstream (11). In that case, it is
important to notify the QoS routing entity that selected the path
on which the reservation fails as it may then be able to identify
a new path on which the reservation would succeed at all hops.
Unfortunately, no mechanism is currently available in RSVP to support
that. A possible approach is to again define a new RSVP object (or
piggyback an existing policy object) to carry this information back.
Assuming the availability of such a mechanism, the next issue is to
determine who should be responsible for acting on this information
and possibly selecting a new path. In the context of a source routed
environment, we will, for simplicity, assume that only the entity
that computed the source route can recompute it. More flexible
choices are clearly possible and may even be needed in the case of
hop-by-hop routing. We defer such a discussion to [GOW96]. Assuming
a new path is computed and found to be better (12), then a PATH_TEAR
message is sent on the original path before PATH messages carrying
the new source route are sent on the new path. Note that sending the
PATH_TEAR before the new PATH message may be needed to avoid problems
on segments were the new and old paths coincide (this can be easily
avoided through simple indexing of paths, to uniquely identify them).
Next, we briefly mention some of the modifications and extensions
needed if hop-by-hop routing was used instead. The first
modification is that the QOS_ROUTE object will now be used to
accumulate the list of routers previously visited by the PATH
message. This is needed to prevent formation of loops which could
----------------------------
11. we are assuming for simplicity a unicast fixed filter case, so there
is no possibility of the reservation being blocked by lower ones.
12. The determination of when this is true is a topic in itself.
Guerin,Orda,Williams Expires 10 May 1997 [Page 25]
Internet Draft QoS Routing Mechanisms 5 November 1996
occur if routers used inconsistent information when selecting a QoS
path. Such an occurrence may not be rare as changes in link loads
may not always reach all routers at the same time and can affect
how each identifies the ``best'' next hop for a given flow request.
By carrying and updating at each hop information that identifies
all the routers currently on the path, loops can effectively be
prevented. Another simpler but less accurate approach is to rely
on the monitoring of hop counts. If successive PATH messages are
received with increasing hop count values, this information can be
used to detect that a loop exists on the path and trigger generation
of a local PATH_TEAR and recomputation of a path.
Another modification is needed to deal with reservation failures
as a new path can now be recomputed from any point. This means
that selection of a new best next hop could be triggered locally
upon detecting failure of the reservation. However, local path
``repairs'' may not always be appropriate, and a much better path may
be available by restarting from the source. Therefore, mechanisms
must be put in place that determine when to attempt local re-routing
and when to simply defer this responsibility to another node.
F. Pseudocode for BF Algorithm
Note: The pseudocode below assumes a hop-by-hop forwarding approach in
updating the neighbor field. The modifications needed to support a
source routed approach are straightforward.
Input:
V = set of vertices, labeled by integers 1 to N.
L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
s = source vertex (at which the algorithm is executed).
For all edges (n,m) in L:
b(n,m) = available bandwidth (according to last received update)
on interface associated with the edge between vertices n and m.
H = maximum hop-count (at most the graph diameter).
Type:
tab_entry: record
bw = integer,
neighbor = integer 1..N.
Variables:
TT[1..N, 1..H]: topology table, whose (n,h) entry is a tab_entry record, such
that:
TT[n,h].bw is the maximum available bandwidth (as known
thus far) on a path of at most h hops between
vertices s and n,
Guerin,Orda,Williams Expires 10 May 1997 [Page 26]
Internet Draft QoS Routing Mechanisms 5 November 1996
TT[n,h].neighbor is the first hop on that path (a neighbor
of s). It is either a router or the destination n.
S_prev: list of vertices that changed a bw value in the TT table
in the previous iteration.
S_new: list of vertices that changed a bw value (in the TT table etc.) in the
current iteration.
The Algorithm:
begin;
for n:=1 to N do /* initialization */
begin;
TT[n,0].bw := 0;
TT[n,0].neighbor := null
end;
TT[s,0].bw := infinity;
reset S_prev;
for all neighbors n of s do
begin;
TT[n,1].bw := b[s,n];
TT[n,1].neighbor := n;
if n is a router then S_prev := S_prev union {n}
/* only routers are added to S_prev */
else /* n is a network: */
/* proceed with network--router edges, without counting them as */
/* another hop */
for all (n,k) in L, k <> s, do
/* i.e., for all other neighboring routers of n */
begin;
TT[k,1].bw := min( TT[n,1].bw, b[n,k]);
TT[k,1].neighbor := k;
/* first neighbor in a multi-hop path is a router */
S_prev := S_prev union {k}
/* only routers are added to S_prev */
end
end;
for h:=2 to H do /* consider all possible number of hops */
begin;
reset S_new;
for all vertices m in V do
begin;
TT[m,h].bw := TT[m,h-1].bw;
TT[m,h].neighbor := TT[m,h-1].neighbor
Guerin,Orda,Williams Expires 10 May 1997 [Page 27]
Internet Draft QoS Routing Mechanisms 5 November 1996
end;
for all vertices n in S_prev do
/* as shall become evident, S_prev contains only routers */
begin;
for all edges (n,m) in L do
if min( TT[n,h-1].bw, b[n,m]) > TT[m,h].bw then
begin;
TT[m,h].bw := min( TT[n,h-1].bw, b[n,m]);
TT[m,h].neighbor := TT[n,h-1].neighbor;
if m is a router then S_new := S_new union {m}
/* only routers are added to S_new */
else /* m is a network: */
/* proceed with network--router edges, without counting them as */
/* another hop */
for all (m,k) in L, k <> n,
/* i.e., for all other neighboring routers of m */
if min( TT[m,h].bw, b[m,k]) > TT[k,h].bw then
begin;
/* Note: still counting it as the h-th hop, as (m,k) is a */
/* network--router edge */
TT[k,h].bw := min( TT[m,h].bw, b[m,k]);
TT[k,h].neighbor := TT[m,h].neighbor;
S_new := S_new union {k}
/* only routers are added to S_new */
end
end
end;
S_prev := S_new;
/* the two lists can be handled by a toggle bit */
if S_prev=null then h=H+1 /* if no changes then exit */
end;
end.
References
[BG92] D. Bertsekas and R. G. Gallager. Data Networks. Prentice
Hall, Englewood Cliffs, NJ, 2nd edition, 1992.
[CGR94] B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest
Paths Algorithms: Theory and Experimental Evaluation.
In Proceedings of the 5th Annual ACM SIAM Symposium on
Discrete Algorithms, pages 516--525, Arlington, VA, January
1994.
Guerin,Orda,Williams Expires 10 May 1997 [Page 28]
Internet Draft QoS Routing Mechanisms 5 November 1996
[CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest.
Introduction to Algorithms. MIT Press, Cambridge, MA,
1990.
[GGPS96] L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivarajan.
Efficient Network QoS Provisioning Based on per Node
Traffic Shaping. IEEE/ACM Transactions on Networking,
4(4):482--501, August 1996.
[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability.
Freeman, San Francisco, 1979.
[GOW96] R. Guerin, A. Orda, and D. Williams. Establishment and
management of QoS routes. Research report, IBM, T. J.
Watson Research Center, 1996. (work in progress).
[Her96] S. Herzog. RSVP Extensions for Policy Control.
(draft-ietf-rsvp-policy-ext-01.[ps,txt]. Internet Draft,
November 1996.
[PG94] A. K. Parekh and R. G. Gallager. A Generalized Processor
Sharing Approach to Flow Control in Integrated Services
Networks: the Multiple Node Case. IEEE/ACM Transactions
on Networking, 2:137--150, 1994.
[RZB+96] R. Braden (Ed.), L. Zhang, S. Berson, S. Herzog, and
S. Jamin. Resource reSerVation Protocol (RSVP) version
1, functional specification (draft-ietf-rsvp-spec-13.ps).
INTERNET-DRAFT, Internet Engineering Task Force - RSVP WG,
July 1996.
Authors' Address
Roch Guerin
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
guerin@watson.ibm.com
VOICE +1 914 784-7038
FAX +1 914 784-6318
Ariel Orda
Dept. Electrical Engineering
Technion - I.I.T
Haifa, 32000 - ISRAEL
Guerin,Orda,Williams Expires 10 May 1997 [Page 29]
Internet Draft QoS Routing Mechanisms 5 November 1996
ariel@ee.technion.ac.il
VOICE +011 972-4-8294646
FAX +011 972-4-8323041
Doug Williams
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
dougw@watson.ibm.com
VOICE +1 914 784-5047
FAX +1 914 784-6318
Guerin,Orda,Williams Expires 10 May 1997 [Page 30]