Course pages 2012–13
Algebraic Path Problems, with applications to Internet Routing
This course was presented in 2010 and the materials from that year can be found at http://www.cl.cam.ac.uk/teaching/1011/L11.
The 2012 course will cover much of the same ground but with (hopefully) better lecture notes (slides). New materials will appear as the course proceeds.
Last updated Tue Nov 27 09:35:45 GMT 2012 .
 Lecture slides
 Homework
 Readings
 Classics
 Related work
 Lexicographic Products in Metarouting. Alexander Gurney, Timothy G. Griffin. International Conference on Network Protocols (ICNP), October 2007, Beijing.
 Routing in Equilibrium. João Luís Sobrinho and Timothy G. Griffin. The 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2010).

On the interaction of multiple routing algorithms.
M. Abdul Alim, Timothy G. Griffin.
ACM CoNEXT 2011,
December 2011, Tokyo Japan.

Here is a version that corrects some notational confusion in Section 6 :
pdf.
 Number of semigroups of order n.
 Maximizable routing metrics. Mohamed G. Gouda, Marco Schneider. Journal IEEE/ACM Transactions on Networking (TON). Volume 11 Issue 4, August 2003. Pages 663  675.
 RFC 4264: BGP Wedgies. Timothy G. Griffin and Geoff Huston. The Internet Engineering Task Force (IETF)
 Exploring the stratified shortestpaths problem. Timothy G. Griffin. Networking Science. November 2011.
 On reserve in Lab Library
 Path problems in networks. John S. Baras and George Theodorakopoulos. Morgan and Claypool, 2010.
 Graphs, Dioids and Semirings : New Models and Algorithms, by Michel Gondran , Michel Minoux, 2008
 MPhil project/essay suggestions.
 Explore Trust Semirings (possible applicatiosn incude Ad Hoc networks, social networks, security metrics). An example is this paper : Trust Evaluation in AdHoc Networks.
 Algorithm correctness. There is a general pathfinding algorithm presented in Semiring Frameworks and Algorithms for ShortestDistance Problems. Formalize this proof using an interactive theorem prover.
 Explore generic implementation of semiringbased path finding algorithms. Here's an example in Haskell.