How to avoid looping of packets while implementing k-shortest paths algorithm in IPv4GlobalRouting Protocol

[f201...@pilani.bits-pilani.ac.in]

Hello

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 packets coming in can be forwarded to either 3 or 5. But if forwards back to node 3, 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 didnt 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 checked) 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 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.

Regards
Krishna Garg

[Tommaso Pecorella]

Hi,

this wikipedia page points to some well-known algorithms for this problem. Instead of re-inventing the wheel, you should implement one of them, as the probability to have a not-so-efficinet (or buggy) algorithm are quite high.

That's also why I hate when professors wants to teach to students how all the sorting algorithms works. Show 'em two of them, show that they have different complexities, and then tell them how to find the other ones. The probability that a student have to implement a BubbleSort are next-to-zero.

Cheers,

T.

[f201...@pilani.bits-pilani.ac.in]

Sorry Sir, but let me reframe my question. I have actually implemented Yen's Algorithm only (which is loopless) but the thing is: when the the decision has to be made for every packet at intermediate routers, how will I ensure that no looping takes place. 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 mae at intermediate routers.

Regards
Krishna Garg

[Tommaso Pecorella]

Hi,

good, this is a totally different question (and way more interesting).

The answer is: source routing. You need to decide at the source node what is the packet's path. This can be done through IP header extensions (not a good idea, they have been deprecated), through MPLS (not implemented in ns-3), IntServ (as for MPLS, not implemented in ns-3), or any other means that a router has to understand what was the decision of the source node.

Some techniques (e.g., MPLS, IntServ) could be used through DCE, but I never used it.

Any other technique (if it exists) would need a graph theory analysis, and I'm not sure that it exists. One should remove all the loops in the combined graph, and I don't even know if this would be a good idea, because it will most probably kill any redundant path.

Hope this helps,

T.

[pdbarnes]

IIRC OpenFlow supports MPLS.

A shortcut might be to extend Nix-vector routing to store your k-shortest paths. (Nix-vectors are a form of source routing.)

Peter

[Tommaso Pecorella]

From the OpenFlow manual section:

"All MPLS capabilities are implemented on the OFSID side in the OpenFlowSwitchNetDevice, but ns-3-mpls hasn’t been integrated, so ns-3 has no way to pass in proper MPLS packets to the OpenFlowSwitch."

If it's not true we need to change the manual...

As for Nix, it's a good idea, but it's not "realistic", meaning that the packet size doesn't consider the added informations (the packet size is always the same, no matter how large is the Nix vector). Of course, one can shrink the payload to take into account the extra header, or add an extra header just for this purpose.

Or it could be even possible to consider the bias in the data post-processing.

It all depends on the scenario and the research goals.

T.