An Algebraic Approach to Internet Routing: Solving Path Problems in Graphs

Timothy Griffin
University of Cambridge

A great deal of of interesting work was done in the 1970s in generalizing shortest path algorithms to a wide class of semirings -- called "path algebras" or "dioids." Although the evolution of Internet Routing protocols does not seem to have taken much inspiration from this work, recent "reverse engineering"
efforts have demonstrated that an algebraic approach is very useful for both understanding existing protocols and for exploring the design space of future Internet routing protocols. This course is intended teach participants the basic mathematics needed to understand this approach.
No previous background will be assumed. The course will start from scratch and end with open research problems. Many examples inspired by Internet Routing will be presented along the way.

Back to Internet MRA Tutorials