# Routing Path Assignment for Joint Load Balancing and Fast Failure Recovery in IP Network
## 1 Introduction  
IP networks use routing protocols to derive the shortest paths for traffic delivery. These routing protocols, including Open Shortest Path First (OSPF) and Intermediate System-Intermediate System (IS-IS), have been proven to be highly reliable and robust. However, it is challenging to conduct traffic engineering for a network using only shortest path routing. Conventionally, the only way to change routing paths in an IP network is to modify the link weights [1; 2; 3; 4; 5]. Because a router in an IP network can see the weight of each link, changing the weight of a single link would change the routing of many flows. Determining a set of link weights for a large network is quite challenging. When a link weight system is assigned, only the paths with the lowest costs can be used. As a result, not every desired routing path can be realized in conventional IP networks. By separating the control plane and the data plane, Software Defined Networking (SDN) uses central control to achieve flexible routing and fine-grained traffic management. However, SDN introduces new challenges such as controller overhead and failover latency. In addition, there are already many routers in existing networks. By merging the benefits from the distributed control of conventional IP routing protocols and the centralized control of the SDN network, Fibbing [6; 7] realizes the goal of centralized control on top of the distributed routing in IP networks. A Fibbing network consists of IP routers and a system controller. The routers use the standard unmodified OSPF routing protocol [8]. The system controller is responsible for introducing fake messages into the network. The purpose of the fake messages is used to cheat the real routers. By manipulating the virtual topology, the Fibbing controller can steer a flow to any specific path; thus, it can achieve highly flexible routing in an IP network. The Fibbing controller cleverly uses the OSPF protocol to broadcast additional link state advertisements (LSAs) into the network to generate the desired virtual topology. These LSAs are fake messages. In a Fibbing network, type 5 LSA is the key for traffic steering. A type 5 LSA broadcasted by the Fibbing controller includes two significant pieces of information. First, the LSA indicates a fake node and a specific address space that can be reached via the fake node. Second, it specifies the path cost from the fake node to the specified address space. Although the routers inside the network still follow shortest path routing, the introduced fake nodes change the network topology and the metric link system. Consequently, flows are steered to the desired paths in the physical network. An example is shown in Figure 1. There are six routers (A, B, C, D, E, F) in the network. In the absence of the fake node F, the flow from host H1 to host H2 follows H1\(\rightarrow\)A\(\rightarrow\)B\(\rightarrow\)C\(\rightarrow\)H2 which is the shortest path between H1 and H2. After insertion of the fake node P, the path cost from node P to host H2 is 1. As a result, the fake node P becomes the next-hop node for A, and the new path becomes H1\(\rightarrow\)A\(\rightarrow\)D\(\rightarrow\)E\(\rightarrow\)F\(\rightarrow\)C\(\rightarrow\)H2. In [9], we formulate the load-balanced routing problem as an ILP program. The output of the ILP program is used to deploy the fake nodes to provision one path for each OD pair in the Fibbing controlled network. COYOTE [10] takes advantage of ECMP further to enhance network control flexibility in a Fibbing network. As a result, an OD pair can be assigned more than one path to deliver its traffic. More importantly, not only the desired routing paths but also the ratios to allocate demand to the paths can be specified. In [11], the authors take traffic uncertainty into consideration in a Fibbing network. An algorithm is proposed to determine the oblivious routing paths. In [12], we use Fibbing to design energy-efficient IP networks.