Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper covers the basics well, and at the end presents an impressive analysis of the performance of their architecture. Their architecture is relatively simple. Packets are encapsulated in a custom routing frame, and link estimation is performed using period beacon-ack pairs to estimate the probability of DATA-ACK success. CTS/RTS is disabled (this is typical, I believe,) probably to reduce protocol overhead. Each node either routes traffic to the internet if it is connected, or else forms a default route to a gateway to deliver traffic. The use of source routing everywhere is also notable; this is an approach that really began to be introduced with DSR, as they note, and seems to be gaining favor in ad-hoc networks. I think there are a couple of reasons for this: state is local to sending nodes, and so there is never any confusion about where the packet will go. This makes routing loops impossible, and furthermore eliminates recovery in the case where an intermediate node reboots and comes back up with uninitialized routing tables. This sort of local inconsistency can be very problematic for both link-state and distance vector algorithms.

They evaluate their solution along various axis, including node density and various properties of the topology; they also show which links are most important to the routing. One aspect that I thought was particularly interesting was multi-speed nature of the link, thus presenting implications at the network layer. As they point out, it may be more beneficial to take more hops at a higher bit rate then fewer hops at a lower one, and due to the spacing of the different speeds, link-layer losses of up to 50% may still be the "best" link. They are helped in their design by the fact that energy is not a concern; all the routers are plugged into the wall.