RFC 700

Title Block 📋🎀

okay bestie so here's the header info 💅 this is NWG/RFC 700 (also NIC 31020, and it's INWG Experiments Note 1) from August 1974 ✨ the title is A Protocol Experiment 🧚 and the authors are Eric R. Mader, William W. Plummer, and Raymond S. Tomlinson 🫶 the header doesn't list a category, a status, or anything it obsoletes or updates, so there's nothing to report there 🙈

I. Introduction 🌸

okay so in early February 1974 the main line printer on BBN's TENEX system died 💀 and the team was like "fine, we'll use the PDP-11 line printer over the ARPANET instead" 🖨️ and it had a double purpose 👑 they wanted the actual listings AND they wanted to study network protocols, so it was giving multitasking energy from day one 🔥

II. The Basic Protocol 🦋

this one is built on the protocol Cerf and Kahn described in INWG Note #39 💖 you're expected to already know that doc, so this is just a quick sketch 🎀 also heads up, not every feature in this section actually got implemented, so check out Section VI for the details 👀

okay so at any moment the sender has two pointers into the stream of bytes it's sending 👯‍♀️ bytes to the left of the LEFT pointer have already been sent AND acknowledged ✅ the bytes sitting in the "window" between LEFT and RIGHT have been sent (zero or more times) but no success signal has come back yet 🥺 and bytes to the right of RIGHT are still waiting their turn in the future 💅

in operation the sender keeps on sending bytes from the input stream, so RIGHT keeps advancing 🏃‍♀️ and positive acknowledgements from the receiver push the LEFT edge of the window toward the RIGHT edge 💜

LEFT and RIGHT are actually numerical byte positions in the data stream 🔢 the low order 16 bits of RIGHT get sent with every message as a sequence number, so the receiver can tell which part of the stream it's getting even when messages show up out of order 🌀 the receiver only has a finite amount of buffer space to rebuild an image of the transmitter's window 🧩 and it throws away any message whose sequence number is outside its buffer area 🗑️ BUT messages to the left of LEFT must still be acknowledged even though they're discarded 😭 otherwise a lost ACK would make the sender keep retransmitting a message the receiver keeps ignoring, forever and ever 💀 messages with bad checksums get tossed too 🚫

as "good" messages come in, the holes in the receiver's buffer get filled 🩹 and the continuous segments on the left edge get passed to the physical line printer (in our case) 🖨️ the receiver tells the sender what's up by sending an ACK (acknowledgement) message ✉️ that ACK specifies the sequence number of the byte it'd like to receive next (which becomes the new value of LEFT in the sender) AND the amount of buffer space it currently has free (which becomes the new maximum window width in the sender) 📏 the sender ignores ACKs to the left of LEFT and to the right of RIGHT 🙅‍♀️ so the sender and receiver are both ready to handle multiple copies of the same messages 🫶

now the failures 💔 messages with bad checksums, messages lost in transit (data AND ACKs), and messages thrown out for sequence numbers that looked out of range all look exactly the same to the sender: a dropped ACK ❌ a dropped ACK makes the sender's LEFT edge stop advancing, so the unacknowledged message just sits at the left of the sender's window, and there might be a matching hole at the left of the receiver's image of the window 🕳️ eventually transmission stops, and a (10 second) timeout goes off in the sender, which retransmits everything in the window 🔁 and here's the tea ☕ at the instant of a timeout there's no guarantee the un-ACK'd message is exactly at the left edge, or that it's the only unacknowledged message in the window 🤷‍♀️ retransmissions will probably make the receiver see stuff it's already seen, but duplicates get discarded thanks to sequence number checks 🧹

III. "Say Again" 🗣️

okay this one's an extension to the INWN #39 protocol that actually got implemented 🎉 the receiver can force a retransmission of the entire window by switching on a flag in any message it sends back to the sender 🚩 this is super useful when the receiver thinks a data message got dropped and wants a redo right away instead of waiting around for the sender's timeout 🏃‍♀️ but it only works if the network keeps messages in order 📬 and it's not great if the error rate is high, because you'd be resending the whole window just to recover one or two messages 😩

