Measuring the impact of adversarial errors on packet scheduling strategies
Date
2016ISSN
1094-6136Source
Journal of SchedulingVolume
19Issue
2Pages
135-152Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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 to measure the efficiency of scheduling strategies in such a setting. To this end, we propose an asymptotic 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 with deferred error feedback, which 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 asymptotic throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the metric 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. © 2015, Springer Science+Business Media New York.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Article
Measuring the impact of adversarial errors on packet scheduling strategies
Fernández Anta, Antonio; Georgiou, Chryssis; Kowalski, D. R.; Widmer, J.; Zavou, Elli (2013)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 ...
-
Article
PADS: An approach to modeling resource demand and supply for the formal analysis of hierarchical scheduling
Philippou, Anna; Lee, I.; Sokolsky, O. (2012)As real-time embedded systems become more complex, resource partitioning is increasingly used to guarantee real-time performance. Recently, several compositional frameworks of resource partitioning have been proposed using ...
-
Conference Object
Scheduling workflows with budget constraints
Sakellariou, R.; Zhao, H.; Tsiakkouri, E.; Dikaiakos, Marios D. (Springer Science and Business Media, LLC, 2007)Grids are emerging as a promising solution for resource and computation demanding applications. However, the heterogeneity of resources in Grid computing, complicates resource management and scheduling of applications. In ...