Skip to main content

A Framework for QoS-based Routing in the Internet
draft-ietf-qosr-framework-05

The information below is for an old version of the document that is already published as an RFC.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 2386.
Authors Eric S. Crawley , Raj Nair , Dr. Bala Rajagopalan , Hal J. Sandick
Last updated 2013-03-02 (Latest revision 1998-05-30)
RFC stream Internet Engineering Task Force (IETF)
Intended RFC status Informational
Formats
Stream WG state (None)
Document shepherd (None)
IESG IESG state Became RFC 2386 (Informational)
Consensus boilerplate Unknown
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-ietf-qosr-framework-05
INTERNET DRAFT                          
draft-ietf-qosr-framework-05.txt                May, 27, 1998
                                                

             A Framework for QoS-based Routing in the Internet

     Eric Crawley      Raj Nair     Bala Rajagopalan  Hal Sandick
     Argon Networks    Arrowpoint   NEC USA           Bay Networks 

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. Internet Drafts 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 view the entire list of current Internet-Drafts, please check
   the "1id-abstracts.txt" listing contained in the Internet-Drafts
   Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
   (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au
   (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu
   (US West Coast). 

   Distribution of this memo is unlimited.

   This Internet Draft expires on October, 27, 1998.

                                ABSTRACT

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

1. SCOPE OF  DOCUMENT & PHILOSOPHY

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

draft-ietf-qosr-framework-05.txt                               Page 1


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

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

This approach follows the traditional separation between intra and 
interdomain routing. It allows solutions like QOSPF [GKOP98, ZSSC97], 
Integrated PNNI [IPNNI] or other schemes to be deployed for intradomain 
routing without any restriction, other than their ability to interact 
with a common, and perhaps simple, interdomain routing protocol. The need 
to develop a single, all encompassing solution to the complex problem of 
QoS-based routing is therefore obviated. As a practical matter, there are 
many different views on how QoS-based routing should be done. Much 
overall progress can be made if an opportunity exists for various ideas 
to be developed and deployed concurrently, while some consensus on the 
interdomain routing architecture is being developed.  Finally, this 
routing model is perhaps the most practical from an evolution point of 
view. It is superfluous to say that the eventual success of a QoS-based 
Internet 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, and 
describe an extension of the current interdomain routing model to support 
QoS. It is not an objective of this document to specify the details of 
intradomain QoS-based routing architectures.  This is left up to the 
various intradomain routing efforts that might follow.  Nor is it an 
objective to specify the details of the interface between reservation 
protocols such as RSVP and QoS-based routing. The specific interface 
functionality needed, however, would be clear from the intra and 
interdomain routing solutions devised.  In the intradomain area, the goal 
is to develop the basic routing requirements while allowing maximum 
freedom for the development of solutions. In the interdomain area, the 
objectives are to identify the QoS-based routing functions, and 
facilitate the development or enhancement of a routing protocol that 
allows relatively simple interaction between domains. 

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

draft-ietf-qosr-framework-05.txt                               Page 2


2.  GLOSSARY

The following glossary lists the terminology used in this document and 
an explanation of what is meant. Some of these terms may have different 
connotations, but when used in this document, their meaning is as given.
 
Alternate Path Routing : A routing technique where multiple paths, rather 
than just the shortest path, between a source and a destination are 
utilized to route traffic. One of the objectives of alternate path 
routing is to distribute load among multiple paths in the network.

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

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

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

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

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

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

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

Integrated services:  The Integrated Services model for the Internet 
defined in RFC 1633 allows for integration of QoS services with the best 
effort services of the Internet.  The Integrated Services (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 protocol for 
the Internet.

Path: A unicast or multicast path.

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

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

draft-ietf-qosr-framework-05.txt                               Page 3


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

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

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

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

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

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

3.  QOS-BASED ROUTING: BACKGROUND AND ISSUES 

3.1  Best-Effort and QoS-Based Routing
     ---------------------------------

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

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

Second, today's opportunistic routing will shift traffic from one path 
to another as soon as a "better" path is found.  The traffic will be 
shifted even if the existing path can meet the service requirements of 
the existing traffic.  If routing calculation is tied to frequently 

draft-ietf-qosr-framework-05.txt                               Page 4


changing consumable resources (e.g. available bandwidth) this change will 
happen more often and can introduce routing oscillations as traffic 
shifts back and forth between alternate paths. Furthermore, frequently 
changing routes can increase the variation in the delay and jitter experienced
by the end users. 

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

3.2 QoS-Based Routing and Resource Reservation
    ------------------------------------------

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

Consequently, QoS-based routing is usually used in conjunction with some 
form of resource reservation or resource allocation mechanism. Simple forms 
of QoS-based routing have been used in the past for Type of Service (TOS) 
routing [M91].  In the case of OSPF, a different shortest-path tree can be 
computed for each of the 8 TOS values in the IP header [ISI81]. Such 
mechanisms can be used to select specially provisioned paths but do not 
completely assure that resources are not overbooked along the path.  As long 
as strict resource management and control are not needed, mechanisms such 
as TOS-based routing are useful for separating whole classes of traffic 
over multiple routes.  Such mechanisms might work well with the emerging 
Differential Services efforts [BBCD98].

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

3.3  QoS-Based Routing: Objectives
     -----------------------------

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

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

draft-ietf-qosr-framework-05.txt                               Page 5


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

3.  Graceful performance degradation: State-dependent routing can 
    compensate for transient inadequacies in network engineering (e.g., 
    during focused overload conditions), giving better throughput and a 
    more graceful performance degradation as 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 link and  
   reserve link resources? Note that some of these links may be 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 paths 
   computed for unicast flows? 

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

-  What are the performance objectives while computing QoS-based paths?

-  What are the administrative control issues?

-  What factors affect the routing overheads?, and

-  How is scalability achieved?

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

3.4  QoS Determination and Resource Reservation 
     ------------------------------------------

To determine whether the QoS requirements of a flow can be accommodated 
on a link, a router must be able to determine the QoS available on the 
link. It is still an open issue as to how the QoS availability is 
determined for broadcast multiple access links (e.g., Ethernet). A 
related problem is the reservation of resources over 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 the 
destination of a flow is outside the ATM network, the router may have 
multiple egress choices. Furthermore, the QoS availability on the ATM 
paths to each egress point may be different. The issues then are, 

draft-ietf-qosr-framework-05.txt                               Page 6


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

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

An additional problem with resource reservation is how to determine what
resources have already been allocated to a multicast flow. The availability
of this information during path computation improves the chances of finding 
a path to add a new receiver to a multicast flow. QOSPF [ZSSC97] handles 
this problem by letting routers broadcast reserved resource information to 
other routers in their area. Alternate path routing [ZES97] deals with this 
issue by using probe messages to find a path with sufficient resources. Path 
QoS Computation (PQC) method, proposed in [GOA97], propagates bandwidth 
allocation information in RSVP PATH messages. A router receiving the PATH 
message gets an indication of the resource allocation only on those links in 
the path to itself from the source.  Allocation for the same flow on other 
remote branches of the multicast tree is not available. Thus, the PQC method 
may not be sufficient to find feasible QoS-accommodating paths to all receivers.

3.5  Granularity of Routing Decision
     -------------------------------

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

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

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

The best granularity is found when routing is based on individual flows
but this incurs a tremendous cost in terms of the routing state.  Each QoS 
flow can be routed separately between any source and destination. PQC [GOA97]

draft-ietf-qosr-framework-05.txt                               Page 7


and alternate path routing [ZES97], are examples of solutions which operate 
at the flow level.

Both source/destination and flow-based routing may be susceptible to
packet looping under hop-by-hop forwarding. Suppose a node along a flow or 
source/destination-based path loses the state information for the flow. 
Also suppose that the flow-based route is different from the regular 
destination-based route. The potential then exists for a routing loop to 
form when the node forwards a packet belonging to the flow using its
destination-based routing table to a node that occurs earlier on the 
flow-based path. This is because the latter node may use its flow-based
routing table to forward the packet again to the former and this can
go on indefinitely. 

3.6   Metrics and Path Computation
      ----------------------------

3.6.1 Metric Selection and Representation

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

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

draft-ietf-qosr-framework-05.txt                               Page 8


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

3.6.2  Metric Hierarchy

A hierarchy can be defined among various classes of service based on the 
degree to which traffic from one class can potentially degrade service of 
traffic from lower classes that traverse the same link. In this hierarchy, 
guaranteed constant bit rate traffic is at the top and "best-effort" 
datagram traffic at the bottom.  Classes providing service higher in the 
hierarchy impact classes providing service in 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 for each type of service in the 
worst case.  But, several advantages result by identifying a single 
default metric.  For example, one could derive a single metric combining 
the availability of datagram and real-time service over a common 
substrate.

3.6.3  Datagram Flows

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

3.6.4 Real-time Flows

In real-time quality-of-service, delay variation is generally more 
critical than delay as long as the delay is not too high.  Clearly, 
voice-based applications cannot tolerate more than a certain level of 
delay. The condition of varying delays may be expected to a greater 
degree in a shared medium environment with datagrams, than in a network 
implemented over a switched substrate.  Routing a real-time flow 
therefore reduces to an exercise in allocating the required network 
resources while minimizing fragmentation of bandwidth. The resulting 
situation is a bandwidth-limited minimum hop path from a source to the 
destination.  In other words, the router performs an ordered search 
through paths of increasing hop count until it finds one that meets all 
the bandwidth needs of the flow. To reduce contention and the probability 
of false probes (due to inaccuracy in route tables), the router could 
select a path randomly from a "window" of paths which meet the needs of 
the flow and satisfy one of three additional criteria: best-fit, 
first-fit or worst-fit. Note that there is a similarity between the 
allocation of bandwidth and the allocation of memory in a multiprocessing 
system. First-fit seems to be appropriate for a system with a high 
real-time flow arrival rates; and worst-fit is ideal for real-time flows 

draft-ietf-qosr-framework-05.txt                               Page 9


with high holding times.  This rather nonintuitive result was shown in 
[NC94].

3.6.5  Path Properties

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

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

3.6.6  Performance Objectives 

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

3.7   Administrative Control
      ----------------------

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

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

draft-ietf-qosr-framework-05.txt                               Page 10


3.7.1  Flow Priorities and Preemption

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

3.7.2 Resource Control 

If there are multiple service classes, it is necessary to engineer a 
network to carry the forecasted traffic demands of each class. To do 
this, router and link resources may be logically partitioned among 
various service classes. It is desirable to have dynamic partitioning 
whereby unused resources in various partitions are dynamically shifted 
to other partitions on demand [ACFH92]. Dynamic sharing, however, must 
be done in a controlled  fashion in order to prevent traffic under some 
service class from taking up more resources than what was engineered for 
it for prolonged periods of time. The design of such a resource sharing 
scheme, and its incorporation into the QoS-based routing scheme are 
significant issues. 

3.8   QoS-Based Routing for Multicast Flows 
      -------------------------------------

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

3.9    Routing Overheads 
       -----------------

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

draft-ietf-qosr-framework-05.txt                               Page 11


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

3.10   Scaling by Hierarchical Aggregation 
       -----------------------------------

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

4. INTRADOMAIN ROUTING REQUIREMENTS

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

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

draft-ietf-qosr-framework-05.txt                               Page 12


for intradomain routing that both supports the overall view of QoS-based 
routing in the Internet and allows maximum autonomy in developing 
solutions.

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

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

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

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

- The routing scheme may optionally support QoS-based multicasting 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 to limit 
  the overall resource utilization by individual flows.

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

5. INTERDOMAIN ROUTING 

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

5.1 Interdomain QoS-Based Routing Model
    -----------------------------------

The interdomain QoS-based routing model is depicted below:

draft-ietf-qosr-framework-05.txt                               Page 13


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

Here, ASs exchange standardized routing information via border nodes B. 
Under this model, each AS can itself consist of a set of interconnected 
ASs, with standardized routing interaction. Thus, the interdomain routing 
model is hierarchical.  Also, each lowest level AS employs an intradomain 
QoS-based routing scheme (proprietary or standardized by intradomain 
routing efforts such as QOSPF). Given 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 path 
  computation and flow routing?, and

- How is interdomain QoS-based multicast routing accomplished?

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

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

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

draft-ietf-qosr-framework-05.txt                               Page 14


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

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

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

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

5.2  Interdomain Information Flow
     ---------------------------- 

The information flow between routing domains must enable certain basic 
functions:

1.  Determination of reachability to various destinations

2.  Loop-free flow routes

3.  Address aggregation whenever possible

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

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

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

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

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


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

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

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

Thus, this model is different from the intradomain model, where end nodes 
pick a path dynamically based on the QoS needs of the flow to 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 different QoS 
requirements. For instance, AS4 above can use both AS1 and AS2 as 
transits for same or different destinations. Also, a QoS contract 
between one AS and another may generate another contract between the 
second and a third AS and so forth. 

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

draft-ietf-qosr-framework-05.txt                               Page 16


5.3   Path Computation
      ----------------

Path computation for an external destination at a border node is 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 as propagated by border 
nodes. Selection of a path from among many alternatives would depend on 
the QoS requests of flows, as well as policies. Path computation may also 
utilze any heuristics for optimizing resource usage. 

5.4  Flow Aggregation
     ----------------

An important issue in interdomain routing is the amount of flow state to 
be processed by transit ASs. Reducing the flow state by aggregation 
techniques must therefore be seriously considered. Flow aggregation means 
that transit traffic through an AS is classified into a few aggregated 
streams rather than being routed at the individual flow level. For 
example, an entry border router may classify various transit flows 
entering an AS into a few coarse categories, based on the egress node and 
QoS requirements of the flows.  Then, the aggregated stream for a given 
traffic class may be routed as a single flow inside the AS to the exit 
border router. This router may then present individual flows to 
different neighboring ASs and the process repeats at each entry border 
router. Under this scenario, it is essential that entry border routers 
keep track of the resource requirements for each transit flow and apply 
admission control to determine whether the aggregate requirement from any 
neighbor exceeds the engineered limit. If so, some policy must be invoked 
to deal with the excess traffic. Otherwise, it may be assumed that 
aggregated flows are routed over paths that have adequate resources to 
guarantee QoS for the member flows. Finally, it is possible that entry 
border routers at a transit AS may prefer not to aggregate flows if finer 
grain routing within the AS may be more efficient (e.g., to aid load 
balancing within the AS).

5.5   Path Cost Determination
      -----------------------

It is hoped that the integrated services Internet architecture would 
allow providers to charge for IP flows based on their QoS requirements. 
A QoS- based routing architecture can aid in distributing information on 
expected costs of routing flows to various destinations via different 
domains. Clearly, from a provider's point of view, there is a cost 
incurred in guaranteeing QoS to flows.  This cost could be a function of 
several parameters, some related to flow parameters, others based on 
policy. From a user's point of view, the consequence of requesting a 
particular QoS for a flow is the cost incurred, and hence the selection 
of providers may be based on cost. A routing scheme can aid a provider 
in distributing the costs in routing to various destinations, as a 
function of several parameters, to other providers or to end users. In 
the interdomain routing model described earlier, the costs to a 
destination will change as routing updates are passed through a transit 
domain. One of the goals of the routing scheme should be to maintain a 

draft-ietf-qosr-framework-05.txt                               Page 17


uniform semantics for cost values (or functions) as they are handled by 
intermediate domains. As an example, consider the cost function generated 
by border node B1 in domain A and passed to node B2 in domain B below. 
The routing update may be injected into domain B by B2 and finally passed 
to B4 in domain C by router B3. Domain B may interpret the cost value 
received from domain A in any way it wants, for instance, adding a 
locally significant component to it.  But when this cost value is passed 
to domain C, the meaning of it must be what domain A intended, plus the 
incremental cost of transiting domain B, but not what domain B uses 
internally.

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

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

6. QOS-BASED MULTICAST ROUTING

The goals of QoS-based multicast routing are as follows:

- Scalability to large groups with dynamic membership

- Robustness in the presence of topological changes

- Support for receiver-initiated, heterogeneous reservations

- Support for shared reservation styles, and

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

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

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

draft-ietf-qosr-framework-05.txt                               Page 18


6.1   Scalability, Robustness and Heterogeneity
      -----------------------------------------

When addressing scalability, two aspects must be considered:

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

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

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

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

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

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

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

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

draft-ietf-qosr-framework-05.txt                               Page 19


     multicast path computation is broken up into multiple, concurrent 
     unicast path computations.

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

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

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

6.2    Multicast Admission Control
       ---------------------------

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

7.    QOS-BASED ROUTING AND RESOURCE RESERVATION PROTOCOLS 

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

RSVP has been designed to operate independent of the underlying routing 
scheme. Under this model, RSVP PATH messages establish the reverse path 
for RESV messages.  In essence, this model is not compatible with 
QoS-based routing schemes that compute paths after receiver reservations 

draft-ietf-qosr-framework-05.txt                               Page 20 


are received. While this incompatibility can be resolved in a simple 
manner for unicast flows, multicast with heterogeneous receiver 
requirements is a more difficult case.  For this, reconciliation between 
RSVP and QoS-based routing models is necessary. Such a reconciliation, 
however, may require some changes to the RSVP model depending on the 
QoS-based routing model [ZES97, ZSSC97, GOA97]. On the other hand, 
QoS-based routing schemes may be designed with RSVP compatibility as a 
necessary goal. How this affects scalability and other performance 
measures must be considered. 

8. RELATED WORK 

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

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

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

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

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

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

8.1 Optimization Criteria
    ---------------------

The most common optimization criteria used in adaptive routing is 
throughput maximization or delay minimization. A general formulation of 
the optimization problem is the one in which the network revenue is 
maximized, given that there is a cost associated with routing a flow over 
a given path [MMR96, K88]. In general, global optimization solutions are 

draft-ietf-qosr-framework-05.txt                               Page 21


difficult to implement, and they rely on a number of assumptions on the 
characteristics of the traffic being routed [MMR96]. Thus, the practical 
approach has been to treat the routing of each flow (VC, circuit or 
packet stream to a given destination) independently of the routing of 
other flows. Many such routing schemes have been implemented.

8.2  Circuit Switched Networks
     -------------------------

Many adaptive routing concepts have been proposed for circuit-switched 
networks. An example of a simple adaptive routing scheme is sequential 
alternate routing [T88]. This is a hop-by-hop destination-based routing 
scheme where only local state information is utilized.  Under this 
scheme, a routing table is computed for each node, which lists multiple 
output link choices for each destination. When a call set-up request is 
received by a node, it tries each output link choice in sequence, until 
it finds one that can accommodate the call. Resources are reserved on 
this link, and the call set-up is forwarded to the next node. The set-up 
either reaches the destination, or is blocked at some node. In the latter 
case, the set-up can be cranked back to the previous node or a failure 
declared. Crankback allows the previous node to try an alternate path. 
The routing table under this scheme can be computed in a centralized or 
distributed manner, based only on the topology of the network. For 
instance, a k-shortest-path algorithm can be used to determine k 
alternate paths from a node with distinct initial links [T88]. Some 
mechanism must be implemented during path computation or call set-up to 
prevent looping.

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

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

"Trunk reservation" is a scheme whereby on each link a certain bandwidth 
is reserved for direct routed calls [MS91]. Alternate routed calls are 
allowed on a trunk as long as the remaining trunk bandwidth is greater 

draft-ietf-qosr-framework-05.txt                               Page 22 


than the reserved capacity. Thus, alternate routed calls cannot totally 
displace direct routed calls on a trunk. This strategy has been shown to 
be very effective in preventing the adverse effects of alternate routing. 

"Dynamic alternate routing" (DAR) is a strategy whereby alternate routing 
is controlled by limiting the number of choices, in addition to trunk 
reservation [MS91]. Under DAR, the source first attempts to use the 
direct link to the destination. When blocked, the source attempts to 
alternate route the call via a pre-selected neighbor. If the call is still 
blocked, a different neighbor is selected for alternate routing to this 
destination in the future. The present call is dropped. DAR thus requires 
only local state information. Also, it "learns" of good alternate paths 
by random sampling and sticks to them as long as possible.

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

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

8.3 ATM Networks
    ------------

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

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

draft-ietf-qosr-framework-05.txt                               Page 23 


The next idea is to import the notion of controlled alternate routing into 
traditional link state QoS-based routing [RSR95, GKR96]. To do this, first 
each VC is associated with a maximum permissible routing cost. This cost 
can be set based on expected revenues in carrying the VC or simply based 
on the length of the shortest path to the destination. Each link is 
associated with a metric that increases exponentially with its 
utilization. A switch computing a path for a VC simply determines a least-
cost feasible path based on the link metric and the VC's QoS requirement. 
The VC is admitted if the cost of the path is less than or equal to the 
maximum permissible routing cost. This routing scheme thus limits the 
extent of "detour" a VC experiences, thus preventing excessive resource 
consumption. This is a practical 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 route was also incorporated in a routing scheme 
presented in [ACG92].

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

         o   Scales to very large networks
         o   Supports hierarchical routing
         o   Supports QoS
         o   Uses source routed connection setup
         o   Supports multiple metrics and attributes
         o   Provides dynamic routing

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

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

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

draft-ietf-qosr-framework-05.txt                               Page 24 


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

8.4   Packet Networks
      ---------------

Early attempts at adaptive routing in packet networks had the objective of 
delay minimization by dynamically adapting to network congestion.  
Alternate routing based on k-shortest path tables, with route selection 
based on some local measure (e.g., shortest output queue) has been 
described [R76, YS81]. The original ARPAnet routing scheme was a distance 
vector protocol with delay-based cost metric [MW77]. Such a scheme was 
shown to be prone to route oscillations [B82]. For this and other reasons, 
a link state delay-based routing scheme was later developed for the 
ARPAnet [MRR80]. This scheme 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 
routing schemes, they had features that are relevant to QoS-based routing.

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

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

draft-ietf-qosr-framework-05.txt                               Page 25 


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

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

9. SUMMARY AND CONCLUSIONS

In this document, a framework for QoS-based Internet routing was defined. 
This framework adopts the traditional separation between intra and 
interdomain routing. This approach is especially meaningful in the case 
of QoS-based routing, since there are many views on how QoS-based routing 
should be accomplished and many different needs. The objective of this 
document was to encourage the development of different solution 
approaches for intradomain routing, subject to some broad requirements, 
while consensus on interdomain routing is achieved. To this end, the QoS-
based routing issues were described, and some broad intradomain routing 
requirements and an interdomain routing model were defined. In addition, 
QoS-based multicast routing was discussed and a detailed review of 
related work was presented. 

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

draft-ietf-qosr-framework-05.txt                               Page 26 


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

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

[ACFH92] G. R. Ash, J. S. Chen, A. E. Frey and B. D. Huang, "RealTime 
         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 Call 
         Control in High-Speed Integrated Networks," Proceedings of 
         ITC-13, pp. 397-403, 1992. 

[B82]    D. P. Bertsekas, "Dynamic Behavior of Shortest Path Routing 
         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] D. Black, S. Blake, M. Carlson, E. Davies, Z. Wang, and W. Weiss,
         "An Architecture for Differentiated Services," work in progress, 
         May, 1998.

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

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

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

[BZBH97] R. Braden, L. Zhang, S. Berson, S. Herzog, 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]  I. Castineyra, J. N. Chiappa, and M. Steenstrup, "The Nimrod 
         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 Multicast Routing," 
         Technical Report, 94-565, ISI, University of Southern California, 
         1994.

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

draft-ietf-qosr-framework-05.txt                               Page 27 


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

[GPSS98] A. Ghanwani, J. W. Pace, V. Srinivasan, A. Smith and M. Seaman, 
         "A Framework for Providing Integrated Services over Shared and 
         Switched IEEE 802 LAN Technologies," work in progress, March, 
         1998.

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

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

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

[IBM97]  IBM Corp, SNA APPN - High Performance Routing Architecture 
         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]  USC-ISI, "Internet Protocol," RFC 791, September, 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 in 
         ATM Networks," ACM SIGCOMM Computer Communication Review, 1995.

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

