Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

extremetech.com

Post reply on HN
Print view View original

21–30 of 45 posts

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

#21

Post by mrb »

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.

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

#22

Post by guelo »

tptacek wrote: post #18
guelo wrote: post #11

Ugh, remember when academia helped create the internet by releasing free publicly available unlicensed RFCs? Edit: Not RFPs, duh

I'm not sure I remember how each successive advancement in signaling from 802.3-coax through 10gbE through gigabit wireless was driven by public RFCs.

That's a good point since most networking standards were developed under the IEEE which was always more industry oriented than the IETF, I think they're both mostly industry players at this point. But still, there is a rich history of free contributions by academia which I think is rarer today.

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

#23

Post by jwm »

cbhl wrote: post #17
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…

I wonder what's so proprietary about their algorithm. I'd assume it's just Reed–Solomon coding on a UDP tunnel (or, alternatively, modifying TCP to accept partially mangled-packets if FEC is successful).

This could be demo'd very easily by gluing together:

udpcast (http://www.udpcast.linux.lu/satellite.html) -> Sends/receives files over UDP. Supports FEC.

netcat -> Join file I/O (from udpcast) to local TCP/UDP sockets

openvpn / iptables userspace -> Provide connection routing.

Seems like an evenings work.

Edit: udpcast might not be suitable for this. I am surprised noone has already built a simple UDP FEC tunnel program...

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

#24

Post by jwm »

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.

> 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.

Interestingly, this tool looks like it is useful for the problem you describe:

http://www.udpcast.linux.lu/satellite.html

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

#25

Post by loeg »

codex wrote: post #14

Isn't the downside of FEC encoded packets increased latency? Instead of sending each packet immediately, don't you need to accumulate n packets to encode as a group? Or does the math allow incremental encoding? Simple parity is incremental, but the FEC on DSL lines always added 40ms of latency.

40ms extra latency on wifi is nothing compared to packet loss.

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

#27

Post by dnos »

I'm not up-to-date on networking technologies, but it's surprising to me that some sort of error correction hasn't already been made a standard yet.

I wonder if something along the lines of old-school Parity files would work in the packet world? Basically just blast out the packets and any that were lost, you just reconstruct using the meta-data sent with the other packets.

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

#28

Post by mrb »

jwm wrote: post #24
mrb wrote: post #21

Earlier quoted context omitted.

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.

> 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. Interestingly, this tool looks like it is useful for the problem you describe: http://www.udpcast.linux.lu/satellite.html

Yup. I remember looking at udpcast. I did not select it because, amongst other things, it did not support encryption. And I don't think we could use IPsec.

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

#29

Post by delinka »

I see lots of comments talking about FEC. That's not how the article reads to me. Granted the author (or I?) may be completely out in left field, but here's my take on what it says:

Let's suppose you have a mathematical process that outputs a stream of [useful] data. The description of the process is much, much smaller than the output. You can "compress" the data by sending the process (or equation) instead. Think π. Do you transmit a million digits of π or do you transmit the instruction "π to a million digits"? The latter is shorter.

Now, reverse the process: given an arbitrary set of data, find an equation (or process) that represents it. Not easy for sure. Perhaps not possible. I recall as a teenager reading an article about fractals and compression that called on the reader to imagine a fractal equation that could re-output your specific arbitrary data.

If I've totally missed the article's point, please correct me, but explain why it also talks about algebra.

EDIT: I re-read and noticed this: "If part of the message is lost, the receiver can solve the equation to derive the missing data." I can see the FEC nod here.

Guh. I guess I'm blind tonight. "Wireless networks are in desperate need for forward error correction (FEC), and that’s exactly what coded TCP provides." I cannot for the life of me understand why they'd need to keep this a secret.

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

#30

Post by codex »

loeg wrote: post #25
codex wrote: post #14

Isn't the downside of FEC encoded packets increased latency? Instead of sending each packet immediately, don't you need to accumulate n packets to encode as a group? Or does the math allow incremental encoding? Simple parity is incremental, but the FEC on DSL lines always added 40ms of latency.

40ms extra latency on wifi is nothing compared to packet loss.

Really? My wifi RTT to the metropolitan core is 15 ms, and over LTE it is 47 ms. Not a worthwhile tradeoff at 40 ms unconditional additional RTT delay.

I imagine the higher latency was used to offset lower bandwidth due to FEC encoding loss, by amortizing it over more bits.

Post reply on HN