From: utzoo!decvax!ucbvax!CAD:teklabs!tektronix!davids
Newsgroups: net.ham-radio
Title: Packet protocol proposal (long)
Article-I.D.: tektronix.842
Posted: Thu Dec  9 19:16:49 1982
Received: Sun Dec 12 12:12:16 1982


     This is a proposal for a small network  protocol  suit-
able for ham radio use. There is a small group of us here in
northwest Oregon working on setting up a simplex VHF network
around  this  specification.  Any  constructive criticism or
comments will be accepted. (by mail..)
Dave Schmidt WB7RDI








                   PROPOSED PACKET FORMAT
                 (Preliminary information)
        constructive comments or suggestions welcome


                    David Schmidt WB7RDI



                          ABSTRACT


          Packet radio (and networking in general)  has
     numerous uses, especially in the areas of personal
     computer  file  transfer,  electronic  mail,   and
     general  communications  and control.  Most of the
     common protocols are not suited to Amateur  Radio,
     and   have   limited  applicability  in  a  highly
     volatile network. This packet format  is  intended
     to  implement  ISO  level  1  protocol,  providing
     regional  networking  with  compatibility  between
     many, possibily incompatible, local networks.


                Reply address:

                U.S. mail:      401 SE Maple
                                Scappoose, OR 97056.

                                        or

                                Tektronix DS 19-128
                                PO box 500,
                                Beaverton, OR 97077


                uucp:           tektronix!davids




















               D R A F T  -  December 9, 1982





                           - 2 -


  Format  Description (format info: see appendix B)


  %03x    packet length

  %01c    packet data type: B=binary, T=text, C=control

  %03x    sequence number this packet

  %03x    last sequence number acknowledged from  next  dest
          node

  %s      variable length to/from list

  %s      variable length data

  %04x    packet check word (see appendix C)


  1.      All values are 7 bit ascii,  except  in  the  data
          area, which are by default 7 bit arbitrary binary.


  2.      Most significant bit of each 8-bit byte is an  odd
          orchard bit.  ( see appendix A )
































               D R A F T  -  December 9, 1982





                           - 3 -


TO/FROM list format:


          The to list is just the sequential list  of  nodes
     the  message  is  to  follow  in it's journey. The node
     names are separated by  '!'  characters,*  uucp  style.
     Spaces  and  control  characters are not allowed, since
     they tend to make  handling  I/O  on  some  machines  a
     problem.  Node names ought to be kept to 10 characterss
     or less but no formal limit is needed.  The  list  also
     contains  a  from  section  to allow the receiving node
     reply to the message.  This list is  built  up  as  the
     packet travels, with each station pulling its node name
     from the  to  list  and  putting  it,  along  with  its
     delimiting  character,  onto  the beginning of the from
     list. The to and from lists  are  separated  by  a  '<'
     character.   A  period  delimits  the last entry of the
     from list.

          EXAMPLE:

               To send a msg from 'abc' to 'def' by  way  of
               'efg' and 'ghi':
                                     ghi!efg!def<abc.
               This string is interpreted by node 'ghi'  and
               changed to:
                                     efg!def<ghi!abc.
               and by efg to:
                                     def<efg!ghi!abc.
               and def could respond to the message with:
                                     efg!ghi!abc<def.

          NOTES:


                 1.      No  node  name  may   contain   '<'
                         characters!

                 2.      The  to/from  list   length   stays
                         constant. ( feature )







