搜索

基于多维云用户驱动QOS网络资源调度算法

gecimao 发表于 2019-06-16 22:24 | 查看: | 回复:

  ::本文在云经济模型的基础上,提出一种受用户级QoS驱动的分组调度算法。该算法基于对云QoS的属性分析,对经济云现有的DBC调度算法进行了扩展和改进。在满足任务的截止期限和预算的范围内,根据任务是否具有高网络带宽进行分组。通过把基于用户专有的QoS的需求加入到常规分组调度算法中,从而形成了一个基于网络带宽的分组调度算法。仿真结果显示:在模拟的云环境下,本文算法拥有较高的吞吐量和任务完成率。

  摘要:本文在云经济模型的基础上,提出一种受用户级QoS驱动分组调度算法。该算法基于对云QoS的属性分析,对经济云现有的DBC调度算法进行了扩展和改进。在满足任务的截止期限和预算的范围内,根据任务是否具有高网络带宽进行分组。通过把基于用户专有的QoS的需求加入到常规分组调度算法中,从而形成了一个基于网络带宽的分组调度算法。仿真结果显示:在模拟的云环境下,本文算法拥有较高的吞吐量和任务完成率。

  目前大多数云计算环境下的调度和资源管理问题一般仍使用传统形式,即由调度构件如Glbous根据确定的花费函数来决定任务应在哪里执行,但这些花费函数一般都以系统为中心的,难以通过用户的QoS参数如存取价格、服务传送时间片等驱动。在经济管理模型下,不同的系统当然不会花费同样的价格来存取相同的资源。终端用户也不一定想要支付最高的价格来获得最有效的资源利用,而是有可能基于需求、价值、优先权和可供使用的预算协商一个特定的价格[1]。此外,QoS是一个综合指标,不同应用的侧重不同,在计算密集型任务当中,QoS往往反映资源的运算速度,而在一些数据密集型的任务当中,QoS较多地表示节点之间的带宽、节点数据的质量等指标[2]。在经济学方法中,调度决定不是静态地由单个调度实体来完成,而是由终端用户的要求直接驱动[2]。一个常规的经济模型,一般关注的是运行应用的软件和硬件花费,而经济模型主要对最终用户的服务收取费用[3]。在竞争的经济市场中,基于用户需求和可供使用资源的交易是主要驱动力。

  对此,本文提出了一种面向任务交易成本和截止期限的分组任务调度策略。该策略优先选取用户级具有高网络带宽要求的任务进行调度,根据交易价格和平均价格的比较将任务分成两组,在可用资源列表中对两组任务分别进行时间优化和花费优化调度。最后测试了本文算法的调度性能。

  在竞争的经济市场中,基于用户需求和可供使用资源的交易是主要驱动力。因此,我们关注的是单个用户在云中与其它用户以及云服务提供者和资源拥有者的竞争。

  云需要合适的资源管理模型使成员有效地共享资源。本文采用计算经济模型与用户交互的管理方式,向用户的任务提供服务质量保证。云环境中的QoS有一系列的规范,包括资源响应时间、可用性、安全性、吞吐量等。本文选择在费用(Cost),期限(Deadline)和任务执行的可靠性(Reliability)这三维QoS约束下调用有限的资源来满足不同云用户的请求。调度者和用户需求被公式化为效用函数

  ,分别代表用户选择QoS选择产生的效益,根据每一个效益函数提供定量计算QoS的数学方法。调度问题可以推广为多个不同长度的任务在多个不同资源上的调度问题。同时约定:

  (1)进行调度的一组任务是互相独立,即任务之间没有通信和数据依赖[6];

  (5)任务一旦运行,运行该任务的资源被独占,只能等到任务完成后,再执行别的任务。

  对资源的调用要遵从市场经济模式,当云中有N个任务和M个可用资源时,网络资源调度策略在N个任务和M个资源之间进行匹配,使得既可以满足用户的要求和云资源约束,又可以使完成任务目标代价最优或近似最优[7]。提出任务的客户端希望找到能够满足用户要求的资源使任务执行的时间最短而且价格最低[8]。提供资源的工作端希望自己的资源能够充分利用,尽量减少空闲资源的时间,提高资源的利用率,增加自己的经济效益[9]。

  假设某一时刻云用户向系统提交了N个任务,每个任务的长度为Li,用指令数来度量,单位为MI百万指令,截止期限Deadline以及可以支付的最大预算Budget值(由用户指定)如下表所示,任务按照长度从大到小的顺序进行排序。

  初始状态下云系统中存在的M个可用资源的处理速度以及各个资源的性能开销参数列表如下,其中Vi表示每个资源的处理速度,Ci表示资源R每百万条指令的执行开销(Cost/MI)。资源按照处理速度从大到小的顺序进行排序。新资源因为还未分配任务,所以它的任务列表为空;若某一资源的任务列表不为空,则称这个资源是旧的。将所有到达的任务分配给新资源,若此时没有新资源可用则将任务分配给旧资源。初始时刻,全部资源都是新的,把长度最大的任务T0分配给处理速度最快的资源R0,计算执行的时间和开销是否超出了用户可以承受的Deadline和Budget,如果未超过则将T0加入R0的任务列表,否则考虑下一个可用的新资源。同时将该资源从新资源列表中删除,加入旧资源列表,并将其标志为旧资源,反复进行此过程,直到全部的任务都被调度或调度失败。调度的目标是找到能够在期望的执行时间内完成工作任务、而且所付出的费用相对比较廉价的资源,即时间和费用是最优的[10]。

  在一个三维的QoS模型空间中对此调度问题进行研究。模型空间由运行费用(C),截止期限(D)和可靠性(R)构成。其中C代表花费Cost,执行云任务时的花费包括处理计算资源和网络(传输带宽)资源的花费;D代表截止期限Deadline:处理云任务的全部时间;R代表可靠性Reliability:完成任务的概率。

  (表示资源的处理时间),如果j的计算能力为Cj,则相应的资源分配约束条件为

  在经济模型下最大化任务代理获得的效用,使用拉格朗日数学方法求得多维QoS约束的网络资源调度问题的最优解:在时间期限内,最优化任务代理:

  在资源市场上,计算资源作为资源供应者,考虑到任务代理愿意付出的代价,试图最大化它们的收益

  由以上对QoS进行量化的效益函数表达式可知,完成时间和花费QoS是负QoS参数,其它属性的QoS参数是正QoS参数。所谓的负QoS参数是指QoS值越大,其效益函数值越小,正QoS参数是指QoS值越大,其效益函数值越大,见图1。

  再利用拉格朗日乘数法求解在多QoS约束条件下的最优解,构造以下的辅助函数:

  ,就可以得到最优化任务代理问题的最优解,表示任务代理在约束时间条件下为了最大化系统效益应该付出的价值;

  ,可以求得计算资源代理优化问题的最优解,表示计算资源代理作为资源供应者,为了最大化它的收入希望分配给任务代理的的单元个数。

  图 2、图3显示了本文算法与DBC算法在完成任务效率上的比较。依图2可知,满足要求的任务个数随着deadline的增加而增加,但DBC算法的deadline增加到2400以后,完成的任务个数保持在一个数值不再增加,这是因为完成的任务已经用完了用户提供的budget,增加deadline的值对任务的完成数没有影响,这符合计算经济网格中的交易原则;在期限固定的情况下,随着预算的增加,对于任务的完成情况,本文都比传统DBC优化算法有一些提高,说明本文算法提高了截止期限内的任务完成率(任务的可靠性)。由图3可知,满足要求的任务个数随着budget的增加而增加,但是本文算法的提升速度更快,这是由于本文算法采用拉格朗日计算方式,在Dealine固定的时候,能够更有效地提高资源调度效率,从而在一定截止时间内完成的任务数更多。

  本文对基于经济模型的云网络资源调度问题进行了详细的介绍,分析了使用经济原则和交易议价的优点,认为它能够更好地适应现代网格的发展。在对网格传统的调度算法进行研究的基础上,根据现代网格基于市场经济模型进行资源管理的特点,提出了一种基于多维云用户驱动QoS网络资源调度算法。通过合适的分组机制有效地降低了经济代价,具有一定的部署价值。

  [2]胡自林,徐云, 毛涛. 基于效益最优的云网络资源调度. 计算机工程与应用, 2014, 7: 69-70

  本文来源于中国科技核心期刊《电子产品世界》2016年第1期第41页,欢迎您写论文时引用,并注明出处。

本文链接:http://olivierlutaud.net/diaodusuanfa/573.html
随机为您推荐歌词
推荐文章

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部