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).
    • This file is a first cut at formalizing these results using Coq with ssreflect.
• 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.