Scientific Computing and Numerics (SCAN) Seminar

Kevin TangCornell University
HALO: Hop-by-hop adaptive link-state optimal routing

Monday, October 7, 2013 - 1:25pm
Upson 315

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 algorithms exist, they tend to be either not linkstate algorithms or to require source routing characteristics that make them difficult to implement. In this talk, I will introduce HALO, the first optimal link-state routing algorithm with hop-by-hop forwarding, where link weights can be calculated locally. Furthermore, our solution can adapt to changing traffic patterns automatically. The optimality of the algorithm is proved theoretically and also verified numerically. The talk will emphasize the mathematical part of this project (problem formulation, dynamics description, proof of convergence and optimality) although engineering implmenetation part will also be briefly covered.