Enhanced Logical Representations of a Real Network Based on an Algebraic Model

Abstract

The algebraic model and logical representations of a real network are important but very challenging issues in automatic network verification. In this paper, we abstract the concrete network to its corresponding abstract graph with enhanced vertices and edges by splitting the vertices according to the protocols that they run. Based on classical routing algebra, we consider combining the interactions of different protocols and routing records and then give a newly modified algebraic structure. To apply the abstract modified algebra routing into the concrete network, we make use of the SMT solver to encode the components of algebra into logical constraints motivated by the work of Ryan Beckett et al. By encoding the network behaviors and properties into logical formulas, we can compute whether the experimental network that we configured satisfies any property, including reachability, routing loop, and so on. In the previous work, the routing algebra or the representation of the network is only applied to several network properties. However, in this paper, we extract all kinds of properties into exact logical formulas.

Keywords

• Logical formula
• network verification
• network protocols
• routing algebra
• SMT