Minimizing AoI With Throughput Requirements in Multi-Path Network Communication

Abstract

We consider a single-unicast networking scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. We study problems of minimizing peak/average Age-of-Information ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AoI</i> ) subject to throughput requirements based on a stylized deterministic model in this scenario. The consideration of batch generation and multi-path communication differentiates our <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AoI</i> study from existing ones. We first show that our <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AoI</i> minimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. We then prove that minimizing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AoI</i> and minimizing maximum delay are “roughly” equivalent, in the sense that any optimal solution of the latter is an approximate solution of the former with bounded optimality loss. We leverage this understanding to design a general approximation framework for our problems. It can build upon any <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> -approximation algorithm of the maximum delay minimization problem to construct an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(\alpha +\mathsf {c})$ </tex-math></inline-formula> -approximate solution for minimizing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AoI</i> . Here <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf {c}$ </tex-math></inline-formula> is a constant depending on the throughput requirements. Furthermore, we show that our results can be extended to the multiple-unicast setting. Simulations over various network topologies validate the effectiveness of our approach. Our results make a major advance to optimizing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AoI</i> in multi-path communication, and hence can be of broad interest to the networking research community.

Topics & Concepts