- -

On the nature and impact of self-similarity in real-time systems

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

On the nature and impact of self-similarity in real-time systems

Show simple item record

Files in this item

dc.contributor.author Enrique Hernández-Orallo es_ES
dc.contributor.author Vila Carbó, Juan Antonio es_ES
dc.date.accessioned 2014-05-16T14:01:13Z
dc.date.issued 2012-05
dc.identifier.issn 0922-6443
dc.identifier.uri http://hdl.handle.net/10251/37526
dc.description.abstract In real-time systems with highly variable task execution times simplistic task models are insufficient to accurately model and to analyze the system. Variability can be tackled using distributions rather than a single value, but the proper charac- terization depends on the degree of variability. Self-similarity is one of the deep- est kinds of variability. It characterizes the fact that a workload is not only highly variable, but it is also bursty on many time-scales. This paper identifies in which situations this source of indeterminism can appear in a real-time system: the com- bination of variability in task inter-arrival times and execution times. Although self- similarity is not a claim for all systems with variable execution times, it is not unusual in some applications with real-time requirements, like video processing, networking and gaming. The paper shows how to properly model and to analyze self-similar task sets and how improper modeling can mask deadline misses. The paper derives an analyti- cal expression for the dependence of the deadline miss ratio on the degree of self- similarity and proofs its negative impact on real-time systems performance through system¿s modeling and simulation. This study about the nature and impact of self- similarity on soft real-time systems can help to reduce its effects, to choose the proper scheduling policies, and to avoid its causes at system design time. es_ES
dc.description.sponsorship This work was developed under a grant from the European Union (FRESCOR-FP6/2005/IST/5-03402). en_EN
dc.format.extent 26 es_ES
dc.language Inglés es_ES
dc.publisher Springer Verlag (Germany) es_ES
dc.relation European Union [FRESCOR-FP6/2005/IST/5-03402] es_ES
dc.relation.ispartof Real-Time Systems es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Workload modeling es_ES
dc.subject Stochastic models es_ES
dc.subject Real-time scheduling es_ES
dc.subject Multimedia processing es_ES
dc.subject Self-similar processes es_ES
dc.subject.classification ARQUITECTURA Y TECNOLOGIA DE COMPUTADORES es_ES
dc.title On the nature and impact of self-similarity in real-time systems es_ES
dc.type Artículo es_ES
dc.embargo.lift 10000-01-01
dc.embargo.terms forever es_ES
dc.identifier.doi 10.1007/s11241-012-9146-0
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Informática de Sistemas y Computadores - Departament d'Informàtica de Sistemes i Computadors es_ES
dc.description.bibliographicCitation Enrique Hernández-Orallo; Vila Carbó, JA. (2012). On the nature and impact of self-similarity in real-time systems. Real-Time Systems. 48(3):294-319. doi:10.1007/s11241-012-9146-0 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion http://link.springer.com/article/10.1007/s11241-012-9146-0 es_ES
dc.description.upvformatpinicio 294 es_ES
dc.description.upvformatpfin 319 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 48 es_ES
dc.description.issue 3 es_ES
dc.relation.senia 234307
dc.relation.references Abdelzaher TF, Sharma V, Lu C (2004) A utilization bound for aperiodic tasks and priority driven scheduling. IEEE Trans Comput 53(3):334–350 es_ES
dc.relation.references Abeni L, Buttazzo G (1999) QoS guarantee using probabilistic deadlines. In: Proc of the Euromicro confererence on real-time systems es_ES
dc.relation.references Abeni L, Buttazzo G (2004) Resource reservation in dynamic real-time systems. Real-Time Syst 37(2):123–167 es_ES
dc.relation.references Anantharam V (1999) Scheduling strategies and long-range dependence. Queueing Syst 33(1–3):73–89 es_ES
dc.relation.references Beran J (1994) Statistics for long-memory processes. Chapman and Hall, London es_ES
dc.relation.references Beran J, Sherman R, Taqqu M, Willinger W (1995) Long-range dependence in variable-bit-rate video traffic. IEEE Trans Commun 43(2):1566–1579 es_ES
dc.relation.references Boxma O, Zwart B (2007) Tails in scheduling. SIGMETRICS Perform Eval Rev 34(4):13–20 es_ES
dc.relation.references Brichet F, Roberts J, Simonian A, Veitch D (1996) Heavy traffic analysis of a storage model with long range dependent on/off sources. Queueing Syst 23(1):197–215 es_ES
dc.relation.references Crovella M, Bestavros A (1997) Self-similarity in world wide web traffic: evidence and possible causes. IEEE/ACM Trans Netw 5(6):835–846 es_ES
dc.relation.references Dìaz J, Garcìa D, Kim K, Lee C, Bello LL, López J, Min LS, Mirabella O (2002) Stochastic analysis of periodic real-time systems. In: Proc of the 23rd IEEE real-time systems symposium, pp 289–300 es_ES
dc.relation.references Erramilli A, Narayan O, Willinger W (1996) Experimental queueing analysis with long-range dependent packet traffic. IEEE/ACM Trans Netw 4(2):209–223 es_ES
dc.relation.references Erramilli A, Roughan M, Veitch D, Willinger W (2002) Self-similar traffic and network dynamics. Proc IEEE 90(5):800–819 es_ES
dc.relation.references Gardner M (1999) Probabilistic analysis and scheduling of critical soft real-time systems. Phd thesis, University of Illinois, Urbana-Champaign es_ES
dc.relation.references Garrett MW, Willinger W (1994) Analysis, modeling and generation of self-similar vbr video traffic. In: ACM SIGCOMM es_ES
dc.relation.references Harchol-Balter M (2002) Task assignment with unknown duration. J ACM 49(2):260–288 es_ES
dc.relation.references Harchol-Balter M (2007) Foreword: Special issue on new perspective in scheduling. SIGMETRICS Perform Eval Rev 34(4):2–3 es_ES
dc.relation.references Harchol-Balter M, Downey AB (1997) Exploiting process lifetime distributions for dynamic load balancing. ACM Trans Comput Syst 15(3):253–285 es_ES
dc.relation.references Hernandez-Orallo E, Vila-Carbo J (2007) Network performance analysis based on histogram workload models. In: Proceedings of the 15th international symposium on modeling, analysis, and simulation of computer and telecommunication systems (MASCOTS), pp 331–336 es_ES
dc.relation.references Hernandez-Orallo E, Vila-Carbo J (2010) Analysis of self-similar workload on real-time systems. In: IEEE real-time and embedded technology and applications symposium (RTAS). IEEE Computer Society, Washington, pp 343–352 es_ES
dc.relation.references Hernández-Orallo E, Vila-Carbó J (2010) Network queue and loss analysis using histogram-based traffic models. Comput Commun 33(2):190–201 es_ES
dc.relation.references Hughes CJ, Kaul P, Adve SV, Jain R, Park C, Srinivasan J (2001) Variability in the execution of multimedia applications and implications for architecture. SIGARCH Comput Archit News 29(2):254–265 es_ES
dc.relation.references Leland W, Ott TJ (1986) Load-balancing heuristics and process behavior. SIGMETRICS Perform Eval Rev 14(1):54–69 es_ES
dc.relation.references Leland WE, Taqqu MS, Willinger W, Wilson DV (1994) On the self-similar nature of ethernet traffic (extended version). IEEE/ACM Trans Netw 2(1):1–15 es_ES
dc.relation.references Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61 es_ES
dc.relation.references Mandelbrot B (1965) Self-similar error clusters in communication systems and the concept of conditional stationarity. IEEE Trans Commun 13(1):71–90 es_ES
dc.relation.references Mandelbrot BB (1969) Long run linearity, locally Gaussian processes, h-spectra and infinite variances. Int Econ Rev 10:82–113 es_ES
dc.relation.references Norros I (1994) A storage model with self-similar input. Queueing Syst 16(3):387–396 es_ES
dc.relation.references Norros I (2000) Queueing behavior under fractional Brownian traffic. In: Park K, Willinger W (eds) Self-similar network traffic and performance evaluation. Willey, New York, Chap 4 es_ES
dc.relation.references Park K, Willinger W (2000) Self-similar network traffic: An overview. In: Park K, Willinger W (eds) Self-similar network traffic and performance evaluation. Willey, New York, Chap 1 es_ES
dc.relation.references Paxson V, Floyd S (1995) Wide area traffic: the failure of Poisson modeling. IEEE/ACM Trans Netw 3(3):226–244 es_ES
dc.relation.references Rolls DA, Michailidis G, Hernández-Campos F (2005) Queueing analysis of network traffic: methodology and visualization tools. Comput Netw 48(3):447–473 es_ES
dc.relation.references Rose O (1995) Statistical properties of mpeg video traffic and their impact on traffic modeling in atm systems. In: Conference on local computer networks es_ES
dc.relation.references Roy N, Hamm N, Madhukar M, Schmidt DC, Dowdy L (2009) The impact of variability on soft real-time system scheduling. In: RTCSA ’09: Proceedings of the 2009 15th IEEE international conference on embedded and real-time computing systems and applications. IEEE Computer Society, Washington, pp 527–532 es_ES
dc.relation.references Sha L, Abdelzaher T, Årzén KE, Cervin A, Baker T, Burns A, Buttazzo G, Caccamo M, Lehoczky J, Mok AK (2004) Real time scheduling theory: A historical perspective. Real-Time Syst 28(2):101–155 es_ES
dc.relation.references Taqqu MS, Willinger W, Sherman R (1997) Proof of a fundamental result in self-similar traffic modeling. SIGCOMM Comput Commun Rev 27(2):5–23 es_ES
dc.relation.references Tia T, Deng Z, Shankar M, Storch M, Sun J, Wu L, Liu J (1995) Probabilistic performance guarantee for real-time tasks with varying computation times. In: Proc of the real-time technology and applications symposium, pp 164–173 es_ES
dc.relation.references Vila-Carbó J, Hernández-Orallo E (2008) An analysis method for variable execution time tasks based on histograms. Real-Time Syst 38(1):1–37 es_ES
dc.relation.references Willinger W, Taqqu M, Erramilli A (1996) A bibliographical guide to self-similar traffic and performance modeling for modern high-speed networks. In: Stochastic networks: Theory and applications, pp 339–366 es_ES
dc.relation.references Willinger W, Taqqu MS, Sherman R, Wilson DV (1997) Self-similarity through high-variability: statistical analysis of ethernet lan traffic at the source level. IEEE/ACM Trans Netw 5(1):71–86 es_ES


This item appears in the following Collection(s)

Show simple item record