Archive for April, 2007
With libtrace 3.0 we included an API for extracting wireless metadata from packets. So for example, you can call trace_get_wireless_signal_strength_dbm() on a libtrace packet and get it’s absolute signal strength. This is done by decoding the Radiotap monitoring header if present. This is all fine for physical layer attributes, such as signal and noise levels, but the abstraction starts to get fuzzy when it comes to link-layer specific stuff. For example, libtrace 3.0 released with trace_get_wireless_fcs() which extracted the 802.11 FCS from the Radiotap header (even though this was a non-standard field and has since been removed). The problem is, trace_get_wireless_* shouldn’t be specific to certain MAC layer protocols. What if a CRC-16 is used instead of a CRC-32? trace_get_wireless_fcs() has since been removed, but the point also applies to some of the other functions.
So some of the functions as they exist now extract physical layer attributes, and others extract MAC layer attributes. Since libtrace was released, the Radiotap standard has been updated to include a couple of extra fields, such as the number of retries a packet had. Should a new accessor be added to libtrace to extract this? I’d say no, even though it’s a very interesting piece of data. Keep the trace_get_wireless_* functions as generic ways to get physical layer attributes of wireless frames. Let the user decode the Radiotap header in full if they want the 802.11 specific stuff.
Turns out I’m one of those users, so I’ve created a stand-alone Radiotap decoder in C which can extract all the Radiotap fields. If a new Radiotap field is added that describes an interesting physical layer attribute, then maybe an accessor can be added to libtrace for it, but for MAC layer specific fields a stand-alone Radiotap decoder should be used. This should hopefully keep libtrace as generic as possible.
Download version 0.1 of my C Radiotap decoder if you’re interested. Maybe I’ll get around to uploading it to Google Code Hosting at some point in the future.
April 25th, 2007
After spending most of last week manually validating the packet matcher I’ve decided that it’s at a pretty good state. I’ve settled (for now at least) on calculating the hamming-distance over 128 bits from various parts of TCP, IPv4 and 802.11MAC headers. Any frames that are transmitted and received within a certain time period and have a hamming-distance of 10 or less are marked as matches. This appears to work “quite well”, but I’ll need to come up with some hard numbers if I’m going to make any arguments based on it.
After convincing myself that the packet matcher was in a good state, I started to look at packet errors. On Monday, I took several traces. Each trace consisted of a 10 minute bi-directional TCP iperf between two nodes which were placed about 4 meters apart in the lab. One acted as an AP and the other acted as a station. I took a separate trace for each of the 802.11b rates, 1, 2, 5.5 and 11 Mbits. I did this so I could look at how different encodings affect error patterns within the packet. I’ll take more traces later with 802.11g and a rates.
Interestingly the error rates were very asymmetric. From the station to the AP, each trace showed a Packet Error Rate (PER) of > 10%. However, from the AP to the station the PER was ~1%. This suggests a hidden terminal which is surprising given that the nodes are only approximately 4 meters apart. Also, the PER decreased as the rate increased, which was surprising.
Over the different rates, the errors patterns within packets were very distinct. In the 1 and 2 Mbit traces (DBPSK and DQPSK), errors within packets were highly clustered, however in the 5.5 and 11 Mbit traces (CCK) the errors were more “spread out”.
Another interesting point is that although the PER decreased as the bitrate increased, the rate of errors within each packet increased. So, at higher rates we had less packets with errors, but the packets were more corrupted.
My next objective is to come up with some statistical models of these bit errors so that they can be applied in simulation. I’d also like to get some “proper” traces from real-world links to work on. Hopefully I’ll get some graphs up to illustrate this data within the next few days.
April 25th, 2007
Over the last few weeks I’ve been looking at characterising errors on wireless links. Most of the existing literature deals with modelling packet errors, e.g. defining the probability of a packet failing it’s CRC. Other literature talks about characterising errors within packets using an active approach - injecting known packets into a link and analysing the packets at the receiver.
I’m interested in developing new MAC protocols that can deal with packet errors more efficiently than just using simple ARQ methods. For example, we might want to adapt to varying levels of loss by applying different error-coding to the link. 802.11a already uses a convolutional encoder, but the coding rates are preset and do not vary according to the link quality.
Of course, there are plenty more possible approaches, so I’d like to develop a better error model for use in simulation so that we can test the effectiveness of new protocols. Currently most simulators simply drop random packets (generally uniformly, however the literature suggests a two-state Markov model might be more appropriate). However, to develop protocols that can deal with errors in frames, we need a model of the actual symbol errors within received frames - it is not enough to know that a frame was received in error, we must be able to model where those errors occured within the frame.
Along those lines, I’ve developed a couple of tools to help with building such a model. The first used an active approach, injecting raw 802.11 frames onto the link with known content. The frames included a FEC-protected header which included information such as a sequence number and the address of the sending station. These frames are then analysed for errors on receive and stats are recorded about packet loss and bit-error rate. This approach gives us some good information and is very reproducible, but has some drawbacks. Firstly, it does not depict an accurate view of “normal” network traffic. Secondly, it introduces a high amount of measurement traffic to the link and so cannot be used on an existing network.
The second tool uses a passive approach. We capture all frames from stations that we are interested in and then run the tool to match transmitted packets from one station to the received versions at other stations. This allows us to get error statistics from “real-world” network traffic. This approach requires a packet matching algorithm to match the transmitted packets to received packets which becomes more difficult as packets get more corrupted. Initially I matched only on the 802.11 MAC sequence number field, which was a good start. However, as soon as the MAC sequence field becomes corrupt we cannot match the packet. To improve the matching algorithm, I decided to examine several fields, such as the MAC sequence number, but also the IP ID, TCP sequence/ack, etc. Calculating a hamming-distance over these 128 bits and using a threshold of 5 bits in error resulted in more packets matched, but also introduced many false positives when non-TCP packets were examined. Unfortunately we cannot filter received packets by looking at their contents because the contents might be in error. This method is also prone to error when TCP and IP options are used as we are comparing a predetermined offset (we can’t just look at the TCP or IP header length, as it might be in error).
There is another method that I am investigating at the moment which looks promising. It is based on calculating the entropy of each bit in a frame and using this as a basis for packet matching. However, this leaves me with a few decisions to make. This part of the research was never planned to be this long, and if I continue it will take much longer, especially since I would still need to come up with statistical models once the packet matching algorithm is complete. However, the research is interesting and as far as I am aware it is fairly novel, so maybe it is worth continuing.
My 6-monthly progress report meeting is coming up soon, so I will take the next few days to prepare for that and have a really good think about which direction to take from here. It might be the case that I leave this for now and persue the protocol development side of things and come back to the more analytical side later.
Funnily enough, the process of writing this has left me with a few new ideas. I think I will try to implement a couple and see if I can get some numbers on the accuracy of each method.
April 17th, 2007
I’ve moved the python-radiotap module into a Google Code hosting project, mainly because I wanted to play with the service and python-radiotap seemed like a good reason to do so.
The project can be found at http://code.google.com/p/python-radiotap/
Enjoy.
April 14th, 2007