__________________________
 * The delimiter character tells the node how to relay or
   accept  the  message.  Initially,  the  only delimiter
   character will be the exclaimation  point,  but  other
   delimiters  could  be  used.  (see  'Future  Features'
   section)




               D R A F T  -  December 9, 1982





                           - 4 -


     Data Type Compression:

     Text type (type = 'T')

          No compression, since ASCII is a 7 bit code

     Control type (type = 'C')

          No compression, use ASCII upper case. This is same
          as  text type except the data goes to the protocol
          handling software  instead  of  the  operator.  It
          could  be  used  to get an acknowledge on the last
          packet of a  message,  or  to  enquire  about  the
          status of a node, as an example.

     Binary type (type = 'B')

          To allow shipping 8 bit data, encode  7  bytes  of
          input  data  into 8 7-bit values, justified in the
          lower 7 bits of the value. The first  2  bytes  of
          the  data  are the logical record length in bytes,
          and the logical records are zero filled.

               EXAMPLE:

                    To     send      the      ten      bytes
                    1,2,3,4,5,6,7,8,FF,99 the records are:

                         logical   000A0102030405060708FF99
                         physical  00024010100C0805
                                   0301310F7C640000

                    The physical record is treated as a  bit
                    stream  that  is  then  split into 7 bit
                    groups that are  moved  into  the  least
                    significant 7 bits of 8 bit bytes in the
                    data portion of the  packet.  This  way,
                    the  orchard  bit is still available for
                    error correction.


















               D R A F T  -  December 9, 1982





                           - 5 -


                           Future Features
          (not in preliminary release, but to be introduced)



                    The following features may  become  more
               desirable  as  network  traffic  increases to
               more congested levels.

          Fork:

               This feature will allow one packet to  travel
               (possibly through several relay stations) and
               split  at  some  point  into   packets   that
               continue  along  divergent  paths. The reason
               for this is to allow  a  station  to  send  a
               packet across the network to another area and
               distribute  it  locally.   In   the   initial
               implementation,   it  is  necessary  to  send
               individual  packets   to   each   destination
               station.

          Keep copy:

               This  feature  allows  a  station  to  be   a
               destination  as  well as a relay node. It may
               be easier  to  include  this  with  the  fork
               function,  but  for  now  it is proposed as a
               separate feature.

          Gateway:

               This will become important with time, as more
               networks   become  available.  A  gateway  is
               simply a node that is  'bilingual'--  it  can
               understand  and  generate  packets  in two or
               more different protocols. A gateway will have
               to look at the rest of the to list and decide
               what network it is for. This implies that the
               to/from  list should have the ability to have
               arbitrary  strings  contained  in   it.   For
               example,  if it was desired to send a message
               to the gateway 'xxx' into a foreign  network,
               it  might  be necessary to encode the foreign
               network destination address  in  the  to/from
               list as follows:
                  abc!xxx!$somestring$<here
               The 'somestring' portion would mean something
               to  the gateway, but not necessarily to other
               stations on the network.  This  implies  that
               the initial release of the software should be
               tolerant of any substrings prior to  the  '<'
               character  unless  it  is  to the left of the
               first '!'. This is not a serious problem, and



               D R A F T  -  December 9, 1982





                           - 6 -


               would require little work now, while possibly
               saving lots of work later.   Note  that  this
               precludes  the  use  of  '<'  in  the foreign
               network address string.





















































               D R A F T  -  December 9, 1982





                           - 7 -


                      Syntax for future features

          FORK:           (tolist{,tolist})

               To send a packet to a, b, and c(via d) from e
               via f:
                               f!(a,b,d!c)<e

          KEEP:      use delimiter & instead of !

               To send a packet to  a,  b  and  c  (in  that
               order) from d:
                                  a&b&c<d

          GATEWAY:        no special syntax

               To send a packet to someone  on  usenet  from
               the ham network:
                  gateway!usenet address string<wherever
               The gateway must be able  to  identify  which
               network  the  message  is  for  by some means
               (possibly the next node name) and process the
               rest of the to list accordingly.


































               D R A F T  -  December 9, 1982





                           - 8 -


                         Implementation Hints


               The protocol defined here does not define the
          type   of   transmission   (I.E.   synchronous  or
          asynchronous), the timing of bits  or  transmitter
          keying,  any  upper  level  layers of the protocol
          (except where it is necessary for upper levels  to
          pass data to this layer, as in passing the address
          list to this layer), hardware implementation, etc.
          This  document  is  a suggestion for a data format
          which will allow  the  transfer  of  data  between
          local  area networks (LANs) with utilize different
          formats.  The other use for this document is as  a
          place to start.

               Recently AMSAT came out with a  specification
          for  a  network  protocol  which  is optimized for
          satellite transmission. I feel their  protocol  is
          unsuitable for use as an emergency network, or for
          any unstable one ( as ham networks seem to be * ).
          The  AMSAT network is really just the bottom layer
          (layer 0)  of  an  implementation  which  is  best
          suitable   for  situations  where  a  full  duplex
          repeater is present. It is entirely  possible  for
          the  format  described  in  this  document  to  be
          implemented in a half duplex environment (which is
          what  I  intend  to do) utilizing much of the HDLC
          format which AMSAT has proposed  in  their  bottom
          layer  specification.   I am not rejecting AMSAT's
          proposal, but suggesting that  it  doesn't  handle
          the problems of LANs.

               The system I am implementing  consists  of  a
          datagram  service, with either automatic or manual
          routing (done at a higher level) done at the point
          of  origin.  This allows relay stations to pass on
          the datagram with little processing,  while  still
          allowing   features   typically   found  on  large
          networks.








