Mesh Networking on Wifi cards?

February 1, 2011 6:54 PM

GeekFilter: Is it infeasible to wirelessly mesh/ad hoc network computers together a la MIT's Roofnet using integrated/inexpensive wireless cards instead of dedicated routers?

Lately, I've been thinking about mesh networking a bit due to the recent situation in Egypt, as well as talk from some friends at a college campus that's being a bit more restrictive lately with the network (understandable, as it is the school's service, and they're in the business of providing basic accommodations to dormers, not giving them a darknet). It's effectively impossible to share files across the network, and the bandwidth is very slow to the internet, similar to dial-up at peak hours, meaning people transfer large files via USB sticks and DVD burns (not saying students have a right to trade all files, but there are legitimate uses like collaborating on multimedia-intense projects).

As a result, I've been curious about user-created mesh networks and started googling around about mesh networking. There seem to be a lot of programs that run on the OpenWRT firmware, including some that require little to no configuration, and MIT has documented that they've achieved decent results (~DSL speeds) via their Roofnet project. What I can't seem to find a clear answer on is if it's feasible to create a low-to-zero configuration mesh with 802.11a/b/g/n cards, which are much cheaper and vastly outnumber routers in terms of ownership, meaning there would be many small nodes, likely overlapping well with good user density (say between rooms in a dorm, or in adjacent cubicles, or at a meeting, etc). Yes, running a mesh network complete with routing via a computer-controlled card would consume resources, but this is an era where even budget computers have multiple cores, while routers with 200mhz processors and 8MB of ram manage this trick. Is there something inherently limited about the cards? Are they harder to code for than routers? Too weak in terms of processing power/transmission?

It just seems like we have a lot of potential bandwidth lying fallow. It could be used for things like neighborhood P2P networks, or communications in times of crisis or technical difficulties.

I won't be seriously disappointed if I find out it's impossible. I just want to know why it hasn't happened.

posted by mccarty.tim to technology (6 answers total)

I don't see why it would be impossible. The computers could run router software that acts ike a router. Windows does this with ICS and RRAS, but without WPS-like features.
posted by damn dirty ape at 7:48 PM on February 1, 2011

Sure, this is totally possible. There's even a draft standard for doing it.

My guess is that you'd have random service interruptions and slowdowns when the mesh isn't in a very efficient configuration, and eventually want to install a number of permanent router nodes to ensure coverage.
posted by hattifattener at 8:07 PM on February 1, 2011

There's been a fair bit of discussion and links to mesh networks over at Bre Pettis's blog spawned by the very same thoughts.
posted by Ookseer at 8:57 PM on February 1, 2011

I suspect that the problem you'd run into with resource consumption would have more to do with portable battery life than CPU cycles, especially when you started venturing into the realm of a high-density (or high-complexity) mesh.
posted by schmod at 9:20 PM on February 1, 2011

Yes, this is possible.

I've done mesh networking on PCs before, using OLSR. We didn't see a big hit in terms of CPU utlization (mind you, this was running on PIII nodes). OLSR runs as a application, and takes care of the routing between nodes.The important thing to remember is that with mesh networks your throughput might not be ideal, depending on network condition, such as your signal strength and how many people are using the nodes.

That said, it is pretty easy to setup - install OLSR, configure the appropriate IP addresses, set up forwarding, and bam, one ready made network.
posted by titantoppler at 2:07 AM on February 2, 2011

First, to echo others. Absolutely possible.

Yes, running a mesh network complete with routing via a computer-controlled card would consume resources, but this is an era where even budget computers have multiple cores, while routers with 200mhz processors and 8MB of ram manage this trick. Is there something inherently limited about the cards? Are they harder to code for than routers? Too weak in terms of processing power/transmission?

The weak point, at least with doing it on 802.11 hardware, is radio bandwidth. Far as I know, all client devices, and most consumer grade router devices, are half duplex. They can only transmit or receive, not both at the same time. Secondly, the radio spectrum is a shared resource- only one card can transmit on the same channel at the same time (in the same area). So, like non switched ethernet, you are going to have collisions all over the place. This might not be a problem if the data were limited to text- emails, instant messaging kinds of things. Throw some media or voice in there and it gets to be functionally impossible.

Cellular phones solve this problem by using frequency sharing schemes that (AFAIK) 802.11 hardware doesn't have. First, the cell frequencies have more than 12 channels. Secondly, they are (often) highly directional, which can (sort of) double or triple the bandwidth. A device doesn't need to transmit as loudly to an antenna that is pointed right at it. So background noise is reduced, and other devices can use that same radio frequency pointing in another direction. Third, each channel is split into pieces- I don't know the numbers, but for simplicity, suppose it only takes 1/10th of a second to transmit one second of call audio. The cell tower tells the phones that they get a specific chunk of each second to send their data. Now you can use 10 times the number of devices. (There is another way that I don't understand. Same thing only different.)

Anyway, lacking all of this, the mesh network is going to be inefficient, especially as the area gets saturated with more users. If there is only one path between you and the other end, it is easy. The packets get through or they don't. But if there are 100 people standing on a football field, and each person can connect to say 10 other people, the numbers start getting pretty high for the number of potential paths, and worse, the rate at which paths dry up. The network is going to spend a LOT of its time maintaining this dynamic routing table, and a LOT of time retrying packets.

These constraints almost demand that some kind of hierarchy form up, turning from a purely flat mesh to a multi-tiered mesh of stars. Or some kind of ad-hoc subnetting scheme.

If you could develop a protocol where each radio tried to be as quiet as possible (which I guess they do, but not terribly effectively), added in some frequencies and/or different modulation schemes, tweaked the packets to include beacon-type information including the current sharing algorithm with every packet instead of separate beacon packets from a central router, and forced clients to go through a passive "listen and reassess" routine rather than a "shout, collide and try again" access control scheme, full-duplex radios and maybe build in some minor store, forward or return buffering, it would work pretty good.

Actually, this would make a decent case for a token passing/round robin algorithm. A client goes online, listens for a while to get a "weather report" of all the networks it can hear. Every packet says "This is network A. I am client #7 of 9. I can hear networks B and C and I can speak to networks B and F. I am passing the following three packets for network R, and sending one of my own to client 4. [data passes] Ok, client #8 you are next." Then 8 does the same thing, then 9. 9 is the last in the current chain, so he says "anyone new?" Only at this point will you have any new clients trying to jump in. As the clients listen, they store any packet that they CAN pass along, and if they hear an ACK come back through, they delete it.
posted by gjc at 8:27 AM on February 2, 2011