Optimization Phase

In the optimization phase, we compute $\alpha$ and $\beta$ values that satisfy the constraints for each pair $(i,p)$. In theory, any settings that satisfy the constraints would achieve our optimization goal. However, several practical issues drive how we set up the optimization problem:

• Finite-precision parameter values: The $\alpha$ and $\beta$ values should have finite precision to be configured and stored on the routers. Since the parameter values only have meaning relative to each other, we can limit ourselves to considering integer solutions. This leads us to apply integer programming to solve the problem.

• Limiting the number of unique parameter values: To reduce the overhead of configuring and storing the $\alpha$ and $\beta$ parameters, we prefer solutions that minimize the number of unique values. As such, we attempt to minimize an objective function that is the sum across all of the $\alpha$ and $\beta$ values.

• Robustness to unplanned events: Although we optimize the parameters based on the topology changes in $\Delta G$, the real network might experience events outside of our model. If optimizing based on $\Delta G$ results in solutions with $\alpha = 0$ for an $(i,p)$ pair, then router $i$ would never adapt to a change in IGP distance, however large. To increase the robustness to unplanned events, we add an extra constraint that $\alpha(i,p,e)>0$ for all $i$, $p$, and $e$.

We solve the integer-programming problem for each $(i,p)$ pair using CPLEX [17] with AMPL. Although integer-programming problems are sometimes difficult to solve, our constraints are typically easy to satisfy because many constraints are identical or are subsumed by other constraints. For instance, the second constraint in Figure 3(b) is stricter than the first constraint (i.e., because $4\alpha_B < 6\alpha_B$). In fact, for most of the $(i,p)$ pairs, CPLEX computes the values of $\alpha$ and $\beta$ during a pre-processing phase that analyzes the constraints. Very few $(i,p)$ pairs required more than three simplex iterations in the root node of the branch-and-bound tree to identify parameters that satisfy the constraints and minimize the objective function. Still, for arbitrary topologies and graph transformations, we could conceivably encounter a scenario where no parameter setting would satisfy every constraint. A scenario like this, should it arise, could be handled by an extension to the integer program to minimize the number of constraints that are violated. This could be achieved by including an extra error term in each constraint and selecting an objective function that minimizes the total error.