RFC 59

Flow Control - Fixed Versus Demand Allocation

📅 published June 1970, from ietf

RFC 59 💖

Edwin W. Meyer, Jr. ✨ MIT Project MAC ✨ 27 June 1970

Part 1 of 2 🎀

The Flow Control Tea ☕

okay bestie, so RFC 54 has this flow control plan called prior allocation of buffer space, where every ALL network command reserves buffer space up front. 🎀 It has one big perk: if you never allocate more than 100% of an NCP's buffer space, the situation where more messages get pushed at a HOST than it can handle will literally never happen. 💅

but ngl, it has some seriously bad vibes 💀:

  • (i) chronic underutilization of resources,
  • (ii) highly restricted bandwidth,
  • (iii) considerable overhead under normal operation,
  • (iv) insufficient flexibility under conditions of increasing load,
  • (v) it optimizes for the wrong set of conditions, and
  • (vi) the scheme breaks down because of message length indeterminacy.

Several people from Project MAC and Lincoln Laboratories talked this through, and we are lowkey obsessed with the "cease on link" flow control scheme from RFC 35 by UCLA. It's way more iconic than this new plan 🦋

And the RFC 46 method, which used BLK and RSM control messages, got dropped 😭 because it can't guarantee it will quench flow within a limited number of messages.

The advantages of "cease on link" over the fixed allocation proposal are main-character level:

  • (i) it permits greater utilization of resources,
  • (ii) it does not arbitrarily limit transmission bandwidth,
  • (iii) it is highly flexible under conditions of changing load,
  • (iv) it imposes no overhead on normal operation, and
  • (v) it optimizes for the situations that most often occur.

Its single disadvantage is that under rare circumstances an NCP's input buffers can become temporarily overloaded. This should not be a serious drawback for network operation 🌸

Here's how the vibe works. IMP messages for a particular "receive" link might be coming into the destination HOST faster than the attached process reads them out of the NCP's buffers. At some point the NCP decides the input queue for that link is too big compared to the total free NCP buffer space left. That's when it starts quenching by sending a "cease on link" IMP message to its IMP. Nothing happens yet 🙈, not until the next message for that link arrives at the destination IMP. The message still gets delivered to the receiving HOST, but the RFNM sent back to the transmitting HOST has a special bit set. That bit tells the originating NCP to stop sending over that link. To confirm the pause, the NCP sends an SPD <link> "suspended" NCP control message to the receiving HOST, so it knows the sender really has stopped. Later, once the receiving process has shrunk the input queue for the link to a reasonable size, the NCP tells the sending NCP to start up again by issuing an RSM <link> "resume" NCP control message 🦋

The Premises (aka the Vibe Check) 🧚

The flow control argument is based on the following premises, and honestly they're giving real insight:

  1. Most network transmission falls into two categories:
    • Type 1: short messages (<500 bits) at intervals of several seconds or more. (console communication)
    • Type 2: a limited number (10 - 100) of full messages (8000 bits) in rapid succession. (file transmission)
  2. Most processes are ready to accept transmitted data when it arrives at the destination and will pick it up within a few seconds (longer for large files). So at any particular instant, the great majority of read links have no data buffered at the destination HOST. This assumes a sensible software system at both ends 💜
  3. Flow control need be imposed only rarely on links transmitting Type 1 messages, and somewhat more frequently for Type 2 messages.
  4. Both the total network load and the load over a single connection fluctuate, and they cannot be adequately predicted by either the NCP or the process attached to an individual connection 🌈
  5. Assuming adequate control of wide bandwidth transmission (Type 2), the probability that an NCP will be unable to accept messages from the IMP due to full buffers is quite small, even if the simultaneous receipt of moderately small messages over all active links would more than fill the NCP's input buffers.
  6. If an NCP's buffers do fill completely, it may refuse to accept any transmission from the IMP for up to a minute without utter catastrophe 🙏
  7. Under cases of extreme input load, if an NCP has large amounts of data buffered for input to a local process, AND that process has not read data over that connection for more than a minute, the NCP may delete that data to make space for messages from the IMP. This is expected to happen extremely rarely, except in cases where the process is the main contributor to the overload by maintaining several high volume connections which it is not reading 👑

The Disadvantages of RFC 54 💅

