Measuring the impact of adversarial errors on packet scheduling strategies

DOI10.1007/978-3-319-03578-9_22zbMATH Open1341.90045arXiv1306.1769OpenAlexW2809237793MaRDI QIDQ282242FDOQ282242

Authors: Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, Joerg Widmer, Elli Zavou 

Publication date: 12 May 2016

Published in: Journal of Scheduling, Structural Information and Communication Complexity (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1306.1769

Recommendations

• Measuring the impact of adversarial errors on packet scheduling strategies
• Online packet scheduling under adversarial errors
• Online packet scheduling under adversarial jamming
• Effective routing and scheduling in adversarial queueing networks
• On packet scheduling with adversarial jamming and speedup

zbMATH Keywords

competitive analysisadversarial errorsasymptotic throughputerror feedback mechanismspacket schedulingunreliable link

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Communication networks in operations research (90B18)

Cites Work

• Competitive queue policies for differentiated services
• Title not available (Why is that?)
• Buffer Overflow Management in QoS Switches
• FIFO queueing policies for packets with heterogeneous processing
• Title not available (Why is that?)
• Scheduling. Theory, algorithms, and systems.
• Online bin packing with resource augmentation
• Measuring the impact of adversarial errors on packet scheduling strategies
• Dynamic packet scheduling in wireless networks
• Online packet scheduling under adversarial jamming
• Scheduling over a time-varying user-dependent channel with applications to high-speed wireless data
• Competitive throughput in multi-hop wireless networks despite adaptive jamming
• Continuous error detection (CED) for reliable communication
• Optimal smoothing schedules for real-time streams (extended abstract)
• A near-optimal memoryless online algorithm for FIFO buffering two packet classes
• Error control coding. Fundamentals and applications
• Mixed Criteria Packet Scheduling
• Probability and Computing

Cited In (7)

• Online packet scheduling under adversarial errors
• Measuring the impact of adversarial errors on packet scheduling strategies
• On packet scheduling with adversarial jamming and speedup
• Online packet scheduling under adversarial jamming
• Adaptive scheduling over a wireless channel under constrained jamming
• Adaptive packet scheduling over a wireless channel under constrained jamming
• Fault tolerant scheduling of tasks of two sizes under resource augmentation

This page was built for publication: Measuring the impact of adversarial errors on packet scheduling strategies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q282242)