[M91]    J. Moy, "OSPF Version 2," RFC 1247, July, 1991

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

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

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

draft-ietf-qosr-framework-05.txt                               Page 28 


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

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

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

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

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

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

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

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

[RSR95]  B. Rajagopalan, R. Srikant and K. G. Ramakrishnan, "An 
         Efficient ATM VC Routing Scheme," Draft, 1995 
         (Available from braja@ccrl.nj.nec.com)

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

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

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

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

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

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

draft-ietf-qosr-framework-05.txt                               Page 29 


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

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

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

[ZSSC97] Z. Zhang, C. Sanchez, B. Salkewicz, and E. Crawley, "QoS 
         Extensions to OSPF," work in progress, September, 1997.

AUTHORS' ADDRESSES

   Bala Rajagopalan                          Raj Nair
   NEC USA, C&C Research Labs                Arrowpoint
   4 Independence Way                        235 Littleton Rd.
   Princeton, NJ 08540                       Westford, MA 01886
   U.S.A                                     U.S.A
   Ph: +1-609-951-2969                       Ph: +1-508-692-5875, x29
   Email: braja@ccrl.nj.nec.com              Email: nair@arrowpoint.com

   Hal Sandick                               Eric S. Crawley
   Bay Networks, Inc.                        Argon Networks, Inc.
   1009 Slater Rd., Suite 220                25 Porter Rd.
   Durham, NC 27703                          Littelton, MA 01460
   U.S.A                                     U.S.A
   Ph: +1-919-941-1739                       Ph: +1-508-486-0665
   Email: Hsandick@baynetworks.com           Email: esc@argon.com

        ***** This draft expires on October, 27, 1998  *****

draft-ietf-qosr-framework-05.txt                               Page 30