6 ms·

Went looking for fountain codes, was not disappointed [1]. It's a shame these have been locked up for so long -- there's a lot of network infrastructure that co

Went looking for fountain codes, was not disappointed [1]. It's a shame these have been locked up for so long -- there's a lot of network infrastructure that could be improved by them. The patents are hopefully expiring soon. Generic tornado codes are likely patent free, having been expired for a few years now: https://en.wikipedia.org/wiki/Tornado_code https://en.wikipedia.org/wiki/Tornado_code EDIT: looking a bit deeper into this repo, it's really just a wrapper over the raptorq crate with a basic UDP layer on top. Nothing really novel here that I can see over `raptorq` itself. [1] https://crates.io/crates/raptorq https://crates.io/crates/raptorq

bb88 2y ago
> There's a lot of network infrastructure that could be improved by them. One killer feature was multicast streaming of data. The streaming could do an extra 5% of broadcasting packets instead of several round trips and retransmissions. Now that I think about it, I wish we actually used multicast.
- ddingus 2y ago
  Me too. SGI had good support for it in IRIX and I am pretty sure I saw one video streaming solution using it on a LAN to maximize the throughput possible. Seems like a good tech that fell into disuse.
  - vermilingua 2y ago
    IP CCTV and IP TV (think hotels) make extensive use of multicast, it's not completely disused; but only practical on LAN.
    - ddingus 2y ago
      Good to know. That was basically the use case for it back in the day too. Multiple video streams.
- zamadatix 2y ago
  The hard part about multicast is the scaling overhead of coordinating which streams should go where when it's more than "these couple things on these couple networks". Even then, the way it's a dedicated range of IPs instead of parts of public assignments pretty much shut down the idea it could ever be coordinated at scale outside of a few private networks doing it together. It has found good success in IPTV delivery inside provider's own networks though. Cameras at casinos/hotels/Transit systems and the like too.
  - xxpor 2y ago
    Copying packets is brutal in software as well.
    - zamadatix 2y ago
      Pushing packets in software is generally brutal but multicast/broadcast should be inherently easier. It's less "copy this packet 27 times" and more "instead of receiving 27 packets and sending 27 packets you receive 1 packet and send it 27 times before you remove it from memory". The "hard" part becomes dealing with the queues filling up because you're inherently able to churn out so much more data than you're able to receive vs unicast.
  - elcritch 2y ago
    Ipv6 works much better with multicast. I learned about it a few years back and it's actually core to the ipv6 protocol. That means all ipv6 routers must support multicast. There's 2^112 possible global multicast addresses with ipv6 as well (1). Though yeah, you'll still have queuing overloads as well and other issues. 1. https://learningnetwork.cisco.com/s/question/0D53i00000Kt0EKCAZ/ipv6-multicast-address-ccna https://learningnetwork.cisco.com/s/question/0D53i00000Kt0EK...
    - wmf 2y ago
      all ipv6 routers must support multicast That doesn't help if all routers have it turned off.
    - 2y ago
raggi 2y ago
If you're curious about the RFC IPR: https://datatracker.ietf.org/ipr/2554/ https://datatracker.ietf.org/ipr/2554/
xarope 2y ago
TIL about fountain codes and raptor. Thanks! I wonder if it opens up new opportunities erasure coding replacements, e.g. RAID for disks, PARQ2 for data recovery, or as Reed-Solomon replacements for comms?
- nullc 2y ago
  These sorts of codes are not really the thing you want for RAID-N. They work best with coding groups of thousands of packets or more. For adding redundant blocks to a read-mostly/only file (e.g. to correct for sector errors) they could be useful indeed. as that's a case where you might have a few dozen correction packets protecting millions. I'd really like to see some FS develop support for file protection because on SSDs I'm seeing a LOT more random sector failures that disk failures. RS codes are optimal for erasures so you really only want to use something else where there are so many packets in the group that RS code performance would be poor... or where a rateless code would be useful.
