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.
"
A public service announcement. (Score:-1)
Re:A public service announcement. (Score:0)
Re:A public service announcement. (Score:0)
Moderators: (Score:0)
Don't be silly. The computer is your friend.
Re:A public service announcement. (Score:0)
Re:A public service announcement. (Score:0)
URGENT: Massive Mozilla security hole discovered! (Score:-1, Offtopic)
IMPORTANT: There is a huge security hole in all Mozilla builds thatwas just discovered yesterday. By inserting a properly-constructed URL into anXHTML source file with MIME type application/xml+xhtml, arbitrary code can berun as the client user on his machine. This hole exploits a known bug inMozilla's xml parser, that doesn't properly handle certain character entities(e.g. &#nnn;). If the decimal number inside the character entity is greaterthan 65535 (the maximum legal Unicode value), a buffer overflow is triggeredand arbitrary machine code can be inserted into the running process.
Luckily though, the fix is small, simple,and can be automatically downloaded over the Internet, thanks to Mozilla'sXPI installation facilities. This patch is available from the BrowserSecurity page at data.com and more info is available on Yahoo [yahoo.com]. Simply click the link, and after a short verification the fixwill install itself.Please install their patch ASAP, before malicious hackers wipe Mozilla offthe web!
Isn't open-source grand? Had this been an Internet Explorer exploit,we wouldn't even know of its existence until about a month after sKr1p7 k1dd1eZ started hacking with it. I applaud the Mozilla team for promptly discoveringand disclosing this bug, and the fine folks at data.com for hosting the fix.
Why we won't have wireless for long... (Score:-1, Flamebait)
You see, that colored race which roams the desert looking for ways to destroy us does not realize that we are the only source of progress in philosophy, science, and art. Without America and its good, wholesome Christian values, this world would have nothing. There will be no one left to drive the human race towards perfection.
Once we've been destroyed by these short-sighted individuals, humanity will slowly fall into its doom. Afterall, the arabic peoples won't stop until everyone else is destroyed, then, like animals (I don't even think they're people), they will destroy themselves.
How can a violent race like that ever spawn social progress? They're quite literally like monkeys, running around like crazy, flinging feces at each other. Without Truth (the Word of God), they've gone quite insane with the devil whispering in their ears. Unlike monkeys flinging feces at each other, they fling bombs at each other (and us).
Personally, I'm glad that a good Christian man (women really can't be Good, because they cannot be like God as they lack the proper equipment), like George Walker Bush, has the guts to stand up and say "we won't let these inferior people destroy America". Now we're taking steps to exterminate them and take their resources for the advancement of America. Good show, Bush!
Re:Why we won't have wireless for long... (Score:0)
They're reinvented Alohanet, circa 1970 (Score:5, Informative)
Look up "slotted Aloha" [google.com] for background on this class of idea.
Re:They're reinvented Alohanet, circa 1970 (Score:3, Interesting)
Re:They're reinvented Alohanet, circa 1970 (Score:1)
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.
Re:Computer Networks by AST (Score:0)
Deal with it bitch, you can never be anybody we know.
Re:They're reinvented Alohanet, circa 1970 (Score:5, Funny)
So... (Score:3, Funny)
Mirror (Score:4, Informative)
Is Frottle.. is good (Score:5, Interesting)
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
Re:Is Frottle.. is good (Score:5, Funny)
Re:Is Frottle.. is good (Score:4, Interesting)
Most of us connected to this network because we are interested in the technology behind it. 15 "normal" internet users would have undoubtedly leeched the fsck out of the AP and would have seen problems much sooner....
Proud Denizen of the WaFreeNet
Re:Is Frottle.. is good (Score:5, Informative)
So we rolled our own. Frottle is the result.
Re:Is Frottle.. is good (Score:2)
Token ring reborn! (Score:5, Funny)
Re:Token ring reborn! (Score:3, Funny)
This sounds a LOT like Token ring has gone to the, um... ether?
it's more like Token Bus (Score:1, Informative)
Speed isn't the problem... (Score:5, Funny)
Ah yes.... (Score:5, Funny)
agreed (Score:2, Funny)
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
Re:Ah yes.... (Score:1)
Attention Project Namers: (Score:4, Insightful)
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.
Re:Attention Project Namers: (Score:2, Informative)
Try Googling [google.com.au] for frottle some time. no confusion there!
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: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:802.11x topology change (Score:1)
Re:802.11x topology change (Score:1)
If people connect to the AP without frottle, essentially the collisions and packetloss appear whenever they are uploading. To discourage this, we generally firewall any non-frottle clients, using the frottle stats output in a script. Now, this doesnt stop people using the AP to repeat traffic at the MAC layer, bypassing our routed topilogy - though if this was a problem we could setup MAC filtering.
So, this system is completely succeptible to failure or circumvention. Good this is, we're all mates.
token-passing on top of CDCSMA (Score:2, Insightful)
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....
Just read the article.. (Score:1, Informative)
Color me unimpressed.
Re:Just read the article.. (Score:5, Insightful)
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.
Re:Just read the article.. (Score:0)
Add to that the fact that tunneling IP over ATM horribly degrades TCP performance [a completely new ATM layer had to be invented just to help this problem a bit, and even then performance isn't quite up to par with cheapo IP hardware], mainly because the IP and the ATM layer have different packet boundaries, so they get split up and TCP horribly chokes when part of a packet is lost, trying to rewind a lot of data that is guaranteed intact.
However, you are correct that carrying voice and such over ATM would work a lot better than over IP hardware. ATM was designed for these things. The IP part is only useful if it isn't your absolute priority, and you use something like ABR to provide it.
Re:Just read the article.. (Score:2)
The important point is that the protocol tunneled over the commodity IP connection, and was, by definition, able to use the entire bandwidth of the IP connection. The protocol supported QoS. It was implemented in software. Since the telco involved controlled both ends, it may have been a custom protocol that borrowed features from ATM.
Re:Just read the article.. (Score:1)
-Brian
Re:Just read the article.. (Score:5, Funny)
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.
Re:Just read the article.. (Score:2)
And? If it works better than RTS/CTS and solves their problem..
TokenRing? (Score:0, Redundant)
Re:TokenRing? (Score:4, Interesting)
Re:TokenRing? (Score:5, Insightful)
Re:TokenRing? (Score:2)
I _like_ tokenbus; I designed a TokenBus protocol long ago for the Amiga that was never implemented (complete with auto-registration and optimizations for the common small-number-of-talkers case - let the token ping-pong between two (or n out of m) nodes, and allow other (skipped over) nodes to object to being skipped, causing the token to get passed through the formerly skipped nodes.
Re:TokenRing? (Score:0)
Wow (Score:5, Funny)
Re:Wow (Score:1)
Am I new to warring or... (Score:3, Interesting)
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.
Re:Am I new to warring or... (Score:4, Informative)
Most WaFreeNet nodes are listed here [nodedb.com]
Thanks (Score:2)
What is the state of WAFreeNet these days? (Score:3, Interesting)
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?
Re:What is the state of WAFreeNet these days? (Score:1)
There isn't, simple. And I can't see there being for quite a long time either. I am from Perth originally (lived 18 years, now residing in Washington) and broadband in Australia is still in a very poor state, unless you are exceedingly wealthy.
Re:What is the state of WAFreeNet these days? (Score:1)
You can get some of it cheap, but it's not really world class.
256kbit ADSL with 2GB soft cap for A$50/month
1.5mbit ADSL with ~22GB soft cap for A$150/month
Cable (only in some areas) with 10GB hard cap for A$300/month + A$0.10 per MB over cap
Reliability on the ADSL is pretty crap, many of the ISP's have experienced such huge takeup that their main data pipes cant meet the demand. Also, there are lot of places that cant get ADSL due to multiplexed/pair gain phone systems - Telstra only just released cheaper ISDN plans to combat this.
Telstra and Optus rolled out cables in competing areas, so there is a poor spread, covering only a small fraction of the city.
There's also satellite with ridiculous pricing, and a few wireless ISP's starting up.
Nice concept (Score:0)
Fakin' it. (Score:5, Interesting)
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
Re:Fakin' it. (Score:0)
MOD PARENT UP (Score:0)
Re:Fakin' it. (Score:2)
I also did address using a computer as an access point. This software belongs in the HostAP driver in that case as I said. Running the access point and running the firewall on the same host is often done (I do it myself on my home firewall.) This is the only real solution to the problem as posted. The frottle people should not say they implemented AP polling modes with a software firewall because that is not what they did!
Finally, in the end, I said that frottle may be just fine for smaller installations and that traffic shaping often gets the job done even when it is not the best solution. I traffic shape my upstream bandwidth on my cable modem which fixes the problem of a large upload killing bandwidth even though it's not the real problem. The real problem is the cable modem's internal TCP/IP queues are way too big for multi-user environments (but great for single user environments where they most often are)
All that said, I'll probably fire frottle up on my unit here and see how it works and why. Crosstalk problems often occur in metal buildings and other consumer-level situations where an inexpensive solution like this could prove very effective in treating an annoyance like this.
~GoRK
Re:Fakin' it. (Score:1)
I dont thik we ever said we did. We were quite clear that this was IP layer polling (not just traffic shaping either - it's co-ordinated).
Yes, we are "fakin' it", but unfortunately that is all we have to work with. Karnet, with their expertise and budget, have true AP polling with their Turbocell system.
Now, we dont claim to be RF experts, but from what I can determine our example IS a hidden node scenario - we have many geographically remote clients, connecting to the AP with directional antennas. Those clients are unable to hear each others transmissions, and hence are unable effect propper collision avoidance.
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:Fakin' it. (Score:2)
I also did mention that proper polling support might easily be added to the HostAP project as pure software. This would actually fix the real problem and add real polling to the WLAN... at least for 802.11b, anyway. 802.11g cards seem to be doing AP functions in firmware rather than host-processed.. A shame, really. It's really pushing the bar down on the consumer equipment (without someone reverse engineering the firmware anyway!)
~GoRK
AODV (Score:1, Insightful)
Re:AODV (Score:1)
Adhoc links are all well and good - but you try linking a large number of users via adhoc links and you'll run into a number of problems:
Firstly, cost - that's a lot of dishes, cable and wireless cards you're talking about! We're hobbyists - not a commercial entity.
Secondly, Line of Sight (LOS) - not everyone has LOS to everyone else. And not everyone likes putting up massive masts just so they can. But it is possible to find sweet locations (like HillsHub for us) that have superior elevation and view. That's where an AP and frottle comes into its own - it allows us to leverage that great LOS and for a great number of users to use it and benefit. We didn't have to turn away potential users from using it because of QoS concerns - frottle solves that problem.
Thirdly, interference. You only get about 4 effective channels with the 2.4GHz spectrum, before you start getting overlap and have to start flipping the polarity to squeeze a bit more out of it. So that limits the number of adhoc links you can have at any one location significantly.
With our solution we're using ONE channel, we're all able to connect using minimal hardware (just a cheap Wireless AP and a homemade waveguide), we don't need expensive software - it's all free under the GPL.
We do use adhoc links between AP's to help provide a better backbone - and we've been experimenting with dynamic routing to help use redundant links more effectively.
but i converted that pringles can for a reason! (Score:2)
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'
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.
Re:Not a hidden node problem (Score:0)
Not quite true. We're using standard off-the-shelf APs, with a linux router behind the AP. Frottle is running on the linux router.
Re:Not a hidden node problem (Score:2)
If you use an AP that does the NAT/router for you, anything between the clients is not going to go through the linux router.
Re:Not a hidden node problem (Score:1)
Not true. Each client sends its data one at time, much like a token ring.
Yes, it's a bandaid solution, but your comments are just misleading. How about you read the documentation next time.
Re:Not a hidden node problem (Score:2)
You may also want to try forcing the communication rates for clients operating under contention.
iwconfig eth0 rate 11M
This bypasses the brain dead default behavior where clients drop rates during contention. If you know you have good SQ, set it high.
Last, any kind of ingress traffic from the clients is completely outside the control of the queues (it's already passed over the wireless medium) which is why I dislike this approach compared to something at a lower level.
Here's to hoping the GNU Radio for 2.4Ghz and/or reverse engineered drivers for software defined radios (Broadcom/Atheros?) are available soon for the kind of layer2 tweaks that you hint at.
the 802.11 MAC really does suck shit through a straw. Hopefully we wont have to live with it much longer
No, this IS the hidden node problem (Score:2)
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
Re:No, this IS the hidden node problem (Score:2)
Ok, if you want to be pedantic, I was talking about CSMA/CA in the context of the 802.11 standard, which uses RTS/CTS to address the problem, just like you said. There, that's better.
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.
Adding more radios and sector antennas is simply another band-aid IMHO. Sure, it works, but so does the traffic shaping/psuedo token ring method.
OR, you could upgrade to a faster wireless standard like a or g, and eliminate the contention altogether!
Yeah, because 802.11g and 802.11a use a completely differnt MAC right? wrong. they have the same problem. its just less pronounced because you have more bandwidth. 802.11g is the worst of these two, as you get the same problems as 802.11b, at 802.11b speeds, with just a single 802.11b client on the 802.11g network (hopefully vendors are fixing this problem, but its inherent to the backwards compatible nature of g itself. They have mitigated this problem a bit with prioritization, but it is still very much a problem)
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.
Sorry, the 802.11 MAC is a pile of crap full of inefficiencies in the name of simplicity and cheap implementation. Things like full duplex, smarter rate management, better CA mechanisms, all have vastly more potential for increasing throughput than simply jacking up existing bit rates with the 802.11 MAC.
Re:No, this IS the hidden node problem (Score:2)
Hmm.. I thought we were trying to solve the original problem. If you're going to keep piling nodes onto the hub, you're going to hit limits whether you use the 1-5 gigabuck standard or the 10-100 gigabuck proprietary system.
Umm.. yes, you're right, that's exactly my point. The problem is solved by upping the bandwidth, instead of fiddling around with complicated MACs.
I never saw a simple and cheap solution I didn't like. Jacked up bit rates? Bring 'em on. I'll be running at new speeds by the time you get QoS working at the original rate...
simon
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.
Re:Problems with this (Score:1, Interesting)
In fact, we had a similar product that did much of this in a software layer above 802.11, and measured aggregate throughputs of 2-3 times higher than vanilla 802.11. I guess that the concept is similar to what the frottle folks are doing.
Re:Problems with this (Score:2)
Except that RTS/CTS doesn't work well enough.
802.11* was designed for indoor use, so the MAC layer depends on all stations hearing each other in order to arbitrate access to the shared medium.
As a fall-back they also included RTS/CTS mode. But RTS/CTS is rather suboptimal - some sort of polling or token mode would work better for outdoor wireless data comm.
So these guys implemented a token mode for controlling the clients' access to the wireless medium. Hack? Sure. Would it be better to implement it in the radio firmware? Sure. But it works!
Oh yeah (Score:1)
Re:Oh yeah (Score:1)
I only just setup the sourceforge page yesterday (though we had it registered for some time before that).
I saw this back in 1988 (Score:0)
Frottle master is a "man in the middle" (Score:3, Interesting)
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.
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.
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,
Must... refrain... from... making... (Score:0)
What about Bob? (Score:0)
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?
I can't stand those (Score:1)
Perth, wireless capital of the world (Score:2, Interesting)
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.
Just add bandwidth, duh (Score:1)
802.11a/g are at 54 Mbps, who knows what the next jump will be.
simon
-1, moderator is ignorant (Score:2)
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
Re:-1, moderator is ignorant (Score:1)
Thanks, but get real.
PS - the token in this system doesnt get passed from client to client. The master hands out a control packet, the client sends data, sends a response packet, then the master moves on.
If the client overruns - not much we can do. If the token gets lost, the master just waits a moment and sends a control packet to the next client. It doesnt even need to be in order - busy clients can get more time, quiet clients less, or even skipped completely for several cycles.
Re:-1, moderator is ignorant (Score:2)
You acknowledge on your page that you are introducing greater latency. Latency is another bugbear of the 802.11 QoS crowd, because it affect voice applications. 802.11 latency also goes way up when the hidden node problem occurs. Again with that situation, increasing bandwidth will solve the problem.
In addition, you said in another post that you collected $150 each --- money that could be spent to install new hubs and/or higher bandwidth hubs.
I'm not dissing your efforts, I think CWNs are great. But there is a broad group of people who think that QoS is needed everywhere, Wi-Fi, in IPv6, etc., and it's bad news.
simon
In a perfect world, yes... (Score:1)
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.
Re:In a perfect world, yes... (Score:1)
simon
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.
Re:Good news. (Score:3, Insightful)
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.
Re:Good news. (Score:0)