0
$\begingroup$

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).

Following is the network topology I am simulating in NS-3...

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.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you're asking here. "How do I implement protocol X in simulator Y?" sounds a lot like a programming question. What are you looking for in an answer? $\endgroup$ – David Richerby Jan 24 '16 at 16:48
  • $\begingroup$ Let me reframe my question. In simple words, by Yen's algorithm I could find k-shortest loopless paths yet I can't ensure that packet will be able to follow the entire path at once without ending up in loops because of the independent decisions made at intermediate routers. (suggestion might include change in routing technique or implementation in code or further changes in routing table itself) $\endgroup$ – user3306097 Jan 25 '16 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.