WFQ不是PGPS吗？ ——对"一种新的基于GPS的分组公平调度器"一文的评注

邬海涛等^[1]声称"证明了WFQ、WF²Q等算法并不是P-GPS(基于分组的GPS),也就不能保证P-GPS的时延及服务特性".不幸的是,该文对WFQ系统中一个关键概念"阻塞的连接的集合"的理解是错误的,因此导致该文的结论无效.     

一类基于调度表的公平轮循调度算法

本文研究了一类利用时标在调度表中安排信元发送时隙的公平轮循(Fair Round Robin,FRR)调度算法.对其中三种算法的性能进行了分析比较.FRR能够保证连接的带宽和时延,同时实现复杂性低于一些分组公平排队算法,例如WF²Q+.     

一种新的HSDPA分组调度算法研究

目前已提出的HSDPA调度算法仅是基于用户的优先级进行数据分组的调度.文章考虑了3G系统的业务多样性,综合考虑用户的优先级和业务的级别,创新性地提出将两类分组调度算法,即基于业务类别的分组调度算法--加权公平排队算法,与基于用户优先级的调度算法--最短队列算法或者最长队列算法相结合后的调度算法.仿真的结果显示,提出的调度算法能满足不同业务要求的QoS.从吞吐量和延时来看,最短队列算法与加权公平排队算法结合方案优于最长队列算法与加权公平排队算法结合的方案.     

一种分级WFQ的宽带无线接入系统QoS架构

文章介绍了加权公平排队(WFQ)分组调度算法和IEEE 802 16的QoS架构.在此基础上,文章结合分级WFQ分组调度算法和IEEE 802 16协议中所提供的控制机制提出了一种适合于BWA系统的QoS架构.该架构充分利用IEEE 802.16提供的控制机制,结合分级WFQ公平队列调度算法,在主动授予业务(UGS)、实时轮询业务(rtS)、非实时轮询业务(nrtPS)和尽力传输业务(BE)之间公平分配带宽,并保证各种业务的QoS特性,完成了在IEEE 802 16协议中留给用户自己定义的调度策略.     

WFQ流量调度算法研究

高速包交换电路常常需要为各种不同要求的服务公平地分配带宽,在公平分配带宽的同时还需要满足这些服务的服务质量(QoS)参数.不同QoS需求的业务将被复用到同一条输出链路上,要为它们公平地分配带宽就需要用到各种各样的流量调度算法.加权公平队列(WFQ)是一种常用的流量调度算法.它不仅能保证带宽分配的公平性,而且具有较好的时延性能.文章较为详细地讨论了WFQ算法的基本原理.     

在CICQ交换结构下实现分布式的WFQ类加权公平调度算法

传统的基于crossbar的输入排队交换结构在提供良好的QoS方面存在很大的不足,而CICQ(Combined Input and Crosspoint buffered Queuing)交换结构与传统的交换结构相比,不但能在各种输入流下提供接近输出排队的吞吐率,而且能提供良好的QoS支持。该文基于CICQ结构,提出了在输入排队条件下实现基于流的分布式WFQ类分组公平调度算法的方案,并通过仿真验证了这一方案的有效性。     

一种基于紧急程度的自时钟开始时间公平排队分组调度算法

为了克服目前GPS (Generalized Processor Sharing)类调度算法中实时应用分组的排队时延较大且不稳定的局限性,该文提出一种新的分组排队调度算法,该调度算法在计算分组服务标签时添加了一个紧急程度函数,调整了到达分组间的竞争关系,从而可以按照实时性应用的要求来调整到达分组的转发先优级,由此显著降低了实时性应用分组的排队时延和抖动幅度。分析和仿真实验表明,与GPS类其它调度算法相比,该调度算法对于实时应用的分组能提供较低的、更稳定的排队时延保证,同时还继承了GPS类算法的公平性和排队时延有界等特性,而且对系统虚拟时间的跟踪计算更为简捷高效。     

调度机制对网络QoS影响的研究分析

