Algebraic Path Problems, with applications to Internet Routing (Michaelmas 2020)

Change log

• 30 Nov: Added quizzes from last two years
• 29 Nov: Added slides on an example inspired by problem set 2. We will discuss this on Monday 30 Nov.
• 27 Nov: Added sample solutions to problem set 2.
• 27 Nov: Added Zoom meeting of 23 Nov.
• 18 Nov: Added slides and 2 videos on a continuation of multi-objective optimisation.
• 18 Nov: Added video for zoom meeting of 16 Nov.
• 13 Nov: Added slides and video on multi-objective optimisation.
• 09 Nov: Corrected solution for problem 6 of set 1.
• 09 Nov: Added video for zoom meeting of 9 Nov.
• 09 Nov: Added project examples from last year
• 09 Nov: Added slides and video on Martelli's semiring and reductions
• 08 Nov: Added solutions to problem set 1
• 01 Nov: Added problem set 2
• 01 Nov: Added slides and video on closing CAS after adding lexicographic combinator for bi-semigroups.
• 26 Oct: Added slides and video on lexicographic combinator for bi-semigroups.
• 26 Oct: Added slides and video on bi-semigroup combinators.
• 22 Oct: Added slides and video on semigroup combinators.
• 22 Oct: Added recording of second meeting.
• 18 Oct: Added slides and videos for two topics: 1) Semigroups and order, 2) Solving some matrix equations
• 14 Oct: Added lecture 2 slides and two related videos
• 13 Oct: Added short video on the last half of lecture 1 slides
• 12 Oct: Added recording of firt meeting.
• 12 Oct: Added lecture 1 slides and problem set 1.
• 11 Oct: Created page

Lecture slides and related materials (HERE)

Required Reading

• General Background
• An Algebra for Network Routing Problems. B. A. CARRÉ (1970).
• Semiring frameworks and algorithms for shortest-distance problems, M. Mohri
• 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.
• A survey on multi-constrained optimal path computation: Exact and approximate algorithms. Rosario G.Garroppo, Stefano Giordano, Luca Tavanti. Computer Networks Volume 54, Issue 17, 3 December 2010, Pages 3081-3107. (Follow instructions for institutional access.)
• Recent Research
• An algebraic theory of dynamic network routing João Luís Sobrinho. IEEE/ACM Transactions on NetworkingOctober 2005. (Follow instructions for institutional access.)
• 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.
• Rate of convergence of increasing path-vector routing protocols. Matthew L. Daggitt and Timothy G. Griffin. ICNP 2018.
• Routing on Multiple Optimality Criteria João Luís Sobrinho and Miguel Alves Ferreira SIGCOMM 2020

Optional Reading

• 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