Implement ARQ for data transmission

[dl1com]

I propose to add a selective acknowledgement algorithm (see also https://en.wikipedia.org/wiki/Retransmission_(data_networks)). Some thoughts on this:

Receiver:

• The receiver of a dl_data frame generates a message of a new type (let's name it arq_response for now) upon receive of the fragment where the final_flag is set to indicate the missing fragments to the sender.
• The arq_response message contains the sequence number of the dl_data message and a bit field, which indicates the successfully received fragments to the sender. The size of the bit field is ceil(MAX_FRAGNR/8) bytes.
• When receiving a fragment, the receiver starts a timer. If this timer runs out without receiving another fragment of the message, the arq_response message is triggered. This handles the case where the last fragment is lost.

Sender:

• The sender has to preserve the fragmented message until every fragment was acknowledged or a timeout or retry-counter have been exceeded.
• On receive of a arq_responsemessage, the sender transmits the indicated fragments to the receiver and increases a retry counter for this frame
• If there is no missing fragment indicated, the sender moves on to the next frame in its tx buffer
• TODO What should happen if the sender never receives the arq_response after a given timeout?

It should be configurable whether ARQ mode is used, or for which type(s) of data it is used (e.g. UDP traffic vs. TCP traffic).

Possible optimizations (later work):

• Downlink data: The BS scheduler could assign a UL slot to a client when expecting to receive an arq_response from it.
• Uplink data: When requesting missing fragments from a client, the BS scheduler could assign a UL slot automatically to the client.

[lukasostendorf]

I started to implement an ARQ scheme based on the selective repeat algorithm. I think selective repeat ARQ with a sender window will give us a better throughput. The idea of waiting until one frame is received and requesting retransmission of all missing fragments on a frame per frame basis gives us high waiting times especially if the number of fragments per frame is low.

Working branch: https://github.com/HAMNET-Access-Protocol/HNAP4PlutoSDR/tree/arq_scheme The following has been implemented:

• I had to restructure the dl_data and ul_data headers. They have to contain a flag whether ARQ mode shall be used. Otherwise we cannot achieve the parallel usage of an acknowledged mode (AM) and unacknowledged mode (UM) on a per frame basis. This is highly desired in order to better serve UDP and TCP applications.
• A new message dl_data_ack and ul_data_ack is introduced. They are 16bits long, contain the sequence and fragnr that is acknowledged. There is space for an ACK_type flag. This allows us to send ACK and NAK messages. The latter is not implemented yet, could be a further enhancement to reduce the number of ack transmissions. Module: mac_messages
• The sender uses a send window for the AM mode. It can send up to ARQ_WINDOW_LEN fragments and then has to wait till the last fragment in the window is acked. There is a configurable timer calculated in number of subframes for each fragment. If no ack is received by that time, the fragment is retransmitted. Module: mac_fragmenter
• The receiver has a large receive window for the AM mode. For every received fragment, it puts the data to its window buffer. Then the receiver checks whether all fragments of a frame are present and releases the frame in that case. Module: mac_reassembler_am
• We support parallel usage of the acknowledged mode and the unacknowledged mode. The TAP listener will inspect each ethernet frame that is received on whether it is an IPv4-TCP packet. ARQ is automatically activated for these. Module: mac_bs and mac_ue

Open questions

Shall we include a retransmission limit at the sender side? The difficulty with this is how can the receiver notice that the sender "gave up" to finish the transmission of a certain sequence. The current implementation expects that the sender window is small enough to avoid any sequence numbering ambiguities and that the sender retries transmissions until everything is received. If the first assumption is not valid anymore, this leads to partially received frames in the rx buffer, that are never released and therefore might be mixed up with later received frames.

[dl1com]

Shall we include a retransmission limit at the sender side? The difficulty with this is how can the receiver notice that the sender "gave up" to finish the transmission of a certain sequence. The current implementation expects that the sender window is small enough to avoid any sequence numbering ambiguities and that the sender retries transmissions until everything is received. If the first assumption is not valid anymore, this leads to partially received frames in the rx buffer, that are never released and therefore might be mixed up with later received frames.

@hgn Any comments/experiences on this? A short search on this topic brought up this paper: https://onlinelibrary.wiley.com/doi/pdf/10.1002/ecja.10181 (I don't have access to it, though).

@lukasostendorf Is packet ordering still maintained in AM? From what I see in the code, all fragments of a frame have to be transmitted successfully before sending the fragments of the next frame, is this correct?