Based on the premises above, I see the following disadvantages in the flow control proposed in RFC 54:

  1. Chronic Underutilization of Resources 😭: A fixed allocation of buffer space dedicated to a single Type 1 connection will go perhaps 90% unused if we actually achieve responsive console interaction through the network. That's because it's empty most of the time and very seldom more than partially filled. Flip it around, and a demand allocation scheme could handle several times as many console connections using the same buffer resources. (It has been suggested that this underutilization could be fixed by allocating more than 100% of the available buffer space. That's in fact no solution at all, because it defeats the basic premise behind this method of flow control: guaranteed receptivity. True, it might fail in less than one case in 1000, but that is exactly the case flow control exists for. 🙈)
  2. Highly Restricted Bandwidth 🐢: While all that buffer space dedicated to low volume connections is being wasted (and it can't be deallocated, see below), high volume communication is unnecessarily slowed by inadequate buffer allocation. (Because of the inability to deallocate, it's unwise to give a large allocation.) Data is sent down the connection up to the allocation limit, then it stops. Several seconds later, after the receiving process picks up some of the data, a new allocation is made and another parcel of data is sent. It seems clear that even under only moderately favorable conditions, a demand allocation scheme would allow several times the bandwidth this one does 🚀
  3. Considerable Overhead During Normal Operation 🎀: Flow control actually needs to be imposed relatively rarely. However, this plan imposes a constant overhead on all connections due to the continuing need to send new allocations. Under demand allocation, only two RFC's, two CLS's, and perhaps a couple of SPD and RSM control messages need to be transmitted for a single connection. Under this plan, a large fraction of the NCP control messages will be ALL allocation requests. There will probably be several times as many control messages to process at both the sending and receiving NCPs as under a demand allocation scheme 🫶

okay so let's look at how an NCP runs when it's using demand allocation with "cease on link" for flow control 💅 the flow control algorithm sets the maximum permissible queue length (MQL) at a certain fraction (say 10%) of the total empty buffer space that's available right now. if a connection's input queue goes above the MQL, the NCP blocks that connection. this can happen either because new input landed in the queue or because the MQL got recalculated lower 🫶 when load is light, the MQL is pretty high, so relatively long input queues can hang out without the connection getting blocked ✨

as load goes up, the leftover buffer space shrinks and the MQL keeps getting recalculated lower 📉 this barely affects console stuff with short queues, but more of the queues for high volume connections start going above the MQL. when they do, "cease on link" messages get sent out for those connections 🦋

if the flow control constants are set properly, there's a high probability that flow over the quenched links will actually stop before buffer space gets critically scarce 🤞

ngl though, there's still a finite probability that the data still coming in over the quenched links fills the buffers anyway 😭 that's most likely under already heavy load, when previously inactive links start transmitting all at once at high volume.

once the NCP's buffers are full, it has to stop taking all messages from its IMP. this is serious bc now the NCP can't receive control messages sent by other NCP's, and the IMP might soon be forced to stop accepting messages from the NCP too. (lowkey saved though, because the NCP already sent "cease on link" for basically all of the high volume connections before it stopped taking data from the IMP 🙌)

in most cases, input from the IMP only stays stopped for a few seconds. after a very short interval, some process with data queued for input is likely to come along and pick it up from the NCP's buffers. the NCP immediately starts taking data from the IMP again. the IMP output may stop and start several times as the buffers open and then refill 🌊 but more processes are now reading data queued for their receive sockets, so the NCP's buffers are emptying at an accelerating rate 🚀 soon the reading processes make enough buffer space to take in all the messages still pending for blocked links, and normal IMP communications resume 🎀

as the reading processes catch up with the sudden burst of data, the MQL becomes lower, and more and more links become unblocked 💖 the crisis can't immediately reappear, because each link generally becomes unblocked at a different time. if new data suddenly shoots through, that link immediately goes blocked again. the MQL goes up, with the result that other links don't become unblocked.

the worst case shows up at a HOST with relatively small total buffer space (less than 8000 bits per active receive link) under heavy load conditions. suppose high volume transmission suddenly comes in over more than a half-dozen links simultaneously, and the processes attached to the receive links take little or none of the input. the input buffers may completely fill, and the NCP must stop all input from the IMP. if some processes are reading links, buffer space soon opens up. shortly it's filled again, this time with messages over links which aren't being read. at this point the NCP is blocked, and could remain that way indefinitely 😬 the NCP waits for a time, hoping that some process starts reading data. if this happens, the crisis may soon ease 🥹

if buffer space doesn't open up on its own after a limited interval, the NCP must take drastic action to get back into communication with its IMP. it selects the worst offending link based on the amount of data queued and the interval since data was last read by this process, and totally deletes the input queue for this link. this should break the logjam and start communications again 💅

this type of situation is expected to occur most often when a process deliberately tries to block an NCP in this manner. the solution has serious consequences only for "bad" processes: those that flood the network with high volume transmission over multiple links which aren't being read by the receiving processes. 💀

because of the infrequency and tolerability of this situation, the overall performance of the network using this scheme of demand allocation should still be much superior to that of a network employing a fixed allocation scheme 👑

       [ This RFC was put into machine readable form for entry ]
         [ into the online RFC archives by William Lewis 6/97 ]
📦 where this page comes from