Statistical Guarantee Optimization for Age of Information for the D/G/1 Queue

Age of Information (AoI) has proven to be a useful metric in networked systems where timely information updates are of importance. Recently, minimizing the "average age" has received considerable attention. However, various applications pose stricter age requirements on the updates which demand knowledge of the AoI distribution. In this work, we study the distribution of the AoI and devise a problem of minimizing the tail of the AoI distribution function with respect to the frequency of generating information updates, i.e., the sampling rate of monitoring a process, for the D/G/1 queue model under FCFS queuing discipline. We argue that computing an exact expression for the AoI distribution may not always be feasible. Therefore, we opt for computing a bound on the tail of the AoI distribution and use it to formulate a tractable alpha-relaxed Upper Bound Minimization Problem (alpha-UBMP), where alpha > 1 is an approximation factor. This approximation can be used to obtain "good" heuristic solutions. We demonstrate the efficacy of our approach by solving alpha-UBMP for the D/M/1 queue. We show, using simulation, that the rate solutions obtained are near optimal for minimizing the tail of the AoI distribution.QC 20190107