I just stumbled on an interesting paper by Shyamnath Gollakota and Dina Katabi at MIT describing ZigZag decoding. They will be talking about their work at SIGCOMM later this month.
The problem they've addressed is that of hidden terminals competing in a shared medium, in this case 802.11 WiFi. This diagram shows the problem:
Alice's radio can "hear" the base station (the access point of AP above) and can transmit to it, but her radio can't hear Bob's radio so, while Bob is transmitting, Alice starts transmitting. Their transmissions interfere, neither is acknowledged, both retry and even though they each delay a random interval, it's highly likely that at least part of their retransmissions again interfere. Alice's and Bob's radios are said to be hidden from each other. The critical issue is, since they can't hear each other the normal "listen before transmit" algorithm doesn't help.
ZigZag allows the base station to decode both of the colliding packets with an efficiency as good as if they had been sent in separate timeslots. What's more ZigZag is compatible with all the various WiFi modulations and works with existing terminals, i.e., only the base station (the AP) requires an upgrade.
So far they've only implemented a prototype in software using GNU radio, so we're unlikely to see this in commercial products for a year or two. But their results are impressive:
- The loss rate averaged over scenarios with partial or perfect hidden terminals decreases from 82.3% to less than 0.7%, with some severe cases where the loss rate goes down from 100% to zero.
- Averaging over all sender-receiver pairs, including those that do not suffer from hidden terminals, we find that ZigZag improves the average throughput by 31% when compared to current 802.11.
- At all SNRs, ZigZag’s bit error rate (BER) is lower than if the colliding packets were scheduled in separate time slots. The average reduction in bit error in comparison to scheduling packets separately is 1.4x.
They've invented a straight forward approach to decoding colliding packets. It seems obvious now that I read it and yet I've been interested in this subject for 25 years and their approach never occurred to me. :( If you are at all interested, read just the introduction to their paper.
Why does it matter?
First, it's another increment in the continuing exponential improvement in radio performance
Second, it helps IT directors get more capacity on wireless LANs.
But most important for the long term, it improves the prospects for mesh networks. While I can't predict specifics for how it will happen, mesh networks have the potential to create capacity from the edge! No operators, just individuals and enterprises purchasing devices for other reasons. Now that will be significant!
Comments