Alexander Gurney

Increasing bisemigroups and algebraic routing

Citation Timothy G. Griffin and Alexander J. T. Gurney. 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.