Recovery of Packet Losses in Wireless Broadcast for Real-Time Applications
| Autor: | Athina Markopoulou, Arash Saber Tehrani, Alexandros G. Dimakis, Anh Le |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computer Networks and Communications
business.industry Computer science Network packet Real-time computing 020206 networking & telecommunications 020302 automobile design & engineering 02 engineering and technology Broadcasting Wireless broadcast Computer Science Applications 0203 mechanical engineering Packet loss Linear network coding 0202 electrical engineering electronic engineering information engineering Wireless Electrical and Electronic Engineering business Software Computer network |
| Zdroj: | IEEE/ACM Transactions on Networking. 25:676-689 |
| ISSN: | 1558-2566 1063-6692 |
| Popis: | We consider the scenario of broadcasting for real-time applications, such as multi-player games and video streaming, and loss recovery via instantly decodable network coding. The source has a single time slot or multiple time slots to broadcast (potentially coded) recovery packet(s), and the application does not need to recover all losses. Our goal is to find packet(s) that are instantly decodable and maximize the number of lost packets that the users can recover. First, we show that this problem is equivalent to the unique coverage problem in the general case, and therefore, it is hard to approximate. Then, we consider the practical probabilistic scenario, where users have i.i.d. loss probability and the number of packets is either constant (video streaming), linear (multi-player games), or polynomial in the number of users, and we provide two polynomial-time (in the number of users) algorithms. For the single-slot case, we propose Max Clique , an algorithm that provably finds the optimal coded packet w.h.p. For the case where there is a small constant number of slots, we propose Multi-Slot Max Clique , an algorithm that provably finds a near-optimal solution w.h.p. when the number of packets is sufficiently large. The proposed algorithms are evaluated using both simulation and real network traces from an Android multi-player game. And they are shown to perform near optimally and to significantly outperform the state-of-the-art baselines. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|