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.