HALO: Hop-by-hop adaptive link-state optimal routing

Current intra-domain routing protocols like OSPF and IS-IS use link-state routing algorithms with hop-by-hop forwarding that sacrifice traffic engineering performance for ease of implementation and management. Though optimal traffic engineering routing algorithms exist, they tend to be either not link-state algorithms or to require source routing---characteristics that make them difficult to implement. As the focus of this dissertation, we introduce HALO, the first optimal link-state routing algorithm with hop-by-hop forwarding. Furthermore, we will show that our solution can adapt to changing network topology and traffic patterns automatically because the link weights that the protocol uses are purely based on link rates---a useful property in dynamic network conditions. The optimality of the algorithm is proved, its search trajectory is compared with previously proposed optimal routing schemes and the affects of its co-existence with single path routing is studied. Additionally, we present the results of numerical evaluations on several test cases including the benchmark Abilene network that confirms the optimality of the algorithm, evaluates its speed of convergence and adaptivity under changing network conditions and provides evidence of the ability of the protocol to handle asynchrony in the network. We also present results from an experimental testbed that provides further evidence of the optimality, rate of convergence and adaptivity of the HALO protocol.