  A weakness of next-hop routing is that following a link or router failure
there may be no routes between some source-destination pairs, or packets may
get stuck in a routing loop as the protocol operates to establish new routes.
In this article, we address these weaknesses by describing mechanisms to choose
alternate next hops.
  Our first contribution is to model the scenario as the following {\sc tree
augmentation} problem. Consider a mixed graph where some edges are directed and
some undirected. The directed edges form a spanning tree pointing towards the
common destination node. Each directed edge represents the unique next hop in
the routing protocol. Our goal is to direct the undirected edges so that the
resulting graph remains acyclic and the number of nodes with outdegree two or
more is maximized. These nodes represent those with alternative next hops in
their routing paths.
  We show that {\sc tree augmentation} is NP-hard in general and present a
simple $\frac{1}{2}$-approximation algorithm. We also study 3 special cases. We
give exact polynomial-time algorithms for when the input spanning tree consists
of exactly 2 directed paths or when the input graph has bounded treewidth. For
planar graphs, we present a polynomial-time approximation scheme when the input
tree is a breadth-first search tree. To the best of our knowledge, {\sc tree
augmentation} has not been previously studied.
