Minimizing AoI With Throughput Requirements in Multi-Path Network Communication

作者：Liu, Qingyu^*; Zeng, Haibo^*; Chen, Minghua^*

来源：IEEE/ACM Transactions on Networking, 2022, 30(3): 1203-1216.

DOI：10.1109/TNET.2021.3135494

• Throughput
• Delays
• Task analysis
• Routing
• Spread spectrum communication
• Receivers
• Minimization
• Age-of-information
• AoI minimization
• multi-path communication
• time-critical network flow

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 (AoI) subject to throughput requirements based on a stylized deterministic model in this scenario. The consideration of batch generation and multi-path communication differentiates our AoI study from existing ones. We first show that our AoI 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 AoI 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 alpha-approximation algorithm of the maximum delay minimization problem to construct an (alpha+c)-approximate solution for minimizing AoI. Here c 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 AoI in multi-path communication, and hence can be of broad interest to the networking research community.