Increasing wireless network speed by 1000%, by replacing packets with algebra • Hacker News Board

Re: Increasing wireless network speed by 1000%, by replacing packets with algebra

#41

Post by kokey » Wed, Oct 24, 2012, 1:25 PM UTC

mrb wrote: post #21

tomstokes wrote: post #3

Summary: TCP throughput drops dramatically when packet loss is present. This technique uses forward error correction to compensate for packet loss, resulting in higher effective throughput over lossy links. Many WiFi and cellular connections are lossy, so this would be helpful in those cases. They haven't improved the underlying link rate at all. In fact, the FEC overhead is going to reduce the effective link rate. H…

Yep. This appears to be nothing more than FEC. Maybe they used LDPC or LDGM, which are superior to traditional Reed-Solomon codes. I remember doing research on FEC codes back in 2003-2004 for developing a protocol for sending large files over satellite links to multicast recipients when I was working for SmartJog.

Soon we will see an article about how they turn blocks of file data into algebra to save disk space.

Re: Increasing wireless network speed by 1000%, by replacing packets with algebra

#42

Post by jasonwatkinspdx » Wed, Oct 24, 2012, 1:49 PM UTC

Jabbles wrote: post #38

Has anyone done an experiment to see what simply duplicating every TCP packet sent over wireless does? If you're in a situation where you're limited by random packet loss and not by raw bandwidth, I imagine it could help... Obviously this is a much weaker and less efficient solution that what is proposed in the paper, but this would be trivial to implement. I believe netem allows you to simulate this.

There was an RTS game in the late 90's that did something like this. It was peer to peer, with peers broadcasting their input events to each other and running mirrored simulations in lockstep. So the bandwidth used was trivial since you can code a keypress or mouse click in just a couple bytes, but any packet loss would degrade the game for all peers. So they just duplicated the last packets input data in successive packets. No algebraic coding or any other attempt to save bandwidth, since the data was already trivial.

Re: Increasing wireless network speed by 1000%, by replacing packets with algebra

#43

Post by eru » Wed, Oct 24, 2012, 2:19 PM UTC

ChuckMcM wrote: post #12

andrewcooke wrote: post #8

Earlier quoted context omitted.

http://en.wikipedia.org/wiki/Forward_error_correction#Low-de... implies that they are used in 802.11n (i have no idea what is new in this article)

I was thinking the exact same thing. Oh look, someone had discovered forward error correction. Now if they can compute a series of code blocks over a rolling set of data blocks, that would be new. It would be like singing a round of "Row Row Row your Boat" but in data packets, just waiting and you'll be able to figure out the packets that were dropped. Anyone know if this is what they did?

Wouldn't that be something like fountain codes?

Re: Increasing wireless network speed by 1000%, by replacing packets with algebra

#44

Post by ChuckMcM » Wed, Oct 24, 2012, 3:05 PM UTC

eru wrote: post #43

ChuckMcM wrote: post #12

Earlier quoted context omitted.

I was thinking the exact same thing. Oh look, someone had discovered forward error correction. Now if they can compute a series of code blocks over a rolling set of data blocks, that would be new. It would be like singing a round of "Row Row Row your Boat" but in data packets, just waiting and you'll be able to figure out the packets that were dropped. Anyone know if this is what they did?

Wouldn't that be something like fountain codes?

yes and no. So typically low density parity codes (aka fountain codes) break up a 'chunk' into some number of data blocks and some number of code blocks. Depending on the number of code blocks (its a tradeoff between time and number of blocks) you get 'most' of the blocks back and you can reconstruct the data blocks.

Now you could code up a packet, break it up and then add code blocks, that works great for the packet, but if you don't get enough blocks from that set of blocks you have to resend the packet which is something you don't want to do.

So if instead you send say 3 data blocks and 2 code blocks and then start sending two data blocks and 1 code block and set it up (this is the part that would be impressive) so that the previous two code blocks and the current one could reconstruct the two datablocks you just sent. (re-using previously sent code blocks) My brain is wincing trying to imagine the kind of ECC code that would be, sort of like solving the ECC polynomials in two dimensions or something.

Any way, if you could do that, the outcome would be that you could continually send data and dropped packets would always be correctable by later packets received. I drew out a picture of what relationship the code blocks would need and its complicated. Say you did an 8x3 (8 data segments, 3 code segments, you send

    D01 D02 C01 D03 D04 C02 D05 D06 C03 D07 D08 
    C04 D09 D10 C05 D11 D12 C06 D13 D14 C07 D15

And you do the math such that over any 11 pieces of that you can recover the 8 data pieces. Including:

    D05 D06 C03 D07 D08 C04 D09 D10 C05 D11 D12

(see what I did there? Data segments from both parts and code blocks from both parts).

Anyway, that would be some nice math if its doable. And really game changing, it would mean you would get less bandwidth in a situation where there was no packet loss (you're injecting ECC data). But it also makes me wonder if you don't just fix the underlying wireless protocol to do this with the frames sent, why does it have to be at the TCP level?

Re: Increasing wireless network speed by 1000%, by replacing packets with algebra

#45

Post by codex » Wed, Oct 24, 2012, 5:15 PM UTC

What's funny here is that wireless networks already use FEC at the physical layer. This just adds more, less conservative, FEC higher up for apps where it makes more sense to reduce throuhput and increase some average case latency to avoid worse case latency and worse case throughput.