IV. Establishing an Association 🤝

in the experiment, two flags were used to set up an association 💕 FRST (FiRST flag) was the equivalent of SYN from INWG Note #39 ✨ it marks the first message of an association, and it tells the receiver to accept the sequence number in that message as the starting point for sequence numbers for the association 🌱

the second flag is HUH, a receiver-to-sender flag 🙋‍♀️ it's the receiver asking the sender to define the sequence numbers 🔢 when the sender gets a message with a HUH in it, it responds by switching on FRST in the next data message 🫶 normally HUH only gets sent if the receiver has been restarted, or if it's replying to messages on a port it knows isn't part of an association 🚪

V. A Problem 😬

okay so this is a severe problem the team found while working on association setup 🚨 if the PDP-11 (receiver) got reloaded while the spooler (sender) was running, the first few pages of the data stream got printed about six times before normal operation kicked in 🙃 here's how it happened:

1. The sender would be stuck in a loop, timing out and retransmitting because the receiver hadn't responded.
2. When the receiver restarted, it would see a whole window's worth of messages and reply to each one with a HUH.
3. For each HUH, the sender would reset the window and include a FRST flag with the first message in each of the (six) retransmissions.
4. The receiver would see the first message of the first retransmission containing a FRST, accept the sequence number, and print the data from that message and the ones after it. Then another message containing the FRST flag would show up and the cycle would repeat (five more times). Note that the ACKs generated in the repetitions were ignored by the sender because they were to the left of the window. 🔁💀

the "cure" they tried first was changing the receiver program so that after sending a HUH, it ignores messages until one with a FRST flag shows up 🩹 but this is NOT a real solution in general 🙅‍♀️ because if either the message containing the HUH or the response gets lost in transmission, the receiver port is useless 💔 they used a timeout to guard against that, but the timeout can't be trusted, because it might cause two messages with FRST flags to be received, which is literally the exact problem they were trying to avoid 🤦‍♀️

there's an alternate cure that doesn't depend on the network being lossless 🌊 the sender would respond to a HUH by ignoring all messages for at least a round trip delay time before sending its response containing the FRST flag ⏳ the catch is you'd have to define what that time is 🤔 and in general this can't be done when messages can get trapped for indefinite amounts of time in network partitions 🧱 this will be discussed more fully in a subsequent document 📚

VI. Features not Investigated 🔍

none of the programs so far have supported any of these features 🙈

1. Window size control. The window size was a constant (2048 bytes). In a future experiment the window size will be varied not only by indications of buffer space in the receiver, but also as a function of estimated transit time. (see below). 📏
2. Reassembly. Since reassembly is conceptually easy, it is likely to be one of the first extensions. A message corrupter will be included in the receiver to test the functioning of the reassembly mechanism. 🧪
3. Expanded Internetwork Addresses
4. Multiple Associations
5. Reliable Making and Breaking of Associations

VII. Implementations Notes 🛠️

the sender is about ten pages of assembly code for the network message interface 📄 it has two processes: one fills a buffer by reading the input data stream, and the other sends network messages from the buffer and processes replies from the receiver 🔄 the two are joined by a coroutine mechanism, but in the future they'll be two parallel TENEX processes 🧚

the receiver program is about four pages of BCPL code, plus IO device drivers and routines that implement the queueing primitives 🎀

each message holds between zero and 255 bytes of data, arranged (as a coding convenience) in a way that's directly compatible with the BCPL string handling routines 🧵 messages carry a single byte of checksum, which is the low eight bits of the twos complement negation of the twos complement sum of all the other bytes in the message 🔢 the authors recommend that some more reliable checksum function get used in the future 💜 they say even eight-bit ones complement arithmetic would be better ✨

source files for the various programs are available from the authors at Bolt Beranek and Newman, 50 Moulton Street, Cambridge Mass., 02138 📬

VIII. Simple Rate Calculations 🧮

okay math time, but make it cute 💅 if we assume an active association has reached steady state, that processing delays are lumped into the transit time T, and that there are no errors, then we can calculate the maximum data rate like this 🦋

