Lightweight Modeling of Complex State Dependencies in Stream Processing Systems

Anne Bouillard 1 Linh Phan 2 Samarjit Chakraborty 2
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Over the last few years, Real-Time Calculus has been used extensively to model and analyze embedded systems processing continuous data/event streams. Towards this, bounds on the arrival process of streams and bounds on the processing capacity of resources serve as inputs to the model, which are used to calculate end-to-end delays suffered by streams, maximum backlog, utilization of resources, etc. This “functional” model, although amenable to computationally inexpensive analysis methods, has limited modeling capability. In particular, “state-based” processing, e.g. blocking write – where the processing depends on the “state” or fill-level of the buffer – cannot be modeled in a straightforward manner. This has led to a number of recent proposals on using automata-theoretic models for stream processing systems (e.g. Event Count Automata [RTSS 2005]). Although such models offer better modeling flexibility, they suffer from the usual state-space explosion problem. In this paper we show that a number of complex state-dependencies can be modeled in a lightweight manner, using a feedback control technique. This avoids explicit state modeling, and hence the state-space explosion problem. Our proposed modeling and analysis therefore extend the original Real-Time Calculus-based functional modeling in a very useful way, and cover much larger problem domain compared to what was previously possible without explicit state-modeling. We illustrate its utility through two case studies and also compare our analysis results with those obtained from detailed system simulations (which are significantly more time consuming).
Type de document :
Communication dans un congrès
15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2009), Apr 2009, San Francisco, United States. 10 p., 2009
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00429776
Contributeur : Anne Bouillard <>
Soumis le : mercredi 4 novembre 2009 - 13:59:49
Dernière modification le : jeudi 11 janvier 2018 - 06:20:08
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:20:52

Fichier

rtas09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00429776, version 1

Collections

Citation

Anne Bouillard, Linh Phan, Samarjit Chakraborty. Lightweight Modeling of Complex State Dependencies in Stream Processing Systems. 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2009), Apr 2009, San Francisco, United States. 10 p., 2009. 〈inria-00429776〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

190