An Algebraic Approach to Internet Routing
2009–10

Principal lecturer: Dr Timothy G. Griffin
Taken by: MPhil ACS

• Approach 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?".
• Lecture Slides
  • Lectures 1-3: One slide per page : L11_01_02_03.pdf. Two slides per page : L11_01_02_03_2up.pdf.
  • Lectures 4-8 : One slide per page : L11_04_08.pdf.
  • Lecture 9 : Talk slides from RelMiCS11/AKA6. One slide per page : griffin_relmics_2009.pdf. Two slides per page : griffin_relmics_2009_2up.pdf.
  • Lectures 15-16: One slide per page : L11_15_16.pdf. Two slides per page : L11_15_16_2up.pdf.
• Assessment Four exercises sheets.
• (Tentative) Outline
  • Week 1: General introduction. Brief account of Internet routing. Introduction to Semirings. [BC1975,GM2008]
  • Week 2: Semigroups and related order theory. Semirings [BC1975,GM2008]
  • Week 3: Semiring Constructions. [JS2002,GG2007,LeBT2004]
  • Week 4: Beyond Semirings, and living without distributivity [JS2003,JS2005,GG2008].
  • Week 5: Algorithmics. Matrix methods. Bellman-Ford. Dijkstra. Distributed algorithms.
  • Week 6: Internet Routing I : OSPF, ISIS, RIP, EIGRP, BGP. Internet Routing II : route redistribution. [BG2009]
  • Week 7: Internet Routing III : interdomain routing (BGP) [RFC4264]
  • Week 8: Metarouting [GS2005,BTG2007,TG2009].
• Bibliography Clearly we will not have time to cover all of these papers in depth!
  • [BC1975] Regular Algebra Applied to Path-Finding Problems. R.C. Backhouse and B.A.Carr J.Inst.Maths.Applics (1975) 15, 161–186.
  • [BG2009] A model of Internet routing using semi-modules. John N. Billings and Timothy G. Griffin. RelMiCS11/AKA6, November 2009.
  • [LeBT2004] Network Calculus Jean-Yves Le Boudec and Patrick Thiran
  • [BTG2007] An architecture for metarouting. John N. Billings, Philip J. Taylor, Timothy G. Griffin. Routing in Next Generation Workshop (RiNG), Madrid, December 2007.
  • [GG2007] Lexicographic Products in Metarouting. Alexander Gurney, Timothy G. Griffin. ICNP, October 2007, Beijing.
  • [GG2008] Increasing Bisemigroups and Algebraic Routing. Timothy G. Griffin and Alexander Gurney, RelMiCS10, April 2008.
  • [GM2008] Graphs, Dioids and Semirings : New Models and Algorithms, by Michel Gondran , Michel Minoux.
  • [GS2005] Metarouting. Timothy G. Griffin and João Luís Sobrinho. SIGCOMM 2005.
  • [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)

Last update : Thu Nov 26 13:45:37 GMT 2009