Time: 3.7 hours
J. Cardoso, A. Sheth, J. Miller, J. Arnold, and K. Kochut. Quality of service for workflows and web service processes. Web Semantics: Science, Services and Agents on the World Wide Web(if = 3.023), 1(3):281--308, April 2004. (gs:360)
这篇28页双栏的论文, 有点吓人, 不过内容不难, 看起来比较快. 作者Cardoso在写作这篇论文时的单位是葡萄牙马德拉大学, 现在不知道在哪里. 这篇04年的论文引用率挺高的, 之后讨论服务组合QoS的论文很多都会引用这一篇. 以下是论文笔记:
1. 这篇论文的背景是METEOR系统, 这是个工作流管理系统(WfMS), 被应用于一个生物基因资源项目(Fungal Genome Resource laboratory, University of georgia, USA), 需要支持QoS.
本文的内容主要分为两个部分.
第一部分介绍Workflow quality of service(time, cost, reliability)模型, 单个task的QoS属性估测, 以及Workflow QoS聚合方法.
第二部分介绍了对METEOR系统进行扩展来实现对QoS需求的支持(S7). (这部分这次不细看了)
2. (S4.1)作者引用文献说明流行的工作流分为三种:
ad hoc workflows, administrative workflows, production workflows
本文讨论的QoS model针对的是production workflow, 这种workflow更加"structured, predictable, and repetitive".
3. Workflow QoS model (S4)
(1) task time
T(t) = DT(t) + PT(t),
其中T是task response time, DT是delay time, PT是process time. Delay time可再分为queuing delay和setup delay.
(2) task cost
C(t) = EC(t) + RC(t)
其中C是cost, EC是enactment cost(管理工作流系统和监控工作流实例的花费), RC是realization cost(运行task的成本). RC可以再分成 direct labor cost, machine cost, direct material cost, and setup cost.
(3) task reliability
reliability block diagrams (RBD) 通常被用来对系统进行reliability analysis, 作者将RBD和workflow结构建立起映射关系, 从而可以用RBD的方法对工作流的reliability进行分析.
task failure可分为两类, 第一种是system failure, 第二种是process failure.
本文使用了discrete-time modeling方法来描述task reliability, 可以表示为:
R(t) = 1 – (system failure rate + process failure rate)
4. (S5) 这一章在讨论确定单个task的QoS属性和分支选择概率的办法
(1) 有些task的QoS属性确定比较复杂, 因为要依赖user input和system environment.
要根据input的值域的概率分布来估算.
(2) task runtime behavior specification有两类信息
basic class:
minimum value, average value, maximum value
distributional class:
the specification of a constant or of a distribution function
(3) re-computation of QoS task要根据designer specification和workflow system log来确定
(S5.1)最后一节介绍了规则.
5. (S6) 本章讨论的是Workflow QoS聚合的方法, 是本文的重点
作者开发了Stochastic workflow reduction(SWR)算法来计算Workflow的QoS, 借用了Graph reduction的技术.
这里共讨论了6种reduction rule, 针对time, cost, reliability这三种QoS属性
(1) sequential
聚合方法比较大众化. No comment.
(2) parall
No comment.
(3) conditional 
(4) loop
Loop可以分成两种:
(S6.1.3)这一部分的计算我没有看懂, 文中对一些符号缺乏必要的解释, 不解.
过段时间再看, 或者有谁能给我解释一下?
n个task同时执行, 当任意m个task完成时就算成功.
这个结构的reliability计算比较复杂, 详见(S6.1.4)的介绍.
(6) network
a network task represents a sub-workflow.
6. 这篇是早期讲述服务组合QoS聚合比较有名的一篇, 现在来看都是比较大众化的讨论, 不过在当时, 服务组合的QoS聚合还是比较新鲜的topic, 原先从事workflow研究工作的人最方便转到这个topic. Jaeger的工作与本文类似, 在写QoS aware service composition的论文时, 一般都可以也有必要引用他们的这些论文.