A genetic-based approach to web service composition in geo-distributed cloud environment

智慧网络 / 2022-10-24

A genetic-based approach to web service composition in geo-distributed cloud environment

https://www.sciencedirect.com/science/article/pii/S0045790614002419

Computers and Electrical Engineering 2015

Dandan Wang, Yang Yang, Zhenqiang Mi 北京科技大学

被引用量大，问题有一定相关性

摘要

​ 服务组合（Service Composition）中的一个重要研究问题是如何根据服务水平协议（Service Level Agreement，SLA）从一组功能等价的服务中选择最佳候选服务。

​ 文章中将服务的 QoS 以及云端网络环境同时纳入考量，提出了一个服务组合模型。

​ 该文章也提出了一种基于遗传算法（Genetic Algorithm）的网络服务组合方式，以最小化 SLA violations。

创新点

  1. We first specify a realistic QoS-based composition model that allows us to consider the distributed network environment.
    1. 在服务组合问题中考虑了网络 QoS
    2. 这个模型同样适合拥有多个 QoS criteria 的问题
    3. 提供了一个在服务组合中计算 QoS 的方法
  2. A heuristic composition algorithm based on genetic algorithm to maximize user experience and minimize SLA violation is proposed to solve the problem in this work.
    1. 传统图论方法的复杂度极大
  3. We use the notion of skyline to generate the initial population, which improve the solution quality and convergence speed.

定义

云服务

  • The cloud architecture includes three layers: software layer, platform layer and infrastructure layer.
  • QoS of web services refers to various nonfunctional characteristics such as response time, throughput, availability, and reliability.
  • In cloud environment, it is a challenge to search for an optimal and feasible composition path efficiently because the problem of service composition is an NP-complete problem.
  • Cloud providers derive their profits from the margin between the operational cost of infrastructure and the revenue generated from users. Therefore, cloud providers are interested in maximizing profit and ensuring QoS for users to enhance their reputation in the marketplace. They are looking into solutions that can minimize the SLA (Service Level Agreements) violation.

原子服务

  • Atomic service is an independent unit to solve a particular task in a service computing system. Atomic services are published to brokers by service providers in order to be discovered.
    • QoS of atomic services can be provided by providers, computed based on execution and monitored by the users, or collected via users’ feedback in terms of the characteristic of each QoS criterion.
  • A service set is a collection of atomic services with the same function but different QoS levels.
  • In SOA, a service level agreement (SLA) is a legal contract between service provider and user.
    • SLA 就是服务商与用户之间关于 QoS 的基本协定，或者说是 QoS 必须满足的基线

建模

  • 服务组合模型分为服务发现（Service Discovery:）和服务选择（Service Selection）两部分

    • 服务发现是 functional 的，要求服务集合里的原子服务得满足任务的功能性要求
    • 服务选择是 non-fuctional 的，QoS 描述的就是这种 non-functional 属性

  • 分布式服务组合的性能很大程度上取决于网络性能，网络延迟可以分为原子服务之间的延迟以及原子服务与用户之间的延迟两类

    • The delay between datacenters is measurable and predictable because that the number of datacenters for certain cloud provider is limited and stable.
    • The network delay between service and user can be obtained from the feedback of network and the information of execution monitoring.

  • 三种服务组合结构：sequential, parallel and conditional

    • 很明显，我们的模型属于 sequential structure

  • 优化目标与约束

    • the user experience can be optimized
    • the QoS requirements described in SLA can be satisfied