__________________________
 * By unstable I mean that the existence (as far as other
   nodes of the network is concerned) of a node (station)
   is dependent on factors such as  the  antenna  falling
   down, kids unplugging the rig, etc.




               D R A F T  -  December 9, 1982





                           - 9 -


          WB7RDI Network layer 0 specification (preliminary)


               This is a description of the particular layer
          0  software  and protocol to be implemented for my
          use (and by some of the hams I work with).  It  is
          included  here  as  an example, not as part of the
          level 1 protocol referred to in the rest  of  this
          document.

               The software used  in  the  network  will  be
          written  primarily  in  machine  independent, high
          level  code  (C  language),   with   the   machine
          dependent  sections  clearly  separated  from  the
          rest. In this system, the bottom level will get  a
          buffer  of  transmit data (with the header already
          in place) and will place  it  in  an  SDLC  format
          frame.  The  SDLC address field will be set to the
          'global'  address  (  address  255   )   for   any
          transmission that is to be directed to a node that
          has an unknown address, such as when  a  relay  is
          desired,  but  otherwise is undefined. The control
          field is left zeros for now, but later could carry
          additional information.** The  information  fields
          of  the  frame  are  filled with the data from the
          layer 1 buffer, and the final checksum is  as  per
          SDLC  specification.  This  has been done to allow
          the Z80-SIO to perform much  of  the  work.  (Many
          other synchronous interface chips have the ability
          to do this, such as the Intel 8251, but  the  Z80-
          SIO  contains hardware CRCC generation and the Z80
          interrupt structure for our Z80 based systems)

               At this time, the transmit routine will  wait
          for  a  clear  channel,  then  transmit the frame,
          preceded by  a  number  of  SDLC  flag  characters
          (number   to   be   defined   later,   after  some
          experimentation). As soon as the  frame  has  been
          completely  sent,  a number of flag characters are
          sent  followed  by   the   deactivation   of   the
          transmitter.   At  this point, a timer will start.
          If the times times out before  an  acknowledgement
          is  received,  the frame will be queued to be sent
          again.  Only after  the  frame  has  been  sent  a
          number  of  times  will the attempt be aborted. If
          the transmit routine  detects  a  carrier  on  the
          channel  when  either  the  transmitter  is  first
