A tool for path computation algorithms

Fri, 12/18/2009 - 18:30 by Pascal Mérindol • Categories:

Multipath computation algorithms

Multipath computation algorithms are useful to enable multipath routing and so providing reliability and efficiency. According to the objective (e.g., load balancing or fast rerouting) and the forwarding context (e.g., hop by hop, tunneling,...), there exists several shortest paths algorithms to perform multiple paths computation. In order to evaluate several existing approaches and algorithms, we have developed a tool analysing a bunch of pertinent indicators (e.g., the computation time, the coverage,...). Our tool allows for analysing various path computation methods depending on a large set of parameters.

Overview of the proposed tool

This page provides a tool analysing path computation algorithms performances. In particular, our tool analyses the computation time and various path diversity metrics (e.g., local or distributed). It allows for analyzing time complexities, space complexities and diverse properties related to multipath routing. Generally speaking, we provide algorithms such as the classical Dijkstra algorithm, ECMP, Dijkstra-Transverse (DT) and its variants mDT. Our main concerns is to compare our Two Best First Hops (TBFH) algorithm with kSPF which computes a Shortest Path Tree per neighbor.
Our tool also includes several priority queues (e.g., double linked lists, binary heap, ...) and can emulate various loop-free forwarding rules (e.g., DC, LFA, node-LFA, ...). Those rules, priority queues and algorithms are detailed in the technical report available below and in the list of publications given at the end of this web page.

Technical Report

The technical report is available here.
Abstract: Multipath routing allows for load balancing and fast re-routing in order to improve the reliability and the efficiency of the network. Current IP routers only support Equal Cost MultiPath (ECMP) which guarantees that the forwarding paths do not contain loops. However, ECMP provides limited path diversity. In this paper, we present an efficient algorithm that allows routers to enable more path diversity: our algorithm let each router computes at least the two best first hop distinct paths towards each destination and achieves a good tradeoff between path diversity and overhead.
In addition, we propose a multipath routing scheme whose goal is to combine fast re-routing and load balancing loop-free routes. The low overhead of our scheme (no additional signaling messages and low complexity) and the nature of its loop-free rules allow to incrementally deploy it on current IP routers. Using actual, inferred, and generated topologies, we compare our algorithm to existing solutions.

The code

Our code is available on request. Our tool is coded in C for efficiency. Please send an e-mail to pascal.merindol(at)uclouvain.be for further informations.
Some topologies examples are given below in the format required by our tool. Note that the IGEN generator allows to generate topologies in this particular format.

Public weighted topologies (in our tool's format)

See also our mrinfo topologies data set. Here, we give some tools for format conversion.

Publications and related work