CSP Algorithms

Evaluation of state-of-the-art CSP algorithms

Performance evaluation of 19 state-of-the-art unicast constrained shortest path (CSP) algorithms. The runtime and optimality gap of the algorithms is evaluated for different topologies, topology sizes and for different tightness levels of the constraint bound.

Home »

CSP Algorithms

Download SQLite DB

Size (compressed): 25GB (6.3GB)
First publication: 11/03/2017
Last update: 08/01/2018

Visualize results »

Routing Problem

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.

Evaluation Metrics

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.

Evaluation Dimensions

The performance (runtime ratio and optimality gap) of the different algorithms is evaluated along the following four dimensions (4D).

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

Evaluation Setup

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.

Update

08/01/2018
The code was revised in order to
  • 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.
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.

Publications

#1

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
DOI PDF

People

Jochen W. Guck
Technical University of Munich
Amaury Van Bemten
Technical University of Munich
Martin Reisslein
Arizona State University
Wolfgang Kellerer
Technical University of Munich