__________________________
** The address and control fields being stated  this  way
   force  compatibility  between SDLC and HDLC, so to the
   user, it is not important which  is  being  used.   NO
   ATTEMPT  HAS  BEEN  MADE  TO  USE  THE  FULL SDLC/HDLC
   SPECIFICATION, just the basic frame format.




               D R A F T  -  December 9, 1982





                           - 10 -


          turned  off,  or  when  the  frame  is  ready  for
          transmission,  the  transmitter  will  delay for a
          time that is  proportional  to  the  frame  length
          times  a locally generated random number plus some
          constant. This allows small frames a better chance
          of  making  it  through  the  collisions  than big
          frames. This is also a type  of  priority,  making
          small  packets  more  desirable  to use than large
          packets.  Small packets should serve  to  increase
          the   rate  of  data  flow,  resulting  in  higher
          transfer efficiency for a particular message.   It
          is  assumed  that  ethics  will  keep  people from
          always using a non-random number, which can result
          in  two  stations  always  trying  to  transmit at
          exactly the same time. This also indicates a  need
          for   a   good  random  number  generator  (either
          hardware or software) at each  station,  with  the
          number  scrambled  by  something  other  than  the
          network information, to which  all  stations  have
          access.

               The  receive  routine  is  always  ready   to
          receive  data,  depositing  the  data  in  a large
          buffer for processing when  time  allows.  In  the
          later  versions,  I  intend to use a multi-tasking
          kernel in the networking  software  to  allow  the
          transmit routine to 'roll out' when it is waiting.
          This will make more time available for the receive
          routine  to  process incoming data. If the receive
          buffer overflows, the data that is the  oldest  is
          discarded,  as  a  retransmission  should occur to
          replace it.

               We  have  been  working  with   Manchester***
          encoding modems using direct FSK of the VHF  gear.
          This  results in good signal to noise ratios for a
          given power due to the low bandwidth involved.  It
          also  makes  it  easier  to 'roll your own' modem,
          since  the  FM  gear  has  most  of  the   'modem'
          functions   like   limiters,  discriminators,  and
          carrier detection built in. (I have done  most  of
          the  work  on  Icom 22-S transceivers, but work is
          taking place on a Motorola MICOR at this time.)

__________________________
*** Manchester encoding is a method which allows data  to
    be modulated on a carrier to achieve a 50% duty cycle
    over any bit period. It is simply  180  degree  phase
    modulation of a square wave equal in frequency to the
    bit rate, and synchronized to  the  bit  rate  (don't
    worry,  it  fits into about 4-6 ICs). This allows the
    data to pass through AC  coupled  stages  without  as
    much distortion as would usually happen.




               D R A F T  -  December 9, 1982





                           - 11 -


          APPENDIX A: Orchard codes

          Orchard Coding -- a method to correct and detect errors


               The orchard code was  covered  very  well  in
          Electronics,  May  5, 1981. A brief description is
          in order here, though.

               Imagine an orchard (with each tree  being  in
          either  a row or column) with a road running along
          one of the rows at the edge  of  the  orchard.  To
          identify  any given tree, several methods could be
          used: the row and column  of  the  tree,  or  some
          other  geometrical  relation.  If  the only way to
          identify the tree is by placing  flags  along  the
          road,   it  becomes  apparent  that  the  tree  in
          question can be identified by placing flags by the
          columns  in  which  the  tree  is  a  member. Some
          agreement  about  the  definition  of  columns  is
          needed,  of  course. This is the theory used here;
          any bit can be singled out of an array of bits  by
          flags  at  the  column it is in, as well as by the
          other columns where it is visible at a  45  degree
          angle. (see below)


                               column numbers
                  1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l
                  * * * * ` * * * ! * * * ' * * * * * * * * 7
                  * * * * * ` * * ! * * ' * * * * * * * * * 6
                  * * * * * * ` * ! * ' * * * * * * * * * * 5
                  * * * * * * * ` ! ' * * * * * * * * * * * 4
                  * * * * * * * * + * * * * * * * * * * * * 3
                  * * * * * * * * * * * * * * * * * * * * * 2
                  * * * * * * * * * * * * * * * * * * * * * 1
                  * * * * * * * * * * * * * * * * * * * * * 0

                                                            ^
                                                            |
                                                          row #
















               D R A F T  -  December 9, 1982





                           - 12 -


               To point to the bit marked with a  plus  sign
          (col  9, row 3), it is only needed to mark columns
          5, 9, and d. These are  on  the  diagonals  marked
          with quotes.  By calculating a 'parity' * for each
          set of diagonals from a bit, it is easy to compare
          this parity later to see if anything has  changed.
          It  is  also fairly easy to see that if columns 5,
          9, and d are of the wrong parity, the  bit  marked
          with  a  plus is in error. I have found that it is
          possible to reconstruct data that has  been  badly
          damaged   fairly  well,  but  it  is  possible  to
          reconstruct it wrong if there is more than one bit
          in  error  in  a local area (the diagonals for two
          bits  near  each  other   intersect   at   several
          locations)  which  is  why a second check for data
          integrity is used (see the checksum words  at  the
          end  of  the  packet spec). Orchard codes on 7 bit
          data (8 bit bytes) cost 12.5% overhead for  binary
          data,  and  are free for ASCII, as compared to 50%
          and higher for many error correcting  codes.  They
          also   seem   to  be  good  in  the  bursty  noise
          environment in which radio seems doomed  to  live.
          (Much  like holograms, a lot of the buffer of data
          can be reconstructed from what is left,  but  also
          like holograms, the 'image' detail deteriorates as
          more of the buffer is destroyed.)

               In the case of light channel usage and  short
          frames,  it is probably just as well to retransmit
          the frame, but when usage is high or you  have  an
          error  in  a  large frame, reconstruction can save
          valuable time.













