Code Poetry
and Text Adventures

by catid posted (>30 days ago) 12:53am Thu. Feb 13th 2014 PST
The Longhair project ( http://github.com/catid/longhair ) is a pretty good example of a fast UDP packet erasure code.  It is fast for the range of values that are most useful for real-time video/games.

The way I imagined applying the Longhair codec is to switch to a new code every RTT/2 seconds.  Let's call this the "RTT/2-switch" method.  In this method redundant data from the previous code group is interspersed into the next one.  This way only one encoder object needs to be running at a time.  When used in this way, the worst-case recovery time is the RTT, because a lost packet at the start of the code group may be finally delivered when the last recovery packet is sent roughly RTT seconds later.  The best-case performance of this method would be almost instant, because in the best case, the last packet of the code group is lost, and the first redundant packet fills in that gap.

Worst-case recovery time of RTT is pretty good.  This is the best-case ARQ recovery time possible.  But I think there is a better way that has even lower latency! =)

Instead of having disjoint code groups, why not have the code groups overlap?  I'm calling this property "memory."  It means that a redundant packet "remembers" information about the last H (for History) packets.  If a packet is older than H packets, then the redundant packet cannot help.  And every time a new redundant packet is sent, it contains information about some set of packets that came before it.

Working it out on paper, it looks like this approach has lower worst-case latency than the RTT/2-switch method.  In fact the latency appears to be the smallest possible with any sort of delivery mechanism.

Over Wirehair the recovery is not probabilistic, it is guaranteed if enough packets are received.  Furthermore it is likely to run faster than Wirehair while using less memory.  This means that for a lot of cases, RaptorQ is also not the best solution, ie. for video streaming, as Wirehair is a similar or better codec than RaptorQ.

So how can it be constructed?

My initial idea was to build a really large CRS matrix (like in Longhair) and then modify it.

To simplify the discussion without loss of generality imagine data being sent at a fixed rate.  Every 3 original packets one redundant packet is sent.

Then let's choose a memory (H) for the code.  From what I've worked on before it seems like it's important for H to be longer than the longest expected recoverable outage.  For example if a burst loss can be no longer than 100 ms, then 100 ms of packets is a good idea for H.  So for the sake of discussion I also need to know the data rate.  Let's say 5 original packets are sent every 100 ms for roughly 65 KB/s of bandwidth.  And the redundant packets add 22 KB/s at the rate I've specified.  Clearly I'm sacrificing bandwidth for lower packetloss in this example.

Here is the scenario graphically represented:

Original Data: 0 1 2 [r0] 3 4 5 [r1] 6 7 8 [r2] 9 10 11 [r3]
r0:            A B C      0 0 0      0 0 0      0  0  0
r1:            0 D E      F G H      0 0 0      0  0  0
r2:            0 0 0      0 I J      K L M      0  0  0
r3:            0 0 0      0 0 0      0 N O      P  Q  R

Note all the zeroes!  This is what I meant by modified CRS codes.  Normally those would be filled in with non-zero GF(256) values to make an invertible Cauchy matrix.

It achieves the property that in a single loss, recovery is possible at the VERY NEXT redundant packet.  Perfect!

And with this amount of extra redundancy, it can recover from 2 losses anywhere by the second redundant packet.  Nice!

And 3 losses in a row are recoverable in some cases such as if 2, 3, 4 above are lost.  Then r0, r1, and r2 would work together to fix the data.  Note that 3 losses are never recoverable without a huge amount of extra latency in the RTT/2-switch scheme.  So this actually improves the quality of the error correction in addition to lowering latency.  Wow, totally unexpected!

So I think I have a way to generate these matrices that is somewhat clever and new.  Generating the Cauchy matrix is done by picking non-repeating configurations of X[], Y[] and setting each element at i,j to 1 / (X[j] + Y[i]).  So it seems that as long as *nearby* rows and columns do not repeat, I can reuse values of X[] and Y[].  This is great because some values for X[] and Y[] are better than others: They can yield fewer ones in the 8x8 bitmatrix representation (like in Longhair/Jerasure CRS codes) of each element in the matrix, which leads to a faster codec.  For instance it would be great to periodically have a row of all 1s once the opportunity arises again.

Conceptually this leads to a roughly diagonal matrix that goes on forever, cycling through the most optimal patterns of Cauchy matrix rows.  Like a rainbow road.  If the chain is ever broken by too much loss, once that loss is "forgotten" (out of the memory of the code), then the code resumes being good at recovering data again.  Interestingly this causes the same latency for switching codes as overlapped ones, so this is not a regression.

Yo dawg.  What if I protected the r0, r1, r2 packets with more erasure codes?  This is sort of how Wirehair works, by the way.

Protecting the redundant symbols with more redundant symbols seems to introduce unwanted latency.  For example if there was a super-code that protected the "r0, r1, r2" values then it would need to wait for r0, r1, r2 to be emitted, which would delay recovery of the original data.  Another approach could be to try to include r0 as input for r1.  The problem with this is that if r0 is lost, then r1 cannot recover an additional loss of original data that is more important to fix.  Even if I could recover r0 from r1, it would just be useful for recovering even older data, which is not too exciting because it's supposed to be low-latency.
last edit by catid edited (>30 days ago) 10:41am Thu. Feb 13th 2014 PST
by catid posted (>30 days ago) 11:10am Wed. Oct 29th 2014 PDT
Originally posted by :

Sure please contact me via the Email link at the bottom =)
by (Anonymous) posted (>30 days ago) 2:43pm Thu. Aug 28th 2014 PDT