Keywords

1 Introduction

Network utility maximization (NUM) problem is stated as a problem of maximizing concave objective function over a set of linear constraints [9]. The objective function aggregates the “utility” of a collection of flows, which is a nondecreasing function of the amount of flow transmitted between a source and sink nodes. Flows share common links along their paths, and total flow allocation in each link is limited by a fixed capacity.

The formulation of NUM problem is as follows. Let F be the set of flows (or commodities), | F |  = m. For each flow k ∈ F let x k  ≥ 0 represent the transmission rate assigned to it. The network consists of L links, each of capacity c l  > 0. Each flow passes through a subset of links, which is expressed by a binary m × L matrix A = [A kl ], defined as: a kl  = 1 iff. kth flow passes through lth link. For each flow we have utility function \( {u}_k:\mathbb{R}\to \mathbb{R} \), which assigns utility (payoff) to rate x k of a flow. The goal is to maximize the sum of all utilities:

$$ {\displaystyle \underset{\mathbf{x}}{ \max }}\left\{{\displaystyle \sum_{i\in F}}{u}_i\right({x}_i\left):\kern2.77695pt \mathbf{A}\mathbf{x}\le \mathbf{c},\mathbf{x}\ge 0\right\}. $$
(1)

An instance of NUM consists of a set of flows F, set of functions u i for each i ∈ F, matrix A and vector c.

While NUM problem, formulated in this way, can be used to model performance of transmission control mechanisms in computer networks, there are also several related issues that can be captured within this framework. In this paper we focus on the network design problem from the perspective of utility maximization. The basic model (1) assumes fixed flow assignment, expressed in terms of matrix A. This is reasonable, since in typical IP networks routing problem is separated from transmission rate control problem. One may ask however, whether it is possible to solve these problems jointly (in an efficient way)? Matrix A can be seen as a result of transformation of input set consisting of source-destination pairs into a flow-to-link assignment. We consider the problem of selecting a matrix that represents such paths for each flow, that the corresponding NUM problem has the greatest optimal solution over all possible sets of paths.

1.1 Problem formulation

We state a mixed-integer programming formulation of the considered problem as follows. Consider a complete graph G on n vertices, V = {1, …, n}, with capacity function \( c\kern-1.75pt :\kern-1.75pt V\kern-1pt \times \kern-1pt V\kern-1pt \to \kern-1pt {\mathbb{R}}_{+}\cup \left\{0\kern-1pt \right\} \). Let \( I=\left\{\right({s}_1,{t}_1\left),\right({s}_2,{t}_2\left),\dots, \right({s}_m,{t}_m\left)\right\} \) be a subset of V × V. Given is a set of functions \( {u}_k:\mathbb{R}\to \mathbb{R} \), k ∈ F = {1, …, m}.

Let x k  ≥ 0 be a real variable denoting the rate of kth flow, let y ijk be binary variable, assuming the value 1 if and only if kth flow uses edge (i, j) on its path from source s k to destination t k , and value 0 otherwise. We wish to maximize the following objective function:

$$ U\left(\mathbf{x},\mathbf{y}\right)={\displaystyle \sum_{k\in F}}{u}_k\left({x}_k\right) $$
(2)

subject to constraints:

