RFC 64

Getting Rid of Marking 🎀

Okay bestie, so this RFC is from M. Elie at UCLA and it's in the Network Working Group 💖. It's Request for Comments #64, and the title is Getting Rid of Marking ✨. The original doesn't list a category, a date, or anything it obsoletes or updates, so I'm not making any of that up 🙈.

The big idea: marking is kinda late to the party, but Elie thinks there are better solutions, and suggests a simple change to the IMP-HOST interface that avoids it 🦋.

1. The harm. 💅

Marking was added to help the sending Host, because it lets a message's text start on a word boundary 🌸. The problem is it's not it's not giving for a receiving Host with a different word length 💀. It also adds useless bits to the message 😭. Elie explains this with their Sigma 7, which is a 32 bit machine 👑.

1.1 Inefficiency in Computation 🧚

Say we get a message from an 18 bit machine (figure 1.1). It's coded in 8 bit ASCII characters, which will eventually be the standard on the network 🌈. To translate it into our EBCDIC internal code, for example, we'd have to shift the whole message first. We need to find the first 1 after the leader, then work out that the message has to shift 4 bits to the left 🫶. That takes about 12 �sec per double word, which adds up to 1,5 msec per full regular message 😵. Not huge, but it's about one-third of the time it takes to translate the message into internal code, which is a lot ngl 🔥.

0                        17           0                           31
--------------------------            ------------------------------
|        leader          |            |           leader           |
--------------------------            ------------------------------
|               | 0 0 0 1|            | 0 0 0 1 |                  |
--------------------------            -----------                  |
|                        |            |                            |
|                        |            |                            |
|                        |            |                            |
| message                |            | message                    |
|                        |            |                            |
|                        |            |                            |
|                        |            |                            |
|                        |            |                            |
|                        |            |                            |
|                        |            |                            |

                            figure 1.1

1.2 Inefficiency in transmission 🍓

The bigger problem is all the extra bits stuffed into the message 😤. It gets worse when messages are just one character long 💅. Figure 1.2 shows a 1 character text sent by the Sigma 7. That means 112 bits get transmitted to carry only 8 bits of actual info, so the efficiency factor is 0.07 💀. Dropping the marking would bump that up to 0.10 ✨. For a 32 bit text (like some control commands), efficiency would go from 0.28 to 0.4 🙌. Even for one packet messages it still gets 3% better 🦋.

                            -----------------------------------
   Sigma 7                  |           leader                |
                            -----------------------------------
   Message                  |00000000000000000000000000000001 |
                            -----------------------------------
                            | text | 000000000000000000000000 |
                            -----------------------------------
   16 bits of padding       | 1000000000000000 |
   added by sending IMP     --------------------

                                figure 1.2

2. A remedy. 🌸

So this is Elie's suggested fix for the Host-IMP user interface 🎀. It was roughly sketched on diagrams pulled from the BBN 1822 report 📝.

2.1 Host to Imp 💖

The fix is to add a counter that goes up to 32 ✨. It starts when a message begins, and it ticks up for every bit passed to the IMP 🧮. When it hits 32, it sends a "word complete" signal, which asks for a new word in the shift register and resets the word length counter 🔄. So the unused bits in the last word of the leader never get sent, and the message starts with the next word instead 🫶 (see figure 2.1).

   0                                       23
   ------------------------------------------
   |             leader                     |
   |                   ----------------------
   |                   | XXXXXXXXXXXXXXXX   | <- contents of
   |-----------------------------------------    sending Host memory
   |                                        |    (24 bits)
   |            Message                     |
   |                                        |

   Corresponding message in the sending IMP memory


   0                             15
   --------------------------------
   |                              |
   |                              |
   |         leader               |
   |                              |
   --------------------------------
   |                              |
   |   message                    |
   |                              |


                                figure 2.1

2.2 Imp to Host 🧚‍♀️

Same idea on the way back: add a counter up to 32 🌈. Once 32 bits have come into the shift register from the Imp at the start of a new message, the counter lets the register keep shifting until it's full (the word length counter notices that) without taking in any new bits from the Imp 💅.

So the next bit of the message, which is the first bit of text, gets put in as the first bit of the next word 🫶 (see figure 2.2).

Message in receiving IMP memory  Contents of receiving Host memory (35
bits)

0                        15      0                                   35
------------------------------   --------------------------------------
|                            |   |                                    |
|       leader               |   |     leader                  | 0000 |
------------------------------   --------------------------------------
|                            |   |                                    |
| message                    |   | message                            |
|                            |   |                                    |
|                            |   |                                    |

                               figure 2.2

Okay so the total cost of all those useless marking bits going over the network, plus the compute to reshape received texts, means this change is probably worthwhile to think about 🤔. BUT it's not Elie's call to make, so they're just putting the better option out there instead of marking 💜.

Pages 5 and 6 contain a wire Diagram of a "IMP to Host" "Host's special Interface"

[ This RFC was put into machine readable form for entry ] [ into the online RFC archives by Gottfried Janik 2/98 ] 🫶