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.
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
Yet another project following the tradition of allowing the developers' children to name it.
...
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.
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.
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
yes, check out nodedb.com
Most WaFreeNet nodes are listed here
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
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.
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!