Simulation Phase

To illustrate how we construct the constraints on $\alpha$ and $\beta$ for the initial topology $G$ and each topology change $\delta$, consider the example in Figure 3(a). In the initial topology, node $A$ would select node $B$ as the egress point because $B$ is closer than $C$. We can express this by $m(A,p,B) < m(A,p,C)$ for topology $G$, as shown by the first constraint in Figure 3(b). Then, we consider each topology change $\delta$ and determine the preferred egress selection with the policy in mind, where $T=2$ and $\delta_1$ is the failure of the link with cost $4$ and $\delta_2$ is the failure of the links with costs $4$ and $6$. In the new graph $\delta_1(G)$, $A$ is closer to $C$ (with a distance $d(\delta_1(G),A,C)$ of $5$) than to $B$ (with a distance $d(\delta_1(G),A,B)$ of $6$). However, since $d(\delta_1(G),A,B) < 2 \cdot d(G,A,B)$, $A$ should continue to select egress-point $B$. This decision is expressed by the second equation in Figure 3(b). We use the same methodology to evaluate the best egress selection after $\delta_2$. In this case, the distance from $A$ to $B$ is above the threshold, so $A$ should switch to using egress-point $C$, as expressed by the third equation.

Figure 3: Example illustrating constraints on values of $\alpha$ and $\beta$.

More generally, our algorithm consists of two main steps. First, we compute the distances $d(\cdot,i,e)$ for the original graph $G$ and all transformations $\delta \in \Delta G$ using an all-pairs shortest path algorithm. (For simple graph transformations, such as all single-link failures, an incremental Dijkstra algorithm can reduce the overhead of computing the $\vert\Delta G\vert+1$ instances of the all-pairs shortest paths.) Then, we generate the constraints for each $(i,p)$ pair as presented in Figure 4.

Figure 4: Algorithm of the simulation phase.

Step $2$ runs once (on the original graph) and step $3(b)$ runs $\vert\Delta G\vert$ times (on each graph transformation), generating a constraint for each alternative to the desired egress point for that configuration. As a result, the algorithm produces $(\vert\Delta G\vert + 1) \cdot (\vert E(p)\vert - 1)$ constraints for each pair $(i,p)$. The size of $E(p)$ is limited by the number of edge nodes that have best BGP routes for a prefix; in practice, the size is usually one, two, or three, or at most ten. Fortunately, any prefixes that have the same egress set produce the same constraints, and the same values of $\alpha$ and $\beta$. The number of unique egress sets is typically orders of magnitude less than the number of prefixes, which substantially reduces the running time of the algorithm. In order to reduce the complexity and number of configurable parameters, we group all routers in the same PoP into a single node; these routers typically make the same BGP routing decisions anyway, since they essentially act as one larger router. Ultimately, the running time of the algorithm is dominated by the number of topology changes in $\Delta G$.