Data Flow Dissemination in a Network

We consider the following network model motivated, in particular, by blockchains and peer-to-peer live streaming. Data packet flows originate at the network nodes and need to be disseminated to all other nodes. Packets are relayed through the network via links of limited capacity. A packet leaves the network when it is disseminated to all nodes. The network is stable when it is positive recurrent; and when it is, the age of the oldest packet, referred to as Age-of-Information (AoI) is stochastically bounded. Under the Random-Useful (RU) discipline a node $u$ communicates on link $(u,v)$ a randomly chosen available packet not present at $v$. RU discipline is known to have the maximum stability region for a single flow; we show that this extends to arbitrary number of flows. Our main results concern the Oldest-Useful (OU) discipline, under which a node $u$ communicates on link $(u,v)$ the oldest available packet not present at $v$. OU discipline is a natural candidate for reducing the AoI. We show that, surprisingly, OU \emph{does not} provide the maximum stability region. As the main result of this paper, we prove that OU \emph{does} have the maximum stability region in the important special case of a complete graph network with equal capacities on all links and equal flow rates originating in all nodes. Simulation results show that, in the latter special case, OU out-performs RU in terms of AoI. In the final part of this paper, we consider the cumulative delays experienced by a packet as it propagates through the system, specifically their limiting behavior as $N \to \infty$. We state some conjectures about this behavior, supported by heuristic arguments and simulation experiments. Notably, we conjecture (and observe in simulations) that the expected delays under RU and OU remain of the same order as those in the "free" system.Comment: 26 pages, 9 figures, 3 table