Course pages 2014–15
Algebraic Path Problems, with applications to Internet Routing
- Lecture slides
- L11_2014_Lecture01.pdf
- L11_2014_Lecture02_03.pdf (spilled into Lecture 4!)
- L11_2014_Lecture05_07.pdf
- L11_2014_Lectures08_09.pdf
- L11_2014_Lecture10_11.pdf
- L11_2014_Lectures_12_13_14.pdf (spilled into Lecture 15!)
- L11_2014_Lecture_16.pdf
- Required Reading
- An Algebra for Network Routing Problems. B. A. CARRÉ (1970).
- Algebra and algorithms for QoS path computation and hop-by-hop routing in the internet. João Luís Sobrinho. IEEE/ACM Transactions on Networking (TON). Volume 10 Issue 4, August 2002.
- Lexicographic Products in Metarouting. Alexander Gurney, Timothy G. Griffin. International Conference on Network Protocols (ICNP), October 2007, Beijing.
- On the Forwarding Paths Produced by Internet Routing Algorithms. Seweryn Dynerowicz (University of Namur, Belgium), Timothy G. Griffin. ICNP 2013.
- Routing in Equilibrium. Joao Luis Sobrinho and Timothy G. Griffin. The 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2010).
- On reserve in CL 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
- Fun
- Number of semigroups of order n.
- Number of partially ordered sets of order n.
- Fun with semirings: a functional pearl on the abuse of linear algebra. Stephen Dolan. Proceeding of the 18th ACM SIGPLAN international conference on Functional programming (ICFP 2013).
- Selected RFCs from the The Internet Engineering Task Force (IETF)
- RFC 1058: Routing Information Protocol (RIP). C. Hedrick (1988)
- RFC 2328 : OSPF Version 2. J. Moy. (1998) .
- RFC 4271: A Border Gateway Protocol 4 (BGP-4). Y. Rekhter, T. Li, S. Hares. (2006)
- RFC 4264: BGP Wedgies. Timothy G. Griffin and Geoff Huston.
- Further reading
- A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph. Alberto Martelli. Journal of the ACM (JACM). Volume 23, Issue 1, Jan. 1976.
- An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset. S. Tsukiyama, I. Shirakawa, H. Ozaki, H. Ariyoshi. Journal of the ACM (JACM). Volume 27 Issue 4, Oct. 1980.
- Bottleneck shortest paths on a partially ordered scale. J. Monnot, O. Spanjaard. 4OR, volume 1, 2003.
- Semiring Frameworks and Algorithms for Shortest-Distance Problems. Mehryar Mohri. Journal of Automata, Languages and Combinatorics. Volume 7 Issue 3, January 2002.
- Trust Evaluation in Ad-Hoc Networks. George Theodorakopoulos, John S. Baras. Proceeding of the 3rd ACM workshop on Wireless security, 2004.
- Maximizable routing metrics. Mohamed G. Gouda, Marco Schneider. Journal IEEE/ACM Transactions on Networking (TON). Volume 11 Issue 4, August 2003. Pages 663 - 675.
- MPhil project/essay suggestions.
- Explore a topic of these lectures or the Further reading using the Coq interactive theorem prover. If interested, talk to Tim.