2.2. Data Format

The data portion of a packet immediately follows the header if the SO flag is not set and LENGTH > 0. It consists of LENGTH data octets immediately followed by two data checksum octets. If present the data portion contains LENGTH+2 octets.

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 Packet

2.2.1. Data Checksum

The last two octets of the data portion of a packet are a data checksum. A 16-bit checksum is used by this protocol to detect incorrectly transmitted data. This has shown itself to be a reliable method for detecting most categories of bit drop out and bit insertion. While it does not guarantee the detection of all such errors the probability of such an error going undetected is on the order of 2**(-16).

The checksum octets follow the data to enable the sender of a packet to compute the checksum while transmitting a packet and the receiver to compute the checksum while receiving the packet. Thus neither must store the packet and then process the data for checksumming in a separate pass.

Order of Transmission

The order in which the 8-bit octets are assembled into 16-bit words, which is the low order octet and which is the high, must be rigidly specified for the purpose of computing 16-bit checksums. We specify the big endian ordering in the diagram above [Cohen 81].

Checksum Algorithm

The checksum algorithm chosen is similar to that used by IP/TCP protocols [IP 81] [TCP 81]. This algorithm has shown itself to be both reliable and relatively easy to compute. The interested reader may refer to [TCP Checksum 78] for a more thorough discussion of its properties.

The checksum algorithm is:

SENDER

The unsigned sum of the 16-bit words of the data portion of the packet is formed. Any overflow is added into the lowest order bit. This sum does not include the header portion of the packet. For the purpose of building a packet for transmission the two octet checksum field is zero. The sum formed is then bit complemented and inserted into the checksum field before transmission.

If the total number of data octets is odd then the last octet is padded to the right (low order) with zeros to form a 16-bit word for checksum purposes. This pad octet is not transmitted as part of the packet.

RECEIVER

The sum is computed as above but including the values received in the checksum field. If the 16-bit sum is octal 177777 then the data is presumed to be valid. In all other cases the data is presumed to be invalid.

This unsigned 16-bit sum adds 16-bit quantities with any overflow bit added into the lowest order bit of the sum. This is called 'end around carry'. End around carry addition provides several properties: 1) It provides full commutivity of addition (summing in any order is equivalent), and 2) If you apply a given rotation to each quantity before addition and when the final total is formed apply the inverse rotation, then the result will be equivalent to any other rotation chosen. The latter property gives little endian machines like a PDP-11 the go ahead to pick up 16-bit quantities and add them in byte swapped order.

The PDP-11 code to calculate the checksum is:

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 result

2.3. Sequence Numbers

Sequence numbers work with acknowledge numbers to inform the sender that his last data packet was received, and to inform the receiver of the sequence number of the next data packet it expects to see. When the ACK flag is set in a packet the AN field contains the sequence number of the next data packet it expects from the sender. The sender looks at the AN field and by implication knows that the packet he just sent should have had a sequence number of:

<AN received-1 modulo 2>

If it did have that number that packet is considered to have been acknowledged.

Similarly, the receiver 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 this is not the case then the receiver assumes that it is receiving a duplicate of a data packet it earlier acknowledged. This implies that the packet containing the acknowledgment did not arrive and therefor the packet that contained the acknowledgment should be retransmitted. The duplicate data packet is discarded.

The only packets which require acknowledgment are packets containing status flags (SYN, RST, FIN, or SO) or data. A packet which contains only an acknowledgment, i.e. <AN=n><CTL=ACK>, does not require a response (it contains no status flags or data).

Both the AN and SN fields are a single bit wide. Since at most one packet is in the process of being sent/acknowledged in a particular direction at any one time a single bit is sufficient to provide a method of duplicate packet detection and removal of a packet from the retransmission queue. The arithmetic to advance these numbers is modulo 2. Thus when a data packet has been acknowledged the sender's next sequence number will be the current one, plus one modulo 2: <SN = SN + 1 modulo 2>

The individual acknowledgment of each packet containing data can mislead one into thinking that side A of a connection cannot send data to side B until it receives a packet from B. That only then can it acknowledge B's packet and place in the acknowledging packet some data of its own. This is not the case.

As long as its last packet sent requiring a response has been acknowledged each side of a connection is free to send a data packet whenever it wishes. Naturally, if one side is sending a data packet and it also must acknowledge receipt of a data packet from the other side, it is most efficient to combine both functions in a single packet.

2.4. Maximum Packet Size

The maximum packet size is:

SYNCH + HEADER + Data Checksum + 255 = 261 octets

There is therefor no need to allocate more than that amount of storage for any received packets.