Computer Laboratory

Course material 2010–11

An Algebraic Approach to Internet Routing

Principal lecturer: Dr Timothy Griffin
Taken by: MPhil ACS

  • Approach 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 present 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.

    The course takes a high-level, top-down approach to the analysis and design of Internet routing protocols. We ask "WHAT problem is being solved?" before asking "HOW do we solve it?".

  • Goals On completion of this module students should:
    • understand the basics of semigroups and semirings,
    • be able to reason about and prove various properties of such algebraic structures,
    • understand applications of semirings and related structures in diverse fields of computer science and operations research,
    • have a deeper understanding of the applications of semirings and related structures to Internet routing.
  • (Evolving) Outline
    • pre-term recommended reading : [BC1975]
    • Week 1: Basics General introduction. Brief account of Internet routing. Introduction to semigroups, associated order relations, and semirings. [BC1975,GM2008,BT2010]
    • Week 2: More on semirings Solving path problems in graphs using matrix methods. [BC1975,GM2008,BT2010]
    • Week 3: constructions Semiring Constructions. [JS2002,GM2008,GG2007,RM2006]. Focus on lexicographic product [GG2007] and why "bisemigroup" framework [GG2008] is easier to work with for building semirings than directly implementing Manger's approach [RM2006].
    • Week 4: Review and Semimodules Modeling route redistribution with semimodules [BG2009].
    • Week 5: A mini-metalanguage for bisemigroups Applying some of the ideas of [GG2007] to semirings/bisemigroups, but with necessary AND sufficient conditions for each property of interest.
    • Week 6: Beyond Semirings Algebras of Monoid Endomprhisms (AMEs) [GM2008]. Using AMEs to define scoped product (a metric-dependent partition). Then we consider metric-neutral partitions.
    • Week 7: Living without distributivity Global vs. local optimality. Using Dijkstra's algorithm for computing local optima [SG2010]. Matrix methods, algorithms in the Bellman-Ford family, distributed versions [JS2003,JS2005,GG2008,SG2010].
    • Week 8: Return to mini-metalanguage
  • Lecture Slides
  • Assessment Problem sets are here L11_problem_sets_2010.pdf (currently contains only problem set 1).
    • set 1 due 22 October, 2010.
    • set 2 due 12 November, 2010.
    • set 3 due 1 December, 2010.
    • set 4 due 15 December, 2010.
  • Core Bibliography Clearly we will not have time to cover all of these papers in depth!
  • Additional (routing related) reading
    • [JS2002] J. L. Sobrinho, ”Algebra and Algorithms for QoS Path Computation and Hop- by-Hop Routing in the Internet,” IEEE/ACM Transactions on Networking , pp. 541-550, August 2002.
    • [JS2003] J. L. Sobrinho, ”Network Routing With Path Vector Protocols: Theory and Applications” in Proc. ACM SIGCOMM 2003, pp. 49-60, Karlsruhe, Germany, August 2003.
    • [JS2005] J. L. Sobrinho, ”An Algebraic Theory of Dynamic Network Routing,” IEEE/ACM Transactions on Networking, pp. 1160-1173, October 2005.
    • [RFC4264] RFC 4264: BGP Wedgies. Timothy G. Griffin and Geoff Huston.
    • [TG2009] A model of configuration languages for routing protocols. Philip J. Taylor and Timothy G. Griffin. PRESTO workshop (at SIGCOMM 2009)
    • [GG2008] Increasing Bisemigroups and Algebraic Routing. Timothy G. Griffin and Alexander Gurney, RelMiCS10, April 2008.
  • Additional reading (path algorithms, applications of semirings in Computer Science)
    • [LeBT2004] Network Calculus Jean-Yves Le Boudec and Patrick Thiran
    • Transitive closure and related semiring properties via eliminants. S. Kamal Abdali and B. David Saunders. Theoretical Computer Science Volume 40, 1985, Pages 257-274 Eleventh International Colloquium on Automata, Languages and Programming. From ScienceDirect
    • Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains. Morten Kühnrich, Stefan Schwoon, Jiří Srba, Stefan Kiefer. http://arxiv.org/abs/0901.0501
    • An Incremental Algorithm for a Generalization of the Shortest-Path Problem. G. Ramalingam, Thomas Reps. (1992) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.6796

Last update : Fri Nov 26 15:24:47 GMT 2010