This is an ASCII representation of the Postscript file in
/hamradio/tcpip/misc/newlink.ps which contains copies of
the presentation slides for non-Postscript equipped users.
---
Slide #1
Toward New Link-Layer
Protocols for
Amateur Packet Radio
Phil Karn, KA9Q
karn@unix.ka9q.ampr.org
---
Slide #2
AX.25
* Created in 1982 - over a decade ago
* Based on CCITT X.25 LAPB (itself based on HDLC and SDLC)
* Defines datagram-style addressing header for use with LAPB
* No allowance for the special problems of radio - collisions, noisy
radio links, congestion, hidden terminals, etc
---
Slide #3
AX.25 - 11 years later
* What do we have now that we didn't have in 1982?
*Far* more powerful computers (100-1000x CPU, RAM, disk)
A variety of RF modems (sort of)
A variety of upper layer protocols (TCP/IP, ROSE, NET/ROM, TexNet)
A *lot* of users
A decade of experiance!
---
Slide #4
AX.25 - Lessons Learned
* Link protocols designed for wired networks (espeacially by PTT
monopolies) don't transition very well to radio
* Efficient channel access is a serious problem in real networks
* Pure ARQ doesn't work very well, espeacially with QRM
like 70cm military radar
* What a link protocol doesn't do is just as important as what it
does do (e.g., "connections" are superfluous at the link layer)
* We actually need a variety of link protocols, each suited to a
particular channel (wire, HF, VHF/UHF, satellite), and tied together
into a uniform Internetwork, e.g., with TCPIP. CLOVER is one
such protocol, specifically designed for HF. We need more.
---
Slide #5
Forward Error Correction (FEC)
Send redundant information to allow correction of (some)
errors without retransmission
Exploit Shannon's tradeoff between bandwidth and S/N ratio:
C = B log2(1+S/N)
The *only* practical way to deal with certain types of interference,
e.g., radar
---
Slide #6
Why Use FEC?
* ARQ discards "bad" packets, while FEC uses *all* of the received
energy to produce a (hopefully) error-free packet
* As long as ARQ retransmissions are rare, the loss is minimal
Rule of thumb: no more than 1% packet loss rate
* We are far worse than this on most amateur links!
* Small packets may help, but adds considerable overhead
* The alternative (increasing power and/or antenna gain) is not always
practical or economical
* Brains over brawn!
---
Slide #7
Why Not Use FEC?
* Constant overhead, whether needed or not
* Compute-intensive to decode
---
Slide #8
FEC - Some Examples
* Block Coding
BCH - AMPS (FM cellular phone) control messages
Reed-Solomon (compact disks)
Hamming (Microsat computer memories)
* Convolutional (stream)
CDMA digital cellular
Space communications (VSAT, interplanetary, etc)
V.32/V.32bis telephone modems ("trellis coding")
---
Slide #9
Sample Convolutional Coder
+---------------------------+
1 -->| XOR | --> Symbol #1
+---------------------------+
^ ^ ^ ^ ^
| | | | |
+---+---+---+---+---+---+---+
Data in -->| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+---+
| | | | |
v v v v v
+---------------------------+
| XOR | --> Symbol #2
+---------------------------+
k=7("constraint length")
r=1/2("rate")
NASA standard
planetary code
---
Slide #10
Decoding Convolutional Codes
* Parallel (Viterbi)
Constant decode time
Limited constraint length - complexity O(2^k)
Well suited for hardware implementation - chips commercially available
Best for channels limited by thermal or thermal-like noise, e.g.,
satellite or spread spectrum
* Sequential (Fano, Stack)
Variable decoding time, depends on error rate; either faster or slower
than Vierbi
Allows very long constraint lengths (k=32 common)
With k large, nil probability of incorrect decode (timeout more likely)
Good for software implementation, espeacially when error rate is low
---
Slide #11
Sequential Decoding
+-------
|
| 11
|
+-------+
| |
| | 00
| 00 |
+-------+ +------- (etc)
| | +-------
| | |
| | 11 | 10
| | |
| +-------+
| |
1 | | 01
| 01 |
^ | +-------
| Start --> --+
v | +------- (etc)
| 10 |
0 | | 00
| |
| +-------+
| | |
| | 01 | 11
| | |
+-------+ +-------
| +-------
| 10 |
| | 01
| |
+-------+
|
| 10
|
+-------
---
Slide #12
Sequential Decoding, contd
* Decoder has a copy of the encoder, compares received symbols
with versions regenerated locally
* By "intelligent" trial and error, the decoder finds the data
sequence that produces the best match between locally
regenerated symbols and the actual received sequence
* The decoder also produces a "metric", its estimate of
the quality of the incoming symbol stream. Like an S-meter,
only more useful
* Decoder is very fast when there are few errors because it doesn't
have to back up very much; slows down considerably when error
rate is very high
---
Slide #13
A Fano Decoder in C
* "Hard decision" Fano Sequential Decoder in C
* Choice of several r=1/2, k=32 polynomial (e.g., NASA standard)
* On a 33 MHz 486, decodes 56 kilosymbols (28 kilobits) per second
on average with input symbol error rate < 2%
* Proves feasibility of sequential decoding with modern amateur
resources
---
Slide #14
Frame Synchronization
* Need to reliably detect the beginning of a packet in the presense
of errors as high as 10% to provide margin for FEC
* 8-bit HDLC "flag" unsuitable due to short length
* Use pseudorandom sequence with good autocorrelation properties,
e.g., a PN sequence
* The longer the PN sequence, the greater the margin between missing
frame sync and falsely detecting one in noise. 64 looks good, and is
easy to implement in software on a 32-bit CPU
* Reliable sync enables use of negative acknowledgements (NAKs) to
request additional information to aid decoding
---
Slide #15
Detecting Sync
received +--------------------------+
symbols ----> | 64-stage shift register |
+---------------+----------+
|
+--+--+
64-bit ----> | XOR |
sequence +--+--+
mask |
+---+---+
| count |
| 0's |
+---+---+
|
v
0-Count > T
or < 64-T (T ~=13)
---
Slide #16
Hidden Terminals
* Proposed solution: Use Multiple Access with Collision Avoidance
(MACA), ARRL Computer Networking Conference 1990
* Synopsis: Use RTS/CTS (Request-to-Send/Clear-to-Send) handshake
to hold off hidden terminals before actually sending data
* Extra overhead of RTS/CTS handshake can be mitigated with
large data packets, which use of FEC facilitates
---
Slide #17
One Possible Frame Layout
+------+--------+----------+-------------------------+-----------+
| sync | header | hdr tail | data (coded or uncoded) | data tail |
+------+--------+----------+-------------------------+-----------+
tail replaced
Header contents (always coded): with CRC
in uncoded
Source address (callsign) data packets
Destination address
Packet type (RTS, CTS, data, ACK, NAK)
Data length
Data format (data only, parity only, both, neither, interleave on/off)
Decoder metric from last packet received
Use r=1/2 systematic code in adaptive ARQ/FEC hybrid to allow
transmission of FEC parity symbols only when needed
---
Slide #18
Sample Protocol Sequence
Sender Receiver
+------+ +----------+
|\
| \ RTS (length)
\
\| Holds off
/| hidden terminals
/
/ CTS (length)
|/
|\
\ Data
\
\| Rx CRC fails,
/| requests parity
/
/ NAK
|/
|\
\ Parity
\
\| Rx decodes packet,
/| returns metric
/
/ ACK (metric)
|/
|\
---
Slide #19
Conclusion
Although forward error correction (FEC) has been around in
the commercial, military and scientific worlds for some time,
only recently have dramatic advances in personal computers
brought these powerful techniques within the means of the
average radio amateur.
Now is the time to experiment with FEC with an eye toward a
whole new generation of amateur packet radio link layer protocols.
---
EOF