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

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

引言

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

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

1 系统模型假设

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

云需要合适的资源管理模型使成员有效地共享资源。本文采用计算经济模型与用户交互的管理方式，向用户的任务提供服务质量保证。云环境中的QoS有一系列的规范，包括资源响应时间、可用性、安全性、吞吐量等^[6]。本文选择在费用(Cost)，期限(Deadline)和任务执行的可靠性(Reliability)这三维QoS约束下调用有限的资源来满足不同云用户的请求。调度者和用户需求被公式化为效用函数、和，分别代表用户选择QoS选择产生的效益，根据每一个效益函数提供定量计算QoS的数学方法。调度问题可以推广为多个不同长度的任务在多个不同资源上的调度问题。同时约定：

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

(2) 各种资源有不同的处理能力;

(3)一个资源在同一时刻只能处理一个任务;

(4)一个任务不能同时在两个资源上处理;

(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的任务列表，否则考虑下一个可用的新资源。同时将该资源从新资源列表中删除，加入旧资源列表，并将其