  A new timeliness metric, called Age-of-Information (AoI), has recently
attracted a lot of research interests for real-time applications with
information updates. It has been extensively studied for various queueing
models based on the probabilistic approaches, where the analyses heavily depend
on the properties of specific distributions (e.g., the memoryless property of
the exponential distribution or the i.i.d. assumption). In this work, we take
an alternative new approach, the robust queueing approach, to analyze the Peak
Age-of-Information (PAoI). Specifically, we first model the uncertainty in the
stochastic arrival and service processes using uncertainty sets. This enables
us to approximate the expected PAoI performance for very general arrival and
service processes, including those exhibiting heavy-tailed behaviors or
correlations, where traditional probabilistic approaches cannot be applied. We
then derive a new bound on the PAoI in the single-source single-server setting.
Furthermore, we generalize our analysis to two-source single-server systems
with symmetric arrivals, which involves new challenges (e.g., the service times
of the updates from two sources are coupled in one single uncertainty set).
Finally, through numerical experiments, we show that our new bounds provide a
good approximation for the expected PAoI. Compared to some well-known bounds in
the literature (e.g., one based on Kingman's bound under the i.i.d. assumption)
that tends to be inaccurate under light load, our new approximation is accurate
under both light and high loads, both of which are critical scenarios for the
AoI performance.
