# Routing Path Assignment for Joint Load Balancing and Fast Failure Recovery in IP Network
## 3 Optimization Models
### Load Balancing and Node Failure Protection (LB&NFP)
For destination node \(d\), Constraint (11) requires that if link \(l\) is used to carry traffic with destination \(d\) in the normal state, the potential of the upstream node of link \(l\) must be higher than the potential of the downstream node of link \(l\). Because any non-zero \(x_{dl}\) enforces \(y_{dl}\) become 1, if link \(l\) is used to carry traffic with destination \(d\) in the normal state, the potential of the upstream node of link \(l\) must be higher than the potential of the downstream node of link \(l\). More specifically, no matter the network is operating in which state \(s\), any path \((n_{1},\,n_{2},\,\ldots,\,d)\) that is used to carry non-zero traffic with destination node \(d\) in the normal state, the order of node potential is \(p_{n1d}^{s}>p_{n2d}^{s}>\ldots>p_{dd}^{s}\). Constraint (11) enforces the order of potential nodes within a single path (i.e., a traffic branch). However, it does not restrict the relationship between two nodes that belong to different branches. To enable taking an R3 neighbor to reroute traffic, we include Constraint (12) in the formulation. When a node failure happens, an upstream node with high potential can reroute, interrupting traffic to a neighbor with low potential if it is a node in a different branch. Because we only allow traffic to be delivered from a high potential node to a low potential node, loop free is guaranteed in the network whether it is in the normal or failure state. Constraint (14) guarantees 100% survivability against any single node failure. It requires that every node has at least one neighbor node to reroute traffic while the network is in a failure state. On the left-hand side of the constraint, when node \(s\) fails, every node \(n\) that is a neighbor of \(s\) must still be able to send its traffic to destination \(d\). After excluding the link (\(n\), \(s\)), if node \(n\) has a link with \(y_{dl}=1\) or \(z_{dl}^{s}=1\) means node \(n\) has a higher potential than the head node of link \(l\), and node \(n\) can take link \(l\) to deliver traffic with destination \(d\) without generating any loops. Based on the output of LB&NLP, we can determine the deployment of the fake nodes. The acyclic graph for the working paths can be obtained by collecting the links with a non-zero value of \(x\). The backup path planning can be derived from \(y\) and \(z\). Suppose node \(n\) uses multiple outgoing links to carry traffic with destination d in the normal state. In that case, we do not need to deploy additional fake nodes for \(n\) to reroute traffic against any of its downstream node failures. This is the case of node X shown in Figure 3. Node X always has an R1 neighbor to recover the failure. Suppose node \(n\) has only one single next-hop node \(j\) for traffic delivery with destination \(d\). We have to deploy a fake node to reroute the traffic when \(j\) fails. The neighbor for the reroute is either an R2 or an R3 neighbor. According to Constraint (14), there must be at least one outgoing link \(l\) of node \(n\) with \(y_{dl}=1\) or \(z_{dl}^{s}=1\). We can select any link \(l\) with \(y_{dl}=1\) or \(z_{dl}^{s}=1\) to be used for node \(n\) to reroute traffic with destination \(d\).