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