Simtel MSDOS - Coast to Coast/simteldosarchivecoasttocoast2.iso/uucp/uucproto.des

Text File | 1994-03-07 | 14KB | 247 lines

                     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);
     }