Citation: Gurney, Alexander J. T. and Griffin, Timothy G. 2010. Neighbor-specific BGP: An algebraic exploration. Proceedings of the 18th IEEE International Conference on Network Protocols (ICNP 2010), Kyoto, pages 103–112.
Presentation slides (809 kB PDF).
Abstract: There are several situations in which it would be advantageous to allow route preferences to be dependent on which neighbor is to receive the route. This idea could be realised in many possible ways and could interact differently with other elements of route choice, such as filtering: not all of these will have the property that a unique routing solution can always be found. We develop an algebraic model of route selection to aid in the analysis of neighbor-specific preferences in multipath routing. Using this model, we are able to identify a set of such routing schemes in which convergence is guaranteed.
Citation: Gurney, Alexander J. T. 2009. Construction and verification of routing algebras. PhD thesis, University of Cambridge.
Abstract: Standard algorithms are known for finding the best routes in a network, for some given notion of route preference. Their operation succeeds when the preferences satisfy certain criteria, which can be expressed algebraically. The Internet has provided a wide variety of route-finding problems for which these criteria can be hard to verify, and the ambitions of network operators and researchers are more diverse still.
One solution is to provide a formal means of describing route preferences in such a way that their correctness criteria can be automatically verified. This thesis makes the following contributions:
Citation: Griffin, Timothy G. and Gurney, Alexander J. T. 2008. Increasing bisemigroups and algebraic routing. Proceedings of the 10th International Conference on Relational Methods in Computer Science (RelMiCS 10), Frauenworth, Germany. Also appeared as LNCS, volume 4988.
Abstract: The Internet protocol used today for global routing—the Border Gateway Protocol (BGP)—evolved in a rather organic manner without a clear theoretical foundation. This has stimulated a great deal of recent theoretical work in the networking community aimed at modeling BGP-like routing protocols. This paper attempts to make this work more accessible to a wider community by reformulating it in a purely algebraic setting. This leads to structures we call increasing bisemigroups, which are essentially non-distributive semirings with an additional order constraint. Solutions to path problems in graphs annotated over increasing bisemigroups represent locally optimal Nash-like equilibrium points rather than globally optimal paths as is the case with semiring routing.
Citation: Gurney, Alexander J. T. and Griffin, Timothy G. 2007. Lexicographic products in metarouting. Proceedings of the 15th IEEE International Conference on Network Protocols (ICNP 2007), Beijing.
Presentation slides (560k PDF).
Abstract: Routing protocols often keep track of multiple route metrics, where some metrics are more important than others. Route selection is then based on lexicographic comparison: the most important attribute of each route is considered first, and if this does not give enough information to decide which route is better, the next attribute is considered; and so on.
We investigate protocols that find globally optimal paths and protocols that find only locally optimal paths. In each case we characterize exactly when lexicographic products can be used to define well-behaved routing protocols. We apply our results to protocols that can partition a network into distinct administrative regions, such as OSPF areas and BGP autonomous systems. We show that in some cases this type of local autonomy is fully compatible with global optimality.
Third-year project: A component library for category theory constructions
— trying to do what Rydeheard and Burstall did (921k PDF) with ML programs representing various ideas from category theory, except I used C#. This was early days for the language (no generics yet, for example) so part of the plan was to explore how expressive it could be for this kind of problem. Anything higher-order turned out to be a bit tricky, but the object-oriented framework gave some neat payoffs for some constructions, in particular the various special kinds of colimits. Supervised by Alan Wood.
Fourth-year project: Supergraph enumeration for complex networks
— using combinatorial species theory to approximate the proportion of simple graphs that contain a triangle. Counting graphs is really quite difficult, and if we want to count only some graphs it's generally even harder. But by giving a species for a structure that is almost-but-not-quite a supergraph of K3, we can get an asymptotic result for the actual number of supergraphs of K3. (And indeed for Kn in general, where n ≥ 3.) Supervised by Gustav Delius. This project was originally supposed to be about random graphs in general, but after seeing François Bergeron's talk on species at CTCS 04 I realized that species theory could be useful for characterising certain kinds of structure that arise within graphs, including random graphs.
Departmental prize for outstanding achievement, 2005.
At Cambridge I have supervised students in: