# 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)  
The second formulation determines working and backup path assignments to protect against any single node failure. Given a destination node, the collection of links used in the routing paths must become an acyclic graph. This property is true for the network operating in a normal state and true under any single node failure state. To maintain flow routing in an acyclic graph toward every destination node, we introduce the concept of node potential to facilitate the problem formulation. A packet can only be sent from a node with high potential to a node with low potential. This rule is applied for the packets forwarding in the normal state and the backup state. Because a flow can only be delivered from a high potential node to a low potential node, the routing path is guaranteed to be loop-free whether the network is in the normal or a failure state. Because we consider every node failure, the total number of failure states is the same as the number of nodes in the network. Each failure state is mapped to a single node in the network. The meaning of \(N\), \(L\), \(L_{n}^{out}\), \(L_{n}^{in}\), \(C_{l}\), and \(r_{nd}\) are the same as those used in the LBO formulation. The additional notations are listed below. Input Constants:  
\[ \begin{array}{ll}h(l):&\text{the head node of link }l;\\ t(l):&\text{the tail node of link }l;\\ M:&\text{a big number;}\\ N_{s}\;:&\text{set of nodes that are neighbors of node }s.\end{array} \]  
Decision Variables:  
\[ \begin{array}{ll}u:&\text{utilization on the most congested link;}\\ x_{dl}:&\text{total traffic with destination d carried on link }l;\\ y_{dl}:&\text{=1, if link }l\text{ is used to carry traffic with destination }d\text{ in the normal state; }=0,\\ &\text{otherwise;}\\ z_{dl}^{s}:&\text{=1, if link }l\text{ can be used to reroute packets with destination }d\text{ in state }s\\ &\text{=0, otherwise;}\\ p_{n,d}^{s}:&\text{the potential difference between node }n\text{ to node }d\text{ when network is in state }s.\end{array} \]  
Problem (LB&NFP):  
\[ \begin{array}{ll}\min\ u\\ \text{Subject to:}\\ \sum\limits_{l\in L_{dl}^{su}}x_{dl}-\sum\limits_{l\in L_{dl}^{su}}x_{dl}\;=r_ {nd}&\forall\;d\in N,\;n\in N\backslash\{d\}\\ \sum\limits_{l\in L_{dl}^{su}}x_{dl}\;=\;0&\forall\;d\in N\\ \sum\limits_{l\in L_{dl}^{su}}x_{dl}\;=\;\sum\limits_{n\in N}r_{nd}&\forall \;d\in N\\ \sum\limits_{d\in N}x_{dl}\;\leq\;u\text{C}_{l}&\forall\;l\in L\\ x_{dl}\;\leq\;y_{dl}\text{C}_{l}&\forall\;l\in L,s\in N,\;d\in N\\ p_{l}^{s}(l)d\;\;-p_{h(l)d}^{s}\;\geq\;M(y_{dl}-1)+1&\forall\;l\in L,s\in N,\;d \in N\\ p_{l(l)d}^{s}\;\;-p_{h(l)d}^{s}\;\geq\;M(z_{dl}^{s}-1)+1&\forall\;l\in L,s\in N,\;d\in N\\ p_{dl}^{s}\;=0&\forall\;d\in N,\;s\in N\\ \sum\limits_{l\in L_{dl}^{su}(n,s)}(y_{dl}\;+z_{dl}^{s})\geq 1&\forall\;n\in N _{s},\;d\in N\backslash\{s\},\;s\in N\\ x_{dl}\;\geq 0&\forall\;d\in N,\;l\in L\\ y_{dl}\in\{0\,,\,1\}&\forall\;d\in N,\;l\in L\\ z_{dl}^{s}\;\in\{0\,,\,1\}&\forall\;l\in L_{n}^{su}(n,s),\;n\in N_{s}\,,s\in N\\ p_{dl}^{s}\;\geq 0&\forall\;n\in N,\;s\in N,\;d\in N\\ \end{array}  \tag{10}\]  
For a directional link \(l=(a,b)\), traffic using the link must visit node \(a\) before node \(b\). Hence, we call node \(a\) the upstream node, and node \(b\) is the downstream node of this link \(l\). The first four constraints have appeared in Problem LBO. Constraint (10) is used to determine which link can deliver traffic in the normal state. If \(x_{dl}\) is non-zero, which means link \(l\) is used to carry traffic with destination \(d\) in the normal state, it results in \(y_{dl}\) becoming 1. Constraints (11), (12), and (13) are constraints to determine node potential. We have mentioned that if a feasible set of node potentials can be assigned to each node in every single node failure state, we can guarantee loop-free routing in the network.