$$ {\forall}_{k\in F}\kern8.33pt {\forall}_{i\in V}\kern8.33pt {\displaystyle \sum_{j=1}^n}{y}_{i jk}-{\displaystyle \sum_{j=1}^n}{y}_{j i k}=\left\{\begin{array}{c}1,\ \mathrm{if}\ i={s}_k,\\ {}-1,\ \mathrm{if}\ i={t}_k,\\ {}0,\ \mathrm{otherwise},\end{array}\right. $$
(3)
$$ {\forall}_{\left( i, j\right)\in V\times V}\kern8.33pt {\displaystyle \sum_{k\in F}}{x}_k{y}_{ijk}\le c\left( i, j\right), $$
(4)
$$ {\forall}_{k\in F}\kern8.33pt {x}_k\ge 0. $$
(5)
$$ {\forall}_{i, j, k\in V\times V\times F}\kern8.33pt {y}_{i jk}\in \left\{0,1\right\}, $$
(6)

We call this problem Utility-Maximizing Network Design problem (UMND). The problem can be seen as maximizing over all routing matrices A in (1), constrained to represent m simple paths between given set of source-destination node pairs I, in addition to selecting the best transmission rates x. The underlying connection structure can be, in general, an arbitrary graph, since capacity function c may assign values of zero to some edges.

2 Related works

Problems of maximizing the aggregate utility of flows in network are called network utility maximization (NUM) problems [2], [3], [6], [9]. NUM is related to the well-known maximum multicommodity flow problems [10]. In the latter we are given a set of k source-destination pairs (each representing a single commodity) with a demand D k , and the goal is to find flow assignment function for each pair, such that link capacities are not exceeded and the flow conservation law is preserved on each node, and the common fraction of all routed commodity demands is maximized. In NUM demands are not fixed, but expressed using utility functions.

Combinatorial problems in which we are concerned with selecting subgraphs from a family of graphs are usually called network design problems. One commonly encountered problem in this area is called buy-at-bulk network design [1]. In this problem we are given a set of source-destination pairs in an undirected graph with given edge lengths, and we need to connect these pairs of nodes by purchasing the capacity c of any edge at some cost f(c) per unit of length. The goal is to purchase sufficient amount of capacity for each edge so that it is possible to route total demand d i between ith source-destination pair, while minimizing the cost paid. This problem is similar to UMND in the aspect that the cost is usually modeled using concave function f for purchasing capacity, which reflects the fact that increasing allocated resource for larger values yields reduction in cost.

In [7] a network design problem is formulated in which we look for set of shortest paths between all vertex pairs with total weights no greater than given threshold. It is established that such problem is NP-complete. In [12] a similar problem of joint routing and rate control to the one considered in this paper was formulated, and for general utility functions it was shown to be NP-complete. Here we consider only the class of iso-elastic utility functions, and show NP-completeness for such restricted class of problems. Moreover, we indicate that for such class of utility functions the randomized rounding [4], [11], technique may lead to a constant-factor approximation algorithm.

3 Main Results

It is easy to see that for an optimal solution we should assign to each flow the widest simple path between source and destination (this is such a path on which the minimal capacity of edges is maximized, and there are no repeated nodes). In case m = 1 this is easy to find just by computing maximum spanning tree in given graph, and restricting it to the path between s 1 and t 1. However, for m > 1 the paths resulting in highest bandwidth (and highest utility) for different flows may not be disjoint, which would violate capacity constraints.

For general utility functions u i the problem appears to be difficult to solve. However, in practical applications, such as in computer networking, we are usually interested in utility functions which allow for fair allocations [8]. Henceforth, we restrict the choice of utility function to the family of iso-elastic functions:

$$ {u}_i\left({x}_i\right)=\left\{\begin{array}{cc}{w}_i\frac{1}{1-\gamma}{x}_i^{1-\gamma}& \gamma >0,\gamma \ne 1,\\ {}{w}_i \log {x}_i& \gamma =1,\end{array}\right. $$
(7)

where γ ∈ (0, 1] is a parameter. Such form of utility has the property that each flow i ∈ F receives a share of capacity proportional to its weight w i . If a link of capacity c is the bottleneck link for a collection of flows F, then maximal value of ∑ i ∈ F u i (x i ) for any i ∈ F is:

$$ {x}_i^{\ast }= c\frac{w_i^{1/\gamma}}{{\displaystyle \sum_{k\in F}}{w}_k^{1/\gamma}}. $$

If in addition to the network size n, also the number of flows m is given as a part of the input, then the utility-maximizing network design problem is very likely to be intractable.

Theorem 1

Problem UMND is NP-complete.

Proof. We reduce the BIN-PACKING problem [5] to UMND with iso-elastic utility functions with parameter γ = 1. In the decision version of BIN-PACKING problem we are given a set of items U = { a 1, a 2, …, a m }, each with integer size w(a k ) = w k  > 0, and two integers B, K > 0, and we ask whether it is possible to pack all the items into K bins of size B each.

Given an instance of BIN-PACKING, we construct an instance of UMND as follows. Each a i  ∈ U corresponds to one source node s i . Let \( C=\sum_{i=1}^m{w}_i \). There is a central layer of K edges of capacity B, such that each of m source nodes is connected with each of these K edges via an edge of capacity w i , (thus there are K outgoing edges from each source node s i ). Each of K edges from the central layer is connected to a single edge of capacity C. The other endpoint of this edge is the terminal node for all m flows. This is illustrated in Figure 1.

Fig. 1.
figure 1

Example network resulting from reducing instance of BIN-PACKING for m = 4 items and K = 3 bins of size B.

Full size image

Each route from a source node to the terminal node must pass through exactly one of K edges of capacity B in the central layer and through the single terminal edge of capacity C. If the latter edge were a bottleneck, its capacity must have been completely filled, and since the utility functions are iso-elastic, each flow would be assigned a fraction w i of its capacity. Consequently, the optimal solution of UMND problem would have the value:

$$ {v}^{\ast }={\displaystyle \sum_{i=1}^m}{w}_i \log {w}_i $$

We claim that such flow assignment is achieved if and only if the given instance of BIN-PACKING problem has a solution. To see this, suppose that all items U can be packed into K bins of size B. Then each flow of rate x i  = w i would pass through one of the central layer edges, and then through the terminal edge of capacity C, contributing to filling it completely. On the other hand, if not all items from U fit into K bins, the only way to route all flows through central layer would be to reduce the rate of at least one flow below the corresponding value w i . But that would result in a solution of UMND strictly less than v ∗.

Consequently, UMND is NP-hard. Moreover, its decision version obviously belongs to NP, since given a routing matrix and transmission rates, we can easily verify feasibility and evaluate the value of objective function in polynomial time, using formulation (2)–(6). Then it remains to compare the value of objective with a given threshold value. □ 

3.1 Linear-factor approximation algorithm

Consequently, we are interested in designing polynomial time approximation algorithms for UMND. Perhaps one of the simplest heuristics is based on finding the widest path for each flow separately, followed by squeezing the flows appropriately in order to fit into all links whose capacities were violated. This is summarized as Algorithm 1. As shown in Theorem 2 such algorithm never returns a solution that is less than a factor \( O\left(\frac{1}{m}\right) \) of optimal value.

Theorem 2

Algorithm 1 is \( O\left(\frac{1}{m}\right) \) -approximate for UMND.

Proof. Let (x i ∗) i ∈ F be rates in optimal solution of UMND, and let OPT be the value of optimal solution. Let (x i ) i ∈ F be rates in a solution produced by Algorithm 1, and let \( \upsilon \) be the value of this solution. Let P j denote the path computed by Algorithm 1 for realizing flow j (i.e., set of edges that make up this path).

For each flow i ∈ F in solution given by Algorithm 1, let e(i) denote the bottleneck edge of i. Observe, that if e(i) is a bottleneck edge for some flow i in the solution produced by Algorithm 1, it must be that x i ∗ ≤ c(e(i)), as the Algorithm 1 in its first phase finds the widest edge for flow i, unconstrained by the presence of other flows, so no higher allocation for i can be in optimal solution. But since e(i) is a bottleneck edge, some subset of flows contribute to filling its capacity: \( \sum_{j: e(i)\in {P}_j}{x}_j= c\left( e\right( i\left)\right) \) (this sum always includes flow i). In the special case this sum may include all flows, if e(i) happens to be the bottleneck for all flows. Thus we have:

$$ {\displaystyle \sum_{j\in F}}{x}_j\ge {\displaystyle \sum_{j: e(i)\in {P}_j}}{x}_j= c\left( e\right( i\left)\right)\ge {x}_i^{\ast }, $$

which, after summing over all i ∈ F, gives:

$$ {\displaystyle \sum_{i\in F}}{\displaystyle \sum_{j\in F}}{x}_j= m{\displaystyle \sum_{j\in F}}{x}_j\ge {\displaystyle \sum_{i\in F}}{x}_i^{\ast }. $$
(8)

Let M = max(i, j) ∈ V ×V c(i, j). Since each u j (x j ) for x j  ∈ [0, M], can never assume value greater than \( {w}_j\frac{1}{1-\gamma}{M}^{1-\gamma} \), we can write:

$$ {\displaystyle \sum_{j\in F}}{u}_j\left({x}_j\right)\ge \alpha {\displaystyle \sum_{j\in F}}{x}_j, $$

where \( \alpha =\underset{i\in F}{ \min}\left\{{w}_i\frac{1}{1-\gamma}{M}^{-\gamma}\right\} \), and, consequently from (8):

$$ \overset{\sim }{\upsilon}={\displaystyle \sum_{j\in F}}{u}_j\left({x}_j\right)\ge \frac{\alpha}{m}{\displaystyle \sum_{j\in F}}{x}_j^{\ast }. $$
Table 1
Full size table

Since for all j ∈ F, \( \alpha {x}_j^{\ast }+\alpha \ge {u}_j\left({x}_j^{\ast}\right) \), we obtain:

$$ \overset{\sim }{\upsilon}\ge \frac{\alpha}{m}{\displaystyle \sum_{j\in F}}{u}_j\left({x}_j^{\ast}\right)-\alpha =\alpha \frac{1}{m} O P T-\alpha = O\left(\frac{1}{m}\right) O P T.\kern2.4em \square $$

To see that the bound of \( \frac{1}{m} \) is strict, consider the network of m parallel links, of which the first one has capacity C, and the remaining m − 1 of them have capacities C −ε each, for some small ε > 0 (see Figure 2). There are m identically weighted flows originating from common node s and terminating at common node t (other edges have sufficiently high capacities to never be bottlenecks). Algorithm 1 would assign all flows to the first link, as it greedily looks for the widest paths for each of them separately. The value of solution would be \( \sum_{i\in F}{u}_i\Big( C/ m\Big)={m}^{\gamma -1}\sum_{i\in F}{u}_i(C) \). Optimal solution would consist of each flow assigned to a separate link, thus giving solution ∑ i ∈ F u i (C) −ε′, where ε′ > 0 can be arbitrarily small.

Fig. 2.
figure 2

Example network illustrating the worst case instance for Algorithm 1.

Full size image

3.2 Constant-factor randomized approximation algorithm

It is possible to obtain a better algorithm by allowing randomization. The idea is to use the the mixed-integer program capturing UMND problem, and to relax integrality constraints. This allows to obtain an upper bound on the optimal solution in polynomial time, by solving the relaxation. Although we allow only for a single path for each flow, after the relaxation, the fractional solution might split a flow among several paths. However, such solution can be treated as a probability distribution on paths for a given flow. Subsequently, we can apply randomized rounding of such solution.

Since constraints (4) are nonlinear, we first need to reformulate it to an equivalent linear program. Let us introduce variables z = [z ijk ], and substitute (4) by the following set of constraints, to make sure that \( {z}_{ijk}={x}_r{y}_{ijk} \):

$$ {\forall}_{i, j, k\in V\times V\times F}\kern8.33pt {z}_{i jk}\le C{y}_{i jk}, $$
(9)
$$ {\forall}_{i, j, k\in V\times V\times F}\kern8.33pt {z}_{i jk}\le {x}_k, $$
(10)
$$ {\forall}_{i, j, k\in V\times V\times F}\kern8.33pt {z}_{i jk}\ge {x}_k- C\left(1-{y}_{i jk}\right), $$
(11)
$$ {\forall}_{i, j, k\in V\times V\times F}\kern8.33pt {z}_{i jk}\ge 0. $$
(12)

Here C = max i, j c(i, j). A path chosen for a flow is represented by a set of selected edges, that is a set of indices of variables, such that \( {y}_{s_k{u}_1}={y}_{u_1{u}_2}=\dots ={y}_{u_q{t}_k}=1 \). Observe, that constraints (3) guarantee that for each flow k there would be exactly one path selected.

Table 2
Full size table

By relaxing constraints (6) to y ijk  ≥ 0 we obtain a linear program. Let \( \left(\widetilde{x}_{\ k}, \widetilde{y}_{\ ijk} \right) \), for i, j, k ∈ V × V × F, denote an optimal fractional solution. Due to the constraint (3), for each flow k the sum of values of edge selection decision variables \({\widetilde{y}_{\ ijk}} \) must be equal to 1. Since \(\widetilde{y}_{\ ijk}\) may now assume fractional values in the range [0, 1] that sum up to 1, we may use these values as a probability distribution of selecting a path among a subset of paths between s k and t k , that fractional solution would contain.

However, there is a concern that with nonzero probability the rounded solution may be infeasible, due to the violation of constraint (4). To overcome this, we may shrink the values of rates obtained from solving linear relaxation by multiplying them by a common factor. This would allow us to bound the probability of constraint violation. This idea leads to the Algorithm 2.

Proposition 1

For any γ ≠ 1, Algorithm 2 returns a feasible solution for UMND with nonzero probability. Such a solution is no worse than e γ−1 times the optimal solution.

Proof. The Algorithm 2 selects for each flow a path from the source s k to destination t k , by randomly forking on each edge, with probability given by fractional solution \( \left(\widetilde{y}_{\ uvk} \right) \). For each flow k, a particular vertex v is added to the currently constructed path with conditional probability:

$$ P r\left[\mathrm{edge}\right( u, v\left)\kern0.3em is\kern0.3em selected\right|\mathrm{current}\kern0.3em \mathrm{path}\kern0.3em \mathrm{include}\kern0.3em \mathrm{vertex}\kern0.3em \mathrm{u}\Big], $$

computed in step 5. In order to show that a solution constructed this way can be feasible, we calculate the probability of violating constraint (4).

Let \( y_{(i,j)}^{k}\in \{0,\widetilde{x}_{k}\} \) be a random variable with \( Pr[y_{(i,j)}^{k} = \widetilde{x}_{k}] = \widetilde{y}_{\ ijk} \). Consider a random variable \( Y=\sum_{k\in F}{Y}_{\left( i, j\right)}^k \). Its expected value is clearly \(\mu =\sum_{k\in F}{\widetilde{x}}_k{\overset{\sim }{y}}_{ij k}\le {c}_{ij}\). We apply Chernoff bound to (4) including rounded solution y ijk  ∈ { 0, 1}. For any (i, j) ∈ V × V and any δ > 0 it holds that:

$$ Pr[\sum_{k\in F}\widetilde{x}_{\ k}y_{ijk} \geq (1 + \delta)c_{ij}] = Pr[\sum_{k\in F}{x}_{\ k}y_{ijk} \geq c_{ij}] \\ {\leq \left(\frac{e^\delta}{(1 + \delta)^(1+\delta)}\right)^{c_{ij}}}$$

where \({x}_r=\frac{1}{1+\delta}{\widetilde {x}}_k \) is rate allocated by Algorithm 2.

Let us denote C = min(i, j) ∈ V ×V c ij . Then:

$$ P r\left[{\displaystyle \sum_{k\in F}}{x}_k{y}_{ij k}\ge {c}_{ij}\right]<{\left(\frac{e^{\delta}}{{\left(1+\delta \right)}^{\left(1+\delta \right)}}\right)}^C=\eta. $$
(13)

The rounded solution generated by Algorithm 2 is feasible if all constraints in set (4) are satisfied. From (13), any constraint concerning edge (i, j) is satisfied with probability at least (1 − η). Since there can be up to n 2 constraints, the probability that all of them are satisfied simultaneously cannot be less than \( \varepsilon ={\left(1-\eta \right)}^{n^2} \). We show that ε > 0. By taking logarithm of (13) we obtain:

$$ \log \frac{e^{\delta}}{{\left(1+\delta \right)}^{\left(1+\delta \right)}}= \log\ {\eta}^{1/ C}, $$

and for δ ≥ e − 1:

$$ \log\ {\eta}^{1/ C}=\delta -\left(1+\delta \right) \log \left(1+\delta \right)\le \log \left(1+\delta \right)\left(\delta -1-\delta \right)= \log \frac{1}{1+\delta}. $$

Thus fixing δ = e − 1 (see step 9 of Algorithm 2) we get \( \log\ {\eta}^{1/ C}= \log \frac{1}{e} \), and consequently \( \varepsilon \ge {\left(1-{e}^{- C}\right)}^{n^2} \), which is greater than zero.

Finally, we evaluate the objective function, given solution (x k ) k ∈ F returned by Algorithm 2, and under the assumption that u k are of the form (7). Since \( \sum_{k\in F}{u}_k\left({\widetilde {x}}_k\right)\ge \sum_{k\in F}{u}_k\left({x}_k^{\ast}\right)= O P T \), we have:

$$ \sum_{k\in F}{u}_{k}(x_{k}) = \sum_{k\in F}{u}_{k}(\frac{1}{e}\widetilde{x}_{\ k}) = e^{\gamma-1} \sum_{k\in F}{u}_{k}(\widetilde{x}_{\ k}) \geq e^{\gamma-1}OPT.\square$$

Table 1 contains results of computational experiments for several randomly generated input data sets, comparing performance of two presented approximation algorithms: values of solutions and corresponding running times (in secs.). Last two columns contain value of optimal solution (OPT) and running time of branch and cut algorithm from CPLEX solver; n is the number of nodes, d is the number of edges, and m is the number of flows.

Table 1 Performance evaluation of Algorithms 1 and 2.
Full size table

4 Conclusions

The utility-maximizing network design problem with iso-elastic utility functions has been shown to be NP-complete. Approximate solutions can be obtained in polynomial time deterministically, but presented study suggests that randomization may yield better results. As Algorithm 2 may fail to give a feasible solution, further investigations are needed to determine the required number of runs.