Instability of sharing systems in the presence of retransmissions
Retransmissions represent a primary failure recovery mechanism on all layers of communication network architecture. Similarly, fair sharing, for example, processor sharing (PS), is a widely accepted approach to resource allocation among multiple users. Recent work has shown that retransmissions in failure-prone, for example, 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, for example, 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 a larger stability region and should be preferred in these systems.
instabilities retransmissions fair sharing processor sharing restarts discriminatory processor sharing non-preemptive scheduling gi/g/1 queue job fragmentation 60k25 68m20 93e15 60f99 90b18