say the sequence numbers passed by the RIGHT pointer are some function of time, R(t) 🕰️ messages the receiver gets are the same function of time, just delayed by T (a transit time) seconds 🚚 since processing time is zero, the acknowledgments carry this same function, R(t-T) ✉️ and the acknowledgements the sender receives have sequence numbers R(t-2T) 🔁

L(t) = R(t-2T)
L(t) = R(t) - W

the acknowledgements at the sender set the LEFT pointer, L(t) 🎯 and R(t) is ahead of L(t) by the width of the window, which is a constant in steady state 📏 so we get the two relations above 💕

now let R(t) = Bt, which means the sequence numbers increase linearly with time 📈

R(t) = Bt

(microscopically, short bursts alternate with longer periods of inactivity, but the average bandwidth is still B 🌊) under those assumptions the bandwidth comes out to:

B = W/2T

so the bandwidth in bytes per second is just the steady state window width divided by the round trip delay time 🎀 and going the other way, that same relation can determine the buffer size needed 🧩 for the receiver to guarantee it accepts information that was transmitted, it has to supply buffering equal to (or greater than) the window size 🛡️ the window size has to be equal to or greater than the desired bandwidth times the round-trip delay time, which means it equals the number of messages in a round-trip "pipeline" 🚰

the bandwidth in the presence of a relatively low error rate can also be calculated 🐛 assume B and W are expressed in terms of (full) messages rather than byte numbers 📦 each error has two effects: a timeout delay of D seconds, and retransmission of W messages 😭 so the time

💜 to be continued! part 2 is coming with the rest of the maths and everything after it 🧚

Okay so Q(M,N) is basically the total time it takes to send M messages when N of them get messed up 😭 It's three things added together: the time to send everything once, N*D seconds of timeout waiting, and the time to resend the window N more times 💅

Q(M,N) = (2T/W)*M + N*D + N*2T

Next we divide by M to get the time per message, and multiply the last term by (W/W), which is just 1, bestie 🧚

Q(M,N)/M = (2T/W) + (N/M)*D + (2T/W)*(N/M)*W .

And (M/N) is just the fraction of messages in error, so we call it E 🦋

Q(E) = (2T/W)*(1 + EW) + ED

B(E) = 1/[(2T/W)(1+EW) + ED]

Now the "say again" mechanism (see Section III.) is literally the main character here ✨ It forces D to be zero, which means you still get a reasonable average data rate even when errors are happening. Iconic, honestly 👑

Let's look at an example. Say you've got a network with an E of 0.01, W is 20 messages, and T is 0.5 second. A 10 second timeout gives you B(D=10) = 6.7, but with forced retransmission, B(D=0) = 20. That's a huge glow-up 🌸🔥

---

IX. A Sequence Number Consideration 🎀

Okay, sequence numbers have to be big enough to reject duplicate messages 💅 The rule is that it must be impossible to cycle through more than half the sequence number space during a message's lifetime, even at the maximum transmission rate 😭

Let's do the math. If we assume a 1 MegaByte per second network and a maximum lifetime of 500 seconds, the sequence number field of each message has to be able to hold the number 2*500*10**6. That's 10**9, or about 2**30 🤯 So a 32-bit (4-byte) sequence number field is recommended. Periodt 💖

---

X. Additional Control Functions 🧚

Okay so when someone tries to establish an association by sending a SYN, the receiver should be able to deny the attempt with a RELease. There are three ways to do it 🙈

          REJECT.  (I'm busy.  Try again later.)
          ABORT.  (I don't understand what you are sending.
                    (Bad port, etc.))
          ABNORMAL (SYN arrived on a established connection.)
                    (Receiver breaks connection and issues this REL.)

And once an association is already up, the sender can RELease it in either of these ways 💜

          DONE.  (I'm done sending to you.)
          GAG.  (Stop.  You are sending garbage (ACK's).)

Last thing, and it's a vibe: these can be coded as combinations of bits in the FLAGS, which are convenient for programming 🫶✨