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",
}
```