2013.5.29 Towards Network-aware Service Composition in the Cloud
A. Klein, F. Ishikawa, S. Honiden. Towards network-aware service composition in the cloud[A]; proceedings of the Proceedings of the 21st international conference on World Wide Web[C], 2012. ACM: 959-968.
1. INTRODUCTION
1.1 Service Composition
抽象服务abstract task构成服务组合，每个抽象服务又映射多个具体服务concrete services。
工作流
1.2 QoS-aware Service Composition
在选择具体服务时，需要考虑功能和非功能需求functional and non-functionalrequirements。
组合服务的QoS是根据workflow patterns通过单一服务计算而得，找到满足约束和偏好的具体服务时一个NP-难问题。可以用整数规划和启发式算法求解。
1.3 Service Composition in the Cloud
云计算的出现，SaaS——软件即服务，意味着越来越多的web服务会充斥于整个世界。
1.3.1 Network-Awareness
首先，网络对整个服务组合QoS的影响随着服务分布式程度的提高而逐渐加大。
除此以外，现有的方法在服务本身的QoS和网络QoS上不加以区分。
基本的共识是服务的提供者需要在SLA中申明网络的延迟性，但这点很难做到，因为用户位置不同对延迟性有很大的影响。考虑地域不同，服务提供者如果提供所有用户中最大的反馈时间，用户可能会因此选择局部的服务提供商。如用户在Frankfurt、New York、Tokyo对相同服务有不同的体验。
1.3.2 Scalability可扩展性
随着服务数量的增加，现有方法的可扩展性就变得非常关键。因为对于每个抽象服务有更多功能等效的服务可供选择，这就使问题的复杂性呈指数提高。
某人会争论针对相同功能不同的提供者提供服务的数量不可能无限增长。通常情况下，一小部分的大提供商和相当部分的中提供商已经有能力饱和市场。最关键的是在传统的服务组合中，大多数提供商仅提供一份SLA。只有在某些情况下，少数的SLA会被执行。如服务提供商会为不同类别的用户提供不同等级（platinum, gold and silver）的QoS服务。
如上图所示，一个抽象服务T通过不同的接口I_1,...,I_T_i提供不同SLA的服务实例T_i，每个不同特性（CPU、内存等）的服务实例可能运行在一个物理机或虚拟机上，这些实例在不同的位置以为不同国家的人提供服务。为了区别不同的实例，我们需要对每个单一服务有更多的选择。如每个任务有50个选择，如果每个提供商提供50个实例，那一共有50*50=2500个选择。
1.4 Contributions
本文贡献
1）网络模型
2）网络感知QoS计算
3）网络感知选择算法
2. RELATED WORK
3. APPROACH
3.1 Network Model
网络模型包含两个部分：网络协作系统形成我们的网络感知方法的基础，局部敏感哈希模式允许我们找到接近于确定网络位置或网络路径的服务。
3.1.1 Network Coordinate System
在云环境下，我们面临处理a huge number服务N的挑战。我们采用现有的网络协作系统来计算两个网络位置的服务或用户的延迟。测量两两之间的link距离需要O(N^2)次测量。那每个服务都必须ping所有服务，这显然不现实。
因此，使用网络协作系统network coordinate (NC) systems来对任意两个网络位置之间的延迟做一个准确的评估；需要O(N)次测量，对已新的网络位置需要O(1)次度量。基于通用的NC系统，如Vivaldi（基于模型的欧几里德距离模型）。每个网络位置（服务和用户）被放在二维的空间中，如上图，两个位置的延迟简单理解为两个位置的欧几里德距离。这让我们的网络感知QoS计算能较精确地评估云环境下组合服务的QoS。
3.1.2 Locality-sensitive Hashing Scheme
为了提高网络感知选择算法的效率，仅能计算任意网络位置之间的延迟是不够的。此外，我们需要能够找到离特定网络位置/路径最近的服务，这样就可以有效搜索最低延迟的服务组合。为达到这功能，我们在通用NC系统上使用位置敏感哈希模式a simple locality-sensitive hashingscheme (LSH)。
维护一张二维覆盖网络，每个bucket里放一个服务。有以下两个操作：
1）Compute the Hull of a Location计算位置的边界外壳Hull，如fig5a)所示的浅灰色方块。给定一个位置 ，我们可以找到执行特定任务的服务，该任务为在需求位置周围的特定范围内最接近于外壳的位置。
2）Compute the Hull of a Network Path计算网络路径的边界外壳Hull，如fig5b)。
3.2 Network-aware QoS Computation
包含两个阶段：
1）Simulated Execution：有两种工作流表示方法：图模型、树模型，其中树模型从图模型转化而来。
2）QoS Aggregation：树模型通过层次方法进行聚合，聚合过程中考虑AND\OR\LOOP算子
3） Example
3.3 Network-aware Selection Algorithm
采用遗传算法genetic algorithm，计算时间为多项式。
3.3.1 Genetic Algorithm
编码
流程：First, an initial population isgenerated. Then, in every iteration, individuals are selected,changed either by mutation or crossover operations, and inserted into the new population for the next iteration. Thisprocedure is repeated until a convergence criteria is met,which checks if the fitness of the population has a reached asatisfactory level, or if the fitness does not improve anymore.
3.3.2 Initial Population
初始种群随机生成，为了提高随机性，加速进化，提高最终解的质量，采用Localizer启发式策略来生成1/4的初始种群。主要是寻找就近解。
3.3.3 Selection
选择概率，保证高适应度的选择概率高。
3.3.4 Elitism精英主义
保留top-k个个体。
3.3.5 Mutation突变
突变的目的是防止局部最优。
随机选择基因的一部分，即随机选择一个就近服务。
3.3.6 Crossover交叉
细节未看。
4. EVALUATION
4.1 Setup
随机生成100,000个单独位置，workflows的task从10—80，每个task有500—4000个候选服务（步进为500）
每个服务的QoS属性通过正态分布随机生成。
服务之间的延迟通过欧几里德距离计算
4.2 Algorithms对比算法：
1）Random：随机选择
2）Dijkstra：最短路径，但只能用于延迟Latency一个属性，其他QoS属性不适用
3）GA 100：种群数为100，在标准的QoS模型上，不考虑网络延迟，每个服务的运行时间=执行时间+最大延迟时间
4）GA* 100：*表示加入我们对网络延迟的预测，即欧几里德距离
5）GA* 50：
6）NetGA 100：section3中描述的方法
7）NetGA 50：
4.3 Optimality
这篇论文主要从latency上面做文章，提出了网络模型、网络感知QoS计算、网络感知选择算法。