在网络中采用的调度机制与网络的服务质量有很密切的关系.为了满足不同网络业务服务的要求.QoS网络必须提供不同的排队规则.利用网络模拟器NS-2仿真分析各种队列调度算法,包括:去尾算法,基于轮循的调度算法,分组公平队列,基于类的队列算法,随机早期检测算法对QoS各个因子的影响以及队列调度算法的特点,根据算法特点指出不同调度算法运用的最佳场合.     

基于量子通信的电力业务调度算法

量子通信能够有效提高电力业务传输的可靠性与安全性,但由于量子密钥成码率低,难以满足重要电力业务的加密需求,因此,需要一种队列调度算法对量子通信中的待加密电力业务进行合理调度。提出了一种改进的加权公平队列（weighted fair queuing,WFQ）算法LD-WFQ,算法通过估计待加密数据分组的预计耗时,优先处理即将超时的待加密数据分组,在保持高优先级业务量子加密时延达标率的基础上,有效降低了低优先级业务的量子加密超时率。与WFQ算法进行仿真对比,结果证明了LD-WFQ算法的优越性。     

用户系统基于流的QoS调度

Diff-Serv网与用户系统之间有服务等级协议，有必要对用户系统的分组流进行合理调度，以确保定购的服务等级上速率、突发比特量等符合协议要求。进行合理调度还有有效分配带宽好处。基于流的排队(FBQ)在加权公平分享带宽的同时起到流量整形(traffic shaping)的作用，比较适合这种调度要求。但FBQ对带宽利用率不够高，本文在FBQ分类结构基础上通过新颖的分配令牌参数和虚拟时钟的方法构建新的分级调度算法，保留FBQ优点但提高带宽利用率。     

Rate-proportional servers: a design methodology for fair queueingalgorithms

Generalized processor sharing (GPS) has been considered as an ideal scheduling discipline based on its end-to-end delay bounds and fairness properties. Until recently, emulation of GPS in a packet server has been regarded as the ideal means of designing a packet-level scheduling algorithm to obtain low delay bounds and bounded unfairness. Strict emulation of GPS, as required in the weighted fair queueing (WFQ) scheduler, however, incurs a time-complexity of O(N) where N is the number of sessions sharing the link. Efforts in the past to simplify the implementation of WFQ, such as self-clocked fair queueing (SCFQ), have resulted in degrading its isolation properties, thus affecting the delay bound. We present a methodology for the design of scheduling algorithms that provide the same end-to-end delay bound as that of WFQ and bounded unfairness without the complexity of GPS emulation. The resulting class of algorithms, called rate-proportional servers (RPSs), are based on isolating scheduler properties that give rise to ideal delay and fairness behavior. Network designers can use this methodology to construct efficient fair-queueing algorithms, balancing their fairness with implementation complexity     

基于OPNET的试验通信网QoS性能分析与仿真

从试验通信网IP化的需求出发,使用OPNET仿真软件研究了IP技术体制下试验通信网的QoS性能,主要研究了区分服务机制的优先级排队(PQ)和加权公平排队(WFQ)两种队列调度算法。实验结果表明,在试验通信网带宽资源紧张的情况下,为保证重要程度高的任务信息的传输质量,可以通过PQ将其设置成高的优先级进行保障,或通过WFQ为其分配充足的带宽资源进行保障。     

利用基于测量的WFQ实现比例区分服务模型及其性能分析

本文首先介绍了比例区分服务模型的定义以及现有的两种实现算法BPR和WTP,然后定量地分析了WFQ算法在系统负荷和业务负载分布变化时的性能变化,得出了其本身具有一定的抗突发能力.提出了一种基于测量的可变权值的WFQ调度算法,最后通过仿真,将它与BPR,WTP和WFQ进行了比较.仿真结果证明基于测量的WFQ在业务负载正常分布的情况下性能比WFQ更好,且抗高等级突发的能力更强.     

An efficient ATM network switch scheduling

