Course material 2010–11
An Algebraic Approach to Internet Routing
A great deal of of interesting work was done in the 1970s in generalizing shortest
path algorithms to a wide class of semirings — called ”path algebras” or ”dioids”.
Although the evolution of Internet Routing protocols does not seem to have
taken much inspiration from this work, recent reverse engineering efforts have
demonstrated that an algebraic approach is very useful for both understanding
existing protocols and for exploring the design space of future Internet routing
protocols. This course is intended present the basic mathematics needed to
understand this approach. No previous background will be assumed. The course
will start from scratch and end with open research problems. Many examples
inspired by Internet Routing will be presented along the way.
The course takes a high-level, top-down approach to the analysis and design of Internet routing protocols. We ask "WHAT problem is being solved?" before asking "HOW do we solve it?".
On completion of this module students should:
- understand the basics of semigroups and semirings,
- be able to reason about and prove various properties of such algebraic structures,
- understand applications of semirings and related structures in diverse fields of computer science and operations research,
- have a deeper understanding of the applications of semirings and related structures to Internet routing.
- (Evolving) Outline
- pre-term recommended reading : [BC1975]
- Week 1: Basics General introduction. Brief account of Internet routing. Introduction to semigroups, associated order relations, and semirings. [BC1975,GM2008,BT2010]
- Week 2: More on semirings Solving path problems in graphs using matrix methods. [BC1975,GM2008,BT2010]
- Week 3: constructions Semiring Constructions. [JS2002,GM2008,GG2007,RM2006]. Focus on lexicographic product [GG2007] and why "bisemigroup" framework [GG2008] is easier to work with for building semirings than directly implementing Manger's approach [RM2006].
- Week 4: Review and Semimodules Modeling route redistribution with semimodules [BG2009].
- Week 5: A mini-metalanguage for bisemigroups Applying some of the ideas of [GG2007] to semirings/bisemigroups, but with necessary AND sufficient conditions for each property of interest.
- Week 6: Beyond Semirings Algebras of Monoid Endomprhisms (AMEs) [GM2008]. Using AMEs to define scoped product (a metric-dependent partition). Then we consider metric-neutral partitions.
- Week 7: Living without distributivity Global vs. local optimality. Using Dijkstra's algorithm for computing local optima [SG2010]. Matrix methods, algorithms in the Bellman-Ford family, distributed versions [JS2003,JS2005,GG2008,SG2010].
- Week 8: Return to mini-metalanguage
- Lecture Slides
- Slides from last year : http://www.cl.cam.ac.uk/teaching/0910/L11/.
- Slides rewritten for this year will be produced and posted here during the term.
- Lectures 1-4: (Updated 18 Oct.) One slide per page : L11_2010_01_04.pdf. Two slides per page : L11_2010_01_04_2up.pdf.
- Lectures 5 and 6: One slide per page : L11_2010_05_06.pdf. Two slides per page : L11_2010_05_06_2up.pdf.
- Lecture 7 : Review, no slides.
- Lecture 8: Semimodules and route redistribution. One slide per page : L11_2010_lecture_08.pdf. Two slides per page : L11_2010_lecture_08_2up.pdf.
- Lecture 9: A mini-metalanguage. One slide per page : L11_2010_lec09.pdf.
- Lectures 10 and 11: Algebras of Monoid Endomprhisms (AMEs). One slide per page : L11_2010_lec10.pdf. Two slides per page : L11_2010_lec10_2up.pdf.
- Lectures 12: Clean (metric-neutral) partitions. One slide per page : L11_2010_lec12.pdf. Two slides per page : L11_2010_lec12_2up.pdf.
- Lectures 13 and 14: Routing in Equilibrium : L11_2010_lec13_14.pdf. (Corrections made on Friday, 26 November).
- Assessment Problem sets are here L11_problem_sets_2010.pdf (currently contains only problem set 1).
- set 1 due 22 October, 2010.
- set 2 due 12 November, 2010.
- set 3 due 1 December, 2010.
- set 4 due 15 December, 2010.
- Core Bibliography
Clearly we will not have time to cover all of these papers in depth!
- [BC1975] Regular Algebra Applied to Path-Finding Problems. R.C. Backhouse and B.A.Carr J.Inst.Maths.Applics (1975) 15, 161–186.
- [GM2008] Graphs, Dioids and Semirings : New Models and Algorithms, by Michel Gondran , Michel Minoux. (On reserve in Lab Library) Chapter 8 is on-line : Collected Examples of Monoids, (Pre)-Semirings and Dioids.
- [BT2010] Path problems in networks. John S. Baras and George Theodorakopoulos. Morgan and Claypool, 2010. (On reserve in Lab Library)
- [GS2005] Metarouting. Timothy G. Griffin and João Luís Sobrinho. SIGCOMM 2005.
- [RM2006] R.Manger, A Catalogue of Useful Composite Semirings for Solving Path Problems in Graphs. Proceedings of the 11th International Conference on Operational Research, KOI 2006, Pula, Croatia, September 27 – 29, 2006. Page 13 of http://www.oliver.efpu.hr/koi06/koi06_proceedings.pdf
- [GG2007] Lexicographic Products in Metarouting. Alexander Gurney, Timothy G. Griffin. ICNP, October 2007, Beijing.
- [BG2009] A model of Internet routing using semi-modules. John N. Billings and Timothy G. Griffin. RelMiCS11/AKA6, November 2009.
- [LXZ2010] Theory and New Primitives for Safely Connecting Routing Protocol Instances. Franck Le, Geoffrey Xie, Hui Zhang. SIGCOMM 2010.
- [SG2010] Routing in Equilibrium. Joao Luis Sobrinho and Timothy G. Griffin. The 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2010).
- Additional (routing related) reading
- [JS2002] J. L. Sobrinho, ”Algebra and Algorithms for QoS Path Computation and Hop- by-Hop Routing in the Internet,” IEEE/ACM Transactions on Networking , pp. 541-550, August 2002.
- [JS2003] J. L. Sobrinho, ”Network Routing With Path Vector Protocols: Theory and Applications” in Proc. ACM SIGCOMM 2003, pp. 49-60, Karlsruhe, Germany, August 2003.
- [JS2005] J. L. Sobrinho, ”An Algebraic Theory of Dynamic Network Routing,” IEEE/ACM Transactions on Networking, pp. 1160-1173, October 2005.
- [RFC4264] RFC 4264: BGP Wedgies. Timothy G. Griffin and Geoff Huston.
- [TG2009] A model of configuration languages for routing protocols. Philip J. Taylor and Timothy G. Griffin. PRESTO workshop (at SIGCOMM 2009)
- [GG2008] Increasing Bisemigroups and Algebraic Routing. Timothy G. Griffin and Alexander Gurney, RelMiCS10, April 2008.
- Additional reading (path algorithms, applications of semirings in Computer Science)
- [LeBT2004] Network Calculus Jean-Yves Le Boudec and Patrick Thiran
- Transitive closure and related semiring properties via eliminants. S. Kamal Abdali and B. David Saunders. Theoretical Computer Science Volume 40, 1985, Pages 257-274 Eleventh International Colloquium on Automata, Languages and Programming. From ScienceDirect
- Interprocedural Dataflow Analysis over Weight Domains with Infinite Descending Chains. Morten Kühnrich, Stefan Schwoon, Jiří Srba, Stefan Kiefer. http://arxiv.org/abs/0901.0501
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem. G. Ramalingam, Thomas Reps. (1992) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.6796