Extended version of this paper:

  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

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