__________________________
 * It is rather arbitrary, but I have treated the  parity
   calculation  much  the same as it is done in the usual
   usage of parity: odd parity = odd number of bits in  a
   group,  even  parity = even number of bits in a group,
   including the parity bit in a group. When I  say  'odd
   orchard',  I  mean 'there are an odd number of bits in
   each group of diagonals from an orchard bit'.




               D R A F T  -  December 9, 1982





                           - 13 -


          APPENDIX B: Format specification

               The format for the data is  specified  to  be
          compatible   with   standard   'C'  printf  format
          strings. For the benefit of  people  not  familiar
          with   printf,   the   following   information  is
          supplied.


                 o The percent sign is used  to  signal  the
                   start  of a format specification.  In the
                   usage shown, it is not really necessary.



                 o The number  following  the  percent  sign
                   (when  present)  specifies  the number of
                   characters of information that should  be
                   output. Furthermore, if the number starts
                   with a zero, the leading zeros should  be
                   printed.



                 o The  character   following   the   number
                   specifies  the  type  of  data:  'c'  = a
                   single character,  'x'  =  a  hexadecimal
                   value,   'd'   =  a  decimal  value,  's'
                   indicates a  string  of  characters  (the
                   string  does  not contain anything except
                   the characters, no termination characters
                   or   leading   and  trailing  blanks  are
                   intended).   The  only   variation   from
                   standard  C definition is in the case for
                   hexadecimal characters:  capital  letters
                   are more portable.

                    EXAMPLE:

                              The string %03x%2c%s

                            indicates a three character  hex
                    number  with  leading  zeros followed by
                    two characters, followed by an arbitrary
                    length string.












               D R A F T  -  December 9, 1982





                           - 14 -


               APPENDIX C: Some thoughts on the checksum field

                    The  checksum  field  would  ideally  be
               something  along the lines of a CRCC-16 check
               word, but software implementations of CRCC-16
               take  several  seconds  to execute for packet
               lengths over a few  bytes  (4095  bytes  took
               approximately 7 seconds when written in BDS C
               -- but I don't maintain that I did  the  most
               optimum  coding  ). For the moment, I plan to
               use a simple summation of the  bytes  of  the
               packet,   which   takes  much  less  time  to
               calculate.

                    I  would  appreciate  comments  on  this
               subject,  as  well  as  on the possibility of
               assuming the existence of  hardware  CRCC  in
               the  system  doing  the error correction.  It
               would be possible to allow the checksum field
               to   be   unspecified,  and  just  let  error
               correction happen between stations that agree
               on   a  checksum  method,  since  the  packet
               checksum could be verified in a  lower  level
               by   something  like  the  HDLC  frame  check
               sequence.  In   this   case,   the   checksum
               specified  on  this  level would be used only
               for the error correction  system.   The  type
               and  existence  of  the  packet checksum word
               could be defined for any given LAN, with  the
               gateway stations handling conversion from one
               checksum word format  to  another.  Within  a
               LAN,  the  case  of  the  data type character
               could determine whether error correction  was
               'turned   on'   for   a   packet--upper  case
               indicating orchard bits and checksums present
               and  lower  case  indicating  that  no  error
               checking exists in this level, for example.




















               D R A F T  -  December 9, 1982