Distributed balancing under interval flow constraints in directed communication topologies

Abstract

In this paper, we propose a distributed algorithm that relies on a strongly connected (but possibly directed) communication topology to achieve admissible and balanced flows in a given network. More specifically, 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. The paper proposes and analyzes a distributed iterative algorithm for computing admissible and balanced flows, i.e., flows that are within the given interval at each edge and balance the total inflow and the total out-flow at each node. Unlike previous work that required a communication topology with bidirectional exchanges between pairs of nodes that are physically connected (i.e., nodes that share an edge in the physical topology), the distributed algorithm we propose only requires a communication topology that matches the physical topology (which is, in general, directed). The proposed algorithm allows the nodes to asymptotically (with geometric rate) compute a set of admissible and balanced flows, as long as such solution exists. © 2017 IEEE.