Problem Definition: Balancing Link Utilization

Traffic engineering--adapting the flow of traffic to the prevailing network conditions--is a common task that can be performed in several ways. Traffic engineering considers a network topology ($G$) with the capacity of each link ($c(\ell)$), and the traffic demands $v(i,p)$ (i.e., the volume of traffic to destination prefix $p$ that enters the network at ingress router $i$), as summarized in Table IV. The effects of the IGP weights on the intradomain paths can be represented by the routing matrix $R(i,e,\ell)$, which captures the fraction of traffic from router $i$ to router $e$ that traverses link $\ell$. If the network has one shortest path between $i$ and $e$, $R(i,e,\ell)$ is one for any link $\ell$ on that path, or zero otherwise; if multiple shortest paths exist, $R(i,e,\ell)$ may be fractional. The flow of traffic also depends on the egress set $E(p)$ and the egress point $b(i,p)$ that router $i$ uses to reach prefix $p$.

Table IV: Notation for the traffic-engineering problem

Link capacity	$c(\ell)$, for $\ell\in L$
Traffic demand	$v(i,p)$ for $i\in N$, $p\in P$
Routing matrix	$R(i,e,\ell)$, for $i,e \in N$, $\ell\in L$
Egress selection	$b(i,p)\in E(p)$ for $i\in N$, $p\in P$
Link traffic load	$t(\ell)$ for $\ell\in L$
Link utilization	$u(\ell)=t(\ell)/c(\ell)$, $\ell\in L$
Multicommodity flow path	$\tau(i,e,p) \subset G$
Decision variable	$x(i,e,p) \in \{0, 1\}$
Link congestion penalty	$\phi (u(\ell ))$, $\ell\in L$
Objective function	$\Phi=\sum_{\ell\in L} \phi(u(\ell))$

Traffic engineering involves tuning the network configuration to minimize some function of the load on the links. The load $t(\ell)$ on link $\ell$ can be determined as follows:

$$t(\ell) = \displaystyle \sum_{i \in N}\sum_{\tiny\begin{array}{c} p \in P,\\ b(i,p) = e, \\ e \in E(p) \end{array}} v(i,p) \cdot R(i,e,\ell)$$

and the resulting link utilization is $u(\ell)=t(\ell)/c(\ell)$. The common approach to traffic engineering is to formulate an optimization problem that minimizes an objective function that penalizes solutions in terms of the load they place on each link. In our work, we consider the function $\phi (u(\ell ))$ in Figure 7 that increasingly penalizes loads as they near or pass the link's capacity. This piecewise-linear function can be expressed by the equation

$$\phi(u(\ell)) = \left\{ \begin{array}{ll} u(\ell), & u(\ell) \in ... ...\ 5000 \cdot u(\ell) - 16318/3, & u(\ell) \in [11/10,\infty) \end{array}\right.$$ (1)

that was introduced in [19] and used in several other traffic-engineering studies. The network-wide objective function $\Phi$ is the sum of the link penalties--i.e., $\Phi=\sum_{\ell\in L} \phi(u(\ell))$.

Figure 7: Piecewise-linear penalty function $\phi (u(\ell ))$ versus link utilization

[angle=-90,scale=.3]cost-function.eps

Network administrators can minimize the objective function by changing the intradomain paths ( $R(i,e,\ell)$), interdomain routes ($E(p)$), or the egress-point selection ($b(i,p)$). Tuning the IGP link weights (to influence the intradomain paths) and the BGP policies (to influence the interdomain routes) lead to NP-complete optimization problems [9,7,8,6]. The computational intractability of these problems forces the use of local-search techniques that repeatedly evaluate parameter settings in the hope of finding a good solution. Although local-search heuristics often produce good parameter values [9,12], the solutions are not optimal and are not guaranteed to have performance that is close to optimal. In addition, the solutions require changing the IGP weights or BGP policies, which triggers routing-protocol convergence and leads to transient disruptions. In contrast, using TIE to control the egress-point selections $b(i,p)$ leads to a simpler optimization problem that does not require changes to the routing-protocol configuration. Since we are simply selecting among existing paths and not change the configuration of routing protocols, our approach does not trigger routing convergence.