RFC relevance of multicast

As per Relevance of the word multicast, we have this rfc below:

Network Working Group E.
Request for Comments: 2386 Argon
Category: Informational R.

B.
NEC
H.
Bay
August 1998

A Framework for QoS-based Routing in the

Status of this

This memo provides information for the Internet community. It
not specify an Internet standard of any kind. Distribution of
memo is unlimited

Copyright

Copyright (C) The Internet Society (1998). All Rights Reserved

QoS-based routing has been recognized as a missing piece in
evolution of QoS-based service offerings in the Internet.
document describes some of the QoS-based routing issues
requirements, and proposes a framework for QoS-based routing in
Internet. This framework is based on extending the current
routing model of intra and interdomain routing to support QoS

1. SCOPE OF DOCUMENT &

This document proposes a framework for QoS-based routing, with
objective of fostering the development of an Internet-wide
while encouraging innovations in solving the many problems
arise. QoS-based routing has many complex facets and it
recommended that the following two-pronged approach be
towards its development

1. Encourage the growth and evolution of novel intradomain QoS-
routing architectures. This is to allow the development
independent, innovative solutions that address the many QoS-
routing issues. Such solutions may be deployed in
systems (ASs), large and small, based on their specific needs

Crawley, et. al. Informational [Page 1]

RFC 2386 A Framework for QoS-based Routing August 1998

2. Encourage simple, consistent and stable interactions between
implementing routing solutions developed as above

This approach follows the traditional separation between intra
interdomain routing. It allows solutions like QOSPF [GKOP98, ZSSC97],
Integrated PNNI [IPNNI] or other schemes to be deployed
intradomain routing without any restriction, other than their
to interact with a common, and perhaps simple, interdomain
protocol. The need to develop a single, all encompassing solution
the complex problem of QoS-based routing is therefore obviated. As
practical matter, there are many different views on how QoS-
routing should be done. Much overall progress can be made if
opportunity exists for various ideas to be developed and
concurrently, while some consensus on the interdomain
architecture is being developed. Finally, this routing model
perhaps the most practical from an evolution point of view. It
superfluous to say that the eventual success of a QoS-based
routing architecture would depend on the ease of evolution

The aim of this document is to describe the QoS-based routing issues
identify basic requirements on intra and interdomain routing,
describe an extension of the current interdomain routing model
support QoS. It is not an objective of this document to specify
details of intradomain QoS-based routing architectures. This is
up to the various intradomain routing efforts that might follow.
is it an objective to specify the details of the interface
reservation protocols such as RSVP and QoS-based routing.
specific interface functionality needed, however, would be clear
the intra and interdomain routing solutions devised. In
intradomain area, the goal is to develop the basic
requirements while allowing maximum freedom for the development
solutions. In the interdomain area, the objectives are to
the QoS-based routing functions, and facilitate the development
enhancement of a routing protocol that allows relatively
interaction between domains

In the next section, a glossary of relevant terminology is given.
Section 3, the objectives of QoS-based routing are described and
issues that must be dealt with by QoS-based Internet routing
are outlined. In Section 4, some requirements on intradomain
are defined. These requirements are purposely broad, putting
constraints on solution approaches. The interdomain routing model
issues are described in Section 5 and QoS-based multicast routing
discussed in Section 6. The interaction between QoS-based
and resource reservation protocols is briefly considered in
7. Security considerations are listed in Section 8 and related
is described in Section 9. Finally, summary and conclusions
presented in Section 10.

Crawley, et. al. Informational [Page 2]

RFC 2386 A Framework for QoS-based Routing August 1998

2.

The following glossary lists the terminology used in this
and an explanation of what is meant. Some of these terms may
different connotations, but when used in this document, their
is as given

Alternate Path Routing : A routing technique where multiple paths
rather than just the shortest path, between a source and
destination are utilized to route traffic. One of the objectives
alternate path routing is to distribute load among multiple paths
the network

Autonomous System (AS): A routing domain which has a
administrative authority and consistent internal routing policy.
AS may employ multiple intradomain routing protocols internally
interfaces to other ASs via a common interdomain routing protocol

Source: A host or router that can be identified by a unique
IP address

Unicast destination: A host or router that can be identified by
unique unicast IP address

Multicast destination: A multicast IP address indicating all
and routers that are members of the corresponding group

IP flow (or simply "flow"): An IP packet stream from a source to
destination (unicast or multicast) with an associated Quality
Service (QoS) (see below) and higher level
information. The associated QoS could be "best-effort".

Quality-of-Service (QoS): A set of service requirements to be met
the network while transporting a flow

Service class: The definitions of the semantics and parameters of
specific type of QoS

Integrated services: The Integrated Services model for the
defined in RFC 1633 allows for integration of QoS services with
best effort services of the Internet. The Integrated
(IntServ) working group in the IETF has defined two service classes
Controlled Load Service [W97] and Guaranteed Service [SPG97].

RSVP: The ReSerVation Protocol [BZBH97]. A QoS signaling
for the Internet

Path: A unicast or multicast path

Crawley, et. al. Informational [Page 3]

RFC 2386 A Framework for QoS-based Routing August 1998

Unicast path: A sequence of links from an IP source to a unicast
destination, determined by the routing scheme for forwarding packets

Multicast path (or Multicast Tree): A subtree of the network
in which all the leaves and zero or more interior nodes are
of the same multicast group. A multicast path may be per-source,
which case the subtree is rooted at the source

Flow set-up: The act of establishing state in routers along a path
satisfy the QoS requirement of a flow

Crankback: A technique where a flow setup is recursively
along the partial flow path up to the first node that can
an alternative path to the destination

QoS-based routing: A routing mechanism under which paths for
are determined based on some knowledge of resource availability
the network as well as the QoS requirement of flows

Route pinning: A mechanism to keep a flow path fixed for a
of time

Flow Admission Control (FAC): A process by which it is
whether a link or a node has sufficient resources to satisfy the
required for a flow. FAC is typically applied by each node in
path of a flow during flow set-up to check local
availability

Higher-level admission control: A process by which it is
whether or not a flow set-up should proceed, based on estimates
policy requirements of the overall resource usage by the flow
Higher-level admission control may result in the failure of a
set-up even when FAC at each node along the flow path
resource availability

3. QOS-BASED ROUTING: BACKGROUND AND

3.1 Best-Effort and QoS-Based

Routing deployed in today's Internet is focused on connectivity
typically supports only one type of datagram service called "
effort" [WC96]. Current Internet routing protocols, e.g. OSPF, RIP
use "shortest path routing", i.e. routing that is optimized for
single arbitrary metric, administrative weight or hop count.
routing protocols are also "opportunistic," using the
shortest path or route to a destination. Alternate paths
acceptable but non-optimal cost can not be used to route
(shortest path routing protocols do allow a router to alternate

Crawley, et. al. Informational [Page 4]

RFC 2386 A Framework for QoS-based Routing August 1998

several equal cost paths to a destination).

QoS-based routing must extend the current routing paradigm in
basic ways. First, to support traffic using integrated-
class of services, multiple paths between node pairs will have to
calculated. Some of these new classes of service will require
distribution of additional routing metrics, e.g. delay, and
bandwidth. If any of these metrics change frequently, routing
can become more frequent thereby consuming network bandwidth
router CPU cycles

Second, today's opportunistic routing will shift traffic from
path to another as soon as a "better" path is found. The
will be shifted even if the existing path can meet the
requirements of the existing traffic. If routing calculation is
to frequently changing consumable resources (e.g.
bandwidth) this change will happen more often and can
routing oscillations as traffic shifts back and forth
alternate paths. Furthermore, frequently changing routes can
the variation in the delay and jitter experienced by the end users

Third, as mentioned earlier, today's optimal path routing
do not support alternate routing. If the best existing path
admit a new flow, the associated traffic cannot be forwarded even
an adequate alternate path exists

3.2 QoS-Based Routing and Resource

It is important to understand the difference between QoS-
routing and resource reservation. While resource
protocols such as RSVP [BZBH97] provide a method for requesting
reserving network resources, they do not provide a mechanism
determining a network path that has adequate resources to
the requested QoS. Conversely, QoS-based routing allows
determination of a path that has a good chance of accommodating
requested QoS, but it does not include a mechanism to reserve
required resources

