Getting rid of marking
Removing unnecessary padding bits from network messages.
Elie, M., "Getting rid of marking", RFC 64, DOI 10.17487/RFC0064, July 1970, <https://www.rfc-editor.org/info/rfc64>.
@misc{rfc64,
series = {Request for Comments},
number = 64,
howpublished = {RFC 64},
publisher = {RFC Editor},
doi = {10.17487/RFC0064},
url = {https://www.rfc-editor.org/info/rfc64},
author = {M. Elie},
title = {{Getting rid of marking}},
pagetotal = 4,
year = 1970,
month = jul,
} RFC text
Network Working Group M. Elie
Request for Comments #64 UCLA
Getting Rid of Marking
Though we realize that this improvement is perhaps somewhat late
to be implemented, we believe that there exist better solutions than
marking and suggest a simple modification to the IMP-HOST interface
which would avoid it.
1. The harm.
Marking was introduced to suit the sending Host because it permits
the text of a message to start on a word boundary, however, it does not
suit the receiving Host with a different word length. Moreover,it
introduces in the message useless bits. Let us illustrate this by the
example of our Sigma 7, a 32 bit machine.
1.1 Inefficiency in Computation
Suppose we receive a message from an 18 bit machine (figure 1.1)
coded in 8 bit ASCII characters which will eventually become standard on
the network. In order to translate this message into our EBCDIC
internal code, for instance.
0 17 0 31
-------------------------- ------------------------------
| leader | | leader |
-------------------------- ------------------------------
| | 0 0 0 1| | 0 0 0 1 | |
-------------------------- ----------- |
| | | |
| | | |
| | | |
| message | | message |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
figure 1.1
we first have to shift the whole message. We must detect the firsl 1
following the leader, and from this determine that we must shift the
message 4 bits to the left. This takes approximately 12 �sec per double
word, which makes 1,5 msec per full regular message. This is not huge,
but still it is about one-third of the time it will take to translate
the message in internal code.
1.2 Inefficiency in transmission
More important is the inefficiency resulting from adding
unnecessary bits to the message, especially if it turns out that one
character messages are used. Figure 1.2 shows the example of a 1
character text sent by the sigma 7, which results in transmitting 112
bits to carry 8 bits of information, thus leading to an efficiency
factor of 0.07. Supression of marking would
-----------------------------------
Sigma 7 | leader |
-----------------------------------
Message |00000000000000000000000000000001 |
-----------------------------------
| text | 000000000000000000000000 |
-----------------------------------
16 bits of padding | 1000000000000000 |
added by sending IMP --------------------
figure 1.2
increase this efficiency to 0.10. For a 32 bit text (length of some
control commands), it would increase the efficiency form 0.28 to 0.4.
For one packet messages, the efficiency would still be increased by 3%.
2. A remedy.
This is a suggested modification of the Host-Imp users interface
which has been tentatively sketched on diagrams extracted form BBN 1822
report.
2.1 Host to Imp
The modification consists of adding a counter to 32, enabled
as the beginning of a message, and incremented at each bit passed to the
IMP; when it reaches 32 it forces a "word complete" signal asking for a
new word in the shift register and resetting the word length counter;
thus the unused bits in the last word of the leader are not transmitted
and the message starts with the next word (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
The modification consists of adding a counter to 32. When 32 bits
have entered the shift register form the Imp at the beginning of a new
message, the counter allows the register to be shifted up to the point
to be full (which is detected by the word length counter) without
entering any new bit from the Imp.
Thus, the next bit of the message which is the first bit of text will be
entered 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
Though the accumulated cost of useless marking bits sent over the
network plus computation to reshape received texts makes this
modification probably whorkwhile being considered, this decision is not
of our competence and we merely wanted to suggest a better solution then
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 ]
AI ELI5
On this page
§1The Problem of Marking
Marking is a field in messages that indicates where the actual data begins. It was introduced so the message text could start on a word boundary in the sender's machine. However, machines have different word lengths (e.g., 18 bits versus 32 bits), so the receiver cannot use the marking scheme designed for the sender's hardware. Marking wastes bits in transmission and requires computation to remove.
If the sender says 'the real message starts at bit 4', a receiver with a different-sized word does not understand that numbering system.
§2Inefficiency in Computation and Transmission
To process a received message with marking, the receiving host must detect the first 1 bit after the leader field, determine the shift amount, and shift the entire message accordingly. On a Sigma 7 (32-bit machine) receiving from an 18-bit machine, this takes about 12 microseconds per 36-bit word, or 1.5 milliseconds for a full message. This is roughly one-third of the time needed to translate the message into the host's internal format.
More serious is the transmission waste. A single ASCII character (8 bits) sent with marking, leader, and padding uses 112 bits on the network, for an efficiency of only 7%. A 32-bit control message achieves 28% efficiency. Removing marking would increase these to 10% and 40% respectively. Even for larger messages, the gain is significant—3% more efficiency for typical packet messages.
It is like sending a postcard with lots of empty space marked 'not part of the message'—the post office has to read and skip those marks, and they take up postage.
§3Proposed Hardware Modification
The RFC suggests adding a bit counter to the shift register in the host-IMP interface hardware, starting at the beginning of a message.
From host to IMP: The counter increments with each bit sent. When it reaches 32 bits (one complete word), it forces a 'word complete' signal to the IMP, requests a new word from the sender's memory, and resets. This eliminates unused padding bits in the last word before the leader ends.
From IMP to host: A counter again counts to 32 bits. Once 32 bits have been received, the shift register is allowed to fill to its natural word boundary without accepting any new bits from the IMP. The next bit from the IMP becomes the first bit of the next word, which is the start of the actual message text.
Instead of the sender marking where the message starts, the hardware automatically aligns the next message to start right after the last bit needed, with no wasted padding labeled as 'not part of it'.