davids (12/10/82)
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, 1982gnu (12/11/82)
Sigh. Yet another ad-hoc protocol invented "because none of the other protocols were good enough". I did this once myself (with PCNet) and came out of it with the belief that in most cases, it doesn't really matter what the protocol is. It only matters that there IS a protocol, that is, an agreement among all the potential users. The larger the group, the better, since the objective is easy interchange. Now that the major packet groups in SF, Tucson, St. Louis, New Jersey, Washington, Vancouver, and elsewhere seem to finally be agreeing on the need for protocol standardization (probably due the the prospect of a satellite mailbox system within a small number of years), out comes yet another protocol. Look: somehow with the horrendous UUCP protocol we've managed to patch together a network of hundreds of computers and thousands of people. Surely with that as a daily example you can live with the problems (and yes, there are plenty) with the agreed-upon standard link-level amateur packet protocol (which itself follows several ISO/ANSI standards, making it likely that cheap available hardware, software, and gatewaying will be available). Please reconsider? Yes, it's definitely fun to play around designing and implementing a protocol for a year or two, but if at the end of it you can only talk to 4 other people, why not consider doing something with better odds? John Gilmore, Sun Microsystems PS: Yes, PCNet works, sort of, and yes, I can talk to about 4 people with it. And yes, it took a year. PPS: There are cheap ways to calculate CRC in software, like ~10 instructions per byte as I recall. It helps a lot to know the math, which I don't.