  Information updates in multihop networks such as Internet of Things (IoT) and
intelligent transportation systems have received significant recent attention.
In this paper, we minimize the age of a single information flow in
interference-free multihop networks. When preemption is allowed and the packet
transmission times are exponentially distributed, we prove that a preemptive
Last-Generated, First-Served (LGFS) policy results in smaller age processes
across all nodes in the network than any other causal policy (in a stochastic
ordering sense). In addition, for the class of New-Better-than-Used (NBU)
distributions, we show that the non-preemptive LGFS policy is within a constant
age gap from the optimum average age. In contrast, our numerical result shows
that the preemptive LGFS policy can be very far from the optimum for some NBU
transmission time distributions. Finally, when preemption is prohibited and the
packet transmission times are arbitrarily distributed, the non-preemptive LGFS
policy is shown to minimize the age processes across all nodes in the network
among all work-conserving policies (again in a stochastic ordering sense).
Interestingly, these results hold under quite general conditions, including (i)
arbitrary packet generation and arrival times, and (ii) for minimizing both the
age processes in stochastic ordering and any non-decreasing functional of the
age processes.
