Trustworthy Systems

Kleene modules for routing procedures

Authors

Peter Hoefner

NICTA

UNSW

Abstract

In the past, algebraic techniques based on semirings have been used describe shortest path algorithms and routing procedures. These approaches often use matrices over semirings/Kleene algebra, which form again a semiring/Kleene algebra. While these approaches work well for shortest paths algorithms, they fail when modelling timing aspects of routing algorithms. A major shortcoming is that at least one distributivity law has to be dropped on the level of semiring. This implies the loss of associativity on the matrix-level. In this talk I will present the shortcoming with the help of the Ad hoc On-Demand Distance Vector (AODV) routing protocol. AODV is a widely used and standardised routing protocol designed for wireless mesh networks (WMNs); AODV also forms the basis of new WMN routing protocols, such as the upcoming IEEE 802.11s wireless mesh network standard. I will argue that Kleene module can help in this regard. I will show how crucial aspects of routing protocols in general, and AODV in particular, can be modelled using modules. The talk will be concluded with some discussion on on-going developments and future work.

BibTeX Entry

  @misc{Hoefner_12_2,
    author           = {H\"ofner, Peter},
    booktitle        = {Workshop on Lattices and Relations},
    month            = aug,
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/6568.pdf},
    title            = {Kleene Modules for Routing Procedures},
    year             = {2012}
  }

Download