rfc1046.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 619 行 · 第 1/2 页

   described above.  This would still be done in a way to not exceed the
   allowed service rate of the available bandwidth.

   These service rates are suggestions.  Some simplifications can be
   considered, such as having only two routing classes; low delay, and
   other.

Priority

   There is the ability to select 8 levels of priority 0-7, in addition
   to the class of service selected.  To provide this without blocking
   the least priority requests, we must give preempted datagrams
   frustration points every time a higher priority request cuts in line
   in front of it.  Thus if a datagram with low priority waits, it will
   always get through even when competing against the highest priority
   requests.  This assumes the TTL (Time-to-Live) field does not expire.

   When a datagram with priority arrives at a node, the node will queue
   the datagram on the appropriate queue ahead of all datagrams with
   lower priority.  Each datagram that was preempted gets its priority
   raised (locally).  The priority data will not bump a lower priority
   datagram off its queue, discarding the data.  If the queue is full,
   the newest data (priority or not) will be discarded.  The priority
   preemption will preempt only within the class of service queue to



Prue & Postel                                                   [Page 6]

RFC 1046                Type-of-Service Queuing            February 1988


   which the priority data is targeted.  A request specifying regular
   class of service, will contend on the queue where it is placed, high
   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 the
   datagram is preempted, increment the value by one.  Looking at an
   example, assume we use a multiplier of 2.  A priority 6 buffer will
   have an initial local value of 12.  A new priority 7 datagram would
   have a local value of 14.  If 2 priority 7 datagrams arrive,
   preempting the priority 6 datagram, its local value is incremented to
   14.  It can no longer be preempted.  After that, it has the same
   local value as a priority 7 datagram and will no longer be preempted
   within this node.  In our example, this means that a priority 0
   datagram can be preempted by no more than 14 higher priority
   datagrams.  The priority is raised only locally in the node.  The
   datagram could again be preempted in the next node on the route.

   Priority queuing changes the effects we were obtaining with the low
   delay queuing described above.  Once a buffer was queued, the delay
   that a datagram would see could be determined.  When we accepted low
   delay data, we could guarantee a certain maximum delay.  With this
   addition, if the datagram requesting low delay does not also request
   high priority, the guaranteed delay can vary a lot more.  It could be
   1 up to 28 times as much as without priority queuing.

Discussion and Details

   If a low delay queue is for a satellite link (or any high delay
   link), the max queue size should be reduced by the number of
   datagrams that can be forwarded from the queue during the one way
   delay for the link.  That is, if the service rate for the low delay
   queue is L datagrams per second, the delay added by the high delay
   link is D seconds and M is the max delay per node allowed (MGD) in
   seconds, then the maximum queue size should be:

         Max Queue Size = L ( M - D),  M > D
                        = 0         ,  M <= D

   If the result is negative (M is less than the delay introduced by the
   link), then the maximum queue size should be zero because the link
   could never provide a delay less than the guaranteed M value.  If the
   bandwidth is high (as in T1 links), the delay introduced by a
   terrestrial link and the terminating equipment could be significant
   and greater than the average service time for a single datagram on
   the low delay queue.  If so, this formula should be used to reduce
   the queue size as well.  Note that this is reducing the queue size
   and is not the same as the allocated bandwidth.  Even though the



Prue & Postel                                                   [Page 7]

RFC 1046                Type-of-Service Queuing            February 1988


   queue size is reduced, the chit scheme described below will give low
   delay requesters a chance to use the allocated bandwidth.

   If a datagram requests multiple classes of service, only one class
   can be provided.  For example, when both low delay and high
   reliability classes are requested, and if the low delay queue is
   full, queue the data on the high reliability queue instead.  If we
   are able to queue the data on the low delay queue, then the datagram
   gets part of the high reliability service it also requested, because,
   once data is queued, data will not be discarded.  However, the
   datagram will be routed as a low delay request.  The same scheme is
   used for any other combinations of service requested.  The order of
   selection for classes of service when more than one is requested
   would be low delay, high throughput, then high reliability.  If a
   block of datagrams request multiple classes of service, it is quite
   possible that datagram reordering will occur.  If one queue is full
   causing the other queue to be used for some of the data, data will be
   forwarded at different service rates.  Requesting multiple classes of
   service gives the data a better chance of making it through the net
   because they have multiple chances of getting on a service queue.
   However, the datagrams pay the penalty of possible reordering and
   more variability in the one way transmission times.

   Besides total buffer consumption, individual class of service queue
   sizes should be used to SQ those asking for service except as noted
   above.

   A request for regular class of service is handled by queuing to the
   high reliability or high throughput queues evenly (proportional to
   the service rates of queue).  The low delay queue should only receive
   data with the low delay service type.  Its queue is too small to
   accept other traffic.

   Because of the small queue size for low delay suggested above, it is
   difficult for low delay service requests to consume the bandwidth
   allocated.  To do so, low delay users must keep the small queue
   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 the
   low delay queue to be able to consume the allocated bandwidth, a
   count of the various types being forwarded should be kept.  The
   service rate should increase if the actual percentage falls too low
   for the low delay queue.  The measure of service rates would have to
   be smoothed over time.

   While this does sound complicated, a reasonably efficient way can be
   described.  Every Q seconds, where Q is less than or equal to the
   MGD, each class gets N M P chits proportional to their allowed
   percentage.  Send data for the low delay queue up to the number of



Prue & Postel                                                   [Page 8]

