| | An Algebraic Approach to Internet Routing 2009–10
Principal lecturer: Dr Timothy G. Griffin Taken by: MPhil ACS
- Approach
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?".
- Lecture Slides
- Assessment Four exercises sheets.
- (Tentative) Outline
- Week 1:
General introduction. Brief account of Internet routing. Introduction to Semirings. [BC1975,GM2008]
- Week 2:
Semigroups and related order theory. Semirings [BC1975,GM2008]
- Week 3:
Semiring Constructions. [JS2002,GG2007,LeBT2004]
- Week 4:
Beyond Semirings, and
living without distributivity [JS2003,JS2005,GG2008].
- Week 5:
Algorithmics. Matrix methods. Bellman-Ford. Dijkstra.
Distributed algorithms.
- Week 6:
Internet Routing I : OSPF, ISIS, RIP, EIGRP, BGP.
Internet Routing II : route redistribution. [BG2009]
- Week 7:
Internet Routing III : interdomain routing (BGP) [RFC4264]
- Week 8:
Metarouting [GS2005,BTG2007,TG2009].
- 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.
- [BG2009]
A model of Internet routing using semi-modules.
John N. Billings and Timothy G. Griffin.
RelMiCS11/AKA6, November 2009.
- [LeBT2004]
Network Calculus
Jean-Yves Le Boudec and Patrick Thiran
- [BTG2007]
An architecture for metarouting.
John N. Billings, Philip J. Taylor, Timothy G. Griffin.
Routing in Next Generation Workshop (RiNG), Madrid, December 2007.
- [GG2007]
Lexicographic Products in Metarouting.
Alexander Gurney, Timothy G. Griffin.
ICNP, October 2007, Beijing.
- [GG2008]
Increasing Bisemigroups and Algebraic Routing.
Timothy G. Griffin and Alexander Gurney,
RelMiCS10, April 2008.
- [GM2008]
Graphs, Dioids and Semirings : New Models and Algorithms, by Michel Gondran , Michel Minoux.
- [GS2005]
Metarouting.
Timothy G. Griffin and João Luís Sobrinho.
SIGCOMM 2005.
- [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)
Last update : Thu Nov 26 13:45:37 GMT 2009
|