An Algebraic Approach to Loop Free Routing

Validation models not only provide a better understanding of the system, but can also help in improving the reliability and robustness of the design. EIGRP metric can be modeled algebraically using semirings. EIGRP uses DUAL algorithm which is the basis for loop free routing with non lexical metric. DUAL was validated using the classical shortest path problem. However, it was shown that DUAL does not perform as expected in the absence of monotonicity. This article approaches loop free routing from an algebraic perspective. Conditions for loop free routing and the relations between them were presented algebraically and proved correct. Then, we investigate loop free routing in the presence and the absence of monotoncity.