Slashdot Mirror
frottle: Defeating the Wireless Hidden Node Problem
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.
"
Look up "slotted Aloha" for background on this class of idea.
Am I *not* supposed to understand a word of that?
In case the site (or routes to the site) get slashdotted. Here is a mirror. Sourceforge also has an annoying habit of downing themselves for maintenance. Enjoy!
It really does make a huge difference too. With 15 odd users on an AP we had a nightmare.. someone would start transferring a file and people would drop out, packetloss, etc. The strongest SNR would always dominate, uploads were nigh on impossible (when ANY download was occurring) and the network had no QoS at all.
:)
Thanks to the great work of Frottle, we're now cruising along - we all get a fair go, we have QoS, and bandwidth is shared equally and we're all pretty damn pleased with it.
Is Frottle.. is good
-- Wireless WaFreenet user since March 2002
Fans of Madge, Thomas Conrad and IBM rejoice!
In a lot of cases, I have noticed, speed isn't the problem. A lot of times, I conenct to a WiFi network at full speed, and it is very responsive, and then suddenly it will drop link. It will go from full signal strength to none, seemingly instantly, then work again a minute or so later. This is because the problem is reliability of connection, especially in 'built up areas' i.e. the city. So, what we really need is a redundant, wireless backbone, so I can browse my pr0n-- err, open source software without gettting dropped signals.
====
Crudely Drawn Games
The article relates to 802.11, however this would probably work on packet radio too.
You could achieve the same thing on packet radio by using a digipeater instead of having all nodes transmit/receive on the same frequency, and I think you'd get better thruput with a digipeater than using Frottle.
If a tree fell on a florist, and nobody was around to hear it, would he make a noise?
Yet another project following the tradition of allowing the developers' children to name it.
...
Never call anything Freenet. It is too generic a term and is used for several different commercial and nonprofit organizations and projects.
It's much worse than Firebird.
If nothing else, realize that it messes up people who search for you on Google because of all the @freenet.com email addresses.
It sounds like this is an attempt to change the topology of 802.11x to a polled topology without the true benefit of such topology without changing the hardware.
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.
Seems like using a fork in a drillpress for a daquiri blender... doable, but rather outside the intentions of the tool designers!
Perhaps this will stimulate some hardware vendor to make token-passing wireless network hardware to eliminate the latency problems. IBM, Madge and Thomas Conrad must have boatloads of relevant expertise already....
before I could even understand the problem there is a solution. I'm impressed. And to think, these people do this in their spare time.
I agree. Freenet? Again?
At least we know who to thank- on the bottom of frottle's page under the special thanks is:
jas for coming up with such a catchy name
Yay jas.... very catchy.
J
what. Is there some place that the coordinates of all these hotspots are shown? I think it would be helluva cool to be able to see GPS coordinates, or some sort of listing of where there are these hotspots around. It could be helpful in traveling, and the such.
I don't have a wireless card, much less a laptop, but if i wanted to travel, i imagine that having something like this would be quite helpful, rather than roaming around looking for the symbol etched on a roadsign.
I'm from Perth (born in Subiaco) and have lived outside of Australia since I was a teenager - have visited home a couple of times here and there, and every time I've been impressed with how much progress Perth has made in implementing advanced Internet technologies. Last time I was there - a year ago - I noted teams of wireless-hackers putting up repeater boxes in various neighborhoods at least 4 times - I don't know if it was just by chance, but I kept running into these 3 guys!
One of the things which has kept me from moving back home to Perth and setting up digs has been the state of the Internet down there - the Telecom monopoly, and the distances involved, have been a big factor. Maybe I'm spoiled by American and European bandwidth situations and maybe I ought to just go home and bear with it, but I would be curious to hear from anyone who knows what the scene is like in Perth for cheap, affordable world-class Internet bandwidth?
; -- the corruption of government starts with its secrets. a truly free people keep no secrets. --
Well, this idea is good and all (that's why it's a part of the spec!) But the problem with a firewall-based solution is that it is behind the AP and thus the solution of traffic control through client polling is only simulated. Without the AP performing the polling, you don't acutally solve this so called "hidden node" problem.
... about 6 years or so, even the 802.11b ap's! It's like trying to make steel in your fireplace. The consumer-grade equipment is not designed to take the heat. Consumer-grade AP's are going to lack some of the features needed in carrier-grade equipment such as polling. It makes them cheaper - no doubt they are missing features.
802.11b people have a bad habit of thinking that the problems they face are new or unique, so they do a lot of re-inventing the wheel. This, normally is not a bad thing, but quite often "WiFi" supporters produce a crude solution while spewing insane amounts of bullshit radio pseudosience. When did "crosstalk" suddenly mutate into "hidden node problems?" Alvarion (Breezecom) has had polling support in their AP's for
What someone who wants to fix this really ought to do is modify the ihostap drivers to do polling 'on the air' -- If it is possible, at any rate.. I am unaware of the specific implemenation, and it's likely that even toying with the HostAP drivers will not allow one to work with the radio at a low enough level. Still, you know, if it works, it works. Traffic shaping can make things seem faster on congested networks of any kind, so if it throttles the abuser down enough where other radios can get a word in edgewise, then it does a little towards curing a symptom of the real problem. For the freenets and coffee shops, this may be entirely sufficient.
~GoRK
Tannenbaum's best known work is Operating Systems, the Minix book.
Yes, I know he was critical of Linus on comp.os.minix, that is why I voted to create comp.os.linux. They are still excellent books.
Is your comment designed to infer that token-ring is a less advanced network topology? Token-ring is actually younger then ethernet and has many advantages. It holds up performance wise under load and you can predict the max amout of time a packet will take to travel the network. Thisis something you cannot do on a larger ethernet. Token is widely used with medical and manufacturing eguipment were messaging latency must be garunteed. The only reason speeds of token have not increased is cheaper ethernet is well suited to most but not all situations, wireless A/p like envirormentsthat effectivly are shared medialike a hub is one example where ether falls appart fast with many users. Token would hold perfromance and make best use of the air time. Token scales, ether does not unless you add segments. Token has not increased speed because there has been little demand for it. But it is the more advanced technology and would be the solution for large wireless applications.
Color me unimpressed.
Why are you critical of the solution? It appears to work well and is inexpensive. What is wrong with that?
A friend who used to work for a "baby bell" was involved with a project to provide VoIP and video services, as well as internet, over their DSL infrastructure. The problem that they ran into was that IP, as supported by their commodity DSL equipment, did not support QoS. Their solution was to tunnel a more advanced network protocol (ATM I think) over the entire DSL IP connection. Then they ran their voice and video over ATM directly and ran IP as another tunnel over ATM. It wasn't elegant, but it was cheaper and more effective than manufacturing new devices.
Anytime you can use commodity off-the-shelf hardware, you can usually save money.
It's also an order of magnitude more difficult to implement (due to problems like recovering lost tokens) and was limited by spec. to 16Mbits/second, with a higher proportion of those bits devoted to overhead. Oh, and chipsets to do Token Ring were an order of magnitude more expensive. Token Ring is to Ethernet as Steam Engines are to Internal Combustion engines -- yes, if they'd put as much time, energy, and money into developing Token Ring as they have into Ethernet, it would be a better technology than Ethernet (mostly because like you said, worse case packet delivery time is deterministic). But they haven't!
"Freedom means freedom for everybody" -- Dick Cheney
While this does deal with one aspect of the Hidden Node problem (packet collisions) you haven't fixed the real problem: The remote clients cannot hear each other. This is just a fundamental problem with CSMA/CA on a RF spectrum.
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.
This is not really a hidden node problem, as they make it out to be.
... data packet ...
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.
1. Isn't this what RTS/CTS is for?
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.
Taral
WARN_(accel)("msg null; should hang here to be win compatible\n");
-- WINE source code
Color me unimpressed.
Yeah, me too. You lamers. All you're doing is adapting old ideas that you didn't invent to new situations. You should just deal with the problem and stop trying to improve your situation. Who do you think you are? People with free will? WTF is wrong with you?
If you want good behavior from your wireless system, you're supposed to go forth and spend large sums of money on exotic, highly vertical equipment from specialized vendors. How do you expect to command respect from anyone if you don't do it that way?
Idiots.
Maw! Fire up the karma burner!
I note that the Frottle master relays traffic when two non-master nodes wish to talk to each other - even if they could talk directly. This both reduces the potential agregate peer-to-peer bandwidth by a factor of two (or more) and sets up the Frottle master as a "man-in-the-middle".
I'd rather see the master simply arbitrating bandwidth in its neighborhood and the peers exchanging data directly. General-casing that to multiple simultaneous masters, while relaying but only when necessary and only by efficient paths, limits out at a mesh network with extreme bandwidth usage efficiency.
But the thing that bugs me is the security implications of having all non-master nodes relay through the master. That lets a hostile node that achieves (or spoofs-up) master-node status perform man-in-the-middle attacks on the security of the communication.
Being man-in-the-middle is probably not a big deal if the master is also the main internet gateway (so it would be man-in-the-middle to most traffic anyhow), operated by a well-known and trusted organization. And it does simplify routing packets from one channel to another. But it bothers me anyhow.
Fortunately, any node that can also hear its peer can check the honesty of the master's forwarding.
Which leads to a potential way to eliminate unnecessary bounces off the master: Clients can inform it that they can hear other particular clients and what the differential delay characteristics are from their site. Then the master can just assign the transmission slot for the packet and drop it on the floor while the receiving peer captures it directly.
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
It's definitely a great hack. But of course if you just waited a year (or so ;-), 802.11e would have provided the same but with less overhead and enforcing the limits on the ether.
...). But it would work.
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,
At one stage (a year go, not sure if its still the case), Perth (capital of Western Australia) had more wireless networks per capita than anywhere else in the world. Yes, that includes San Francisco.
Why? Because it is a spread out, very flat city with piss poor and expensive broadband internet. It's also isolated from the rest of the country, so it's quite often the last Australian city to get infrastructure. There is also an abundance of unused satellite TV antennas from a failed provider, which people let you take off their roof for free (I collected 9 in one afternoon with a mate one day). They make excellent wireless receivers if you mod them right.
I went to Uni in Perth, and in the last 12 months my mates there have put up 3 antennas - they are Comowireless on the node database. I live in Sydney now, and I don't see anywhere near as many wireless antennas here as I did when I lived in Perth.
Once upon a time, in the mystical land of Oz, there was the quiet city of Perth. Broadband was expensive (cable was only in one suburb), and ADSL was only just beginning to roll out. WiFi has just been released, and a group of enthusiasts saw the potential.
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.