Finite Abstractions of Network Calculus Elements for Formal Verification of Network Bounds

Abstract

This thesis presents a method to semi-automate the reasoning about network bounds, namely the backlog and delay. Network Calculus offers a rich theory for modeling network elements. Using the modeling techniques of network calculus, network elements are represented by discrete-time systems whose dynamics are linear in min-plus algebra. From the state-space representation of a min-plus linear (MiPL) system, a finite-state symbolic model or quotient system can be constructed. The construction of such quotient systems is done by first partitioning the state-space according to the MiPL dynamics and certain atomic propositions defined over the states. The transitions between the quotient states are then computed based on the dynamical system. The resulting finite abstraction simulates the infinite-state discrete-time model, which permits applying formal verification to reason about the properties of the discrete-time system. The work is finalized by transforming the backlog and virtual delay properties of the original model to equivalent specifications, given by Linear Temporal Logic (LTL) formulas, on the finite abstraction.