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

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

Author Contributor Faculty Department Programme Date2013-09-20

AbstractThis 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.

SubjectNetworked Control Systems

Network Calculus

Leaky Buckets

Latency-Rate Servers

Virtual Delay

Backlog

Min-Plus Systems

Piecewise-Affine Systems

Symbolic Models

Finite Abstractions

Formal Methods

Verification

Model Checking

Linear Temporal Logic

2013-10-07

Part of collectionStudent theses

Document typemaster thesis

Rights(c) 2013 Dahlan, B.