Consequently, QoS-based routing is usually used in conjunction
some form of resource reservation or resource allocation mechanism
Simple forms of QoS-based routing have been used in the past for
of Service (TOS) routing [M98]. In the case of OSPF, a
shortest-path tree can be computed for each of the 8 TOS values
the IP header [ISI81]. Such mechanisms can be used to
specially provisioned paths but do not completely assure
resources are not overbooked along the path. As long as
resource management and control are not needed, mechanisms such
TOS-based routing are useful for separating whole classes of

Crawley, et. al. Informational [Page 5]

RFC 2386 A Framework for QoS-based Routing August 1998

over multiple routes. Such mechanisms might work well with
emerging Differential Services efforts [BBCD98].

Combining a resource reservation protocol with QoS-based
allows fine control over the route and resources at the cost
additional state and setup time. For example, a protocol such as
may be used to trigger QoS-based routing calculations to meet
needs of a specific flow

3.3 QoS-Based Routing:

Under QoS-based routing, paths for flows would be determined
on some knowledge of resource availability in the network, as well
the QoS requirement of flows. The main objectives of QoS-
routing are

1. Dynamic determination of feasible paths: QoS-based routing
determine a path, from among possibly many choices, that has
good chance of accommodating the QoS of the given flow.
path selection may be subject to policy constraints, such as
cost, provider selection, etc

2. Optimization of resource usage: A network state-dependent QoS
based routing scheme can aid in the efficient utilization
network resources by improving the total network throughput.
a routing scheme can be the basis for efficient
engineering

3. Graceful performance degradation: State-dependent routing
compensate for transient inadequacies in network
(e.g., during focused overload conditions), giving
throughput and a more graceful performance degradation
compared to a state-insensitive routing scheme [A84].

QoS-based routing in the Internet, however, raises many issues

- How do routers determine the QoS capability of each outgoing
and reserve link resources? Note that some of these links may
virtual, over ATM networks and others may be broadcast multi
access links

- What is the granularity of routing decision (i.e., destination
based, source and destination-based, or flow-based)?

- What routing metrics are used and how are QoS-accommodating
computed for unicast flows

Crawley, et. al. Informational [Page 6]

RFC 2386 A Framework for QoS-based Routing August 1998

- How are QoS-accommodating paths computed for multicast flows
different reservation styles and receiver heterogeneity

- What are the performance objectives while computing QoS-
paths

- What are the administrative control issues

- What factors affect the routing overheads?,

- How is scalability achieved

Some of these issues are discussed briefly next. Interdomain
is discussed in Section 5.

3.4 QoS Determination and Resource

To determine whether the QoS requirements of a flow can
accommodated on a link, a router must be able to determine the
available on the link. It is still an open issue as to how the
availability is determined for broadcast multiple access links (e.g.,
Ethernet). A related problem is the reservation of resources
such links. Solutions to these problems are just emerging [GPSS98].

Similar problems arise when a router is connected to a large non
broadcast multiple access network, such as ATM. In this case, if
destination of a flow is outside the ATM network, the router may
multiple egress choices. Furthermore, the QoS availability on the
paths to each egress point may be different. The issues then are

o how does a router determine all the egress choices across
ATM network
o how does it determine what QoS is available over the path
each egress point?,
o what QoS value does the router advertise for the ATM link

Typically, IP routing over ATM (e.g., NHRP) allows the selection of
single egress point in the ATM network, and the procedure does
incorporate any knowledge of the QoS required over the path.
approach like I-PNNI [IPNNI] would be helpful here, although
introduces some complexity

An additional problem with resource reservation is how to
what resources have already been allocated to a multicast flow.
availability of this information during path computation improves
chances of finding a path to add a new receiver to a multicast flow
QOSPF [ZSSC97] handles this problem by letting routers
reserved resource information to other routers in their area

Crawley, et. al. Informational [Page 7]

RFC 2386 A Framework for QoS-based Routing August 1998

Alternate path routing [ZES97] deals with this issue by using
messages to find a path with sufficient resources. Path
Computation (PQC) method, proposed in [GOA97], propagates
allocation information in RSVP PATH messages. A router receiving
PATH message gets an indication of the resource allocation only
those links in the path to itself from the source. Allocation
the same flow on other remote branches of the multicast tree is
available. Thus, the PQC method may not be sufficient to
feasible QoS-accommodating paths to all receivers

3.5 Granularity of Routing

Routing in the Internet is currently based only on the
address of a packet. Many multicast routing protocols
routing based on the source AND destination of a packet.
Integrated Services architecture and RSVP allow QoS determination
an individual flow between a source and a destination. This set
routing granularities presents a problem for QoS routing solutions

If routing based only on destination address is considered, then
intermediate router will route all flows between different
and a given destination along the same path. This is acceptable
the path has adequate capacity but a problem arises if there
multiple flows to a destination that exceed the capacity of the link

One version of QOSPF [ZSSC97] determines QoS routes based on
and destination address. This implies that all traffic between
given source and destination, regardless of the flow, will
down the same route. Again, the route must have capacity for all
QoS traffic for the source/destination pair. The amount of
state also increases since the routing tables must
source/destination pairs instead of just the destination

The best granularity is found when routing is based on
flows but this incurs a tremendous cost in terms of the
state. Each QoS flow can be routed separately between any source
destination. PQC [GOA97] and alternate path routing [ZES97],
examples of solutions which operate at the flow level

Both source/destination and flow-based routing may be susceptible
packet looping under hop-by-hop forwarding. Suppose a node along
flow or source/destination-based path loses the state information
the flow. Also suppose that the flow-based route is different
the regular destination-based route. The potential then exists for
routing loop to form when the node forwards a packet belonging to
flow using its destination-based routing table to a node that

Crawley, et. al. Informational [Page 8]

RFC 2386 A Framework for QoS-based Routing August 1998

earlier on the flow-based path. This is because the latter node
use its flow-based routing table to forward the packet again to
former and this can go on indefinitely

3.6 Metrics and Path

3.6.1 Metric Selection and

There are some considerations in defining suitable link and
metrics [WC96]. First, the metrics must represent the basic
properties of interest. Such metrics include residual bandwidth
delay and jitter. Since the flow QoS requirements have to be
onto path metrics, the metrics define the types of QoS guarantees
network can support. Alternatively, QoS-based routing cannot
QoS requirements that cannot be meaningfully mapped onto a
combination of path metrics. Second, path computation based on
metric or a combination of metrics must not be too complex as
render them impractical. In this regard, it is worthwhile to
that path computation based on certain combinations of metrics (e.g.,
delay and jitter) is theoretically hard. Thus, the
combinations of metrics must be determined while taking into
the complexity of computing paths based on these metrics and the
needs of flows. A common strategy to allow flexible combinations
metrics while at the same time reduce the path computation
is to utilize "sequential filtering". Under this approach,
combination of metrics is ordered in some fashion, reflecting
importance of different metrics (e.g., cost followed by delay, etc.).
Paths based on the primary metric are computed first (using a
algorithm, e.g., shortest path) and a subset of them are
based on the secondary metric and so forth until a single path
found. This is an approximation technique and it trades off
optimality for path computation simplicity (The filtering
may be simpler, depending on the set of metrics used. For example
with bandwidth and cost as metrics, it is possible to first
the set of links that do not have the requested bandwidth and
compute the least cost path using the remaining links.)

Now, once suitable link and node metrics are defined, a
representation of them is required across independent domains -
employing possibly different routing schemes - in order to
path metrics consistently (path metrics are obtained by
composition of link and node metrics). Encoding of the maximum
minimum, range, and granularity of the metrics are needed. Also,
definitions of comparison and accumulation operators are required.
addition, suitable triggers must be defined for indicating
significant change from a minor change. The former will cause
routing update to be generated. The stability of the QoS routes

Crawley, et. al. Informational [Page 9]

RFC 2386 A Framework for QoS-based Routing August 1998

depend on the ability to control the generation of updates.
interdomain routing, it is essential to obtain a fairly stable
of the interconnection among the ASs

3.6.2 Metric

