Towards an Algebra of Routing Tables

erschienen 2011 in H. de Swart (eds.): Relational and Algebraic Methods in Computer Science (RAMiCS 12), LNCS 6663, 2011.

Abstract: We use well-known algebraic concepts like semirings and matrices to model and argue about Wireless Mesh Networks. These networks are used in a wide range of application areas, including public safety and transportation. Formal reasoning therefore seems to be necessary to guarantee safety and security. In this paper, we model a simplified algebraic version of the AODV protocol and provide some basic properties. For example we show that each node knows a route to the originator of a message (if there is one).