doc: Add RFC documents

1 files changed, 619 insertions, 0 deletions

diff --git a/doc/rfc/rfc1046.txt b/doc/rfc/rfc1046.txt
new file mode 100644
index 0000000..0229856
--- /dev/null
+++ b/doc/rfc/rfc1046.txt
@@ -0,0 +1,619 @@
+
+
+
+
+
+
+Network Working Group                                            W. Prue
+Request for Comments:  1046                                    J. Postel
+                                                                     ISI
+                                                           February 1988
+
+
+      A Queuing Algorithm to Provide Type-of-Service for IP Links
+
+Status of this Memo
+
+   This memo is intended to explore how Type-of-Service might be
+   implemented in the Internet.  The proposal describes a method of
+   queuing which can provide the different classes of service.  The
+   technique also prohibits one class of service from consuming
+   excessive resources or excluding other classes of service.  This is
+   an "idea paper" and discussion is strongly encouraged.  Distribution
+   of this memo is unlimited.
+
+Introduction
+
+   The Type-of-Service (TOS) field in IP headers allows one to chose
+   from none to all the following service types; low delay, high
+   throughput, and high reliability.  It also has a portion allowing a
+   priority selection from 0-7.  To date, there is nothing describing
+   what should be done with these parameters.  This discussion proposes
+   an approach to providing the different classes of service and
+   priorities requestable in the TOS field.
+
+Desired Attributes
+
+   We should first consider how we want these services to perform.  We
+   must first assume that there is a demand for service that exceeds
+   current capabilities.  If not, significant queues do not form and
+   queuing algorithms become superfluous.
+
+   The low delay class of service should have the ability to pass data
+   through the net faster than regular data.  If a request is for low
+   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 concerned
+   with promptness of delivery than guaranteed delivery.  The Internet
+   should provide a Maximum Guaranteed Delay (MGD) per node, or better,
+   if the datagram successfully traverses the Internet.  In the worst
+   case, a datagram's arrival will be MGD times the number of nodes
+   traversed.  A node is any packet switching element, including IP
+   gateways and ARPANET IMP's.  The MGD bound will not be affected by
+   the amount of traffic in the net.  During non-busy hours, the delay
+   provided should be better than the guarantee.  If the delay a
+
+
+
+Prue & Postel                                                   [Page 1]
+
+RFC 1046                Type-of-Service Queuing            February 1988
+
+
+   satellite link introduces is less than the MGD, that link should be
+   considered in the route.  If however, the MGD is less than the
+   satellite link can provide, it should not be used.  For this
+   discussion it is assumed that delay for individual links are low
+   enough that a sending node can provide the MGD service.
+
+   Low delay class of service is not the same as low Round Trip Time
+   (RTT).  Class of service is unidirectional.  The datagrams responding
+   to low delay traffic (i.e., Acking the data) might be sent with a
+   high reliability class of service, but not low delay.
+
+   The performance of TCP might be significantly improved with an
+   accurate estimate of the round trip time and the retransmission
+   timeout.  The TCP retransmission timeout could be set to the maximum
+   delay for the current route (if the current route could be
+   determined).  The timeout value would have to be redetermined when
+   the number of hops in the route changes.
+
+   High throughput class of service should get a large volume of data
+   through the Internet.  Requesters of this class are less concerned
+   with the delay the datagrams have crossing the Internet and the
+   reliability of their delivery.  This type of traffic might be served
+   well by a satellite link, especially if the bandwidth is high.
+   Another attribute this class might have is consistent one way
+   traversal time for a given burst of datagrams.  This class of service
+   will have its traversal times affected by the amount of Internet
+   load.  As the Internet load goes up, the throughput for each source
+   will go down.
+
+   High reliability class of service should see most of its datagrams
+   delivered if the Internet is not too heavily loaded.  Source Quenches
+   (SQ) should not be sent only when datagrams are discarded.  SQs
+   should be sent well before the queues become full, to advise the
+   sender of the rate that can be currently supported.
+
+   Priority service should allow data that has a higher priority to be
+   queued ahead of other lower priority data.  It is important to limit
+   the amount of priority data.  The amount of preemption a lower
+   priority datagram suffers must also be limited.
+
+   It is assumed that a queuing algorithm provides these classes of
+   service.  For one facility to be used over another, that is, making
+   different routing decisions based upon the TOS, requires a more
+   sophisticated routing algorithm and larger routing database.  These
+   issues are not discussed in this document.
+
+
+
+
+
+
+Prue & Postel                                                   [Page 2]
+
+RFC 1046                Type-of-Service Queuing            February 1988
+
+
+Applications for Class of Service
+
+   The following are examples of how classes of service might be used.
+   They do not necessarily represent the best choices, but are presented
+   only to illustrate how the different classes of service might be used
+   to advantage.
+
+   Interactive timesharing access using a line-at-a-time or character-
+   at-a-time terminal (TTY) type of access is typically low volume
+   typing speed input with low or high volume output.  Some Internet
+   applications use echoplex or character by character echoing of user
+   input by the destination host.  PC devices also have local files that
+   may be uploaded to remote hosts in a streaming mode.  Supporting such
+   traffic can require several types of service.  User keyboard input
+   should be forwarded with low delay.  If echoplex is used, all user
+   characters sent and echoed should be low delay to minimize the
+   echoing delay.  The computer responses should be regular or high
+   throughput depending upon the volume of data sent and the speed of
+   the output device.  If the computer response is a single datagram of
+   data, the user should get low delay for the response, to minimize the
+   human/computer interaction time.  If however the output takes a while
+   to read and digest, low delay computer responses are a waste of
+   Internet resources.  When streaming input is being sent the data
+   should be sent requesting high throughput or regular class of
+   service.
+
+   The IBM 3270 class of terminals typically have traffic volumes
+   greater than TTY access.  Echoplex is not needed.  The output devices
+   usually handle higher speed output streams and most sites do not have
+   the ability to stream input.  Input is typically a screen at a time,
+   but some PC implementations of 3270 use a variation of the protocol
+   to effectively stream in volumes of data.  Low delay for low volume
+   input and output is appropriate.  High throughput is appropriate for
+   the higher volume traffic.
+
+   Applications that transfer high volumes of data are typically
+   streaming in one direction only, with acks for the data, on the
+   return path.  The data transfer should be high throughput and the
+   acks should probably be regular class of service.  Transfer
+   initiation and termination might be served best with low delay class
+   of service.
+
+   Requests to, and responses from a time service might use low delay
+   class of service effectively.
+
+   These suggestions for class of service usage implies that the
+   application sets the service based on the knowledge it has during the
+   session.  Thus, the application should have control of this setting
+
+
+
+Prue & Postel                                                   [Page 3]
+
+RFC 1046                Type-of-Service Queuing            February 1988
+
+
+   dynamically for each send data request, not just on a per
+   session/conversation/transaction basis.  It would be possible for the
+   transport level protocol to guess (i.e., TCP), but it would be sub-
+   optimal.
+
+Algorithm
+
+   When we provide class of service queuing, one class may be more
+   desirable than the others.  We must limit the amount of resources
+   each class consumes when there is contention, so the other classes
+   may also operate effectively.  To be fair, the algorithm provides the
+   requested service by reducing the other service attributes.  A
+   request for multiple classes of service is an OR type of request not
+   an AND request.  For example, one can not get low delay and high
+   throughput unless there is no contention for the available resources.
+
+Low Delay Queuing
+
+   To support low delay, use a limited queue so requests will not wait
+   longer than the MGD on the queue.  The low delay queue should be
+   serviced at a lower rate than other classes of service, so low delay
+   requests will not consume excessive resources.  If the number of low
+   delay datagrams exceeds the queue limit, discard the datagrams.  The
+   service rate should be low enough so that other data can still get
+   through. (See discussion of service rates below.)  Make the queue
+   limit small enough so that, if the datagram is queued, it will have a
+   guaranteed transit time (MGD).  It seems unlikely that Source Quench
+   flow control mechanisms will be an effective method of flow control
+   because of the small size of the queue.  It should not be done for
+   this class of service.  Instead, datagrams should just be discarded
+   as required.  If the bandwidth or percentage allocated to low delay
+   is such that a large queue is possible (see formula below), SQs
+   should be reconsidered.
+
+   The maximum delay a datagram with low delay class of service will
+   experience (MGD), can be determined with the following information:
+
+      N = Queue size for low delay queue
+      P = Percentage of link resources allocated to low delay
+      R = Link rate (in datagrams/sec.)
+                      N
+      Max Delay =   -----
+                    P * R
+
+   If Max Delay is held fixed, then as P and R go up, so does N.  It is
+   probable that low delay service datagrams will prove to be, on the
+   average, smaller than other traffic.  This means that the number of
+   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 Queuing
+
+   To support high reliability class of service, use a queue that is
+   longer than normal (longer queue means higher potential delay).  Send
+   SQ earlier (smaller percentage of max queue length) and don't discard
+   datagrams until the queue is full.  This queue should have a lower
+   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 longer
+   queueing times for this class of service.
+
+   This queuing procedure will only be effective for Internet
+   unreliability due to congestion.  Other Internet unreliability
+   problems such as high error rate links or reliability features such
+   as forward error correcting modems must be dealt with by more
+   sophisticated routing algorithms.
+
+High Throughput Queuing
+
+   To support high throughput class of service have a queue that is
+   treated like current IP queuing.  It should have the highest service
+   rate.  It will experience higher average through node delay than low
+   delay because of the larger queue size.
+
+   Another thing that might be done, is to keep datagrams of the same
+   burst together when possible.  This must be done in a way that will
+   not block other traffic.  The idea is to deliver all the data to the
+   other end in a contiguous burst.  This could be an advantage by
+   allowing piggybacking acks for the whole burst at one time.  This
+   makes some assumptions about the overlying protocol which may be
+   inappropriate.
+
+Regular Service Queuing
+
+   For datagrams which request none of the three classes of service,
+   queue the datagrams on the queue representing the least delay between
+   the two queues, the high throughput queue or the high reliability
+   queue.  If one queue becomes full, queue on the other.  If both
+   queues are full, follow the source quench procedure for regular class
+   of service (see RFC-1016), not the procedure for the queue the
+   datagram failed to attain.
+
+   In the discussion of service rates described below, it is proposed
+   that the high throughput queue get service three times for every two
+   times for the high reliability queue.  Therefore, the queue length of
+   the high reliability queue should be increased by 50% (in this
+   example) to compare the lengths of the two queues more accurately.  A
+
+
+
+Prue & Postel                                                   [Page 5]
+
+RFC 1046                Type-of-Service Queuing            February 1988
+
+
+   simplification to this method is to just queue new data on the queue
+   that is the shortest.  The slower service rate queue will quickly
+   exceed the size of the faster service rate queue and new data will go
+   on the proper queue.  This however, would lead to more packet
+   reordering than the first method.
+
+
+Service Rates
+
+   In this discussion, a higher service rate means that a queue, when
+   non-empty, will consume a larger percentage of the available
+   bandwidth than a lower service rate queue.  It will not block a lower
+   service rate queue even if it is always full.
+
+   For example, the service pattern could be; send low delay 17% of the
+   time, high throughput 50% of the time, and high reliability 33% of
+   the time.  Throughput requires the most bandwidth and high
+   reliability requires medium bandwidth.  One could achieve this split
+   using a pattern of L, R,R, T,T,T, where low delay is "L", high
+   reliability is "R", and high throughput is "T'.  We want to keep the
+   high throughput datagrams together.  We therefore send all of the
+   high throughput data at one time, that is, not interspersed with the
+   other classes of service.  By keeping all of the high throughput data
+   together, we may help higher level protocols, such as TCP, as
+   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]
+
\ No newline at end of file