NICTA
UNSW
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.
@misc{Hfner_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} }