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 »- Without
*any*impact on the output of the algorithms, - BD can
**reduce the runtime**of some CSP algorithms by**75% on average**, and - in favorable cases, BD can reduce the runtime of several algorithms by
**96% on average**. - The topology size has no influence on the impact of BD.
- BD has a
**greater**impact when it can be used**for SPT searches**compared to single-destination SP searches. - BD has a
**greater**impact when the**source and destination nodes are close to each other**compared to the size of the topology. - BD also often has a greater impact when the delay constraint is tighter.

Size (compressed): **963MB (383MB)**

First publication: **01/03/2019**

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

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

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

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

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

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

Amaury Van Bemten, Jochen W. Guck, Carmen Mas Machuca, Wolfgang Kellerer

arXiv preprint arXiv:1903.00436.

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

Jochen W. Guck, Amaury Van Bemten, Martin Reisslein, Wolfgang Kellerer

IEEE Communications Surveys & Tutorials. Volume: 20, Issue: 1, Firstquarter 2018

DOI PDF

Amaury Van Bemten

Technical University of Munich

Technical University of Munich

Jochen W. Guck

Technical University of Munich

Technical University of Munich

Carmen Mas Machuca

Technical University of Munich

Technical University of Munich

Wolfgang Kellerer

Technical University of Munich

Technical University of Munich