算法

  • There are many well-known heuristic search methods, such as Tabu Search, Simulated Annealing and Genetic Algorithm. 作者从中选择了进化算法

    • Genetic Algorithm is population-based, whereas Tabu Search and Simulated Annealing are individual-based.
    • The optimization of the parameters for Genetic Algorithm is simpler than other algorithms under our proposed model.

  • Fitness function

    f(CS)=∑i=1oαi×ζi(CS)ζi−(CS)=Sqi−−qi−(CS)Sqi−ζi+(CS)=qi+(CS)−Sqi+Sqi+f(C S)=\sum_{i=1}^{o} \alpha_{i} \times \zeta_{i}(C S) \\ \begin{aligned} \zeta_{i}^{-}(C S) &=\frac{S q_{i}^{-}-q_{i}^{-}(C S)}{S q_{i}^{-}} \\ \zeta_{i}^{+}(C S) &=\frac{q_{i}^{+}(C S)-S q_{i}^{+}}{S q_{i}^{+}} \end{aligned}

    • SqSq 是 QoS 的约束，qq 是 QoS 值，αi\alpha_i 是用户对第 ii 种 QoS 的偏好比（∑iαi=1\sum_i\alpha_i=1）

    • The fitness function must promote the increase of positive criteria and the decrease of negative criteria (two types of QoS criteria).

      • The increase of values for positive criteria is beneficial for users, such as availability and reputation.
      • The decrease of values for negative criteria is beneficial for users, such as time and price.
      • In the evolution process, the fitness function can help to maximize positive criteria and minimize negative criteria.

    • The fitness function needs to reflect users’ preference.

      • some users prefer service with high availability to short response time
      • weights are assigned to QoS criteria to represent users’ preference

  • Encoding

    • 基因组
      • genomes represent the possible choices available in the problem
      • 将一个服务组合编码为一个基因组
    • 基因
      • 将原子服务编码为基因组中的基因

  • Initial population

    • 使用 skyline 的概念初始化其中 1/5 的 population，其余的随机初始化
      • Skyline set is a subset of service set. Skyline set comprises the atomic services in a service set that are non-dominated.
      • 一个原子服务如果在某一个 QoS 指标上都没有人超过它，它就是 non-dominated 的
    • Brokers maintain a list of skyline set of each service set which can be updated when there are changes of atomic services.

  • Selection operator

    • 使用 roulette-wheel selection 策略，在大小为 NN 的 popularity 中选择第 kk 个 individual 的概率为 $ p_{k}=\frac{f_{k}}{\sum_{j=1}^{N} f_{j}} $
    • 有更高的概率选到好的基因，好的基因也更可能遗传下去

  • Crossover operator

    • 随机挑选亲代
    • 亲代被分割成两部分，后面部分进行交换

  • Mutation operator

    • 随机挑选基因组中的一个基因，然后用与它相关的服务组中的一个随机原子服务进行替换
    • 能够避免收敛到局部最优点

评价

  • 服务组合模型
    • 建模和我们的方法接近，有借鉴意义
      • 我们也是默认服务发现过程已经实现，主要在做服务组合
      • 但我们不是在 Scheduler 完成的整个服务组合，而是对 Sequential 的原子服务，上一级提供服务的实体自己选择下一级的实体，Scheduler 控制这一过程中的可选范围
    • 有必要使用这篇论文中的一些定义
      • 主要是原子服务相关内容
    • 我们同样可以使用基于 SLA 的约束，但优化目标不局限于本文中带用户倾向的 QoS
  • 进化算法
    • 算法本身对我们而言没有太大价值
    • 通过权重系数 α\alpha 在优化目标中描述用户倾向，通过归一化计算 ζ\zeta 将约束放入优化目标
      • 我们可以继承这种做法，但是 ff 应该只作为优化目标中的一个 multi objective 项，通过这个目标来满足约束、提升用户 QoS
        • 这部分关于 QoS 的考虑，能够满足我们选择 Provider 时对延迟的追求
        • 同时，这个 QoS 设计是多目标的，我们也可以设计一种关于 Depositary 和 Filestore 的 QoS，从而限制 Provider 的可选择存储节点范围
      • 优化目标的主体部分应该是选择节点的公平性
        • 对于存储资源，应该以剩余出口带宽量为目标
          • 基于历史经验，估计 Filestore 在未来一段时间内的长期出口带宽，并需要当前出口带宽满足 QoS 约束
          • 对于只会进行瞬时下载的 Depositary，则直接使用当前的出口带宽
        • 对于渲染资源，应该按照资源与用户之间的网络距离（几跳转发能到达用户）为目标，需要满足渲染能力的约束
    • 参考这篇论文，还可以引入关于各节点的 reputation 作为 QoS 的一部分，以实现对背书系统的考量
      • reputation 的设置与动态维护，需要 Scheduler 进行背书
    • 用户的偏好（preference）应该是一张表，按照不同的业务类型（fps、act、rpg）分配不一样的偏好
      • reputation 的比重应该是固定的，Provider 的 reputation 权重应该是其中最大的
      • SLA 应该是硬指标，其中的一部分由用户自己选择（帧率、分辨率），其他的由具体的游戏类型（或根据是哪个游戏）映射到一个预先配置的表中，然后找出对应的 QoS 基线

文章目录

最新评论

最新文章

一只学术咸鱼 _(:ᗤ」ㄥ)_