Multi-Commodity Flow Formulation for Arbitrary Paths

If there are no bandwidth constraints in a network each communicating pair of nodes could communicate over the shortest path between them and thus minimize latency and cost to the network. In real networks all network links have a bandwidth constraint. Hence the question arises as to how to best choose paths between communicating nodes within the bandwidth constraints of the links. Such problems are known as multi-commodity flow (MCF) problems. The "multi" comes from the requirement of multiple source-destination node pairs needing to communicate at the same time.

We can mathematically represent an MCF problem in terms of the flow variables \( x_{ij}^{sr} \) which are defined as the amount of "flow" for the source-receiver pair \( (s, r) \) flowing over the network link \( (i, j) \). If we denote the network cost for using link \( (i, j) \) by \( c{n_{ij}} \) then the total network cost for all flows using the network is:

$$ \sum\limits_{s,r} {\sum\limits_{(i,j)} {c{n_{ij}}x_{ij}^{sr}} } $$

Note that the above is summed over all source destination pairs and all links. The link bandwidth constraint equations can be written as:

$$   \sum\limits_{s,r} {x_{ij}^{sr}}  \leqslant {b_{ij}}\quad \forall (i,j) $$

where \( b_{ij} \) is the bandwidth capacity for link \( (i, j) \) and we have one constraint equation for each link.
Finally we need equations to ensure that no flow gets lost at any node. This leads to the following flow conservation equations for each node \(i\):
 $$  \sum\limits_{\{ j|(i,j) \in L\} } {x_{ij}^{sr}}  - \sum\limits_{\{ j|(j,i) \in L\} } {x_{ji}^{sr}}  = \left\{ {\begin{array}{*{20}{l}}
   {{q_{sr}}}&{{\text{if }}i = s} \\
   { - {q_{sr}}}&{{\text{if }}i = r} \\
   0&{{\text{otherwise}}}
   \end{array}} \right. $$

This equation also explicitly contains the requirements that the bandwidth required between source and receiver, \( (r, s) \), which are denoted by \( q_{sr} \) are met.

A formulation where the values of \( x_{ij}^{sr} \) are continuous (real valued) results in what is known as a linear programming (LP) problem. If the values of \( x_{ij}^{sr} \) are discrete (integer valued) the problem is then a mixed integer linear programming (MILP) problem.  Open source and commercial solvers exist that for obtaining the solutions to these problems for quite large formulations. A fairly complete mathematical overview of linear and nonlinear MCF problems can be found in [1].

Multi-Commodity Flow Formulation with Given Paths

Restricting the Paths Chosen

In the basic multi-commodity flow (MCF) formulation above we did not place any restrictions on where the paths used by a source destination pair could go. Without making the LP problem any more difficult to solve one can prevent paths servicing source-receiver pair \( (s, r)\) from using a particular link \((i,j)\) by setting the flow variable \(x_{ij}^{sr} = 0\). We can therefore put different restrictions on the links used for each source-destination pair.

Restricting to a set of Given Paths

While the above restrictions on the paths chosen by a MCF algorithm are powerful, they cannot handle the case where the paths to be used must be taken from a given set of paths. Such a case can arise in WSON networks with impairments where only a limited set of paths have been "qualified" for use [2]. Another case is when the network owner does not want to share complete topology information on his network or only wants to allow the user a restricted set of paths.

Regardless of the motivation we are led to a very different formulation of the MCF problem which we refer to as the MCF given paths formulation. Let \(\bf{W}\) denote the set of source-receiver \( (s, r)\) pairs to be considered. Let \(\bf{P}_{sr}\) denote the set of paths that may be used for the source-destination pair \( (s, r)\). Let \(q_{sr}\) denote the bandwidth demand of the source-receiver pair, and \({y_{p,sr}} = 0,1\) indicate whether a particular path p between the source-destination pair is used. Note that we can allow \({y_{p,sr}} \in [0,1]\)if inverse multiplexing mechanisms are available. The link bandwidth constraint can be formulated as:

$$\sum\limits_{(s,r) \in {\bf{W}}} {\sum\limits_{\{ p|(i,j) \in p\} } {{q_{sr}}{y_{p,sr}}} }  \le {b_{ij}}$$

The demand constraint can be formulated as:

$$\sum\limits_{p \in {{\bf{P}}_{sr}}} {{y_{p,sr}} = 1} \quad \forall s,r $$

The network cost is:

$$\sum\limits_{(s,r) \in {\bf{W}}} {\sum\limits_{p \in {{\bf{P}}_{sr}}} {\sum\limits_{\{ (i,j)|(i,j) \in p\} } {c{n_{ij}}{q_{sr}}y_{p,sr}^{}} } } $$

where \(c{n_{ij}}\) is the cost per bandwidth to use link \( (i,j) \).

References

[1] Dimitri P. Bertsekas, Network Optimization: Continuous and Discrete Models. Athena Scientific, 1998.

[2] Asuman E. Ozdaglar and Dimitri P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Transactions on Networking, vol. 11, no. 2, pp. 259-272, 2003.