Lecture 17: Coding, Error Detection andCorrectionErrors and Losses• Physical layers use encoding to protect link layerfrom chip errors• All or nothing: if chip errors exceed layer 1robustness, you lose the whole packet (bad CRC)• We can use these techniques at higher layers aswell: erasure coding- Encoding data of length L as k symbols: any n of the ksymbols can regenerate the original data (n ≥ L).Cyclic Redundancy Check (CRC), revisited• Distill n bits of data into a c bit CRC, c << n• Can’t detect all errors (2−cchance another packet’sCRC matches)• CRCs are designed to detect certain forms of errorsmore than others- Assured to detect bursts of bit errors shorter than c- E.g., flip one bit, there will be a different CRC valueMessage Authenticaion Codes• When sending packets securely (confidentially),sometimes you use a Message AuthenticationCode (MAC) instead of a CRC• Kind of like a CRC, but seeded with a secret• MAC needs different properties to be strongagainst attackers- If any bit in the message changes, each bit in the MACneeds to have an equal probability of being 0 or 1- Starting with packet P , can’t append data and generatenew MAC- Can flip a bit and get the same MAC valueCyclic Redundancy Check, continued• Can be computed iteratively (e.g., as a packet isspooled out)• Mathematical basis- CRC of length n computed as an nth degree polynomial- CRC of length n is remainder after dividing message by anumber k > 2n- k = 25, k = 11001, x4+ x3+ x0• To detect burst errors of length b, n > bFields• A set of numbers of which you can add, subtract,multiply, and divide• A field can be finite (Galois Field)• E.g., Galois Field GF (p) field of integers modulo p,p is prime• In GF (7), 6 + 3 = 2Reed-Solomon• Standard erasure coding technique: used in CDs• Core idea: any k distinct data points define aunique polynomial of degree k − 1• Data to transmit defines the polynomial P• Compute coded data C = P (x) for x0, x1, xn• Transmit C• A receiver that gets k different xnvalues canreconstitute original polynomial (and data)Power of Erasure Coding• Make data k − 1 term polynomial• Compute n data points, where n > k• Any k data points can successfully regenerate data• Can tolerate n − k losses, orn−k2errors• Known errors/losses are called erasures: erasurecodingCode Word Sizes• Large polynomials lead to large values: 63 · 1910!• Reed-Solomon works on fields• GF(256), 63 · 1910= 106• Reed-Solomon uses GF(256);• Sends 223 data symbols, 32 symbols are parityvalues (223,255)• 8 bits can have very efficient implementationsError Burstiness• Reed-Solomon divides data into code symbols(e.g., 8 bits)• Any one bit error invalidates that symbol• Robust to bursts of errors, weaker against randomerrors• Big bursts can overwhelm the code: CDs useCross-Interleaved Reed-Solomon Coding (CIRC)to spread errors across symbol blocksReed-Solomon• Useful for making media more resilient: operateson small datum• Increasing the coding factor k increasesrobustness: can be made robust to arbitrary losses• Is there some way to do something similar on largedata (e.g., packets?)Erasure Codes, Revisited• Data of length k• Erasure codes can regenerate data from anyk(1 + γ) code symbols• Do not necessarily handle errors• Perfect world, γ = 0 (not possible in practice)• Also want decoding to be fast/simpleProblem Statement• Have a large piece of data• Want to deliver it to many client nodes• Do not want to maintain per-client state• Goal: send packets, any k packets can reconsitutedata with very high probability• Example: television over IPWhy Not Reed-Solomon• We’re operating on a very large piece of data• Can deal with larger chunks than Reed-Solomon• Allows us to do something simpler?LT Codes• Data of length N• Code words of length l, any l will do!• Break data into k = ⌈DL⌉ chunks C• Each transmitted packet Ciis an XOR of somenumber of random chunks• Symbol generation is O(ln(k/δ)) on average• Requires k + O(√k ln2(k/δ)) symbols to decodewith probability 1 − δPower of XOR• Data A, B, C, D• Have x0= A, x1= A ⊕ B, x2= A ⊕ C, x3= C ⊕ D• A = x0• B = A ⊕ x1• C = A ⊕ x2• D = C ⊕ x3XOR, VisuallyHow to XOR?• How LT codes XOR the data into code words iscritical• d(Ci) is the degree of codeword i: how many dataitems are XORed in it• Example bad distributions- ∀Ci, d(Ci) = 1: sending data in the clear- ∀Ci, d(Ci) = k −1: each codeword is the XOR of all but onedata symbol- Both have k unique code words, and require receiving all kCodeword DegreeLT Decoding Algorithm• We receive n codewords• Initially, all input symbols are uncovered• Each codeword with d = 1 covers the input symbol• Ripple: set of covered input symbols that have notbeen processed• For each symbol in the ripple- Scan across the codewords and remove it from those thathave it (via XOR), reducing degree by 1- If codeword has degree 1, cover its input symbolLT Decoding• Decoding stops when the ripple is size 0- If all input symbols are covered, success- If any input sybmols are uncovered, failure• How big should the ripple be?- Small, so there is low redundancy in coverage- Never zero, because that halts decoding• Control ripple size through degree distribution ρ2-minute breakLT Encoding• Two goals- Minimize number of needed encoding symbols (bps)- Minimize average degree of encoding symbols (CPU cycles)• Step through three examples:- All-at-once: ρ(1) = 1- Ideal: ρ(1) = 1/k, ρ(i) = 1/i(i − 1)- Robust: more on this laterAll-at-once• How many encoded symbols does it take?• Bins and balls: how many balls must be thrown toensure that there is one in each of k bins?• O(k · ln(k/δ)) for probability 1 − δ• Requires ln(k/δ) factor (on average ln(k))• k = 1000, δ = 0.01%, ln(107) = 16Ideal distribution• ρ(1) = 1/k, ∀i, i = 2, . . . , k, ρ(i) = 1/i(i − 1)• Expected behavior is perfect: one input has a d of1, each cover releases another symbol• Requires k symbols, sum of degrees is k · ln(k)• Same sum of degrees as all-at-once, but only ksymbolsThe World Is Not Ideal• “However, this heuristic analysis makes thecompletely unrealistic assumption that theexpected behavior is the actual behavior, and thisis far from the truth. In fact, the Ideal Solitondistribution works very poorly in practice becausehe expected size of the ripple is
View Full Document
Unlocking...