RFC 916
Reliable Asynchronous Transfer Protocol (RATP)
RFC 916: Reliable Asynchronous Transfer Protocol (RATP) ✨
Okay bestie, welcome to RFC 916! 🎀 This one is from October 1984, written by G. Finn from ISI 💅. It's an RFC (Request for Comments) that's basically a "hey everyone, here's a proposal, tell me what you think" kind of doc, so it's not a finished standard. It doesn't obsolete or update anything, so it's a totally fresh start 🌸. The whole point is a protocol called RATP that lets two programs talk reliably over a link, so the stuff you send comes out the other end intact and unaltered 🫶.
This is part 1 of 9, so there's more coming! 🦋
Status of This Memo 🎀
Status of This Memo ✨
Okay so the vibe here is: this RFC is a proposed protocol for the ARPA-Internet community 💜, and it's basically begging for discussion and suggestions for improvements 🙏. Distribution is totally unlimited, so share it with everyone 🌈.
Here's the tea 🍓: this paper proposes and specifies a protocol that lets two programs reliably communicate over a communication link ✨. It makes sure whatever goes in one end, if received, arrives at the other end intact and unaltered 💖. The protocol is called RATP, and it's designed for a full duplex point-to-point connection 🔥. It also has some features that are tailored to the RS-232 links that were super common back then 💅.
Introduction 🌸
We are literally witnessing an explosion in the small or personal computer market 🚀. These inexpensive computers usually aren't hooked up to a network, so they're mostly stand-alone devices 🥺. BUT almost all of them have an RS-232 interface, and they usually have a modem too 💻. That means they can talk over the phone to any other similarly equipped computer ☎️✨.
The phone system is a pervasive network, but the big catch is how unpredictable the circuit quality is 💀. Phone circuits were designed for voice, not data 🎙️. Voice can handle way more "noise" than a data circuit can, so a voice circuit tolerates a much higher level of noise than a data circuit does 🙈. Which means it's not unusual for a byte to get noise inserted into it, and for spurious data bytes to get added to the stream too 😭.
So we really need a way to reliably transfer data over an RS-232 point-to-point link, and the need is severe 🔥. As more powerful personal computers show up, they need to talk to each other more and more 💜. The new markets and services these computers will let people use will lean heavily on the phone system 📞. Think electronic mail, electronic banking, ordering merchandise from home with a PC, and so on 🛍️. As the information revolution keeps going, data itself becomes a commodity 💎. All of that needs the data sent or received to be accurate 🫶.
1. Philosopy of Design 🦋
Okay, so there were a LOT of tradeoffs made here 🧠. The top priority was ensuring reliability, and then favoring simplicity of implementation 💖. The hope is that this protocol is simple enough for not only small computers but also stand-alone devices with microcomputers that accept commands over RS-232 lines 🤖. Fancy stuff like dynamic window management [TCP 81] got left out just for simplicity's sake 💅. Having several packets outstanding at once was also cut for the same reason, and data queued to send when a connection gets closed remotely is discarded 🗑️. That removes two states from the protocol implementation, which is honestly iconic 👑.
Someone might ask why we even need this protocol, since there are already RS-232 transport protocols out there 🤔. True, but some of them lack one or more features that are vitally important, or they're just too complex 😤. See Appendix II for a quick survey 📚.
- A protocol that can only transfer data in one direction can't use a single RS-232 link for a full-duplex connection 🙅♀️. So it can't act as a bridge between most computer networks 🌉. It also can't support any app that needs two-way data exchange 💔. It's not really a platform for building most higher level applications either 🏗️. One-way data flow is fine for a weak version of file transfer, but not enough for remote terminal service, transaction oriented processing, and things like that 📁.
- Some existing RS-232 transport protocols only allow fixed size packets, or they don't let the receiver put a limit on the sender's packets 📦. If that block size is too large for the receiving end concentrator, the concentrator will probably immediately invoke flow control 🚧. That leads to a ton of dropped and damaged packets 😩. The receiver MUST be able to tell the sender, at connection initiation, the maximum packet size it's prepared to receive 📏.
Wait, I need to pause on that. The original says "must" there, so I'm keeping it as a MUST, not softening it. Receivers have to inform the sender of the maximum packet size at connection initiation, no exceptions 🔒.
- Some protocols have a bunch of features that may or may not be implemented at each site 🎲. Examples are several checksumming algorithms, different data transmission restrictions, sometimes 8-bit data, sometimes restricted ASCII subsets, and so on 🌀. Then every site is supposed to implement all the various features, and that's rarely actually met 🙃.
Finally, this document is kinda huge 📜. It tries to fully specify how the protocol behaves 🔍. A careful explanation of how it behaves in all circumstances is needed so any questions an implementor has can be answered, and so the protocol can be verified 🧪. The size of this spec should not be read as a sign that it's hard to implement 💁♀️.
1.1. The Host Environment 🌍
This protocol is designed to run on any point-to-point communication link that can transmit and receive data 📡. The link doesn't have to be asynchronous 🙌. Neither end controls when the other decides to transmit, so the link SHOULD be full duplex 💜. In the vast majority of cases, an asynchronous full-duplex RS-232 link is what gets used 🔌.
In practice, this protocol could live anywhere from the RS-232 driver software on a microcomputer in a concentrator all the way up to the user software level 🧩. Ideally it lives inside the host operating system or concentrator 🏠. It should be an option tied to the communication link, selectable by the user program 🎛️. If reliable data transmission matters a lot, the software would pick that option 💯. Once the option is chosen, the initial connection handshaking begins 🤝.
There are plenty of cases where this protocol won't live in a host operating system (at first, it always won't) 😅. There's also tons of stand-alone equipment that accepts commands over an RS-232 link, like a plotter 🖨️. Having a several hour plot ruined by noise on an unreliable line happens way too often 😭. So the sending and receiving sides should be as simple as possible, so applications and stand-alone devices can use the protocol without spending much time or space 🧚.
1.2. Relation to Other Protocols 🔗
The "layering" concept has become the accepted way to design communication protocols 🍰. Since this protocol operates in a point-to-point environment, it covers both the datagram and reliable connection layers 🎀. No multi-network capability is implied 🙅. When a link using this protocol bridges different networks, other protocols like TCP are expected to have their packets fragmented and encapsulated inside this protocol's packets 🎁.
2. Packet Specification 📦
RATP sends data over a full-duplex communication link ✨. Data can go in both directions over the link 🔁. A stream of data is communicated by being broken into 8-bit pieces called octets 🧁. Those octets are serially accumulated to form a packet 📚. The packet is the unit of data communicated over the link 💖. The protocol virtually guarantees that data sent at one end, if received, arrives unaltered and intact at the other end 🫶.
Within an octet, all eight bits contain data 8️⃣. All eight bits MUST be preserved by the link interface and the associated device driver 🔒. In many operating systems this is ensured by putting the connection into RAW or BINARY data mode 🛠️. During normal operation, packets are transmitted and acknowledged one at a time over the link in each direction 🔄. Each packet is made of a HEADER followed by a DATA portion 🧱. The DATA portion MAY be empty 🫧.
NOTE: Some older operating systems and devices don't allow 8-bit communication over an RS-232 link ⚠️. Most of them allow restricted 7-bit communication instead 🙃. RATP can automatically detect this during connection initiation, and it uses a special packing strategy when full 8-bit communication isn't possible 🧩. This is totally transparent to any client software 🫶. See Appendix I for a discussion of this case 📖.
2.1. Header Format 🧾
Byte No.
+-------------------------------+
| |
1 | Synch Leader | Hex 01
| |
+-------------------------------+
| S | A | F | R | S | A | E | S |
2 | Y | C | I | S | N | N | O | O | Control
| N | K | N | T | | | R | |
+-------------------------------+
| |
3 | Data length (0-255) |
| |
+-------------------------------+
| |
4 | Header Checksum |
| |
+-------------------------------+
Header Portion of a Packet2.1.1. Synch Leader 🎯
RS-232 gives us a self-clocking communications medium 🕰️. The wires data flows over are often in "noisy" environments, where the noise can show up as unwanted added data 📢. That's why the beginning of a packet is marked by a one octet SYNCH pattern 🚦. This lets the receiver throw away noise that shows up on the connection before a packet arrives 🗑️. The SYNCH pattern is defined to be the one octet hex 01, the ASCII Start Of Header character <SOH> 🎉.
The SYNCH pattern SHOULD ideally be unlikely to occur as the result of noise 🤞. Different modems and such respond to noise differently, so this is hard to achieve 😵. The chosen pattern is thought to be a good compromise, since many modems show noise by setting the high order bits 💭. Situations will happen where the receiver is scanning for the start of a packet and sees a spurious SYNCH pattern 👀. To catch that kind of situation, a header checksum is provided (see below) 🛡️.
2.1.2. Control Bits 🎛️
The first octet after the SYNCH pattern holds a 5-bit field of control flags plus two 1-bit sequence number fields 🔢. The last bit is reserved and MUST be zero 🙅♀️.
2.1.2.1. SYN - Synchronize Flag 🤝
Synchronize the connection 🔗. No data MAY be sent in a packet that has the SYN flag set 🚫.
2.1.2.2. ACK - Acknowledge Flag ✅
The acknowledge number is significant 💌. Data MAY accompany a packet that has this flag set, as long as neither SYN, RST, nor FIN is also set 💜. Once a connection has been established, this is always set 🌈.
That's a wrap on part 1! 💖 Part 2 is coming next, bestie, so stay tuned 🦋✨
2.1.2.3. RST - Reset Flag 🚨
Okay bestie, RST is the panic button. It's how one end of a connection can reset the other when something anomalous (aka weird) happens. 😭 And no data may be sent in a packet that has the RST flag set. No exceptions, no cap 💅
2.1.2.4. FIN - Finishing Flag 🦋
FIN basically says "I'm done." It means no more data will be sent to the other end of the connection, and no more data will be accepted either. Same rule as RST, though: no data may be sent in a packet that has the FIN flag set. Gone, but make it clean ✨
2.1.2.5. SN - Sequence Number 🔢
This is the Sequence Number attached to this packet. Simple, iconic, no drama 💖
2.1.2.6. AN - Acknowledge Number 🫶
If the ACK control flag is set, this is the next Sequence Number the sender of the packet is expecting to receive. It's giving "here's what I want next" energy 🌸
2.1.2.7. EOR - End of Record 🎀
The EOR bit is a little helper for higher level protocols that might need to fragment their packets. Like, the Internet protocol often uses packets as big as 576 octets, and a packet that size would need fragmenting when it's carried over this protocol. 🙈 If EOR is set, it's just telling the higher level that a record ends in this packet. It's information only, so the higher level is the one responsible for setting or clearing it when it builds packets to send. Also, the interface to the protocol has to give a way to read, set, and clear this bit 💅
2.1.2.8. SO - Single Octet ⌨️
Okay, so one use case that's considered super important is single character transmission. Picture a user typing on a personal computer keyboard and sending each key to another computer over an unreliable link. Rapid interactive response is the goal, so lots of typed characters are expected to go out one at a time. To keep the overhead low for this special case, the SO control flag exists 👑
The SO flag means nothing if the SYN, RST, or FIN flags are set. Assuming none of those are set, SO set means this packet carries a single octet of data. Since the data is always one octet, the LENGTH field is superfluous and actually holds the data octet itself. The data portion of the packet isn't transmitted at all 🧚
This is the glow-up part 🌈 Without SO, a packet would need seven octets. With it, only four are needed, so transmission efficiency improves by 40 percent. And the header checksum still protects that single octet of data 💜
2.1.3. Length 📏
The second octet after the SYNCH pattern holds length info. If the SYN bit is present, this field is the maximum number of data octets the receiver is allowed to transmit to the sender in any single packet. That quantity is called the MDL. A sender may say it doesn't want to accept any data octets by setting an MDL of zero. In that case, presumably all the data is moving from sender to receiver. Obviously, if data is going to be transmitted, both sides of a connection can't have an MDL of zero 🙅♀️
If none of SYN, RST, or FIN are set, this is an 8-bit field called LENGTH. In that case, if the SO bit is set, LENGTH contains a single octet of data. Otherwise, it holds the count of data octets in the packet. A single packet can carry anywhere from zero (0) up to MDL octets of data. And MDL is capped at a maximum of 255 🔥
2.1.4. Header Checksum 🧮
The header checksum algorithm is the 8-bit version of the 16-bit data checksum we'll get to below. It's built and processed in a similar way, just eight bits wide instead of sixteen. When sending, the header checksum octet starts out cleared. Then an 8-bit sum of the control, length, and header checksum octets is formed using end-around carry. That sum gets complemented and stored in the header checksum octet. On receipt, the receiver forms the same 8-bit end-around carry sum of those same three octets. If the sum is octal 377, the header is presumed valid. In all other cases, the header is assumed to be invalid ✅
Why bother giving the header its own protection? That's covered in the chapter on error handling. The header checksum covers the control and data length octets, and it does not include the SYNCH pattern 🦋
2.2. Data Format 🍓
The data portion of a packet comes right after the header if the SO flag isn't set and LENGTH > 0. It's made of LENGTH data octets, immediately followed by two data checksum octets. If it's present, the data portion has LENGTH+2 octets total 💅
Data Byte No.
+-------------------------------+
1 | | High order \
+-- --+ > Word
2 | | Low order /
+-- --+
. | Data | High order \
+-- --+ > Word
. | | Low order /
+-- --+
LENGTH | | High order \
+-------------------------------+ > Word
| Imaginary padding octet 0 | Low order /
+-------------------------------+
LENGTH+1 | | High order \
+-- Data Checksum --+ > Word
LENGTH+2 | | Low order /
+-------------------------------+
Data Portion of a Packet2.2.1. Data Checksum 🌸
The last two octets of the data portion are a data checksum. This is a 16-bit checksum that catches incorrectly transmitted data. It's been shown to be a reliable way to detect most kinds of bit drop-out and bit insertion. It doesn't guarantee that every such error gets caught, though. The chance that one slips through undetected is on the order of 2**(-16) 🙈
The checksum octets come after the data so the sender can compute the checksum while it's transmitting, and the receiver can compute it while it's receiving. That means neither side has to store the whole packet and then go back for a separate checksumming pass. Efficient, bestie ✨
Order of Transmission
How 8-bit octets get assembled into 16-bit words is a big deal. You have to decide which octet is the low order one and which is the high order one, and that has to be rigidly specified if you want to compute 16-bit checksums. This protocol uses big endian ordering, as shown in the diagram above [Cohen 81] 🧠
Checksum Algorithm
The checksum algorithm is similar to the one used by the IP and TCP protocols [IP 81] [TCP 81]. It's been shown to be reliable and relatively easy to compute. If you want a deeper dive into its properties, the interested reader can check out [TCP Checksum 78] 📚
The checksum algorithm works like this:
SENDER 💌
The unsigned sum of the 16-bit words in the data portion of the packet is formed. Any overflow gets added into the lowest order bit. This sum doesn't include the header portion of the packet. When building a packet for transmission, the two octet checksum field is zero. The sum is then bit complemented and inserted into the checksum field before the packet is sent.
If the total number of data octets is odd, the last octet is padded on the right (low order) with zeros so it forms a 16-bit word for checksum purposes. That pad octet is not transmitted as part of the packet 🫧
RECEIVER 📨
The sum is computed the same way, but this time it includes the values received in the checksum field. If the 16-bit sum is octal 177777, the data is presumed valid. In all other cases, the data is presumed invalid 🙅♀️
This unsigned 16-bit sum adds 16-bit quantities, with any overflow bit added into the lowest order bit of the sum. That's called 'end around carry', and it gives a couple of really nice properties: 1) it's fully commutative, so summing in any order gives the same result, and 2) if you apply a given rotation to each quantity before addition, then apply the inverse rotation to the final total, the result is equivalent to any other rotation you pick. That second one is the real win, because it lets little endian machines like the PDP-11 grab 16-bit quantities and add them in byte swapped order 👑
Here's the PDP-11 code for calculating the checksum:
CLR R0 ; R0 will get the checksum
; R2 contains LENGTH count
LOOP: ADD (R1)+,R0 ; Add the next 16-bit byte
ADC R0 ; Make any carry be end around
SOB R2,LOOP ; Loop over entire packet
COM R0 ; Bit complement result2.3. Sequence Numbers 🔁
Sequence numbers team up with acknowledge numbers to do two jobs. They tell the sender that its last data packet was received, and they tell the receiver which sequence number the next data packet should carry. When the ACK flag is set in a packet, the AN field holds the sequence number of the next data packet the sender is expected to send. The sender looks at the AN field and, by implication, knows the packet it just sent should have had this sequence number:
<AN received-1 modulo 2>If it did have that number, the packet is considered acknowledged 🎉
The receiver works the same way in reverse. It expects the next data packet it sees to have an SN field value equal to the AN field of the last acknowledge message it sent. If that's not the case, the receiver assumes it's getting a duplicate of a data packet it already acknowledged. That suggests the packet carrying the acknowledgment never arrived, so the packet with the acknowledgment should be retransmitted. The duplicate data packet is discarded 🗑️
Only packets that contain status flags (SYN, RST, FIN, or SO) or data need acknowledgment. A packet that's only an acknowledgment, i.e. <AN=n><CTL=ACK>, doesn't require a response, since it has no status flags or data in it 💜
Both the AN and SN fields are a single bit wide 🦋. Since at most one packet is being sent or acknowledged in a particular direction at any one time, a single bit is enough for duplicate packet detection and for removing a packet from the retransmission queue ✨. The arithmetic to advance these numbers is modulo 2, so once a data packet is acknowledged, the sender's next sequence number is the current one plus one, modulo 2:
<SN = SN + 1 modulo 2>Okay, so, the individual acknowledgment of each data packet can make you think side A can't send data to side B until it hears a packet from B. Like, A has to wait for B's packet, acknowledge it, and then tuck some of its own data into that acknowledgment. 🙅♀️ That's not how it works, bestie.
As long as its last packet that needed a response has been acknowledged, each side of a connection is free to send a data packet whenever it wants 💅. And if one side is sending data and also needs to acknowledge a data packet from the other side, it's most efficient to combine both jobs into one packet. Iconic efficiency 🔥.
2.4. Maximum Packet Size
The maximum packet size is:
SYNCH + HEADER + Data Checksum + 255 = 261 octetsSo there's no need to allocate more storage than that for any received packet 🧚.
3. The Opening and Closing of a Connection
3.1. Opening a Connection
Okay, the "three-way handshake" is the procedure used to set up a connection 🤝. It's normally started by one end and answered by the other. It still works if both sides start it at the same time ✨. Experience has shown that opening a connection this way keeps the chance of false connections down to an acceptably low level 🙈.
Here's the simplest version of the three-way handshake. Time goes top to bottom, line by line, and some lines are numbered so we can point at them 📍. User events go in brackets, like [OPEN]. An arrow (-->) shows which way a packet is flowing, and an ellipsis (...) means a packet is in transit 🚚. Side A and side B are the two ends of the connection. An "XXX" means the packet got lost or rejected 💀. The contents of the packet are shown in the middle of each line. The state of both connections is whatever the departure or arrival of the packet on that line caused 🌸. The data portion of a packet is left out to keep things clean.
Side A Side B
1. CLOSED LISTEN
2. [OPEN request]
SYN-SENT -> <SN=0><CTL=SYN><MDL=n> ...
3. --> SYN-RECEIVED
... <SN=0><AN=1><CTL=SYN,ACK><MDL=m> <--
4. ESTABLISHED <--
--> <SN=1><AN=1><CTL=ACK><DATA> ...
5. --> ESTABLISHEDOn line 2, the user on side A has asked for a connection to be opened 🎀. Side A tries to open it by sending a SYN packet to side B, which is in the LISTEN state. The SYN gives its initial sequence number, which is zero here. It also puts the largest number of data octets it can handle in any one packet into the LENGTH field of the header, which is the MDL. The MDL is normally positive. Sending this packet puts A into the SYN-SENT state.
On line 3, side B has just received the SYN from A, so B moves to SYN-RECEIVED 👀. Now B sends a SYN back to A, acknowledging the SYN it just got. Notice the AN field says B is now expecting to hear SN=1, which acknowledges the SYN from A that used SN=0 💅. B also puts the largest number of data octets it's ready to handle in its LENGTH field.
On line 4, side A receives the SYN from B, which acknowledges A's original SYN. That puts A into ESTABLISHED 🎉. Side A can now be confident that B expects to receive more packets from A.
A is now free to send B the first DATA packet. On line 5, when side B receives that packet, B moves into ESTABLISHED too 👑. DATA can't be sent until the sender is in ESTABLISHED, because the LENGTH field is used to set the MDL when the connection is opened 🧐.
3.2. Recovering from a Simultaneous Active OPEN
Honestly, it's totally possible for both ends to choose an active OPEN at the same time 😭. In that case, neither end is in LISTEN, and both send SYN packets. A reliable bidirectional protocol has to recover from this situation 🫶. It should recover in a way that lets the connection be successfully opened.
Side A Side B
1. CLOSED CLOSED
2. [OPEN request]
SYN-SENT --> <SN=0><CTL=SYN><MDL=n> ...
3. ... [OPEN request]
<SN=0><CTL=SYN><MDL=m> <-- SYN-SENT
4. --> SYN-RECEIVED
... <SN=0><AN=1><CTL=SYN,ACK><MDL=m> <--
5. (packet finally arrives)
SYN-RECEIVED <-- <SN=0><CTL=SYN><MDL=m>
--> <SN=0><AN=1><CTL=SYN,ACK><MDL=n> --> ESTABLISHED
... <SN=1><AN=1><CTL=ACK> <--
6. (packet finally arrives)
ESTABLISHED <-- <SN=0><AN=1><CTL=SYN,ACK><MDL=m>
--> <SN=1><AN=1><CTL=ACK> ...During a simultaneous connection, both sides of the connection go from CLOSED through SYN-SENT to SYN-RECEIVED, and then finally to ESTABLISHED 🦋✨.
3.3. Detecting a Half-Open Connection
Any computer can crash after a connection has been set up 💥. After it recovers, it might try to open a brand-new connection. The other end has to be able to spot this and treat it as an error 🚨.
Side A Side
1. ESTABLISHED ESTABLISHED
--> <SN=0><AN=1><CTL=ACK><DATA> ...
-->
(crashes)
2. XXX <SN=1><AN=1><CTL=ACK><DATA> <--
3. (attempts to open new connection )
--> <SN=0><CTL=SYN><MDL=m> -->
... <SN=0><AN=1><CTL=RST,ACK> <-- (abort)
CLOSED
4. <--
(connection refused)
CLOSED3.4. Closing a Connection
Either side can choose to close an established connection 👋. You do it by sending a packet with the FIN control bit set. A FIN packet can't carry any data 🙅♀️. The other end responds by shutting down its own end of the connection and sending back a FIN, ACK 💅.
Side A Side B
1. ESTABLISHED ESTABLISHED
2. [CLOSE request from user]
FIN-WAIT --> <SN=0><AN=1><CTL=FIN> ...
3. --> LAST-ACK
... <SN=1><AN=1><CTL=FIN,ACK> <--
4. TIME-WAIT <--
--> <SN=1><AN=0><CTL=ACK> ...
5. --> CLOSED
6. (after 2*SRTT time passes)
CLOSEDOn line 2, the user on side A of the fully open connection decides to close it down with a CLOSE call 🥺. No more data gets accepted for sending. If data is still unsent, the message "Warning: Unsent data remains." is passed to the user ⚠️. No more data will be received either. A packet containing a FIN and no data is built and sent. Side A goes into FIN-WAIT.
Heads up, bestie: if there's still unsent data when you CLOSE, you'll get the "Warning: Unsent data remains." message 🚨.
Side B sees the FIN and immediately builds a FIN, ACK in response, then goes into LAST-ACK 🫠. When side A gets that FIN, ACK, it immediately sends back an ACK and moves to TIME-WAIT. On line 5, side B gets the final acknowledgment of its FIN, ACK and goes to CLOSED 🌈. On line 6, after waiting long enough to be sure its last acknowledgment arrived, side A goes to CLOSED too ✨. (SRTT is the Smoothed Round Trip Time, and it's defined in section 6.3.1 ⭐.)
4. Packet Reception
Receiving a packet is pretty straightforward, but there are a few points worth talking about 🧠. This chapter goes through packet reception one stage at a time, in time order 📚.
Synch Detection
The first stage in receiving a packet is finding the SYNCH pattern 🔍. Octets are read nonstop and thrown away until the SYNCH pattern shows up. Once SYNCH has been seen, move on to the Header Reception stage 🚀.
Header Reception
The rest of the header is three octets long 🎀. Nothing else can happen until the whole header has been read. Once it's read, the header checksum test runs 🧮. If that test fails, it's assumed the current SYNCH pattern came from a data error 😬. Since the correct SYNCH could show up right after the current one, go back to the Synch Detection stage, but treat the three octets of the header that followed the bad SYNCH as new input 🔁.
If the header checksum test succeeds, move on to the Data Reception stage 💖.
Data Reception
Next, we figure out how much of the packet is left to read 📏. If any of the SYN, RST, SO, or FIN flags are set, then legally the whole packet has already been read, and it's considered to have 'arrived' 🎁. A packet with one of those flags set has no data portion. Otherwise, the LENGTH field says how much data is still left to read. In that case, if LENGTH is zero, the packet has no data portion and is considered to have arrived 🦋.
Now we assume a data portion is present and LENGTH was non-zero. The data checksum is LENGTH+2 octets, so those must be read next 🧁. Once they're read, the data checksum test runs. If that test fails, the entire packet is thrown out and we go back to the Synch Detection stage 💔. If it passes, the packet is considered to have arrived ✅.
Once a packet has arrived, it's handed up to the upper level protocol software 🚚. In a multiprocess implementation, packet reception starts over at the Synch Detection stage 🔄.
5. Functional Specification
Okay, here's the big picture 🌟. A handy way to talk about and build protocols is as a state machine 🧩. A connection can be thought of as passing through a bunch of states, with possible error conditions, from the moment it starts until it closes 🎬. In this model, each state is a known point in a connection's history 📖. The connection moves from state to state in response to events 💫. Those events come from user calls to the protocol interface (like a request to open or close a connection, or data to send), from incoming packets 📦, and from timeouts ⏰.
Okay so info about a connection has to be kept at both ends of it 💖 Following the lingo from [TCP 81], all the stuff a connection needs to work properly is called the Transmission Control Block, or TCB 🎀. The user requests to the protocol interface are OPEN, SEND, RECEIVE, ABORT, STATUS, and CLOSE ✨.
This chapter is split into three parts 🧚. First we get a quick rundown of each state, then a closer look at which transitions can happen between states, and last a deep dive into what each state actually does 🔥.
5.1. Protocol States
The states used to describe this protocol are:
- LISTEN 👂 Waiting for a connection from the other end of the link.
- SYN-SENT 📤 Waiting for a matching connection request, after you've already sent a connection request.
- SYN-RECEIVED 📥 Waiting for a confirming connection request acknowledgment, after you've both received and sent a connection request.
- ESTABLISHED 🎉 The connection is fully opened at both ends. This is the normal state for data transfer, and it's giving main character energy.
- FIN-WAIT 👋 You're waiting for a connection termination request from the other end, and also for an acknowledgment of a termination request you sent earlier.
- LAST-ACK 🫶 This end has seen and acknowledged a termination request from the other end. You've responded with a termination request of your own and are now waiting for an acknowledgment of that one.
- CLOSING 🤝 Waiting for an acknowledgment of a connection termination request.
- TIME-WAIT ⏳ Waiting for enough time to pass so you can be sure the other end received the acknowledgment of its termination request.
- CLOSED 💀 A fictional state (not a real place you can hang out, lol). It represents a completely terminated connection. If either end of a connection is in this state, it will neither send nor receive data or control packets. Iykyk 🙈
5.2. State Transitions
This section covers the events that make the protocol leave its current state. Each state gets a quick mention, followed by a list of the events that make it depart and which state it moves to as a result. Departures caused by the presence of an RST flag are not shown 🌸
5.2.1. LISTEN
This is a request to listen for any connection from the other end of the link. In this state, no packets are sent. The connection may be thought of as half-open. A STATUS request will return this information to the caller 👀
It's arrived at from the CLOSED state in response to a passive OPEN. In a passive OPEN, no packets are sent, and the interface is just waiting for the other end of the link to start a connection. This state can also be reached in certain cases in response to an RST connection reset request 🔄
Departures
- A CLOSE request is made by the user. Delete the half-open TCB and go to the CLOSED state.
- A packet arrives with the SYN flag set. Retrieve the sender's MDL that they placed into the LENGTH field. Set AN to be received SN+1 modulo 2. Build a response packet with SYN, ACK set. Choose your MDL and place it into the LENGTH octet. Choose your initial SN and place it in AN. Send this packet and go to the SYN-RECEIVED state 🚀
5.2.2. SYN-SENT
It's arrived at from the CLOSED state in response to a user's active OPEN request 💌
Departures
- A CLOSE request is made by the user. Delete the TCB and go to the CLOSED state.
- A packet arrives with the SYN flag set. Retrieve the sender's MDL that they placed into the LENGTH field. Set AN to be received SN+1 modulo 2. Build a response packet with ACK set, and place AN in it. Send this packet and go to the SYN-RECEIVED state.
- A packet arrives with the SYN, ACK flags set. Retrieve the sender's MDL that they placed into the LENGTH field. Set AN to be received SN+1 modulo 2. Build a response packet with ACK set. Set SN to be SN+1 modulo 2, then place SN and AN into the header. Remembering the other end's MDL, build the data portion of the packet. Send this packet and go to the ESTABLISHED state 🥳
5.2.3. SYN-RECEIVED
It's arrived at from the LISTEN and SYN-SENT states in response to an arriving SYN packet 📩
Departures
- A CLOSE request is made by the user. Create a packet with FIN set. Send it and go to the FIN-WAIT state.
- A packet arrives with the ACK flag set. This packet acknowledges a previous SYN packet. Go to the ESTABLISHED state. The TCB should now note that the connection is fully opened ✨
- A packet arrives with the FIN flag set. The other end has decided to close the connection. Create a packet with FIN, ACK set. Send it and go to the LAST-ACK state.
5.2.4. ESTABLISHED
This is the normal state for a connection 💕 Data packets may be exchanged in both directions (as long as the MDL allows it). It's arrived at from the SYN-RECEIVED and SYN-SENT states in response to the completion of connection initiation 🎀
Departures
- In response to a CLOSE request from the user. Set AN to be the most recently received SN+1 modulo 2. Build a packet with FIN set. Set SN to be SN+1 modulo 2, place SN and AN into the header, and send the packet. Go to the FIN-WAIT state.
- A packet containing a FIN is received. Set AN to be received SN+1 modulo 2. Build a response packet with both FIN and ACK set. Set SN to be SN+1 modulo 2, then place SN and AN into the header. No data portion is built. Send this packet and go to the LAST-ACK state 😭
5.2.5. FIN-WAIT
It's arrived at from either the SYN-RECEIVED state or the ESTABLISHED state. In both cases, the user has requested a CLOSE of the connection and a packet with a FIN was sent 🫠
Departures
- A FIN, ACK packet is received that acknowledges the FIN just sent. Go to the TIME-WAIT state.
- A FIN packet is received, which means the other end of the connection has simultaneously decided to close. Set AN=received SN+1 modulo 2, and SN=SN+1 modulo 2. Send a response packet with the ACK set. Go to the CLOSING state.
5.2.6. LAST-ACK
It's arrived at from the ESTABLISHED and SYN-RECEIVED states 🌙
Departures
- An ACK is received for the last packet sent, which was a FIN. Delete the TCB and go to the CLOSED state.
5.2.7. CLOSING
It's arrived at from the FIN-WAIT state 🫧
Departures
- An ACK is received for the last packet sent, which was a FIN. Go to the TIME-WAIT state.
5.2.8. TIME-WAIT
It's arrived at from the FIN-WAIT and CLOSING states 🕰️
Departures
- This state waits until 2*SRTT time has passed. It then deletes the TCB associated with the connection and goes to the CLOSED state.
5.2.9. CLOSED
This state can be reached for a number of reasons:
- While in the LISTEN state, the user requests a CLOSE.
- While in the SYN-SENT state, the user requests a CLOSE.
- While in the TIME-WAIT state, the 2*SRTT time period has elapsed.
- While in the LAST-ACK state, an arriving packet has an ACK of the previously sent FIN packet.
In this state, no data is read or sent over the link. To leave this state, an outside request to open a new connection is required 🔐
Departures
- The user requests an active OPEN. Create a packet with SYN set. Choose your MDL and place it into the LENGTH octet. Choose your initial SN. AN is immaterial. Send this packet and go to the SYN-SENT state. The TCB for this connection is created. The connection may be thought of as half-open. A STATUS request will return this information to the caller 🚦
- The user requests a passive OPEN. The TCB for this connection is created. The connection may be thought of as half-open. A STATUS request will return this information to the caller. Go to the LISTEN state 👂
5.3. State Behavior
This section discusses in detail how each state behaves when a packet arrives. In what follows, a packet is not considered to have arrived until it has passed a number of tests (see the chapter entitled: Packet Reception) 🔍
The method chosen to describe state behavior is tabular. Each state is listed opposite a sequence of named procedures to execute whenever a packet has arrived 📋
STATE BEHAVIOR
=============+========================
LISTEN | A
-------------+------------------------
SYN-SENT | B
-------------+------------------------
SYN-RECEIVED | C1 D1 E F1 H1
-------------+------------------------
ESTABLISHED | C2 D2 E F2 H2 I1
-------------+------------------------
FIN-WAIT | C2 D2 E F3 H3
-------------+------------------------
LAST-ACK | C2 D3 E F3 H4
-------------+------------------------
CLOSING | C2 D3 E F3 H5
-------------+------------------------
TIME-WAIT | D3 E F3 H6
-------------+------------------------
CLOSED | G
-------------+------------------------For example, in the ESTABLISHED state, when a packet arrives, procedure C2 is executed, then D2, then E, F2, H2, and finally I1. Any procedure may end the processing that's happening or cause a state change. Note that these procedures run in sequence, first C2, then D2, and so on. The time ordering cannot be mixed 🧩
The particular actions associated with each procedure are now described 💅
Procedure A
This procedure details the behavior of the LISTEN state. First, check the packet for the RST flag. If it's set, the packet is discarded and ignored, and you return and continue the processing associated with this state 🙅♀️
We'll assume now that the RST flag was not set. Check the packet for the ACK flag. If it's set, that's an illegal condition, since no connection has been opened yet. Send an RST packet with the correct response SN value:
<SN=received AN><CTL=RST>Return to the current state without any further processing 🫶
We're still in the LISTEN state, bestie 🎀 and now we're assuming neither the RST nor the ACK flag got set. 🫣
Peep for a SYN flag. If it's there, someone is trying to open a connection, so make a TCB for it 📝. The sender dropped its MDL in the LENGTH field, and their starting SN is in there too. Grab both and stash them in the TCB 💾. The SO flag gets ignored here, because it means nothing when SYN, RST, or FIN is set 🙈.
Then send a SYN packet that acknowledges the SYN you got. Pick your own starting SN and your own MDL for this end of the connection 💖:
<SN=0><AN=received SN+1 modulo 2><CTL=SYN, ACK><LENGTH=MDL>Then go to the SYN-RECEIVED state, no extra processing needed ✨.
Anything that fails all of those checks gets discarded and ignored 🗑️. Stay in your current state, no extra processing. Bye bye 👋
Procedure B 🦋
This is the SYN-SENT state, and we land here when this end decides to do an active OPEN 🚀.
First, check the packet for the ACK flag. If ACK is set, check whether the AN value was what you expected. If it was, keep going below. If it wasn't, the AN value is unexpected 😬. If RST was set, discard the packet and stay in the current state with no extra processing. If RST wasn't set, send a reset:
<SN=received AN><CTL=RST>Then discard the packet and stay in the current state with no extra processing.
At this point, either ACK was set and AN was what you expected, or ACK wasn't set at all. Second, check the RST flag. If RST is set, there are two cases 💅:
- If ACK is set, discard the packet, flush the retransmission queue, tell the user "Error: Connection refused", delete the TCB, and go to the CLOSED state without any further processing.
- If ACK wasn't set, discard the packet and stay in this state with no extra processing.
At this point we assume the packet had an ACK that was Ok, or no ACK at all, and no RST. Now check the packet for the SYN flag. If ACK is set, then our SYN got acknowledged 🥰. Store the MDL you received in the TCB. We're technically in the ESTABLISHED state now 👑. Send an acknowledgment packet, plus any initial data that's queued to send:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK><DATA>Then go to the ESTABLISHED state with no extra processing.
If SYN is set but ACK isn't, the other end also did an active open 👀. Acknowledge the SYN, pick your MDL, and send:
<SN=0><AN=received SN+1 modulo 2><CTL=SYN, ACK><LENGTH=MDL>Then go to the SYN-RECEIVED state with no extra processing.
Anything that doesn't meet the tests above gets discarded and ignored 🫠. Stay in the current state with no extra processing.
Procedure C1 🌸
Check the received SN field. If the SN value was expected, return and keep going with the processing for this state ✅.
If it wasn't what we expected, then if RST or FIN was set, discard the packet and stay in the current state with no extra processing.
If neither RST nor FIN was set, we assume this packet is a duplicate of one we already got 👯. Send an ACK back:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK>Then discard the duplicate and stay in the current state with no extra processing.
Procedure C2 🧚
Check the received SN field. If the SN value was expected, return and keep going with the processing for this state ✨.
If it wasn't, then if RST or FIN was set, discard the packet and stay in the current state with no extra processing.
If SYN was set, we assume the other end crashed and is trying to open a brand new connection 💀. We respond by sending a legal reset:
<SN=received AN><AN=received SN+1 modulo 2><CTL=RST, ACK>This makes the other end, which is still in SYN-SENT, close 🔒. Flush the retransmission queue, tell the user "Error: Connection reset", discard the packet, delete the TCB, and go to the CLOSED state with no extra processing.
If none of RST, FIN, or SYN was set, we assume this packet is a duplicate of one we already got 🙃. Send an ACK back:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK>Then discard the duplicate and stay in the current state with no extra processing.
Procedure D1 💜
Check the packet for an RST flag. If RST isn't set, return and keep going with the processing for this state 🌈.
RST is now assumed to be set 😱. If the connection started from the LISTEN state (it was passively opened), flush the retransmission queue, discard the packet, and go to the LISTEN state with no extra processing.
If the connection was started actively instead (it came from SYN-SENT), flush the retransmission queue, tell the user "Error: Connection refused", discard the packet, delete the TCB, and go to the CLOSED state with no extra processing.
Procedure D2 🍓
Check the packet for an RST flag. If RST isn't set, return and keep going with the processing for this state ✅.
RST is now assumed to be set 💔. Flush any data that's still waiting to be sent. Flush the retransmission queue, tell the user "Error: Connection reset.", discard the packet, delete the TCB, and go to the CLOSED state with no extra processing.
Procedure D3 🎀
Check the packet for an RST flag. If RST isn't set, return and keep going with the processing for this state 🌸.
RST is now assumed to be set. Discard the packet, delete the TCB, and go to the CLOSED state with no extra processing 🫡.
Procedure E 💥
Check for the SYN flag. If SYN isn't set, return and keep going with the processing for this state ✅.
Now we assume SYN was set. A SYN showing up here is an error 🚨. Flush the retransmission queue and send a legal RST packet.
If ACK was set, send:
<SN=received AN><CTL=RST>If ACK wasn't set, send:
<SN=0><CTL=RST>The user should receive the message "Error: Connection reset.", then the TCB gets deleted and we go to the CLOSED state with no extra processing 💅.
Procedure F1 🦄
Check for the ACK flag. If ACK isn't set, discard the packet and return with no extra processing 🙅.
Now we assume ACK was set. If the AN field value was what we expected, return and keep going with the processing for this state ✨.
Now we assume ACK was set but the AN field value was unexpected 😬. If the connection started from the LISTEN state (it was passively opened), flush the retransmission queue, discard the packet, and send a legal RST packet:
<SN=received AN><CTL=RST>Then delete the TCB and go to the LISTEN state with no extra processing.
Otherwise, the connection was started actively (it came from SYN-SENT). Tell the user "Error: Connection refused", flush the retransmission queue, discard the packet, and send a legal RST packet:
<SN=received AN><CTL=RST>Then delete the TCB and go to the CLOSED state with no extra processing.
Procedure F2 🌷
Check for the ACK flag. If ACK isn't set, discard the packet and return with no extra processing 🙅.
Now we assume ACK was set. If the AN field value was what we expected, flush the retransmission queue and tell the user "Ok" if a buffer has been fully acknowledged 🙌. Another packet with data can go out now. Return and keep going with the processing for this state.
Now we assume ACK was set but the AN field value was unexpected. This is treated as a duplicate acknowledgment 🙄. It gets ignored, and we return and keep going with the processing for this state.
Procedure F3 🌊
Check for the ACK flag. If ACK isn't set, discard the packet and return with no extra processing 🙅.
Now we assume ACK was set. If the AN field value was what we expected, keep going with the processing for this state 💫.
Now we assume ACK was set but the AN field value was unexpected. This gets ignored. Return and keep going with the processing for this state 🫶.
Procedure G 🧊
This is the CLOSED state of a connection 🔐. Every incoming packet gets discarded. If the packet had RST set, take no action. Otherwise we have to build an RST packet, because this end is closed and the other end has wrong info about the state of the connection, so it needs to hear about it 📣.
If ACK was set, send:
<SN=received AN><CTL=RST>If ACK wasn't set, send:
<SN=0><AN=received SN+1 modulo 2><CTL=RST, ACK>After sending the reset packet, return to the current state with no extra processing 🩷.
Procedure H1 🌙
Our SYN got acknowledged 🎉. We're technically in the ESTABLISHED state now. Send any initial data that's queued to go:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK><DATA>Go to the ESTABLISHED state and run procedure I1 to process any data in this packet 💖.
Anything that doesn't meet the tests above gets discarded and ignored 🗑️. Stay in the current state with no extra processing.
Procedure H2 🍒
Okay bestie, we're picking up right where the FIN check lives 🔍
Check the presence of the FIN flag. If FIN is not set, then just keep going with the processing for this state 💖
So now we're assuming FIN is set 👀 That means the other end has decided to close the connection 💅 Flush the retransmission queue. If any data is still waiting to go out, tell the user Warning: Data left unsent. The user MUST also be informed Connection closing. ✨ An acknowledgment for the FIN MUST be sent too, and it also says this end is closing too 🫶:
<SN=received AN><AN=received SN + 1 modulo 2><CTL=FIN, ACK>Then go to the LAST-ACK state without any further processing. Bye bye, no extra steps 🦋
H3
This state is the final behavior of the FIN-WAIT state 🌸
If the packet did not contain a FIN, it's a duplicate 🙈 That means the other end hasn't seen the FIN we sent earlier. Don't panic, we just rely on retransmission of our earlier FIN packet to tell the other end we want to close. Discard the packet and return without any further processing.
Now we have a packet that should contain a FIN. By the rules of this protocol, an ACK of a FIN requires a FIN, ACK in response and no data 📜 If the packet has data in it, that's an illegal condition 💀 Send a reset:
<SN=received AN><AN=received SN+1 modulo 2><CTL=RST, ACK>Then discard the packet, flush the retransmission queue, tell the user Error: Connection reset., delete the TCB, and go to the CLOSED state without any further processing. Rough day, but it's giving clean exit 🧚
We now assume the FIN flag was set and no data came along with it. If the AN field value was expected, then this packet is acknowledging a FIN we already sent 🎀 The other end is assumed to be closing too, and it's waiting on an acknowledgment. So send an acknowledgment of the FIN:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK>Start the 2*SRTT timer associated with the TIME-WAIT state, discard the packet, and go to the TIME-WAIT state without any further processing 🌈
Otherwise, the AN field value was unexpected. That means both sides are closing at the same time, which is a whole main character moment 👑 Send an acknowledgment of the FIN:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK>Discard the packet and go to the CLOSING state without any further processing ⭐
H4
This state is the final behavior of the LAST-ACK state 🥹
If the AN field value is expected, then this ACK is responding to the FIN, ACK we recently sent 💜 This is the final acknowledging message, and it means both sides agree to close the connection. Discard the packet, flush all queues, delete the TCB, and go to the CLOSED state without any further processing. Iconic finish 🏁
Otherwise, the AN field value was unexpected. Discard the packet and stay in the current state without any further processing 🫠
H5
This state is the final behavior of the CLOSING state 🌷
If the AN field value was expected, then this packet acknowledges the FIN we recently sent 🍓 This is the final acknowledging message, and it means both sides agree to close the connection. Start the 2*SRTT timer associated with the TIME-WAIT state, discard the packet, and go to the TIME-WAIT state without any further processing ✨
Otherwise, the AN field value was unexpected. Discard the packet and stay in the current state without any further processing 💅
H6
This state is the behavior of the TIME-WAIT state 🕰️ Check the presence of the ACK flag. If ACK is not set, discard the packet and return without any further processing.
Check the presence of the FIN flag. If FIN is not set, discard the packet and return without any further processing.
We now assume the FIN flag was set. This situation means the last acknowledgment of the FIN packet sent by the other end didn't arrive 🥺 So resend the acknowledgment:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK>Restart the 2*SRTT timer, discard the packet, and stay in the current state without any further processing 🧸
I1
This is the stage of processing in the ESTABLISHED state where all the flag bits have been handled and only data might be left 📦 Check whether the packet contains data. If it doesn't, discard the packet and return to the current state without any further processing.
We assume the packet contained data, meaning either the SO flag was set or LENGTH is positive 🎁 That data goes into the user's receive buffers. As those fill up, the user should be told Receive buffer full. Then an acknowledgment gets sent:
<SN=received AN><AN=received SN+1 modulo 2><CTL=ACK>If data is queued to send, it's most efficient to piggyback this acknowledgment on that data packet 🎒
Discard the packet and return to the ESTABLISHED state without any further processing 🌸
5.4. Timers ⏰
There are three timers associated with this protocol 🫧 Here's a quick look at what each one does and what happens when it expires. How these timeouts actually behave and get set up is up to the protocol implementation 🛠️
5.4.1. User Timeout
Real talk, implementations need a user-controllable timeout for successfully opening a connection, successfully acknowledging data, and successfully closing a connection 🙏 Picture a connection that's so noisy nothing gets through, or one that's physically cut. Without an overriding timeout, those situations would retransmit forever 😭
When this timeout expires, the user is told Error: Connection aborted due to user timeout., all queues are flushed, the TCB is deleted, and the CLOSED state is entered 🚪
5.4.2. Retransmission Timeout
This timer makes sure any packet with a significant SN gets acknowledged 📬 When one is sent, it goes into a retransmission queue and the retransmission timer starts. If no acknowledgment shows up before the timer runs out, the packet is retransmitted and the timer restarts. If the acknowledgment arrives in time, the timer stops and the packet leaves the retransmission queue. Then the next packet with a significant SN can go out 🚀
This timeout is meant to work together with a counter that tracks how many times a packet has been retransmitted 🔢 Normally, there's an upper limit on retransmissions. If that limit gets exceeded, the connection is aborted, kind of like the user timeout. The user is told Error: Connection aborted due to retransmission failure, all queues are flushed, the TCB is deleted, and the CLOSED state is entered 💀
5.4.3. TIME-WAIT Timeout
This timeout catches any FIN packets that might be retransmitted from the other end when an acknowledgment packet got dropped 🕵️♀️ The timeout period SHOULD be at least as long as 2*SRTT. Once it expires, the other end is assumed to be closed, the TCB is deleted, and this end enters the CLOSED state too 🎀
6. Data Error Handling 🚨
This chapter goes deep on the data errors an established connection can run into 🔍 These are different from the protocol errors we covered above. In the order we'll discuss them, they are:
- Framing Errors
- Missing SYNCH pattern
- Unacknowledged packets
- Bad packets
- Duplicate packets
- Outside flow control
- Packets that are too large
- Packets that are too small
6.1. Framing Errors
The RS-232 specification only gives framing for an individual octet 🧵 Link level protocols for computer networking usually frame each packet. The SYNCH pattern marks the beginning of a packet 🏁 No similar pattern was picked to mark the end and fully frame the packet 🤷♀️
Any bit pattern can show up in the data portion of a packet 😳 For any particular pattern to reliably mark the end of a packet, that terminating pattern can't be allowed to appear in the data. This is usually handled by the sender changing any occurrence of the terminating pattern in the data so it's no longer recognizable as that pattern, and it can be restored on receipt. Both the sender and the receiver are REQUIRED by this technique to examine all the data 👀 Without a protocol chip to handle this, it's a source of some overhead 🐢
6.1.1. Synthetic Framing
Without framing, the end of the packet MUST be determined synthetically 🧩 The start of a packet is indicated by the SYNCH pattern. The expected end can only be figured out by reading the LENGTH octet in the header. It's important to know whether LENGTH can be trusted 🥸 This is handled by using a one-octet header checksum that covers the first two octets after the SYNCH pattern. If the header passes the checksum and none of the SYN, FIN, RST, or SO flag bits are set, then LENGTH is trusted and the number of octets expected beyond the header is LENGTH+2. (For packets where any of those flag bits are set, the packet length is fixed and only includes a header portion 📏)
If the header fails the checksum, we're in some trouble 😬 The length is wrong, so it could be too small or too large. To recover, do the following. Starting right after the SYNCH pattern, rescan for the next SYNCH pattern. Throw away all octets until a SYNCH is seen, then try to reinterpret it as a packet. The sender's retransmission timeout guarantees a new copy of the packet will be sent, so after the initial SYNCH pattern is discarded, the SYNCH pattern at the beginning of the retransmitted packet will eventually be seen 🔁✨
6.1.2. Costs of Synthetic Framing
This framing strategy causes no overhead unless data errors happen in the packet 🙌 That's presumed to be pretty unlikely 🎲 It also removes the overhead of both sender and receiver having to scan through the data to handle any termination pattern that might show up in it 💜
The worst case is kinda brutal 💀: a packet header fails its checksum, a fresh SYNCH pattern shows up in the next few octets, that header fails its checksum too, and so on, until the SYNCH pattern of the retransmitted packet is finally spotted. Consistently bad behavior like that means an extremely noisy communications link 📡
6.2. Missing SYNCH Pattern 🔍
Any valid packet must begin with the SYNCH pattern. Any receiver must discard all input octets until the SYNCH pattern is seen. The data which immediately follows a SYNCH pattern is interpreted as a packet. The header checksum test is applied, then LENGTH+2 octets are read, the data checksum test is applied, etc. 🧚
6.3. Unacknowledged Packets ⏰
If an ACK for a packet is not obtained within the retransmission timeout interval, that packet is retransmitted. Because significant variability in response can be expected from either end of a connection, it is best to dynamically calculate the retransmission timeout interval. An example of such a calculation is provided below. The protocol will operate successfully, although not with as high an effective transmission rate, if a realistic upper bound time is used instead. 💖
A realistic upper bound time depends upon the packet size and line speed. If the baud rate of the connection is 300 or above, let B be the baud rate (for clarity, assume it is the same in both directions), let L be the MDL of the receiver, and let P be the packet processing time of the receiver. Then an Upper Bound for the Reception Time (UBRT) is:
UBRT = L/(B/10) seconds + P secondsand a realistic upper bound time is 2*UBRT seconds. ✨
6.3.1. Calculation of Retransmission Timeout Interval 🧮
For the purpose of detecting retransmission time out, the protocol must have access to a clock which provides at least single second resolution. One technique for calculating the round trip time is:
Measure the elapsed time between sending a packet with a particular SN and receiving an ACK with an AN which covers that SN. The measured elapsed time is the Round Trip Time (RTT). Next, a Smoothed Round Trip Time (SRTT) is calculated as:
SRTT = (ALPHA * SRTT) + ((1- ALPHA) * RTT)and based upon this, you compute the Retransmission Time Out (RTO) as:
RTO = min[UBOUND, max[LBOUND, (BETA * SRTT)]]where UBOUND is an upper bound on the timeout (e.g., 1 minute), LBOUND is a lower bound on the timeout (e.g., 1 second), ALPHA is a smoothing factor (e.g., .8 to .9), and BETA is a delay variance factor (e.g., 1.3 to 2.0). 📊
6.4. Bad Packets 🙅♀️
A bad packet is received when it fails either the header or data checksum tests. When this happens, the sender will retransmit the packet after the retransmission timeout interval. 🔁
6.5. Duplicate Packets 👯♀️
A duplicate packet is a packet which passes the checksum tests but for which the SN received is significant but not the expected value. This is normally caused when the sender did not get the ACK last sent by the receiver. This situation is diagrammed below. 🎀
Side A Side B
ESTABLISHED ESTABLISHED
1. --> <SN=1><AN=0><CTL=ACK><DATA> ...
-->
2. XXX <SN=0><AN=0><CTL=ACK><OTHER-DATA> <--
3. (after SRTT)
--> <SN=1><AN=0><CTL=ACK><DATA> ...
4. -->
... <SN=0><AN=0><CTL=ACK><OTHER-DATA> <--
5. <--In line 2, B's packet was lost in transit. It may have failed its checksum tests when it reached A, or its initial SYNCH pattern was smashed, etc.. In line 3, side A comes to the decision that its packet from line 1 was not received after SRTT time passes, and retransmits that packet. 😬
In line 4, side B receives the packet. It detects a duplicate because it already sent a packet acknowledging A's SN=1 (although that packet was lost). B now discards the duplicate and immediately retransmits its last packet to A. Side A finally receives the retransmitted packet in line 5. 🥹
6.6. Outside Flow Control 🚦
There are many large computer systems which make use of flow control to regulate their input side of an RS-232 link. Flow control based upon two special characters, such as <Ctrl-S> (ASCII DC3) and <Ctrl-Q> (ASCII DC1), is almost universally in use today. So it becomes important for the protocol to be able to either:
- Recognize and obey the flow control of the host computer(s), or
- Ignore the flow control but still guarantee reliable data reception.
It is the latter approach which this protocol takes. This decision was made because the number of differing flow control characters in use would make it difficult to obey them all. 🙃
There is a particular type of flow control with which this protocol will not operate. The ENQUIRE, ACKNOWLEDGE method of flow control requires that the receiver of an inquiry respond with an acknowledge before any more data will be sent to it. This type of flow control also usually prohibits unrestricted 8-bit data transmission, because the inquiry character is forbidden as a data byte. 🚫
For the other class of flow control methods, a proof is required that data may still be reliably transmitted and received if flow control is ignored. For the purposes of this discussion, assume <Ctrl-S> is sent when the receiving end of the connection wishes the sender to stop transmitting. A <Ctrl-Q> is sent when the receiver wishes the sender to resume. The choice of these particular two characters is arbitrary. If the sender does not immediately cease transmission upon receipt of the <Ctrl-S>, characters may be discarded. Since this protocol chooses to ignore the flow control characters, any part of a packet may be discarded. 🫠
More precisely stated, consider X to be the receiver and Y to be the sender. The packet sent is represented by the string abc, where a, b, and c are data segments of unspecified size. X may receive one of:
1. abc
2. ab
3. ac
4. bcFor case [1], the correct data is received and no special action need be taken. ✅
For cases [2], [3], and [4], we have a situation identical to data dropped during transmission. This is handled by the same checksum, time-out and retransmission strategy already described. 🔄
Assume Y is not now in the act of receiving a packet. Then Y sees the two characters <Ctrl-S> and <Ctrl-Q> appear as input in that order. Y is waiting for a message to appear and so expects to see a SYNCH pattern. If the two characters "<Ctrl-S><Ctrl-Q>" are not part of a SYNCH pattern, then they will be immediately discarded. If Y is receiving a packet, then the <Ctrl-S> and <Ctrl-Q> are seen to be added noise characters and would be detected by the checksum tests. The packet being received would require retransmission. 📦
The question of which character to pick for the SYNCH pattern is slightly muddied by the above observation. To the author's knowledge, <SOH> is rarely, if ever, picked for flow control. This is part of the motivation in using it as the SYNCH pattern. 🌈
How does one guarantee that any data will actually arrive successfully? The initial choice of maximum data counts during connection establishment is very important. Some knowledge of one's own operating system must be assumed. If it is known, for example, that streams of data in excess of a certain length will often trigger flow control at the connection baud rate, then the maximum data count should be chosen sufficiently lower that flow control rarely will be employed. An intelligent choice of the maximum data count will guarantee that some packets will arrive without encountering flow control. 🧠💅
6.7. Packets that are too Large 🚨
Assume a packet arrives which passes its header checksum test but whose LENGTH is larger than the MDL of the receiver. In such a case, the sender has violated the protocol, or a packet has a data error in the LENGTH octet and has passed the header checksum test. The latter is unlikely, so we assume the former. The receiver will abort his connection. The sender must inform the user Error: Connection aborted due to MDL error, and go to the CLOSED state. 💀
When the MDL is exceeded, the receiver will transmit a legal reset:
<SN=received AN><CTL=RST>6.8. Packets that are too Small 🪶
Assume that a packet has passed its header checksum test, but some of the data octets have been dropped by the link. In such a case, the receiver's routine which reads data and builds packets is expecting octets which do not arrive. After SRTT, the sender will retransmit this packet to the receiver. The receiver will now have enough data to complete the packet. Almost certainly, however, it will fail the data checksum test. As with any bad packet, the receiver will rescan from the octet immediately following the SYNCH pattern for the next SYNCH pattern. In this manner, the receiver will eventually see the SYNCH pattern of the retransmitted packet. 🦋
I. Inability to Transmit/Receive 8-bit Data 💖
okay so, some older operating systems and devices literally can't do 8-bit communication over an RS-232 link 😭. most of them can only do restricted 7-bit communication. if that's unavoidable, both ends of the connection must have a protocol layer underneath this protocol 🫶. that lower layer unpacks the packets it sends over the RS-232 link and repacks the packets it receives over it. RATP will automatically figure out whether full 8-bit or restricted 7-bit communication is being used (more on that below) ✨.
the strategy for restricted 7-bit communication is called 4/8 packing 🎀. each octet gets chopped into two 4-bit nibbles. the high order four bits go out first, followed by the low order bits. on the receiving side, each octet gets repacked by the inverse function: the high order nibble arrives first, then the low order nibble, and those two get glued back together into one octet 🧩.
I.1. Encoding for Transmission 🌸
some systems can't do 8-bit over RS-232 at all, and on top of that some operating systems put special restrictions on the non-printable ASCII characters 💀. so the encoding for 4/8 packing should restrict itself to transmitting data only in the printable 7-bit ASCII range 💅.
I.2. Framing an Octet 🦋
the seventh and highest order bit of a transmitted 7-bit ASCII byte is a flag. it tells you whether the high or low order nibble of an octet is inside this character 👀. if the flag is set, it means a new octet is coming in, and this printable ASCII character holds the high order nibble in its four low order bits. it also means the next ASCII character received should not have its highest order bit set.
this high order flag bit gets set by adding the ASCII character "@" (octal 100) to a data byte. so the first nibble of an octet always goes out with "@" added to its value. the high order nibble becomes the characters "@" through letter "O" 🔥.
the lower order nibble goes out with zero "0" added to its value, so it becomes the characters "0" through "?". when receiving 4/8 packed data, any characters not within the range "0" through letter "O" get discarded 🗑️.
here's an octet whose octal value is 45, sent as two 7-bit printable ASCII characters:
+-------------+
High order |1|0|0|0|1|0|0| First transmitted ("@" + data) = D
+-------------+
Low order |0|1|1|0|1|0|1| Second transmitted ("0" + data) = 5
+-------------+okay now this part is super important 😤. since data bytes can get dropped or added at any time, you always need to know which portion of an octet is expected, and you should only deliver complete octets to the higher protocol level. if a single 7-bit character got dropped without anyone noticing, the data stream handed up to the higher level could be shifted by an odd multiple of four bits. in the worst case that could stick around forever, and the higher level would never receive an octet correctly. then no packets would ever be received correctly, and the connection would be totally unusable 💔.
to avoid this, octets get assembled using a state machine that's driven by the presence of the high order flag bit. that bit in a 7-bit printable character marks the beginning of a new octet ✨. the two-state machine that assembles octets is described below. a byte received with the high order flag bit set is called "HIGH", and the byte without it is called "LOW".
State 0
[Start state] Read a byte from the legal restricted set. This is determined by seeing if the byte is in the legal range "@" to the letter "O". If it was not, discard the byte and return to this state.
A HIGH byte was read. Place the four low order bits of the byte into the four high order bits of the assembled octet and go to state 1. Otherwise, discard the byte and return to this state.
State 1
Read a byte from the legal restricted set. This is determined by seeing if the byte is in the legal range zero "0" to the letter "O". If it was not, discard the byte and return to this state.
If a LOW byte was read, subtract zero "0" from the byte, placing the four low order bits of the result into the four low order bits of the assembled octet. A full octet has now been assembled. Pass the octet to the higher level and go to state 0.
Otherwise, a HIGH byte was read. Place the four low order bits of the byte into the four high order bits of the assembled octet and return to this state.
using this state machine to receive 4/8 packed data means the data stream delivered to the higher level won't stay shifted by an odd multiple of four bits forever 🙌. the restriction on which bytes can be read throws out obviously bad data, and in some cases it can handle uncontrolled padding or blocking insertion.
I.3. Automatic Detection of 8-bit or 4/8 Packed Data 🧠
it's an unavoidable problem that some machines can't handle unrestricted 8-bit data. since that's a given, it's desirable to automatically detect whether unrestricted 8-bit or restricted 4/8 packing is being used to send data on a connection. for this discussion, machines that can transmit and receive both unrestricted 8-bit and 4/8 packed data are called smart. machines are called dumb if they can only transmit and receive 4/8 packed data 🤓.
when initiating a connection there are four possible machine configurations:
- A (smart) opens a connection to B (smart).
- A (dumb) opens a connection to B (smart).
- A (dumb) opens a connection to B (dumb).
- A (smart) opens a connection to B (dumb).
each case gets examined, and extensions to the behavior for the LISTEN and SYN-SENT states are provided, which allow both types of machines to initiate or receive a connection 🦋.
Cases 1 and 2: LISTEN Behavior for a Smart Machine
in these cases machine A initiates a connection to B, who is assumed to be in the LISTEN state. B has to be able to passively detect whether 8-bit or 4/8 packing is being used and respond accordingly. the method B uses relies on detecting a valid first packet. in the LISTEN state, B tries to treat the incoming data as if it were both unrestricted 8-bit and 4/8 packed at the same time 👀.
the incoming data is in effect fed to two different receiving algorithms. the detection of a valid header will happen in one of these algorithms before the other. if the first valid header was read assuming unrestricted 8-bit data, then any resulting connection is assumed to use unrestricted 8-bit data for the life of the connection. if the first valid header assumed 4/8 packing, then the resulting connection is assumed to use 4/8 packing for the life of the connection. if an illegal condition is detected in the LISTEN state, the protocol will reply with a RST packet in kind 🚫.
Case 3: LISTEN Behavior for a Dumb Machine
in this case machine B is the recipient of a connection request and can only handle 4/8 packed data. the LISTEN behavior for machine B assumes that all connections are 4/8 packed, and it never deals with unrestricted 8-bit data. as a result, it will refuse to open a connection request from a smart machine (see case 4 below) 🙅♀️.
Case 4: SYN-SENT Behavior for a Smart Machine
in this case machine A tries to open a connection to machine B. however, A has no knowledge of B's capabilities 🤷♀️. A will send its connection request assuming B is smart and using unrestricted 8-bit transmission. it will wait for a reply, assuming the response will also be unrestricted 8-bit. if B is in fact dumb, it won't return a SYN-ACK, because of the restriction imposed by case 3 above. if no connection is made with B using 8-bit data, the entire connection initiation is restarted, assuming B is dumb: 4/8 packing is used, and the response is assumed to be 4/8 packed as well 🔁.
the cost of this approach is a longer time to determine whether it's possible to open a connection to B. it's twice as long. but the advantages of being able to automatically adjust to either unrestricted 8-bit or 4/8 packed data outweigh this disadvantage 🏆. RATP will not exhibit the schizophrenic behavior of many other asynchronous protocols when dealing with both classes of machines 🌈✨
II. A Brief Survey of Some Asynchronous Link Protocols 🌸
II.1. DDCMP 💖
okay so DDCMP, Copyright (c) 1978 Digital Equipment Corporation [DDCMP 78], is a reliable point-to-point AND multi-point transmission protocol, and it's used by a lot of that manufacturer's computers. it really does give you reliable asynchronous two-way data transmission, so it's not a mess 💅
some of its choices come from being built for multi-point data links 🔗 which means the headers end up way longer than you'd need for plain two-way point-to-point stuff. bestie, that's a lot of extra baggage 🎒
DDCMP lets up to 255 outstanding unacknowledged messages hang out at once ✨ it also specifically says that one end of a connection can choose to limit its send queue to just one outstanding unacknowledged message. it's also allowed to send a stream of outstanding unacknowledged packets. here's the tea: unless every RS-232 implementation of DDCMP was capped at one outstanding packet, the clash with existing flow control rules could tank the thruput into the ground 📉 (quick side note: DDCMP is assumed to be in control of the link driver, so dealing with all the different flow control mechanisms isn't on the table.)
DDCMP uses a CRC polynomial for data protection, and it's annoyingly hard to calculate on lots of machines without special hardware [TCP Checksum 78]. the good news is that plenty of Digital Equipment computers already have that hardware 🫶
DDCMP does not give the receiver a way to restrict incoming packet size 🙈 yes, higher level protocols built on top of DDCMP could negotiate packet size on their own. but then that job gets pushed away from the link level, which is where it properly belongs. not vibing.
honestly? a full implementation of DDCMP is too complex to even consider 😭 and if you tried to implement only part of it, you'd run into compatibility problems with the implementations that already exist on other computers.
II.2. MODEM Protocol 🦋
this one is super popular amongst microcomputers, so it's kind of iconic 👑 the description here comes from:
MODEM/XMODEM Protocol Explained by Kelly Smith, CP/M-Net "SYSOP" January 8,1980
so the basic idea is that data gets sent in 128-byte sequentially numbered blocks, and every block gets one single checksum byte tacked on at the end 🎀 the receiving computer does its own checksum as the data comes in. once a block is finished, it compares its result with the sending computer's checksum. if they match, the receiver sends back an ACK (ASCII protocol character for ACKNOWLEDGE, 06 Hex, Control-F). the ACK basically means "all's well on this end, send some more..." 💌
the sender starts with an "initial NAK" (ASCII protocol character for NEGATIVE ACKNOWLEDGE, 15 Hex, Control-U). the NAK means "that wasn't quite right, please send again." because the first hookup between the two computers is asynchronous, the receiver will time out while waiting for data and send that NAK as the cue for the sender to start transmitting. the sender knows the receiver is going to time out, and it uses that to "get in sync"... literally clever 🧚
when the sender gets that initial NAK, it replies with a SOH (ASCII protocol character for START OF HEADING, 01 Hex, Control-A). then it sends the first block number, then the 1's complement of the block number, then 128 bytes of 8 bit data, and finally a checksum. the checksum is calculated by summing the SOH, the block number, the block number 1's complement, and the 128 bytes of data 🧮
here's how the exchange looks:
---/NAK/------------------------/ACK/------------------
15H 06H
---/SOH/BLK#/BLK#/DATA/CSUM/---/SOH/BLK#/BLK#/DATA/etc.
01H 01H FEH 8bit 8bit 01H 02H FDH 8bit ....this keeps going with the next 128 bytes. if the receiver ACKed the block, the sender moves on to the next sequential block number and its 1's complement, and so on 💫
okay but here's the catch 👀 as you can see from this partial description, the MODEM protocol is unidirectional. data can only go from the sender to the receiver, as one stream. if you wanted data flowing the other way at the same time, you'd need a second connection over another RS-232 line. not ideal, bestie.
on top of that, this protocol is locked to a fixed 128 octet packet size. a lot of front-end concentrators just can't handle packets that big 😩 it's been observed many times that the concentrator of a busy DECsystem-20 can invoke flow control on input at 1200 baud for packets as small as 64 characters. yikes.
II.3. KERMIT System 🧚
the KERMIT system, Copyright (c) 1981 Columbia University, is a file transfer environment that was developed fairly recently ✨ it has implementations running on DECsystem-20, IBM 370 VM/CMS, 8080 CP/M based systems, the IBM PC, and more.
KERMIT smooshes reliable transfer and file transfer together into one package 🎁 extending it to other applications and higher level protocols would be possible, but the line between the reliable transfer part and the application layer is super blurry. it violates the layering design strategy the Internet uses, and that's a big no from me 🙅♀️
for certain computers there's a limitation to the restricted printable ASCII set, but other computers don't have that limit. this leads to confusion 🌀 KERMIT allows both restricted ASCII and 8-bit transmission, so at least it's flexible.
the KERMIT protocol does have a way to set the MDL when a connection starts 🎀 the catch is that the max packet size is smaller: 96 octets instead of 261 octets.
KERMIT originally used a checksumming algorithm limited to six bits. this is considered too weak at error detection for data packets 🥲 KERMIT now allows two other checksumming algorithms on top of the original one. and there must be a negotiation between sender and receiver about which algorithm to use.
now the simultaneous open situation 🙃 the KERMIT protocol doesn't seem to make any provision for both sides of a connection attempting an active open at the same time. one side has to be the initial "sending Kermit" and the other has to be the "receiving Kermit". the code published as a KERMIT implementation guide can't recover from simultaneous active opens, and it immediately ABORTs. this shows a bias towards unidirectional data flow, which is a whole vibe 📤
the KERMIT packet type (similar to RATP control flags) specifies whether an ACK/NAK is in the packet, or data, and so on. these are mutually exclusive, so piggybacking an ACK on a data packet isn't possible, and that can be a source of overhead 📦 also, KERMIT restricts the sender to a single outstanding unacknowledged packet, just like RATP does. and it gives an entire byte to the sequence number, which is unnecessary 😤
now for error recovery 🚨 the size of a packet is stored in the second byte of the packet, and it isn't protected by a header checksum. if the length field gets messed up by noise on the link, it could end up longer than the correct packet size. the code published as the KERMIT implementation guide relies on detecting the <SOH> character anywhere in a packet to mark the beginning of a packet header, and it re-SYNCHs using this technique. that only works if binary data in a packet is quoted. if full eight bit data is transmitted, it doesn't look like the KERMIT protocol rescans for a new MARK (SYNCH) character within the bad packet data it just consumed. in those circumstances it will throw away the retransmitted packet, or portions of it. re-SYNCHing under those conditions is problematic 💀
References 📚
[Cohen 81]
Cohen, D. On Holy Wars and a Plea for Peace. IEEE Computer, October, 1981.
[DDCMP 78]
DDCMP AA-D599A-TC edition, Digital Equipment Corporation, 1978. Version 4.0.
[IP 81]
Postel, J. DOD Standard Internet Protocol [RFC-791] Defense Advanced Research Projects Agency, 1981.
[TCP 81]
Postel, J. Transmission Control Protocol [RFC-793] Defense Advanced Research Projects Agency, 1981.
[TCP Checksum 78]
Plummer, W. W. TCP Checksum Function Design. Technical Report, Bolt Beranek and Newman, Inc., 1978.
Editors Notes 💌
This memo was prepared in essentially this form in June 1983, and set aside. Distribution at this time is prompted by the the "Thinwire" proposal described in RFC-914.
--jon postel 🫶
📦 where this page comes from
- ietf: rfc916 1984-10
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms