home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Internet Info 1997 December
/
Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso
/
drafts
/
draft_ietf_q_t
/
draft-ietf-qosr-framework-00.txt
< prev
next >
Wrap
Text File
|
1997-03-25
|
72KB
|
1,475 lines
INTERNET DRAFT
draft-ietf-qosr-framework-00.txt March, 21, 1996
A Framework for QoS-based Routing in the Internet
Eric Crawley Raj Nair Bala Rajagopalan Hal Sandick
Bay Networks Ascom Nexion NEC USA IBM
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 learn the current status of any Internet Draft, please check the
1id-abstracts.txt listing contained in the Internet Drafts Shadow
Directories on ds.internic.net, nic.nordu.net, ftp.nisc.sri.com or
munnari.oz.au.
Distribution of this memo is unlimited.
This Internet Draft expires on September, 26, 1997.
ABSTRACT
QoS-based routing is being recognized as the missing piece in the evolution
of QoS-based service offerings in the Internet. This document describes
some of the QoS-based routing issues and proposes a framework for QoS-based
routing in the Internet.
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 might be best to employ the following
two-pronged approach be towards its development:
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. Specify simple, consistent and stable interactions between ASs implementing
routing solutions developed as above.
draft-ietf-qosr-framework-00.txt [Page 1]
This approach follows the traditional separation between intra and interdomain
routing. It allows solutions like QOSPF [GOW96, ZSSC96], 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.
The aim of this draft is to describe the QoS-based routing issues, begin
identifying the basic requirements on intra and interdomain routing, and
describe a model for interdomain routing. It is not an objective of this draft
to dictate 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 how particular signaling protocols such
as RSVP should interact with QoS-based routing. The specific interactions
needed,
however, would be clear from the intra and interdomain routing solutions
devised.
In the intradomain area, the goal is to develop consensus on the basic routing
requirements while allowing maximum freedom for the development of solutions. In
the interdomain area, the objectives are to begin identifying the QoS-based
routing functions, and facilitate the development of a routing protocol that
allows relatively simple interaction between domains. The views presented in
this draft are expected to evolve as consensus emerges on Internet-wide
QoS- based
routing needs.
In the next section, a glossary of relevant terminology is given. In Section 3,
the objectives of QoS-based routing are described and past work in related areas
is reviewed. The issues that must be dealt with by QoS-based Internet routing
efforts are briefly outlined in Section 4. In Section 5, a start is made in
defining the intradomain routing requirements. These requirements are
purposely broad, putting few constraints on solution approaches. The
interdomain routing model and issues are described in Section 6. Among topics
that deserve special attention are routing metrics and path computation, and
multicast routing. These are discussed in Sections 7 and 8, respectively. The
interaction between QoS-based routing and signaling is briefly considered in
Section 9. Finally, summary and conclusions are presented in Section 10.
2. GLOSSARY
The following glossary lists the terminology used in this draft and an
explanation
of what is meant. Some of these terms may have different connotations, but when
used in this draft, 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 intradomain routing
protocol and administrative authority.
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.
draft-ietf-qosr-framework-00.txt [Page 2]
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 [W96] and Guaranteed Service [SPG97].
RSVP: The ReSerVation Protocol [BZBH96]. 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.
Flow set-up: The act of determining the path for a flow, and attempting to
establish state in routers along the flow path to satisfy its QoS requirement.
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 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.
draft-ietf-qosr-framework-00.txt [Page 3]
3. BACKGROUND
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.
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].
"Adaptive" routing, which has similar goals as above, 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.
3.1 Related Work
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.
draft-ietf-qosr-framework-00.txt [Page 4]
3.1.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
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.
3.1.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 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.
draft-ietf-qosr-framework-00.txt [Page 5]
"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.
3.1.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.
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
draft-ietf-qosr-framework-00.txt [Page 6]
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.
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.
3.1.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,
draft-ietf-qosr-framework-00.txt [Page 7]
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.
Subarea 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 applications 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.
The service delivered by APPN was still based on the network engineering,
transmission priority and network congestion. Then in 1995 IBM introduced
an extension to APPN, High Performance Routing (HPR)[IBM97]. HPR uses
a highly responsive 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. 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.
4. QOS-BASED ROUTING ISSUES
Based on the discussion so far, we can identify a number of issues with
regard to QoS-based Internet routing. While some of these are general
concerns with any QoS-based routing scheme, others are specific to the
Internet environment:
draft-ietf-qosr-framework-00.txt [Page 8]
- 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 routing metrics are used and how is flow admission control done?
- What is the granularity of routing decision (i.e., destination-based, source
and destination-based, or flow-based)?
- With flow-based routing, how are QoS-accommodating paths computed by
routers for unicast flows?
- How are QoS-accommodating paths computed for multicast flows with different
reservation styles and receiver heterogeneity?
- What are the administrative control issues?
- What factors affect the routing overheads?, and
- What are the scalability issues?
Some of these issues are discussed briefly next. Metrics and path
computation is
discussed in Section 7 and interdomain routing is discussed in Section 6.
4.1 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. The ISSLL working group and the IEEE
802.1 group are attempting to resolve these issues.
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,
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 with some complexity.
4.2 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 destination. This set of routing
granularities presents a problem for QoS routing solutions.
draft-ietf-qosr-framework-00.txt [Page 9]
If routing based only on destination address is considered, then all
flows between any source and the destination will be routed over the
same path. This is fine if the path has adequate capacity but it can
be a problem if there are multiple flows to a destination that exceed
the capacity of the link.
One version of QOSPF [ZSSC96] 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 is also increased
since the routing tables must include source/destination pairs instead
of just destination. This amount of state increases rapidly as the
traditional routes are summarized.
The best granularity is found when routing is based on individual flows
but this has a tremendous cost for routing state. Each QoS flow can be
routed separately between any source and destination. Use of the IPv6
flow label can help in identifying or classifying flows.
Both source/destination and flow based routing also have a dangerous
property when it comes to route loop detection. If a node along a flow
or source/destination based path loses the state information for the
flow and the flow based route is different from the destination only
based routing, the potential exists for a route loop to form when the
node forwards the packet based on destination routing towards a node
earlier on the path.
4.3 Unicast Flow Path Computation Algorithms
With flow-based routing, how should paths be computed for unicast flows? The
answer to this question depends on the performance objectives of a QoS-based
routing scheme. One common objective 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 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 draft 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 interesting 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.
Path computation with multiple QoS constraints on a flow is a difficult
problem [WC96]. The determination of allowable combination of QoS
parameters, the performance objectives, and algorithms for path computation
based on these are issues that must be addressed by the routing scheme.
draft-ietf-qosr-framework-00.txt [Page 10]
4.4 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 6.
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.
4.4.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.
4.4.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.
4.5 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 [BZBH96], may require
new algorithms. Multicast routing is discussed in some detail in Section 8.
draft-ietf-qosr-framework-00.txt [Page 11]
4.6 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.
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).
4.7 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 as discussed before, 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, along with a higher level admission control mechanism.
5. 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 for intradomain routing that both supports the overall view
of QoS-based routing in the Internet and allows maximum autonomy in developing
solutions.
draft-ietf-qosr-framework-00.txt [Page 12]
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
signaling requirement. 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 should support QoS-based multicasting with receiver
heterogeneity and shared reservation styles.
- Etc.
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.
- Etc.
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.
6. INTERDOMAIN ROUTING
The interdomain routing model is depicted below.
AS1 AS2 AS3
___________ _____________ ____________
| | | | | |
| B------B B----B |
| | | | | |
-----B----- B------------- --B---------
\ / /
\ / /
____B_____B____ _________B______
| | | |
| B-------B |
| | | |
| B-------B |
--------------- ----------------
AS4 AS5
draft-ietf-qosr-framework-00.txt [Page 13]
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. Finally, 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 the link state routing paradigm, 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 is not necessarily 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.
- 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 may also allow the implementation QoS-enhanced versions
of traditional interdomain protocols such as IDRP.
While limiting the information flow between domains results in routing
simplicity and scalability, the information exchanged must enable certain
basic functions:
draft-ietf-qosr-framework-00.txt [Page 14]
- determination of reachability to various destinations
- loop-free flow routes
- address aggregation when possible
- 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.
- determination, optionally, of multiple paths for a given destination,
based on
service classes.
- expression of routing policies, including monetary cost, as a function
of flow
parameters, usage and administrative factors.
These capabilities may be realized using a QoS-based path vector, link state
or some other interdomain routing scheme. With any interdomain routing scheme
the exact nature of the QoS and policy information exchanged between domains,
as well as triggers for changes in interdomain routes and QoS indications,
are to
be determined. The next section discusses some general issues with metrics and
path computation. This discussion is relevant to both intra and interdomain
routing.
7. METRICS AND PATH COMPUTATION
7.1 Background
Routing a flow represents the intent to use a collection of resources that
could
be distributed throughout the network. Most of these resources are usually
concentrated along the path of the flow. Consequently, it is important to
determine the path of a flow with the least impact on network performance by
considering flow attributes such as priority, level of guaranteed service and
possibly the estimated life of the connection. When signaling is involved,
these needs have to be communicated to the router through a well-defined
interface with the upper-layer software. The use of suitable metrics will
ensure that the computed paths are both consistent with the requirements of the
flow and those of the network.
To allow a consistent interpretation of the metrics, a uniform representation of
common metrics such a delay, residual bandwidth, etc., is required.
Encoding of the maximum, minimum, range, and granularity 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 an update to be
generated. The stability of the QoS routes would depend on the ability to
control the generation of updates. It is essential to obtain a fairly
stable view
of the interconnection among the routing domains.
Two classes of allocation schemes must be considered: link-by-link and path-
by-path. The former refers to policies that consider a link in isolation to the
rest of the network. The latter optimizes allocation of resources along an
entire path with respect to the entire network or subnetwork.
draft-ietf-qosr-framework-00.txt [Page 15]
A link-by-link scheme implies that the traffic characteristics of a flow does
not significantly impact route selection. This is valid for bursty traffic
streams where individual bursts are not correlated to each other significantly.
While this may be true for LAN-interconnections, this condition does not
apply to real-time traffic such as voice/video where traffic streams exhibit a
high degree of auto-correlation.
In the rest of this discussion on metrics, we refer to terms such as "link" and
"trunk" in a generic way that would include both physical and logical links.
7.2 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.
7.3 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.
7.4 Datagram Flows
A delay-sensitive metric is the 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,
we could use a recursive filtering technique that is based on a simple and
efficient weighted averaging algorithm [NC94]. 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.
7.5 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
draft-ietf-qosr-framework-00.txt [Page 16]
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 with high holding times.
This rather nonintuitive result was shown in [NC94].
7.6 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 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.
In addition to this, the routing cost for a flow has to capture the effects of
different classes of service supported on the path taken by a flow. That is, a
flow may be routed on a link supporting multiple COS. How resources are
reserved for and shared among various flows on the link should be reflected
draft-ietf-qosr-framework-00.txt [Page 17]
on the cost of using the link. Specifically, the interactions between the new
flow and the existing flows (or future flows where appropriate) on the link
should be accounted for. For example, a new real-time flow of priority K over
a trunk may impact existing real-time flows of lower priority sharing the
same trunk. The lower priority flows are impacted, for instance, if they get
preempted in order to route the higher priority flow. Or, flows may
sometimes experience worse QoS than originally contracted at setup time.
8. 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.
One possible 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. However, this
model corresponds to the present RSVP signaling model.
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.
8.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 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 [ZSSC96] 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.
draft-ietf-qosr-framework-00.txt [Page 18]
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 IDMR
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, 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 some thought.
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.
8.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 to/ 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.
draft-ietf-qosr-framework-00.txt [Page 19]
9. QOS-BASED ROUTING AND SIGNALING
There must clearly be a well-defined interface between routing and
signaling. The
nature of this interface, and the interaction between routing and signaling has
to be determined through joint work by the routing and signaling efforts.
Lack of
proper coordination could result in incompatibilities. 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 are received. The
receiver-
oriented multicast routing model described above is an example. Clearly,
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. 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. Thus, the
issue of
routing-signaling interaction can be quite involved.
10. SUMMARY AND CONCLUSIONS
In this draft, a framework for QoS-based Internet routing was defined. This
framework emphasizes 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 draft
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, a start was made on defining
the intradomain routing requirements and the interdomain routing
philosophy. Two areas that are particularly important for both intra and
interdomain routing, metrics and path computation, and QoS-based multicast
routing, were discussed in some detail. A detailed review of related work and
QoS-based routing issues was also presented.
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.
draft-ietf-qosr-framework-00.txt [Page 20]
[B85] A. E. Baratz, "SNA Networks of Small Systems", IEEE Journal on Selected
Areas in Communications, May 1985.
[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," Proceedings of SIGCOMM `92, pp. 53-64, 1992.
[BZBH96] R. Braden, L. Zhang, S. Berson, S. Herzog, S. Jamin. Resource
ReSerVation Protocol (RSVP) -- Version 1 Functional Specification.
Internet Draft, draft-ietf-rsvp-spec-14. November, 1996.
[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," Internet Draft, draft-ietfnimrod-routing-arch-01.txt,
Febrauary, 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 Specification
(Version 1),"
RFC 1940, May, 1996.
[GKR96] R. Gawlick, C. R. Kalmanek, and K. G. Ramakrishnan, "On-Line Routing
of Permanent Virtual Circuits," Computer Communications, March, 1996.
[GM79] J. P. Gray, T. B. McNeil, "SNA Multi-System Networking," IBM Systems
Journal, 18 No. 2, pp. 263-297, 1979.
[GOW96] R. Guerin, A. Orda and D. Williams, "QoS Routing Mechanisms and OSPF
extensions," Internet Draft, draft-guerin-qos-routing-ospf-00.txt,
November, 1996.
[SPG97] S. Shenker, C. Partridge, R. Guerin. Specification of Guaranteed
Quality
of Service. Internet Draft draft-ietf-intserv-guaranteed-svc-07.txt,
February 1997.
[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.
[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.
draft-ietf-qosr-framework-00.txt [Page 21]
[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.
[M94] J. Moy, "MOSPF: Analysis and Experience," RFC 1585, March, 1994.
[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.
[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 Telecommunications 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 `95, 1995.
[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.
[W96] J. Wroclawski. Specification of the Controlled-Load Network Element
Service. Internet Draft, draft-ietf-intserv-ctrl-load-svc-04.txt,
November 1996.
[WC96] Z. Wang and J. Crowcroft, "QoS Routing for Supporting Resource
Reservation," available at
http://boom.cs.ucl.ac.uk/staff/zwang/pub.htm.
draft-ietf-qosr-framework-00.txt [Page 22]
[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.
[ZSSC96] Z. Zhang, C. Sanchez, B. Salkewicz, and E. Crawley, "QoS Extensions to
OSPF," Internet Draft, draft-zhang-qos-ospf-00.txt, June, 1996.
AUTHORS' ADDRESSES
Bala Rajagopalan Raj Nair
NEC USA, C&C Research Labs Ascom Nexion
4 Independence Way 289 Great Rd.
Princeton, NJ 08540 Acton, MA 01720
U.S.A U.S.A
Ph: +1-609-951-2969 Ph: +1-508-266-4536
Email: braja@ccrl.nj.nec.com Email: nair@nexen.com
Hal Sandick Eric S. Crawley
IBM ND, E95/B664 Bay Networks Inc.
800 Park Offices Drive 3 Federal Street, BL3-04
RTP, NC 27705 Billerica, MA 01821
U.S.A U.S.A
Ph: +1-919-254-4614 Ph: +1-508-670-8888
Email: sandick@vnet.ibm.com Email: esc@baynetworks.com
******* This draft expires on September, 26, 1997 ********
draft-ietf-qosr-framework-00.txt [Page 23]