Extended version of this paper:

@article{"
  title = "On Selection of Candidate Paths for Proportional Routing",
  author = "Srihari Nelakuditi and Zhi-Li Zhang and David H.C. Du",
  journal = "Computer Networks",
  volume = "44",
  pages = "79--102",
  year = "2004"
}

Problem of shortest path routing: Unbalanced traffic distribution. Some links are increasingly congested while other links are underloaded. Therefore, multipath routing is introduced.

Minimizing number of multipaths is important because of:

Overhead in establishing, maintaining, and tearing down of paths
Complexity in distributing traffic to paths increases as the number of paths increases
There are limits imposed by, for example, MPLS label spaces

OSPF is a link state protocol with infrequent link state update. We can piggyback QoS information with the updates.

Minimizing overall blocking probability

This paper proposes the following problem setup:

Source routing network
Route over paths set up a priori
All flows have the same bandwidth demand (1 unit)
Flow arrive Poisson, holding time is exponential (M/M/1)
Performance metric is the overall blocking probability
Objective: Proportional QoS routing, i.e. route flows to paths to minimize overall blocking probability as experienced by flows

The global optimal proportioning problem is the following:

Assume all nodes know the network topology and the offered load between every source-destination pair. Then we define \(\hat c_\ell >0\) to be the capacity of (unidirectional) link \(\ell\) and \(\sigma = (s,d)\) to be a source-destination pair. Given the arrival rate and holding time of this pair to be \(\lambda_\sigma\) and \(\mu_\sigma\) respectively, its offered load is \(\nu_\sigma = \lambda_\sigma/\mu_\sigma\). Assume that the set of all feasible path for routing σ to be \(\hat{R}_\sigma\).

The global optimal proportioning problem is therefore, to find \(\{\alpha_r^\ast, r\in\hat{R}_\sigma\}\) such that \(\sum_{r\in\hat{R}_\sigma} \alpha_r^\ast = 1\) and \(W=\sum_\sigma\sum_{r\in\hat{R}_\sigma}\alpha_r\nu_\sigma(1-b_r)\) is maximized, where \(b_r\) is the blocking probability on path \(r\), which could be derived from Erlang’s formula using capacity of \(\hat{c}\), and M/M/1 arrival-departure pattern of offered load \(\nu\).

Usually, we use only a subset of paths \(R_\sigma \subset \hat R_\sigma\) such that for some small \(\epsilon\), \(R_\sigma = \{r: r\in\hat{R}_\sigma, \alpha_r^\ast>\epsilon\}\).

Solving the global optimal proportioning problem requires the global knowledge on the offered load. Therefore localized strategies exists to achieve the near-optimal solution. Two strategies are mentioned in the paper, they are:

equalizing blocking probabilities (ebp): To make \(b_{r_1} = b_{r_2} = \cdots = b_{r_k}\) on one source-destination pair and their \(k\) paths
equalizing blocking rate (ebr): To make \(\alpha_{r_1}b_{r_1} = \alpha_{r_2}b_{r_2} = \cdots = \alpha_{r_k}b_{r_k}\)

In the paper, ebp is used, with an approximation. Instead of calculating the adjustments directly, the fractions \(\alpha_{r_i}\) are adjusted adaptively at a frequency \(\theta\). It is first find the average blocking probability \(\bar{b} = \sum_i\alpha_{r_i}b_{r_i}\), and increase \(\alpha_{r_i}\) if \(b_{r_i} < \bar{b}\) or decrease otherwise. The amount of adjustment is depended on \(\lvert b_{r_i} - \bar{b}\rvert\).

Minimizing the number of candidate paths

The set of paths for a particular source-destination pair is determined by “widest disjoint paths” (wdp).

The width of a path is the residual bandwidth on its bottleneck link, i.e. \(w_r = \min_{\ell\in r} c_\ell\) where \(c_\ell = \hat c_\ell - \nu_\ell\) is the average residual bandwidth on link \(\ell\). Usually, we compute the residual bandwidth on a link by using the utilization \(u_\ell\) as reported by the link state update, i.e. \(c_\ell = (1-u_\ell)\hat{c}_\ell\). The distance of a path is defined as \(\sum_{\ell\in r} 1/c_\ell\).

The width of a set of paths \(R\) is computed as follows,

First pick the path \(r^\ast\) with the largest width. If multiple such paths exist, choose the one with shortest distance.
Then decrease the residual bandwidth on all links of \(r^\ast\) by \(w_{r^\ast}\), this essentially remove \(r^\ast\) from next selection
Repeat this process until we exhaust \(R\)
The sum of all widths of paths is the width of \(R\)
The last path selected in this computation is denoted by \(\textrm{NARROWEST}(R)\)

To select η paths from the set \(\hat{R}_\sigma\), the idea of the algorithm is as follows

Include a new path \(r\in\hat R_\sigma\) to \(R_\sigma\) if it contributes to the largest resulting width to \(R_\sigma\) and \(\lvert R_\sigma\rvert<\eta\)
If \(\lvert R_\sigma\rvert = \eta\), a new path has to be added and an old path has to be removed, so that the resulting width is maximized
Such addition or addition/removal results in a new width of \(R_\sigma\), it is accepted only if the new width is larger than the old width by a fraction of \(\psi\)
If no addition is made to \(R_\sigma\), remove a path from it if this does not result in decreasing its width.

Property of this algorithm is to select a set of candidate paths that are mutually disjoint with respect to bottleneck links. This path selection procedure and the proportioning procedure are run together as a heuristic, to “trade-off slight increase in blocking for significant decrease in the number of candidate paths”.

Bibliographic data

@inproceedings{
   title = "On Selection of Paths for Multipath Routing",
   author = "Srihari Nelakuditi and Zhi-Li Zhang",
   booktitle = "Proceedings of IWQoS",
   pages = "170--186",
   year = "2001",
}