The Stop-And-Wait ARQ Protocol

From JavierValcarce.Eu

There are two implementations of this protocol: the C# implementation is for the host and the C version is intended for a 8-bit microcontroller with very limited resources. It's written in fully portable C (C99) and works on AVR, PIC, 8051, etc with > 2K program memory. There is no need to use an RTOS but could be used in such environment. The performance of stop-and-wait protocol is poor but given the limited resources available at this devices is the most appropriate choice because is simpler and requires less memory.

Protocol Overview

Stop-An-Wait (also called the bit banging protocol) is the simplest ARQ protocol and hence the one with the poorest performance. The following figures summary the pathological scenarios that can occur and how the protocol addresses this problems. The transmitter (TX) and receiver (RX) have both an internal state, their FSMs are depicted below.

There are two types of frames: data frames and acks. The format of each frame is:

[0x00 -       CRC_LSB CRC_MSB] for ACK0   (size = 3           bytes)
[0x01 -       CRC_LSB CRC_MSB] for ACK1   (size = 3           bytes)

[0x02 PAYLOAD CRC_LSB CRC_MSB] for Frame0 (size = 3 + Payload bytes)
[0x03 PAYLOAD CRC_LSB CRC_MSB] for Frame1 (size = 3 + Payload bytes)

The CRC uses 16-bit (2 bytes, little-endian) standard polynomial CRC16=0x8005 (reciprocal is 0xA001), the size of payload is limited by the protocol MTU (Maximum Transfer Unit) which is defined by the constant ARQ_MTU (10 by default, 60 byte max.).

Framing

In order to recovery frame synchronization (to know where a frame starts and ends) the protocol use an algorithm called COBS (Consistent Overhead Byte Stuffing) described in Stuart Cheshire, Mary Baker, "Consistent Overhead Byte Stuffing", IEEE/ACM Transactions on Networking, Vol. 7, No. 2, April 1999.

The advantage of this codec over classic PPP-like byte-stuffing is that it introduces exactly 1 byte of overhead per 254 bytes of frame. This ensures that the channel capacity won't be wasted in case of pathological frames. In the worst case, all payload data are PPP escape sequences, which doubles the final frame size and therefore requires to double the buffer size wasting the scarce memory of small devices).

Link Initialization/Polling

The protocol is designed to periodically send empty data packets in case there is no data available for TX (polling). When the number of retransmission exceeds MAX_RETRIES, the event LinkDown is raised.

By other hand, there are a number of problems that must be addressed in a real implementation: what happens when an end-point reboot?, what happens if the transmitter doesn't receive the ack of the last frame sent and the receiver is turned off? what happens if the tx is disconnected from the original rx (rx1) and connect to another rx (rx2)?

Address correctly all this issues (from a theoretical point of view) would require a much complex connection-oriented protocol, that is, SYN frames, handshaking, ordered close of a connection, etc. I'm not keen to implement all this stuff, it would make the firmware much bigger. A simpler approach is used here with two additional rules:

• Rule 1. After a reboot, the TX always sends an empty data frame to sync the receiver's state.
• Rule 2. After a reboot, the first received frame is always accepted and is used to set the receiver state.

This two additional rules assures that no data packet is lost between a pair of tx/rx. A non acknowledged data frame after a turn off the receiver will remain on a retransmission cycle again and again until the receiver is turned on again, when this occurs the packet will be delivered correctly. Ok. Take into account this when writing your application protocol on top of this one.

C version for the uC

The protocol is written in fully portable C (C99) so it relays on some functions that must be provided by you and which are device dependent like send a character over the serial interface, test if there is a byte available in the rx buffer, get, set, clear timers, etc. With this abstract view of the the device the core protocol is device independent and can be used in AVRs, PICs, 8051, etc, with or without an RTOS.

For an AVR uC and using AVR-GCC toolchain, the computational requirements are aprox:

• 1800 bytes of program memory (compiled with -s option = optimize for size)
• 50 bytes of data memory

The retransmission timer value must be tuned accordingly with the MTU used, serial baud rate an uC performance. For a F_CPU > 4MHz, a MTU = 10 bytes and a serial port at 9600bps a retransmission timer of 50ms is adequate^[1].

The function arq_task() must be called at least when a byte arrives at serial interface or when the tx buffer is empty ot when the retransmission timer strikes, call it in the main loop is ok too. The protocol API is non-blocking, uses FSMs (Finite State Machines) to send/receive bytes over serial the interface an set flags to notify when a packet has been sent/received. The following program echoes all received packets:

int main(void)
{       
        setup();
        arq_init();
 
        while (1)
        {
                arq_task();
 
                if (!arq_rx_empty() && (len == 0)) { arq_recv_pkt(pkt, &len);          }
                if ( arq_tx_empty() && (len != 0)) { arq_send_pkt(pkt,  len); len = 0; }
 
                // Do other tasks ...
        }
        return 0;
}

C# version for the Host

The StopAndWait class (derived from LinkProtocol) is designed to operate with a Stream interface, which is an abstract view of a sequence of bytes. Therefore, the protocol can operate with any type of serial interface, a serial port, a FiniteQueue stream, a tcp socket (... and why would you want to use a stop and wait protocol over a yet reliable tcp channel?)

static void Main(string[] args)
{            
            Random rnd0 = new Random();
            SerialPort com0 = new SerialPort("com7", 9600);
            com0.Open();
            StopAndWait arq0 = new StopAndWait(com0.BaseStream, com0.BaseStream);
 
            byte[] txbuf = new byte[StopAndWait.MTU];
            byte[] rxbuf = new byte[StopAndWait.MTU];
            int rxlen;
            int txlen;
            bool equal;
 
            const int PktCount = 1000000;
 
            Console.WriteLine("Echo test. Tx/Rx {0} packets...", PktCount);
 
            for (int i = 0; i < PktCount; i++)
            {
                // fill pkt of random size with with random bytes
                rnd0.NextBytes(txbuf);
                txlen = rnd0.Next(1, StopAndWait.MTU + 1);
 
                while (arq0.SendPacket(txbuf, 0, /**/txlen) == 0) arq0.TryAgain();
                while (arq0.RecvPacket(rxbuf, 0, out rxlen) == 0) arq0.TryAgain();
 
                // ---------------------------------------------------------
                // check that the transmitted and received packets are equal
                equal = true;
                if (txlen != rxlen)
                    equal = false;
                else
                    for (int j = 0; j < txlen; j++)
                        if (txbuf[j] != rxbuf[j])
                            equal = false;
                // ---------------------------------------------------------
 
                if (!equal)
                    Console.WriteLine("ERROR. TX/RX packet are not equal");
                else
                    Console.Write("\r  Pkt={0,4} E[Rt]={1,5:f2} RxRate={2,8:f2}bps",
                        i, arq0.AvrReTxPerPacket, arq0.RxStats.AverageDataRate);
            }
}

Demo: Echo

In order to test the host-device connection, a test program and firmware (for AVR atmega168/328) are included in the zip file. Build TestArq.csproj C# project and the uC firmware (a Makefile and a AVR Studio project file are included), connect both end points thought a serial port link and check that it works:

The demo firmware echoes every received data packet (1000 packets) back to the host. The --ber is the simulated byte error probability of the channel, with a BER > 0.2 you will not be able to actually send anything at a reasonable rate.

Download

• StopAndWait.zip Includes the C# version for the host and the C version for 8-bit microcontrollers. The C version included is prepared to run on a AVR microcontroller (Arduino with ATmega168) without changes.

1. ↑ The objective of this ARQ protocol is not speed so set timer to a very conservative value to avoid unnecessary retransmissions