Minimum Achievable Peak Age of Information Under Service Preemptions and Request Delay

• Published in: IEEE journal on selected areas in communications 2021-05, Vol.39 (5), p.1365-1379
• Main Authors: Champati, Jaya Prakash, Avula, Ramana R., Oechtering, Tobias J., Gross, James
• Format: Article
• Language: English
• Subjects: Age of Information (AoI); Delays; fixed-threshold policy; Freshness; general service-time distribution; Information retrieval; Markov Decision Process (MDP); Measurement; Minimization; Monitoring; Optimal scheduling; peak Age of Information (PAoI); preemptions; Questions; Queuing theory; Receivers
• ISSN: 0733-8716; 1558-0008; 1558-0008
• DOI: 10.1109/JSAC.2021.3065047

There is a growing interest in analysing freshness of data in networked systems. Age of Information (AoI) has emerged as a relevant metric to quantify this freshness at a receiver, and minimizing this metric for different system models has received significant research attention. However, a fundamental question remains: what is the minimum achievable AoI in any single-server-single-source queuing system for a given service-time distribution? We address this question for the average peak AoI (PAoI) statistic by considering generate-at-will source model, service preemptions, and request delays. Our main result is on the characterization of the minimum achievable average PAoI, and we show that it is achieved by a fixed-threshold policy among the set of all causal policies. We use the characterization to provide necessary and sufficient condition for preemptions to be beneficial for a given service-time distribution. Our numerical results, obtained using well-known distributions, demonstrate that the heavier the tail of a distribution the higher the performance gains of using preemptions.