RFC 1046                Type-of-Service Queuing            February 1988


   chits it receives decrementing the chits as datagrams are sent.  Next
   send from the high reliability queue as many as it has chits for.
   Finally, send from the high throughput queue.  At this point, each
   queue gets N M P chits again.  If the low delay queue does not
   consume all of its chits, when a low delay datagram arrives, before
   chit replenishment, send from the low delay queue immediately.  This
   provides some smoothing of the actual bandwidth made available for
   low delay traffic.  If operational experience shows that low delay
   requests are experiencing excessive congestion loss but still not
   consuming the classes allocated bandwidth, adjustments should be
   made.  The service rates should be made larger and the queue sizes
   adjusted accordingly.  This is more important on lower speed links
   where the above formula makes the queue small.

   What we should see during the Q seconds is that low delay data will
   be sent as soon as possible (as long as the volume is below the
   allowed percentage).  Also, the tendency will be to send all the high
   throughput datagrams contiguously.  This will give a more regular
   measured round trip time for bursts of datagrams.  Classes of service
   will tend to be grouped together at each intermediate node in the
   route.  If all of the queues with datagrams have consumed all of
   their allocated chits, but one or more classes with empty queues have
   unused chits then a percentage of these left over chits should be
   carried over.  Divide the remaining chit counts by two (with round
   down), then add in the refresh chit counts.  This allows a 50% carry
   over for the next interval.  The carry over is self limiting to less
   than or equal to the refresh chit count.  This prevents excessive
   build up.  It provides some smoothing of the percentage allocation
   over time but will not allow an unused queue to build up chits
   indefinitely.  No timer is required.

   If only a simple subset of the described algorithm is to be
   implemented, then low delay queuing would be the best choice.  One
   should use a small queue.  Service the queue with a high service rate
   but restrict the bandwidth to a small reasonable percentage of the
   available bandwidth.  Currently, wide area networks with high traffic
   volumes do not provide low delay service unless low delay requests
   are able to preempt other traffic.

Applicability

   When the output speed and volume match the input speed and volume,
   queues don't get large.  If the queues never grow large enough to
   exceed the guaranteed low delay performance, no queuing algorithm
   other than first in, first out, should be used.

   The algorithm could be turned on when the main queue size exceeds a
   certain threshold.  The routing node can periodically check for queue



Prue & Postel                                                   [Page 9]

RFC 1046                Type-of-Service Queuing            February 1988


   build up.  This queuing algorithm can be turned on when the maximum
   delays will exceed the allowed nodal delay for low delay class of
   service.  It can also be turned off when queue sizes are no longer a
   problem.

Issues

   Several issues need to be addressed before type of service queuing as
   described should be implemented.  What percentage of the bandwidth
   should each class of service consume assuming an infinite supply of
   each class of service datagrams?  What maximum delay (MGD) should be
   guaranteed per node for low delay datagrams?

   It is possible to provide a more optimal route if the queue sizes for
   each class of service are considered in the routing decision.  This,
   however, adds additional overhead and complexity to each routing
   node.  This may be an unacceptable additional complexity.

   How are we going to limit the use of more desirable classes of
   service and higher priorities?  The algorithm limits use of the
   various classes by restricting queue sizes especially the low delay
   queue size.  This helps but it seems likely we will want to
   instrument the number of datagrams requesting each Type-of-Service
   and priority.  When a datagram requests multiple classes of service,
   increment the instrumentation count once based upon the queue
   actually used, selecting, low delay, high throughput, high
   reliability, then regular.  If instrumentation reveals an excessive
   imbalance, Internet operations can give this to administrators to
   handle.  This instrumentation will show the distribution for types of
   service requested by the Internet users.  This information can be
   used to tune the Internet to service the user demands.

   Will the routing algorithms in use today have problems when routing
   data with this algorithm?  Simulation tests need to be done to model
   how the Internet will react.  If, for example, an application
   requests multiple classes of service, round trip times may fluctuate
   significantly.  Would TCP have to be more sophisticated in its round
   trip time estimator?

   An objection to this type of queuing algorithm is that it is making
   the routing and queuing more complicated.  There is current interest
   in high speed packet switches which have very little protocol
   overhead when handling/routing packets.  This algorithm complicates
   not simplifies the protocol.  The bandwidth being made available is
   increasing.  More T1 (1.5 Mbps) and higher speed links are being used
   all the time.  However, in the history of communications, it seems
   that the demand for bandwidth has always exceeded the supply.  When
   there is wide spread use of optical fiber we may temporarily



Prue & Postel                                                  [Page 10]

RFC 1046                Type-of-Service Queuing            February 1988


   experience a glut of capacity.  As soon as 1 gigabit optical fiber
   link becomes reasonably priced, new applications will be created to
   consume it all.  A single full motion high resolution color image
   system can consume, as an upper limit, nearly a gigabit per second
   channel (30 fps X 24 b/pixel X 1024 X 1024 pixels).

   In the study of one gateway, Dave Clark discovered that the per
   datagram processing of the IP header constituted about 20% of the
   processing time.  Much of the time per datagram was spent on
   restarting input, starting output and queuing datagrams.  He thought
   that a small additional amount of processing to support Type-of-
   Service would be reasonable.  He suggests that even if the code does
   slow the gateway down, we need to see if TOS is good for anything, so
   this experiment is valuable.  To support the new high speed
   communications of the near future, Dave wants to see switches which
   will run one to two orders of magnitude faster.  This can not be done
   by trimming a few instructions here or there.

   From a practical perspective, the problem this algorithm is trying to
   solve is the lack of low delay service through the Internet today.
   Implementing only the low delay queuing portion of this algorithm
   would allow the Internet to provide a class of service it otherwise
   could not provide.  Requesters of this class of service would not get
   it for free.  Low delay class of datagram streams get low delay at
   the cost of reliability and throughput.


























Prue & Postel                                                  [Page 11]