  The Internet can be made more efficient and robust with hop-by-hop multipath
routing: Each router on the path can split packets between multiple nexthops in
order to 1) avoid failed links and 2) reduce traffic on congested links. Before
deciding how to split traffic, one first needs to decide which nexthops to
allow at each step. In this paper, we investigate the requirements and
trade-offs for making this choice.
  Most related work chooses the viable nexthops by applying the "Downward
Criterion", i.e., only adding nexthops that lead closer to the destination; or
more generally by creating a Directed Acyclic Graph (DAG) for each destination.
We show that a DAG's nexthop options are necessarily limited, and that, by
using certain links in both directions (per destination), we can add further
nexthops while still avoiding loops. Our solution LFID (Loop-Free
Inport-Dependent) routing, though having a slightly higher time complexity,
leads to both a higher number of and shorter potential paths than related work.
LFID thus protects against a higher percentage of single and multiple failures
(or congestions) and comes close to the performance of arbitrary source
routing.
