The paper is to have a distributed routing algorithm to find, at each node $$i$$, the successor set for destination $$j$$ such that the routing path is loop-free at every instant even the link costs are changing with time. Such algorithm turns out finds the multipath route with unequal length.

The successor set of node $$i$$ has the property that the shortest distance of any node $$k$$ in the set to destination $$j$$ is strictly less than that of node $$i$$ to node $$j$$. Therefore, this avoids loops. The algorithm works as follows

• Every node knows its neighbours, thus the shortest distance from itself to the neighbour
• Every node tells its shortest-distance knowledge to its neighbours
• When a node receive the shortest-distance data from its neighbours, it learns more about the topology. thus also updating its topology knowledge
• When a node $$i$$ knows multiple ways to reach the same node $$j$$, it runs Dijkstra’s algorithm to find the shortest path
• Since shortest path information is updated in node $$i$$, it can send an updated message to its neighbours

In the paper, it assumes the distance may change with time. Therefore, when the shortest path distance at node $$k$$ is calculated and told node $$i$$, the distance may be updated and this may potentially cause loop. Thus additional constraints are needed.

When node $$i$$ wants to forward packets to node $$j$$, it finds a successor set, which is a subset of its neighbours. For any node of the successor set, its distance to node $$j$$ is strictly less than the feasible distance (an estimate of actual distance) of node $$i$$ to node $$j$$. Thus the routing is loop free.

## Bibliographic data

@article{
title = "MPATH: a loop-free multipath routing algorithm",
author = "S. Vutukurya and J.J. Garcia-Luna-Aceves",
journal = "Elsevier Microprocessors and Microsystems",
volume = "24",
pages = "319--327",
year = "2000",
}