分组调度分类.doc

分组调度算法分类1. 基于静态优先级的算法：PQ和QLT（queue length threshold）算法。PQ算法给每个队列赋予不同的优先级，每次需要调度时，具有最高优先级的非空队列中的分组最先被选择服务。算法简单，容易实现，然而在高优先级队列源源不断地有分组到达时，低优先级的队列容易被“饿死”，公平性很差。QLT给每个队列设置调度阈值，需要进行调度时从最高优先级开始比较队列的长度和调度阈值。当最高优先级队列的长度大于其调度阈值时，该队列头部的分组首先被选择服务；当最高优先级队列的长度小于其调度阈值时，不再服务该队列，而是首先检查具有此高优先级的队列，如此类推。通过合理的调度阈值，QLT算法在保证优先级关系的基础上，提高的公平性。2. 基于轮循的算法：RR，WRR（weighted round-robin），DDR等RR只是简单的对所有队列进行轮循调度，一次调度发送一个分组，使得不同队列在某种程度上“平等”的使用带宽资源。由于分组长度不固定，使得长分组队列可能比短分组队列得到更多的服务，获得更高的带宽，公平性受到很大限制，不能提供时延保证。WRR给队列赋予不同的权值，代表一次完整循环队列被服务的分组数。同时为每个队列维护一个计数器，初始化为权值。每次轮循时，计数器为非零的队列允许发送一个分组，并将计数器减一。当所有队列的计数器均为零时，重置权值。能够以比较平滑的方式调度输出业务，但仍存在由于分组变长带来的不公平性。DDR算法以字节为单位为每个队列分配一个带宽配额，该配额的比例对应于队列服务速率的比例。同时，为每个队列维护一个计数器，初始化为其带宽配额。每次轮循时，如果待发分组长度小于或等于计数器值，则允许发送，并把计数器减去此分组的长度值；如果待发分组长度大于计数器值，则检查下一个队列，同时，把该队列计数器的差值累计到下一次循环（即下次调度该队列之前，把此剩余值和配额之和赋予计数器）。很好的解决了带宽分配的公平性问题，但不能很好地满足业务地时延特性。其他算法：URR（urgency-based round-robin），SRR（surplus round-robin）等。3. 基于GPS模型地算法（PFQ算法）：常见的基于GPS模型的算法有：WFQ，WF2Q（worst-case fair weighted fair queuing），WF2Q+，VC（virtual clock），SCFQ（self-clocked fair queueing），SFQ（stochastic fair queueing），SPFQ（starting potential fair queueing），FFQ（frame-based fair queueing）等。此类算法是对理想流体模型GPS的逼近，成为PFQ（packet fair queueing）算法。GPS模型是一个理想化的流模型，假定每一个队列中的业务元可以无限小，队列之间具有相同的优先级，调度器可以根据各队列的共享比例同时服务所有的队列，能够使各业务流真正公平的共享服务器，为每个业务流提供明确的端到端时延上限保证。无法实现。PFQ是把GPS模型应用于网络系统的一类近似算法，在分组进入各自业务流的队列时，为其加上调度优先级标记，并依此顺序逐次调度各分组进行服务。此类算法的基本思想是维护一个系统虚拟时间V(t)，并为每一个队列维护一个虚拟开始时间标签Si(t)（代表队列i头部分组的虚拟开始发送时间）和一个虚拟完成时间标签Fi(t)（代表队列i头部分组的虚拟完成发送时间），并当队列中有分组发送完毕，或者空队列有新分组到达，更新Si(t)，Fi(t)。在每次需要调度时，系统根据时间标签的大小选择一个分组。所有PFQ算法都是在虚拟时间函数的基础上根据一定的选择策略进行调整的。目的是尽量使Si(t)和V(t)之间的差别达到最小，从而尽量精确逼近GPS模型。V(t)的作用是当一个队列变为活动时重置这个队列的虚拟开始时间，以保证算法的公平性。各个具体算法的不同之处在于系统虚拟时间V(t)的计算和分组选择策略。分组选择策略主要有三种：最小虚拟完成时间优先，最小虚拟开始时间优先，最小合法虚拟完成时间优先。可以看成是基于速率的调度算法，通过为每一队列提供一定的速率保证来获得时延保证。4. 基于时延的算法：EDF，RCS（rate-controlled service），Delay-EDD，Jitter-EDD,RC-EDF（rate-controlled EDF），DC-EDF（deadline-curve based EDF），EEDF（earliest effective deadline first）等。以排队时间作为参数，以提供时延保证为目的。此类算法的基本思想是：给每个队列分配一个时延参数Di作为时延上界，为每一个到达的分组计算时间标签Ti = Ai + Di作为到期时间（deadline），其中Ai是分组到达时间。每次调度具有最小到期时间Ti的分组，具有O(logN)的排序复杂度。5. 分层链路共享算法：CBQ（class-based queueing），H-PFQ（hierarchical packet fair queueing），HFSC（hierarchical fair service curve）等。分层链路共享把不同类型的业务流分成不同级别的类，并同时考虑业务的实时性和链路共享的需求，按照不同的层次进行分组调度，从而提供了在分层共享树内不同等级的共享链路带宽资源的方法。分层链路共享的目标是：（1）如果某个业务类有数据到达，系统应该能够为其提供预先分配的带宽保证。这样，保证了某些高优先级业务的实时要求。（2）某个类未用完的带宽可以根据一定的规则被同级别的其他“兄弟”类共享，而不是被所有其他类共享。这样使得某些低优先级业务不会被“饿死”，提高了系统的公平性。为了实现这一控制目标，系统从概念上设计了两级调度器：常规调度器（general scheduler）和链路共享调度器（link-sharing scheduler）。当系统没有出现拥塞时，使用常规调度器，使得各业务类都能得到所需要的服务。常规调度器可以采用轮循调度、静态优先级调度等。当系统出现拥塞时，启动链路共享调度器，对某些超出其额定带宽的业务类进行限制，对其“规则化”。优点是:能够在保持高链路资源利用率的情况下提供很好的带宽、时延保护以及公平性。6. 核心无状态算法：CSFQ（core stateless fair queueing）和CJVC（core stateless jitter virtual clock）等。通过研究在调度过程中需要用到哪些状态信息，考虑如何在核心网络节点中消除它们。此类算法把网络分为边缘和核心两个域，同时又需要边缘节点和核心节点的有效配合。在边缘节点为每个流维护一定的状态信息，并给每一个分组打上调度策略所需要的信息标签。而核心节点则不必进行复杂的流分类和为每一个流都维护状态信息，而是在分组传输的每一跳上，根据分组携带的信息标签进行调度。信息标签由边缘节点生成，一部分信息在传输过程中保持不变，另一部分信息则在分组转发之前进行修改以供下一个节点使用。这种分组转发过程中修改分组头状态信息的方法称为DPS（dynamic packet state）技术，是核心无状态调度策略的关键部分。7. 基于服务曲线的算法：SCED（service curve-based earliest deadline）和HFSC（hierarchical fair service curve）等。8. 比例区分算法：PAD（proportional average delay），WTP（waiting-time priority）和HPD（hybrid proportional delay）等。比例区分服务是一种相对区分服务。在相对区分服务中，数据流被组合成服务类，这些服务类按照其分组转发的服务质量要求进行排序，以决定其排队延迟、分组丢失率等转发行为。网络不提供接纳控制和动态资源预留，而是由用户和应用程序选择最符合他们质量要求和价格限制的服务类。网络应用和用户不能获得绝对的服务质量保证，但网络能够保证高级别的类可以得到比低级别的类更好的服务。在比例区分服务模型中，任意两个数据类在每一跳所获得的服务满足确定的比例，比例参数由网络管理者设定，与类的负载无关。9. 结合缓冲管理的算法：C-DBP-Delay-Loss，JoBS等。C-DBP-Delay-Loss算法：把(m, k)模型和用于调度实时数据流的DBP（distance based priority）算法应用于相对区分服务网络的一种改进算法。(m, k)模型提供了一种用以计算某个流的服务质量特性的方法：在某个给定流中，每k个连续分组中，至少有m个分组能满足端到端时延限制。在DBP算法中，每个网络节点的每个流都关联一个状态机，其中的状态描述了这k个分组的传输情况。一个流的DBP值等于到达某失败状态所需发送的分组数目，其中失败状态是指发送分组数小于丢弃分组数。DBP越小，该流的优先级越高。JoBS算法实现了基于区分服务类的服务速率分配和丢弃控制，可同时提供单节点的时延区分和丢失区分，特点是：把缓冲管理和分组调度综合到一步完成；可同时支持相对和绝对的服务质量（时延和丢失率）保证。JoBS的基本工作原理是：定义一个系统目标函数，并为每个队列设定QoS约束（包括时延和丢失