A hierarchy can be defined among various classes of service based
the degree to which traffic from one class can potentially
service of traffic from lower classes that traverse the same link.
this hierarchy, guaranteed constant bit rate traffic is at the
and "best-effort" datagram traffic at the bottom. Classes
service higher in the hierarchy impact classes providing service
lower levels. The same situation is not true in the other direction
For example, a datagram flow cannot affect a real-time service. Thus
it may be necessary to distribute and update different metrics
each type of service in the worst case. But, several
result by identifying a single default metric. For example,
could derive a single metric combining the availability of
and real-time service over a common substrate

3.6.3 Datagram

A delay-sensitive metric is probably the most obvious type of
suitable for datagram flows. However, it requires careful analysis
avoid instabilities and to reduce storage and bandwidth requirements
For example, a recursive filtering technique based on a simple
efficient weighted averaging algorithm [NC94] could be used.
filter is used to stabilize the metric. While it is adequate
smoothing most loading patterns, it will not distinguish
patterns consisting of regular bursts of traffic and random loading
Among other stabilizing tools, is a minimum time between updates
can help filter out high-frequency oscillations

3.6.4 Real-time

In real-time quality-of-service, delay variation is generally
critical than delay as long as the delay is not too high. Clearly
voice-based applications cannot tolerate more than a certain level
delay. The condition of varying delays may be expected to a
degree in a shared medium environment with datagrams, than in
network implemented over a switched substrate. Routing a real-
flow therefore reduces to an exercise in allocating the
network resources while minimizing fragmentation of bandwidth.
resulting situation is a bandwidth-limited minimum hop path from
source to the destination. In other words, the router performs
ordered search through paths of increasing hop count until it
one that meets all the bandwidth needs of the flow. To
contention and the probability of false probes (due to inaccuracy

Crawley, et. al. Informational [Page 10]

RFC 2386 A Framework for QoS-based Routing August 1998

route tables), the router could select a path randomly from
"window" of paths which meet the needs of the flow and satisfy one
three additional criteria: best-fit, first-fit or worst-fit.
that there is a similarity between the allocation of bandwidth
the allocation of memory in a multiprocessing system. First-fit
to be appropriate for a system with a high real-time flow
rates; and worst-fit is ideal for real-time flows with high
times. This rather nonintuitive result was shown in [NC94].

3.6.5 Path

Path computation by itself is merely a search technique, e.g.,
Shortest Path First (SPF) is a search technique based on
programming. The usefulness of the paths computed depends to a
extent on the metrics used in evaluating the cost of a path
respect to a flow

Each link considered by the path computation engine must be
against the requirements of the flow, i.e., the cost of providing
services required by the flow must be estimated with respect to
capabilities of the link. This requires a uniform method of
features such as delay, bandwidth, priority and other
features. Furthermore, the costs must reflect the lost
of using each link after routing the flow

3.6.6 Performance

One common objective during path computation is to improve the
network throughput. In this regard, merely routing a flow on
path that accommodates its QoS requirement is not a good strategy.
fact, this corresponds to uncontrolled alternate routing [SD95]
may adversely impact performance at higher traffic loads. It
therefore necessary to consider the total resource allocation for
flow along a path, in relation to available resources, to
whether or not the flow should be routed on the path. Such
mechanism is referred to in this document as "higher level
control". The goal of this is to ensure that the "cost" incurred
the network in routing a flow with a given QoS is never more than
revenue gained. The routing cost in this regard may be the
revenue in potentially blocking other flows that contend for the
resources. The formulation of the higher level admission
strategy, with suitable administrative hooks and with fairness to
flows desiring entry to the network, is an issue. The
problem arises because flows with smaller reservations tend to
more successfully routed than flows with large reservations, for
given engineered capacity. To guarantee a certain level

Crawley, et. al. Informational [Page 11]

RFC 2386 A Framework for QoS-based Routing August 1998

acceptance rate for "larger" flows, without over-engineering
network, requires a fair higher level admission control mechanism
The application of higher level admission control to
routing is discussed later

3.7 Administrative

There are several administrative control issues. First, within an
employing state-dependent routing, administrative control of
behavior may be necessary. One example discussed earlier was
level admission control. Some others are described in this section
Second, the control of interdomain routing based on policy is
issue. The discussion of interdomain routing is defered to
5.

Two areas that need administrative control, in addition
appropriate routing mechanisms, are handling flow priority
preemption, and resource allocation for multiple service classes

3.7.1 Flow Priorities and

If there are critical flows that must be accorded higher
than other types of flows, a mechanism must be implemented in
network to recognize flow priorities. There are two aspects
prioritizing flows. First, there must be a policy to decide
different users are allowed to set priorities for flows
originate. The network must be able to verify that a given flow
allowed to claim a priority level signaled for it. Second,
routing scheme must ensure that a path with the requested QoS will
found for a flow with a probability that increases with the
of the flow. In other words, for a given network load, a
priority flow should be more likely to get a certain QoS from
network than a lower priority flow requesting the same QoS.
procedures for flow prioritization can be complex.
and evaluation of different procedures are areas that
investigation

3.7.2 Resource

If there are multiple service classes, it is necessary to engineer
network to carry the forecasted traffic demands of each class. To
this, router and link resources may be logically partitioned
various service classes. It is desirable to have dynamic
whereby unused resources in various partitions are
shifted to other partitions on demand [ACFH92]. Dynamic sharing
however, must be done in a controlled fashion in order to
traffic under some service class from taking up more resources

Crawley, et. al. Informational [Page 12]

RFC 2386 A Framework for QoS-based Routing August 1998

what was engineered for it for prolonged periods of time. The
of such a resource sharing scheme, and its incorporation into
QoS-based routing scheme are significant issues

3.8 QoS-Based Routing for Multicast

QoS-based multicast routing is an important problem, especially
the notion of higher level admission control is included.
dynamism in the receiver set allowed by IP multicast, and
heterogeneity add to the problem. With straightforward
of distributed heuristic algorithms for multicast path
[W88, C91], the difficulty is essentially one of scalability.
accommodate QoS, multicast path computation at a router must
knowledge of not only the id of subnets where group members
present, but also the identity of branches in the existing tree.
other words, routers must keep flow-specific state information. Also
computing optimal shared trees based on the shared reservation
[BZBH97], may require new algorithms. Multicast routing is
in some detail in Section 6.

3.9 Routing

The overheads incurred by a routing scheme depend on the type of
routing scheme, as well as the implementation. There are three
of overheads to be considered: computation, storage
communication. It is necessary to understand the implications
choosing a routing mechanism in terms of these overheads

For example, considering link state routing, the choice of the
propagation mechanism is important since network state is dynamic
changes relatively frequently. Specifically, a flooding
would result in many unnecessary message transmissions
processing. Alternative techniques, such as tree-based
[R96], have to be considered. A related issue is the quantization
state information to prevent frequent updating of dynamic state
While coarse quantization reduces updating overheads, it may
the performance of the routing scheme. The tradeoff has to
carefully evaluated. QoS-based routing incurs certain
during flow establishment, for example, computing a source route
Whether this overhead is disproportionate compared to the length
the sessions is an issue. In general, techniques for the
of routing-related overheads during flow establishment must
investigated. Approaches that are useful include pre-computation
routes, caching recently used routes, and TOS routing based on
in packets (e.g., the TOS field).

Crawley, et. al. Informational [Page 13]

RFC 2386 A Framework for QoS-based Routing August 1998

3.10 Scaling by Hierarchical

QoS-based routing should be scalable, and hierarchical aggregation
a common technique for scaling (e.g., [PNNI96]). But this
problems with regard to the accuracy of the aggregated
information [L95]. Also, the aggregation of paths under
constraints is difficult. One of the difficulties is the risk
accepting a flow based on inaccurate information, but not being
to support the QoS requirements of flow because the capabilities
the actual paths that are aggregated are not known during
computation. Performance impacts of aggregating path
information must therefore be understood. A way to compensate
inaccuracies is to use crankback, i.e., dynamic search for
paths as a flow is being routed. But crankback increases the time
set up a flow, and may adversely affect the performance of
routing scheme under some circumstances. Thus, crankback must be
judiciously, if at all, along with a higher level admission
mechanism

4. INTRADOMAIN ROUTING

At the intradomain level, the objective is to allow as much
as possible in addressing the QoS-based routing issues. Indeed,
are many ideas about how QoS-based routing services can
provisioned within ASs. These range from on-demand path
based on current state information, to statically provisioned
supporting a few service classes

