Whilst much research in data communications is focussed on high speed networks, there are also growing needs to support data transmission over very low speed networks, such as packet radio. A new simplified Logical Link Control layer, DUAL, is described, which is designed for the efficient transmission of higher layer traffic (such as IP). This is achieved by using link layer addresses tailored to the network protocol used, minimizing the link layer overheads, and by incorporating a modified IP header compression scheme adapted for use in a multi-point environment. The implementation of DUAL in FreeBSD is then described.
This paper describes a new Link Protocol called DUAL (Digital Unreliable Amateur Link protocol), designed for flexible and efficient transmission of higher layer traffic (such as IP), over very low speed networks (such as packet radio [Kah77]), by:
Packet radio is a mode of communications that links stations together using a shared access wireless media. An effort to standardize these networks has been underway since 1982, under the sponsorship of the American Radio Relay League [KPD85] and [DW89], and has produced a standard for a link level protocol suitable for packet-radio networks known as AX.25 [Fox84]. The AX.25 Link-Layer Protocol is designed to be used between Amateur Radio stations in a multi-point communications environment. It is closely based on HDLC [Bla93]. Figure 1 below depicts the structure of the AX.25 frame.
There are two differences between the AX.25 frame format and that of HDLC: the Protocol Identifier (PID) field and the address field. The PID field is used to designate the layer 3 protocol that is using the AX.25 link protocol. This allows multiple users of the link layer protocol. Another difference between AX.25 and HDLC is the address field. The AX.25 address field is from 14 to 70 octets long, depending on whether and how many repeaters are used between a particular source-destination pair. If the sending and receiving stations are in the same cluster (within range of each other), then it is only necessary to specify the source and destination station addresses. Each is specified using 7 octets, which contains a callsign of up to 7 characters. If a frame is to go through a repeater, an additional source route address subfield is appended to the end of the address field. For a comprehensive discussion about how to encode the AX.25 address field, see [Fox84].
A key issue in the packet radio network is transmission efficiency, and it is clear that AX.25 doesn't use its link capacity efficiently because:
DUAL attempts to address some of the identified deficiencies in AX.25. DUAL is designed to accept packets from higher layers, and to pass them on to the appropriate MAC and Physical layers for encoding and eventual transmission. The receiving entity takes no remedial actions; if the frame is in error due to transmission noise, it is discarded, and the receiver is not informed about the loss of the traffic. Error recovery is a function of upper-layer protocols, like TCP.
DUAL is configured to support connectionless-mode operations. This mode does not set up a logical link connection; instead it manages the link layer frames as independent and separate entities. No relationship is maintained between successive data transfer, and moreover, ACKs and NACKs are not provided. Error checking is performed on the frame by the Checksum field.
Since DUAL is connectionless, there will be no requests for retransmissions of bad frames, and collision may also occur, with the potential of losing the frames that collided. Collision detection and recovery is the responsibility of the MAC layer below DUAL.
Because of the connectionless nature of DUAL the following services provided by the AX.25 protocol are not required:
These are part of the reliable virtual circuit capabilities found in AX.25, which have been removed to minimise the header size in DUAL. The address field is also different in DUAL.
DUAL, the Digital Unreliable Amateur Link format, provides an amateur link layer with:
DUAL sits as the basic Logical Link Control layer. Below DUAL is the Medium Access Layer, which controls access to the link and performs other tasks such as bit/byte-stuffing. At the bottom is the Physical Layer, which transmits the data over the medium using some form of modulation, and perhaps with some data encoding.
A fuller description of the DUAL protocol is given in [MTB95].
DUAL's packet format is designed to be minimal, flexible, and to meet the needs of both the underlying MAC and Physical layers, and the Network layers above DUAL. In order to minimise header sizes, DUAL is a datagram protocol only. Also DUAL is designed to tailor its link layer addresses to be more useful to the network layers above DUAL. This again helps to reduce the size of DUAL's headers.
The protocol field is divided into a Protocol-Id (5 bits) and an Address-Type (3 bits), and specifies the higher layer protocol used. The size and format/content of the Source, Destination and Checksum fields are determined entirely by the Protocol-Id/Address-Type field, and are tailored to suit the protocol being transmitted over the link. For most Protocol-Id/Address-Type pairs, it is expected that the checksum will be calculated according to the ISO 3309 (HDLC) specification [ISO3309].
The Source and Destination Address fields contain the link address of the node which transmits the packet, and the node which is the destination of the packet. The format of each field is determined by the Protocol-Id/Address-Type field in the packet. Note that the two addresses need not be the same size or format; this provides more flexibility for choosing link addresses by the higher layer protocol. However, both must be an integral number of octets wide.
The Data field contains the data payload of the packet. The format depends on the upper level protocol described by the Protocol-Id.
As can be seen, the DUAL packet format is very minimal. As an example, where IP is used over DUAL on a Class-C subnet, the overall DUAL link header is 5 octets: 1 for protocol/address, 1 for source, 1 for destination and 2 for the checksum. This compares well with the 19 octets required in the existing packet radio AX.25 header for IP, a saving of 74% in the link header.
DUAL can support up to 32 higher layer protocols. The following protocol-ids are currently defined.
| Value | Description |
| 0: PR_BCAST | The data field contains some information to be broadcast to all stations on the link described below of packets with this protocol-id. |
| 1: PR_VC | This id is reserved for future use for a protocol that provides AX.25-style virtual circuit connections. |
| 2: PR_NETROM | This id is reserved for future use in carrying NETROM data. |
| 3: PR_ROSE | This id is reserved for future use in carrying ROSE data. |
| 4: PR_IP | The data field contains an IP datagram, and is described in detail later. |
| 5: PR_CIP | The data field contains a TCP/IP segment which has been compressed, and is described in detail later. |
| 6: PR_IPX | This id is reserved for future use in carrying Novell IPX data. |
| 30: PR_EXP0 | This id is reserved for future use in carrying data for experimental protocols. |
| 31: PR_EXP1 | This id is reserved for future use in carrying data for experimental protocols. |
A descriptive name for each Protocol-Id is given, starting with the prefix `PR_'. Note that not all 32 values have been `given' to protocols, nor has the packet formats for those protocols with protocol-ids been defined. These packet formats will be defined in future papers.
At the time of writing, only the PR_BCAST, PR_IP and PR_CIP packet formats and protocol definitions have been defined.
The PR_BCAST Protocol-Id is used to broadcast frames on a DUAL link.
All broadcast packets include the callsign of the transmitting station as the source address. This is a fixed 10-octet field. The callsign is expressed in 7-bit ASCII, with the most significant bit of each octet off (i.e 0). The callsign is `big-endian', i.e the first characters of the source callsign come first in the field. If the callsign is shorter than 10 characters, the unused octets have all their bits off (i.e 0).
Thus, for example, the callsign VK1XWT would be represented by the 10 octets 86, 75, 49, 88, 87, 84, 0, 0, 0, 0 (decimal).
The packet has no destination address; it is implicit that the packet is to be received by all stations, and hence the destination address is non-existent (or more strictly, it has a length of zero). The Checksum field is 2 octets in length and is calculated as per the checksum in PR_IP.
This format allows a station to broadcast its callsign and associated link layer addresses to satisfy the amateur regulations.
When the Protocol-Id field is 0 (PR_BCAST) and the Address-Type field is 0 (AD_CALL), the packet contains the sender's amateur callsign and one or more DUAL Link addresses that are to be associated with this callsign. The format of the packet is shown in Figure 3.
Between the Callsign and the CRC are one or more blocks which give link addresses associated with the callsign. Each block begins with two octets. The first gives the size in octets of the link address in the block. The second octet gives a Protocol-Id/Address-type pair that identifies the format of the given link address.
The Size field in each block is required, as an implementation of DUAL may not be able to recognise a given link address. Therefore it needs to know the size of the given link address so that it can skip it and parse any further link addresses. The drawback of this field is that it limits link addresses to 255 octets in size.
This format allows a station to broadcast its callsign and plain ASCII text in its Data field. The intention is to allow BBSs to broadcast stuff like: VK1BBS: Mail for VK1XWT, VK10K VK1KCM.
When the Protocol-Id field is 0 (PR_BCAST) and the Address-Type field is 1 (AD_BEACON), the packet contains the sender's amateur callsign and the BBS broadcast data, for example: VK1BBS: Mail for VK1XWT, VK1OK, VK1KCM. The format of the packet is shown in Figure 4. The actual textual information to be broadcasted comes between the Callsign and the CRC.
As part of our design goals in improving efficiency, as well as minimising the header size, we also wanted to remove the need for using ARP and RARP. To do this, we decided to use full or partial IP addresses as the Link address when transmitting IP packets. Partial IP addresses can be used when the size of the subnet serviced by the link is known.
DUAL defines the following address-types for use when IP is the higher layer protocol.
| Value | Description |
| 0: AD_0IP | The address field is zero octets in length, i.e non-existent. This is useful when the link is a point-to-point link, and the nodes at each end know the other's IP address. |
| 1:AD_1IP | The address field is unsigned and 1 octet in length. It contains the least significant octet of the IP address. |
| 2:AD_2IP | The address field is unsigned, big-endian and 2 octets in length. It contains the 2 least significant octets of the IP address. |
| 3:AD_3IP | The address field is unsigned, big-endian and 3 octets in length. It contains the 3 least significant octets of the IP address. |
| 4:AD_4IP | The address field is unsigned, big-endian and 4 octets in length. It contains the 4 least significant octets of the IP address. |
For all multi-octet address-types (i.e AD_2IP to AD_4IP), the address is transmitted in big-endian format, in the same manner as IP addresses in IP datagrams.
For address-types AD_1IP to AD_4IP, the broadcast address has all bits turned on (i.e all 1's).
The CRC field is two octets in length, and is calculated over the entire packet (except the CRC field itself) according to the ISO 3309 (HDLC) specification. The field is transmitted in big-endian format.
A suitable size for the link addresses must be chosen in any given link in order to distinguish between all nodes sharing that link.
No amateur radio callsigns are transmitted as part of IP transmission. This makes packets smaller, but may contravene amateur radio regulations in many countries. This may be handled by using regular broadcast packets with this information, as described earlier.
The largest omission is that of routing. DUAL performs no routing whatsoever. DUAL believes that the given link is a broadcast link, and all stations on the link can be reached. In many (if not all) situations, this is not the case. We believe that this problem can be solved via appropriate IP netmasks and routing protocols at the network level (i.e at IP).
In the design of DUAL, we believed it was possible to adapt the TCP/IP header compression scheme used in Compressed SLIP [Jac90]. This would reduce header overhead from 18+40 octets (AX.25, IP, TCP) to 5+5 bytes (DUAL, compressed TCP/IP). Note that this compression is specific to TCP packets; UDP packets cannot be compressed since there is no ongoing state to use.
The main limitation with the original TCP/IP header compression scheme is that it was designed for use over a point-to-point link, where the identity of the machine at the other end is known. We had to extend its semantics to cope with the broadcast, multi-point environment used by DUAL.
Figure 5 shows a typical (and minimum length) TCP/IP header. The header size is 40 bytes: 20 bytes of IP and 20 of TCP. All these fields serve a purpose and it's not possible to simply omit some in the name of efficiency.
However in a TCP connection typically tens or hundreds of packets are exchanged. About half of the per-packet information remains constant over the life of a connection, shown by the shaded fields in figure 5. So if the sender and receiver keep track of active connections and the receiver keeps a copy of the header from the last packet it saw from each connection, the sender gets a factor-of-two compression by sending only a small (around 8 bit) connection identifier together with the 20 bytes that change and letting the receiver fill in the 20 fixed bytes from the saved header. One can scavenge a few more bytes by sending changes to some field values, rather than the values themselves.
Consequently, the compressed header sent instead of a normal TCP/IP header is usually 4 or 5 octets in length, and gives the `differences' between the last TCP/IP header for the TCP connection and the current TCP/IP header. As well, a `connection number' is sent to the destination, to allow it to find the correct saved header information and to decompress the TCP/IP header. This results in the total header overhead typically being reduced from 58 to 10 octets, an 83% reduction in the packet header size. For a more detail discussion on IP compression, see [Jac90].
On a broadcast link, such as DUAL, the connection number in the compressed header is not sufficient to identify the TCP connection. DUAL saves both the connection number and the link source address in each state entry. When a packet has been received, the algorithm uses both of these to find the correct state entry required to uncompress the packet.
At the same time, the state table is stored as a Least Recently Used linked list. This improves searches through the list as the most recently used states will be found quickly. When a new TCP connection is opened, the state entry at the least recent end of the linked list is used to store the state of the connection's compression, and it is of course moved to the front of the list.
The original compression scheme used 8-bit connection numbers, but suggested that 16 numbers would be a good implementation maximum over a point-to-point link. In a broadcast environment, a station may have to deal with more than 16 compressed connections, especially if it is a packet router. Therefore, we have increased the implementation maximum from 16 to 256 connection numbers.
Another major alteration was a restriction of the compression scheme's behaviour. When two or packets for the same TCP connection are transmitted sequentially by the CSLIP sender, the connection number is removed from the compressed header. This information is vital in a broadcast environment, so DUAL transmits connection numbers in every compressed header, and the receiver rejects any packet without a connection number.
Figure 6 shows the format of a compressed TCP/IP packet (for both CSLIP and DUAL). There is a change mask that identifies which of the fields expected to change per-packet have changed, a connection number, so the receiver can locate the saved copy of the last packet for this TCP connection, the unmodified TCP checksum so the end-to-end data integrity check will still be valid, then for each bit set in the change mask, that amount the associated field changed. Optional fields, controlled by the mask, are enclosed in dashed lines in the figure.
The implementation modifies the existing SLIP/CSLIP [Rom88] implementation in FreeBSD 1.1, chosen because the source was available, the network stack was mature, and the authors had experience with it. The changes made primarily affected the packet format, in order to make DUAL into a multi-point protocol.
As DUAL is a Link Layer (or more strictly, a LLC layer), it was implemented as an `interface' in the network stack, which handles KISS [CK85] frames, a close relative of SLIP, to interface with KISS-mode packet radio hardware.
After some consideration of the existing code in the BSD Network Stack, we determined that there were existing pieces of code that could be shared by SLIP and DUAL, and also PPP, by suitable re-arrangement of the following source files: the actual SLIP framing code in net/if_sl.c, the TCP/IP header compression code in net/slcompress.c, and the HDLC checksum code in net/if_ppp.c.
The SLIP framing code was moved into a new file, net/if_slframe.c, with the remainder of SLIP left in net/if_sl.c. The HDLC checksum code was moved to net/hdlc_fcs.c, with PPP left untouched.
The TCP/IP header compression code in net/slcompress.c was already shared between SLIP and PPP, and we have not moved any code from this file, but we have substantially altered the code to make the scheme work as described above.
With the shared pieces of code separated, we adapted net/if_dual.c and net/if_dual.h from the SLIP interface code, in order to implement the DUAL protocol.
Figure 7 shows a block diagram of the DUAL input/output driver and the compression software.
The networking system calls a DUAL output driver with an IP packet to be sent over the serial line. Before passing the packet to the compressor (see figure 7), the output driver builds the DUAL header packet format. Then the compressor checks if the protocol is TCP. Non-TCP packets and uncompressible TCP packets (detailed in [Jac90]) are just marked as TYPE_IP and passed to the framer. Compressible TCP packet are looked up in an array of packet headers. If a matching connection is found, the incoming packet is compressed, the (uncompressed) packet header is copied into the array, and a packet of type COMPRESSED_TCP is sent to the framer. If it is not found, then it is sent as an UNCOMPRESSED_TCP packet, and added to the array of packet headers. An UNCOMPRESSED_TCP is identical to the original IP packet except that the IP protocol field is replaced with a connection number, an index into the array of saved packet headers. This is how the sender (re-)synchronizes the receiver when using compressed headers.
The framer is responsible for transmitting the packet data, type and boundary. The framer encapsulates the incoming packets in KISS [CK85] format, ready to be forwarded to the radio hardware for transmission on the radio channel. Since the compression is a differential coding, the framer must not re-order packets. It must also provide good error detection and, if connection numbers are compressed, must provide an error indication to the decompressor.
An incoming packet goes through the framer for CRC check; if it fails, the framer will discard the packet without notifying the upper layer. The upper layer protocol is responsible for error recovery, eg. the sending TCP will eventually time out when no ACK arrives. If the CRC checks does not fail, the framer passes the packet to the decompressor. The decompressor restores the TCP/IP headers if they have been compressed using the saved packet headers, and then passes the packet to the DUAL input driver to find out which upper layer protocol is waiting for the incoming packet.
DUAL provides a new format for efficient low speed data transmission, which allows the packet transmission to be tailored to the link environment used. For the transmission of TCP/IP packets, the header compression scheme used in Compressed SLIP has been altered to work in a broadcast, multi-point environment. Overall, there is an 83% decrease in header size when using DUAL to transmit TCP/IP packets, compared with TCP/IP transmission over AX.25. We have implemented a basic DUAL layer in the BSD Network Stack in FreeBSD. The implementation is robust and confirms our protocol design.
The Berkeley Unix implementation of DUAL for FreeBSD 1.1. is available in machine readable form via anonymous ftp from Internet host minnie.cs.adfa.edu.au (131.236.23.152), in the file /pub/Dual/dual.tar.gz This is a gzip Unix tar file. It must be ftped in binary mode. Also in that directory you can find a copy of the original technical report [MTB95].
The authors gratefully acknowledge support from ATERB grant N033/011 1992/93. They would also like to thank those members of the School of Computer Science and those local radio amateurs who assisted with comments and suggestions.