Tuesday, August 21, 2012

[Trema][Concept] How to do flow-based ECMP in Routing Switch App

  As we have known that Routing Switch App uses Dijkstra algorithm to pick up the lowest cost of the path. Only one path will be selected. If we want to do flow-based ECMP, how to do it? I have a simple way to slightly modify the Routing Switch App and then it can become "ECMP Routing Switch" App.

  Here is a topology as follows. If the source is PC1 and destination is PC2, we can know that the source switch is A and destination switch is B. I will base on this to explain my idea.

  First, we setup a number of multi-path , for instance, 8, and let the loop to do Dijkstra algorithm these times.
  Second, we need to add a new chosen flag to record nodes in the path that we have picked up, and get rid of the source and destination node. And also, when Dijkstra algorithm is running, we also need to add a condition to avoid from choosing the node whose chosen flag is true.

For instance, Path 1 is A->B->C->D. We need to add flag on B and C as true.
                        Path 2 is A->E->F->D. We need to add flag on E and F as true.

In this case, Dijkstra algorithm is not able to pick up the third path so that making paths is done.
I have implemented this in Routing Switch App and it works. I will post the real case in the next article.

Post a Comment