队列调度模型（共7篇）
队列调度模型 篇1
本文针对结合用户侧和电网侧多种因素来实现电动汽车充电最优方案的问题, 提出模仿计算机操作系统多级反馈队列来得到最优充电序列并在云平台实现的观点。在电动汽车智能充电行业起到对已有的研究补充和开辟新思路的作用。
当今社会对煤、石油、天然气等传统化石能源拥有巨大的需求, 但是越来越严重的环境问题和能源紧缺, 迫使公众亟待寻找一种可以节省能源并且环保可靠地交通工具, 而电动汽车的出现解决了这一问题。但是大规模电动汽车在同一时间段集中充电将带来新一轮的负荷增长, 尤其是电动汽车在高峰期充电将进一步加剧电网负荷峰谷差, 将会对配电网的运行造成严重影响, 包括电压跌落、线路或变压器负荷超载、加大损耗风险。另外, 电动汽车对电网造成的叠加负荷也同时表现出随机性和分散性, 使得调控电网变得更加复杂。因此, 为了保证电网运行的稳定性, 降低能源浪费以及达到效益最优化, 对于电动汽车的充电行为模式进行优化是有必要的。
确定最优充电模式的唯一途径是综合考虑充电设备 (包括充电站和充电桩) 和充电汽车两方面的数据信息, 并且对所有数据进行统一分析和处理。近年来, 根据侧重点的不同, 不同的研究机构和人员研究、比较了多种不同的充电模型。从研究层面上来划分的话, 可以分为以下几个方面:1) 单一电动汽车充电控制;2) 同一充电站多充电目标集中充电处理;3) 区域内多个站的电动汽车协调充电控制。文献针对有序充电的策略方法, 归纳为基于最优经济运行的充电模型、最优市场机制和商业运营模式、时空有序性3类方法;文献提出一种基于电网负荷的有序充电控制模型, 进行实时有序控制, 提高了电网的安全性;文献在考虑电动汽车的充电功率、充电时间以及变压器可用容量等约束条件的前提下, 提出基于多智能体协同控制的电动汽车充电优化策略;文献将电动汽车看成一个小型“集聚体”, 以有功网损最小为目标函数, 计及节点电压、线路潮流、配变容量、集中式充电功率的动态爬升约束以及充电能量平衡约束, 提出基于配电网安全运行的充电优化问题模型;文献提出了一种基于分布式控制的电动汽车有序充电控制模型, 并给出了分布式有序充电控制的优化计算方法;文献通过网格选取法, 考虑到配电变压器的供电容量, 从时间和功率两个维度来控制电动汽车的充电行为。但目前还未存在一种综合考虑电网和用户多种因素及优先级的充电方案, 更无有效的算法实现此类充电方案。
为了得到多种优化方案, 需要统一电网、充电设备和电动汽车三方面的数据信息, 并进行有效的分析处理。伴随着电动汽车保有量的提升, 为了满足充电需求, 充电站和充电桩必将会在电网内增加负荷接入点, 这样一来会造成各种异构化数据激增。云计算平台能够高效地采用集群化并行处理技术来解决海量数据的分析处理。实现区域电网内电动汽车优化充电需要综合考虑电网侧、用户侧多方面因素, 结合多种经典优化算法, 利用多维信息融合处理技术, 本文提出了一种基于多级反馈队列的电动汽车优化充电模型, 并阐述了在云计算平台对该模型的实现过程。
电动汽车多级反馈队列充电模型
模型需求目标分析
充电汽车的充电行为主要包含了三个行为主体:电网、充电汽车和充电代理商。三者之间的交互包含了能量和数据两种交互信息。要提出最优化的充电模型, 需要处理好三个关系:一是政府、企业和市场的关系;二是产品、基础设施和商业模式的关系;三是汽车的使用者、电力企业和充电代理商的关系。对于汽车的使用者, 重点是关注充电电价、充电耗时以及充电是否方便等需求;对于后两者, 重点是关注电网运行的安全性和稳定性、是否符合公平性原则以及电能是否充分利用。保证用户公平性是充电服务最重要的目标之一, 关系到电能有序利用的实施效果。公平性原则是为了满足电动汽车用户有突发性充电需求, 避免了电能不能补充的情况。而保证电网稳定运行和提升能源利用率, 又是对充电进行优化的最终目标。因此, 最优充电模型应该关注排队早、时间要求迫切、充电时间长的充电汽车首先充电。并且在充电过程中, 要实时地进行策略调整来满足各方的不同需求。这里综合考虑多方面关系, 根据各方需求, 建立区域电网内多级反馈队列优化充电模型。
基于多级反馈队列的优化充电模型建立
在计算机操作系统中, 有一种作业调度的应用场景:在同一时刻, 大量作业同时请求有限资源, 系统如何调度从而为作业有序地分配资源。参考作业调度的工作流程, 可以用类似的方案处理电动汽车充电的工作任务。在满足公平性原则的前提下, 将每一次的充电行为看做是一个调度任务, 相对应的电力能源就是资源。模型的最终目的是得到最优的任务执行序列, 来达到较高的电力能源利用率以及最小的电网负荷。
多级反馈队列进程调度算法为了保证公平性和较高的资源利用率, 采用了基于高优先级优先调度和时间轮转片轮转调度算法, 在处理过程中不断进行调整。在本文提出的电动汽车充电模型中, 根据排队时间长短、充电时间长短、充电时间紧迫性以及已经等待的时间等指标来定义任务的初始优先级。然后把充电的全部过程切成等长的时间, 不同的任务队列对应的单条时间长度可以不同。每个单独的时间充电完成以后, 调整优先级, 然后根据调整后的优先级进行任务调度。
图1为多级反馈队列优化充电模型整体架构图。
多级反馈队列优化充电模型调度算法分为以下步骤:
1) 在考虑了任务时长、已经排队时长以及用户紧迫度等因素以后, 对可以参与有序充电队列调度的充电任务计算对应的任务优先级。本文依据响应比算法, 以充电紧迫程度为优先级, 提出公式 (1) 作为优先级计算公式。
公式中, T表示完成充电所需的剩余时间, W表示已经排队时长, TC表示当前时间, TU表示用户设置的充电任务截止时间 (即取车时间) 。 (TU-TC) -T表示距离任务截止的时间和剩余任务所需要的时间之差, 用来表示当前用户充电任务紧迫程度。对于等待而未充电的用户, 其剩余充电所需时长T为固定值, 而W即等待时间逐渐增大, 因此响应比会增加;对于正在充电的用户来说, 其一开始等待的时长W已经为定值, 而剩余充电所需时长T则逐渐变小, 因此响应比会降低。对于公式分母部分, 无论等待充电还是正在充电的用户, 随着时间的推移, 距离设置的充电结束时间值越近, TU-TC越小, 代表任务越紧迫, 其响应比也就越高。而分母增加-T则是为了保证充电能够完整的进行, 因为若到了距离结束时限的时长无限接近于充电时长T还未开始充电, 则 (TU-TC) -T无限接近于0, 整个响应比会无限大, 使优先级达到最大。
2) 根据优先级, 设置多级队列。根据优先级确定各个任务执行的先后顺序, 同时依据优先级的大小分到若干不同等级的任务队列当中。不同等级的队列对应不同大小的时间片, 时间片长短和队列的优先级成反比。
3) 首先, 按照优先级从高到低的顺序选择队列中的充电任务开始执行, 每次时间片执行完毕, 需要再一次计算来确定各个任务的优先级, 并以此为依据, 再次分配充电任务到不同的队列中。
4) 只有当优先级最高的队列中的任务完成以后, 才处理优先级次一级的队列中的任务。
图2和图3分别为车辆接入流程和车辆充电流程。其中, 车辆接入流程为事件驱动型, 即车辆接入事件激活流程, 将充电任务存入充电优先队列;车辆充电流程为时间驱动型, 即时间片不断轮转, 每次时间片轮转结束时, 从优先级队列中取出任务进行充电, 并重新计算优先级队列。
以上提出的基于多级反馈队列实现的充电模型, 在保证电网稳定运行的基础上, 同时兼顾了每一个用户的实际充电需求, 达到了不同用户之间的公平。
基于云计算平台的多级反馈队列充电模型M-R算法实现
区域电网电动汽车多信息源融合问题分析
实现多级反馈队列充电模型需要考虑到以下几个方面:充电汽车、充电用户个人、充电站以及电网负荷等多方面的数据信息。在处理充电任务时, 需要综合分析多方数据, 不可避免的会遇到以下问题:
1) 综合分析多方数据时遇到的异构数据问题。
2) 电动汽车和充电设备 (包括充电站和充电桩) 分散性较强, 并会产生海量数据, 这些数据的存储问题需要解决。
3) 实现模型计算时需要考虑到多种因素, 最终得到最优方案, 这导致分析计算复杂, 计算量巨大。
4) 充电方案的生成需要具有时效性, 充电用户提交的充电需求应该迅速得到反馈。
综上所述, 在处理电动汽车充电任务时所遇到的问题呈现出数据量大, 处理时效性强等特点。想要解决以上问题, 需要使用云平台实现对大数据的处理。Hadoop是一个能够对大量数据进行分布式处理的软件平台, 实现了Map Reduce编程模型和HDFS分布式存储架构。对于电动汽车充电任务而言, Map Reduce模型实现了海量数据计算的并行化处理, HDFS存储结构解决了充电任务过程中需要存储的多方信息分散化的问题, 并保证了数据的统一管理。
基于Hadoop的多级反馈队列优化充电模型系统架构和平台搭建
基于Hadoop的多级反馈队列优化充电模型系统架构如图4所示。
在实现模型系统时, 按照逻辑层次的划分, 主要分为以下几个部分:
1) 物理层:其中包括实际的计算机服务器、虚拟机集群、计算机通信网络共同组成的服务器集群。
2) 数据储存和基础计算层:是实现Hadoop云计算平台的关键部分。通过和物理层的数据联系, 搭建了云计算平台最主要的三个部分:HDFS、HBase、Map Reduce。
3) 高级计算层:是更高级业务计算的处理部分, 已经存储到数据储存层的数据通过数据总线提交到这一层, 同时通过基础计算层提供的接口来实现复杂的计算模型。
4) 业务交互层:实现平台业务对用户的可视化展示并提供用户操作服务, 交互手段包括Web应用和手机App。
5) 调度控制层:实现了平台各个模块之间的控制管理, 可以提供平台业务功能模块控制、平台服务器间工作负荷调整以及日志管理等功能。
6) 消息数据总线:为平台不同模块之间的数据和信息交互提供了通道, 对平台各个模块进行了解耦合, 为平台提供了良好的可扩展性。
平台软硬件环境配置如表1所示。
在集群上搭建Hadoop-1.1.2内核的云计算环境, 其他组件版本为JDK-1.7.0_67, HBase-0.94.11。
基于HBase的分布式存储结构
基于多级反馈队列的充电模型采用非关系型数据库HBase, 因为HBase可以实现对充电任务中海量数据的存储并且提供对这些超大数据的快速索引。另外, HBase对Hadoop也有很好的支持。根据HBase具有的延展特性和非关系特性, 在设计存储数据库的时候, 主要创建了两个层次的数据表:第一, 包含了多种电网侧基础数据 (包括充电设备信息、电网负荷信息等) 的基础数据表;第二, 记录了从用户创建充电任务开始与之相关的需求和操作信息的充电任务表。
在HBase数据库中, 表的结构是由Row Key、列族、时间戳和Cell组成的。表2和表3分别为两张表的基础结构, 由于空间关系, 未列出具体列键信息。
基于Map Reduce的模型并行化算法实现
多级反馈队列充电模型的M-R算法按照Map Reduce机制分为Map阶段和Reduce阶段, 依据框架接口设计Map函数和Reduce函数。模型中各个充电任务的优先级是由Map函数计算得来的, 而通过比较优先级得出多级反馈队列由Reduce函数完成。这个算法包含一个二次排序过程, 将各个充电任务按照优先级进行排序, 使传入Reduce的是已排好序的任务, 从而提升效率。模型的实现过程如表4、5、6所示。
总结与展望
本文主要介绍了一种基于反馈队列调度的电动汽车充电模型及其云实现, 提出了一种电动汽车优化充电方案, 并利用M-R框架实现了方案的并行化计算。解决了大规模电动汽车接入电网导致的一系列电气问题和相关大数据分析问题, 对于智能电网中其他优化计算问题也具有一定参考价值。
随着电动汽车的普及和发展, 电动汽车作为电网负荷给电网带来的运行压力会越来越明显, 分析用户充电行为、优化用户充电策略能够主动为电网侧降低运行风险、保障电网安全。在智能电网与车联网等多方信息数据融合进一步发展的未来, 结合了能源互联网概念的电动汽车充电策略应当会有更深层次的发展。
摘要：充电汽车的普及和推广, 使人们在日常出行方面减少了化石燃料的使用, 从一定程度上解决了能源短缺和大气污染的问题, 但同时也造成了大规模充电行为对电网产生的巨大冲击, 影响了电网的稳定运行。文章借鉴计算机操作系统任务调度算法, 提出一种考虑到电网侧负荷以及充电公平性的多级反馈队列优化充电模型。电动汽车在关注的电网中按照以上提出的充电方案来进行充电, 既没有违背公平原则, 又实现了最优化充电, 同时保证电网安全稳定运行, 降低了资源浪费。电动汽车充电过程中涉及到了多方面的异构化信息, 其中包括车联网、智能电网、充电设备网络和额外的有关信息。而以上模型的实现需要把多方面的数据信息加以融合, 并且要解决海量数据带来的大数据处理问题。本文提出的电动汽车充电模型利用Hadoop云计算平台来解决大数据集的并行化计算问题, 使用HDFS分布式文件系统和HBase非关系型数据库解决海量数据的存储问题。
路由器队列调度机制研究 篇2
关键词：视频点播,实时业务,队列调度,区分服务
1 常见路由器队列调度机制
(1) 先进先出队列FIFO调度算法
(2) 优先级队列PQ调度算法
(3) 加权公平队列WFQ调度算法
(4) 差值加权轮训队列DWRR调度算法
2 队列调度算法的性能指标
队列调度算法性能的好坏主要涉及到时延性能、公平性、复杂性这三个方面。
时延性能:队列调度算法应为不同的业务流提供端到端的时延保证, 而且只与此业务流的某些参数 (如带宽需求等) 有关, 而与其他的业务流无关。Stiliadis和Varma首先提出了一种分析网络中不同队列调度算法带来的端到端时延的模型;时延速率调度器 (LRS:Latency2Rate Server) 。Francini随后又提出了另一种分析端到端时延的模型:速率分隔 (RST:Rate2Spaced2Timestamp Scheduler) , 此模型的限制条件比LRS要少且在定长分组环境下应用时更加有效。
公平性:可用的链路带宽必须以公平的方式分配给共享此链路的各业务流:此外队列调度算法必须能够隔离不同的业务流, 让不同的流只享用自己可以享用的带宽, 这样即使存在恶意或高突发性业务, 它也不致影响到其他的正常业务流。关于算法公平的定义有:服务公平指数 (SFI:Service Fairness Index) 和最坏公平指数 (WFI:Worst2case Fairness Index) 两种。
复杂性和可扩展性:调度算法实现起来应该比较简单.在高速网络中, 传输一个分组的时间很小, 所以调度算法必须在短时间里完成对分组的调度, 这就要求调度算法尽量简单, 易于实现。另外当业务流数量增加和链路速率变化范围较大时, 调度算法仍应有效工作;这要求调度算法应该具有良好的可扩展性。
3 现有队列调度算法性能比较
3.1 基于轮询的调度算法
传统的轮循 (RR:Round Robin) 算法对不同队列 (业务流) 进行无区别的循环调度服务.这样, 如果不同的队列具有不同的分组长度, 则分组长度大的队列可能会比分组长度小的队列接受更多的服务, 使队列之间产生不公平的现象;而且, 这种算法不能对业务提供时延保证.后来为了改进RR算法, 出现了一些改进型的算法。如加权轮询 (WRR Weighted Round Robin) , 差额轮询 (DRR Deficit Round Robin) , 紧急轮询 (URR Urgencybased Round Robin) 。
3.2 加权公平队列WFQ调度算法
WFQ调度机制是由Demers等人提出, 又由Parekh等人实现基于报文的PGPS (packet by packet generalized processor sharing) 的排队算法。
WFQ调度机制主要分为基于流的WFQ和基于类的WFQ (CBWFQ) 2种。它们的主要区别在于:前者的队列数在理论上没有限制, 但队列数目太多会增大调度的复杂度, 而后者最多为64个队列。WFQ算法能到达很好的公平性和时延保证, 但是系统其系统需时间函数计算复杂度为O (N) (N为总的队列数) , 且具有较大的WFI, 使得输出的突发度增加。它虽然很好的解决了RR机制的不公平性, 但是包含了GPS调度机制的局限性, 它调度的结果会带来带宽保证和时延保证的耦合性 (即低带宽保证总以为着不严格的时延保证) , 这个特性使得WFQ不适合调度某些类型的业务, 这类业务的特点是带宽需求不大, 但是有着极严格的时延要求, 如语音等实时业务。
3.3 基于时延的调度算法
基于轮询和WFQ的调度算法可以看成是基于速率的调度算法, 这种算法通常为每个队列提供一定的速率保证来达到提供时延保证的目的。而基于时延的调度算法则是以 (为各队列) 直接提供时延保证为目的, 这类算法的代表是最早期限优先 (EDF, Earliest Deadline First) 。
4 基于区分服务的调度算法
区分业务 (Diffserv Differentiated Service) 体系结构正成为解决因特网上服务质量的一种有效的办法, 能支持Diff Serv技术的一个子网被称为Diff Serv域, 它由一些边缘路由器和域内路由器组成, 边缘路由器执行较为复杂的业务流分类、业务量调节及队列管理和调度的功能, 而域内路由器则执行较为简单的队列管理和调度的功能。之前介绍的队列调度都没有边缘交换节点和域内交换节点。都是基于每个业务流的调度算法, 他们需要交换节点维护每个业务流的一些状态信息, 尽管这样可以达到很好的调度性能, 但同时带来了不易扩展和不强壮的缺点。
基于这种考虑, Stocia提出了两种新的调度算法:CSFQ (Core Stateless Fair Queueing) 和CJVC (Core Jitter Virtual Clock) , 其核心在于对交换节点进行了“边界交换节点”和“域内交换节点”的区分, 从而不需要每个交换节点都维护所有业务流的状态信息。
5 结论
基于多业务的队列调度算法研究 篇3
首先,可被用于使用户平等地共享链路的可用带宽或实现分级的链路共享;其次用以隔离恶意业务流,为正常业务流提供良好的服务。
根据不同的服务规则,队列调度算法可以分为先来先服务、轮循调度等。根据调度算法的调度目标,又可分为基于速率的和基于延时的这两类。根据调度算法的工作状态,又可以分为持续工作算法和非持续工作算法。
1 典型的队列调度算法
1.1 先来先服务调度算法
先来先服务[3,4](FCFS)的调度算法是目前路由器上最常用的队列调度算法,它的基本思想是根据数据包到达的先后来提供服务,到达早的数据包先得到服务,后达到的数据包要在先到达的数据包服务完成之后才能得到服务。这样那些实时性要求比较高的分组就不能及时地得到服务,不能提供很好的实时性服务,不能对网络业务提供延时保证。
FCFS的优点是:
(1)队列管理简单,调度实现方便;
(2)这种排队方式下,在接收端不需要对分组进行重排序,并且最大时延可以通过最大队列深度决定。只要保证较短的队列长度,就可以获得较小的时延。
缺点是后达到的数据包要在先到达的数据包服务完成之后才能得到服务。这样那些实时性要求较高的分组,不能及时的得到服务,实时性、延时差。
1.2 基于轮询的调度算法
传统的轮循调度算法RR[4,5,6],对不同的队列业务流进行无区别的循环调度服务。这样,如果不同的队列具有不同的分组长度,则分组长度大的队列可能会比分组长度小的队列接受更多的服务,使队列之间产生不公平的现象,而且这种算法不能对业务提供时延保证。为了改进算法的时延特性和其在变长分组环境中的不公平性,出现了一些改进型的算法,如加权轮循、均匀轮询等,这些算法力图在保持RR算法实现简单性的同时,从不同的方面改进算法的时延特性及其在变长分组环境下的不公平性。
1.3 加权循环队列调度算法
加权循环调度[7,8,9](Weighted Round Robin,WRR)支持不同的带宽需求,可以为不同的队列分配不同比例的输出带宽。
在 WRR 算法中,分组首先被赋予不同的权值,然后被分配到与之相应的队列,对每一个队列采用轮询服务,因此在一个轮询周期中每一个队列至少有一个分组被传送,所以避免了绝对的优先级排队策略中低优先级队列可能出现的队列“饥饿”现象。WRR 算法可以通过为那些对延迟要求高的数据流分配较大的权值,使其占有较多的输出带宽,从而减小延迟,这样可以为对实时要求高的应用提供良好的QoS[10,11]保证。但是WRR算法存在着不足,其中最主要的不足在于它分配的带宽的权值是固定的,不能很好地适应网络的变化。
2 改进的自适应的队列调度算法
2.1 算法思想
针对WRR算法权值是固定的,不能很好地适应网络的变化情况,对其进行了改进,在WRR基础上提出一种自适应的调度算法(MWRR),该算法根据各队列的延迟时间动态调整队列的调度次序,能自适应地根据网络的业务情况,调整各个队列的调度顺序。MWRR算法能够降低实时多媒体业务端对端时延和传输时延抖动,为实时多媒体业务提供更好的QoS保证。
MWRR调度算法主要思想:首先为每一个队列分配一个权值,再根据队列的初始权值进行带宽分配,最后根据各个队列的调节因子动态的调整各个队列的权值。这样,MWRR调度算法可根据网络变化情况,决定带宽的分配,可以自适应网络的变化,对网络的QoS提供保证。
2.2 算法描述
设Wi为各个数据流的初始权值(Wi<1),B表示网路带宽,ti为数据流i中的数据包在路由器中排队时的延迟时间,Ti为数据流i中数据包在整个网络中的延迟时间,β为调节因子。ti和Ti需要为每个队列增加一个计时器来进行实时的记录延迟时间。
Wi=BWiβ
其中,
这样,带宽的分配由调节因子动态地在充分考虑业务的实时性要求的同时,综合考虑网络的整体性能来动态地调整各个业务得到的带宽服务,从而为各业务提供整体的良好服务质量。
2.3 算法仿真
为了验证MWRR调度算法的优越性,进行简单的网络仿真[12,13]。仿真拓扑图,如图4 所示,在路由器3调度算法分别使用WRR和MWRR,其余的路由器都使用WRR,数据流的初始权值分别为1/2,3/8,1/8。
由仿真结果可以看出,MWRR算法明显提高了各数据流的吞吐量。
3 结束语
队列调度是实现网络控制的关键技术。一个能用于控制的调度算法,应该能对每一数据流提供一定的速率或延时上的保证,并保证算法的公平性。在IP网中提供QoS 保证,一个基本的目的就是能为各业务流提供区分服务和公平性保证,而队列调度机制正是实现这一目的的基本技术。队列调度算法不仅是保证服务质量的重要手段,也是网络本身参与拥塞控制的方式之一。
网络队列调度算法的NS仿真 篇4
随着Internet的迅猛发展,多媒体技术和电子商务应用日益广泛,网络拥塞的越来越严重,传输效率变得低下,就需要好的调度算法来解决。如何设计好的调度算法来预防和避免网络拥塞是目前一个研究的热门问题。
拥塞避免的关键就是提前预知发生拥塞的地方,而路由器是这个分组转发的中间枢纽,在路由器上选择合适的队列算法尤为重要。队列调度机制对数据包在网络中的传输具有很大影响,队列的调度算法对传输延迟、丢失率等性能指标也有着直接的影响。本文对采用不同队列调度机制的网络分别进行了NS2模拟,并对他们在拥塞窗口、吞吐量、平均队列和丢包率进行比较,得出模拟结果对比图,为进一步改善网络拥塞的研究提供参考。
1 队列调度机制
随着Internet的迅速发展,其网络规模越来越庞大,结构日趋复杂,仅仅依靠端到端的拥塞控制是不够的,网络本身也必须参与资源的控制和管理,在网络发生拥塞时,网络节点必须丢弃一些分组,这个问题的解决首先必须实施有效的队列管理机制。队列调度算法运行在网络节点中发生冲突需排队等待调度之处,它按照一定的服务规则对交换节点的不同输入业务流分别进行调度和服务,使所有的输入业务流能按预定的方式共享交换节点的输出链路带宽。常见的队列调度算法主要有以下几种:
1.1 被动队列管理机制的Droptail算法
Droptail是先到先服务(First Come First Served)的,FIFO队列实现的FCFS是Internet使用最多的一种方式,它的最大优点在于实施简单。FIFO本质上是一种“去尾”(Drop-tail)的算法,不需要选择丢弃的分组,只是在系统中没有空闲缓冲资源时丢弃到达的分组。虽然这种算法已经在Internet上成功工作了许多年,但它有三个严重的缺陷:1)持续的满队列状态;2)业务流对缓存的死锁;3)业务流的全局同步。
1.2 主动队列管理机制
1.2.1 RED算法
随机早期检测算法RED (Random Early Detection)是由Sally Floyd和Van Jacobson提出的,最常用于路由器的拥塞避免控制的。主要功能是为分组选择合适的路径。RED算法的基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞,一旦发现接近拥塞,就随机地选择连接来通知拥塞,使它们在队列溢出导致丢弃分组之前减少发送窗口,降低数据发送速度,从而缓解网络拥塞。
RED算法可以分成两部分,1)计算平均队列长度,用来反映拥塞状况。2)计算包被标记或丢弃的概率。RED算法通过定时的读取路由器缓冲区的数据包队列的长度,利用指数加权移动平均算法(EWMA)计算出数据包的平均队列长度。当拥塞发生时,RED丢弃每个连接分组的概率与该连接占用的带宽成比例,它监视每个输出队列的平均队列长度,随机选择分组丢弃。虽然RED通过随机早期检测和丢包,从而有效地在TCP流之间分配带宽,但混合TCP和非TCP数据流时,RED不能有效地保护TCP流,没有拥塞控制或采用比TCP更贪婪的非TCP流将比TCP流攫取更多的网络带宽,这种不公平性的主要原因是在拥塞发生时非TCP流不降低发送速率或降低的程度比TCP少,而RED对所有的数据流都采用同样的丢包比率。RED算法相比DropTail的好处是:首先,队列缓冲总是预留了一定的缓冲空间,这样可以更好地处理突发性。其次,保持较短的队列长度,可以更好地支持实时应用。最后,RED算法可以最少化全局同步的发生。
1.2.2 REM算法
随机指数标记REM (Random Exponential Marking)是在最优化流控模型的基础上,利用网络流量优化理论中的“价格”的概念来探测和控制网络的拥塞状态。虽然是把流量控制运用于网络拥塞,但性能目前不太理想。在该算法中,源端发送速率和路由器拥塞度量相互影响,远端根据反馈回来的精确拥塞度量(价格)调整其发送速率,而各源端发送速率的大小又会反过来影响拥塞度量,从而构成一个闭环拥塞控制系统。
REM算法属于主动队列管理算法之一,它是一种基于流检测的拥塞控制算法,并非通过延时或丢包等指示,而是通过由分布在链路上的包标记信息计算得到的带宽价格,检测拥塞,进而发送端相应的调整其发送速率。
1.3 链路调度机制SFQ算法
开始时间公平排队算法SFQ(Staring-time Fairness Queueing)的基本思想是采用虚拟时钟的方法进行分组的选择。为每一个队列维护一个虚拟开始和一个虚拟结束时间标签,当队列中有分组发送完毕,或者空队列中有分组到达时分别计算这两个时间标签。每次调度时,系统根据模拟时间标签的大小选择一个分组。SFQ算法按照包的虚拟开始时间标签递增的顺序调度包,并对系统的虚拟时间的计算可以调整。数据包的虚拟开始时间标签等于该数据包到达时刻的虚拟时钟和流中上一个包的虚拟结束时间标签的最大值。
1.4 算法复杂度低的DRR算法
差额轮循DRR (Deficit Round Robin)算法将有数据包等待发送的队列序号放入一个链表中,每次访问链表头上的队列时,先将队列的令牌数加上一个预先分配的值,然后服务该队列。每次服务前判断队头上的数据包长度是否大于队列令牌数,如果队列头上的数据包长度小于该队列剩余的令牌数,服务后队列令牌数减去发送的数据包长度;否则将其从链表中取出并插入链表尾部,然后访问链表中的下一个队列,当队列为空时将其移出链表。DRR算法需要在发送数据包之前知道数据包长度来决定是否可以发送,这样会增加实现的开销,同时,DRR持续对满足条件的链表头上的队列服务,直到队列用尽它的令牌。缺点是时延大,但可以支持变长的数据包的调度,算法复杂度低。
2 各种算法仿真及性能分析
下面的仿真是在NS环境下,网络拓扑为图1所示,0节点为发端,2节点和3节点为中间路由器,4节点为接收端,2节点到3节点的链路为瓶颈链路带宽0.3mbps,传播延时100ms,采用不同的队列算法,队列大小20;0到2节点的链路2Mbps,传播延迟10ms,队列为50;3节点和4节点链路为0.5Mbps,传播延时30ms,队列为50;0是ftp发端,4是接收端,采用的是TCP Reno拥塞控制算法,分组大小为552Bytes,window大小为8000;另外一条是1节点发,5节点收,发送的是固定速率的CBR;模拟时间为50s。
TCP拥塞窗口的大小反映了TCP发端对发送数据流量的控制,间接的反映了链路阻塞情况的。从图2的TCP拥塞窗口的大小来分析,RED算法最好,因为窗口震荡小,恢复时间短,SFQ次之,DRR最差,而Droptail与REM基本一致。
队列长度是在网络瓶颈路由器中等待转发的包的数目,是测量网络的一个重要性能指标。图3是各种算法仿真所得的路由平均队列长度变化图。可以看出,平均队列包的变化幅度基本是算法RED最好,队列大小平均保持在10左右,队列波动远小于其他调度机制。依次是SFQ、REM、Droptail,最差的是DRR算法。
平均丢包率是指在某时刻被丢弃包的总数与发送数据包的总数的百分比。丢包越少,网络的利用率就越大,网络的服务质量就越高;丢包率太大会浪费网络资源,导致网络的利用率低,有时会加深网络拥塞的程度。从图3也可以看出,平均队列增大,丢包数也增大。
吞吐量能反映网络算法的性能。从图4可知,吞吐量的大小是DRR最大,刚开始是吞吐量Droptail要大一点,次之是RED、REM、SFQ最差,因为RED预先做好了丢包的准备,所以吞吐量比Droptail要小一些。
3 结论
NS仿真表明RED算法在拥塞窗口、平均队列长度和丢包率上都具有很好的性能,在吞吐量上性能略差。同时还存在,平均队列长度对实际队列变化反映比较慢;丢包相对也多;主要是对控制参数敏感,难以优化参数;链路的公平性问题。针对公平性问题,近来出现很多改进的算法,如RED-PD算法。那么如何改进RED算法的这些不足,更好的利用网络资源是未来研究的热点。
摘要：为了提高网络资源和解决网络拥塞,网络的调度机制的选择至关重要。采用网络仿真工具NS2的方法,对Droptail、RED、REM、SFQ和DRR五种队列调度机制进行模拟,得到它们的拥塞窗口、平均队列长度、丢包率、吞吐量性能对比图。结果表明:相对于其他队列调度机制,RED算法在拥塞窗口、平均队列长度、丢包率上性能更优,但在吞吐量上略差。
关键词：队列调度,拥塞机制,NS2,模拟
参考文献
[1]杨吉文,张卫东.基于Ns2的主动队列管理仿真研究[J].计算机工程.2006,32(17):189-191.
[2]吴忠,范君晖.TCP流拥塞窗口的非线性动力学行为仿真分析[J].计算机仿真.2005,2 2(9):280-284.
[3]曾晓红,漆丽娟,谢树云.一种改进的TCP拥塞控制算法的公平性研究[J].计算机仿真.2010,27(4):120-123.
[4]王红旗.TCP/IP拥塞控制的典型算法分析[J].四川理工学院学报(自然科学版).2008,21(6):42-46.
[5]陈琳,双学芹.TCP网络拥塞控制算法比较研究[J].长江大学学报(自然科学版).2010,7(1):60-64.
[6]张牧,李君.TCP拥塞控制算法的仿真研究[J].计算机工程与应用.2008,44(21):82-84.
[7]于斌,孙斌,温暖等.NS2与网络模拟[M].北京:人人民邮电出版社,2006.
[8]徐雷鸣,庞博,赵耀.NS与网络模拟[M].北京:人民邮电出版社,2003.
[9]秦冀,姜雪松.移动IP技术与NS-2模拟[M].北京机械工业出版社,2006.
队列调度模型 篇5
1 操作系统内存限制
目前windows 32位操作系统最大能够支持3.6GB内存, 即便硬件系统安装再多的内存也是徒劳。虽然Vista SP1以及Windows7系统能够识别4GB以上更高容量的内存, 但是实际应用也只能用到3.6GB而已。
Windows 32位操作系统受制于32位架构限制, 即使其采用虚拟内存的寻址方式, 最多只能寻址到4GB。虚拟内存在早期的计算机中, 地址的转换很单纯, 有效地址就直接等于物理存储器的地址, 这适合同一时间只有一个进程在运作。然而Windows不肯能只有一个应用程序运行, 多进程同时进行数据处理是现代计算机的基本特征。因此, 人们决定为每个进程划定一块专用内存区域, 这样可以让多个进程同时运行。然而, 这样做的缺点也是显然的, 这种分段方式一般会在进程开关的重复过程中产生很多内存碎片, 很多小块内存无法被有效的利用。基于内存容量是有限的, 因此应用程序也不可能将所有数据都调入内存当中。
为了解决这个矛盾, 操作系统都引入了虚拟内存机制。在现在的Windows系统中, 任何一个进程都会被赋予其自己的虚拟地址空间, 这是一种逻辑地址空间, 并不存在实体, 该虚拟地址空间可以覆盖了一个相当大的范围。对于一个32位进程, 其可以拥有的虚拟地址空间为2^32=4GB, 典型情况为2GB用户空间, 2GB系统内核空间 (最大可调整为3GB用户空间和1GB内核空间) , 这与安装了多少物理内存没有任何关系。每个进程的虚拟地址空间都会被标上各自的ID, 这样两个进程之间的虚拟地址就不会互相干扰。虽然每一个32位进程可使用4GB的地址空间, 但并不意味着每一个进程实际拥有4GB的物理地址空间或使用4GB物理内存, 虚拟地址仅仅是一种逻辑地址。应用程序自然不能总在看不见摸不着的虚拟地址里溜达, 最终还是需要实实在在的物理存储器关联。应用程序会去为其虚拟地址申请物理存储空间, 这个空间通常会小于应用程序的总虚拟空间。这里所说的物理存储器并不局限于计算机内存, 还包括在磁盘空间上创建的页文件 (pagefile.sys) , 其存储空间大小为计算机内存和页文件存储容量之和 (所以Windows自动管理时的pagefile.sys是很大的) 。
2 操作系统内存地址扩展
2.1 物理地址扩展 (Physical Address Extension, PAE) 是早在PentiumPro时代就有的, 它可以提高IA32处理器应对4GB以上内存的能力。当启用PAE之后, Windows操作系统将从两级线性地址转换变为三层地址转换, 额外的一层转换用于访问超过4GB地址的物理内存, 可以将超出4GB地址的物理内存映像为应用程序进程的虚拟地址空间以提升虚拟内存性能。
2.2地址窗口扩展 (Address Window Expansion, AWE) 更是可以将未分页的物理内存转换到进程的虚拟地址。通过PAE, 我们可以完整的利用到被回收至4GB以上地址的那部分内存。PAE内存分页和非PAE内存分页模式的主要区别是PAE模式要求的额外分页级别 (3级而非2级) 。PAE模式要求多于4GB的RAM。硬件驱动程序在PAE模式下应该始终接收64位地址, 而一些旧驱动程序或硬件不能解释这种地址。就是因为一些旧硬件不支持PAEX86, 因此在PAE功能默认是不开启的。
3 数据的预处理
虽然通过物理地址扩展、地址窗口扩展可以增加应用程序物理内存使用, 但是无论如何扩展, 基于内存容量是还是有限的, 应用程序需要处理的数据也不可能将所有数据都调入内存当中。
例如指纹比对系统中目前单个指纹特征数据压缩比最好约0.2K, 单个人10个手指指纹采集数据量约2K, 1000人约2M, 100万人约2G, 1亿人比对库约200G。
如此之大数据量不可能一次读入内存, 必须采取一种策略分块或分段读入内存, 同时完成对数据的处理。算法的优劣直接影响系统的性能和软件的运行效率。
由于这些数据一般存储在数据库中, 如果先从数据库中选取数据, 逐条比对处理。由于计算机硬件体系中, 硬盘的存取速度远远小于内存的存储速度, 硬盘每次的I/O都需要占用大量的CPU时间。因此, 为了提高内存调度算法的效率对所处理的数据进行预处理。首先从数据库选取所需数据, 按照一定大小写入若干个文件中, 文件结构是前面几个固定字节记录写入文件记录数, 后面为数据记录。
4 环形内存调度算法
内存调度算法采用环形队列保存管理读入内存数据。环环队列的数据结构, 是一个先进先出循环缓冲区, 可以向面向应用进程提供对内存的互斥访问。相对于普通的队列, 当读指针等于环形的最大长度时, 无论队列是否有空间, 都将无法将数据存入队列。
环形队列的实现是基于如下结构:
数据存储类型--VData;
静态数组:VData*iReadDataBuffer;
数组最大长度:Int i Max ReadDataNumber;
寻址函数Int Next Pos (Int i Pos) ;
寻址函数根据参数i Pos并根据数组的最大长度i Max ReadData Number计算i Pos逻辑上的下一个元素在数组中的下标从而实现环环队列。
缓冲管理器VData数组选取长度大小是内存管理成功与否的关键因素之一。若VData数组长度过短, 可能缓冲区读入数据迅速充满;另一方面, 若VData数组过长, 则数组本身浪费了大量空间, 同时由于操作系统的内存资源严格受限, 堆空间无法承载过多的待处理数据, 从而造成有空余的VData单元而无可用空间存储数据的情况。因此需要选择合适的数组长度。
数据结构
缓冲队列头 (r BufferHeader) :记录即将被读出的VData单元在VData数组中的下标。
缓冲队列尾 (r BufferTail) :记录下一个将被写入数据的VData单元在VData数组中的下标。
有效数据区:以缓冲队列头 (r BufferHeader) 为起点, 循环向后直到r BufferTail。
无效数据区:VData数组中, 有效数据区以外的区域。
环形缓冲写入操作
若缓冲队列不满 (即:i EnableInput=True) , 则将经InVData (VData&VData) 参数VData传入的VData对象的复制给缓冲队列尾指向的VData单元 (i ReadDataBuffer[rBufferTail]) , 并检查i ReadData Buffer[rBufferTail].iIntegrated属性。i Integrated属性表示当前VData单元中VData数据的完整性:EEmpty表示当前VData单元无数据, 可以直接将数据复制到其i VData所指向的内存中;EPar表示当前VData单元已经保存了部分数据, 需要将新读入的数据连接到i VData中原有数据的后边;EIntegrated表示VData单元中的数据完整, 在保存了Marker标志位为1的数据后, 需要将其i Integrated属性置为EIntegrated并使用r BufferTail=Next Pos (rBufferTail) 将r BufferTail后移1位;反之, 若保存的数据中Marker位为0, 则说明该数据并没有承载数据的末尾部分, 还有后续数据。
此时, 置i Frame Buffer[rBufferTail].iIntegrated为EPart并且不移动r BufferTail。
环形缓冲队列读出操作
若缓冲队列不为空 (即:r BufferTail<>r BufferHeader) 时, 使用rData返回r BufferHeader指向的VData数据单元, 并使用r BufferHeader=Next Pos (rBufferHeader) 将r BufferHeader后移一位。移动r BufferHeader后需要检查缓冲区状态:
a.若此时r BufferHeader=r BufferTail则说明缓冲区在此次Pop操作后已经为空, 此时若设置了缓冲观察器, 则通知其调用NotifyBufferEmpty函数对“缓冲区已空”事件进行处理。
b.若此时缓冲队列中的有效数据区的VData个数为预先设置的“恢复入队阈值” (i ResumePushFrameThreshold) , 则说明此前发生过“缓冲区已满”事件, 入队函数 (PushL) 被禁用, 而在此次调用Pop方法后, 缓冲区里有足够的剩余空间用于接收新的数据。因此, 重新启用PushL方法并且通知缓冲观察器继续读入数据。
环形缓冲队列结构如图1所示。
结束语
本文真对操作系统内存容量的及操作系统对应用程序使用内存的限制的分析, 提出了一种环形队列内存调度算法, 设计及实现了环形队列的内存调度算法。
摘要：本文真对操作系统内存容量的及操作系统对应用程序使用内存的限制的分析, 提出了一种环形队列内存调度算法, 设计及实现了环形队列的内存调度算法。
关键词：物理地址扩展,地址窗口扩展,环形队列
参考文献
[1]孙钟秀.操作系统教程 (第3版) [M].北京:高等教育出版社, 2006.
[2]http://support.microsoft.com/kb/274750/zh-cn.
队列调度模型 篇6
LTE能为用户提供更高传输速率、更低时延和更好的QoS(Quality of Service)保证。为了实现这一要求,寻求更好的无线资源管理方法成为解决问题的关键。LTE的信道具有时变特性,并采用了共享信道的机制,如何在用户之间灵活分配和动态调度可用的无线资源,是最大限度提高频谱利用率和系统吞吐量的前提。上行调度区别于下行调度,上行采用SC-FDMA[1]技术,要求分配给任一UE的RB资源必须是连续的,传统的下行分组调度算法不能直接应用于上行。上行调度既要考虑优先级调度因子的影响,还要保证分配的RB具有连续性[1]。
本文提出了一种基于队列感知和信道感知的LTE系统上行调度算法,简称RPE(Riding Peak Evolution)算法。该算法研究了待传数据量大小、队列等待时延和信道状态信息对调度优先级[3]的影响,重新定义了调度优先级因子的表达式,然后在已有RP算法基础之上,依据重新定义的优先级进行RB的分配。仿真结果表明,该算法与传统调度算法相比提高了频谱效率,同时提升了系统的吞吐量。
2 LTE上行分组调度算法
LTE上行调度算法主要分为两类,一类是基于调度优先级的调度算法,一类是基于资源分配方法的调度算法。前者是根据计算得到的调度优先级对UE进行排序,然后依次为UE分配RB资源;后者是根据当前UE在每个RB上的度量值进行资源分配,为了保证RB连续性,还需要权衡UE在连续RB上的总度量值。在LTE上行调度过程中,上述两类调度算法是相辅相成的,既要根据UE的QoS需求计算调度优先级,又要考虑在RB分配过程中保证连续性,使系统频谱利用率最高和系统吞吐量最大。
2.1 基于调度优先级的传统算法
文献[2,3,4]分别介绍了目前主流的分组调度算法有最大载干比算法(Max C/I)、轮询算法(RR)和比例公平算法(PF),这些都是基于调度优先级进行资源分配的算法。最大载干比算法实现了吞吐量最大化,优先为信道质量好的UE进行调度,不能保证公平性。轮询算法保证了用户间的公平性,但是在系统吞吐量上欠佳。比例公平算法在吞吐量和公平性上达到一个平衡,目前大多数研究都是建立在PF算法基础上改进的。本文调度优先级也以PF算法为基础,把队列大小和队列时延考虑到其中,重新定义了调度优先级因子表达式。频域的PF算法的优先级表达式:
式中ri ,j(t ) 是指用户i在时刻t在RBj上获得最大传输速率,由信道质量决定;Ri (t ) 是指UEi 在时刻t内的平均吞吐量,根据(2)式进行更新:
式中tc 为更新时间窗。
2.2 基于资源分配方法的传统算法
文献[5,6,7]介绍了基于资源分配方法的上行调度算法主要有:最先最大值扩张算法(FME)、递归最大值扩张算法(RME)、峰值选择算法(RP)。最先最大值扩张算法是从具有PF调度度量值最高的RB开始查找,依次比较与当前RB相邻两个RB的调度度量值进行单边查找,选取优先级高的RB进行分配,但是该算法查找方法效率低。递归最大值扩张算法原理与FME一样,区别是采取了双边递归查找,查找效率明显提高。RP算法的原理同FME算法、RME算法一样,同样利用多载波系统的多普勒效应,用户信道质量状态在时域和频域上具有相关性。RP算法步骤如下:
step1:查找UE i-RB j的SINR度量值矩阵,选取具有最高SINR值的RBc ,其对应UEi ;
step2:把RBc 分配给UEi ,将此SINR度量值从矩阵中剔除;
step3: 查找具有次最高SINR度量值对应的RB,如果该RB有相邻的已被分配的RB,则此RB被分配给和相邻RB同样的UE;如果没有,则该RB被分配到给其对应的UE,剔除该SINR度量值。
step4: 执行step3,直到所有的RB都被分配完毕。
3 基于队列感知和信道感知的调度算法
队列状态信息包括队列大小和队列时延,对于非fullbuffer业务的系统来说,队列长度有界。如果用户的信道质量好,但是其对应的待传数据量不足,仅凭借信道质量好就在共享信道上优先调度该用户,就会造成系统资源的浪费,所以调度优先级需要考虑队列大小,优先为待传数据量大且信道质量相对较好的UE分配RB。同时不同业务队列对队列时延的要求不同,为保障UE的QoS需求,调度算法还应该充分考虑调度过程中各业务队列的时延要求,优先为时延要求更为严格且信道质量相对较好的UE分配RB。综合考虑队列大小、队列时延和信道质量计算调度优先级,优先为优先级别高的用户进行资源调度。
3.1 算法描述
LTE系统中eNodeB端通过UE端上报信道质量状态,可以获得每个用户在每个RB上的瞬时传输速率。ri,j(t )表示UEi 在RBj 上的获得的瞬时传输速率,B代表每个RB的带宽为180KHz,SINRi,j表示UEi 在RB j上的信道质量状态,ri ,j(t ) 表示为:
由式(3)我们可以得到,在每个TTI内,用户i能达到的总传输速率为:
其中xi ,j(t ) = 1表示RBj分给用户i,值为0时表示未分配给该用户,同时需满足每个RB最多只能分配给一个用户: 其中m表示RB个数。
调度过程中不仅需要考虑当前信道条件下的传输速率,还要考虑当前待传队列的数据量大小。针对每种业务队列,其到达率λi(t )服从参数为λi 的泊松分布,队列到达的时间间隔为一个TTI,记为T。则在单位时间T内,业务队列的平均到达率为λi 。由于缓存区域有界,设最大容纳的业务队列长度为Qthi 。则在t时刻开始,队列大小为:
同时由于队列长度有界,在t时刻待传队列的实际长度为:
式(5)中QLi (t ) 为当前信道实际传输的数据量,由当前信道状态下总传输速率和当前待传队列数据量大小决定,其表达式为:
由上可以设计基于队列大小的调度优先级因子表达式为:
其中n表示用户数, 为n个用户的平均待传数据量。在t时刻内,待传用户i的队列长度和所有用户的队列长度平均值成指数关系增长,用户的队列长度越长调度优先级越高。
由式(8)可知,相同条件下,待传数据量越大被调度的几率越大。LTE上行调度还需要考虑用户业务的QoS需求,本文考虑了队列等待时延对上行调度的影响。根据Litter公式可以估算出队列等待时延的计算公式为:
LTE系统中调度对象既包括非实时性业务,也包括实时性业务。非实时性业务和实时性业务对时延的要求不一样,当eNodeB调度混合业务时,需要根据统一的时延调度优先级公式对不同业务进行调度。对于非实时性业务,可以采用下式:
由式(7)可知,其中Qi (t ) 为在t时刻待传队列的实际长度,Qthi 为队列长度门限值,超过队列门限的数据包将直接被丢弃,用户队列长度和队列门限成指数性关系增长,队列长度越接近门限值,调度优先级越高。
对于实时性业务来说,每种业务对应一个时延门限值,可以采用下式:
式中Wthi 表示用户i当前业务对应的时延门限值,由于业务队列的平均到达率为λi ,所以(11)式可以变为:
其中Dthi=Wthi×λi ,是由业务时延得到对应的时延门限队列长度值。又由于VoIP、流媒体等实时性业务相对于FTP、WWW等非实时性业务对时延要求更高,所以Dthi(t )
在PF算法基础上,综合考虑队列大小和队列时延,得到基于队列感知和信道感知的调度优先级表达式为:
3.2 RPE算法流程
根据式(14)得到的调度度量值表达式,得到RPE算法流程,具体算法伪代码如下:
4 仿真结果和性能分析
本文算法通过系统级仿真验证所提算法的性能,并与传统频域的RME、FME算法进行比较。仿真参数为:小区数为7个,载波频率2GHz,带宽为20MHz,阴影衰落服从对数正态分布,标准差为8dB,快衰落为Jakes多径模型,UE的移动速度为3km/h,天线配置为SISO。仿真中,系统中实时业务以流媒体业务为代表,非实时性业务以FTP业务为代表,最大队列长度为100个数据包。仿真过程中用FQ ( △t) 表征用户的公平性,表达式为:
其中,Qi ( △t) 表示用户i在时间间隔 △t内获得的实际传输速率,系统用户数为n。FQ ( △t ) 1=表示所有用户在时间△t内有相同的数据速率。
图2是系统吞吐量的仿真结果,随小区用户数增加系统吞吐量的变化情况。RPE算法与传统的RP、RME、FME算法相比较,吞吐量有所提升,这是因为相同条件下,RPE算法下的用户得到的实际传输速率相比于其他三种算法有所增加,每个TTI实际能够传输的数据速率增加了,所以系统吞吐量也跟着增加。当小区内用户数少时,RPE算法和其他算法性能无大差别,这是由于用户数少时,系统有相对足够的RB为用户分配,RPE算法在低负载场景下性能提升不明显。
图3是用户数据速率公平性的仿真结果,小区活跃的用户数增加对用户数据速率公平性的影响。由图可以看出,RME算法相比较RPE、RP、FME算法在数据速率公平性方面表现较好。RPE算法在满足用户速率需求的同时更好的利用有限的无线资源,使待传数据量大和时延要求严格的用户在相同信道条件下系统获得的实际传输速率增加,但是因为RPE算法考虑了队列状态信息,在优先级表达式加入用户QoS需求的考虑,使系统在用户数据速率公平性方面的性能有所下降。同时,FME算法数据速率公平性随着用户数量增加下降很明显,是因为FME算法在查找最优优先级用户时采取单边查找策略,没有利用频域相关性查找,致使用户资源分配不合理,造成公平性很差。
图4是频谱效率随着用户变化的仿真,从图中可以知道,所提RPE算法在频谱效率上的性能优于FME、RME、RP算法,RPE算法在查找矩阵中的最大优先级时,由于引进新的调度度量值判断条件,使系统用户获得了更高的增益。同时,随着用户数量的增加,RPE算法和RP算法效果相似,只有用户数在5到35之间,RPE算法相比于RP算法获得增益。RME算法相比于FME算法,他们之间的差异接近3%。
图5是各算法在每个TTI内被调度的用户数统计结果,每个TTI时刻内小区中有50个激活的用户。由图可知,RPE算法将可用RBs尽可能多的分配给所有用户使用,相同条件下比FME、RME、RP算法调度更多的用户。
5 结论
队列调度模型 篇7
互联网技术的快速发展伴随着网络用户的迅速增加, 不断给网络服务器的性能带来越发巨大的挑战。集群服务器系统因其具有扩展性好、可用性和性价比高的特点, 已经受到学术界和工业界的广泛关注[1]。各种商业的或非商业的集群系统相继出现。其中由国防科技大学的章文嵩博士发起的LVS集群系统[2], 因其开放性及出色的性能在全球范围内得到大量应用[3]。
集群服务器系统通常由前端服务器 (任务调度机) 与后端真实服务器池组成[4]。前端服务器是客户访问集群服务器的唯一入口, 通过特定的调度算法将收到的客户请求数据包分配给内部的真实服务器。选择一个良好的调度算法以保证内部真实服务器负载的均衡性, 避免出现个别服务器的偏载甚至过载, 同时保证调度的执行效率, 对于集群系统至关重要。调度算法的优劣直接影响了系统性能的好坏[5]。事实上, 负载均衡调度属于并行系统调度的一个特例, 而并行系统的调度问题是NP难解的, 因此无法在合理的时间内找到最优解[5]。目前的负载均衡调度算法多是启发式的, 不同的算法在不同环境下表现差异很大。如何找到一个尽可能优异的算法是目前学术界的一个研究热点。自集群技术出现至今, 已有多种算法被相继提出。以LVS集群为例, 目前常用的面向同构集群 (各服务器提供相同的服务集) 的基本调度算法主要有[5]:轮转调度 (Round-Robin Scheduling) 、加权轮转调度 (Weighted Round-Robin Scheduling) 、最小连接调度 (Least-Connection Scheduling) 和加权最小连接调度 (Weighted Least-Connection Scheduling) 。这几种算法都属于静态算法, 均不考虑各服务器的当前负载。此外, 还有文献[6]提出的动态反馈负载均衡算法 (Dynamic-feedback load balancing) , 在调度时考虑各服务器实时的负载状况, 属于动态算法。
这些算法都是在内核中实现的, 其调度粒度都是面向连接的。本文将针对上述的5种算法分别作出分析, 并在此基础上给出一种新的调度算法—基于优先级队列的动态反馈负载均衡调度算法。
1 LVS集群负载均衡调度算法概述与分析
所谓负载均衡调度, 包含两层含义:一是调度, 即将收到的用户访问请求分配给内部的真实服务器, 由其作出应答;二是负载均衡, 即在进行调度时要尽力保证各个真实服务器不出现过载。
一个负载均衡调度算法的优劣主要从两方面来评价:一是调度的负载均衡性, 即保持各服务器负载均衡的能力。由于用户请求的服务时间变化很大, 集群在运行过程中很容易出现负载的不平衡现象。对这一问题处理不好, 将很容易导致用户的连接请求延迟甚至无法得到应答。二是调度的执行效率。前端服务器 (即负载调度器) 作为集群系统的唯一入口, 其CPU资源是非常宝贵的, 特别是对于VS/NAT型的集群, 前端服务器还要处理对系统所有数据包的转发。如果算法的执行效率不够高, 将很容易使负载调度器成为整个系统的性能瓶颈。
对上文提到的5种负载均衡调度算法简要分析如下:
(1) 简单轮转调度。简单轮转调度算法就是以轮转的方式将客户连接请求分配给各真实服务器[5]。这种算法实现最为简单, 且算法的时间复杂度为O (1) 。但该算法不区分各真实服务器的性能差异, 也不考虑各服务器的当前状态。当各真实服务器性能差异较大, 并且当请求服务时间变化较大时, 这种算法有可能导致各服务器间负载的严重不均衡。
(2) 加权轮转调度。运用这种算法, 需要由系统管理员根据各内部真实服务器的性能设置一个静态的权值, 然后算法以轮转的方式选择出一个合适的真实服务器, 并保证各服务器所收到的连接请求数正比于其权值[5]。这种算法的时间复杂度为O (n) , 其中, n代表系统的规模, 即真实服务器的数量。这种算法考虑了服务器间的性能差异, 负载均衡能力强于简单轮转调度, 但却仍然忽略了各服务器的当前状态, 并且时间复杂度较高, 当系统规模较大时, 可能会带来较高的调度延时, 增大系统开销以致降低影响系统性能。
(3) 最小连接调度。调度器记录各真实服务器的连接数, 算法执行时以轮转的方式查找连接数最小的服务器并为其调度当前请求[5]。类似于轮转调度, 该调度也没有考虑各服务器的性能差异, 并且时间复杂度也是O (n) 。
(4) 加权最小连接调度。类似于加权轮转调度, 由系统管理员为每个服务器根据其性能设定一静态的权值。该算法在调度新连接时尽可能使服务器的当前连接数与其权值成比例。该算法的负载均衡能力要优于前三种算法, 但是时间复杂度也为O (n) 。
(5) 动态反馈负载均衡调度。这一算法会根据服务器的实时负载, 动态地调整各服务器的权值。在此基础上, 调度采用加权轮转调度或者加权最小连接调度。研究表明, 基于动态反馈的调度算法在表现上优于其他算法。但是由于调度采用的是加权轮转调度或者加权最小连接调度, 算法的时间复杂度仍为O (n) 。因此当系统规模较大时, 算法也会带来较高的系统开销。
可见, 以上5种算法中, 除简单轮转调度算法外, 其他4种算法的时间复杂度都是O (n) 。然而, 有研究表明, 简单轮转调度算法的综合性能最差, 而动态反馈负载均衡算法优于现有的其他不考虑服务器动态负载的算法。本文所提出的负载调度算法将基于现有的动态反馈负载调度算法并结合加权轮转调度, 通过加入优先级队列使算法的时间复杂度降至O (1) 以达到更优异的性能表现。
2 基于优先级队列的动态反馈负载均衡调度算法
动态反馈负载均衡算法考虑了各服务器的动态负载状况, 使其获得了更好的性能。本文所提出的算法吸收了这一优势, 并通过建立优先级调度队列, 使得算法的时间复杂度降至O (1) 。
2.1 动态反馈
文中, 动态反馈的含义是指各真实服务器动态反馈给负载调度器的负载信息。这些负载信息是通过一个专门的守护进程Monitor Daemon进行收集的。其工作环境如图1所示。
由图1所可知, Monitor Daemon周期性 (周期T为5~20秒) 地对各真实服务器进行轮询以采集其负载信息。所采集的负载信息包括CPU利用率、内存可用量、进程数和服务响应延时。
除了动态反馈得到的负载, 还可以在调度程序内统计两次轮询期间各服务器所收到的连接请求数。
2.2 动态权值的计算
接下来, 将通过这些动态的负载信息计算出一个动态负载权值wd。最终的权值为原权值与动态负载权值的和。
考虑一组服务器S={S0, S1, S2, …, Sn-1｝, 以向量LOADi= (CONNECTIONi, CPUi, MEMORYi, PROCESSi, RE-SPONSEi) 表示服务器Si的负载。其中, CONNECTIONi表示服务器Si在两次轮询期间所收到的连接数Ni与各服务器收到的连接数平均值的比值, 其公式为:
CPUi的计算公式为:
其中, RATEi表示服务器Si的CPU利用率。
MEMORYi的计算公式为:
其中, AVAILABLE_MEMORYi表示Si的可用内存大小。
PROCESSi和RESPONSEi的计算方法也类似于CON-NECTIONi, 公式直接列出如下:
现在, 引入负载权值向量WEIGHTi= (1-CONNECTI-ONi, 1-CPUi, MEMORYi-1, 1-PROCESSi, 1-RESPONSEi) 。该向量的各个维度表征了相应负载对动态负载权值的贡献。
由于各类负载对服务器的影响程度是不同的, 且不同种类的服务也有其特点, 因此再引入权值系数向量R= (Rcon, Rcpu, Rmem, Rproc, Rresp) , 且有关系Rcon+Rcpu+Rmem+Rproc+Rresp=1。该向量可由系统管理员根据实际情况动态地设定。例如R= (0.1, 0.4, 0.1, 0.1, 0.3) 。服务器Si的动态负载权值wdi计算公式如下:
最终的动态权值为:
即, 每个周期T内根据采集到的服务器负载信息对权值做一次调整, 如果某服务器出现偏载 (负载高于平均水平) , 权值就会被削弱, 否则被提高。其中, λ为负载权值系数, 也可由系统管理员动态设定。在最初服务器被加入集群时, 系统管理员为其设定一个初始权值DEFAULT_WEIGHTi (当服务器Si不可用时, DEFAULT_WEIGHTi为零, 该服务器不接受调度) 。
为避免动态权值变得很大, 将wi的取值区间限定为[max (1, DE FAULT_WEIGHTi/4) , DE FAULT_W EIG-H T*4]。
2.3 优先级调度队列
根据新采集的负载信息算出新的动态权值之后, 将根据新权值建立优先级调度队列。
假定服务器Si的调度信息存储在数据结构SERVER中, 定义下列数据结构作为调度队列的节点:
令[ci=10*wi]作为负载调度的参考权值, 同时作为调度队列的优先级。可按照下列过程建立优先级调度队列:
(1) 定义数组QUEUE_HEAD hv[MAX[ci]], 并将各元素c字段初始化为数组下标值, first和next字段初始化为NULL。
(2) 定义数组QUEUE_NODE nodes[n]。依次扫描服务器调度信息表, 将nodes[i]的c字段初始化为ci, server字段初始化为指向Si的调度信息数据结构。如果DE-FAULT_WEIGHTi>0, 则将nodes[i]插入到hv[ci]指向的调度队列中。重复第 (2) 步直至扫描完Sn-1。
(3) 扫描数组hv, 将其中建立起的调度队列头部组织为一个链表, 该链表的表头为具有最高c值即最高优先级的调度队列头。
假设有一组真实服务器S=邀S0, S1, …, S8妖, 在某一时刻其动态权值向量为W= (3.5, 1.8, 4.7, 2.3, 1.8, 2.3, 1.8, 3.5, 2.6) , 则按照上述过程建立起来的优先级调度队列如图2所示。
2.4 调度算法
定义优先级调度队列头链表的头指针为h, 指针p指向上次选择的服务器, 对其初始化为h->first。调度算法描述伪代码如下。
为降低开销, 各节点的内存都是静态分配并存放在数组中, 不需要动态地申请或释放。分析以上算法, 很容易得出其时间复杂度为O (1) 。
随着算法的执行, 高优先级的调度队列会不断降级, 直至与其下一级队列优先级相等并与其合并。这样, 最终各优先级队列将合并为一个大的调度队列。当优先级降级至0时, 算法返回NULL。此时将恢复原来的优先级队列 (可通过创建一份整个优先级队列的拷贝实现, 此时调度时间会有一个小峰值, 称之为毛刺现象) 。在一个这样的过程中, 服务器Si所得到的连接请求数与其动态权值是成正比的。这一点可以通过以下的分析证明:
在每个优先级队列内, 调度是通过轮转进行的。每当完成一次轮转, 队列内各服务器被调度一次, 且队列降级一次。因此参考权值为ci的服务器参与的降级次数为ci次, 从而其得到的连接请求数Ni也为ci。而ci与wi成正比, 故Ni与ci成正比。这样就保证了算法的负载均衡能力。
此外, 当下一次Monitor Daemon负载采集发生时, 调度队列将被重建。在重建完成后 (而非完成前) 替换原来的优先级队列。这句话的涵义在于, 在重建优先级调度队列的过程中, 调度程序仍可继续进行。这是因为内核中的负载调度进程具有更高的进程优先级。
3 结束语
调度算法的选择, 对集群系统的性能起着至关重要的作用。本文分析了现有通用集群负载均衡调度算法的优缺点, 并在此基础上提出了一种新的调度算法, 即基于优先级队列的动态反馈负载均衡调度算法。该算法采用动态反馈机制以达到尽可能高的负载均衡效果, 并且具有O (1) 的时间复杂度, 因而使其同时具有较以往调度算法更高的执行效率。这有助于提高集群系统的吞吐率, 增强其性能。
参考文献
[1]SCHROEDER T, GODDARD S, RAMAMURTHY B.Scalab-le Web server clustering technologies[J].IEEE Network, 20-00, 14 (3) :38-45.
[2]ZHANG Wensong, JIN Shiyao, WU Quanyuan.LinuxDirector:A connection director for scalable Internet services[J].Compu-t.Sci&Technol.2000, 15 (6) :560-571.
[3]MACK J.LVSDocument[EB/OL].http://www.linuxvirtuals-erver.org, 2003.
[4]ZHANG Xiaolan, BARRIENTOS M, CHEN J, et al.HACC:AnArchitecture for Cluster-based Web Servers[C]//Proceeding ofthe 3rd USENIX Windows NT Symposium, Seattle, Washington, 1999:155-164.
[5]GRUDENIC, BOGUNOVIC N.Computer cluster scheduling al-gorithm based on time bounded dynamic programming[J].IEEENetwork, 2011:23-27.
[6]周集良, 彭小宁, 等.基于集群的负载平衡调度算法研究与实现[J].计算机工程, 2005, 31 (12) :108-110.
[7]王晋鹏, 潘龙法, 李降龙.LVS集群中的动态反馈调度算法[J].计算机工程, 2005, 31 (19) :40-42.
[8]唐丹, 金海, 张永坤.集群动态负载平衡系统的性能评价[J].计算机学报, 2004, 27 (6) :803-811.