Evaluation

We evaluate the link utilization achieved by TIE on both the Abilene and ISP networks. We obtained the network topology $G$, the egress sets $\{E(p)\}$, and the traffic demands $v(i,p)$, as explained in the Appendix. We aggregate all traffic from an ingress $i$ to all destination prefixes $p$ that share the same egress set $E(p)$ to build the ingress to egress set traffic demand $v(i,E)$ for each unique egress set $E$. For this problem, we use the IGP link weights as configured in each network. The CPLEX solver took $0.1$ and $1.5$ seconds to run on the 196 MHz MIPS R10000 processor for the Abilene and ISP networks, respectively. The current network IGP configuration is set to achieve good link utilization assuming that the egress-selection mechanism is hot-potato routing. Therefore, we compare the utilization achieved using TIE with that achieved by hot-potato routing.

Table V presents the value of the objective function $\Phi$ for both topologies under both egress-selection policies. TIE's flexibility in balancing load allows us to find an optimal solution for both networks using the linear-programming relaxation. The solution using hot-potato routing is $40\%$ worse than that found using TIE for the ISP network. Hot-potato routing has a congestion function close to TIE for the Abilene network. However, even though the Abilene network is significantly under-utilized, TIE does offer some (admittedly modest) improvements to the objective function.

Table V: Comparison of the network congestion function $\Phi$ between hot-potato routing and TIE.

	Abilene Network	ISP Network
Hot-potato routing	$0.4513510071$	$8.990353677$
TIE	$0.4425879808$	$5.557480707$

Figure 8 shows the ratio of link utilization between hot-potato routing and TIE, for the ten most heavily-loaded links under hot-potato routing; link number $1$ is the most utilized link and number $10$ is the tenth most utilized. The TIE solution reduces the utilization of the most utilized link by $40.9\%$. Although TIE increases the load on some links (as illustrated by link $8$ in the figure), our solution reduces the utilization of two-thirds of the links, and the most utilized link in the TIE solution has $26.3\%$ less utilization than the most utilized link under hot-potato routing.

Figure 8: Comparison of link utilization with hot-potato routing and TIE.

In our ongoing work, we plan to compare the TIE solution with the loose lower bound achieved by multicommodity flow with no restrictions on using valid IGP paths. We also want to compare this solution with that achieved by using other traffic-engineering mechanisms: (i) heuristics for IGP link-weight optimization; (ii) heuristics for setting local-preference values in BGP import policies; and (iii) egress-point optimization where each router $i$ is forced to have a single ranking of egress points across all destination prefixes, as in Section II-B. These comparisons will help us understand how much of the performance benefit of TIE comes from the decoupling of egress selection from the IGP weights versus the ability to exert fine-grain control over the ranking of egress points.