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

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

Dahlan, B.

Mazo, M. (mentor)

Electrical Engineering, Mathematics and Computer Science

Delft Center for Systems and Control

Embedded Systems

2013-09-20

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.

Networked 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

http://resolver.tudelft.nl/uuid:c6a21f0e-8bac-440b-a360-eaf4212c8107

2013-10-07

Student theses

master thesis

(c) 2013 Dahlan, B.