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 shortest-paths 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 Ad-Hoc Networks.
- Algorithm correctness. There is a general path-finding algorithm presented in Semiring Frameworks and Algorithms for Shortest-Distance Problems. Formalize this proof using an interactive theorem prover.
- Explore generic implementation of semiring-based path finding algorithms. Here's an example in Haskell.