the higher priority packets, the lower priority class can be
completely prevented from being sent.
An alternative scheduling scheme is round-robin or some
variant, which gives different classes of packets access to a
share of the link. A variant called Weighted Fair Queueing, or
WFQ, has been demonstrated to allocate the total bandwidth of a
link into specified shares.
There are more complex schemes for queue management, most of
which involve observing the service objectives of individual
packets, such as delivery deadline, and ordering packets based
on these criteria.
4.1.2 Packet Dropping
The controlled dropping of packets is as important as their
scheduling.
Most obviously, a router must drop packets when its buffers are
all full. This fact, however, does not determine which packet
should be dropped. Dropping the arriving packet, while simple,
may cause undesired behavior.
In the context of today's Internet, with TCP operating over
best effort IP service, dropping a packet is taken by TCP as a
signal of congestion and causes it to reduce its load on the
network. Thus, picking a packet to drop is the same as picking
a source to throttle. Without going into any particular
algorithm, this simple relation suggests that some specific
dropping controls should be implemented in routers to improve
congestion control.
In the context of real-time services, dropping more directly
relates to achieving the desired quality of service. If a
queue builds up, dropping one packet reduces the delay of all
the packets behind it in the queue. The loss of one can
contribute to the success of many. The problem for the
implementor is to determine when the service objective (the
delay bound) is in danger of being violated. One cannot look
at queue length as an indication of how long packets have sat
in a queue. If there is a priority scheme in place, packets of
lower priority can be pre-empted indefinitely, so even a short
queue may have very old packets in it. While actual time
stamps could be used to measure holding time, the complexity
may be unacceptable.
Some simple dropping schemes, such as combining all the buffers
in a single global pool, and dropping the arriving packet if
the pool is full, can defeat the service objective of a WFQ
scheduling scheme. Thus, dropping and scheduling must be
coordinated.
4.1.3 Packet Classification
The above discussion of scheduling and dropping presumed that
the packet had been classified into some flow or sequence of
packets that should be treated in a specified way. A
preliminary to this sort of processing is the classification
itself. Today a router looks at the destination address and
selects a route. The destination address is not sufficient to
select the class of service a packet must receive; more
information is needed.
One approach would be to abandon the IP datagram model for a
virtual circuit model, in which a circuit is set up with
specific service attributes, and the packet carries a circuit
identifier. This is the approach of ATM as well as protocols
such as ST-II [ST2-90]. Another model, less hostile to IP, is
to allow the classifier to look at more fields in the packet,
such as the source address, the protocol number and the port
fields. Thus, video streams might be recognized by a
particular well-known port field in the UDP header, or a
particular flow might be recognized by looking at both the
source and destination port numbers. It would be possible to
look even deeper into the packets, for example testing a field
in the application layer to select a subset of a
hierarchically-encoded video stream.
The classifier implementation issues are complexity and
processing overhead. Current experience suggests that careful
implementation of efficient algorithms can lead to efficient
classification of IP packets. This result is very important,
since it allows us to add QoS support to existing applications,
such as Telnet, which are based on existing IP headers.
One approach to reducing the overhead of classification would
be to provide a "flow-id" field in the Internet-layer packet
header. This flow-id would be a handle that could be cached
and used to short-cut classification of the packet. There are
a number of variations of this concept, and engineering is
required to choose the best design.
4.1.4 Admission Control
As we stated in the introduction, real-time service depends on
setting up state in the router and making commitments to
certain classes of packets. In order to insure that these
commitments can be met, it is necessary that resources be
explicitly requested, so that the request can be refused if the
resources are not available. The decision about resource
availability is called admission control.
Admission control requires that the router understand the
demands that are currently being made on its assets. The
approach traditionally proposed is to remember the service
parameters of past requests, and make a computation based on
the worst-case bounds on each service. A recent proposal,
which is likely to provide better link utilization, is to
program the router to measure the actual usage by existing
packet flows, and to use this measured information as a basis
of admitting new flows [JCSZ92]. This approach is subject to
higher risk of overload, but may prove much more effective in
using bandwidth.
Note that while the need for admission control is part of the
global service model, the details of the algorithm run in each
router is a local matter. Thus, vendors can compete by
developing and marketing better admission control algorithms,
which lead to higher link loadings with fewer service
overloads.
4.2 Applying the Mechanisms
The various tools described above can be combined to support the
services which were discussed in section 3.
o Guaranteed delay bounds
A theoretical result by Parekh [Parekh92] shows that if the
router implements a WFQ scheduling discipline, and if the
nature of the traffic source can be characterized (e.g. if it
fits within some bound such as a token bucket) then there
will be an absolute upper bound on the network delay of the
traffic in question. This simple and very powerful result
applies not just to one switch, but to general networks of
routers. The result is a constructive one; that is, Parekh
displays a source behavior which leads to the bound, and then
shows that this behavior is the worst possible. This means
that the bound he computes is the best there can be, under
these assumptions.
o Link sharing
The same WFQ scheme can provide controlled link sharing. The
service objective here is not to bound delay, but to limit
overload shares on a link, while allowing any mix of traffic
to proceed if there is spare capacity. This use of WFQ is
available in commercial routers today, and is used to
segregate traffic into classes based on such things as
protocol type or application. For example, one can allocate
separate shares to TCP, IPX and SNA, and one can assure that
network control traffic gets a guaranteed share of the link.
o Predictive real-time service
This service is actually more subtle than guaranteed service.
Its objective is to give a delay bound which is, on the one
hand, as low as possible, and on the other hand, stable
enough that the receiver can estimate it. The WFQ mechanism
leads to a guaranteed bound, but not necessarily a low bound.
In fact, mixing traffic into one queue, rather than
separating it as in WFQ, leads to lower bounds, so long as
the mixed traffic is generally similar (e.g., mixing traffic
from multiple video coders makes sense, mixing video and FTP
does not).
This suggests that we need a two-tier mechanism, in which the
first tier separates traffic which has different service
objectives, and the second tier schedules traffic within each
first tier class in order to meet its service objective.
4.3 An example: The CSZ scheme
As a proof of concept, a code package has been implemented which
realizes the services discussed above. It actually uses a number
of the basic tools, combined in a way specific to the service
needs. We describe in general terms how it works, to suggest how
services can be realized. We stress that there are other ways of
building a router to meet the same service needs, and there are in
fact other implementations being used today.
At the top level, the CSZ code uses WFQ as an isolation mechanism
to separate guaranteed flows from each other, as well as from the
rest of the traffic. Guaranteed service gets the highest priority
when and only when it needs the access to meets its deadline. WFQ
provides a separate guarantee for each and every guaranteed flow.
Predictive service and best effort service are separated by
priority. Within the predictive service class, a further priority
is used to provide sub-classes with different delay bounds.
Inside each predictive sub-class, simple FIFO queueing is used to
mix the traffic, which seems to produce good overall delay
behavior. This works because the top-tier algorithm has separated
out the best effort traffic such as FTP.
Within the best-effort class, WFQ is used to provide link sharing.
Since there is a possible requirement for nested shares, this WFQ
code can be used recursively. There are thus two different uses
of WFQ in this code, one to segregate the guaranteed classes, and
one to segregate the link shares. They are similar, but differ in
detail.
Within each link share of the best effort class, priority is used
to permit more time-sensitive elastic traffic to precede other
elastic traffic, e.g., to allow interactive traffic to precede
asynchronous bulk transfers.
The CSZ code thus uses both WFQ and priority in an alternating
manner to build a mechanism to support a range of rather
sophisticated service offerings. This discussion is very brief,
and does not touch on a number of significant issues, such as how
the CSZ code fits real time traffic into the link sharing
objectives. But the basic building blocks are very simple, and
very powerful. In particular, while priority has been proposed as
a key to real-time services, WFQ may be the more general and
powerful of the two schemes. It, rather than priority, supports
guaranteed service and link sharing.
5. Reservation Setup Protocol
There are a number of requirements to be met by the design of a
reservation setuop protocol. It should be fundamentally designed for
a multicast environment, and it must accommodate heterogeneous
service needs. It must give flexible control over the manner in
which reservations can be shared along branches of the multicast
delivery trees. It should be designed around the elementary action
of adding one sender and/or receiver to an existing set, or deleting
one. It must be robust and scale well to large multicast groups.
Finally, it must provide for advance reservation of resources, and
for the preemption that this implies. The reservation setup protocol
RSVP has been designed to meet these requirements [RSVP93a, RSVP93b].
This section gives an overview of the design of RSVP.
5.1 RSVP Overview
Figure shows multi-source, multi-destination data delivery for a
particular shared, distributed application. The arrows indicate
data flow from senders S1 and S2 to receivers R1, R2, and R3, and
the cloud represents the distribution mesh created by the
multicast routing protocol. Multicasting distribution replicates
each data packet from a sender Si, for delivery to every receiver
Rj. We treat uncast delivery from S1 to R1 as a special case, and
we call this multicast distribution mesh a session. A session is
defined by the common IP (multicast) destination address of the
receiver(s).
Senders Receivers
_____________________
( ) ===> R1
S1 ===> ( Multicast )
( ) ===> R2
( distribution )
S2 ===> ( )
( ) ===> R3
(_____________________)
Figure 2: Multicast Distribution Session
5.1.1 Flowspecs and Filter Specs
In general, an RSVP reservation request specifies the amount of
resources to be reserved for all, or some subset of, the
packets in a particular session. The resource quantity is
specified by a flowspec, while the packet subset to receive
those resources is specified by a filter spec. Assuming
admission control succeeds, the flowspec will be used to
parametrize a resource class in the packet scheduler, and the
filter spec will be instantiated in the packet classifier to
map the appropriate packets into this class. The subset of the
classifier state that selects a particular class is referred to
in RSVP documentation as a (packet) "filter".
The RSVP protocol mechanisms provide a very general facility
for creating and maintaining distributed reservation state
across the mesh of multicast delivery paths. These mechanisms
treat flowspecs and filter specs as mostly opaque binary data,
handing them to the local traffic control machinery for
interpretation. Of course, the service model presented to an
application must specify how to encode flowspecs and filter
specs.
5.1.2 Reservation Styles
RSVP offers several different reservation "styles", which
determine the manner in which the resource requirements of
multiple receivers are aggregated in the routers. These styles
allow the reserved resources to more efficiently meet
application requirements. Currently there are three
reservation styles, "wildcard", "fixed-filter", and " dynamic-
filter". A wildcard reservation uses a filter spec that is not
source-specific, so all packets destined for the associated
destination (session) may use a common pool of reserved
resources. This allows a single resource allocation to be made
across all distribution paths for the group. The wildcard
reservation style is useful in support of an audio conference,
where at most a small number of sources are active
simultaneously and may share the resource allocation.
The other two styles use filter specs that select particular
sources. A receiver may desire to receive from a fixed set of
sources, or instead it may desire the network to switch between
different source, by changing its filter spec(s) dymamically.
A fixed-filter style reservation cannot be changed during its
lifetime without re-invoking admission control. Dynamic-filter
reservations do allow a receiver to modify its choice of
source(s) over time without additional admission control;
however, this requires that sufficient resources be allocated
to handle the worst case when all downstream receivers take
input from different sources.
5.1.3 Receiver Initiation
An important design question is whether senders or receivers
should have responsibility for initiating reservations. A
sender knows the qualities of the traffic stream it can send,
while a receiver knows what it wants to (or can) receive.
Perhaps the most obvious choice is to let the sender initiate
the reservation. However, this scales poorly for large,
dynamic multicast delivery trees and for heterogeneous
receivers.
Both of these scaling problems are solved by making the
receiver responsible for initiating a reservation. Receiver
initiation handles heterogeneous receivers easily; each
receiver simply asks for a reservation appropriate to itself,
and any differences among reservations from different receivers
are resolved ("merged") within the network by RSVP. Receiver
initiation is also consisent with IP multicast, in which a
multicast group is created implicitly by receivers joining it.
Although receiver-initiated reservation is the natural choice
for multicast sessions, the justification for receiver
initiateion may appear weaker for unicast sessions, where the
sender may be the logical session initiator. However, we
expect that every realtime application will have its higher-
level signalling and control protocol, and this protocol can be
used to signal the receiver to initiate a reservation (and
perhaps indicate the flowspec to be used). For simplicity and
economy, a setup protocol should support only one direction of
initiation, and, and receiver initiation appears to us to be
the clear winner.
RSVP uses receiver-initiation of rservations [RSVP93b]. A
receiver is assumed to learn the senders' offered flowspecs by
a higher-level mechanism ("out of band"), it then generates its
own desired flowspec and propagates it towards the senders,
making reservations in each router along the way.
5.1.4 Soft State
There are two different possible styles for reservation setup
protocols, the "hard state" (HS) approach (also called
"connection-oriented"), and the "soft state" (SS) approach
(also called "connectionless"). In both approaches, multicast
distribution is performed using flow-specific state in each
router along the path. Under the HS approach, this state is
created and deleted in a fully deterministic manner by
cooperation among the routers. Once a host requests a session,
the "network" takes responsibility for creating and later
destroying the necessary state. ST-II is an example of the HS
approach [ST2-90]. Since management of HS session state is
completely deterministic, the HS setup protocol must be
reliable, with acknowledgments and retransmissions. In order
to achieve deterministic cleanup of state after a failure,
there must be some mechanism to detect failures, i.e., an
"up/down" protocol. The router upstream (towards the source)
from a failure takes responsibility for rebuilding the
necessary state on the router(s) along an alternate route.
RSVP takes the SS approach, which regards the reservation state
as cached information that is installed and periodically
refreshed by the end hosts. Unused state is timed out by the
routers. If the route changes, the refresh messages
automatically install the necessary state along the new route.
The SS approach was chosen to obtain the simplicity and
robustness that have been demonstrated by connectionless
protocols such as IP [Clark88].
5.2 Routing and Reservations
There is a fundamental interaction between resource reservation
set up and routing, since reservation requires the installation of
flow state along the route of data packets. If and when a route
changes, there must be some mechanism to set up a reservation
along the new route.
Some have suggested that reservation setup necessarily requires
route set up, i.e., the imposition of a virtual-circuit internet
layer. However, our goal is to simply extend the Internet
architecture, not replace it. The fundamental connectionless
internet layer [Clark88] has been highly successful, and we wish
to retain it as an architectural foundation. We propose instead
to modify somewhat the pure datagram forwarding mechanism of the
present Internet to accomodate "IS".
There are four routing issues faced by a reservation setup
protocol such as RSVP.
1. Find a route that supports resource reservation.
This is simply "type-of-service" routing, a facility that is
already available in some modern routing protocols.
2. Find a route that has sufficient unreserved capacity for a
new flow.
Early experiments on the ARPANET showed that it is difficult
to do load-dependent dynamic routing on a packet-by-packet
basis without instability problems. However, instability
should not be a problem if load-dependent routing is
performed only at reservation setup time.
Two different approaches might be taken to finding a route
with enough capacity. One could modify the routing
protocol(s) and interface them to the traffic control
mechanism, so the route computation can consider the average
recent load. Alternatively, the routing protocol could be
(re-)designed to provide multiple alternative routes, and
reservation setup could be attempted along each in turn.
3. Adapt to a route failure
When some node or link fails, adaptive routing finds an
alternate path. The periodic refresh messages of RSVP will
automatically request a reservation along the new path. Of
course, this reservation may fail because there is
insufficienct available capacity on the new path. This is a
problem of provisioning and network engineering, which cannot
be solved by the routing or setup protocols.
There is a problem of timeliness of establishing reservation
state on the new path. The end-to-end robustness mechanism
of refreshes is limited in frequency by overhead, which may
cause a gap in realtime service when an old route breaks and
a new one is chosen. It should be possible to engineer RSVP
to sypplement the global refresh mechanism with a local
repair mechanism, using hints about route changes from the
routing mechanism.
4. Adapt to a route change (without failure)
Route changes may occur even without failure in the affected
path. Although RSVP could use the same repair techniques as
those described in (3), this case raises a problem with the
robustness of the QoS guarantees. If it should happen that
admission control fails on the new route, the user will see
service degradation unnecessarily and capriciously, since the
orginal route is still functional.
To avoid this problem, a mechanism called "route pinning" has
been suggested. This would modify the routing protocol
implementation and the interface to the classifier, so that
routes associated with resource reservations would be
"pinned". The routing prootocol would not change a pinned
route if it was still viable.
It may eventually be possible to fold together the routing and
reservation setup problems, but we do not yet understand enough to
do that. Furthermore, the reservation protocol needs to coexist
with a number of different routing protocols in use in the
Internet. Therefore, RSVP is currently designed to work with any
current-generation routing protocol without modification. This is
a short-term compromise, which may result in an occasional failure
to create the best, or even any, real-time session, or an
occasional service degradation due to a route change. We expect
that future generations of routing protocols will remove this
compromise, by including hooks and mechanisms that, in conjunction
with RSVP, will solve the problems (1) through (4) just listed.
They will support route pinning, notification of RSVP to trigger
local repair, and selection of routes with "IS" support and
adequate capacity.
The last routing-related issue is provided by mobile hosts. Our
conjecture is that mobility is not essentially different from
other route changes, so that the mechanism suggested in (3) and
(4) will suffice. More study and experimentation is needed to
prove or disprove this conjecture.
6. ACKNOWLEDGMENTS
Many Internet researchers have contributed to the work described in
this memo. We want to especially acknowledge, Steve Casner, Steve
Deering, Deborah Estrin, Sally Floyd, Shai Herzog, Van Jacobson,
Sugih Jamin, Craig Partridge, John Wroclawski, and Lixia Zhang. This
approach to Internet integrated services was initially discussed and
organized in the End-to-End Research Group of the Internet Research
Taskforce, and we are grateful to all members of that group for their
interesting (and sometimes heated) discussions.
REFERENCES
[CerfKahn74] Cerf, V., and R. Kahn, "A Protocol for Packet Network
Intercommunication", IEEE Trans on Comm., Vol. Com-22, No. 5, May
1974.
[Clark88] Clark, D., "The Design Philosophy of the DARPA Internet
Protocols", ACM SIGCOMM '88, August 1988.
[CSZ92] Clark, D., Shenker, S., and L. Zhang, "Supporting Real-Time
Applications in an Integrated Services Packet Network: Architecture
and Mechanisms", Proc. SIGCOMM '92, Baltimore, MD, August 1992.
[DKS89] Demers, A., Keshav, S., and S. Shenker. "Analysis and
Simulation of a Fair Queueing Algorithm", Journal of
Internetworking: Research and Experience, 1, pp. 3-26, 1990. Also
in Proc. ACM SIGCOMM '89, pp 3-12.
[SCZ93a] Shenker, S., Clark, D., and L. Zhang, "A Scheduling Service
Model and a Scheduling Architecture for an Integrated Services
Packet Network", submitted to ACM/IEEE Trans. on Networking.
[SCZ93b] Shenker, S., Clark, D., and L. Zhang, "A Service Model for the
Integrated Services Internet", Work in Progress, October 1993.
[Floyd92] Floyd, S., "Issues in Flexible Resource Management for
Datagram Networks", Proceedings of the 3rd Workshop on Very High
Speed Networks, March 1992.
[Jacobson91] Jacobson, V., "Private Communication", 1991.
[JCSZ92] Jamin, S., Shenker, S., Zhang, L., and D. Clark, "An Admission
Control Algorithm for Predictive Real-Time Service", Extended
abstract, in Proc. Third International Workshop on Network and
Operating System Support for Digital Audio and Video, San Diego, CA,
Nov. 1992, pp. 73-91.
[Parekh92] Parekh, A., "A Generalized Processor Sharing Approach to
Flow Control in Integrated Services Networks", Technical Report
LIDS-TR-2089, Laboratory for Information and Decision Systems,
Massachusetts Institute of Technology, 1992.
[Partridge92] Partridge, C., "A Proposed Flow Specification", RFC1363,
BBN, July 1992.
[RSVP93a] Zhang, L., Deering, S., Estrin, D., Shenker, S., and D.
Zappala, "RSVP: A New Resource ReSerVation Protocol", Accepted for
publication in IEEE Network, 1993.
[RSVP93b] Zhang, L., Braden, R., Estrin, D., Herzog, S., and S. Jamin,
"Resource ReSerVation Protocol (RSVP) - Version 1 Functional
Specification", Work in Progress, 1993.
[ST2-90] Topolcic, C., "Experimental Internet Stream Protocol: Version
2 (ST-II)", RFC1190, BBN, October 1990.
[Tenet90] Ferrari, D., and D. Verma, "A Scheme for Real-Time Channel
Establishment in Wide-Area Networks", IEEE JSAC, Vol. 8, No. 3, pp
368-379, April 1990.
Security Considerations
As noted in Section 2.1, the ability to reserve resources will create
a requirement for authentication, both of users requesting resource
guarantees and of packets that claim to have the right to use those
guarantees. These authentication issues are not otherwise addressed
in this memo, but are for further study.
Authors' Addresses
Bob Braden
USC Information Sciences Institute
4676 Admiralty Way
Marina del Rey, CA 90292
Phone: (310) 822-1511
EMail: Braden@ISI.EDU
David Clark
MIT Laboratory for Computer Science
545 Technology Square
Cambridge, MA 02139-1986
Phone: (617) 253-6003
EMail: ddc@LCS.MIT.EDU
Scott Shenker
Xerox Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, CA 94304
Phone: (415) 812-4840