skip to content

Department of Computer Science and Technology

 
Principal lecturer: 
Students: 
MPhil ACS, Part III
Term: 
Michaelmas term
Course code: 
L11
Prerequisites: 
An undergraduate course in discrete mathematics.
Hours: 
16

Aims

A great deal 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 to 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.

Syllabus

  • History, overview, motivation (1L)
  • Semigroups and order theory (2L)
  • Semirings and related structures (3L)
  • Algorithms for solving algebraic path problems in graphs (3L)
  • Metarouting (2L)
  • Algebraic models of Internet Routing (4L)

Objectives

On completion of this module, students should:

  • understand the basics of semirings,
  • be able to reason about and prove various properties of algebraic structures,
  • understand applications of semirings and related structures in diverse fields of computer science and operations research,
  • have a deep understanding of the applications of semirings and related structures to Internet routing.

Coursework

Exercise sheets will be provided.

Practical work

Several MRE (metarouting toolkit, pronounced Mr. E or mystery) exercises will be assigned.

Assessment

  • 2 ticked exercises 10%
  • Test 30%
  • Project and report 60%

Recommended reading

Primary text: Gondran, M. and Minoux, M. (2008). Graphs, Dioids and Semirings – New Models and Algorithms. Springer.

Backhouse, R.C. and Carr, B.A. 'Regular Algebra Applied to Path-Finding Problems' J.Inst.Maths.Applics . (1975). 15, pp. 161-186
Griffin, T. G. and Gurney, A. Increasing Bisemigroups and Algebraic Routing, RelMiCS10, April 2008.
Griffin, T. G. and Sobrinho, J. L., Metarouting. SIGCOMM 2005
Gurney, A. and Griffin, T. G., Lexicographic Products in Metarouting. ICNP, October 2007, Beijing.
Sobrinho, J. L. “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.
Sobrinho, J. L. “Network Routing With Path Vector Protocols: Theory and Applications” in Proc. ACM SIGCOMM 2003, pp. 49-60, Karlsruhe, Germany, August 2003.
Sobrinho, J. L. “An Algebraic Theory of Dynamic Network Routing,” IEEE/ACM Transactions on Networking, pp. 1160-1173, October 2005.

Further Information

Due to COVID-19, the method of teaching for this module will be adjusted to cater for physical distancing and students who are working remotely. We will confirm precisely how the module will be taught closer to the start of term.