Monday, December 21, 2009

Beating the Multi-Hop Routing problem (or not)

Most of those familiar with wireless meshing are familiar with the multi-hop wireless problem. For those unfamiliar with the space, the problem is simple: A radio has a fixed maximum bandwidth (for 802.11g it's roughly 22Mbps of half-duplex real throughput). Any time a device needs to receive and forward data over the same radio, it must share this bandwidth between sending and receiving, meaning that after four or five radio hops there is precious little bandwidth left. (for the first hop, the bandwidth hit is roughly 50%, I haven't tested what happens after that, but one would expect the proportional degradation per hop gets less severe as the signal thins out) At any rate, the multi-hop problem is a major issue in a region-scale wireless network with sparse or distributed network resources, and since FabFi is going to be HUUUUGE, I set about some experiments to see how one might beat it.

The bandwidth halving over multiple hops is fundamentally a physics/hardware problem. A single radio cannot send and receive at the same time, and no two radios can talk on the same channel at the same time. Two radios can, however, talk at the same time on non-overlapping channels--theoretically--begging the question, if every device had two radios, would we be cool?

Sadly, not so much...

A little bench testing with four routers yields the following (I believe these numbers are full-duplex, so x2 accordingly for what you would expect the numbers to be...)
  • setup 1: Single-hop cabled , 24.3 Mbps
  • setup 2: Multi-hop cabled, 24.2 Mbps
  • setup 3: Single-hop wireless, (ch11) 11.4 Mbps
  • setup 4: Multi-hop Radio-cable-radio (close quarters, directed, ch 1., 11) 5.82 Mbps
  • setup 4b: Multi-hop Radio-cable-radio (close quarters, ch 1., 11) 5.81 Mbps
  • setup 5: Multi-hop Radio-cable. (ch 11) 11.5 Mbps
  • setup 6: multi-hop Radio-cable-radio (30', ch 1, 11) 10.8 Mbps
(same physical setup as above, but with different channel selections)
  • setup 6b: multi-hop Radio-cable-radio (30', ch 1, 6) 15.4 Mbps
  • setup 6c: multi-hop Radio-cable-radio (30', ch 1, 5) 12.2 Mbps
  • setup 6d: multi-hop Radio-cable-radio (30', ch 13, 9) 11.2 Mbps
  • setup 6e: multi-hop Radio-cable-radio (30', ch 1, 4) 6.54 Mbps
  • setup 6f: multi-hop Radio-cable-radio (30', ch 1, 3) 5.39 Mbps
  • setup 6g: multi-hop Radio-cable-radio (30', ch 1, 2) 6.98 Mbps

Background, for reference:
From the above, it is clear that a multi-radio 2.4GHz device is unlikely to have the desired effect of radio-radio hopping without bandwidth degradation unless the physical radios are fairly far apart. It is, however feasible to achieve bandwidth preserving multi-hop routing over the radio with two wireless devices separated over a wired LAN, suggesting that there might be a benefit to modifying the OLSR protocol and channel selection algorithms to take advantage of this situation when it arises in the wild.

As an aside, the above also suggests that in a crowded RF environment, spreading devices across all 13 wifi channels, using ch 1, 5, 9, and 13 is nearly as bandwidth-preserving than the traditional 1, 6, 11 configuration. Channels closer than four apart interfere with each other almost completely, even at a modest distance from each other.

Thursday, December 17, 2009

More Links, Magic Bandwidth.

This week, for the first time ever, I witnessed 20 simultaneous nodes running in Jalalabad. In the last week there have been two new links, and now multiple groups are working on adding links. Very cool. The link on the right is the newest one. Where is the water tower? It's not visible at all, but the connection works. H &M are definitely stretching the limit of what we thought would be reliable, but if it works, it works...

Even cooler is the network is starting to generate enough load that some of the network services we've put in place are starting to work their magic. JBad has a guaranteed 2Mbit full duplex sat connection. In practice, that means that download speeds max out at about 252KByte/sec (KBps), with occasional peaks above that value. In order to increase the effective bandwidth, we have a local cache that saves pieces of the internet that are commonly accessed and serves them back locally. For the first time last week, we saw the local internet traffic exceeding the uplink bandwidth enough that it showed on the traffic graphs (node tab on this page: fabfi.fablab.af/stats.php?). Eventually we hope to capture most of the real-time traffic inside the fabfi net...

Friday, December 4, 2009

See subject of last post

NewHameed and Rahmat have linked up two more Fabfis this week, with one going over 6km! They have been making excellent use of existing hardware to make many:one connections and use the routers more efficiently. Soon the water-tower won't be the only fabfi hub in Jalalabad...