Packet Driver Protocol
G. L. Chesson
Bell Laboratories
Abstract
These notes describe the packet driver link protocol that
was supplied with the Seventh Edition of and is used by the
UUCP program.
General Information flow between a pair of machines may be regu-
lated by first representing the data as sequence-numbered packets
of data and then establishing conventions that govern the use of
sequence numbers. The PK, or packet driver, protocol is a par-
ticular instance of this type of flow-control discipline. The
technique depends on the notion of a transmission window to
determine upper and lower bounds for valid sequence numbers. The
transmitter is allowed to retransmit packets having sequence
numbers within the window until the receiver indicates that pack-
ets have been correctly received. Positive acknowledgement from
the receiver moves the window; negative acknowledgement or no
acknowledgement causes retransmission. The receiver must ignore
duplicate transmission, detect the various errors that may occur,
and inform the transmitter when packets are correctly or in-
correctly received. The following paragraphs describe the packet
formats, message exchanges, and framing used by the protocol as
coded in the UUCP program and the kernel. Although no attempt
will be made here to present internal details of the algorithms
that were used, the checksum routine is supplied for the benefit
of other implementors. Packet Formats The protocol is defined in
terms of message transmissions of 8-bit bytes. Each message in-
cludes one control byte plus a data segment of zero or more in-
formation bytes. The allowed data segment sizes range between 32
and 4096 as determined by the formula 32(2k) where k is a 3-bit
number. The packet sequence numbers are likewise constrained to
3-bits; i.e. counting proceeds modulo-8. The control byte is
partitioned into three fields as depicted below.
bit 7 6 5 4 3 2 1 0
t t x x x y y y
The t bits indicate a packet type and determine the interpreta-
tion to be placed on the xxx and yyy fields. The various in-
terpretations are as follows:
tt interpretation
00 control packet
10 data packet
11 `short' data packet
01 alternate channel
A data segment accompanies all non-control packets. Each
transmitter is constrained to observe the maximum data segment
size established during initial synchronization by the receiver
that it sends to. Type 10 packets have maximal size data seg-
ments. Type 11, or `short', packets have zero or more data bytes
but less than the maximum. The first one or two bytes of the
data segment of a short packet are `count' bytes that indicate
the difference between the maximum size and the number of bytes
in the short segment. If the difference is less than 127, one
count byte is used. If the difference exceeds 127, then the
low-order seven bits of the difference are put in the first data
byte and the high-order bit is set as an indicator that the
remaining bits of the difference are in the second byte. Type 01
packets are never used by UUCP and need not be discussed in de-
tail here. The sequence number of a non-control packet is given
by the xxx field. Control packets are not sequenced. The newest
sequence number, excluding duplicate transmissions, accepted by a
receiver is placed in the yyy field of non-control packets sent
to the `other' receiver. There are no data bytes associated with
a control packet, the xxx field is interpreted as a control mes-
sage, and the yyy field is a value accompanying the control mes-
sage. The control messages are listed below in decreasing prior-
ity. That is, if several control messages are to be sent, the
lower-numbered ones are sent first.
xxx name yyy
1 CLOSE n/a
2 RJ last correctly received sequence number
3 SRJ sequence number to retransmit
4 RR last correctly received sequence number
5 INITC window size
6 INITB data segment size
7 INITA window size
The CLOSE message indicates that the communications channel is to
be shut down. The RJ, or reject, message indicates that the re-
ceiver has detected an error and the sender should retransmit
after using the yyy field to update the window. This mode of re-
transmission is usually referred to as a `go-back-N' procedure.
The SRJ, or selective reject, message carries with it the se-
quence number of a particular packet to be retransmitted. The
RR, or receiver ready, message indicates that the receiver has
detected no errors; the yyy field updates the sender's window.
The INITA/B/C messages are used to set window and data segment
sizes. Segment sizes are calculated by the formula 32(2yyy) as
mentioned above, and window sizes may range between 1 and 7.
Measurements of the protocol running on communication links at
rates up to 9600 baud showed that a window size of 2 is optimal
given a packet size greater than 32 bytes. This means that the
link bandwidth can be fully utilized by the software. For this
reason the SRJ message is not as important as it might otherwise
be. Therefore the implementations no longer generate or respond
to SRJ messages. It is mentioned here for historical accuracy
only, and one may assume that SRJ is no longer part of the proto-
col. Message Exchanges Initialization Messages are ex-
changed between four cooperating entities: two senders and two
receivers. This means that the communication channel is thought
of as two independent half-duplex data paths. For example the
window and segment sizes need not be the same in each direction.
Initial synchronization is accomplished with two 3-way
handshakes: two each of INITA/INITB/INITC. Each sender transmits
INITA messages repeatedly. When an INITA message is received,
INITB is sent in return. When an INITB message is received and
an INITB message has been sent, an INITC message is sent. The
INITA and INITB messages carry with them the packet and window
size that each receiver wants to use, and the senders are sup-
posed to comply. When a receiver has seen all three INIT mes-
sages, the channel is considered to be open. It is possible to
design a protocol that starts up using fewer messages than the
interlocked handshakes described above. The advantage of the
more complicated design lies in its use as a research vehicle:
the initial handshake sequence is completely symmetric, a
handshake can be initiated by one side of the link while the con-
nection is in use, and the software to do this can utilize code
that would ordinarily be used only once at connection setup time.
These properties were used in experiments with dynamically ad-
justed parameters. That is attempts were made to adapt the win-
dow and segment sizes to changes observed in traffic while a link
was in use. Other experiments used the initial handshake in a
different way for restarting the protocol without data loss after
machine crashes. These experiments never worked well in the
packet driver and basically provided the impetus for other proto-
col designs. The result as far as UUCP is concerned is that ini-
tial synchronization uses the two 3-way handshakes, and the INIT
messages are ignored elsewhere. Data Transport After in-
itial synchronization each receiver sets a modulo-8 incrementing
counter R to 0; each sender sets a similar counter S to 1. The
value of R is always the number of the most recent correctly re-
ceived packet. The value of S is always the first sequence
number in the output window. Let W denote window size. Note
that the value of W may be different for each sender. A sender
may transmit packets with sequence numbers in the range S to
(S+W-1) mod-8. At any particular time a receiver expects arriv-
ing packets to have numbers in the range (R+1) mod-8 to
(R+W) mod-8. Packets must arrive in sequence number order are
are only acknowledged in order. That is, the `next' packet a re-
ceiver will acknowledge must have sequence number (R+1) mod-8. A
receiver acknowledges receipt of data packets by arranging for
the value of its R counter to be sent across the channel where it
will be used to update an S counter. This is done in two ways.
If data is flowing in both directions across a channel then each
receiver's current R value is carried in the yyy field of non-
control packets. Otherwise when there is no bidirectional data
flow, each receiver's R value is transmitted across the link as
the yyy field of an RR control packet. Error handling is up to
the discretion of the receiver. It can ignore all errors in
which case transmitter timeouts must provide for retransmission.
The receiver may also generate RJ error control packets. The yyy
field of an incoming RJ message replaces the S value of the local
sender and constitutes a request for retransmission to start at
that sequence number. The yyy field of an incoming SRJ message
selects a particular packet for retransmission. The resemblance
between the flow control procedure in the packet driver and that
defined for X.25 is no accident. The packet driver protocol be-
gan life as an attempt at cleaning up X.25. That is why, for ex-
ample, control information is uniform in length (one byte), there
is no RNR message (not needed), and there is but one timeout de-
fined in the sender. Termination The CLOSE message is
used to terminate communications. Software on either or both
ends of the communication channel may initiate termination. In
any case when one end wants to terminate it sends CLOSE messages
until one is received from the other end or until a programmable
limit on the number of CLOSE messages is reached. Receipt of a
CLOSE message causes a CLOSE message to be sent. In the environ-
ment it also causes the SIGPIPE or `broken pipe' signal to be
sent to the local process using the communication channel.
Framing The term framing is used to denote the technique
by which the beginning and end of a message is detected in a byte
stream; error control denotes the method by which transmission
errors are detected. Strategies for framing and error control
depend upon additional information being transmitted along with
the control byte and data segment, and the choice of a particular
strategy usually depends on characteristics of input/output dev-
ices and transmission media. Several framing techniques are in
used in support of PK protocol implementations, not all of which
can be described in detail here. The technique used on asynchro-
nous serial lines will be described. A six byte framing envelope
is constructed using the control byte C of a packet and five oth-
er bytes as depicted below.
<DLE><k><c0><c1><C><x>
The <DLE> symbol denotes the ASCII ctrl/P character. If the en-
velope is to be followed by a data segment, <k> has the value
log2(size)-4; i.e. 1 < k < 8. If k is 9, then the envelope
represents a control packet. The <c0> and <c1> bytes are the
low-order and high-order bytes respectively of a 16-bit checksum
of the data segment, if there is one. For control packets <c1>
is zero and <c0> is the same as the control byte C. The <x> byte
is the exclusive-or of <k><c0><c1><C>. Error control is accom-
plished by checking a received framing envelope for compliance
with the definition, and comparing a checksum function of the
data segment with <c0><c1>. This particular framing strategy as-
sumes data segments are constant-sized: the `unused' bytes in a
short packet are actually transmitted. This creates a certain
amount of overhead which can be eliminated by a more complicated
framing technique. The advantage of this strategy is that i/o
devices can be programmed to take advantage of the constant-sized
framing envelopes and data segments.
The checksum calculation is displayed below as a C function.
Note that the code is not truly portable because the definitions
of and are not necessarily uniform across all machines that might
support this language. This code assumes that and are 16 and 8-
bits respectively.
/* [Original document's version corrected to actual version] */
chksum(s,n)
register char *s;
register n;
{
register short sum;
register unsigned short t;
register short x;
sum = -1;
x = 0;
do {
if (sum<0) {
sum <<= 1;
sum++;
} else
sum <<= 1;
t = sum;
sum += (unsigned)*s++ & 0377;
x += sum^n;
if ((unsigned short)sum <= t) {
sum ^= x;
}
} while (--n > 0);
return(sum);
}
TUCoPS is optimized to look best in Firefox® on a widescreen monitor (1440x900 or better).
Site design & layout copyright © 1986-2024 AOH
