Local queuing under contention



Garncarek, P, Jurdziński, T and Kowalski, DR ORCID: 0000-0002-1316-7788
(2018) Local queuing under contention. .

Access the full-text of this item by clicking on the Open Access link.

Abstract

We study stability of local packet scheduling policies in a distributed system of n nodes. The local policies at nodes may only access their local queues, and have no other feedback from the underlying distributed system. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate ρ and burstiness b. In this work, we assume that the underlying distributed system is a shared channel, in which in order to get rid of a packet from the queue, a node needs to schedule it for transmission on the channel and no other packet is scheduled for transmission at the same time. We show that there is a local adaptive scheduling policy with relatively small memory, which is universally stable on a shared channel, that is, it has bounded queues for any ρ < 1 and b ≥ 0. On the other hand, without memory the maximal stable injection rate is O(1/log n). We show a local memoryless (non-adaptive) scheduling policy based on novel idea of ultra strong selectors which is stable for slightly smaller injection c/log 2 n, for some constant c > 0.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 10 May 2019 10:15
Last Modified: 19 Jan 2023 00:46
DOI: 10.4230/LIPIcs.DISC.2018.28
Open Access URL: http://drops.dagstuhl.de/opus/volltexte/2018/9817/...
URI: https://livrepository.liverpool.ac.uk/id/eprint/3040605