INFORMATION-UPDATE SYSTEMS: MODELS, ALGORITHMS, AND ANALYSIS

Abstract

Age of information (AoI) has been proposed as a new metric to measure the staleness of data. For time-sensitive information, it is critical to keep the AoI at a low level. A lot of work have been done on the analysis and optimization on AoI in information-update systems. Prior studies on AoI optimization often consider a push model, which is concerned about when and how to "push" (i.e., generate and transmit) the updated information to the user. In stark contrast, we introduce a new pull model, which is more relevant for certain applications (such as the real-time stock quotes service), where a user sends requests to the servers to proactively "pull" the information of interest. Moreover, we propose to employ request replication to reduce the AoI. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different levels of information freshness and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process for the servers and exponentially distributed response time with known expectation, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Then, we extend our analysis to the setting where the user aims to maximize the utility, which is an exponential function of the negative AoI and represents the user's satisfaction level about the timeliness of the received information. We can similarly derive a closed-form formula of the expected utility and find the optimal number of responses to wait for. Further, we consider a more realistic scenario where the updating rate and the mean response time at the servers are unknown to the user. In this case, we formulate the utility maximization problem as a stochastic Multi-Armed Bandit (MAB) Problem. The formulated MAB problem has a special linear feedback graph, which can be leveraged to design policies with an improved regret upper bound. We also notice that one factor has been missing in most of the previous solutions on AoI minimization, which is the cost of performing updates. Therefore, we focus on the tradeoff between the AoI and the update cost, which is of significant importance in time-sensitive data-driven applications. We consider the applications where the information provider is directly connected to the data source, and the clients need to obtain the data from the information provider in a real-time manner (such as the real-time environmental monitoring system). The provider needs to update the data so that it can reply to the clients' requests with fresh information. However, the update cost limits the frequency that the server can refresh the data, which makes it important to design an efficient policy with optimal tradeoff between data freshness and update cost. We define the staleness cost, which reflects the AoI of the data and formulate the problem as the minimization over the summation of the update cost and the staleness cost. We first propose important guidelines of designing update policies in such information-update systems that can be applied to arbitrary request arrival processes. Then, we design an update policy with a simple threshold-based structure, which is easy to implement. Under the assumption of Poisson request arrival process, we derive the closed-form expression of the average cost of the threshold-based policy and prove its optimality among all online update policies. In almost all prior works, the analysis and optimization are based on traditional queueing models with the probabilistic approaches. However, in the traditional probabilistic study of general queueing models, the analysis is heavily dependent on the properties of specific distributions. Under this framework, it is also usually hard to handle distributions with heavy tail behavior. To that end, in this work, we take an alternative new approach and focus on the Peak Age of Information (PAoI), which is the largest age of each update shown to the end users. Specifically, we employ a recently developed analysis framework based on robust optimization and model the uncertainty in the stochastic arrival and service processes by uncertainty sets. This robust queueing framework enables us to approximate the steady-state PAoI performance of information-update systems with very general arrival and service processes, including those exhibiting heavy-tailed behavior. We first propose a new bound of the PAoI under the single-source system that performs much better than previous results, especially with light traffic. Then, we generalize it to multi-source systems with symmetric arrivals, which involves new technical challenges. It has been extensively investigated for various queueing models based on the probabilistic approaches. However, in the traditional probabilistic study of general queueing models, the analysis is heavily dependent on the properties of specific distributions, such as the memoryless property of the Poisson distribution. Under this framework, it is also usually hard to handle distributions with heavy tail behavior. To that end, we take an alternative new approach and focus on the Peak Age of Information (PAoI), which is the largest age of each update shown to the end users. Specifically, we employ a recently developed analysis framework based on robust optimization and model the uncertainty in the stochastic arrival and service processes by uncertainty sets. This robust queueing framework enables us to approximate the steady-state PAoI performance of information-update systems with very general arrival and service processes, including those exhibiting heavy-tailed behavior. We first propose a new bound of the PAoI under the single-source system that performs much better than previous results, especially with light traffic. Then, we generalize it to multi-source systems with symmetric arrivals, which involves new technical challenges.