  An Algebraic Approach to Internet Routing 2009–10
Principal lecturer: Dr Timothy G. Griffin Taken by: MPhil ACS
 Approach
The course takes a highlevel, topdown 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. BellmanFord. 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 PathFinding Problems.
R.C. Backhouse and B.A.Carr J.Inst.Maths.Applics (1975) 15, 161–186.
 [BG2009]
A model of Internet routing using semimodules.
John N. Billings and Timothy G. Griffin.
RelMiCS11/AKA6, November 2009.
 [LeBT2004]
Network Calculus
JeanYves 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
byHop Routing in the Internet,” IEEE/ACM Transactions on Networking ,
pp. 541550, August 2002.
 [JS2003]
J. L. Sobrinho, ”Network Routing With Path Vector Protocols: Theory
and Applications” in Proc. ACM SIGCOMM 2003, pp. 4960, Karlsruhe,
Germany, August 2003.
 [JS2005]
J. L. Sobrinho, ”An Algebraic Theory of Dynamic Network Routing,”
IEEE/ACM Transactions on Networking, pp. 11601173, 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
