8/7/2015 11:30EE, Meyer 861


Scalable and Efficient Multipath Routing: Complexity and Algorithms

Janos Tapolcai and Gabor Retvari

Budapest University of Technology and Economics

A fundamental unsolved challenge in multipath routing is to provide a sufficient diversity of disjoint end-to-end paths, each one satisfying certain operational goals (e.g., shortest possible), without overwhelming the data plane with prohibitive amounts of forwarding state. In the presentation, we study the problem of finding a pair of shortest disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the underlying mathematical problem is NP-complete and we present heuristic algorithms that improve the known complexity bounds from cubic to the order of a single shortest path search. Finally, by extensive simulations we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1-5%), eventually opening the door for wide-scale multi path routing deployments.

Bio: Janos Tapolcai received his M.Sc. ('00 in Technical Informatics), Ph.D. ('05 in Computer Science) degrees from Budapest University of Technology and Economics (BME), Budapest, and D.Sc. ('13 in Engineering Science) from Hungarian Academy of Sciences (MTA). Currently he is an Associate Professor at the High-Speed Networks Laboratory at the Department of Telecommunications and Media Informatics at BME. His research interests include applied mathematics, combinatorial optimization, optical networks and IP routing, addressing and survivability. He is an author of over 110 scientific publications, he is the recipient of the Google Faculty Award and Best Paper Award in ICC'06, in DRCN'11. He is a TPC member of leading conferences such as IEEE INFOCOM (2012 - 2014), and is a winner of MTA Momentum (Lendulet) Program.

Gabor Retvari received the M.Sc. and Ph.D. degrees in electrical engineering from the Budapest University of Technology and Economics (BME). He is now a Senior Research Fellow at the High Speed Networks Laboratory, BME. He has been passionate about the questions of routing scalability for a long time and he has done plenty of research in this field, using a diverse set of mathematical tools ranging from abstract algebra to computational geometry and, more recently, information-theory. He maintains numerous open source scientific tools written in Perl, C and Haskell.