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