Finite-Time Distributed Flow Balancing

Abstract

We consider a flow network that is described by a digraph (physical topology), each edge of which can admit a flow within a certain interval, with nonnegative end points that correspond to lower and upper flow limits. The paper proposes and analyzes a distributed iterative algorithm for computing, in finite time, admissible and balanced flows, i.e., flows that are within the given intervals at each edge and balance the total in-flow with the total out-flow at each node. The algorithm assumes a communication topology that allows bidirectional exchanges between pairs of nodes that are physically connected (i.e., nodes that share a directed edge in the physical topology). If the given initial flows and flow limits are commensurable (i.e., integer multiples of a given constant), then the proposed distributed algorithm operates exclusively with flows that are commensurable and is shown to complete in a finite number of steps (assuming a solution set of admissible and balanced flows exists). When no upper limits are imposed on the flows, a variation of the proposed algorithm is shown to complete in finite time even when initial flows and lower limits are arbitrary nonnegative real values (not necessarily commensurable).