AIMD-Inspired Switching Control of Computing Networks

Abstract

We consider the scheduling problem of requests entering a distributed computing network consisting of a set of noncooperative nodes, where a node is represented by a queue combined with a computing unit. Our interaction-free setup between nodes renders decentralized scheduling challenging, with most existing results focusing on centralized 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 positive, constrained 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 analyzing 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 decentralized resource allocation controller coupled with the scheduling scheme leading to a stable closed-loop control system that is guaranteed to avoid underutilization of resources and is tunable via the sets of AIMD parameters.