The problem of allocating network resources to application sessions backlogged at an individual switch has a great impact on the end-to-end delay and throughput guarantees offered by the network. There exists a class of algorithms based on weighted fair queueing (WFQ) for scheduling packets which are work-conserving and they guarantee fairness to the backlogged sessions. These algorithms also apply to ATM networks with a packet equal to a single cell or an ATM block (of fixed size). Bursts are groups of varying numbers of cells. We generalize WFQ to schedule bursts. Our motivation is to derive an adaptive algorithm which generalizes the (fixed size) packet level to a varying size packet level. The new algorithm enhances the performance of the switch service for many important applications. The proposed scheme maintains the work-conserving property, and also provides throughput and fairness guarantees. The worst-case delay bound is also given. We use simulation to study the performance characteristics of our algorithm. Our results demonstrate the efficiency of the new algorithm.     

Efficient fair queueing algorithms for packet-switched networks

Although weighted fair queueing (WFQ) has been regarded as an ideal scheduling algorithm in terms of its combined delay bound and proportional fairness properties, its asymptotic time complexity increases linearly with the number of sessions serviced by the scheduler, thus limiting its use in high-speed networks. An algorithm that combines the delay and fairness bounds of WFQ with O(1) timestamp computations had remained elusive so far. In this paper we present two novel scheduling algorithms that have O(1) complexity for timestamp computations and provide the same bounds on end-to-end delay and buffer requirements as those of WFQ. The first algorithm, frame-based fair queueing (FFQ), uses a framing mechanism to periodically recalibrate a global variable tracking the progress of work in the system, limiting any short-term unfairness to within a frame period. The second algorithm, starting potential based fair queueing (SPFQ), performs the recalibration at packet boundaries, resulting in improved fairness while still maintaining the O(1) timestamp computations. Both algorithms are based on the general framework of rate-proportional servers (RPSs) introduced by Stiliadis and Varma (see ibid., vol.6, no.2, p.164-74, 1998). The algorithms may be used in both general packet networks with variable packet sizes and in asynchronous transfer mode (ATM) networks     

高效的WF2Q+调度算法的实现研究

文章提出了WF^2Q＋调度算法的两种实现模型，即离散模型和离散简化模型。它们是在WF^2Q＋调度算法数学模型的基础上的高效实现方法。离散模型很好的保持了WF^2Q＋调度算法数学模型的性能，而且便于硬件实现。离散简化模型在离散模型的基础上进行简化，基本保持了WF^2Q＋度算法数学模型的性能，但大大节约了系统资源，易于实现。WF^2Q＋调度算法的离散模型和离散简化模型非常适合应用于高速核心交换网络中的分组调度。     

A Totally Shared Optical Packet Switch: Dimensioning, Control Algorithm and Performance

In this paper, a novel optical packet switch is proposed, which uses a set of shared fiber delay lines (FDLs) and a set of shared tunable wavelength converters (TWCs) to resolve optical packet contentions. In addition, two control algorithms, i.e., Fiber-First (FF) and Wavelength-First (WF), are proposed to schedule optical packets. Performance of the novel switch is evaluated by means of simulation experiments. Simulation results show that based on either of these two control algorithms, the switch can achieve super performance without employing a lot of FDLs and TWCs. Moreover, the performance of FF and WF is compared. Detail analyses are also given in this paper.     

Exact GPS Simulation and Optimal Fair Scheduling With Logarithmic Complexity

Generalized processor sharing (GPS) is a fluid scheduling policy providing perfect fairness over both constant-rate and variable-rate links. The minimum deviation (lead/lag) with respect to the GPS service achievable by a packet scheduler is one maximum packet size. To the best of our knowledge, the only packet scheduler guaranteeing the minimum deviation is worst-case fair weighted fair queueing , which requires on-line GPS simulation. Existing algorithms to perform GPS simulation have worst-case computational complexity per packet transmission (being the number of competing flows). Hence, has been charged for complexity too. However it has been proven that the lower bound complexity to guarantee deviation is, yet a scheduler achieving such a result has remained elusive so far. In this paper, we present L-GPS, an algorithm that performs exact GPS simulation with worst-case complexity and small constants. As such it improves the complexity of all the packet schedulers based on GPS simulation. We also present , an implementation of based on L-GPS. has complexity with small constants, and, since it achieves the minimum possible deviation, it does match the aforementioned complexity lower bound. Furthermore, both L-GPS and comply with constant-rate as well as variable-rate links. We assess the effectiveness of both algorithms by simulating real-world scenarios.