Another aspect that might invite differing solutions is
optimization. Based on the technique used for this,
routing could be very sophisticated or rather simple. Finally,
service classes supported, as well as the specific QoS engineered
a service class, could differ from AS to AS. For instance, some
may not support guaranteed service, while others may. Also, some
supporting the service may be engineered for a better delay
than others. Thus, it requires considerable thought to determine
high level requirements for intradomain routing that both
the overall view of QoS-based routing in the Internet and
maximum autonomy in developing solutions

Our view is that certain minimum requirements must be satisfied
intradomain routing in order to be qualified as "QoS-based" routing
These are

- The routing scheme must route a flow along a path that
accommodate its QoS requirements, or indicate that the flow
be admitted with the QoS currently being requested

Crawley, et. al. Informational [Page 14]

RFC 2386 A Framework for QoS-based Routing August 1998

- The routing scheme must indicate disruptions to the current
of a flow due to topological changes

- The routing scheme must accommodate best-effort flows without
resource reservation requirements. That is, present best
applications and protocol stacks need not have to change to run
a domain employing QoS-based routing

- The routing scheme may optionally support QoS-based
with receiver heterogeneity and shared reservation styles

In addition, the following capabilities are also recommended

- Capabilities to optimize resource usage

- Implementation of higher level admission control procedures
limit the overall resource utilization by individual flows

Further requirements along these lines may be specified.
requirements should capture the consensus view of QoS-based routing
but should not preclude particular approaches (e.g., TOS-
routing) from being implemented. Thus, the intradomain
are expected to be rather broad

5. INTERDOMAIN

The fundamental requirement on interdomain QoS-based routing
scalability. This implies that interdomain routing cannot be
on highly dynamic network state information. Rather, such
must be aided by sound network engineering and relatively
information exchange between independent routing domains.
approach has the advantage that it can be realized by
extensions of the present Internet interdomain routing model.
number of issues, however, need to be addressed to achieve this,
discussed below

Crawley, et. al. Informational [Page 15]

RFC 2386 A Framework for QoS-based Routing August 1998

5.1 Interdomain QoS-Based Routing

The interdomain QoS-based routing model is depicted below

AS1 AS2 AS
___________ _____________ ____________
| | | | | |
| B------B B----B |
| | | | | |
-----B----- B------------- --B---------
\ / /
\ / /
____B_____B____ _________B______
| | | |
| B-------B |
| | | |
| B-------B |
--------------- ----------------
AS4 AS

Here, ASs exchange standardized routing information via border
B. Under this model, each AS can itself consist of a set
interconnected ASs, with standardized routing interaction. Thus,
interdomain routing model is hierarchical. Also, each lowest
AS employs an intradomain QoS-based routing scheme (proprietary
standardized by intradomain routing efforts such as QOSPF).
this structure, some questions that arise are

- What information is exchanged between ASs

- What routing capabilities does the information exchange lead to
(E.g., source routing, on-demand path computation, etc.)

- How is the external routing information represented within an AS

- How are interdomain paths computed

- What sort of policy controls may be exerted on interdomain
computation and flow routing?,

- How is interdomain QoS-based multicast routing accomplished

At a high level, the answers to these questions depend on the
paradigm. Specifically, considering link state routing,
information exchanged between domains would consist of an
representation of the domains in the form of logical nodes and links
along with metrics that quantify their properties and
availability. The hierarchical structure of the ASs may be

Crawley, et. al. Informational [Page 16]

RFC 2386 A Framework for QoS-based Routing August 1998

by a hierarchical link state representation, with appropriate
aggregation

Link state routing may not necessarily be advantageous
interdomain routing for the following reasons

- One advantage of intradomain link state routing is that it
allow fairly detailed link state information be used to
paths on demand for flows requiring QoS. The state and
aggregation used in interdomain routing, on the other hand,
this property to a great degree

- The usefulness of keeping track of the abstract topology
metrics of a remote domain, or the interconnection between
domains is not obvious. This is especially the case when the
topology and metric encoding are lossy

- ASs may not want to advertise any details of their
topology or resource availability

- Scalability in interdomain routing can be achieved only
information exchange between domains is relatively infrequent
Thus, it seems practical to limit information flow between
as much as possible

Compact information flow allows the implementation QoS-
versions of existing interdomain protocols such as BGP-4. We look
the interdomain routing issues in this context

5.2 Interdomain Information

The information flow between routing domains must enable
basic functions

1. Determination of reachability to various

2. Loop-free flow

3. Address aggregation whenever

4. Determination of the QoS that will be supported on the path to
destination. The QoS information should be relatively static
determined from the engineered topology and capacity of an
rather than ephemeral fluctuations in traffic load through
AS. Ideally, the QoS supported in a transit AS should be
to vary significantly only under exceptional circumstances,
as failures or focused overload

Crawley, et. al. Informational [Page 17]

RFC 2386 A Framework for QoS-based Routing August 1998

5. Determination, optionally, of multiple paths for a
destination, based on service classes

6. Expression of routing policies, including monetary cost, as
function of flow parameters, usage and administrative factors

Items 1-3 are already part of existing interdomain routing. Item 5
also a straightfoward extension of the current model. The
problem areas are therefore items 4 and 6.

The QoS of an end-to-end path is obtained by composing the
available in each transit AS. Thus, border routers must
determine what the locally available QoS is in order to
routes to both internal and external destinations. The
of local "AS metrics" (corresponding to link metrics in
intradomain case) should not be subject to too much dynamism. Thus
the issue is how to define such metrics and what triggers
occasional change that results in re-advertisements of routes

The approach suggested in this document is not to compute paths
on residual or instantaneous values of AS metics (which can
dynamic), but utilize only the QoS capabilities engineered
aggregate transit flows. Such engineering may be based on
knowledge of traffic to be expected from each neighboring ASs and
corresponding QOS needs. This information may be obtained based
contracts agreed upon prior to the provisioning of services. The
metric then corresponds to the QoS capabilities of the "virtual path
engineered through the AS (for transit traffic) and a
metric may be used for different neighbors. This is illustrated
the following figure

AS1 AS2 AS
___________ _____________ ____________
| | | | | |
| B------B1 B2----B |
| | | | | |
-----B----- B3------------ --B---------
\ /
\ /
____B_____B____
| |
| |
| |
| |
---------------
AS

Crawley, et. al. Informational [Page 18]

RFC 2386 A Framework for QoS-based Routing August 1998

Here, B1 may utilize an AS metric specific for AS1 when
path metrics to be advertised to AS1. This metric is based on
resources engineered in AS2 for transit traffic from AS1. Similarly
B3 may utilize a different metric when computing path metrics to
advertised to AS4. Now, it is assumed that as long as traffic
into AS2 from AS1 or AS4 does not exceed the engineered values,
path metrics would hold. Excess traffic due to
fluctuations, however, may be handled as best effort or marked with
discard bit

Thus, this model is different from the intradomain model, where
nodes pick a path dynamically based on the QoS needs of the flow
be routed. Here, paths within ASs are engineered based on presumed
measured or declared traffic and QoS requirements. Under this model
an AS can contract for routes via multiple transit ASs with
QoS requirements. For instance, AS4 above can use both AS1 and AS2
transits for same or different destinations. Also, a QoS
between one AS and another may generate another contract between
second and a third AS and so forth

An issue is what triggers the recomputation of path metrics within
AS. Failures or other events that prevent engineered
allocation should certainly trigger recomputation.
should not be triggered in response to arrival of flows within
engineered limit

5.3 Path

Path computation for an external destination at a border node
based on reachability, path metrics and local policies of selection
If there are multiple selection criteria (e.g., delay, bandwidth
cost, etc.), mutiple alternaives may have to be maintained as well
propagated by border nodes. Selection of a path from among
alternatives would depend on the QoS requests of flows, as well
policies. Path computation may also utilze any heuristics
optimizing resource usage

5.4 Flow

An important issue in interdomain routing is the amount of flow
to be processed by transit ASs. Reducing the flow state
aggregation techniques must therefore be seriously considered.
aggregation means that transit traffic through an AS is
into a few aggregated streams rather than being routed at
individual flow level. For example, an entry border router
classify various transit flows entering an AS into a few
categories, based on the egress node and QoS requirements of
flows. Then, the aggregated stream for a given traffic class may

