An Algebraic Approach to Internet Routing
Principal lecturer: Dr Timothy G. Griffin
Taken by: MPhil ACS
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.
- 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:
Clearly we will not have time to cover all of these papers in depth!
Regular Algebra Applied to Path-Finding Problems.
R.C. Backhouse and B.A.Carr J.Inst.Maths.Applics (1975) 15, 161–186.
A model of Internet routing using semi-modules.
John N. Billings and Timothy G. Griffin.
RelMiCS11/AKA6, November 2009.
Jean-Yves Le Boudec and Patrick Thiran
An architecture for metarouting.
John N. Billings, Philip J. Taylor, Timothy G. Griffin.
Routing in Next Generation Workshop (RiNG), Madrid, December 2007.
Lexicographic Products in Metarouting.
Alexander Gurney, Timothy G. Griffin.
ICNP, October 2007, Beijing.
Increasing Bisemigroups and Algebraic Routing.
Timothy G. Griffin and Alexander Gurney,
RelMiCS10, April 2008.
Graphs, Dioids and Semirings : New Models and Algorithms, by Michel Gondran , Michel Minoux.
Timothy G. Griffin and João Luís Sobrinho.
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.
J. L. Sobrinho, ”Network Routing With Path Vector Protocols: Theory
and Applications” in Proc. ACM SIGCOMM 2003, pp. 49-60, Karlsruhe,
Germany, August 2003.
J. L. Sobrinho, ”An Algebraic Theory of Dynamic Network Routing,”
IEEE/ACM Transactions on Networking, pp. 1160-1173, October 2005.
RFC 4264: BGP Wedgies. Timothy G. Griffin and Geoff Huston.
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