Solving the Traffic-Engineering Problem with TIE

Traffic engineering with TIE involves assigning each $(i,p)$ pair to an egress point $b(i,p)\in E(p)$ in a way that minimizes the objective function $\Phi$. A solution can be realized by setting $\beta(i,p,b(i,p))$ to a low value, while setting $\beta(i,p,e)$ to a high value for all $e\neq b(i,p)$, and all $\alpha$ values to zero. In contrast to the fixed-ranking scheme in Section II-B, we allow a router's ranking of egress points to differ across the prefixes. In practice, we envision solving richer optimization problems that consider robustness to changes in the network topology $G$, the egress sets $E(p)$, and the traffic demands $v(i,p)$, which would lead to solutions that assign values to both $\alpha$ and $\beta$. In this paper, we focus on fixed topology, egress sets, and traffic demands, to illustrate how TIE provides the flexibility needed to balance load across the links.

We formulate the egress-selection problem as a path-based multicommodity-flow problem that accounts for the constraints that the routing matrix $R(i,e,\ell)$ imposes on the flow of traffic. For a router $i$ and prefix $p$, we consider the topology $\tau(i,e,p)$ induced by the links $\ell\in L$ for which $R(i,e,\ell) > 0$. All links in the graph $\tau(i,e,p)$ can be used to route traffic from $i$ to $p$ through the egress point $e\in E(p)$. We call $\tau$ a path in the multicommodity-flow formulation. We represent the actual routing of the traffic from $i$ to $p$ by a $(0,1)$-decision variable $x(i,e,p)$, such that $x(i,e,p) = 1$ if and only if the path $\tau(i,e,p)$ is selected to send traffic from $i$ to $p$. The choice of a path $\tau$ determines the egress point $e\in E(p)$ selected. For all pairs $(i,p)$, the egress-selection problem requires that a single egress point $e\in E(p)$ be chosen. We express this requirement by the following equation:

$$\sum_{e \in E(p)} x(i,e,p) = 1.$$

The contribution of the traffic going from $i$ to $p$ to the load on link $\ell$ is the product of the traffic demand $v(i,p)$, the routing-matrix element $R(i,e,\ell)$, and the decision variable $x(i,e,p)$. The total load on a link is the sum of all the contributions, i.e.

$$t(\ell) = \sum_{i \in N}\sum_{p \in P}\sum_{e \in E(p)} v(i,p) \cdot R(i,e,\ell) \cdot x(i,e,p).$$

A piecewise-linear integer-programming formulation for the single egress-selection problem is to minimize the objective function $\Phi=\sum_{\ell\in L} \phi(u(\ell))$ such that the $(0,1)$-decision variables $x(i,e,p)$ sum to $1$ for each $(i,p)$ pair. Defining $\phi (u(\ell ))$ to be a linear variable and applying a standard transformation results in the linear integer-programming formulation:

$$\min \sum_{\ell \in L} \phi(u(\ell))$$ s.t.

$$u(\ell) = \Big(\sum_{i\in N}\sum_{p\in P}\sum_{e \in E(p)} v(i,p) \cdot R(i,e,l) \cdot x(i,e,p)\Big)/c(\ell), \; \forall l \in L,$$

$$\sum_{e \in E(p)} x(i,e,p) = 1, \; \forall i \in N, p \in P,$$

$$\phi(u(\ell)) \geq u(\ell),\; \forall l \in L,$$

$$\phi(u(\ell)) \geq 3 \cdot u(\ell) - 2/3,\; \forall l \in L,$$

$$\phi(u(\ell)) \geq 10 \cdot u(\ell) - 16/3,\; \forall l \in L,$$

$$\phi(u(\ell)) \geq 70 \cdot u(\ell) - 178/3,\; \forall l \in L,$$

$$\phi(u(\ell)) \geq 500 \cdot u(\ell) - 1468/3,\; \forall l \in L,$$

$$\phi(u(\ell)) \geq 5000 \cdot u(\ell) - 16318/3,\; \forall l \in L,$$

$$x(i,e,p) \in \{0,1\}, \; \forall i \in N, p \in P, e \in E(p),$$

$$\phi(u(\ell)) \geq 0, \; \forall l \in L.$$

However, in general, this integer multicommodity-flow problem is intractable. Instead, we consider its linear-programming relaxation obtained by relaxing the integrality constraints $x(i,e,p) \in \{0, 1\}$ to simply $x(i,e,p) \geq 0$. For both networks we consider, the CPLEX solver produced solutions with only integer values of $x(i,e,p)$, allowing us to configure the $\beta(i,p,e)$ values to pick the single egress point $b(i,p)$ for each $(i,p)$ pair. For situations where the solution of the linear-programming relaxation is fractional, applying a simple heuristic based on randomized rounding can produce a valid egress selection. For each pair $(i,p)$ with fractional $x(i,e,p)$ values, egress point $e\in E(p)$ is selected with probability $x(i,e,p)$. Randomized rounding is repeatedly applied and the best solution found is output by the algorithm.