As per Relevance of the word datagram, we have this rfc below:
Network Working Group W.
Request for Comments: 1046 J.
February 1988
A Queuing Algorithm to Provide Type-of-Service for IP
Status of this
This memo is intended to explore how Type-of-Service might
implemented in the Internet. The proposal describes a method
queuing which can provide the different classes of service.
technique also prohibits one class of service from
excessive resources or excluding other classes of service. This
an "idea paper" and discussion is strongly encouraged.
of this memo is unlimited
The Type-of-Service (TOS) field in IP headers allows one to
from none to all the following service types; low delay,
throughput, and high reliability. It also has a portion allowing
priority selection from 0-7. To date, there is nothing
what should be done with these parameters. This discussion
an approach to providing the different classes of service
priorities requestable in the TOS field
Desired
We should first consider how we want these services to perform.
must first assume that there is a demand for service that
current capabilities. If not, significant queues do not form
queuing algorithms become superfluous
The low delay class of service should have the ability to pass
through the net faster than regular data. If a request is for
delay class of service only, not high throughput or high reliability
the Internet should provide low delay for relatively less throughput
with less than high reliability. The requester is more
with promptness of delivery than guaranteed delivery. The
should provide a Maximum Guaranteed Delay (MGD) per node, or better
if the datagram successfully traverses the Internet. In the
case, a datagram's arrival will be MGD times the number of
traversed. A node is any packet switching element, including
gateways and ARPANET IMP's. The MGD bound will not be affected
the amount of traffic in the net. During non-busy hours, the
provided should be better than the guarantee. If the delay
Prue & Postel [Page 1]
RFC 1046 Type-of-Service Queuing February 1988
satellite link introduces is less than the MGD, that link should
considered in the route. If however, the MGD is less than
satellite link can provide, it should not be used. For
discussion it is assumed that delay for individual links are
enough that a sending node can provide the MGD service
Low delay class of service is not the same as low Round Trip
(RTT). Class of service is unidirectional. The datagrams
to low delay traffic (i.e., Acking the data) might be sent with
high reliability class of service, but not low delay
The performance of TCP might be significantly improved with
accurate estimate of the round trip time and the
timeout. The TCP retransmission timeout could be set to the
delay for the current route (if the current route could
determined). The timeout value would have to be redetermined
the number of hops in the route changes
High throughput class of service should get a large volume of
through the Internet. Requesters of this class are less
with the delay the datagrams have crossing the Internet and
reliability of their delivery. This type of traffic might be
well by a satellite link, especially if the bandwidth is high
Another attribute this class might have is consistent one
traversal time for a given burst of datagrams. This class of
will have its traversal times affected by the amount of
load. As the Internet load goes up, the throughput for each
will go down
High reliability class of service should see most of its
delivered if the Internet is not too heavily loaded. Source
(SQ) should not be sent only when datagrams are discarded.
should be sent well before the queues become full, to advise
sender of the rate that can be currently supported
Priority service should allow data that has a higher priority to
queued ahead of other lower priority data. It is important to
the amount of priority data. The amount of preemption a
priority datagram suffers must also be limited
It is assumed that a queuing algorithm provides these classes
service. For one facility to be used over another, that is,
different routing decisions based upon the TOS, requires a
sophisticated routing algorithm and larger routing database.
issues are not discussed in this document
Prue & Postel [Page 2]
RFC 1046 Type-of-Service Queuing February 1988
Applications for Class of
The following are examples of how classes of service might be used
They do not necessarily represent the best choices, but are
only to illustrate how the different classes of service might be
to advantage
Interactive timesharing access using a line-at-a-time or character
at-a-time terminal (TTY) type of access is typically low
typing speed input with low or high volume output. Some
applications use echoplex or character by character echoing of
input by the destination host. PC devices also have local files
may be uploaded to remote hosts in a streaming mode. Supporting
traffic can require several types of service. User keyboard
should be forwarded with low delay. If echoplex is used, all
characters sent and echoed should be low delay to minimize
echoing delay. The computer responses should be regular or
throughput depending upon the volume of data sent and the speed
the output device. If the computer response is a single datagram
data, the user should get low delay for the response, to minimize
human/computer interaction time. If however the output takes a
to read and digest, low delay computer responses are a waste
Internet resources. When streaming input is being sent the
should be sent requesting high throughput or regular class
service
The IBM 3270 class of terminals typically have traffic
greater than TTY access. Echoplex is not needed. The output
usually handle higher speed output streams and most sites do not
the ability to stream input. Input is typically a screen at a time
but some PC implementations of 3270 use a variation of the
to effectively stream in volumes of data. Low delay for low
input and output is appropriate. High throughput is appropriate
the higher volume traffic
Applications that transfer high volumes of data are
streaming in one direction only, with acks for the data, on
return path. The data transfer should be high throughput and
acks should probably be regular class of service.
initiation and termination might be served best with low delay
of service
Requests to, and responses from a time service might use low
class of service effectively
These suggestions for class of service usage implies that
application sets the service based on the knowledge it has during
session. Thus, the application should have control of this
Prue & Postel [Page 3]
RFC 1046 Type-of-Service Queuing February 1988
dynamically for each send data request, not just on a
session/conversation/transaction basis. It would be possible for
transport level protocol to guess (i.e., TCP), but it would be sub
optimal
When we provide class of service queuing, one class may be
desirable than the others. We must limit the amount of
each class consumes when there is contention, so the other
may also operate effectively. To be fair, the algorithm provides
requested service by reducing the other service attributes.
request for multiple classes of service is an OR type of request
an AND request. For example, one can not get low delay and
throughput unless there is no contention for the available resources
Low Delay
To support low delay, use a limited queue so requests will not
longer than the MGD on the queue. The low delay queue should
serviced at a lower rate than other classes of service, so low
requests will not consume excessive resources. If the number of
delay datagrams exceeds the queue limit, discard the datagrams.
service rate should be low enough so that other data can still
through. (See discussion of service rates below.) Make the
limit small enough so that, if the datagram is queued, it will have
guaranteed transit time (MGD). It seems unlikely that Source
flow control mechanisms will be an effective method of flow
because of the small size of the queue. It should not be done
this class of service. Instead, datagrams should just be
as required. If the bandwidth or percentage allocated to low
is such that a large queue is possible (see formula below),
should be reconsidered
The maximum delay a datagram with low delay class of service
experience (MGD), can be determined with the following information
N = Queue size for low delay
P = Percentage of link resources allocated to low
R = Link rate (in datagrams/sec.)
Max Delay = -----
P *
If Max Delay is held fixed, then as P and R go up, so does N. It
probable that low delay service datagrams will prove to be, on
average, smaller than other traffic. This means that the number
datagrams that can be sent in the allocated bandwidth can be larger
Prue & Postel [Page 4]
RFC 1046 Type-of-Service Queuing February 1988
High Reliability
To support high reliability class of service, use a queue that
longer than normal (longer queue means higher potential delay).
SQ earlier (smaller percentage of max queue length) and don't
datagrams until the queue is full. This queue should have a
service rate than high throughput class of service
Users of this class of service should specify a Time-to-Live (TTL
which is made appropriately longer so that it will survive
queueing times for this class of service
This queuing procedure will only be effective for
unreliability due to congestion. Other Internet
problems such as high error rate links or reliability features
as forward error correcting modems must be dealt with by
sophisticated routing algorithms
High Throughput
To support high throughput class of service have a queue that
treated like current IP queuing. It should have the highest
rate. It will experience higher average through node delay than
delay because of the larger queue size
Another thing that might be done, is to keep datagrams of the
burst together when possible. This must be done in a way that
not block other traffic. The idea is to deliver all the data to
other end in a contiguous burst. This could be an advantage
allowing piggybacking acks for the whole burst at one time.
makes some assumptions about the overlying protocol which may
inappropriate
Regular Service
For datagrams which request none of the three classes of service
queue the datagrams on the queue representing the least delay
the two queues, the high throughput queue or the high
queue. If one queue becomes full, queue on the other. If
queues are full, follow the source quench procedure for regular
of service (see RFC-1016), not the procedure for the queue
datagram failed to attain
In the discussion of service rates described below, it is
that the high throughput queue get service three times for every
times for the high reliability queue. Therefore, the queue length
the high reliability queue should be increased by 50% (in
example) to compare the lengths of the two queues more accurately.
Prue & Postel [Page 5]
RFC 1046 Type-of-Service Queuing February 1988
simplification to this method is to just queue new data on the
that is the shortest. The slower service rate queue will
exceed the size of the faster service rate queue and new data will
on the proper queue. This however, would lead to more
reordering than the first method
Service
In this discussion, a higher service rate means that a queue,
non-empty, will consume a larger percentage of the
bandwidth than a lower service rate queue. It will not block a
service rate queue even if it is always full
For example, the service pattern could be; send low delay 17% of
time, high throughput 50% of the time, and high reliability 33%
the time. Throughput requires the most bandwidth and
reliability requires medium bandwidth. One could achieve this
using a pattern of L, R,R, T,T,T, where low delay is "L",
reliability is "R", and high throughput is "T'. We want to keep
high throughput datagrams together. We therefore send all of
high throughput data at one time, that is, not interspersed with
other classes of service. By keeping all of the high throughput
together, we may help higher level protocols, such as TCP,
described above. This would still be done in a way to not exceed
allowed service rate of the available bandwidth
These service rates are suggestions. Some simplifications can
considered, such as having only two routing classes; low delay,
other
There is the ability to select 8 levels of priority 0-7, in
to the class of service selected. To provide this without
the least priority requests, we must give preempted
frustration points every time a higher priority request cuts in
in front of it. Thus if a datagram with low priority waits, it
always get through even when competing against the highest
requests. This assumes the TTL (Time-to-Live) field does not expire
When a datagram with priority arrives at a node, the node will
the datagram on the appropriate queue ahead of all datagrams
lower priority. Each datagram that was preempted gets its
raised (locally). The priority data will not bump a lower
datagram off its queue, discarding the data. If the queue is full
the newest data (priority or not) will be discarded. The
preemption will preempt only within the class of service queue
Prue & Postel [Page 6]
RFC 1046 Type-of-Service Queuing February 1988
which the priority data is targeted. A request specifying
class of service, will contend on the queue where it is placed,
throughput or high reliability
An implementation strategy is to multiply the requested priority by 2
or 4, then store the value in a buffer overhead area. Each time
datagram is preempted, increment the value by one. Looking at
example, assume we use a multiplier of 2. A priority 6 buffer
have an initial local value of 12. A new priority 7 datagram
have a local value of 14. If 2 priority 7 datagrams arrive
preempting the priority 6 datagram, its local value is incremented
14. It can no longer be preempted. After that, it has the
local value as a priority 7 datagram and will no longer be
within this node. In our example, this means that a priority 0
datagram can be preempted by no more than 14 higher
datagrams. The priority is raised only locally in the node.
datagram could again be preempted in the next node on the route
Priority queuing changes the effects we were obtaining with the
delay queuing described above. Once a buffer was queued, the
that a datagram would see could be determined. When we accepted
delay data, we could guarantee a certain maximum delay. With
addition, if the datagram requesting low delay does not also
high priority, the guaranteed delay can vary a lot more. It could
1 up to 28 times as much as without priority queuing
Discussion and
If a low delay queue is for a satellite link (or any high
link), the max queue size should be reduced by the number
datagrams that can be forwarded from the queue during the one
delay for the link. That is, if the service rate for the low
queue is L datagrams per second, the delay added by the high
link is D seconds and M is the max delay per node allowed (MGD)
seconds, then the maximum queue size should be
Max Queue Size = L ( M - D), M >
= 0 , M <=
If the result is negative (M is less than the delay introduced by
link), then the maximum queue size should be zero because the
could never provide a delay less than the guaranteed M value. If
bandwidth is high (as in T1 links), the delay introduced by
terrestrial link and the terminating equipment could be
and greater than the average service time for a single datagram
the low delay queue. If so, this formula should be used to
the queue size as well. Note that this is reducing the queue
and is not the same as the allocated bandwidth. Even though
Prue & Postel [Page 7]
RFC 1046 Type-of-Service Queuing February 1988
queue size is reduced, the chit scheme described below will give
delay requesters a chance to use the allocated bandwidth
If a datagram requests multiple classes of service, only one
can be provided. For example, when both low delay and
reliability classes are requested, and if the low delay queue
full, queue the data on the high reliability queue instead. If
are able to queue the data on the low delay queue, then the
gets part of the high reliability service it also requested, because
once data is queued, data will not be discarded. However,
datagram will be routed as a low delay request. The same scheme
used for any other combinations of service requested. The order
selection for classes of service when more than one is
would be low delay, high throughput, then high reliability. If
block of datagrams request multiple classes of service, it is
possible that datagram reordering will occur. If one queue is
causing the other queue to be used for some of the data, data will
forwarded at different service rates. Requesting multiple classes
service gives the data a better chance of making it through the
because they have multiple chances of getting on a service queue
However, the datagrams pay the penalty of possible reordering
more variability in the one way transmission times
Besides total buffer consumption, individual class of service
sizes should be used to SQ those asking for service except as
above
A request for regular class of service is handled by queuing to
high reliability or high throughput queues evenly (proportional
the service rates of queue). The low delay queue should only
data with the low delay service type. Its queue is too small
accept other traffic
Because of the small queue size for low delay suggested above, it
difficult for low delay service requests to consume the
allocated. To do so, low delay users must keep the small
continuously non-empty. This is hard to do with a small queue
Traffic flow has been shown to be bursty in nature. In order for
low delay queue to be able to consume the allocated bandwidth,
count of the various types being forwarded should be kept.
service rate should increase if the actual percentage falls too
for the low delay queue. The measure of service rates would have
be smoothed over time
While this does sound complicated, a reasonably efficient way can
described. Every Q seconds, where Q is less than or equal to
MGD, each class gets N M P chits proportional to their
percentage. Send data for the low delay queue up to the number
Prue & Postel [Page 8]
RFC 1046 Type-of-Service Queuing February 1988
chits it receives decrementing the chits as datagrams are sent.
send from the high reliability queue as many as it has chits for
Finally, send from the high throughput queue. At this point,
queue gets N M P chits again. If the low delay queue does
consume all of its chits, when a low delay datagram arrives,
chit replenishment, send from the low delay queue immediately.
provides some smoothing of the actual bandwidth made available
low delay traffic. If operational experience shows that low
requests are experiencing excessive congestion loss but still
consuming the classes allocated bandwidth, adjustments should
made. The service rates should be made larger and the queue
adjusted accordingly. This is more important on lower speed
where the above formula makes the queue small
What we should see during the Q seconds is that low delay data
be sent as soon as possible (as long as the volume is below
allowed percentage). Also, the tendency will be to send all the
throughput datagrams contiguously. This will give a more
measured round trip time for bursts of datagrams. Classes of
will tend to be grouped together at each intermediate node in
route. If all of the queues with datagrams have consumed all
their allocated chits, but one or more classes with empty queues
unused chits then a percentage of these left over chits should
carried over. Divide the remaining chit counts by two (with
down), then add in the refresh chit counts. This allows a 50%
over for the next interval. The carry over is self limiting to
than or equal to the refresh chit count. This prevents
build up. It provides some smoothing of the percentage
over time but will not allow an unused queue to build up
indefinitely. No timer is required
If only a simple subset of the described algorithm is to
implemented, then low delay queuing would be the best choice.
should use a small queue. Service the queue with a high service
but restrict the bandwidth to a small reasonable percentage of
available bandwidth. Currently, wide area networks with high
volumes do not provide low delay service unless low delay
are able to preempt other traffic
When the output speed and volume match the input speed and volume
queues don't get large. If the queues never grow large enough
exceed the guaranteed low delay performance, no queuing
other than first in, first out, should be used
The algorithm could be turned on when the main queue size exceeds
certain threshold. The routing node can periodically check for
Prue & Postel [Page 9]
RFC 1046 Type-of-Service Queuing February 1988
build up. This queuing algorithm can be turned on when the
delays will exceed the allowed nodal delay for low delay class
service. It can also be turned off when queue sizes are no longer
problem
Several issues need to be addressed before type of service queuing
described should be implemented. What percentage of the
should each class of service consume assuming an infinite supply
each class of service datagrams? What maximum delay (MGD) should
guaranteed per node for low delay datagrams
It is possible to provide a more optimal route if the queue sizes
each class of service are considered in the routing decision. This
however, adds additional overhead and complexity to each
node. This may be an unacceptable additional complexity
How are we going to limit the use of more desirable classes
service and higher priorities? The algorithm limits use of
various classes by restricting queue sizes especially the low
queue size. This helps but it seems likely we will want
instrument the number of datagrams requesting each Type-of-
and priority. When a datagram requests multiple classes of service
increment the instrumentation count once based upon the
actually used, selecting, low delay, high throughput,
reliability, then regular. If instrumentation reveals an
imbalance, Internet operations can give this to administrators
handle. This instrumentation will show the distribution for types
service requested by the Internet users. This information can
used to tune the Internet to service the user demands
Will the routing algorithms in use today have problems when
data with this algorithm? Simulation tests need to be done to
how the Internet will react. If, for example, an
requests multiple classes of service, round trip times may
significantly. Would TCP have to be more sophisticated in its
trip time estimator
An objection to this type of queuing algorithm is that it is
the routing and queuing more complicated. There is current
in high speed packet switches which have very little
overhead when handling/routing packets. This algorithm
not simplifies the protocol. The bandwidth being made available
increasing. More T1 (1.5 Mbps) and higher speed links are being
all the time. However, in the history of communications, it
that the demand for bandwidth has always exceeded the supply.
there is wide spread use of optical fiber we may
Prue & Postel [Page 10]
RFC 1046 Type-of-Service Queuing February 1988
experience a glut of capacity. As soon as 1 gigabit optical
link becomes reasonably priced, new applications will be created
consume it all. A single full motion high resolution color
system can consume, as an upper limit, nearly a gigabit per
channel (30 fps X 24 b/pixel X 1024 X 1024 pixels).
In the study of one gateway, Dave Clark discovered that the
datagram processing of the IP header constituted about 20% of
processing time. Much of the time per datagram was spent
restarting input, starting output and queuing datagrams. He
that a small additional amount of processing to support Type-of
Service would be reasonable. He suggests that even if the code
slow the gateway down, we need to see if TOS is good for anything,
this experiment is valuable. To support the new high
communications of the near future, Dave wants to see switches
will run one to two orders of magnitude faster. This can not be
by trimming a few instructions here or there
From a practical perspective, the problem this algorithm is trying
solve is the lack of low delay service through the Internet today
Implementing only the low delay queuing portion of this
would allow the Internet to provide a class of service it
could not provide. Requesters of this class of service would not
it for free. Low delay class of datagram streams get low delay
the cost of reliability and throughput
Prue & Postel [Page 11]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
