AIMD-inspired switching control of computing networks

We consider the scheduling problem of requests entering a distributed computing network consisting of a set of non-cooperative nodes, where a node is represented by a queue combined with a computing unit. Our interaction-free setup between nodes renders decentralised scheduling challenging, with most existing results focusing on centralised or static solutions. Inspired by congestion control, we propose a new average-based additive increase multiplicative decrease (AIMD) admission control policy which requires minimal communication between individual nodes and an aggregator. The proposed admission policy infers a discrete-event model expressed as a positivconstrained switching system that is triggered whenever the queue of the aggregation point of requests vanishes. We show convergence of the proposed AIMD system under unknown, peak-bounded workload profiles by analysing the spectrum of rank-one perturbations of symmetric matrices and the boundedness of the joint spectral radius of sets of symmetric matrices. Contrary to methods that address scheduling and resource allocation asynchronously or via a two-step approach, our AIMD-based scheme can tackle both tasks simultaneously. This is illustrated by proposing a decentralised resource allocation controller coupled with the scheduling scheme leading to a stable closed-loop control system, that is guaranteed to avoid underutilisation of resources and is tunable via the sets of AIMD parameters.