  In this work, we investigate the design of information-update systems, where
incoming update packets are forwarded to a remote destination through multiple
servers (each server can be viewed as a wireless channel). One important
performance metric of these systems is the age-of-information or simply age,
which is defined as the time elapsed since the freshest packet at the
destination was generated. Recent studies on information-update systems have
shown that the age-of-information can be reduced by intelligently dropping
stale packets. However, packet dropping may not be appropriate in many
applications, such as news and social updates, where users are interested in
not just the latest updates, but also past news. Therefore, all packets may
need to be successfully delivered. In this paper, we study how to optimize
age-of-information without throughput loss. We consider a general scenario
where incoming update packets do not necessarily arrive in the order of their
generation times. We prove that a preemptive Last Generated First Served (LGFS)
policy simultaneous optimizes the age, throughput, and delay performance in
infinite buffer queueing systems. We also show age-optimality for the LGFS
policy for any finite queue size. These results hold for arbitrary, including
non-stationary, arrival processes. To the best of our knowledge, this paper
presents the first optimal result on minimizing the age-of-information in
communication networks with an external arrival process of information update
packets.
