I am trying to implement k-shortest paths algorithm in NS-3 for IPv4GlobalRoutingProtocol. I am concerned about how to avoid looping of packets. My implementation calculates k-shortest paths from every node to every other node in the network and accordingly I store the possible nexthops (to which the packet may be forwarded to).
Let Source Node = 0, Destination Node = 5
Looping I: E.g. Nexthops for node 4 will be 3 & 5. So any packet coming in at node 4 can be forwarded to either 3 or 5. But if node 4 forwards back to node 3 and again node 3 may forward to node 4... this can go infinitely.
To avoid looping I, I carefully avoided to forward the packet from where it is being received. But still looping II didn't get solved, rather this solution kind of induces looping II problem to some extent.
Looping II: If I say, k = 3 (3 shortest paths are computed) and I consider Node 15. Possible paths: 15->3->6->5 15->3->4->5 15->1->2->3->4->5 So, nexthops would be: 3 and 1. But if I say that packet mustn't be forwarded to node from where it is being received (so as to avoid looping I), then only possible nexthop is node 1. In this case, from node 1 onwards, we again can fall in infinite loop (1->2->3->15->...).
It would be great help if someone can come up with solution that avoids both the looping problems. Please ask for any more clarifications required on my question.