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
I was playing with setting up bind for my local network at home yesterday and forgot a semi-colon at the end of the localdomain zone. Of course, I’d removed localhost and mugen (the name of the machine I was using) from /etc/hosts so that I could test bind. Restart bind, ping mugen, fail. Oh well… sudo vim /etc/bind/named.conf… sudo can’t look up mugen using gethostbyname(). Shit. No sudo for me. No root user either. Eventually fixed by connecting a monitor and keyboard and starting in single user mode.
Moral of the story? Don’t screw up your resolver if you like having sudo.
March 1st, 2007
Here’s a little bit of code I wrote recently to parse Radiotap headers in Python. It’s pretty simple, you get two methods, get_length(buf) and parse(buf).
get_length(buf) takes a string holding a radiotap header and returns the recorded length of the radiotap header. Use this method to determine where the next protocol header starts in your buffer.
parse(buf) takes the same string and returns a dictionary mapping the RTAP_* constants defined in the radiotap module to the values recorded in the radiotap header. This dictionary will only contain the keys that are present in the radiotap header, so you can use things like has_key(radiotap.RTAP_ANTENNA) to see if the radiotap header contained antenna information.
Just note that all values are passed back as they are read, so they will all be little-endian, as this is what Radiotap is encoded in.
radiotap parser for python.
February 19th, 2007
Go check out FON. What a cool idea. Basically if you share your WiFi, you’ll get free access to other Fonero’s (members of the FON community) WiFi. You can either buy a FON WiFi “social” router straight from their website, or if you’ve got a compatible router (such as the Linksys WRT54G) you can download a customised version of OpenWRT and roll your own FON AP.
The APs broadcast two ESSID’s, one for your private WiFi network, and another that others can connect to after authenticating as part of the FON community. One of the really cool things about it is that you’ve got different types of Fonero. For example, a “Linus” will give away free WiFi to other Foneros, and in return gets free roaming to other FON APs. An “Alien” is someone who isn’t part of the FON community, but they can still use the FON network by buying a day pass for 3 euros. Finally, a “Bill” can forego the free roaming side of things and instead opt for a 50% cut of the money that Aliens pay to access the network through their AP.
FON’s got some pretty major investment partners too. They’ve partnered with Skype to launch a WiFi handset that will allow free Skype calls from FON APs. Google’s in as well, although it’s not clear what they are offering, besides money. Google does run some fairly large WiFi networks IIRC, so it’s possible those will turn into FON AP’s as well.
Of course, there’s the obligatory Web 2.0 mash-up, where you can bring up a Google Maps interface and find FON APs around the globe. I had a quick look and there don’t seem to be any in Oceania at all.
Unfortunately I can’t really see the relevance of this in a place like Hamilton. Free WiFi would work in built-up cities that consist of nothing but high-rise apartments, but who’s going to want to sit outside my house in Hamilton East and use my FON AP? It’s not like there’s a nice cafe close enough to sit and swill coffee while you surf. Most New Zealand towns just don’t have the population density to support it. Then again, that might be a good thing. Open up a FON AP, watch as no one uses your monthly data allowance and then get access to free FON points around the world. Now all I need to do is travel. At least I know I’ll be able to get WiFi when I next visit Muscat, Oman.
Hmm…
February 1st, 2007
The best thing about the OpenMoko platform is the fact that it’s open. Don’t like something about your phone? Well, change it! It also means that someone can have an idea for a feature and see it come to fruition very quickly. As well as that, we can integrate right into the phone’s UI and core functionality, rather than being restricted to being a separate Java (or whatever) applet.
So I was thinking about some of the things I’d like my phone to do. One of those things would be timed profile activation, but with a twist. You’ve got a smartphone, so it syncs with iCal, Evolution, Exchange, whatever, so it knows when your meetings/lectures/appointments are already. So why not automatically switch the phone to it’s “meeting” profile when you’re in a meeting? You’re not explicitly telling the phone to go silent from 3-4pm, it just “knows” that when you’re in a meeting (which you have with Bob today at 3, by the way - would you like me to send him an SMS reminder?) you’d like it to be quiet. Wouldn’t that be nice. Maybe modern smartphones already do this… who knows.
Location-based profile activation via GPS came to mind as well, but without coverage indoors and GPS’s relatively low fix resolution it might not be completely feasible. You could of course say “When I’m at work do this, and when I’m at home do that”, but you wouldn’t be able to say, “When I’m in the tearoom do something else”.
I’m sure there are plenty of other interesting things that could be done. I think I need to go find something to do or I’m going to be up all night thinking about it 
January 30th, 2007
… but I’ve found someone else. It was a brief romance, based mainly on that special kind of geek lust. The promise of something totally revolutionary, a wake up call for the handset industry busy basking in it’s own mediocrity. And, it was shiny. But as the Reality Distortion Field wore off, and we came to find out more about you, things started to look grim. The killer was the closed ecosystem.
Enter OpenMoko. Yes, it’s “old news”, and mattb blogged about it a few days ago, but I only became aware of it today, and boy did it hit that last nail into iPhone’s coffin (well, for me at least).
The Neo1973 lacks some of the nicer features of the iPhone, such as WiFi and built-in storage. However, WiFi is being worked on for a future release, and given the micro-SD slot, storage shouldn’t be an issue (plus, it’s upgradeable). It lacks a camera, but to be honest, I don’t care. The Neo1973 also lacks decent mobile data support with GPRS. Then again, iPhone isn’t 3G either. Both phones are quad-band GSM.
But even with all these “lacking” features, the Neo1973 has some really nice things that iPhone doesn’t. GPS, for instance. It also sports a very nice sounding 2.8″ TFT screen at 640×480 pixels compared to iPhone’s bigger but lower resolution screen (3.5″ at 320×480). That’s a hell of a resolution for a 2.8″ screen. The Neo1973 will also be carrier neutral and be sold directly from the manufacturer from their website, with worldwide shipping.
And the kicker of course is that it runs Linux and the whole stack is open. I like the fact that developers (well, anyone really) will be able to buy one before public release, as this will ensure that there are some really good apps available when it does come out. I really really want one, but I’m not sure I want to buy a smartphone without WiFi. I think I’ll wait for version 2 (developer release in September ‘07 according to the current timeline) to see if it gets WiFi and better mobile data. If it does, I’ll be all over it. Until then, I’ll continue to live with my trusty three-year-old Nokia.
January 30th, 2007
… on an apple bluetooth keyboard. Well, that didn’t take long, did it
And taking the Logitech back to Dick Smith was a lot easier than I expected. I figured saying “This doesn’t work with my Mac” wouldn’t make me any friends, especially as it turns out the box says “System Requirements: Windows XP”, but the lady was very nice, and didn’t even look in the box to see if everything was in order. Big ups to DSE for that one.
January 30th, 2007
Oh yeah, so we’re like the first country to see the sun, which means we’re the first to get Vista! Woo!
I just went over to Ascent to check something out before hitting the sack, and was greeted with a nice big graphic proclaiming Vista’s arrival with what appears to be Vista’s slogan, at least in NZ…
“The ‘Wow’ Starts Now!”
…
Wow.
January 30th, 2007
So I went out and got myself a Bluetooth keyboard and mouse today, as my shiny new MacBook Pro has Bluetooth and I want to use it in lid-closed mode at home. Plus, you know, it’s wireless.
I should point out that in my quest to find a wireless setup, I specifically wanted Bluetooth, as I didn’t want to have to use the USB dongle that comes with most (non-BT) wireless combos. Turns out Bluetooth isn’t as wide-spread as I hoped it would be and most setups use these proprietary wireless dongles. Anyhow, I found a very nice BT combo in the MX5000 Cordless Desktop, which comes with a MX1000 Laser mouse and MX5000 keyboard. The package also includes a USB BT dongle for people without built-in BT.
The MX1000 Laser mouse that comes in the combo is superb, and it was picked up by OS X immediately. Much, much nicer than using the built-in trackpad for extended periods of time, and certainly nicer than my several year old USB mouse I was using.
The MX5000 keyboard however, is a completely different story. The keyboard itself is very nice, and paired with OS X pretty much just as easily as the mouse did. That’s where the fun stopped though. Upon pairing with the device, OS X detected the new keyboard and tried to ascertain it’s layout by asking me to press the key directly to the right of the left-shift key. So I did. And nothing happened.
Hrm. So the alpha keys aren’t working - but the volume control, power button, etc, work. Ugh. Googling presented me with several blog posts and forum threads of people complaining that their new MX5000 wasn’t working, in exactly the same way as I have described. Gutted. Really should have looked that up before hand, but it’s Bluetooth, right? Thats why I avoided the combos with proprietary wireless dongles, cause they likely woulnd’t have Mac drivers.
So I take a look at the big “Read Me First” packaging insert and see that by default it’s paired with the included dongle and you have to install the (XP only) software first, before you can use it with built-in BT (It uses some “Secure Connect” thing to stop people snooping on your keypresses, which is odd, as BT already has encryption). OK, I grab my XP box thinking that I’ll unlock it after installing the drivers and I’ll be able to use it fine with my Mac. After an incredibly painful set of drivers and application installs, the keyboard worked with XP (It even replaced XP’s built-in BT stack). Unfortunately there was no obvious way to turn off the Secure Connect stuff. I assume that by replacing XP’s BT stack it implements it now anyway. I don’t have an XP box with built-in BT to see if it will connect straight away, so that’s out of the question.
I really don’t want to take this keyboard back (mainly cause I like the mouse so much and I can’t seem to find it separately), so I try plugging the BT dongle into my Mac and hey presto, the keyboard works. It doesn’t integrate with the Mac’s BT interfaces, I assume the dongle just presents a standard looking USB keyboard.
But that’s not cool - I’ve got built-in BT but my BT keyboard doesn’t work with it. I really don’t want to have to screw with this dongle thing every time I get home. I just want it to work…
So I remember looking through the developer tools included with OS X and seeing a BT packet sniffer. I unplug the BT dongle and unpair the mouse. Start sniffing, pair the keyboard with built-in BT, and start pressing some keys. I can see “HID Interrupts” being generated, and the keycodes they produce. It seems as though the keys are working and are producing consistent key-codes, but OS X doesn’t know how to interpret them. Interesting.
So, the next step is to figure out how to get OS X to remap those keycodes. I’ve spent a couple of hours trawling through the IOKit documentation (kernel API for developing drivers), the HID docs, the BT docs, etc, but nothing has stood out. It seems I’m looking at it from much too low - I shouldn’t need to write a driver for the damn thing!
I’m sure I’ve seen something in Linux that would let you sit on a terminal and view keycodes and their mappings as codes are generated. Something like that in OS X would be nice - I’m sure it exists, but I’m still pretty much an OS X n00b. Once that’s found and I can be sure that the keypresses are making their way up the stack (all I can see now are BT packets and HID interrupts caused by them), then a way to remap keycodes is needed. Easy!
*sigh* Of course, I could just take it back tomorrow and buy an Apple keyboard instead. Writing all this out has pissed me off so much that it’s pretty tempting. We’ll see what happens.
January 30th, 2007
Next Posts
Previous Posts