frottle: Defeating the Wireless Hidden Node Problem 121
jasonjordan writes "The West Australian FreeNet Group was the first to go War Flying - and now we've released "frottle" (freenet throttle) - an open source project to control & manage traffic on fixed wireless networks. Such control eliminates the common hidden-node effect even on large scale wireless networks.
frottle works by scheduling client traffic by using a master node to co-ordinate - effectively eliminating collisions!
Developed and tested on the large community wireless network of WaFreeNet, We've found it has given us a significant improvement in network usability and throughput.
"
They're reinvented Alohanet, circa 1970 (Score:5, Informative)
Look up "slotted Aloha" [google.com] for background on this class of idea.
Mirror (Score:4, Informative)
Re:Is Frottle.. is good (Score:5, Informative)
So we rolled our own. Frottle is the result.
802.11x topology change (Score:5, Informative)
In a true polled topology client packets aren't sent until the AP says they can. The client equipment remains completely silent until they receive the right to broadcast packet. AP's are programmed to completely ignore packets that are sent out of turn anyway.
802.11x hardware is NOT designed that way. Sure you can control data flow that way but your AP is still open to the same problems as before. I wonder what happens when one of the client on one of the computers crashes and ceases to act as a polled client. Will it start hogging time slices from the AP again? Seems to me it would unless there was a radical hardware change to both AP and client adapter.
Re:Attention Project Namers: (Score:2, Informative)
Try Googling [google.com.au] for frottle some time. no confusion there!
Just read the article.. (Score:1, Informative)
Color me unimpressed.
Re:802.11x topology change (Score:5, Informative)
Correct!
We have built a city-wide wireless freenet using commodity hardware. Things were working well, but as we grew larger the hidden node effect became a larger problem. Swapping all the hardware over is a big expense, and a big undertaking for a bunch of hobbyists.
We did investigate doing so, and also investigated a firmware solution (KarlNet TurboCell) but found it unsuitable to our needs.
On a whim, one of us implemented a small master/slave polling system in Perl which seemed to do the job surprisingly well, and it just grew from there.
Re:Am I new to warring or... (Score:4, Informative)
Most WaFreeNet nodes are listed here [nodedb.com]
Computer Networks by AST (Score:5, Informative)
Tannenbaum's best known work is Operating Systems [amazon.com], the Minix book.
Yes, I know he was critical of Linus on comp.os.minix [comp.os.minix], that is why I voted to create comp.os.linux [comp.os.linux]. They are still excellent books.
it's more like Token Bus (Score:1, Informative)
This isn't the *real* hidden node problem (Score:3, Informative)
802.11b orginially proposed using RTS/CTS to rememdy the problem, but they quickly realized that this cut network bandwidth down to 1/2 or 1/4 of available bandwidth. Not good.
The only way that you could really fix the problem is to use multiple receivers (access points) located throughout and have them vote on the packets by using a diversity antenna pair. Between the two access points, they should get enough transmission from both stations (remote clients) to reassemble both packets and send them on their merry way.
This software doesn't really handle 802.11b itself , which allows for clients to clobber each other. Good job getting around the problem, though.
Not a hidden node problem (Score:5, Informative)
This is more a problem with the inherent lack of scalability of a CSMA/CA architecture. Everyone is familiar with the way ethernet degrades under saturation: you only get about 70% of that 100Mbit throughput utilized. Ethernet is CSMA/CD - collision detection.
In wireless the problem is even more pronounced in infrastructure mode because you are using CSMA/CA -- collision avoidance. This means that for every packet to be sent, the clients must coordinate use of the medium before sending, using a RTS/CTS handshake.
(client) can I send now?
(AP) not your turn yet
(client) can I send now?
(AP) not your turn yet
(client) can I send now?
(AP) yes
(client)
When you put many clients (20+) on the same AP sharing the same medium, a large amount of bandwidth is spent simply coordinating contention free access to the wireless medium itself.
Traffic shaping (which is all frottle is doing) helps ease this problem by reducing the amount of data clients try to send/recv in a given period of time, and thus reduces some of the contention.
This is simply a band-aid on a more fundamental problem, however.
The only true way to prevent this kind of inefficiency for larger numbers of clients is to use a true wireless phased array switch, like vivato, which can effectively emulate a dedicated medium to each client, preventing any contention that arises in the broadcast CSMA/CA situation.
Also, it is important to note that communication between nodes on the wireless will NOT be shaped by the frottle queues unless you are using hostap or some other linux based access point. In such a scenario, two nodes talking to each other could use as much of the medium as they liked (as coordinated by the access point itself) without frottle seeing any of the traffic.
Problems with this (Score:3, Informative)
2. What 802.11 really needs is <b>power scaling.</b> It's the big difference between cellular networks and wifi. Like the article says, the person with the highest S/N gets to talk.
Re:Problems with this (Score:3, Informative)
Request to Send / Clear to Send
Required to solve (reduce) hidden station problems.
Station 1: Hey, can I send? (RTS)
Access Point: Yeah, go ahead. (CTS)
Station 2 (who can't hear Station 1, but can hear the access point): Well, since a CTS came back taht I didn't request, I know someone else is sending. Therefore, I'll shut the hell up.
802.11e anyone? (Score:3, Informative)
11e will have a mode called HCF (Hybrid Coordinator Function) recently renamed to HCCA (forgot what that stands for) where the Accesspoint can be asked for timeslots and it will assigned them to the requestors after each beacon causing a content-free period. Only afterwards a (prioritized) contention mechanism will come into place for the rest of the transmission time till the next beacon (called EDCF=Enhanced DCF).
Actually HCCA is not really intended for web browsing over 20km wireless link but more for real-time traffic over 10m wireless link (e.g. videos to your Webpad, PDA,
Re:Fakin' it. (Score:2, Informative)
Let us also consider the cost of alvarion breezecoms (the outdoor models) of easily 1600+ American dollars. I've got a choice between that and a 75 dollar (or less) AP with a 100 dollar beater laptop in a 50$ (max, maybe less if I can find something used and appropriate, which I can) hoffman box. Subtract that from the profit margin of your basic Mom&Pop Wisp (almost nonexistent labor of love style) or neghborhood "sharing" project and I thinks the usefulness of their project becomes apparent.
From all of us who can't drop a couple of g's on an access point, thanks guys!
Re:Frottle master is a "man in the middle" (Score:2, Informative)
Frottle can run in many modes, and doesnt need traffic to pass through the master, though it is more reliable to do so.
As far as Client-Client comms goes, we've always discouraged it for it's use of bandwidth, and before frottle it was the main cause of collisions. For this reason, we stick most of our resources at the master, meaning most data is only a single RF hop away.
Re:Frottle master is a "man in the middle" (Score:1, Informative)
In the WAFreeNet scenario, the nodes are well dispersed, and we're all using directional antennas to connect to the APs, so the nodes cannot talk to each other directly anyway.
The story of frottle.... (Score:3, Informative)
A bunch of people got together, and through many donations, were able to buy their first public WAFreenet Access Point. Now - Perth is fairly flat, with a long ridge running down one side - perfect! The AP was setup on a private property with an incerible view of the city, and we named it HillsHub (we'll call it HH).
By about 5 clients, the hidden node issue started to get noticable. Easy, they turned on RTS, and it made an improvement.
Since it had such good visibility, HH began to get pretty popular. By about 10 clients it was really stuggling, and many of those clients had AP and clients of their own adding to the routed traffic. RTS just wasnt cutting it anymore - the RTS packets are subject to collisions aswell. In a desperate effort to regain some control, rate limiting was implemented, dropping speeds back to 10kB/sec during the day to maintain some reliability. However - during the night, a free for all would occur - some people would get 100's kB/sec, whislt others would be drowned out, near complete packetloss.
By 14 clients, the situation was ridiculous. We HAD to do something. We knew Kalrnet Turbocell (a polled system) would fix it, so we sold our soul (advertising on the e3 website) and negotiated a lower price - even then we needed to fork out A$150 each. We got together and pooled the cash, and just as we were about to buy, realised that the linux support was terrible - old, buggy kernels, binary driver only. We stopped in our tracks, and wondered what to do.
There were plenty of ideas about building our own kalrnet, but none of us were kernel programmers, so it seemed a bit out of reach. That was until one day, when I came up with a plan. I'd read that iptables could send packets to a userspace program, so inspired by some examples (countertrace), I set about building the first version of frottle using perl.
There was nothing new about the concept - polled systems and token rings are common knowledge in communications and networking. It wasnt difficult - it only took me a weekend, and that included the time spent learning perl (it was my first go). It was even operating at the wrong layer - using UDP control messages to schedule IP traffic. Regardless of all it's limitations, it worked, so I got the other WAFreenet members involved with testing and development. Radix picked it up and tried to continue development with C++, but had problems. Then, ChrisK took up the challege, and the result is the dynamic, performance C version we have released.
Halfway through development, WiCCP was released. This was a similar concept, but implemented as an loadable module/interface. We liked the concept better than our userspace app, so we trialled it ourselves. One of the perth guys (Brad) even got involved with development, improving the product. Still, whislt it was an implrovement on no QoS, it didnt seem to perform quite as well as frottle. This was the decider, so ChrisK prepared frottle for release.
So, there you have it. As a developer, I've been paying attention to the comments here. Many of you have given positive feedback, and for that we're thankfull. Unfortunately, some of you have decided it would be easier to point out the flaws...
Well, no shit sherlock! We're quite aware of frottle's limitations, the concept is far from origonal, and it really is a kludge. The inherent problems of 802.11b are still there, and all we've done is work around them. The thing is, no-one else had done it before - at least not for free, and not when we started. We've spent our own time on frottle in order to improve our situation, and help the performance of free community wireless networks the world over.
Criticise all you like, but the fact is, we have experienced an enourmous, measurable improvement to our network performance. As far as we're concerned, this is BIG news.