IEN-182 Issues in Buffer Management Bolt Beranek and Newman Inc. Eric C. Rosen May 1980 IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen Table of Contents 1 Introduction.......................................... 1 2 Overview.............................................. 2 3 General Considerations of Buffer Management........... 3 4 Buffer Management with an Ample Supply of Buffers............................................... 9 4.1 Buffering for Output............................... 16 4.2 Buffering for Input................................ 18 4.3 Buffering for Generating Control Messages.......... 28 4.4 Buffering Data at the Source Node.................. 29 5 Buffer Management with a Shortage of Buffers (ARPANET).............................................. 32 -i- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen 1 Introduction This note is an abridged extract from BBN Report No. 4473, "ARPANET Routing Algorithm Improvements, Volume 1", by Rosen et al. It discusses the issues of buffer management in the switches which implement a network and is based on experiences gained during the evolution of the ARPANET. Since the Internet is itself a network, and hosts or gateways implementing TCP, IP, and other protocols have similar buffer management design decisions, this IEN is intended to distill some of the ARPANET issues and present them to a wider audience currently grappling with some of the same problems. The original report is quite large (500 pages). This is the first of several such extracts we plan to produce to serve as background for the internet project work. The report was first published in August 1980. Some of the terminology used may cause confusion if associated with internet work, for example "reassembly". This note discusses mechanisms purely internal to the ARPANET, which itself has many similarities to internet and TCP mechanisms in internet hosts. The ARPANET IMPs use retransmission, ACKS, flow control/windowing, fragmentation and reassembly, out-of-order sequencing, and other mechanisms which create a serial byte- -1- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen stream service based on a datagram network, much as TCP does. The issues to be discussed in these notes are at least partially applicable to the internet mechanisms, including TCP in hosts, as well as IP in gateways, since those mechanisms are functionally similar in the services they are intended to implement. We propose no solutions here, such as buffer mechanisms for TCP implementations, but rather intend to explore the issues which motivated the IMP implementation in the ARPANET, to help TCP and internet implementors in their similar tasks of creating an Internet. Anyone interested in seeing how the issues raised in this discussion can be applied to the ARPANET will want to see Chapter 7 of BBN Report No. 4088, as well as Chapter 1.5 of BBN Report No. 4473, which are not included in this excerpt. Copies of those reports are available from the author. 2 Overview We will begin by considering, in general, the function of a buffer management scheme in a packet-switching network. We will discuss the way in which such a procedure might be designed in an "ideal" network, where there is an ample supply of buffers. We will see that, no matter how many buffers there are, careful -2- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen buffer management is essential to good performance. We will then discuss the way in which procedures designed for an ideal network need to be modified for a network (like the ARPANET and most other networks) in which buffer space is a scarce resource. Finally, we will compare the current ARPANET buffer management procedures to the procedures we develop, and will recommend changes to the former. 3 General Considerations of Buffer Management A network node must execute many different functions for which it requires buffers. Among these functions are: 1) Transmitting packets on the various output devices (inter-node trunks or host access lines). Packets must be buffered while queuing for these devices, while in transmission on these devices, and (sometimes) while awaiting acknowledgment from the node or host on the other side of the device. 2) Receiving packets from the various input devices. 3) Reassembling messages so they can be transmitted to the destination host. 4) Processing packets. Packets must be buffered while the -3- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen CPU is processing them, and they may have to occupy buffers while queuing for a busy processor. 5) Creating protocol or control messages. The IMPs often need to create control messages in order to run the many protocols necessary for proper network operation. It should be clear that, no matter how many buffers exist in a node, a "laissez-faire" approach to buffer management cannot possibly succeed. In a laissez-faire approach, buffers are allocated to the various processes that need them on a first- come, first-serve basis. Any process, at any time, can obtain any number of buffers that are available at that time. No import is given to considerations of fairness or of overall network performance. Therefore, a laissez-faire scheme will be prone to lock-up. Suppose, for example, that the output processes in some node have taken all the buffers. Then no input can be done. If, as is often the case, the output processes cannot free their buffers until an acknowledgment is received from some other node, and if acknowledgments cannot be received because no buffers are available for input, then there is a deadlock, and the buffers will never be freed. It is important to understand that this sort of deadlock is not caused by a SHORTAGE of buffer space. No matter how much buffer space is available, it is always possible, for example, that the network will try to utilize some output -4- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen device at a higher capacity than it is capable of handling. With a laissez-faire approach to buffer management, there is no bound on the number of buffers which may end up holding packets for the overloaded device. The possibility of deadlock cannot be eliminated by adding more buffers. This particular sort of deadlock is just one example of a more general situation. For the network to perform well, all the processes in the nodes must be able to run at an adequate rate. This cannot be guaranteed unless each process is guaranteed the resources that it needs. Unless each process is explicitly prevented from "hogging" resources, other processes may be unable to run, and the network will not, in general, be able to give adequate performance. It must be understood, of course, that the buffer supply is not the only resource which must be managed in order to prevent hogging. Similar sorts of deadlocks can occur if some processes are allowed unrestricted access to CPU cycles, thereby preventing others from ever running at all. Although this chapter is primarily concerned only with management of the buffer space resource, management of the CPU resource is equally important. Furthermore, it must not be imagined that deadlocks are the only sort of performance degradation against which a buffer management scheme must protect. Freedom from deadlocks is only a necessary, not a sufficient, condition of adequate network -5- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen performance. A scheme which dedicates some small number of buffers to each process, while taking a laissez-faire approach to the large majority of the buffers, may prevent deadlocks, since it will permit each process to run at some slow but non-zero rate. However, such an approach may not allow all the processes to run at "adequate" speeds; if some processes are running "too slowly," then ordinary users of the network may not be able to distinguish that situation from the situation where there is a deadlock. The problem is the general one of "fairness." The purpose of a buffer management scheme is to ensure that no process gets either more or less than its fair share of the buffer resource. (It is worth noting that simply specifying a protocol in some formal language, i.e., in a way which is not implementation-specific, and proving it to be deadlock-free, does not guarantee that the protocol will perform fairly. Such formal specifications almost never address such important issues as buffer management or fairness. In fact, by abstracting the protocol specification from implementation considerations, such issues are only obscured and made easier to overlook.) Of course, such notions as "adequate performance," "too slow," and "fair share" are hopelessly qualitative. Implementing a buffer management scheme in an actual network would require giving some quantitative interpretation to these notions. The precise way in which these notions are quantified would depend on the design -6- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen objectives of the particular network, as well as its performance characteristics, and it would probably require a large degree of arbitrariness. This does not mean, though, that the qualitative considerations cannot guide the development of a buffer management procedure, but only that any such procedure should be sufficiently parameterized so that it can be tuned to meet the PARTICULAR requirements of a PARTICULAR network. The considerations raised above do not mean that there should be no sharing of buffers among processes, but only that the sharing should be controlled so that considerations of fairness and overall network performance can play a role. There is, of course, a disadvantage to restricting the amount of sharing of buffers among processes. If a buffer is available for process A, but not for process B, then there will be situations in which a buffer must lie idle, because process A does not need it, even though process B really has a use for it. In these particular situations, the performance of process B (and possibly of the whole node) may be degraded. The justification for keeping the buffer idle though is that it is possible that process A will have a need for the buffer before process B would finish with it, and that if such a situation were to arise, overall performance would be improved by keeping the buffer idle until needed by process A. The validity of the justification -7- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen depends on the probability that process A really will need the buffer before process B would finish with it. This sort of probability is very difficult to evaluate A PRIORI. Furthermore, the probability may change as network conditions change. This suggests that we might want to vary the number of buffers reserved for particular processes as a function of the utilization of resources by the various processes. That is, the buffer management scheme may need feedback from a more general congestion control scheme which can measure the pattern of resource utilization and determine whether it is satisfactory. This is only natural. The purpose of a congestion control scheme is to ensure that the demands placed on resources in the network do not exceed the capacity of the resources, AND that the resources are allocated to the demands in the way that yields best overall network service. In order to achieve these goals, the algorithm (or at least the parameters of the algorithm) used to assign resources to demands may need to change as the pattern of demands changes. A buffer management scheme is an algorithm for assigning one particular kind of resource (buffers) to the demands made on that resource. Hence it is just a part of a congestion control scheme, and may need to interact with the other parts of the scheme for best overall performance. -8- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen 4 Buffer Management with an Ample Supply of Buffers If we were designing a new network, with an ample amount of buffer space, one of the important desiderata of the buffer management scheme would be to enable all output devices (i.e., hosts and inter-node trunks) to run at their rated capacity. Transmission of packets over an output device is usually controlled by means of a protocol which requires the packet to remain buffered until a positive acknowledgment is received. The number of buffers needed to run such a device at full capacity is a function both of the transmission speed of the device and of the time it takes (on the average) for acknowledgments to return, which itself is a function of the physical length of the transmission line (speed-of-light propagation delay) and the processing latencies of the device which is receiving the output. For each output device it is relatively straightforward to compute this number of buffers, at least approximately. To ensure that each output device can always run at its rated capacity, the buffer management scheme must "dedicate" that number of buffers to the particular output device in question. It is important to understand just what it means to "dedicate N buffers" to a particular device or process. It does NOT means that certain physical buffers (i.e., physical areas of memory) are set aside for use only by that process. It means -9- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen only that the process should always be able to obtain N buffers whenever it has a need for N buffers. There is no reason at all why the same N physical buffers should be used each time. To see exactly what this means in practice, we must consider the mechanism whereby a buffer is (logically) moved from a source process to a destination process. At any given time, a buffer which is not free is considered to be under the control of some process. When that process has completed its processing of the buffer, it must somehow release control of it. In some cases (e.g., a packet has been transmitted on an inter-node trunk and an acknowledgment for it received) the packet which is in the buffer is no longer needed at that node, and the buffer can be freed. In other cases, however, control of the buffer must be turned over to some other process. An example is a packet which is under control of the forwarding process of the routing algorithm. Once the routing algorithm decides where to forward the packet, the buffer in which it resides must be turned over to some output process which will ensure its transmission over the appropriate output device. Before turning the buffer over to the next process, it must be determined whether doing so would prevent any other process from obtaining the number of buffers that have been "dedicated" to it. If so, the buffer cannot be turned over to that destination process. If the packet residing in the buffer is under control of some sort of reliable -10- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen transmission procedure (e.g., the ARPANET's IMP-IMP protocol), the buffer can simply be freed. This will not result in loss of the packet, since the reliable transmission procedure will ensure that the packet is seen again, and again, until it is finally accepted. This is usually the case in the ARPANET with a packet that has been received from a neighboring node. If the receiving node discards the packet without sending an acknowledgment to the transmitting node, the latter node can usually be relied upon to send the packet again. (Note that this implies that, in the ARPANET, the receiving node cannot send an inter-node acknowledgment for a packet until that packet has been turned over to its final output process.) On the other hand, some packets may not be under the control of a reliable transmission procedure. This may be the case with control packets that are created in the node itself and which must be transmitted to some other node for reasons determined by some end-end protocol. Freeing the buffer occupied by such a packet may result in loss of the packet. Since this is undesirable, if the buffer cannot be given to its destination process, it must be returned to the source process, where it must sit on some queue until some future time when it can be accepted by the destination process. In general, when making the determination as to whether a buffer can be turned over to a particular process, it is not -11- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen sufficient merely to consider the number of buffers already in control of the destination process. One must also take into consideration the source process of the buffer. After all, there may be cases in which the source process and the destination process share a common pool of buffers. In such cases, buffer management considerations can never cause the destination process to refuse the buffer, no matter how many buffers are already under its control. It follows that the correct decision as to whether a buffer ought to be refused cannot be made without knowledge of its source process. Also, only by considering the buffer's source process can it be determined whether or not the buffer, if refused, will be freed. This is important to know, since ONCE IT HAS BEEN DECIDED THAT A PARTICULAR PACKET CANNOT BE DISCARDED AT WILL, NO PROCESS SHOULD EVER REJECT THE PACKET AS A RESULT OF BUFFER MANAGEMENT CONSIDERATIONS. Any process that will not be able to obtain an adequate number of buffers if the packet is accepted will also be unable to obtain an adequate number of buffers if the packet is rejected. After all, rejection of the packet will merely cause its buffer to be held in a queue somewhere else in the node until it can be accepted. Since the buffer cannot be freed, it will not become available for use by any other process, so there is no point in refusing it. Rejecting the packet will serve only to increase its delay, without any countervailing advantage. This may mean that the -12- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen number of buffers under the control of a given process exceeds the nominal maximum which we have decided to allow to that process. The point of the buffer management scheme, however, is not so much to prevent a process from obtaining more than some maximum number of buffers as to ensure that a process can always obtain some minimum number of buffers. In the situation just described, holding one process to a certain maximum number of buffers does not help any other process to obtain its minimum. And while moving the buffer from the source process to the destination process in this situation may cause the source process to have less than its minimum number of buffers, it cannot hurt the performance of the source process, which, after all, has already finished with its use of the buffer. There is certainly no point in forcing a process to keep control of a buffer with which it is finished; that could serve only to degrade overall performance. To put the point another way, once the node has committed itself not to discard the packet, all buffer management considerations are otiose. Of course, this is not to say that a packet to which the node is committed ought never to be refused by any process in the node, but only that considerations of buffer management can play no role in the refusal. There are many resources other than buffer space which may be in short -13- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen supply; management of these resources may well dictate the rejection of a packet to which the node is committed. However, the same considerations apply. A packet should never be rejected due to resource management considerations unless rejecting it will free resources which would not be free were the packet accepted. Of course, this principle may have unfortunate side- effects that must be controlled. If two packets are competing for buffer space, and one of the packets is discardable while the other is not, the non-discardable packet has an advantage, since it cannot be refused. For example, in the ARPANET, packets which an IMP receives from a neighboring IMP are discardable, since they are controlled by a reliable transmission procedure (the IMP-IMP protocol) and will be retransmitted if dropped. Packets received from a host, however, are controlled by the 1822 protocol, which does not provide for retransmissions, and which in fact assumes that the IMP will not drop a packet once it has fully received it. This fact gives packets received from hosts an unfair advantage over packets received from neighboring IMPs in the competition for buffer space. This is a particularly unhappy situation, since it can lead to the violation of one of the basic principles of congestion control, namely that packets already in the network should be favored over packets just -14- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen entering the network. The correct solution to this problem, of course, is to refrain from using protocols which force a node to treat a packet as non-discardable before all the resources needed to process that packet have been obtained. We will return to this issue when we discuss the particular case of buffer management in the ARPANET. It should also be noted that moving a buffer from a source process to a destination process typically requires the mediation of a third process which serves as the Dispatcher. In the ARPANET, this is the function of the TASK process. While a buffer is queued for or being processed by the Dispatcher, it is still considered to be under the control of the source process, for purposes of buffer management. The reason, of course, is that the decision as to whether a particular destination process must refuse the buffer is independent of whether the buffer is being passed to it directly by the source process, or whether it is being passed to it by the Dispatcher. Therefore, it makes no sense to treat the Dispatcher itself as a source process. Similarly, since the Dispatcher itself can never refuse a buffer, it makes no sense to treat it as a destination process either. The use of a dispatching process should be transparent to the buffer management scheme. Sometimes a buffer may need to be under the simultaneous -15- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen control of two distinct processes in order for its packet to be processed. If this is ever the case, the buffer management scheme must ensure that whenever the buffer can be assigned to one process, it can also be assigned to the other. If the buffer cannot be processed unless controlled by both processes, then a situation where it can be controlled by one process but not the other makes no sense at all. Such a situation would simply result in a waste of space, by allowing a buffer to be occupied by a packet which cannot be processed. This illustrates a most important point in the design of a buffer management scheme. The purpose of buffer management is to ensure good overall network performance. Therefore, ONE CANNOT DETERMINE HOW MANY BUFFERS NEED TO BE DEDICATED TO A PROCESS BY CONSIDERING THAT PROCESS IN ISOLATION. RATHER, ONE MUST CONSIDER THE ROLE THAT THAT PARTICULAR PROCESS PLAYS IN DETERMINING OVERALL NETWORK PERFORMANCE. 4.1 Buffering for Output We now consider, in general, which sorts of processes in the network nodes need to have buffers dedicated to them. Whenever a particular device is running at close to its maximum capacity and the demands on the device vary stochastically, the device will sometimes be overloaded. That is, although the -16- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen device is fully utilized during some interval by the presence of n packets, a larger number of packets destined for that device will arrive during that interval. If the device is overloaded in the steady state, then some sort of congestion control procedure must be brought into effect to reduce the demand for that particular device. We are presently assuming, though, that the device is not overloaded in the steady state, and that any intervals of overload are caused by the variance in the demand. In such a situation, it is desirable to smooth the effects of the temporary overload by buffering the excess packets. So the buffer management system should allow more buffers to be assigned to an output device at a given time than are strictly needed to run that device at full capacity. The question is whether a certain number of excess buffers should be "dedicated" to each device (in the sense described above), or whether the excess buffers should be in a common pool, sharable among all the output devices on a first-come, first-served basis. In this case, it seems that the buffers ought to be sharable. If all these buffers end up queued to a single output device, no other device is thereby prevented from running at full speed, since each device still has its own supply of dedicated buffers. Therefore there is no reason to strictly partition this additional buffer space. -17- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen One might argue that the number of buffers dedicated to a particular device should only be enough to run the device at its AVERAGE rate, not at its maximum or peak rate. After all, the purpose of having a sharable pool of excess buffers is to smooth the effects of stochastic peaks. But stochastic peaks occur whenever the average utilization of a device is exceeded, not necessarily when its maximum utilization is exceeded. This argument, however, ignores the fact that several devices may exceed their average utilization at the same time. If this happens, and if there are not enough buffers dedicated to each device to run it at full speed, then some devices may be under- utilized while others will be over-utilized, which is what the buffer management scheme ought to try avoid as far as possible (at least, if the supply of buffers is ample). 4.2 Buffering for Input We have yet to discuss the issue of whether it is necessary to dedicate buffers to the input devices, as well as to the output devices. Packets may arrive at a node either from a neighboring node, or from a locally-attached host. Receiving and processing a packet requires a buffer. Even if all output devices are running at full speed and have their full complement -18- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen of buffers, it is still necessary to dedicate a certain number of additional buffers to the input devices. Failure to do so can result in the stopping of all input whenever all the output devices are fully utilized. At first glance, this might seem like a desirable effect. After all, there is no point in accepting input when the output devices are already overloaded; to do so only leads to congestion. However, there are two problems with this argument: 1) Not all packets which arrive at a node as input will necessarily leave the node as output. Some packets are control packets which may cause the processor to take some action other than simply forwarding the packet somewhere else. The node should always be able to process these packets, no matter what the utilization of its output devices. 2) Packets cannot be processed instantaneously; there is always some latency. It may be the case that although no output buffers are available at the time a packet arrives, there will be buffers available by the time the packet is processed (e.g., by the time the processor determines which output device to route the packet to). If no buffers are available at the time the packet is received, it has to be discarded and re-transmitted, -19- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen thus introducing a potentially large amount of additional delay. This additional delay can be eliminated by having a supply of buffers for input. These arguments show that there should be some buffers available for input over and above those which can be used for output. We have not yet dealt with the issues of how many buffers there should be, and whether they should be sharable among all the input devices. It is sometimes suggested that there should be two buffers dedicated to each input device, to allow "double buffering." However, this is something of a confusion. The point of double buffering is to allow an input to be received while the previous input is being processed. This makes sense if the time it takes to process the previous input is less than the time it takes to receive the current input. Then by the time the input is received, processing of the previous one has been completed, and the buffer which held the previous input can be re-used to receive the next input, while the current input is being processed. The purpose of such a scheme is to ensure that reception of an input is not delayed by the time it takes to process the previous input. It is easy to see though that this scheme is not directly applicable to a packet-switching node. There is no way to guarantee that the time needed to process one packet is less than the time needed to receive the next packet. -20- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen If the processor is busy, so that many packets are queued for it, and the inter-node trunks run at a high speed, so that packets are received very rapidly, merely dedicating two buffers to an input device will not ensure that a buffer is always available to receive the next packet. One might think that this means that a larger number of buffers must be dedicated to each input line. By making the number large enough, we can make the probability of missing an input due to lack of buffers as small as we like. But it would be a mistake to do so. In general (though not invariably), after a packet is input and processed, it will be routed to some output device. There cannot be a shortage of buffers for input unless either all the output devices are heavily loaded (i.e., all the output-dedicated buffers are in use), or the processor itself is overloaded (so that many buffers are queued for the processor). A certain number of input-dedicated buffers are needed to permit input to flow smoothly under such situations, as well as to ensure that control packets can be processed. However, if the node is really congested (i.e., either the output devices or the CPU are overutilized in the steady state), having a large number of input buffers will not smooth the flow; it will result only in larger queues. The number of input-dedicated buffers need only be large enough to enable the processor to run at its full -21- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen capacity while the output devices are also running at full capacity. In order for an output device to run at full capacity, it should always be able to get enough buffers so that it can buffer all in-flight packets for the required period of time while still having a small queue of packets waiting to be sent. Running the processor at full speed requires only enough buffers so that a small number of packets can always be on the queue for the processor. This does not require a large number of buffers to be dedicated to input; even less does it require a large number of buffers to be dedicated to a particular input device. However, as we have pointed out, it does require SOME dedicated buffers. We have now determined that there need not be a very large number of buffers dedicated to input. We have not yet resolved the question of whether these buffers should be sharable among all the input devices, or whether a certain number of buffers should be dedicated to each input device. To answer this question we must determine whether, if the buffers are sharable, some one input device can monopolize the buffer pool, preventing input from any of the other devices. This might well be the case, for three reasons. First, one input device might run at a higher speed than the others. Second, one input device might be more heavily utilized than the others, or might receive shorter -22- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen packets than the others. Third, some artifact of the interrupt structure of the node might tend to favor certain devices over others. (Thus in the ARPANET, each inter-IMP trunk is serviced at a different priority level; naturally, the one that is serviced with the highest priority is favored. This is due to the interrupt structure of the 316, rather than the software.) If any of these conditions hold, some input devices may be able to utilize so many buffers that the others are slowed down. Therefore a small number of buffers should be dedicated to each input device. Another reason for dedicating a few buffers to each input device is the following. Certain inputs are processed at a very high priority level, without any queuing for the processor. These inputs are always control packets, which are not going to be routed to any output device. Furthermore, they are only those few types of control packets which must be processed very quickly. An example is the line up/down protocol packet of the ARPANET. When one IMP sends one of these packets to another, it expects a reply back within a few hundred milliseconds, no matter how congested the processor of the receiving IMP is. The receiving IMP must always be able to receive such packets and to process them immediately, without having to queue them. If this is not done, the line may be brought down spuriously, resulting -23- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen in a significant and needless degradation of network service. In order to ensure rapid processing, at least one buffer must be dedicated to each input device from which control packets of this sort may be received. Furthermore, the use of these buffers is even more restricted than that of other buffers which are input- dedicated. Ordinarily, to say that N buffers are dedicated to input is to say that there must always be N buffers which cannot be given to any process which is not input related. These buffers can, however, be queued to the processor (i.e., to the Dispatcher) after being filled with an input. After all, the main point of having input-dedicated buffers is to enable the processor to continue to look at inputs even if all output devices are running at full capacity. This goal cannot be achieved unless the input buffers can be queued for the processor. The point of this paragraph, on the other hand, is that there be certain sorts of control packets which require IMMEDIATE processing. In order to ensure that a buffer is always available to each input device to process such packets, each input device should have one buffer dedicated to it which is not queueable to ANY other process, including the Dispatcher. Is a single such buffer enough? The feasibility of having protocols which require immediate processing of control packets is clearly dependent on the constraint that such packets be few and far- between. Otherwise, there may just be too many of them to -24- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen process them all "immediately," and the protocol will not work. As long as this constraint is met, a single buffer should be enough. It must be pointed out that the proper use of the non- queueable buffer is often a matter of some subtlety. Suppose a packet is received from some inter-node trunk, and that packet contains node-node acknowledgments (possibly piggybacked on an ordinary data packet) for packets that were transmitted (in the opposite direction) over the same trunk. Suppose further that after the packet is received, there are no more free buffers in the nodes. Clearly, any data in the packet cannot be processed; doing so would require queuing the packet for the processor, thereby violating the rule that each input device have a non- queueable buffer dedicated to it. But what of the acknowledgments -- should they be processed? In the ARPANET, received node-node acknowledgments are processed at the highest priority level, with no queuing. So they CAN be processed without violating the buffer management rules that we have advanced. Furthermore, one might argue that it is really important to process the acknowledgments as soon as possible. After all, processing received acknowledgments can result in freeing buffers. Since, ex hypothesi, there are very few free buffers in the machine, processing the acknowledgments is of -25- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen great importance, and should be done immediately. This argument, however, does not hold under all conditions. When there are very few free buffers in the node, it may be that a large number of buffers are holding packets which have already been transmitted on inter-node trunks, and which are awaiting acknowledgment. In this case, processing the acknowledgments as quickly as possible has a salutary effect on the node's performance. However, there are other conditions which may result in a short supply of free buffers. Suppose, for example, that the node is CPU-bound, i.e., that the processor is overloaded. Then one would expect to find the majority of buffers queued for the processor. (This situation is very common in certain of the more heavily loaded ARPANET nodes.) Since these buffers contain packets which have not yet been transmitted out any inter-node trunk, the buffers cannot possibly be freed as a result of processing acknowledgments. The only way to expedite the freeing of these buffers is to reduce the demand on the processor, especially the demand at the higher priority levels. Thus the best strategy here may be to NOT process the acknowledgments, thereby reducing the processing load. Deciding whether a certain packet should be processed immediately may depend not only on the function of the packet, but on the conditions in the node at that time. This shows again that a buffer management scheme is only part of a more general congestion control strategy, and cannot be expected -26- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen to do the whole job by itself. It must be understood, of course, that although the number of buffers DEDICATED to input may be small, the number of buffers controlled by the input processes (i.e. the number of buffers containing input packets which have not yet been dispatched) may be much larger. In fact, all the buffers that are dedicated to output processes may be under the control of input processes at some time. This may seem paradoxical, but it is easy to see why it is the case. In general, a packet cannot be output unless it has first been input. It makes no sense to refuse to use a buffer for input because one wants to save it for output -- it will never be used for output unless it is used for input first. Therefore, all buffers must be available for input, regardless of the number which are "dedicated" to other processes. (There is one exception to this rule. It may be desirable to save a few buffers for creating control messages, which, being created in the node, are never actually input. These buffers would then be unavailable for input. This is discussed below in greater detail.) To restate the point -- while only a small number of buffers need to be DEDICATED to input, a large number of buffers need to be AVAILABLE to input. -27- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen 4.3 Buffering for Generating Control Messages There are other functions besides input and output for which buffers are required. One such function is the creation of the control messages needed to run the various protocols used by the node. Every so often, the node will have to respond to a certain event by creating a control packet and transmitting it to some destination. Often one node will contain buffers which cannot be freed until a control packet from some other node is received. If a node cannot create the necessary control packets because it cannot get buffers for them, then deadlocks are possible. Even if deadlocks are avoided, good network performance can depend on the timely creation and transmission of control packets. Nodes which have high buffer utilization because they are handling many data packets ought not to be at a disadvantage when it comes to obtaining buffers in which to create control packets. Indeed, it is just such nodes which are most likely to have the largest number of protocol-imposed responsibilities, and hence to have the greatest need for buffers in which to create control messages. In order to ensure that the flow of control messages is not slowed by the flow of data packets, each node should have a supply of buffers dedicated solely to the function of creating control messages. -28- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen 4.4 Buffering Data at the Source Node In many packet-switching networks, packets received from a host are buffered at the source node until an end-end acknowledgment is received. (This is true of single-packet messages in the ARPANET.) An insufficient supply of buffers for this purpose will hold the throughput of the locally attached hosts to an artificially low level. Furthermore, the holding time of a buffer which must await an end-end acknowledgment is very long, relative to the holding time of other buffers. This implies that the number of buffers needed to serve the function might be quite large, if an adequate level of throughput is to be maintained. A basic principle of congestion control in packet switching networks is that packets which are already in the network should not be unduly interfered with by packets which are entering the network. The buffer management scheme we have been outlining applies this principle by dedicating pools of buffers to each output device and to the various protocol functions. That is, the scheme ensures that local inputs cannot hog the buffer space at a node, which would result in degrading the flow of traffic through the node. There is a question, however, as to whether there should be a pool of buffers DEDICATED to buffering input packets at the source node, or whether this function should compete with other functions for a sharable buffer pool. Since -29- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen we have already assigned dedicated buffer pools to those other functions that need them, the only possible bad result of not dedicating a pool of buffers for source buffering of local inputs would be that these other functions would be able to hold down the throughput due to local hosts, by taking most of the buffering for themselves. It is sometimes thought that this is actually a good feature. That is, if the node is so heavily loaded with transit traffic and with traffic destined for output to local hosts, perhaps it is good to reduce the amount of buffer space available for source buffering. After all, when the network is heavily loaded, one does want to reduce the input rate, and reducing the buffer space available for source buffering of input will have this effect. This argument, however, ignores fairness considerations. In the ARPANET, for example, there are a few nodes which, because they are on the major cross-country paths, have a much greater load of transit traffic than does the vast majority of nodes. However, these nodes which are heavily loaded with transit traffic also have local hosts and TIPs. The users of these local hosts and TIPs have a right to the same service as is given to users whose local IMPs do not have a heavy load of transit traffic. If the heavy load of transit traffic at these nodes is allowed to get so much buffer space that the throughput obtainable by the local users is degraded, then users at these nodes are at a disadvantage with -30- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen respect to users at other nodes. This is hardly fair. If the transit load at some node is "too heavy," then ALL users which are sending traffic through that node should be forced to reduce their input rate, not just the users who happen to be locally attached to that node. Of course, this effect cannot be achieved merely by buffer management. It requires a more general congestion control scheme. Our present point though is that since a heavy transit load should not be permitted by itself (in the absence of instructions from a congestion control scheme) to degrade the throughput of local users, a non-sharable pool of buffers should be dedicated to the function of buffering local input while awaiting end-end acknowledgments. Of course, as long as the transit traffic at some node must compete with the input traffic at that node for some resource (even if only the processor), there will always be a certain amount of "unfair" interference. A good buffer management scheme can limit, but not eliminate, the effect. It is important to note that this point can be obscured by certain assumptions of homogeneity which it is often convenient to make when analyzing or simulating a buffer management system. When trying to perform such analysis, it is often convenient to create a network model in which the ratio of transit traffic to input traffic is the same at all nodes. Once -31- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen one has made that assumption, it is clear that the question of fairness will not arise, since all nodes will be equally loaded, and input at all nodes will be equally constrained. Therefore, if one has made that assumption, it may seem reasonable to design a buffer management scheme which allows transit traffic to lock out locally input traffic entirely. Assumptions of homogeneity beg the question of fairness, and in doing so lead to congestion control or buffer management schemes which are seriously deficient. 5 Buffer Management with a Shortage of Buffers (ARPANET) We have so far been discussing the issues that arise in the design of a buffer management scheme for a node which has ample buffer space. We have argued that good buffer management is important for good network performance, no matter how many buffers exist in a node. Our basic approach has been to dedicate enough buffers to each function which requires them so that all such functions can be performed at full speed, with the minimum amount of interference from other functions. The assumption that there is an "ample" supply of buffer space is just the assumption that there exist enough buffers to do this. Any excess amount of buffers should be sharable among several functions, and should be -32- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen used to smooth the effects of stochastic peak loads or processor latency. We turn now to the issues that must be addressed when designing a buffer management scheme for a node which does NOT have ample buffer space. Our main interest will be buffer management in the 316/516 IMP, which is severely memory-limited. However, our discussion will also have application to the design of a buffer management scheme for new networks which are not expected to be memory-limited. It is often thought that networks designed with present technology will always have ample buffer space, since memory is now one of the cheapest components of a computer. This is somewhat of an oversimplification, though. However cheap memory is, it is always cheaper to have less. We would not expect nodes to be designed with arbitrarily large amounts of buffer space. Rather, the amount of memory configured into a node will generally be determined by making a sizing decision based both on economics and on the design objectives of the node. Yet at the present state of the art, making such sizing decisions is more of an art than a science, and such decisions can easily be wrong. Furthermore, future re- configurations of the network, e.g., adding long-delay or higher speed lines, can invalidate the original sizing decisions. Yet the addressing, mapping, or bus structure of the computer may -33- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen make it difficult or impossible to freely add additional memory to the initial configuration. It is never good to assume, in network design, that buffer space will always be ample throughout the life of the network. For these reasons, our discussion of buffer management in the ARPANET should have wider application. In the ARPANET, each Honeywell 316/516 IMP has between 30 and 35 buffers, depending on the configuration of the node and the presence or absence of various optional software packages (which, when present, reside in an area of memory otherwise devoted to buffer space). This is nowhere near the amount of buffers needed to ensure that all processes requiring buffers can run at full speed. A sensible approach in such a case is to dedicate to each process enough buffers to allow the process to run at only a fraction of full speed, while making the additional buffers sharable. However, unless there are enough sharable buffers to enable some of the processes to sometimes run at full speed, the scheme will prevent any process from EVER running at full speed, even when there are a sufficient number of idle buffers. This would be a very undesirable situation. With a severely memory-limited node, as in the ARPANET, it may be necessary to dedicate to a process only the minimum number of buffers required to ensure that the process can run at all (i.e., to prevent a deadlock situation in which the process is -34- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen completely locked out). THIS MEANS THAT MUCH OF THE ABILITY OF THE BUFFER MANAGEMENT SCHEME TO PROTECT ONE PROCESS FROM UNDUE INTERFERENCE BY ANOTHER IS LOST. The price for retaining that ability would be to guarantee slow performance by some of the processes, even while resources (buffers) lie idle. Such a price may be too high to pay. To put this point another way, we must worry not only about under-control of the buffer space, but also about over- control. If buffer space is under-controlled, one process can hog the buffers, preventing other processes from getting their fair share. If buffer space is over-controlled, then a process may be limited to a particular proportion of the buffer space, even if granting it a larger proportion in some particular situation may be the best strategy from the point of view of overall network performance. With ample buffer space, over- control is not generally a problem, since every process can get as many buffers as it needs. When buffer space is scarce, however, strict and inflexible limitations on the amount of buffer space that can be under the control of a particular process may result in no process ever being able to get enough buffers to perform well. A loosening of the controls may be necessary in such cases. As we shall see, the current ARPANET buffer management scheme suffers from over-control in some -35- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen instances. In the ARPANET, the situation is even worse. There are not enough buffers available to dedicate even the minimum amount to certain processes. For example, one process which requires buffers is the process governing output to a host, of which there may be four attached to each node. An ARPANET message may be up to 8 packets long (i.e., may occupy up to 8 buffers). Before any message can be delivered to a host, all eight packets must be present, so that the message can be "reassembled." There is no point to dedicating fewer than 8 buffers to each host, since that would not guarantee that enough buffer space would always be available to deliver a message to the host. On the other hand, one cannot dedicate 8 buffers to each of four hosts, since that would leave no buffers for any other function. A similar problem arises with respect to packets which must be buffered at the source node awaiting end-end acknowledgments (RFNMs). There can be as many as 8 such packets per "connection," where two packets are considered to be on the same connection if they have the same source host, the same destination host, and the same priority. With four source hosts per node, each of which can be communicating with an arbitrary number of destination hosts, the number of buffers required to guarantee maximum throughput is more buffers than exist in the entire node. However, it is still -36- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen the case that there are too few buffers to enable a buffer management scheme to ensure fairness to both host input and host output functions. This means, of course, that improving the buffer management scheme can increase the fairness, but not optimize it. The way the ARPANET deals with this problem is simply to lump together all host input and output functions and dedicate a single pool of buffers to the combined set of functions. This pool is known as the "Reassembly" pool, and its size varies from about 18 to 22 buffers, depending on an IMP's configuration. (The term "reassembly" is very misleading in this context, since reassembly of packets into messages is only one of many functions which must obtain buffers from the reassembly pool.) This approach recognizes that there is simply an insufficient amount of buffering to enable separate pools of buffers to be dedicated to the separate hosts, or even to enable separate pools of buffers to be dedicated separately to input and output functions, without paying the overly high price of ensuring poor performance by some processes even under conditions of low buffer utilization. The main disadvantage of the approach is that it robs the buffer management scheme of its ability to ensure fairness among the various competing functions that are lumped together. However, that is really just the result of having an -37- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen insufficient supply of buffers, and we do not see any way of improving the situation simply by altering the buffer management scheme. Attempting to maximize fairness under these conditions requires a strategy other than partitioning the buffer space. The scheme in the ARPANET, though, does make an attempt to separate host-related functions from functions related solely to the operation of the inter-IMP trunks. Failure to separate host- related functions from each other may cause different host- related functions to interfere with each other. Failure to separate host-related functions from operation of the inter-IMP trunks would enable host-related functions to interfere with the node's store-and-forward ability, which could be even worse, since that could make the network more prone to congestion. As we shall see, however, the ARPANET's buffer management scheme is not entirely successful in preventing interference between store-and-forward functions and host-related functions. Even though fairness between host input and host output functions cannot be guaranteed in the ARPANET simply by partitioning the buffer space, there are other sorts of procedures which a buffer management scheme can bring to bear to help bring about (if not to guarantee) fairness. The present buffer management scheme makes no real attempt to "prioritize" the input and output functions. That is, if at some given time, -38- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen buffers are needed for both input and output, the buffers will be assigned in the order in which they are requested. Because of the software architecture of the IMP, this appears to give an advantage to host input. The request for a buffer to hold a packet received from a local host is made by the high-priority routine which services the host-IMP interface. The request for a buffer to hold a packet for output to a local host is made either by the TASK process or by one of the background processes, which run at lower priority levels. Furthermore, requests for output buffers, if not served the first time they are made (because of unavailability of buffers), are put on a queue which is served in round-robin fashion at the lowest priority level. Any number of requests for host input buffers can be served between the time a request for a host output buffer is first queued and the time it is finally served. This seems to violate the principle of congestion control which states that output-related functions should be favored over input-related functions. It would not seem to be a difficult matter for requests for buffer space to be prioritized or re-ordered so that buffers are never provided for input while there are outstanding requests for output buffers. (Note that this issue of re-ordering the requests would not arise if there were ample buffer space, since in that case, all functions could be guaranteed sufficient buffering, regardless of the order in which requests were made.) -39- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen This principle, however, would have to be applied with some care. In the ARPANET, a request for output buffer space may be either a request for one buffer (for single packet messages) or a request for eight buffers (for multi-packet messages). If a source node has requested a single-packet allocate for some packet from some destination node, it must buffer the packet until the output buffer space is made available. Meanwhile, other packets from the same source host may still be entering the network. On the other hand, if a source node is waiting for a multi-packet allocate, it does not buffer the multi-packet message while waiting. Rather, it stops all input from the source host until the output buffers are allocated. That is, if a single-packet request remains unserved, buffer space is used as the source node, while input at the source node continues unabated. If a multi-packet request remains unserved, not only is no buffer space wasted at the source node, but input from the source host is stopped. The congestion control principle that output should be favored over input is reasonable because "output" means that resources already in use will be freed, while "input" means that resources currently free will be put into use. Competition between a host input packet and an unserved single packet request is clearly competition between input and output. However, competition between host input and an unserved multi- packet request is more like competition between input at one IMP -40- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen and input at another. Hence, prioritization or re-ordering of requests for buffers need only be done in the former case. Even there, care must be taken to ensure that a large flow of single packet messages to the hosts at one IMP does not prevent those hosts from ever sending any inputs of their own into the network. While output should be favored over input, output should not be able to lock out input. After all, output at one IMP is input at another. If output is too much favored over input, the result is that input at one IMP is favored over input at another IMP. Therefore, it is possible that, IN THE ABSENCE OF A GENERAL FLOW CONTROL PROCEDURE, which would explicitly match IMP-IMP flows to the amount of resources available, PRIORITIZATION OF BUFFER REQUESTS COULD DO AS MUCH HARM AS GOOD. A full investigation of the issues relevant to end-end flow control in the ARPANET is not within the scope of the present contract, however. The 316/516 IMP does not have enough buffer space to ensure transmission over the inter-IMP trunks at the full rate of 50 kbps. Only the minimum number of buffers necessary to prevent a trunk from being locked out is dedicated to each trunk. This minimum number, of course, is one. There is also a maximum number of buffers which can ever be under the control of the combined trunk output processes. This number is either 10, 12, or 14, depending on whether the IMP has 2, 3, or 4 trunks. -41- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen Furthermore, there is also a minimum number of buffers which are available for trunk output, but unavailable for host-related functions. This number (which includes the single buffer dedicated to each output trunk) is either 6, 9, or 12, depending on whether the IMP has 2, 3, or 4 trunks. (There are certain exceptions to this rule, such as IMPs which have 16-channel satellite lines. See chapter 7 of BBN Report No. 4088 for details. There appears to be no hard and fast rationale for having chosen these particular numbers. Rather, they just "seem to work.") These buffers, except for the buffers which are dedicated to particular trunks, are not, however, dedicated to trunk output; they are also available for other functions that we will discuss shortly. The small difference between the minimum and maximum numbers of buffers available for trunk output (either 4, 3, or 2, depending on IMP configuration) form a pool of buffers which are generally sharable among all the processes in the IMP, which can get them on a first-come, first-serve basis. There is also a maximum number of buffers which can even be under the control of the process which runs a PARTICULAR output trunk. This number is eight (except for satellite lines, for which the number is sixteen). The number eight does not appear to have been chosen in order to meet constraints on the buffer management system. Rather, eight is the number of logical -42- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen channels maintained by the IMP-IMP protocol. That is, it is the number of packets which can be in flight simultaneously on an inter-IMP trunk. There is no inherent reason why the maximum number of packets under control of an output trunk (i.e. the number in-flight at some instant PLUS the number queued at that instant) should be the same as the maximum number of packets which can be in flight simultaneously on that trunk. This particular choice of number appears to have been made primarily for ease of programming. The ARPANET IMP does contain a pool of buffers dedicated to the creation of end-end control messages. In keeping with the principle that, when buffers are in severely short supply, only a minimum number should be dedicated to any particular function, the size of this pool is one. Of course, an IMP may have more than one extant end-end control message at a time. When additional end-end control messages must be created, they are treated as host-related messages. That is, to create an end-end control message, a buffer from the pool for host-related functions must be obtained. This restriction is apparently due to the fact that after a control message is created, it is treated in some ways as if it were a packet submitted by a host. That is, after a control message is created, it is placed on a queue known as the Reply Queue. Packets are removed from the -43- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen Reply Queue by a "Back Host," and submitted to the IMP as if they came from a real host. A Back Host is a software routine which runs at the background level of the IMP. Its purpose is to submit control packets as if they were packets from a real host (though of course, they are submitted at a point which is later in the IMP's logic than the point where a real host would submit a packet). This fact about the software architecture of the IMP makes it appropriate to treat the creation of control packets in a manner analogous to host input. If the submission of control packets were handled differently from the submission of ordinary host input, then it might not be appropriate to create protocol messages on the same buffer pool as ordinary host messages, since protocol messages are handled very differently and in general have different constraints. (Of course, one could raise the further question as to whether the "back host" mechanism is appropriate for handling control packets. However, this cannot be considered here.) We have spoken of the need for having a buffer dedicated to input from each inter-node trunk, in order to be able to process certain sorts of control messages which, although occurring relatively infrequently, need to be processed quickly, with a high degree of responsiveness (i.e., without having to wait on a queue). The IMP does indeed dedicate a buffer to each -44- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen input trunk. That is, a packet which has just arrived on a certain trunk will not even be queued for the dispatcher (TASK) if that would result in there being no buffer at all available to receive the next input from the trunk. However, these dedicated buffers are NOT used for processing those control packets which require high responsiveness. Not only are such buffers not queued for processing, but the packets in such buffers are NEVER processed at all, they are simply discarded. Even if the packet is a line up/down protocol packet, which is ordinarily processed immediately by the routine that handles input from the trunks, it will not be processed if processing it would mean that there is a period of time when no buffer is available to receive the next input from that trunk. Not even the acknowledgments which may be piggybacked in the packet are processed. Rather, the packet is simply discarded, and its buffer reused for the next input. The apparent purpose of this procedure is to ensure that there is never any period of time when a packet can be lost because there is no buffer available in which to receive it. However, although this procedure does help to avoid packet loss, it does this by deliberately discarding packets. From a performance perspective, there does not seem to be much difference between losing a packet and throwing it away. In general, it is not sensible to throw one packet away so that the next will not be lost. Either the buffer dedicated to an input trunk should be used to ensure the -45- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen processing of packets which need high responsiveness (such as line up/down protocol packets, routing updates, and received IMP-IMP acknowledgments), or there should not be any dedicated input buffers. Currently, the dedicated buffers are wasted. The worst thing a buffer management scheme can do is to waste buffers, particularly when buffers are a scarce resource. The IMP does have a small pool of buffers which cannot be placed under the control of any host-related process or of any process which regulates output on the inter-IMP trunks. (The size of this pool is regulated by the parameter MINF, currently set to 3.) These buffers are available only for the processing of such high responsiveness packets as routing updates, line up/down protocol packets, and received IMP-IMP acknowledgments, and for the creation of such subnetwork control packets (not end-end control packets) as nulls, routing updates, and line up/down protocol packets. These buffers are also useful for mediating processor latency. They are not, however, dedicated to the individual input trunks. As we have pointed out previously, it is quite desirable to have such a pool of buffers; this seems a good feature of the IMP's buffer management system. In BBN Report No. 4088 we pointed out several bugs in the IMP's buffer management procedure. One bug was the fact that the buffers which are dedicated to input from the inter-IMP trunks -46- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen are completely wasted. This bug can be fixed either by refraining from dedicating buffers to trunk input, or by processing the packets in these buffers if (and only if) they require high responsiveness. This latter approach would in some sense be equivalent to increasing the value of MINF to three plus the number of trunks, except that it would also ensure some degree of fairness among the input trunks with respect to their ability to obtain buffers from the MINF pool. As we have already discussed, the correct way to fix the bug may depend on whether the IMP is short on buffers or short on CPU cycles. Some mixture of the two approaches may be needed, since in practice the IMPs are sometimes short of buffer space and sometimes short of CPU cycles. It must also be pointed out that processing of received acknowledgments from a particular input trunk may also be important if the corresponding output trunk has most of its logical channels in use, even if there are plenty of free buffers. After all, processing of received acknowledgments not only frees buffers, but also frees logical channels, and a shortage of unused logical channels can have the same effect in degrading performance as a shortage of buffers. In order to pick the strategy which will have the best effect on network performance, we will need to design a method of determining in real time which resource is scarcest in the IMP at some particular moment. -47- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen We also pointed out several other bugs in BBN Report No. 4088. These bugs all have a common source, namely the fact that when a buffer is moved from a source process to a destination process, the buffer management scheme takes no notice of the source process. In particular, a buffer may be rejected even if it cannot be freed. This not only leads to the bugs we described in our previous report, but also to the following sort of bug. Suppose an IMP has three trunks, and that it has a maximum of 12 buffers which can be under the control of the process which regulates output to the trunks. Suppose that there are 8 buffers queued for output to trunk 1, and 3 to trunk 2, while there is one buffer which has already been transmitted on trunk 3, but which is presently awaiting acknowledgment. Suppose also that a packet received from a local host is now ready for transmission to its destination, and that it is routed out trunk 3. The IMP will not permit this packet to be transmitted, since that would place a 13th buffer under control of the trunk output routines. Thus the buffer will be rejected, even through the trunk is idle, and the other resources needed to transmit the packet (e.g., logical channels) are freely available. Furthermore, the rejected buffer will not be freed. Refusing the buffer simply delays transmission of the packet without resulting in the freeing of any resource. Thus it has no salutary effect on network performance, and is in fact counter-productive. This is -48- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen an example of OVER-CONTROL in the buffer management scheme; a buffer is prevented from moving, even though considerations of general network performance would dictate that it be passed to the destination process immediately. This bug, as well as others we have discussed, would be eliminated if the IMP took account of the buffer's source process as well as its destination process. Then the IMP could adopt a policy of never refusing a buffer FOR CONSIDERATIONS OF BUFFER MANAGEMENT unless doing so would result in the buffer's being freed. Even if the ARPANET's buffer management scheme were modified to take account of the criticisms we have been making, there would still be a major problem with it. The problem is that in the competition for buffers to be used to transmit packets to a neighboring IMP, packets input from local hosts are favored over packets arriving from neighboring IMPs, thereby violating an important principle of congestion control. Not only can host access lines be of higher speeds than inter-IMP trunks, but the 1822 protocol, which governs host-IMP access, does not allow the IMP to drop a packet it has received. The IMP-IMP protocol, on the other hand, does allow a receiving IMP to drop a packet. We have already pointed out the way in which this can cause a buffer management scheme to favor the packets from the local hosts. Since it is not feasible to modify the 1822 -49- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen protocol, some other means of eliminating or at least reducing this favoritism must be developed. One way of reducing this favoritism would be to define a pool of buffers reserved exclusively for "transit packets", i.e. packets whose origin and destination are both remote. No such buffer pool exists in the ARPANET at present. The current store-and-forward pool can be completely filled with locally originating packets. Although a locally originating packet requires a buffer from reassembly space when it first enters the IMP, it is moved into store-and-forward space as soon as it is queued to an output trunk. Since locally originating packets cannot be discarded, and hence should never be refused by the buffer management scheme after they are originally received, this division of the buffer pool does not prevent host packets from locking out transit packets entirely. It does prevent all the buffers in the IMP from being devoted to host-related functions, which is very important if the IMP is to continue to function as a store-and-forward node even while handling a large amount of host traffic. Note, however, that a pool dedicated to transit packets would have the same effect. Furthermore, it would have the additional salutary effect of ensuring a supply of buffers for transit packets. We recommend therefore the elimination of the store-and- -50- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen forward pool, and the creation of a transit pool. The transit pool would consist of a minimum number of buffers which would be dedicated to packets with remote origins and remote destinations. Locally originating packets would never be placed in the transit pool, but would remain in the Reassembly pool (which we suggest renaming the "end-end" pool), even while queued for transmission out an inter-IMP trunk. It is also desirable to ensure that a certain number of transit packets may always be queued simultaneously to a given output trunk. Although the presence of the transit pool prevents transit packets from being locked out entirely, it does not prevent them from being locked out on some particular output trunk. However, since every packet queued for an output trunk must be assigned to a logical channel, this can be prevented by saving a certain number of logical channels on each trunk for transit packets only. This may require that a locally originating packet with a remote destination sometimes be refused, even though the trunk is idle and the refused buffer cannot be freed. However, the reason for refusing in this case is not buffer management, but management of logical channels. Refusing a host packet (destined to a remote destination) for reasons of logical channel management WILL result in keeping free a logical channel that would otherwise be occupied. So even -51- IEN-182 Bolt Beranek and Newman Inc. Eric C. Rosen though no buffer is freed, the packet can still be refused without violating any principles of resource management. -52-