Erasure 1 2 Codes slides by Gary Jackson 1 J Byers M Luby M Mitzenmacher and A Rege A Digital Fountain Approach to Reliable Distribution of Bulk Data Proc ACM SIGCOMM 98 28 4 56 67 Oct 1998 2 H Weatherspoon and J D Kubiatowicz Erasure Coding vs Replication A Quantitative Comparison Peer to Peer Systems First International Workshop IPTPS 2002 LNCS 2429 pp 328 337 2002 What is an Erasure Code Given a signal of m blocks recode to n blocks where n m Optimal reconstruct signal given any m unique blocks Suboptimal Reconstruct signal using 1 e m unique blocks Rate r m n and storage overhead is 1 r What are they used for Signals from deep space satellites Reliable multimedia multicasting Digital Fountain Reliable Storage Digital Fountain Problem Transmitting a fixed set of data to multiple clients over unreliable links Previous solution transmit original data interleaved with erasure coded blocks But this has undesirable overhead Ideal Solution Reliable client always gets the whole file Efficient extra work is minimized On demand client gets the file at their discretion Tolerant solution is tolerant of clients with different capabilities Solution Digital Fountain Server transmits constant stream of encoding packets Client succeeds when minimal number of packets are received Assumes fast encode decode Building a Digital Fountain Use Tornado erasure codes because they are fast However they are suboptimal Reconstruction requires 1 m packets or 1 k packets in the paper s terminology Tornado Codes Reed Solomon codes over specified system of polynomials over some finite field y Px Tornado codes system of equations like y x x x x y y y y n i m o j k p l q Comparison Tornado codes appear to be much more efficient asymptotically and use a much faster basic operation XOR But they have overhead Example Tornado Z G1 truncated heavy tail distribution to greater portion of right side x1 xm y1 ym 2 G2 every node on left has out degree of two connecting to remainder of right side S Specially selected graph to connect second layer of redundancy G1 G2 ym 2 1 ym S Runtime Comparison Simulation Set up Compare two schemes Tornado Interleaving Compare two variables performance encode decode time inefficiency ratio of data needed to optimal Interleaving Scheme Divided total message of size K in to B K k blocks each of which is size k Erasure code each block Interleave encoded blocks with data in transmission Choice of k is important Needs to be small for efficient encoding decoding But the smaller it is the more overhead there will be when receiving there is a greater likelihood that we will have to wait longer and receive more duplicate packets to reconstruct any given block What happens when inefficiency is equal Decoding times are inferior for the interleaving scheme when decoding times are equal Inefficiency grows faster with the interleaved scheme These results scale with the size of the file as well as with real trace data Implementation Idea Compare conventional multicast fountain versus layered multicast fountain Basis for comparison is the reception inefficiency total packets used packets Layered Multicast Clients can subscribe to layers of varying rate Clients at higher layers get everything at the lower layers Scheme for moving up and down in the layer hierarchy as conditions change Scheduling across multiple layers One Layer Property assuming fixed level and low packet loss then signal can be reconstructed before duplicates are seen One Layer Property scheme exists for any set of layers Result Reception inefficiency is higher at lower packet loss levels on the 4 layer scheme than on the single layer scheme Erasure Coding vs Replication Premise Erasure codes are good Can the benefit over a replication scheme be quantified Assumptions Uniform environment independently identically distributed failing disks Repair is done on a polling basis not on an interrupt basis Have to check for problems Availability For N 106 M 105 n 2 m 1 P 0 99 n 32 m 16 P 0 999999998 Same overhead 0 0 Conclusion fragmentation increases availability System Comparison Fix certain parameters and see what happens Important parameters MTTF average time before some component fails B number of blocks we care about S total size including overhead BW bandwidth D disk seeks e Repair Epoch period of block verification Fix MTTF and Repair Epoch Keep 100 petabytes of data for 1000 years Result replicated system needs 11x size bandwidth and disk seeks that the erasure coded system needs Fix Storage and Repair Epoch How long can we keep some block Result a given block has an MTTF of 74 years in a replicated system and 10 20 years in an erasure coded system Fix MTTF and Storage Overhead Keep 1000 blocks for 1000 years Result Erasure coded system needs a 28month repair epoch Replicated system needs near instantaneous repair epoch Observation Not using the same sized problem for all comparisons Discussion Future Work Performance should be addressed separately from reliability Need to address failure independence efficient repair it takes a long time to sift through a petabyte of data Conclusion Erasure coded fragments increase MTTF with lower storage bandwidth and disk seek requirements than the requirements for replicated systems Questions Q How do you decide what an optimal r would be A It depends on the other constraints of the application If you expect a higher failure rate you ll need a lower value for r to maintain the ability to reconstruct the signal Questions Q Does erasure coding offer the flexibility to change the rate after it is chosen A There is something called a fountain code or a rateless erasure code http en wikipedia org wiki Rateless erasure codes These can produce as many encoded blocks as one needs but generally require 1 m blocks to recover the signal just like Tornado codes Questions Q Are Tornado codes still used today A Digital Fountain was commercialized They now use a rateless proprietary erasure code called Raptor Questions Q Is there a version of the algorithm that allows for flawed packets but still able to reconstruct the original content A I m not sure I understand the question Generally broken packets are considered lost Questions Q What are unicast multicast and broadcast A Unicast transmitting to a single client Multicast transmitting to subscribed clients Broadcast transmitting to everyone Questions Q What are redundant codewords A Redundant codewords are just the erasure coded blocks as opposed to the