Finding our way around routing algebras

Add to your list(s) Download to your calendar using vCal

• Matthew Daggitt
• Friday 26 February 2016, 11:00-12:00
• Rainbow Room (FS07), Computer Laboratory.

If you have a question about this talk, please contact Ian Orton.

Despite playing a crucial role in almost every part of modern technology, we still do not fully understand the behaviour of routing algorithms and protocols. Typically the difficult questions are avoided at undergraduate level by teaching routing algorithms in the world of semirings which, while having nice properties, don’t possess the required expressibility for useful real world protocols.

In this talk I’ll outline how any routing problem can be viewed from an algebraic perspective and show how this allows us to better reason about their behaviour. In particular I’ll cover the difficulties of moving from distributive algebras, where everyone in the network agrees on the best paths, to non-distributive algebras, where people disagree over which paths should be taken. Finally I’ll provide a high-level overview of my new, more general proof for the convergence of certain classes of non-distributive algebras.

Covering:

• A recap of the Bellman-Ford algorithm (with distributed variants)
• Its behaviour in an idealised world of distributive algebras
• Why distributive algebras tend not to be used in practice
• The convergence properties we can salvage from non-distributive algebras

Prerequisites:

• Not much. Basic familiarity with the Bellman-Ford/Dijkstra routing algorithms would be a plus, but not necessary!

This talk is part of the Logic & Semantics for Dummies series.

This talk is included in these lists:

• Logic & Semantics for Dummies
• Rainbow Room (FS07), Computer Laboratory
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.