Bounded Dijkstra (BD)

Search space reduction for Dijkstra

When used as a subroutine of another algorithm, Dijkstra can often be stopped earlier if paths become too long. We show that this improvement allows to reduce the runtime of some algorithms by 75% in average.

Home »

Bounded Dijkstra (BD)

Download SQLite DB

Size (compressed): 963MB (383MB)
First publication: 01/03/2019

Visualize results »

Proposed Algorithm: Bounded Dijkstra (BD)

When a shortest path (SP) or shortest paths tree (SPT) algorithm is used as a subprocedure of another more complex problem (e.g., the (multi-)constrained shortest path (CSP and MCSP), multi-constrained path (MCP) and the constrained minimum Steiner tree (CMST) problems), it often happens that paths with a total cost greater than a given bound are not used to determine a solution to the original problem.

As a result of the existence of these bounds, and because the Dijkstra algorithm discovers paths in increasing order of cost, we propose to stop the SP/SPT searches earlier, i.e., once it is known that paths with a greater total cost will not be considered by the overlay algorithm. This early termination allows to reduce the runtime of the SP/SPT search, thereby reducing the runtime of the overlay algorithm without impacting its output. We refer to this adaptation of Dijkstra as bounded Dijkstra (BD).

Routing Problem

We evaluate BD in the particular case of its usage for CSP algorithms. 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.

Out of the 19 CSP algorithms presented in our evaluation of CSP algorithms, we consider the 16 that can make use of BD. Details on how each of these algorithms can use BD and the reasons for which the others cannot can be found in Section IV of #1.

Evaluation Metric

BD allows to reduce the runtime of algorithms without impact their output. As a result, for each algorithm, we evaluate the runtime impact of BD by means of the runtime ratio between the runtime of the algorithm without BD and the runtime of the algorithm with BD. For example, for a given request, a runtime ratio of 4 means that the algorithm is 4 times slower when not using BD or, alternatively, BD reduced the runtime of the algorithm by 75%.

Evaluation Dimensions

We evaluate BD on a square grid topology by varying the following three parameters.

Grid size
The width/height of the grid (in terms of nodes) is varied from 6 to 20.
Relative nodes distance
For a given grid size, we define 10 different so-called distance buckets. These buckets correspond to source and destination nodes pairs whose least-hop distance in the grid is between 0 and 10%, 10% and 20%, ..., 90% and 100% of the longest path in the grid (i.e., of 2 × (N − 1) if N is the grid width).
Delay level
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

The impact of BD on each algorithm is evaluated along the three dimensions described here above. More details on the evaluation setup (amount of runs, requests generation, cost and delay metric values, etc.) can be found in Section V-A of #1.

Publications

#1

Bounded Dijkstra (BD): Search Space Reduction for Expediting Shortest Path Subroutines
Amaury Van Bemten, Jochen W. Guck, Carmen Mas Machuca, Wolfgang Kellerer
arXiv preprint arXiv:1903.00436.
PDF

#2

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

Amaury Van Bemten
Technical University of Munich
Jochen W. Guck
Technical University of Munich
Carmen Mas Machuca
Technical University of Munich
Wolfgang Kellerer
Technical University of Munich