Crawley, et. al. Informational [Page 19]

RFC 2386 A Framework for QoS-based Routing August 1998

routed as a single flow inside the AS to the exit border router.
router may then present individual flows to different neighboring
and the process repeats at each entry border router. Under
scenario, it is essential that entry border routers keep track of
resource requirements for each transit flow and apply
control to determine whether the aggregate requirement from
neighbor exceeds the engineered limit. If so, some policy must
invoked to deal with the excess traffic. Otherwise, it may be
that aggregated flows are routed over paths that have
resources to guarantee QoS for the member flows. Finally, it
possible that entry border routers at a transit AS may prefer not
aggregate flows if finer grain routing within the AS may be
efficient (e.g., to aid load balancing within the AS).

5.5 Path Cost

It is hoped that the integrated services Internet architecture
allow providers to charge for IP flows based on their
requirements. A QoS-based routing architecture can aid
distributing information on expected costs of routing flows
various destinations via different domains. Clearly, from
provider's point of view, there is a cost incurred in
QoS to flows. This cost could be a function of several parameters
some related to flow parameters, others based on policy. From
user's point of view, the consequence of requesting a particular
for a flow is the cost incurred, and hence the selection of
may be based on cost. A routing scheme can aid a provider
distributing the costs in routing to various destinations, as
function of several parameters, to other providers or to end users
In the interdomain routing model described earlier, the costs to
destination will change as routing updates are passed through
transit domain. One of the goals of the routing scheme should be
maintain a uniform semantics for cost values (or functions) as
are handled by intermediate domains. As an example, consider the
function generated by border node B1 in domain A and passed to
B2 in domain B below. The routing update may be injected into
B by B2 and finally passed to B4 in domain C by router B3. Domain
may interpret the cost value received from domain A in any way
wants, for instance, adding a locally significant component to it
But when this cost value is passed to domain C, the meaning of
must be what domain A intended, plus the incremental cost
transiting domain B, but not what domain B uses internally

Crawley, et. al. Informational [Page 20]

RFC 2386 A Framework for QoS-based Routing August 1998

Domain A Domain B Domain
____________ ___________ ____________
| | | | | |
| B1------B2 B3---B4 |
| | | | | |
------------ ----------- ------------

A problem with charging for a flow is the determination of the
when the QoS promised for the flow was not actually delivered
Clearly, when a flow is routed via multiple domains, it must
determined whether each domain delivers the QoS it declares
for traffic through it

6. QOS-BASED MULTICAST

The goals of QoS-based multicast routing are as follows

- Scalability to large groups with dynamic

- Robustness in the presence of topological

- Support for receiver-initiated, heterogeneous

- Support for shared reservation styles,

- Support for "global" admission control, i.e.,
control of resource consumption by the multicast flow

The RSVP multicast flow model is as follows. The sender of
multicast flow advertises the traffic characteristics periodically
the receivers. On receipt of an advertisement, a receiver
generate a message to reserve resources along the flow path from
sender. Receiver reservations may be heterogeneous. Other
models may be considered

The multicast routing scheme attempts to determine a path from
sender to each receiver that can accommodate the
reservation. The routing scheme may attempt to maximize
resource utilization by minimizing the total bandwidth allocated
the multicast flow, or by optimizing some other measure

6.1 Scalability, Robustness and

When addressing scalability, two aspects must be considered

1. The overheads associated with receiver discovery. This
is incurred when determining the multicast tree for
best-effort sender traffic characterization to receivers

Crawley, et. al. Informational [Page 21]

RFC 2386 A Framework for QoS-based Routing August 1998

2. The overheads associated with QoS-based multicast
computation. This overhead is incurred when flow-
state information has to be collected by a router to
QoS-accommodating paths to a receiver

Depending on the multicast routing scheme, one or both of
aspects become important. For instance, under the present RSVP model
reservations are established on the same path over which
traffic characterizations are sent, and hence there is no
computation overhead. On the other hand, under the proposed
model [ZSSC97] of multicast source routing, receiver
overheads are incurred by MOSPF [M94] receiver location broadcasts
and additional path computation overheads are incurred due to
need to keep track of existing flow paths. Scaling of QoS-
multicast depends on both these scaling issues. However,
best-effort multicasting is really not in the domain of QoS-
routing work (solutions for this are being devised by the IDMR
[BCF94, DEFV94]). QoS-based multicast routing may build on
solutions to achieve overall scalability

There are several options for QoS-based multicast routing.
source routing is one under which multicast trees are computed by
first-hop router from the source, based on sender
advertisements. The advantage of this is that it blends nicely
the present RSVP signaling model. Also, this scheme works well
receiver reservations are homogeneous and the same as the
reservation derived from sender advertisement. The disadvantages
this scheme are the extra effort needed to accommodate
reservations and the difficulties in optimizing resource
based on shared reservations

In these regards, a receiver-oriented multicast routing model
to have some advantage over multicast source routing. Under
model

1. Sender traffic advertisements are multicast over a best-
tree which can be different from the QoS-accommodating tree
sender data

2. Receiver discovery overheads are minimized by utilizing
scalable scheme (e.g., PIM, CBT), to multicast sender
characterization

3. Each receiver-side router independently computes a QoS
accommodating path from the source, based on the
reservation. This path can be computed based on unicast
information only, or with additional multicast flow-
state information. In any case, multicast path computation

Crawley, et. al. Informational [Page 22]

RFC 2386 A Framework for QoS-based Routing August 1998

broken up into multiple, concurrent nunicast path computations

4. Routers processing unicast reserve messages from
aggregate resource reservations from multiple receivers

Flow-specific state information may be limited in Step 3 to
scalability [RN98]. In general, limiting flow-specific information
making multicast routing decisions is important in any routing model
The advantages of this model are the ease with which
reservations can be accommodated, and the ability to handle
reservations. The disadvantages are the incompatibility with
present RSVP signaling model, and the need to rely on reverse
when link state routing is not used. Both multicast source
and the receiver-oriented routing model described above utilize per
source trees to route multicast flows. Another possibility is
utilization of shared, per-group trees for routing flows.
computation and usage of such trees require further work

Finally, scalability at the interdomain level may be achieved
QoS-based multicast paths are computed independently in each domain
This principle is illustrated by the QOSPF multicast source
scheme which allows independent path computation in different
areas. It is easy to incorporate this idea in the receiver-
model also. An evaluation of multicast routing strategies must
into account the relative advantages and disadvantages of
approaches, in terms of scalability features and
supported

6.2 Multicast Admission

Higher level admission control, as defined for unicast,
excessive resource consumption by flows when traffic load is high
Such an admission control strategy must be applied to multicast
when the flow path computation is receiver-oriented or sender
oriented. In essence, a router computing a path for a receiver
determine whether the incremental resource allocation for
receiver is excessive under some administratively
admission control policy. Other admission control criteria, based
the total resource consumption of a tree may be defined

7. QOS-BASED ROUTING AND RESOURCE RESERVATION

There must clearly be a well-defined interface between routing
resource reservation protocols. The nature of this interface, and
interaction between routing and resource reservation has to
determined carefully to avoid incompatibilities. The importance
this can be readily illustrated in the case of RSVP

Crawley, et. al. Informational [Page 23]

RFC 2386 A Framework for QoS-based Routing August 1998

RSVP has been designed to operate independent of the
routing scheme. Under this model, RSVP PATH messages establish
reverse path for RESV messages. In essence, this model is
compatible with QoS-based routing schemes that compute paths
receiver reservations are received. While this incompatibility can
resolved in a simple manner for unicast flows, multicast
heterogeneous receiver requirements is a more difficult case.
this, reconciliation between RSVP and QoS-based routing models
necessary. Such a reconciliation, however, may require some
to the RSVP model depending on the QoS-based routing model [ZES97,
ZSSC97, GOA97]. On the other hand, QoS-based routing schemes may
designed with RSVP compatibility as a necessary goal. How
affects scalability and other performance measures must
considered

8. SECURITY

