Guest post - One protocol's trash is another protocol's treasure - Decoding with the dropped packets of the 802.11g networks
Foreword
In this post we invited Juan Cabrera to present the work he did as part of his paper “Taking the Trash Back…” which got accepted for European Wireless 2017.
The research investigated how broken packets (invalid CRC check), which in today’s Wi-Fi networks would be dropped, can be utilized by exploiting erasure coding (e.g. Random Linear Network Coding). It revolves around a packet recovery technique called PRAC and how a modification to the PRAC technique can significantly increase it’s efficiency.
Being able to utilize broken packets in todays Wi-Fi networks could yield significant performance improvements and looks like promising technique to squeeze even more performance out of our wireless networks.
What does a packet loss mean? Packet losses observed at higher layers of the IEEE 802.11 protocol stacks are produced in part by data packets dropped by the network interfaces at lower layers. One of the reasons behind it is the presence of errors during wireless transmissions that could not be recovered with standard channel codes, i.e., the channel code tried to correct but mapped to an erroneous message. Unsuccessful error corrections are usually detected at the data link layer, and as a consequence, these packets are dropped, and there we have a loss!. However, a question arises; are these packets completely useless as the data link layer wants us to believe? actually not.
These dropped packets can contain useful information, which could be used to recover the original message. In the literature, there are techniques that exploit the content of these partial packets to extract the original information. Among these techniques, there is one that is particularly interesting for us. In a paper written by Angelopoulos, Chandrakasan and Professor Medard, they proposed a partial packet recovery technique called PRAC (Packetized Rateless Algebraic Consistency). In the publication, they show that if the payloads of the partial packets are coded data from a network coded stream, it is possible to exploit this knowledge to decode a generation (set of packets) of g packets after receiving g+1 packets (partial or correct). Since nothing is for free, the correction comes at the cost of additional processing that can potentially increase the decoding time by orders of magnitude in the event of errors. The reason is that erroneous symbols of the data packets have to be brute-forced until the errors are corrected. Therefore, more errors in the transmissions translates to a significant and non-practical increment of the decoding time.
In this blog entry, we want to discuss a recently accepted publication for European Wireless 2017 where we proposed a modification to the PRAC technique that can reduce the decoding time by an order of magnitude or more.
But first, how broken are the broken packets?
First, we asked ourselves some questions. In IEEE 802.11 networks, how broken are the broken packets (i.e., partial packets dropped at the data link layer)? how many broken packets do we receive under really bad RSSI conditions? and how do broken packets look on average, i.e., where are the bits flipped?
To investigate this, we deployed a simple measurement setup. we used a Raspberry Pi and a laptop connected, with the protocol IEEE 802.11g, to a Wi-Fi access point model with the free HyperWRT-based firmware Tomato. The laptop had two wireless interfaces, one connected to the access point, and the second one configured in monitor mode. The interface in monitor mode is necessary to capture and store, for a future inspection, the packets that failed the CRC at the MAC layer. Without this configuration, the broken packets would be dropped at the network card. We wrote and ran a Python script on the Raspberry Pi to constantly send UDP packets to the laptop connected in the same network. This script also logs-in through SSH into the Wi-Fi access point every five minutes and changes its transmission rate. The used protocol supports the data rates 6,9,12,..,48,54 Mbps. The payload of the UDP packets consisted of 10,000 zero bits (i.e. 1250 bytes a value close to the MTU size). To capture the packets with the wireless interface at the laptop, we used Tshark, the terminal-based version of Wireshark (1). We positioned the laptop as far as possible without loosing connection to the Wi-Fi access point and without line of sight in order to increase the number of errors in the transmissions.
What did we observe?
So, how do the broken packet look like? like this:
In the figure, we computed the probability for each individual bit of the payload to be flipped given that a packet was broken. We inspected the payload of all the received broken packets. For all broken packets sent at a specific data rate, we counted the number of times that each bit of the payload was flipped. Then, we divided this number by the total number of captured broken packets at that data rate. An interesting aspect of our results is that not all bits in the payload are equally likely to be flipped in a received broken packet. The initial bits of the payload are less likely to present errors than the bits located anywhere else in the payload. This means that, for a broken packet, it is less likely to find errors at the beginning of the payload.
To observe how many broken packets were received for the different data rates, and how broken were these packets we counted how many broken packets were received and divided this number by the total number of received packets. This is shown with the solid line in the figure below. As it was intuitively expected, at higher data rates, the number of received broken packets increased. For instance, at 54 Mbps, 46% of the received packets were broken, while at 6 Mbps only 5% of the received packets had errors in the CRC. Furthermore, we could also observe that at higher data rates, the broken packets had less flipped bits on average on their payload. Summarizing, at higher data rates, we received more broken packets, but they were, on average, less broken. For instance, at the maximum transmission rate, only 1% of the bits were flipped, while at 6 Mbps 15% of the bits were erroneous. This is represented with a red line in the figure below.
Exploiting the characteristics of the errors in the broken packets shown in these results could have a huge impact in the number of required transmissions over the network. For example, if we could correct, at 54 Mbps, all the broken packets, then we would reduce almost by half the number of required packet transmissions at the highest data rate.
The DA-PRAC technique
A disadvantage of the PRAC algorithm in practical implementations is the correction process. Due to the brute-force nature of the algorithm, the decoding times are high for a high number of errors. Our proposed algorithm, on the other hand, reduces the decoding time of the standard PRAC technique by introducing a CRC code in the original data packets (making PRAC Data Aware, therefore DA-PRAC).
DA-PRAC encoding process:
Before encoding with Random Linear Network Coding (RLNC) g original data packets (i.e., the generation size), the encoder appends a CRC code to each packet. The CRC is computed over the data of the packet. Then, the remaining of the encoding process is the traditional RLNC scheme, i.e., the data packets are multiplied by encoding vectors to produce linear combinations. The coded packets, denoted as mi, could be sent through a channel that flips some of the bits. The destination node receives the packets mi*, which can contain errors, i.e., flipped bits.
Description of the encoding method of the DA-PRAC technique
When the DA-PRAC decoder receives a set of g+1 correct and erroneous coded packets, it can start the error detection process. This process, consists of decoding the data packets several times using all the possible combinations of g packets out of the received g+1 packets. We refer to these decoded packets as predecoded packets, and we denote them as \(p^{12}_1,p^{12}_2,...,p^{23}_2\). The packet \(p^{xy}_i\) is the predecoded packet \(i\) decoded using the combination of received coded packets \(m^*_x\) and \(m^*_y\) with \(x\neq y\). The locations of the errors can be detected by finding differences when comparing, symbol wise, all the predecoded packets. If the symbols in a specific location in all \(p^{xy}_i\) with \(i\) fixed are equal, then the decoder knows that there are no errors in that location in any of the received coded packets. Otherwise, the differences point to the errors locations.
PRAC’s decoding algorithm: error detection
Finally, to correct the data, the DA-PRAC decoder permutes the symbols of the predecoded packets. The decoder, chooses randomly a set of packets pxyi with x and y fixed. For all the errors locations, it changes the symbols of the chosen packet with the symbol at the same location of the other predecoded packets. For every permutation, it recalculates the inner CRC until it is correct. Once this value is correct, the decoder has a correctly decoded data packet.
PRAC’s decoding algorithm: error correction
Summary and possible applications
The DA-PRAC technique can exploit the addition to the packets of an extra CRC before applying network coding to decode data with erroneous packets while reducing the complexity of other partial packets recovery techniques such as PRAC. The applications of this technique can be beneficial, for example, in live video streaming in multicast scenarios. In such an application, a receiver located in a bad spot respective to the sender will receive several broken packets. It could happen that, even with the redundancy injected to the network by the encoder, this receiver could not get enough correct packets to decode. If this happens the receiver would drop video frames. On the other hand, at the cost of some computational power, it could try to decode the generation using the received broken packets.
(1) We offer access to the aforementioned scripts and CLI commands used to set up the testbed in a Jupyter Notebook available here