Course pages 2013–14
Algebraic Path Problems, with applications to Internet Routing
Last updated Wed Dec 4 08:51:14 GMT 2013 .
- Lecture slides
- First four lectures: L11_2013_lec01_to_lec04.pdf. (Most Typos fixed!) See slide 46 for the first homework set.
- Lectures 05, 06, 07: L11_2013_lec05_07.pdf.
- Lecture 08: L11_2013_lec08.pdf.
- Lecture 09: L11_2013_lec09.pdf.
- Lectures 12, 13: L11_2013_lec12_13.pdf.
- Lectures 14, 15: L11_2013_lec14.pdf.
- Lecture 16: L11_2013_lec16.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.
- 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.