Security issues that arise with routing in general are
maintaining the integrity of the routing protocol in the presence
unintentional or malicious introduction of information that may
to protocol failure [P88]. QoS-based routing requires
security measures both to validate QoS requests for flows and
prevent resource-depletion type of threats that can arise when
are allowed to make arbitratry resource requests along various
in the network. Excessive resource consumption by an errant
results in denial of resources to legitimate flows. While
situations may be prevented by setting up proper policy constraints
charging models and policing at various points in the network,
formalization of such protection requires work [BCCH94].

9. RELATED

"Adaptive" routing, based on network state, has a long history
especially in circuit-switched networks. Such routing has also
implemented in early datagram and virtual circuit packet networks
More recently, this type of routing has been the subject of study
the context of ATM networks, where the traffic characteristics
topology are substantially different from those of circuit-
networks [MMR96]. It is instructive to review the adaptive
methodologies, both to understand the problems encountered
possible solutions

Fundamentally, there are two aspects to adaptive, network state
dependent routing

1. Measuring and gathering network state information,
2. Computing routes based on the available information

Crawley, et. al. Informational [Page 24]

RFC 2386 A Framework for QoS-based Routing August 1998

Depending on how these two steps are implemented, a variety
routing techniques are possible. These differ in the
respects

- what state information is
- whether local or global state is
- what triggers the propagation of state
- whether routes are computed in a distributed or centralized
- whether routes are computed on-demand, pre-computed, or in
hybrid
- what optimization criteria, if any, are used in computing
- whether source routing or hop by hop routing is used,
- how alternate route choices are

It should be noted that most of the adaptive routing work has
on unicast routing. Multicast routing is one of the areas that
be prominent with Internet QoS-based routing. We treat
separately, and the following review considers only unicast routing
This review is not exhaustive, but gives a brief overview of some
the approaches

9.1 Optimization

