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 to be the capacity of (unidirectional) link and to be a source-destination pair. Given the arrival rate and holding time of this pair to be and respectively, its offered load is . Assume that the set of all feasible path for routing σ to be .

The global optimal proportioning problem is therefore, to find such that and is maximized, where is the blocking probability on path , which could be derived from Erlang’s formula using capacity of , and M/M/1 arrival-departure pattern of offered load .

Usually, we use only a subset of paths such that for some small , .

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 on one source-destination pair and their paths
- equalizing blocking rate (ebr): To make

In the paper, ebp is used, with an approximation. Instead of calculating the adjustments directly, the fractions are adjusted adaptively at a frequency . It is first find the average blocking probability , and increase if or decrease otherwise. The amount of adjustment is depended on .

## 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. where is the average residual bandwidth on link . Usually, we compute the residual bandwidth on a link by using the utilization as reported by the link state update, i.e. . The distance of a path is defined as .

The width of a set of paths is computed as follows,

- First pick the path with the largest width. If multiple such paths exist, choose the one with shortest distance.
- Then decrease the residual bandwidth on all links of by , this essentially remove from next selection
- Repeat this process until we exhaust
- The sum of all widths of paths is the width of
- The last path selected in this computation is denoted by

To select η paths from the set , the idea of the algorithm is as follows

- Include a new path to if it contributes to the largest resulting width to and
- If , 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 , it is accepted only if the new width is larger than the old width by a fraction of
- If no addition is made to , 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",
}
```