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....
..and all this is, is a glorified token ring implemented at the OS layer on top of 802.11.
Color me unimpressed.
It's not trolling if it's true!
Yeah but that's no good because then people like me who read at threshold 5 with +6 modifiers on Troll, flamebait, redundant and offtopic don't see the folks that start out at negative one.
Wow... they've just set networkin technology back 15 years.
Article X: The powers not delegated... by the Constitution...are reserved...to the people
It's much simpler to run one net, however. The name escapes me, but there's a system in use on some busy packet radio channels in Europe that's very similar to Frottle. Here in the US, I've never heard of anyone using it though...
that's why all of us with karma must do our part to mod up trolls to at least 0 so they can then be modded down and trigger our modifiers.
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. --
I hope they succeed and bring back the uncontrolled internet so you could achieve the same problems as before. I wonder what happens when one of us connected to this network because we are interested in the technology behind it. For users, would there have been a problem to begin with? Most of it is implemented as a small master/slave polling system in Perl which seemed to do the job surprisingly well, and it just grew from there. Any discussion of the client as one of the AP and would have undoubtedly leeched it out of the same thing on packet radio by using a digipeater instead of having all nodes transmit/receive on the same thing on packet radio by using a digipeater There is not really an absolute difference between them
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.
I dunno, seems a bit of a kludge. Why not run the 802.11 network in ad-hoc mode and dynamic route via AODV. If there are bandwidth problems, pop in more nodes==routes. Yes, the peak performance is necessarily lower, but the worst-case performance must be much better?
Token Ring requires each node forward packets that it didn't originate. In this case, it is merely a bus with token access control.
I am now more Learnded
"prevents clients with stronger signals from receiving bandwidth bias"
all that time and effort to get a stronger signal and they're gonna cast me back down with the technon00bs?
'screw you guys, i'm goin home'
// "Can't clowns and pirates just -try- to get along?"
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
If i had this many /A pageviews for my sourceforge project, I'd also try to submit it as a story on slashdot.
Don't be silly. The computer is your friend.
You are an asshole. Zero me again, and you will regret it.
I've zero'd you once. Feel free to threaten others who won't put up with your shit. Remember, we aren't slashdot. It won't take much to get banned from SRU. If you'd like to take that further, I have your ISPs information in my hands ...
a/s/l here. Sorry, adding domain tags to your s
when it was called 'token-ring'
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,
really... esoteric... renaissance... dance... music... joke...
How much of frozzle's effect could you emulate by putting CBWFQ on the etherswitch that the AP is connected to?
CBWFQ wouldn't implement a token system, but it would slow down flows that met a certain criteria. One thing it can't do is say "people who have transmitted over 2Mb need to go to the back of the line" - has anybody tested it?
Iuhidden nodefS!
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.
he tells like it is!
802.11a/g are at 54 Mbps, who knows what the next jump will be.
simon
home page
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.
First, what the heck is the hidden node problem anyway? It's highly misunderstood. The hidden node problem is when you have a point to multipoint topology in your 802.11 network, aka, a "star" topology. There is one central hub that is connected to the internet, and many nodes that talk to the hub. Now this is all fine and dandy indoors, because indoors usually all of the nodes can hear not just the hub but also each other as well. So they are effectively sharing a single bus, and they can listen to find out if anyone else is using the bus before they talk (classic CSMA situation right?)
Problem is outdoors. Outdoors, you're using long-distance antennas on each of the nodes and an omni on the hub. Now the nodes are mutually deaf, because all they can "see" is the hub, they are too far away from each other to "hear" each other. Thus, they hidden from each other. Now, they cannot perform the Carrier Sense part, because when they listen on the bus, they will not be able to hear if another node is in send mode, sending data to the hub. They will not hear that, and they will decide to broadcast, and the hub will get spammed with two signals at the same time. That's the hidden node problem.
Well there's already a partial solution to the hidden node problem built into 802.11. It's the RTS/CTS system. RTS is Request to Send. Before any node starts talking, it sends a query to the hub, asking if it's all clear. The hub ACKs with a CTS (Clear to Send) response. ALL of the nodes can hear the CTS, so they all delay their own transmissions for a little while.
Of course, you can still have undetectable collisions during the RTS/CTS period! But that's OK, because USUALLY the bandwidth that the hub is CAPABLE of handling FAR exceeds the bandwidth that the nodes NEED. In fact, if you are experiencing the hidden node problem, you can just use TCP throttling to reduce the problem substantially.
We know that the hidden node problem is directly proportional to the percentage of the bandwidth being used. At this point we must say, quite frankly, that the BEST solution is to INCREASE the bandwidth available! Thus, not only do you REDUCE congestion but you also INCREASE speed.
Token ring totally pisses me off. Sure, it's a great idea. You put everyone in a circle and you give one of them a "token". Only the dude with the token is allowed to talk. When they're done talking, they pass the token to the next person, and so on, around the circle, until it comes back and you start again. Great idea in theory.
The problem is there's so many failure cases. What if one node hogs the token? What if a node drops the token? How do you recover from that? What if just one section of the circle dies? When a new node comes online, how do you add it to the token ring? There's a ton of central control required, and that means (a) complexity and (b) overhead and we know that both of those are BAD news.
All that is R&D effort that's totally wasted because all you're doing is making the current system work, that energy could instead be spent on installing a faster model that doesn't get congested in the first place.
</rant>
simon
home page
Actually CSMA/CA does not include handling of hidden nodes. RTS/CTS was specifically ADDED to 802.11, AFTER CSMA/CA was decided, to handle the hidden node problem.
There is mutual interference between hidden nodes during the RTS/CTS phase.
Score another point for Wi-FUD. That is ONE solution but not the ONLY solution. You could of course, also reduce contention for the shared medium by installing multiple hub radios with sector antennas and save a lot of money. OR, you could upgrade to a faster wireless standard like a or g, and eliminate the contention altogether!
In fact, despite the attempts for people introduce "Quality of Service" measures (which is exactly what fropple or whatever it's called really is), ethernet (10,100,1000MB... and more?), the internet, and dare I say it, Wi-Fi continue to work VERY VERY well based on the model of "best-effort access". Yes, they all degrade rather substantially when put under heavy heavy loads. BUT, the solution is to INCREASE available bandwidth, which leads to new possibilities and innovations and solves the old medium access contention problem at the same time.
simon
home page
The topic of buying more equipment was discussed with the HillsHub users. Unfortunately, we couldnt do it.
As I mentioned in the story, HillsHub is very popular due to it's location. It's a private property - owned by the Uncle of one of the wireless enthusiasts. They've been gratious enough to allow one waveguide and a dish on their roof, but that's it. Even if we could put more infrastructure there, there is channel usage and other surrounding AP's (noise/interference) to be aware of. There are real limitiations.
The hidden node issue was noticable to some degree with as low as 4 or 5 users. If we put three AP's at Hills Hub, I bet there would be more than that many users per AP.
As far as latency goes - it is a shame, but that's the price we're willing to pay. With 14 or so users, we're seeing under 200ms round trip latency to the central server - more from client to client. That's not terrible, but not completely suitable for gaming. Were trying to come up with some schedules for modifying the frottle parameters - choosing faster polling (lower latency) for game times, slower polling (higher efficiency) for leeching times.