RFC 1046

RFC 1046: A Queuing Algorithm to Provide Type-of-Service for IP Links 🎀

Bestie, this is RFC 1046 from the Network Working Group 💖. Its authors are W. Prue and J. Postel, both from ISI, and it's dated February 1988. The header doesn't name a category, but the Status section calls it an "idea paper" 💅. The header also doesn't list anything it obsoletes or updates 🌸.

---

Status of this Memo ✨

okay so this memo is basically exploring how Type-of-Service could be implemented on the Internet 🦋. It describes a queuing method that can give you the different classes of service. The technique also stops one class from eating all the resources or locking out the other classes, so no main character hogging the bandwidth 💅🙈. 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 lets you choose anything from none to all of these service types: low delay, high throughput, and high reliability 💖. It also has a chunk for a priority pick from 0-7 ✨. Here's the tea though: so far, nothing describes what should be done with these parameters 😭. This discussion proposes an approach for providing the different classes of service and priorities you can request in the TOS field 👑.

Desired Attributes ✨

Let's think about how we actually 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 💀.

Low delay class of service should be able to zip 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 cares more about 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 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 is low enough that a sending node can provide the MGD service 🧚.

Heads up: low delay class of service is not the same as low Round Trip Time (RTT) 🙅‍♀️. Class of service is unidirectional, so it applies in one direction only 🛤️. 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 📬.

TCP might perform way better 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 whenever 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 care less about 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 📚.

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 has 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 imply that the application sets the service based on the knowledge it has during the session. Thus, the application should have control of this setting 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 cannot 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 🦋.

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 ✨

okay so for datagrams that don't ask for any of the three classes of service 🫶, you queue them on whichever of the two queues gives the least delay, the high throughput queue or the high reliability queue. if one queue is full, they go on the other one. if both are full, you follow the source quench procedure for regular class of service (see RFC-1016), not the procedure for the queue the datagram failed to get onto 😭

in the service rates discussion below, the high throughput queue gets served three times for every two times the high reliability queue does. so to compare the two queue lengths fairly, bump the high reliability queue's length up by 50% (in this example) 🌸 a simpler version is to just queue new data on whichever queue is shortest. the slower service rate queue will quickly grow bigger than the faster one, and new data will land on the proper queue anyway. the catch is that this leads to more packet reordering than the first method. 💅

Service Rates 🎀

in this discussion, a higher service rate means a queue, when it's non-empty, eats up a bigger percentage of the available bandwidth than a lower service rate queue. ngl it still won't block the lower service rate queue, even if it's 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. high throughput needs the most bandwidth and high reliability needs a medium amount. you could get this split with the pattern 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, so we send all of the high throughput data at one time, not mixed in with the other classes of service. keeping them together may help higher level protocols, like TCP, as described above. and it still has to stay within the allowed service rate of the available bandwidth 💖

these service rates are suggestions, bestie. some simplifications can be considered, like having only two routing classes: low delay, and other. 🦋

Priority 👑

you can pick 8 levels of priority, 0-7, on top of whichever class of service you selected. to keep the least priority requests from getting blocked forever, we have to give preempted datagrams frustration points every time a higher priority request cuts in line in front of them. so if a low priority datagram waits, it will always get through, even when it's 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 queues it on the appropriate queue, ahead of all the datagrams with lower priority. each datagram that got preempted has its priority raised (locally). priority data won't bump a lower priority datagram off its queue and throw it away. if the queue is full, the newest data gets discarded, priority or not. priority preemption only happens within the class of service queue the priority data is targeted at. a request specifying regular class of service contends on whichever queue it was placed on, high throughput or high reliability. main character energy, honestly ✨

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 gets preempted, increment the value by one. let's look at an example with a multiplier of 2. a priority 6 buffer starts with an initial local value of 12. a new priority 7 datagram would have a local value of 14. if 2 priority 7 datagrams arrive and preempt the priority 6 datagram, its local value gets incremented to 14. it can't be preempted anymore. after that, it has the same local value as a priority 7 datagram and won't be preempted within this node. so in this example, a priority 0 datagram can be preempted by no more than 14 higher priority datagrams. the priority is only raised locally in the node, so the datagram could get preempted again in the next node on the route 🧚

priority queuing changes the effects we were getting from the low delay queuing described above. once a buffer was queued, you could determine the delay a datagram would see. when we accepted low delay data, we could guarantee a certain maximum delay. with this addition, if the datagram requesting low delay doesn't 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. so 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 queue size is reduced, the chit scheme described below will still 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 are requested, and 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, 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 requests multiple classes of service, it's quite possible that datagram reordering will occur. if one queue is full, causing the other queue to be used for some of the data, the 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 the 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's difficult for low delay service requests to consume the bandwidth allocated to them. to do so, low delay users have to keep the small queue continuously non-empty, and that's hard to do with a small queue. traffic flow has been shown to be bursty in nature. so 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 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, then 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 class's 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, which prevents excessive build up. it provides some smoothing of the percentage allocation over time, but it 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 ✨

okay so bestie, here's the vibe check 🫶 when the output speed and volume match the input speed and volume, the queues just don't get big 💅 like not even a little. and if the queues never grow large enough to blow past the guaranteed low delay performance, then honestly? no queuing algorithm other than first in, first out, should be used 🌸 FIFO is still giving main character energy in that situation.

the algorithm could be switched on once the main queue size goes over a certain threshold 🦋 the routing node can keep checking for queue build up every so often 👀. this queuing algorithm can be turned on when the maximum delays will exceed the allowed nodal delay for the low delay class of service ✨ and it can be turned back off once queue sizes stop being a problem 💖

Issues 💅

okay so there are a few things we need to sort out before type of service queuing like this should actually get implemented 😭

first up: what percentage of the bandwidth should each class of service eat, assuming there's an infinite supply of datagrams for each class? 🍓 and what maximum delay (MGD) should be guaranteed per node for low delay datagrams? 🧚

then there's routing. it's possible to find a more optimal route if the queue sizes for each class of service get factored into the routing decision 🗺️ but that adds extra overhead and complexity to every routing node 🙈 and honestly that might be an unacceptable amount of extra complexity, ngl.

how are we gonna stop people from hogging the more desirable classes of service and the higher priorities? 👑 the algorithm kinda helps by limiting queue sizes, especially the low delay queue size, but it seems likely we'll want to instrument the number of datagrams requesting each Type-of-Service and priority 💜 when a datagram requests multiple classes of service, bump the instrumentation count once, based on the queue that's actually used, checking in this order: low delay, high throughput, high reliability, then regular. if instrumentation shows an excessive imbalance, Internet operations can hand it to administrators to deal with 🫶 this instrumentation would show the distribution of the types of service Internet users actually request, and that info can be used to tune the Internet to match what users demand 🔥

now, will the routing algorithms in use today have problems 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 😭 which makes me wonder: would TCP have to be more sophisticated in its round trip time estimator? 🤔

okay, the big objection is that this algorithm makes routing and queuing more complicated 💀 there's current interest in high speed packet switches that have very little protocol overhead when handling and routing packets, and this algorithm complicates the protocol instead of simplifying it. the bandwidth being made available is increasing though 🌈 more T1 (1.5 Mbps) and faster links are showing up all the time. but historically, demand for bandwidth has always exceeded supply 😤 when optical fiber is widely used we may temporarily experience a glut of capacity, but as soon as a 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 🧚 and 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, bestie. low delay class of datagram streams get low delay at the cost of reliability and throughput 💔