- There is no “best algorithm”. The best algorithm strongly depends on the scenario (topology, topology size, constraint bound tightness, relative importance of optimality and runtime, etc.).
- However, LARAC, SSR+DCCR and the H_MCOP family are often among the best algorithms, both in terms of runtime and optimality gap.
- General trend: algorithms based on a shortest path (SP) algorithm usually have shorter runtimes than algorithms based
on a shortest path tree (SPT) algorithm, which in turn usually have
shorter runtimes than algorithms relying on a k shortest paths
(kSP) algorithm to reach a given optimality level.
The routing problem considered is the unicast constrained shortest path (CSP) routing problem.
A path has to be found from a single source node to a single destination node.
The goal is to find the path minimizing a given metric (usually called cost) while making sure that a second given metric (sometimes referred to as delay, or simply as the constrained metric) is lower than a given constraint bound.
A solution is said feasible if it satisfies the constraint bound.
Metric values are considered positive and additive.
A routing request consists of a source node, a destination node and a constraint bound value.
Only complete algorithms are considered, i.e., algorithms which guarantee to find a solution if there is one.
The performance of the different routing algorithms is measured in terms of their runtime ratio and optimality gap.
- Runtime ratio
- For a given routing request, the runtime ratio of an algorithm is defined as its runtime divided by the runtime, for the same request, of the A* algorithm for finding the least-delay path between the two considered nodes.
- Optimality gap
- For a given routing request, the optimality gap of an algorithm is defined as the relative difference between the cost of its solution and the cost of the optimal solution.
In #1, the optimality gap is referred to as cost inefficiency.
The performance (runtime ratio and optimality gap) of the different algorithms is evaluated along the following four dimensions (4D).
- 4 different topologies are used: one ring bottleneck (ORB), two ring bottleneck (TRB), two ring random (TRR) and grid random (GR).
For each topology, 4 parallel bi-directional edges are defined for each link.
The only difference between the TRB and TRR topologies is the set of nodes which can communicate with each other.
For the TRB topology, the destination node is always the PLC and only the remotes I/Os can be source nodes.
For the TRR topology, any combination of source and destination is possible.
- Topology size (x2)
- All the topologies can be scaled along two dimensions m and n.
These two dimensions vary from 4 to 14.
- Delay level
For a given request, the constraint bound can vary from loose values (for which the least-cost path is feasible) to tight values (for which the least-delay path is not feasible, i.e., for which the problem is infeasible).
For a given source and destination pair, the range of possible constraint bounds is divided into seven sub-ranges called delay levels.
Each algorithm is evaluated along the four dimensions described here above.
More details on the evaluation setup (amount of runs, requests generation, cost and delay metric values, guess function, etc.) can be found in Section IV of #1.
The code was revised in order to
The evaluation was rerun using the new code structure.
Because of an updated Java version, and because we decided not to remove outliers anymore before plotting, the
new data differs very slightly from the original results presented in #1.
However, all the conclusions and lessons learned are of course still valid.
- be able to more easily rerun the evaluation in the future, and
- store the results of all the individual runs, instead of only summarizing stats.
Unicast QoS Routing Algorithms for SDN: A Comprehensive Survey and Performance Evaluation
Jochen W. Guck, Amaury Van Bemten, Martin Reisslein, Wolfgang Kellerer
IEEE Communications Surveys & Tutorials
. Volume: 20, Issue: 1, Firstquarter 2018