Report

Instantly Decodable Network Codes for Real-Time Applications Presented by Marios Gatzianas Anh Le, Arash Tehrani, Alex Dimakis, Athina Markopoulou UC Irvine, USC, UT Austin Real-Time Applications with Wireless Broadcast Real-time applications that use wireless broadcast: • Live video streaming • Multiplayer games Unique characteristics: • Strict deadlines • Loss tolerant Problem: Retransmissions in the presence of loss 2 Broadcast Loss Recovery for Real-Time Applications Strict deadlines: • Instantly decodable network codes (IDNC) Loss tolerant: • We formulate Real-Time IDNC What is a coded packet that is instantly decodable and innovative to the maximum number of users? 3 Related Work • Instantly decodable, opportunistic codes [Katti ’08] [Keller ’08] [Sadeghi ’09] [Athanasiadou ’12] • IDNC focuses on minimizing the completion delay [Sorour ’10, 11, 12] • Index coding and data exchange problems [Birk ’06] [El Rouayheb ’10] 4 Our Contributions We show Real-Time IDNC is NP-Hard • Equivalent to finding a Max Clique in an IDNC graph • Provide a reduction from Exact Cover by 3-Sets Analysis of instances with random loss probabilities • Provide a polynomial time solution for Random Max Clique and Random Real-Time IDNC 5 Outline 1. Real-Time IDNC • Equivalence to Max Clique • NP-Hardness 2. Random Real-Time IDNC • Optimal coded packet (clique number) • Coding algorithm 6 Real-Time IDNC: Problem Formulation - A set of m packets, broadcast by a source - n users, interested in all packets - Each user received only a subset of packets - To recover loss: What is a coded packet that is instantly decodable and innovative to the maximum number of users? 7 Real-Time IDNC: Example - 6 packets: p1 , … , p6 - 3 users: u1 , u2 , u3 p1 p2 p3 p4 p5 p6 • u1 has p1 , p2 0 0 1 1 1 1 • u2 has p3 , p5 1 1 0 1 0 1 • u3 has p3 , p6 1 1 0 1 1 0 p5 + p6 is instantly decodable and innovative to u2 and u3 p2 + p3 is instantly decodable and innovative to all users 8 Mapping: Real-Time IDNC to Max Clique Real-Time IDNC ≡ Max Clique in IDNC graph 9 Real-Time IDNC is NP-Hard Real-Time IDNC ≡ Integer Quadratic Programming (IQP) IQP is NP-Hard: reduction from Exact Cover by 3-Sets Real-Time IDNC ≡ Max Clique ≡ IQP NP-Hard 10 Outline 1. Real-Time IDNC • Equivalence to Max Clique • NP-Hardness 2. Random Real-Time IDNC • Optimal coded packet (clique number) • Coding algorithm 11 Random Real-Time IDNC Setup: iid loss probability p • aij = 1 with probability p Analysis sketch: • Fix a set of j columns • Define a good row as having one 1 among these j columns o A row is good with probability f(j) = j p (1-p) j-1 o Number of good rows has Binomial distribution: Bin(n, f(j)) 12 Analysis of Random Real-Time IDNC Lemma 5 (sketch): The size of the maximum clique that touches j columns is close to the number of good rows w.r.t. these j columns Lemma 6 (sketch): The size of the maximum clique that touches j columns concentrates around n f(j) Theorem 7 (sketch): Maximum clique, that touches any j columns, has size concentrating around n f(j) 13 Analysis of Random Real-Time IDNC (cont.) Corollary 8: The maximum clique touches j* columns, where j* = argmax f(j) Observations: • j* is a constant for a fixed loss rate p • j* increases as loss rate p decreases (more packets should be coded together) 14 Max-Clique Algorithm Observations: • The maximum clique concentrates around n f(j*) • j* is a constant for a fixed loss rate p Polynomial-time algorithm to find the maximum clique and optimal coded packet: • Examine all cliques that touch j columns for all j δ-close to j* • Complexity: O (n m j* + δ ) 15 Evaluation Results Simulation with random loss rate (20 users, 20 packets) Max-Clique outperforms all other algorithms at any loss rate 16 Conclusion We formulate Real-Time IDNC • Equivalent to Max Clique in IDNC graph • NP-Hard proof Analysis of Random Real-Time IDNC • Polynomial time solution to find max clique and optimal coded packet 17