Instability of sharing systems in the presence of retransmissions

DOI10.1007/S11134-015-9440-3zbMATH Open1325.60147arXiv1409.5622OpenAlexW2113025338MaRDI QIDQ747714FDOQ747714

Authors: Predrag R. Jelenković, Evangelia D. Skiani 

Publication date: 19 October 2015

Published in: Queueing Systems (Search for Journal in Brave)

Abstract: Retransmissions represent a primary failure recovery mechanism on all layers of communication network architecture. Similarly, fair sharing, e.g. processor sharing (PS), is a widely accepted approach to resource allocation among multiple users. Recent work has shown that retransmissions in failure-prone, e.g. wireless ad hoc, networks can cause heavy tails and long delays. In this paper, we discover a new phenomenon showing that PS-based scheduling induces complete instability with zero throughput in the presence of retransmissions, regardless of how low the traffic load may be. This phenomenon occurs even when the job sizes are bounded/fragmented, e.g. deterministic. Our analytical results are further validated via simulation experiments. Moreover, our work demonstrates that scheduling one job at a time, such as first-come-first-serve, achieves stability and should be preferred in these systems.

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

Recommendations

• Distribution of the number of retransmissions of bounded documents
• Stability of linear EDF networks with resource sharing
• Stability of Processor Sharing Networks with Simultaneous Resource Requirements
• Instability of SRPT, SERPT and SJF multiclass queueing networks
• Multistability in Queues with Retransmission and Its Relationship with Large Deviations in Branching Processes

zbMATH Keywords

non-preemptive schedulinginstabilities\(\mathrm{GI}/\mathrm{G}/1\) queuejob fragmentationretransmissionssharing systems

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Limit theorems in probability theory (60F99) Communication networks in operations research (90B18) Stochastic stability in control theory (93E15)

Cites Work

• Title not available (Why is that?)
• Waiting Time Distributions for Processor-Sharing Systems
• A survey on discriminatory processor sharing
• Sharing a Processor Among Many Job Classes
• Time-shared Systems
• Processor sharing: a survey of the mathematical theory
• Scheduling strategies and long-range dependence
• Large Deviation Analysis of Subexponential Waiting Times in a Processor-Sharing Queue
• Asymptotic Behavior of Total Times for Jobs That Must Start Over if a Failure Occurs
• Characterizing heavy-tailed distributions induced by retransmissions
• Distribution of the Number of Retransmissions of Bounded Documents
• Mathematical problems in the theory of processor-sharing queueing systems
• Is tail-optimal scheduling possible?

This page was built for publication: Instability of sharing systems in the presence of retransmissions

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