The most common optimization criteria used in adaptive routing
throughput maximization or delay minimization. A general
of the optimization problem is the one in which the network
is maximized, given that there is a cost associated with routing
flow over a given path [MMR96, K88]. In general, global
solutions are difficult to implement, and they rely on a number
assumptions on the characteristics of the traffic being
[MMR96]. Thus, the practical approach has been to treat the
of each flow (VC, circuit or packet stream to a given destination
independently of the routing of other flows. Many such
schemes have been implemented

9.2 Circuit Switched

Many adaptive routing concepts have been proposed for circuit
switched networks. An example of a simple adaptive routing scheme
sequential alternate routing [T88]. This is a hop-by-
destination-based routing scheme where only local state
is utilized. Under this scheme, a routing table is computed for
node, which lists multiple output link choices for each destination
When a call set-up request is received by a node, it tries
output link choice in sequence, until it finds one that
accommodate the call. Resources are reserved on this link, and
call set-up is forwarded to the next node. The set-up either
the destination, or is blocked at some node. In the latter case,

Crawley, et. al. Informational [Page 25]

RFC 2386 A Framework for QoS-based Routing August 1998

set-up can be cranked back to the previous node or a
declared. Crankback allows the previous node to try an
path. The routing table under this scheme can be computed in
centralized or distributed manner, based only on the topology of
network. For instance, a k-shortest-path algorithm can be used
determine k alternate paths from a node with distinct initial
[T88]. Some mechanism must be implemented during path computation
call set-up to prevent looping

Performance studies of this scheme illustrate some of the pitfalls
alternate routing in general, and crankback in particular [A84, M86,
YS87]. Specifically, alternate routing improves the throughput
traffic load is relatively light, but adversely affects
performance when traffic load is heavy. Crankback could
degrade the performance under these conditions. In general
uncontrolled alternate routing (with or without crankback) can
harmful in a heavily utilized network, since circuits tend to
routed along longer paths thereby utilizing more capacity. This is
obvious, but important result that applies to QoS-based
routing also

The problem with alternate routing is that both direct routed (i.e.,
over shortest paths) and alternate routed calls compete for the
resource. At higher loads, allocating these resources to
routed calls result in the displacement of direct routed calls
hence the alternate routing of these calls. Therefore,
approaches have been proposed to limit the flow of alternate
calls under high traffic loads. These schemes are designed for
fully-connected logical topology of long distance telephone
(i.e., there is a logical link between every pair of nodes). In
topology, direct routed calls always traverse a 1-hop path to
destination and alternate routed calls traverse at most a 2-hop path

"Trunk reservation" is a scheme whereby on each link a
bandwidth is reserved for direct routed calls [MS91].
routed calls are allowed on a trunk as long as the remaining
bandwidth is greater than the reserved capacity. Thus,
routed calls cannot totally displace direct routed calls on a trunk
This strategy has been shown to be very effective in preventing
adverse effects of alternate routing

"Dynamic alternate routing" (DAR) is a strategy whereby
routing is controlled by limiting the number of choices, in
to trunk reservation [MS91]. Under DAR, the source first attempts
use the direct link to the destination. When blocked, the
attempts to alternate route the call via a pre-selected neighbor.
the call is still blocked, a different neighbor is selected
alternate routing to this destination in the future. The present

Crawley, et. al. Informational [Page 26]

RFC 2386 A Framework for QoS-based Routing August 1998

is dropped. DAR thus requires only local state information. Also,
"learns" of good alternate paths by random sampling and sticks
them as long as possible

More recent circuit-switched routing schemes utilize global state
select routes for calls. An example is AT&T's Real-Time
Routing (RTNR) scheme [ACFH92]. Unlike schemes like DAR, RTNR
multiple classes of service, including voice and data at fixed rates
RTNR utilizes a sophisticated per-class trunk reservation
with dynamic bandwidth sharing between classes. Also, when
routing a call, RTNR utilizes the loading on all trunks in
network to select a path. Because of the fully-connected topology
disseminating status information is simple under RTNR; each
simply exchanges status information directly with all others

From the point of view of designing QoS-based Internet
schemes, there is much to be learned from circuit-switched routing
For example, alternate routing and its control, and dynamic
sharing among different classes of traffic. It is, however,
simple to apply some of the results to a general topology
with heterogeneous multirate traffic. Work in the area of ATM
routing described next illustrates this

9.3 ATM

The VC routing problem in ATM networks presents issues similar
that encountered in circuit-switched networks. Not surprisingly,
extensions of circuit-switched routing have been proposed. The
of these routing schemes is to achieve higher throughput as
to traditional shortest-path routing. The flows considered
have a single QoS requirement, i.e., bandwidth

The first idea is to extend alternate routing with trunk
to general topologies [SD95]. Under this scheme, a distance
routing protocol is used to build routing tables at each node
multiple choices of increasing hop count to each destination. A
set-up is first routed along the primary ("direct") path.
sufficient resources are not available along this path,
paths are tried in the order of increasing hop count. A flag in
VC set-up message indicates primary or alternate routing,
bandwidth on links along an alternate path is allocated subject
trunk reservation. The trunk reservation values are determined
on some assumptions on traffic characteristics. Because the
works only for a single data rate, the practical utility of it
limited

The next idea is to import the notion of controlled alternate
into traditional link state QoS-based routing [GKR96]. To do this

Crawley, et. al. Informational [Page 27]

RFC 2386 A Framework for QoS-based Routing August 1998

first each VC is associated with a maximum permissible routing cost
This cost can be set based on expected revenues in carrying the VC
simply based on the length of the shortest path to the destination
Each link is associated with a metric that increases
with its utilization. A switch computing a path for a VC
determines a least-cost feasible path based on the link metric
the VC's QoS requirement. The VC is admitted if the cost of the
is less than or equal to the maximum permissible routing cost.
routing scheme thus limits the extent of "detour" a VC experiences
thus preventing excessive resource consumption. This is a
scheme and the basic idea can be extended to hierarchical routing
But the performance of this scheme has not been analyzed thoroughly
A similar notion of admission control based on the connection
was also incorporated in a routing scheme presented in [ACG92].

Considering the ATM Forum PNNI protocol [PNNI96], a partial list
its stated characteristics are as follows

o Scales to very large
o Supports hierarchical
o Supports
o Uses source routed connection
o Supports multiple metrics and
o Provides dynamic

The PNNI specification is sub-divided into two protocols: a
and a routing protocol. The PNNI signaling protocol is used
establish point-to-point and point to multipoint connections
supports source routing, crankback and alternate routing. PNNI
routing allows loop free paths. Also, it allows each
to use its own path computation algorithm. Furthermore,
routing is expected to support incremental deployment of
enhancements such as policy routing

The PNNI routing protocol is a dynamic, hierarchical link
protocol that propagates topology information by flooding it
the network. The topology information is the set of resources (e.g.,
nodes, links and addresses) which define the network. Resources
qualified by defined sets of metrics and attributes (delay,
bandwidth, jitter, etc.) which are grouped by supported
class. Since some of the metrics used will change frequently, e.g.,
available bandwidth, threshold algorithms are used to determine
the change in a metric or attribute is significant enough to
propagation of updated information. Other features include,
configuration of the routing hierarchy, connection admission
(as part of path calculation) and aggregation and summarization
topology and reachability information

Crawley, et. al. Informational [Page 28]

RFC 2386 A Framework for QoS-based Routing August 1998

Despite its functionality, the PNNI routing protocol does not
the issues of multicast routing, policy routing and control
alternate routing. A problem in general with link state QoS-
routing is that of efficient broadcasting of state information.
flooding is a reasonable choice with static link metrics it
impact the performance adversely with dynamic metrics

Finally, Integrated PNNI [I-PNNI] has been designed from the start
take advantage of the QoS Routing capabilities that are available
PNNI and integrate them with routing for layer 3. This would
an integrated layer 2 and layer 3 routing protocol for networks
include PNNI in the ATM core. The I-PNNI specification has
under development in the ATM Forum and, at this time, has not
incorporated QoS routing mechanisms for layer 3.

9.4 Packet

Early attempts at adaptive routing in packet networks had
objective of delay minimization by dynamically adapting to
congestion. Alternate routing based on k-shortest path tables,
route selection based on some local measure (e.g., shortest
queue) has been described [R76, YS81]. The original ARPAnet
scheme was a distance vector protocol with delay-based cost
[MW77]. Such a scheme was shown to be prone to route
[B82]. For this and other reasons, a link state delay-based
scheme was later developed for the ARPAnet [MRR80]. This
demonstrated a number of techniques such as triggered updates
flooding, etc., which are being used in OSPF and PNNI routing today
Although none of these schemes can be called QoS-based
schemes, they had features that are relevant to QoS-based routing

IBM's System Network Architecture (SNA) introduced the concept
Class of Service (COS)-based routing [A79, GM79]. There were
classes of service: interactive, batch, and network control.
addition, users could define other classes. When starting a
session an application or device would request a COS. Routing
then map the COS into a statically configured route which marked
path across the physical network. Since SNA is connection oriented
a session was set up along this path and the application's
device's data would traverse this path for the life of the session
Initially, the service delivered to a session was based on
network engineering and current state of network congestion. Later
transmission priority was added to subarea SNA.
priority allowed more important traffic (e.g. interactive) to
before less time-critical traffic (e.g. batch) and improved link
network utilization. Transmission priority of a session was based
its COS

Crawley, et. al. Informational [Page 29]

RFC 2386 A Framework for QoS-based Routing August 1998

SNA later evolved to support multiple or alternate paths
nodes. But, although assisted by network design tools, the
administrator still had to statically configure routes. IBM
introduced SNA's Advanced Peer to Peer Networking (APPN) [B85].
added new features to SNA including dynamic routing based on a
state database. An application would use COS to indicate it
requirements and APPN would calculate a path capable of meeting
requirements. Each COS was mapped to a table of acceptable
and parameters that qualified the nodes and links contained in
APPN topology Database. Metrics and parameters used as part of
APPN route calculation include, but are not limited to: delay,
per minute, node congestion and security. The dynamic nature of
allowed it to route around failures and reduce network configuration

The service delivered by APPN was still based on the
engineering, transmission priority and network congestion. IBM
introduced an extension to APPN, High Performance
(HPR)[IBM97]. HPR uses a congestion avoidance algorithm
adaptive rate based (ARB) congestion control. Using
feedback methods, the ARB algorithm prevents congestion and
network utilization. Most recently, an extension to the COS
has been defined so that HPR routing could recognize and
advantage of ATM QoS capabilities

Considering IP routing, both IDRP [R92] and OSPF support type
service (TOS)-based routing. While the IP header has a TOS field
there is no standardized way of utilizing it for TOS
and routing. It seems possible to make use of the IP TOS feature
along with TOS-based routing and proper network engineering, to
QoS-based routing. The emerging differentiated services model
generating renewed interest in TOS support. Among the newer schemes
Source Demand Routing (SDR) [ELRV96] allows on-demand
computation by routers and the implementation of strict and
source routing. The Nimrod architecture [CCM96] has a number
concepts built in to handle scalability and specialized
computation. Recently, some work has been done on QoS-based
schemes for the integrated services Internet. For example, in [M98],
heuristic schemes for efficient routing of flows with
and/or delay constraints is described and evaluated

9. SUMMARY AND

In this document, a framework for QoS-based Internet routing
defined. This framework adopts the traditional separation
intra and interdomain routing. This approach is especially
in the case of QoS-based routing, since there are many views on
QoS-based routing should be accomplished and many different needs
The objective of this document was to encourage the development

Crawley, et. al. Informational [Page 30]

RFC 2386 A Framework for QoS-based Routing August 1998

different solution approaches for intradomain routing, subject
some broad requirements, while consensus on interdomain routing
achieved. To this end, the QoS-based routing issues were described
and some broad intradomain routing requirements and an
routing model were defined. In addition, QoS-based multicast
was discussed and a detailed review of related work was presented

The deployment of QoS-based routing across multiple
domains requires both the development of intradomain routing
and a standard way for them to interact via a well-
interdomain routing mechanism. This document, while outlining
issues that must be addressed, did not engage in the specification
the actual features of the interdomain routing scheme. This would
the next step in the evolution of wide-area, multidomain QoS-
routing

[A79] V. Ahuja, "Routing and Flow Control in SNA", IBM
Journal, 18 No. 2, pp. 298-314, 1979.

[A84] J. M. Akinpelu, "The Overload Performance of
Networks with Non-Hierarchical Routing", AT&T
Journal, Vol. 63, pp. 1261-1281, 1984.

[ACFH92] G. R. Ash, J. S. Chen, A. E. Frey and B. D. Huang, "
Network Routing in a Dynamic Class-of-Service Network",
Proceedings of ITC 13, 1992.

[ACG92] H. Ahmadi, J. Chen, and R. Guerin, "Dynamic Routing and
Control in High-Speed Integrated Networks", Proceedings
ITC-13, pp. 397-403, 1992.

[B82] D. P. Bertsekas, "Dynamic Behavior of Shortest Path
Algorithms for Communication Networks", IEEE Trans. Auto
Control, pp. 60-74, 1982.

[B85] A. E. Baratz, "SNA Networks of Small Systems", IEEE JSAC
May, 1985.

[BBCD98] Black, D., Blake, S., Carlson, M., Davies, E., Wang, Z.,
W. Weiss, "An Architecture for Differentiated Services",
Work in Progress

[BCCH94] Braden, R., Clark, D., Crocker, D., and C. Huitema, "
of IAB Workshop on Security in the Internet Architecture",
RFC 1636, June 1994.

Crawley, et. al. Informational [Page 31]

RFC 2386 A Framework for QoS-based Routing August 1998

[BCF94] A. Ballardie, J. Crowcroft and P. Francis, "Core-
Trees: A Scalable Multicast Routing Protocol",
of SIGCOMM `94.

[BCS94] Braden, R., Clark, D., and S. Shenker, "Integrated
in the Internet Architecture: An Overview", RFC 1633,
1994.

[BZ92] S. Bahk and M. El Zarki, "Dynamic Multi-Path Routing and
it Compares with Other Dynamic Routing Algorithms for
Speed Wide Area Networks", Proc. SIGCOMM `92, pp. 53-64,
1992.

[BZBH97] Braden, R., Zhang, L., Berson, S., Herzog, S., and S. Jamin
"Resource ReSerVation Protocol (RSVP) -- Version 1
Functional Spec", RFC 2205, September 1997.

[C91] C-H. Chow, "On Multicast Path Finding Algorithms",
Proceedings of the IEEE INFOCOM `91, pp. 1274-1283, 1991.

[CCM96] Castineyra, I., Chiappa, J., and M. Steenstrup, "The
Routing Architecture", RFC 1992, August 1996.

[DEFV94] S. E. Deering, D. Estrin, D. Farinnacci, V. Jacobson, C-G
Liu, and L. Wei, "An Architecture for Wide-Area
Routing", Technical Report, 94-565, ISI, University
Southern California, 1994.

[ELRV96] Estrin, D., Li, T., Rekhter, Y., Varadhan, K., and D
Zappala, "Source Demand Routing: Packet Format
Forwarding Specification (Version 1)", RFC 1940, May 1996.

[GKR96] R. Gawlick, C. R. Kalmanek, and K. G. Ramakrishnan, "On-
Routing of Permanent Virtual Circuits",
Communications, March, 1996.

[GPSS98] A. Ghanwani, J. W. Pace, V. Srinivasan, A. Smith and M
Seaman, "A Framework for Providing Integrated Services
Shared and Switched IEEE 802 LAN Technologies", Work
Progress

[GM79] J. P. Gray, T. B. McNeil, "SNA Multi-System Networking",
Systems Journal, 18 No. 2, pp. 263-297, 1979.

[GOA97] Y. Goto, M. Ohta and K. Araki, "Path QoS Collection
Stable Hop-by-Hop QoS Routing", Proc. INET '97, June, 1997.

Crawley, et. al. Informational [Page 32]

RFC 2386 A Framework for QoS-based Routing August 1998

[GKOP98] R. Guerin, S. Kamat, A. Orda, T. Przygienda, and D
Williams, "QoS Routing Mechanisms and OSPF extensions",
in progress, March, 1998.

[IBM97] IBM Corp, SNA APPN - High Performance Routing
Reference, Version 2.0, SV40-1018, February 1997.

[IPNNI] ATM Forum Technical Committee. Integrated PNNI (I-PNNI) v1.0
Specification. af-96-0987r1, September 1996.

[ISI81] Postel, J., "Internet Protocol", STD 5, RFC 791,
1981.

[JMW83] J. M. Jaffe, F. H. Moss, R. A. Weingarten, "SNA Routing
Past, Present, and Possible Future", IBM Systems Journal
pp. 417-435, 1983.

[K88] F.P. Kelly, "Routing in Circuit-Switched Networks
Optimization, Shadow Prices and Decentralization", Adv
Applied Prob., pp. 112-144, March, 1988.

[L95] W. C. Lee, "Topology Aggregation for Hierarchical Routing
ATM Networks", ACM SIGCOMM Computer Communication Review
1995.

[M86] L. G. Mason, "On the Stability of Circuit-Switched
with Non-hierarchical Routing", Proc. 25th Conf. On
and Control, pp. 1345-1347, 1986.

[M98] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

[M94] Moy, J., "MOSPF: Analysis and Experience", RFC 1585,
1994.

[M98] Q. Ma, "Quality-of-Service Routing in Integrated
Networks", PhD thesis, Computer Science Department,
Mellon University, 1998.

[MMR96] D. Mitra, J. Morrison, and K. G. Ramakrishnan, "ATM
Design and Optimization: A Multirate Loss
Framework", Proceedings of IEEE INFOCOM `96, 1996.

[MRR80] J. M. McQuillan, I. Richer and E. C. Rosen, "The New
Algorithm for the ARPANET", IEEE Trans. Communications, pp
711-719, May, 1980.

Crawley, et. al. Informational [Page 33]

RFC 2386 A Framework for QoS-based Routing August 1998

[MS91] D. Mitra and J. B. Seery, "Comparative Evaluations
Randomized and Dynamic Routing Strategies for
Switched Networks", IEEE Trans. on Communications, pp. 102-
116, January, 1991.

[MW77] J. M. McQuillan and D. C. Walden, "The ARPANET
Decisions", Computer Networks, August, 1977.

[NC94] Nair, R. and Clemmensen, D. : "Routing in
Services Networks", Proc. 2nd International Conference
Telecom. Systems Modeling and Analysis, March 1994.

[P88] R. Perlman, "Network Layer Protocol with
Robustness", Ph.D. Thesis, Dept. of EE and CS, MIT, August
1988.

[PNNI96] ATM Forum PNNI subworking group, "Private Network-
Interface Spec. v1.0 (PNNI 1.0)", afpnni-0055.00,
1996.

[R76] H. Rudin, "On Routing and "Delta Routing": A Taxonomy
Performance Comparison of Techniques for Packet-
Networks", IEEE Trans. Communications, pp. 43-59, January
1996.

[R92] Y. Rekhter, "IDRP Protocol Analysis: Storage Overhead",
Comp. Comm. Review, April, 1992.

[R96] B. Rajagopalan, "Efficient Link State Routing", Work
Progress, available from braja@ccrl.nj.nec.com

[RN98] B. Rajagopalan and R. Nair, "Multicast Routing with
Reservation", to appear in J. of High Speed Networks, 1998.

[SD95] S. Sibal and A. Desimone, "Controlling Alternate Routing
General-Mesh Packet Flow Networks", Proceedings of
SIGCOMM, 1995.

[SPG97] Shenker, S., Partridge, C., and R. Guerin, "Specification
Guaranteed Quality of Service", RFC 2212, September 1997.

[T88] D. M. Topkis, "A k-Shortest-Path Algorithm for
Routing in Communications Networks", IEEE Trans
Communications, pp. 855-859, July, 1988.

[W88] B. M. Waxman, "Routing of Multipoint Connections",
JSAC, pp. 1617-1622, December, 1988.

Crawley, et. al. Informational [Page 34]

RFC 2386 A Framework for QoS-based Routing August 1998

[W97] Wroclawski, J., "Specification of the Controlled-Load
Element Service", RFC 2211, September 1997.

[WC96] Z. Wang and J. Crowcroft, "QoS Routing for
Resource Reservation", IEEE JSAC, September, 1996.

[YS81] T. P. Yum and M. Schwartz, "The Join-Based Queue Rule
its Application to Routing in Computer
Networks", IEEE Trans. Communications, pp. 505-511, 1981.

[YS87] T. G. Yum and M. Schwartz, "Comparison of Routing
for Circuit-Switched Traffic in Nonhierarchical Networks",
IEEE Trans. Communications, pp. 535-544, May, 1987.

[ZES97] Zappala, D., Estrin, D., and S. Shenker, "Alternate
Routing and Pinning for Interdomain Multicast Routing",
Computer Science Technical Report #97-655, USC, 1997.

[ZSSC97] Zhang, Z., Sanchez, C., Salkewicz, B., and E. Crawley, "
Extensions to OSPF", Work in Progress

Crawley, et. al. Informational [Page 35]

RFC 2386 A Framework for QoS-based Routing August 1998

AUTHORS'

Bala
NEC USA, C&C Research
4 Independence
Princeton, NJ 08540
U.S.

Phone: +1-609-951-2969
EMail: braja@ccrl.nj.nec.

Raj

235 Littleton Rd
Westford, MA 01886
U.S.

Phone: +1-508-692-5875, x29
EMail: nair@arrowpoint.

Hal
Bay Networks, Inc
1009 Slater Rd., Suite 220
Durham, NC 27703
U.S.

Phone: +1-919-941-1739
EMail: Hsandick@baynetworks.

Eric S.
Argon Networks, Inc
25 Porter Rd
Littelton, MA 01460
U.S.

Phone: +1-508-486-0665
EMail: esc@argon.

Crawley, et. al. Informational [Page 36]

RFC 2386 A Framework for QoS-based Routing August 1998

Full Copyright

Copyright (C) The Internet Society (1998). All Rights Reserved

This document and translations of it may be copied and furnished
others, and derivative works that comment on or otherwise explain
or assist in its implementation may be prepared, copied,
and distributed, in whole or in part, without restriction of
kind, provided that the above copyright notice and this paragraph
included on all such copies and derivative works. However,
document itself may not be modified in any way, such as by
the copyright notice or references to the Internet Society or
Internet organizations, except as needed for the purpose
developing Internet standards in which case the procedures
copyrights defined in the Internet Standards process must
followed, or as required to translate it into languages other
English

The limited permissions granted above are perpetual and will not
revoked by the Internet Society or its successors or assigns

This document and the information contained herein is provided on
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE

Crawley, et. al. Informational [Page 37]

if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.

RFC documents can be found at I.E.T.F.

Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX