RFC 203

Achieving Reliable Communication 💖

RFC 203 🎀 is by R. Kalin of MIT Lincoln Lab, from the Network Working Group, with NIC number 7168. It's dated 10 August 1971. The abstract calls it a "non-standard protocol," and no category is listed. It doesn't obsolete or update anything. 🦋

'This material has not been reviewed for public release and is intended only for use with the ARPA network. It should not be quoted or cited in any publication not related to the ARPA network.'

ABSTRACT 🌸

okay so this is a non-standard protocol, suitable for either second or third level use 💅 The whole point is to get error resistant, highly reliable communication channels ✨ It looks at errors from message garbling, message loss, and message pickup, and it also talks about ways to boost throughput 🚀

AIMS AND LIMITATIONS 🧚

bestie, the authors are NOT trying to design a perfect channel 🙈 their take is that in the real world there can be no perfect channels, and no amount of protocol can insure the error free transfer of information 😭 Their goal is to explain the different kinds of errors that can happen and give each one a way to detect and recover, which at a cost can be made arbitrarily good 💜 That means the mean time between undetected errors can be made as large as necessary ✨

ERROR TYPES AND DETECTION 🔥

So over a message switching facility, like the ARPA network, all transmission errors fall into two classes 🍓 One class is a message you expected that never shows up. The other is an unexpected message that gets picked up anyway. A single bit inversion can cause errors of both types 💀 So error detection splits into two parts: figuring out whether the message that just arrived is appropriate right now, and figuring out whether a message has been lost.

Detecting garbled input messages is already well covered by classical coding ( elsewhere, mistakenly termed 'communication' ) theory 🤓 Internal message consistency can be checked with parity bits, checksum fields, or any of the various coding techniques that add some redundancy. With relative simplicity, the likelyhood of an undetected error of this type can be made small enough to be inconsequential ✨

Since it's adequately covered elsewhere, no further discussion shall be given here 🙅‍♀️

Detecting a message's external consistency, meaning whether it can possibly follow the message that arrived right before it, can also be straight forward 🌈 Sequence numbers, if used, can be easily checked. A modulo N sequence field will allow detection of up to N-1 successive message losses 👑 If several concurrent links are in use, sequencing can be maintained for each link. Multi-link single sequence schemes are more complicated, and although they're used between IMPs for transmission of message packets, they shall be ignored here 🙈

A receiving host can't directly detect a lost message 😭 It has to be inferred from other observations. Any automatic correction scheme must be prepared to handle the possibility of faulty inference 💅 A loss would normally be inferred when a message arrives that should follow the one expected. It might also be inferred because the expected message is long overdue ⭐

ERROR CORRECTION 💖

If a BCH or other error correcting code is used for transmission, errors found in a message's internal consistency can sometimes be corrected by the receiving host ✨ If that isn't possible, the content of the message is of little use, because it can not be relied upon. The only reasonable solution is to discard the message and rely on the recovery procedures for lost messages 🫶

External consistency errors can be handled the same way. The message can be thrown away, and the techniques for recovering lost messages are relied upon 🎀 Over a critical channel, a slightly fancier technique can sometimes save some retransmissions 👑 If message N is expected but message N+1 arrives, there's no need to throw away message N+1 and then recover two messages. It could be saved, and only message N retransmitted. Iconic, right? 😭

On noisy channels, saving out of sequence messages can be used to some advantage, especially if recovering from a lost message takes several messages of overhead 🌸 On the ARPA network, though, the measured error rate is so low that its advantages are outweighed by the increase in resident coding 💀

RECOVERING LOST MESSAGES 🦋

The simplest technique the author knows of for recovering lost messages works by these rules:

1. All undiscarded messages have reply messages.
2. Messages with coding errors that can not be corrected are discarded.
3. The receiver can determine if a message is in sequence.
4. Messages received that are out of sequence are discarded.
5. If no reply message is received in N time units since the last transmission, the last message sent is retransmitted ( space need not be isochronic ).
6. A new message is not sent until the reply for the last one has been received.

The protocol above, if run, is highly effective for continuous communication 💅 Because of rule 6), only one message can be in transit at a time, so the necessary sequencing information fits in a single bit 🧚 But unmodified, it isn't suitable for finite communication, since rules 1) and 5) guarantee that there will be no 'last message' 💀 It also doesn't make very effective use of a pipelined channel, since only one message is being sent at a time 🙈

Channel throughput can be increased in several ways. The first is to split the data stream into several ( eg. four or eight ) streams, transmit each one with the protocol above, and then reassemble the streams at the far end ✨ Another way is to modify rules 5) and 6):

5a) If no reply has been received to message M in N time units since the last transmission, then messages M, M+1,... are retransmitted.

6a) There must be no more than L outstanding unreplied messages.

With L equal to one, this protocol degenerates into the first protocol 🌈 Increasing L boosts throughput until the gain is outweighed by the time spent in error recovery. The larger L is, the costlier error recovery gets 👑 The value of N should be adjusted so that the reply time for a message is usually less than N plus the time to send L-1 messages. Increasing N too much lowers the response time to errors, and decreasing N increases the probability of initiating unnecessary retransmissions 🔥

A CRITICAL RACE ⭐

The protocols above leave the details of starting and stopping a finite transmission unresolved 😭 When opening a communication channel, what is the sequence number of the first message sent? What will be the first sequence number of the first message sent? What will be the first sequence number of the first reply received? At the end of transmission, how do you signal the 'last message'? To answer these, two more rules are introduced:

7. If the same message has been received K times ( eg. 50 ), then it should be accepted as being 'in sequence'. The expected sequencing should be adjusted accordingly. K identical reply messages are then sent.
8. If no reply has been received in J seconds, then the retransmission of the last unreplied message should cease.

With these extra rules, a finite transmission starts by repeatedly transmitting the first message until K identical reply messages are received 💖 Sequencing gets adjusted, and then subsequent messages can be sent. A conversation is broken by quitting transmission after the reply to the last message you care about has been received. Eventually the other end will stop resending the reply 🫶 To avoid ambiguity, the variable J should be less than N times K. Problems arise if the network crashes for J seconds, because there's a race condition over whether the lack of a reply is a channel failure or the end of a conversation 💀✨

---

        [ This RFC was put into machine readable form for entry ]
            [ into the online RFC archives by Ryan Kato 6/01]