QoS management for real-time DataBases in embedded systems

ABSTRACT

Real-time database management systems (RT-DBMS) have the necessary characteristics for providing efficient support to develop applications in which both, data and transactions have temporal constraints. However, in the last decade, new applications were identified and are characterized by a large geographic distribution, high heterogeneity, lack of global control, partial failures and lack of safety. Besides, they need to manage large data volumes with real-time constraints. Scheduling algorithms should consider transactions with soft deadlines and the concurrency control protocols should allow conflicting transactions to execute in parallel. The last ones should be based in their requirements, which are specified through both quality of services functions and performance metrics. In this work, a method to model and develop applications that execute in open and unpredictable environments is proposed. Based on this model, it is possible to perform analysis and simulations of systems, to guide the decision making process and to identify solutions for improving it. For validating the model, a case study considering the application domain of sensors network is discussed.

REFERENCES

• 1: Ph. Bonnet, J. Gehrke, and P. Seshadri. Querying the Physical World. IEEE personal Communications. Special Issue Networking the Physical World, 7(5):10--15, Outubro 2000.
• 2: Ph. Bonnet and P. Seshadri. Device Database Systems. Proceedings of the International Conference on Data Engineering ICDE'99, Março 2000. San Diego, CA.
• 3: L. C. DiPippo. Semantic real-time object-based concurrency control. Tese de Doutorado, Department of Computer Science and Statistics, University of Rhode Island, 1995.
• 4: B. P. Douglass. Real-Time "UML": Developing Efficient Objects for Embedded Systems. Addison Wesley, Reading, Massachusets, 1998.
• 5: A. Girault, C. Lavarenne, M. Sighireanu, and Y. Sorel. Fault-Tolerant Static Scheduling for Real-Time Distributed Embedded Systems. 21st International Conference on Distributed Computing Systems(ICDCS), April 2001.
• 6: K. Jensen. Coloured petri nets-Basic Concepts, Analysis Methods and Practical Use, volume 2. Springer-Verlag, 1997.
• 7: K. Jensen. Second Workshop on Practical Use of Coloured Petri Nets and Design/CPN, disponivel em http://www.daimi.au.dk/CPnets/workshop99/. DAIMI, Aarhus, Denmark, 1999.
• 8: K. Jensen and et. al. "Design/CPN" 4.0. Meta Software Corporation and Department of Computer Science, University of Aarhus, Denmark, 1999. On-line version: http://www.daimi.aau.dk/designCPN/.
• 9: K. Kang, S. H. Son, and J. Stankovic. Managing Deadline Miss Ratio and Sensor Data Freshness in Real-Time Databases. IEEE Transactions on Knowledge and Data Engineering, 16(07), July 2004.
• 10: K. D. Kang, S. Son, J. Stankovic, and T. Abdelzaher. A QoS-Sensitive Approach for Timeliness and Freshness Guarantees in Real-Time Databases. EuroMicro Real-Time Systems Conference, Junho 2002.
• 11: Kyoung-Don Kang. qRTDB: QoS-Sensitive Real-Time Database. PhD thesis, Department of Computer Science, University of Virginia, Dezembro 2001.
• 12: Ben Kao, K. Y. Lam, Brad Adelberg, Reynold Cheng, and Tony Lee. Updates and view maintenance in soft real-time database systems. In Proceedings of the eighth international conference on Information and knowledge management, pages 300--307. ACM Press, 1999.
• 13: Kam-Yiu Lam, Tei-Wei Kuo, Ben Kao, Tony S. H. Lee, and Reynold Cheng. Evaluation of concurrency control strategies for mixed soft real-time database systems. Inf. Syst., 27(2):123--149, 2002.
• 14: X. Li, Y. Kim, R. Govindan, and W. Hong. Multi-dimensional range queries in sensor networks. Intel Research, IRB-TR-03-034, september 2004.
• 15: B. Lindstrom and L. Well. "Design/CPN 4.0", Performance Tool Manual. Department of Computer Science, University of Aarhus, Denmark, 1999. On-line version: http://www.daimi.aau.dk/designCPN/.
• 16: J. Lindstrom. Optimistic Concurrency Control Methods for Real-Time Database. PhD thesis, Department of Computer Science, University of Helsinki Finland, January 2003.
• 17: S. H. Son M. Amirijoo, J. Hansson. Specification and Management of QoS in Imprecise Real-Time Databases. International Database Engineering and Applications Symposium (IDEAS), July 2003.
• 18: S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. The Design of an Acquisitional Query Processor for Sensor Networks. To appear in the SIGMOD, Junho 2003.
• 19: Rajeswari Malladi and Dharma P. Agrawal. Current and future applications of mobile and wireless networks. Commun. ACM, 45(10):144--146, 2002.
• 20: Pedro Fernandes R. Neto, A. Perkusich, and Perkusich M. L. B. Modelagem e Análise de Qualidade de Serviços para Bancos de Dados em Tempo-Real. V Workshop de Tempo Real, 2003.
• 21: Pedro Fernandes R. Neto, A. Perkusich, and M. L. B. Perkusich. Formal Specification of the Epsilon Seriazibility Considering Quality of Service. IEEE Systems, Man and Cybernetics Conference, 2003.
• 22: D. Nyström, A. Tesanovic, M. Nolin, C. Norström, and J. Hansson. Pessimistic concurrency control and versioning to support database pointers in real-time databases. Proceedings of Euromicro conference on Real-Time Systems (ECRTS04), July 2004.
• 23: M. L. B. Perkusich. Um Método Baseado em Redes de Petri para a Modelagem de Bancos de Dados para Aplicações em Tempo-Real. Tese de doutorado, Curso de Doutorado em Engenharia Elétrica, CCT/UFPB, April 2000.
• 24: K. Ramamritham and C. Pu. A formal characterization of epsilon serializability. IEEE Transactions on Data and Knowledge Engineering, 6(7):997--1007, 1995.
• 25: K. Ramamrithman. Real-time databases. International Journal of Distributed and Parallel Databases, 1993.
• 26: I. Santoshkumar, G. Manimaran, and C. S. R. Murthy. Static scheduling of object-based real-time tasks with probabilistic conditional branches in distributed systems. 6th IEEE International Workshop on Parallel and Distributed Real-time Systems, March 30-April 3, 1998.
• 27: A. Silberschatz, H. F. Korth, and S. Sudarshan. Sistema de Banco de Dados. MAKRON Books, 1999.
• 28: John A. Stankovic, Krithi Ramamritham, and Marco Spuri. Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms. Kluwer Academic Publishers, 1998.
• 29: David Stewart and Michael Barr. Rate monotonic scheduling. Embedded Systems Programming, pages 79--80, March 2002.
• 30: Y. Yao and J. E. Gehrke. Query Processing for Sensor Networks. To appear in the First Biennial Conference on Innovative Data Systems Research (CIDR 2003), Janeiro 2003. Asilomar, California.
• 31: Haiwei Ye, B. Kerhervé, and G. v. Bochmann. QoS - Aware Distributed Query Processing. 3rd International Workshop on Query Processing and Multimedia Issues in Distributed Systems (QPMIDS), Setembro 1999.

INDEX TERMS

Keywords:
embedded systems, quality of service, real-time database