Computer Laboratory > Teaching > Course material 2009–10 > An Algebraic Approach to Internet Routing


An Algebraic Approach to Internet Routing

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
  • 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!

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