We present HALO (Hop-by-hop Adaptive Link-state Optimal routing), the first link-state routing solution with hop-by-hop packet forwarding that minimizes the cost of routing traffic through packet-switched networks. For stationary input traffic, we prove that HALO converges to the routing assignment that minimizes the cost of the network. Furthermore, our solution does not require traffic matrix as an explicit input and can adapt to changing traffic demand. We also report numerical and experimental evaluations that are used to confirm our theoretical predictions, explore additional aspects of the algorithm, and outline a proof-of-concept implementation of HALO.
Kevin Tang received his B.E degree with honor in electronics engineering from Tsinghua University, Beijing, China, in 1999, and his Ph.D. in electrical engineering with a minor in applied and computational mathematics from Caltech in 2006. He is currently an Associate Professor with the School of Electrical and Computer Engineering at Cornell University where he conducts research on the control and optimization of communication network. Dr. Tang received several awards from his research and teaching including the 2006 George B. Dantzig Dissertation Award from INFORMS, the 2007 Charles Wilts dissertation Prize from Caltech EE, the Michael Tien '72 Excellence in Teaching Award in 2011 from Cornell Engineering College, and the Presidential Early Career Award for Scientists and Engineers from the White House in 2012.