×

The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures. (English) Zbl 1376.68015

Summary: We consider Web services defined by orchestrations in the Orc language and two natural quality of services measures, the number of outputs and a discrete version of the first response time. We analyse first those subfamilies of finite orchestrations in which the measures are well defined and consider their evaluation in both reliable and probabilistic unreliable environments. On those subfamilies in which the QoS measures are well defined, we consider a set of natural related problems and analyse its computational complexity. In general our results show a clear picture of the difficulty of computing the proposed QoS measures with respect to the expressiveness of the subfamilies of Orc. Only in few cases the problems are solvable in polynomial time pointing out the computational difficulty of evaluating QoS measures even in simplified models.

MSC:

68M11 Internet topics
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aws service health dashboard. http://status.aws.amazon.com
[2] Balcazar JL, Diaz J, Gabarro J (1995) Structural complexity I. EATCS series texts in theoretical computer science. Springer, Heidelberg · Zbl 0826.68048
[3] Cardoso J, Sheth AP, Miller JA, Arnold J, Kochut K (2004) Quality of service for workflows and web service processes. J Web Semant 1(3):281-308 · doi:10.1016/j.websem.2004.03.001
[4] Castro J, Gabarro J, Serna M, Stewart A (2015) The robustness of periodic orchestrations in uncertain evolving environments. In: Symbolic and quantitative approaches to reasoning with uncertainty—13th European conference, ECSQARU 2015, Compiegne, July 15-17 · Zbl 1465.68193
[5] Dong JS, Liu Y, Sun J, Zhang X (2014) Towards verification of computation orchestration. Form Asp Comput 26(4):729-759 · Zbl 1342.68209 · doi:10.1007/s00165-013-0280-9
[6] Fu Y, Vahdat A, Cherkasova L, Tang W (2002) Ete: passive end-to-end internet service performance monitoring. In: Proceedings of the general track of the annual conference on USENIX annual technical conference, ATEC ’02. USENIX Association, Berkeley, pp 115-130
[7] Gabarro J, Serna M, Stewart A (2014) Analysing web-orchestrations under stress using uncertainty profiles. Comput J 57(11):1591-1615 · doi:10.1093/comjnl/bxt063
[8] Gao H, Miao H, Zeng H (2013) Predictive web service monitoring using probabilistic model checking. Appl Math Inf Sci 7(1):139-148 · doi:10.12785/amis/071L20
[9] Gilly K, Quesada-Granja C, Alcaraz S, Juiz C, Puigjaner R (2009) A statistically customisable web benchmarking tool. Electron Notes Theor Comput Sci 232:89-99 · doi:10.1016/j.entcs.2009.02.052
[10] Google apps status dashboard. http://www.google.com/appsstatus
[11] Greifeneder J, Frey G (2005) Probabilistic delay time analysis in networked automation systems. In: Proceedings of 10th IEEE international conference on emerging technologies and factory automation, ETFA 2005. IEEE · Zbl 1298.68177
[12] Hoare, T.; Menzel, G.; Misra, J.; Broy, M. (ed.); Grünbauer, J. (ed.); Harel, D. (ed.); Hoare, T. (ed.), A tree semantics of an orchestration language, No. 195, 331-350 (2005), Dordrecht · doi:10.1007/1-4020-3532-2_11
[13] IPFW, Personal page at Purdue University Fort Wayne. http://users.ipfw.edu/jehle/courses/verbs/VERB.HTM
[14] Kitchin D, Cook WR, Misra J (2006) A language for task orchestration and its semantic properties. In: Baier C, Hermanns H (eds) CONCUR 2006—concurrency theory, 17th international conference, LNCS, vol 4137. Springer, pp 477-491 · Zbl 1151.68360
[15] Krushevskaja D, Sandler M (2013) Understanding latency variations of black box services. In: Proceedings of the 22nd international conference on World Wide Web, WWW ’13. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, pp 703-714
[16] McIver A, Morgan C (2005) Abstraction, refinement and proof for probabilistic systems. Springer, Berlin · Zbl 1069.68039
[17] Menasce DA (2002) Qos issues in web services. IEEE Internet Comput 6(6):72-75 · doi:10.1109/MIC.2002.1067740
[18] Menasce DA, Almeida V (2001) Capacity planning for web services: metrics, models, and methods, 1st edn. Prentice Hall PTR, Upper Saddle River
[19] Misra J, Cook W (2007) Computation orchestration: a basis for wide-area computing. Softw Syst Model 6(1):83-110 · doi:10.1007/s10270-006-0012-1
[20] Papadimitriou CH (1994) Computational complexity. Addison Wesley, Reading · Zbl 0833.68049
[21] Rosario S, Benveniste A, Jard C (2010) Flexible probabilistic QoS management of orchestrations. Int J Web Serv Res 7(2):21-42 · doi:10.4018/jwsr.2010040102
[22] Stackoverflow. http://stackoverflow.com · Zbl 1342.68209
[23] Stewart A, Gabarro J, Keenan A (2013) Reasoning about orchestrations of web services using partial correctness. Form Asp Comput 25(6):833-846 · Zbl 1298.68177 · doi:10.1007/s00165-011-0212-5
[24] Stewart A, Clint M, Harmer T, Kilpatrick P, Perrott R, Gabarro J (2008) Assessing the reliability and cost of web and grid orchestrations. In: Proceedings of the third international conference on availability, reliability and security, ARES 2008, March 4-7, Technical University of Catalonia, IEEE, Barcelona, pp 428-433
[25] Stross R \[(2011) 99.999\%99.999\]
[26] Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8(3):410-421 · Zbl 0419.68082 · doi:10.1137/0208032
[27] Vardoulakis D, Wand M (2008) A compositional trace semantics for orc. In: Lea D, Zavattaro G (eds) Coordination models and languages, 10th international conference, COORDINATION 2008, Oslo, LNCS, vol 5052. Springer, pp 331-346 · Zbl 1163.68303
[28] Wehrman I, Kitchin D, Cook W, Misra J (2008) A timed semantics of Orc. Theor Comput Sci 402(2-3):234-248 · Zbl 1147.68436 · doi:10.1016/j.tcs.2008.04.037
[29] Wheeler E (2011) Security risk management. Elsevier, Amsterdam
[30] Yahoo. http://yahoo.com · Zbl 1147.68436
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.