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",
}