TY - GEN
T1 - Measuring the impact of adversarial errors on packet scheduling strategies
AU - Anta, Antonio Fernández
AU - Georgiou, Chryssis
AU - Kowalski, Dariusz R.
AU - Widmer, Joerg
AU - Zavou, Elli
N1 - Funding Information:
This research was supported in part by the Comunidad de Madrid grant S2009TIC-1692, Spanish MICINN/MINECO grant TEC2011-29688-C02-01, and NSF of China grant 61020106002.
PY - 2013
Y1 - 2013
N2 - In this paper we explore the problem of achieving efficient packet transmission over unreliable links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, we propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous error feedback with deferred error feedback, that requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The relative throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the relative throughput of the algorithms and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.
AB - In this paper we explore the problem of achieving efficient packet transmission over unreliable links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, we propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous error feedback with deferred error feedback, that requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The relative throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the relative throughput of the algorithms and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.
UR - http://www.scopus.com/inward/record.url?scp=84892964786&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84892964786&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-03578-9_22
DO - 10.1007/978-3-319-03578-9_22
M3 - Conference contribution
AN - SCOPUS:84892964786
SN - 9783319035772
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 261
EP - 273
BT - Structural Information and Communication Complexity - 20th International Colloquium, SIROCCO 2013, Revised Selected Papers
T2 - 20th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2013
Y2 - 1 July 2013 through 3 July 2013
ER -