Posts filed under 'Ph.D'
I’m sure that no-one has noticed that I’ve been fairly silent on the blogging front for a while. I took a three month break from the Ph.D to do some work for Cambridge Silicon Radio. The experience working on a real-world project was great and the project itself was both interesting and challenging.
I am however looking forward to getting back into the Ph.D work. I’ve still got a week or so before the Ph.D kicks back in so at the moment I’m doing some driver work for RuralLink - specifically getting MadWiFi working better on the CPE/AP devices.
I spent a week or so before the CSR work started looking into performance improvements for MadWiFi. After spending quite a bit of time with oprofile I found a couple of areas in the driver which were causing a large number of PCI transactions to take place unnecessarily. Now, on a laptop or desktop platform this didn’t really make much difference. On an already resource-starved platform such as the Soekris 4526 however, this was resulting in some pretty significant overhead. A couple of patches to MadWiFi later (a couple merged upstream already, one that’s a bit more of a hack specific to our needs) and we’re seeing some much nicer throughput numbers. Off the top of my head, we went from being able to bridge about 9-10 Mbit/s of traffic over wireless through the wired ethernet to about ~15 Mbit/s.
The other neat hack we did was to create a transparent wireless bridge by hacking the ad-hoc demo mode to use 4-address 802.11 frames. This could already be done in other modes, but we really like ad-hoc demo due to its utter simplicity - no associations, no beacons, nothing - just passing frames.
Right now we’re working on implementing our own rate control algorithm. We seem to run into far too many problems on our networks with rate control and Perry came up with a neat idea - as is his wont - so we’re running with it. At the same time we’re looking at using it as a chance to collect large amounts of performance data to give us some deeper knowledge as to what’s going on on our networks. Hopefully lots more info on that soon.
At some point in the (very) near future I need to start thinking about the Ph.D again - I’m starting to think that I should be putting more of a measurement focus into it, but I need to nail down a few ideas first. And maybe play a bit of Guitar Hero as well 
August 9th, 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
http://www.citeulike.org/user/scottr/article/740618
In this paper, we are presented with the argument that ad-hoc wireless networks are not well suited to the standard layered model of networks. While models such as OSI and TCP are suitable for wireline networks, the ever changing environmental factors present in ad-hoc wireless networks make strict layered approaches inefficient.
The paper goes on to categorise cross-layer approaches into one of two categories: evolutionary and revolutionary. Evolutionary approaches take an existing layered architecture and add cross-layer awareness to some or all of the components of the stack. The main focus is to maintain compatibility rather than maximise performance. Revolutionary approaches completely re-think the network architecture and make performance a primary concern, sacrificing compatibility with existing network architectures.
An overview of existing evolutionary approaches is given, and for several of the lower layers of the OSI stack, examples are given for their potential cross-layer interactions, showing that these interactions can increase performance. The discussion on revolutionary approaches focusses mainly on wireless sensor networks, which are inherently cross-layer aware, due to the fact that WSNs are application specific. These revolutionary approaches can lead to increases in performance, but also massive energy savings.
Finally, the paper cautions that revolutionary cross-layer approaches must be dealt with carefully, and that the designer should keep architecture in mind. Unchecked cross-layer design could lead to spaghetti architectures, leaving future improvements to the components in the system difficult to implement without unintended interactions.
This paper is a strong argument for the benefits of cross-layer design, especially in ad-hoc wireless networks. It still seems that most of the cross-layer research done so far (this paper was published May 2006) exists at the network layer, such as routing protocols making decisions based on physical layer properties, such as channel state. This leaves a large area of research virtually untouched, that is of how the MAC layer can be aware of lower layer conditions, such as bitrate, BER, modulation schemes, etc, as well as higher layer factors, such as adapting MAC behaviour based on transport layer information. Research into what information the MAC layer could provide other layers is also another interesting and open question.
August 4th, 2006
http://www.citeulike.org/user/scottr/article/526128
This paper presents a mesh network architecture and MAC protocol optimised for long-distance rural networks. Raman and Chebrolu expand on their previous work on SynRx and SynTx techniques, where with careful attention to the physical topology of the network, several radio interfaces on a node can transmit or receive at the same time without interferring with each other. That is, all interfaces on a node must be either transmitting or receiving, but not a mixture.
The 2P MAC protocol uses SynRx and SynTx by assuming point-to-point links between nodes that have multiple radio interfaces. There are several constraints put on the physical topology of the network to ensure correct operation of 2P. For example, the “mesh” must not contain loops with an odd number of edges. Also, we must pay attention to the angle between links to ensure that side-lobes have a minimal effect. Transmit power for each link is also constrained to ensure that links do not interfere with others. Even with all these constraints, the authors show that it is possible to create networks compatible with 2P. Whether or not it is always practical is something I am not yet convinced of.
Interestingly, 2P has been implemented using driver-level modifications to the Prism2 HostAP drivers. By using a combination of IBSS mode and broadcast frames, immediate ACKs are removed. This is a technique that I was going to use during development of the Atheros based MAC development framework. The authors also use the antenna diversity settings to remove CSMA/CA backoff. When an interface wishes to transmit, it sets it’s rx antenna to the connector that does not have an antenna connected to it. This way, it does not carrier sense the other interfaces transmitting and so does not back off.
The basic premise of 2P is that when a node is transmitting, all of the nodes that are connected to it are receiving. Once all of the interfaces have finished transmitting to their neighbours, the entire network swaps, and so all of the neighbours begin transmitting, and the node goes to receive mode. This requires communication between interfaces on a node, and has also been implemented in the driver.
Simulation results show that because all interfaces on a node can transmit at the same time, overall throughput is greatly increased over a CSMA/CA based network. Implementation results show that while the protocol does not live up to it’s simulation results, it is still on average better than CSMA/CA. The authors discuss the overheads involved in the implementation and the effect on the protocol, which is interesting as I had planned to argue during my research that development of MAC protocols requires more than just simulation to be effective, which this paper touches on.
August 4th, 2006
http://www.citeulike.org/user/scottr/article/692690
In this 2001 paper, Sharon and Altman describe a MAC protocol that exploits the capture phenomena in radio channels. The MAC is point-to-multipoint and uses polling techniques, however it uses the capture phenomena to overcome the fact that polling techniques perform poorly when only a small number of stations have data to transmit. When a base-station polls a station only to find that the station has no data to transmit back, that channel time is lost to protocol overhead. All stations must be polled however to ensure fairness of the medium - something that polling MACs are known for.
In this MAC, two radio channels are used. The first is for data and control frames being passed from the Base Station (BS) to mobile stations (Note that the paper refers to mobile stations throughout, however the authors state that they assume the stations are stationary when transmitting as the MAC relies on knowing the distance to the BS from the station). The second channel is for data and control frames being passed from stations to the BS. A circular list of stations present in the system is stored, and two separate circular lists are also stored - one contains stations that have frames to transmit, the other contains stations that do not have frames to transmit.
During its basic operation, a BS will send a control frame to the next active station giving it permission to transmit one frame’s worth of data. In the same control frame, the BS also queries a station in it’s inactive stations list. The active station will transmit its frame back to the BS and notify it whether it has more frames to transmit. If it does, the BS moves on to the next active station. If it does not, the BS moves the previously active station into the inactive list. When an inactive station is queried, if it does not have any data to transmit it will remain quiet, however if it does, it will transmit a “jam” signal at a low power. This is at the same time as the active station is transmitting it’s data frame. The capture phenomena allows the BS to correctly decode the signal from the active station while the inactive station is transmitting a jam signal. When the active station finishes sending its frame, if the BS detects a jam signal then it will add the inactive station to the active list.
This method allows the BS to poll inactive stations without stopping active stations from transmitting. The paper goes on to show that the MAC obtains better throughput, mean access delay and mean queueing delay when there are stations that are not transmitting than simple token passing does.
The paper is extremely interesting, as the MAC I have implemented in the last couple of months is a simple token passing MAC (with the idea that once we have a solid implementation we can use it as a base for improvements). This shows that with low-level access to the transmit hardware we can do interesting things at the MAC layer. However, the MAC presented in the paper requires two separate radio channels, and hence two separate radios - something that is very expensive to implement. So, it becomes a tradeoff between coming up with interesting theoretical solutions to problems, and coming up with realistic, implementable ones.
August 3rd, 2006
http://www.citeulike.org/user/scottr/article/761662
Iannone et al present a wireless mesh network architecture made up of off-the-shelf components which is self organising and makes the backbone network transparent to the clients - that is, clients from the mesh routers all appear on the same layer 2 network. The network is completely IPv6 based, and makes use of its auto-configuration features. Links between routers are made using 802.11a, and clients connect to the routers using 802.11b, separating the two logical networks physically.
The purpose of the paper is to show that cross-layer information can be used to increase performance. As a base case, the routing protocol uses a simple hop-count metric. It is shown that as the hop count increases, performance decreases. A simple cross-layer metric is introduced which finds a path with the highest bitrate. Use of the cross-layer aware routing protocol shows increases in flow performance.
While this paper is targetted at using cross-layer techniques in routing protocols, it helps to motivate the use of cross-layer techniques in general.
August 3rd, 2006
http://www.citeulike.org/user/scottr/article/782458
In this short paper, Defrawy et al propose a simple framework for cross-layer protocol design. Their argument is that by standardising the interfaces that layers of the protocol stack use to communicate with each other we can maintain the modularity of the stacks, while still benefitting from the use of cross-layer techniques.
A Cross Layer Server sits outside of the protocol stack. A Cross Layer Client is added to each of the layers in the stack and communicates with the server. Each client contains an adaptation module, which implements the logic to adapt the behaviour of the layer dependent on signals from the server. The layer state is abstracted and stored globally by the server, so that other layers can access it. Layer events are passed to the server, which notifies other interested layers, who then run their adaptation algorithm. By implementing the adaptation algorithm within the client, designers can leave the existing protocol layers almost untouched, while easily changing the way in which they react to the cross-layer information.
The protocol designer needs to specify a) the adaptation algorithm for certain layers, b) the events and their parameters and c) a priority policy for the server to use in the case of multiple events. The authors show how a cross-layer aware video transmission protocol can be implemented using their framework.
The paper also references several other papers which summarise the state of cross-layer techniques, so I will be hunting those down once I can get access to the full-text of the IEEE Communications Magazine.
August 2nd, 2006
http://www.citeulike.org/user/scottr/article/503372
This is an interesting paper, which is quite recent, and deals with the same kind of issues I am currently looking at. The main crux of the article is that in order to do MAC research we should be using an overlay approach - implementing the MAC in software on top of the existing 802.11 MAC - as it makes it possible to test the MACs in real world environments. The argument for the need for testing MACs in the real world is one that I would like to persue. They also argue that replacing the MAC layer is too costly, and so they present the overlay solution. The MAC they present using this technique allocates timeslots using a distributed algorithm, and increases the total throughput of the system. The paper also outlines some of the current problems with 802.11 in terms of unfairness, etc.
This sounds similar to what I want to do with the Atheros cards, although it does have differences. In this paper, they are essentially doing scheduling of writes to the NIC, but still using 802.11 for framing, addressing, etc. In my system, I would like to run an entirely separate MAC using broadcast 802.11 frames. Obviously this has quite a bit of overhead, but allows cheap deployment of the protocol, and allows us to (mostly) test it in a (mostly) real-world environment. The WAG cards provide us with a way to run the entire MAC on the hardware without 802.11 encapsulation, but that is a very expensive option. More to come on this later.
July 13th, 2006
What have I been up to lately? Well, I’ve been working on implementing a point-to-multipoint wireless MAC protocol. The interesting thing about it is that it was first designed in SDL, then using Dean’s sdl2cpp translator and the WAND Protocol Development Environment (WPDE), I’m able to get it going in actual hardware (using the WAG cards at this point). Eventually, I’ll write a wrapper so that we can deploy it using Atheros based wireless cards - although that’s going to take some hacking. Essentially the last couple of months has been designing the protocol, learning SDL, implementing the protocol in SDL, and then working with Dean to work his WPDE stuff into a useable state. At this point we’ve nearly got the WAG framework working with a simple point-to-point MAC, and once that’s going I’ll be able to get my point-to-multipoint MAC going.
The MAC is based around token-passing, which we hope will help to avoid the hidden-node problem, as it’s being designed with long-distance, rural networks in mind. There is very little overhead due to not having to use interframe spacing, etc. It should be good to see it going.
In the next six or so weeks I have to write a full proposal for my Ph.D, which will involve sorting out exactly what my research is going to be. At the moment it looks like I’ll be continuing to look at wireless MAC protocols, specifically how to deal with packet loss. For example, we would like to see whether it’s feasible to selectively acknowledge portions of a frame, etc, rather than having to re-transmit entire frames. Looking at modelling loss/bit-errors would be a part of this. During this, I will be attempting to argue that to effectively test MAC protocols we need to use real hardware, rather than just relying on simulation results. Hopefully I will be able to use the WAG environment to validate (or invalidate) simulation environments, and possibly come up with better simulation models. Things are still up in the air, and the next few weeks will involve a lot of literature search to try and narrow my focus a bit more.
July 13th, 2006
Previous Posts