- bb88 2y ago
  For comms it's better since raptorq can generate a large number of symbols. One use would be a TCP replacement. If a file can be transmitted in 100 TCP packets, and there's 10% loss on the link, then the client needs to retry the lost packets in order. With raptorq, the client needs to receive 102 packets (I believe). And this can be any combination of original 100 packets and the large number of potential recovery packets.

bb88 2y ago

> There's a lot of network infrastructure that could be improved by them. One killer feature was multicast streaming of data. The streaming could do an extra 5% of broadcasting packets instead of several round trips and retransmissions. Now that I think about it, I wish we actually used multicast.

ddingus 2y ago
Me too. SGI had good support for it in IRIX and I am pretty sure I saw one video streaming solution using it on a LAN to maximize the throughput possible. Seems like a good tech that fell into disuse.
- vermilingua 2y ago
  IP CCTV and IP TV (think hotels) make extensive use of multicast, it's not completely disused; but only practical on LAN.
  - ddingus 2y ago
    Good to know. That was basically the use case for it back in the day too. Multiple video streams.
zamadatix 2y ago
The hard part about multicast is the scaling overhead of coordinating which streams should go where when it's more than "these couple things on these couple networks". Even then, the way it's a dedicated range of IPs instead of parts of public assignments pretty much shut down the idea it could ever be coordinated at scale outside of a few private networks doing it together. It has found good success in IPTV delivery inside provider's own networks though. Cameras at casinos/hotels/Transit systems and the like too.
- xxpor 2y ago
  Copying packets is brutal in software as well.
  - zamadatix 2y ago
    Pushing packets in software is generally brutal but multicast/broadcast should be inherently easier. It's less "copy this packet 27 times" and more "instead of receiving 27 packets and sending 27 packets you receive 1 packet and send it 27 times before you remove it from memory". The "hard" part becomes dealing with the queues filling up because you're inherently able to churn out so much more data than you're able to receive vs unicast.
- elcritch 2y ago
  Ipv6 works much better with multicast. I learned about it a few years back and it's actually core to the ipv6 protocol. That means all ipv6 routers must support multicast. There's 2^112 possible global multicast addresses with ipv6 as well (1). Though yeah, you'll still have queuing overloads as well and other issues. 1. https://learningnetwork.cisco.com/s/question/0D53i00000Kt0EKCAZ/ipv6-multicast-address-ccna https://learningnetwork.cisco.com/s/question/0D53i00000Kt0EK...
  - wmf 2y ago
    all ipv6 routers must support multicast That doesn't help if all routers have it turned off.
  - 2y ago

raggi 2y ago

If you're curious about the RFC IPR: https://datatracker.ietf.org/ipr/2554/ https://datatracker.ietf.org/ipr/2554/

xarope 2y ago

TIL about fountain codes and raptor. Thanks! I wonder if it opens up new opportunities erasure coding replacements, e.g. RAID for disks, PARQ2 for data recovery, or as Reed-Solomon replacements for comms?

nullc 2y ago
These sorts of codes are not really the thing you want for RAID-N. They work best with coding groups of thousands of packets or more. For adding redundant blocks to a read-mostly/only file (e.g. to correct for sector errors) they could be useful indeed. as that's a case where you might have a few dozen correction packets protecting millions. I'd really like to see some FS develop support for file protection because on SSDs I'm seeing a LOT more random sector failures that disk failures. RS codes are optimal for erasures so you really only want to use something else where there are so many packets in the group that RS code performance would be poor... or where a rateless code would be useful.
bb88 2y ago
For comms it's better since raptorq can generate a large number of symbols. One use would be a TCP replacement. If a file can be transmitted in 100 TCP packets, and there's 10% loss on the link, then the client needs to retry the lost packets in order. With raptorq, the client needs to receive 102 packets (I believe). And this can be any combination of original 100 packets and the large number of potential recovery packets.