下载文档原格式
WFQ算法1 概述分组网络允许用户分享诸如缓冲Buffer 和链路带宽（link bandwidth ）等等这样的资源。
当一组用户（flows or connects ）复用在相同链路时，就需要一个调度策略，决定如何为分组提供服务。
换句话说，当网络资源被完全使用时，就需要一个完善的调度算法来区分不同用户、不同业务流的优先等级以满足不同的QOS 需要。
例如，实时业务一般对延时比较敏感，而数据业务则对数据丢失比较敏感。
WFQ 算法正是为了满足上面需要而出现的。
•加权公平队列（WFQ ：Weighted Fair Queuing )——该算法支持高优先级流量的保证带宽，但低优先级流量可以获得公平的带宽共享权力。
根据数据包标记、源地址和目标地址字段、端口号以及ToS 字段的信息等，制定流量优先级。
如果高优先级队列不在使用中，低优先级流量便可以使用其队列。
该算法可以预防高带宽流量获取不公平的资源共享。
2 WFQ 算法原理的介绍 2.1 GPS 算法原理提到WFQ 算法，首先需要指出的是它本身是对GPS 调度算法的模拟实现。
Generalized processor sharing(GPS)是一种理想的调度策略，它可以提供准确而公平的带宽分配，根据所有等待队列（sessions ）所需的最小带宽（速率）按比例分配出口容量。
GPS 调度算法是基于理想的流模型实现的，即假设GPS 调度器可以同时为所有的等待队列提供服务，输出链路容量可以分成无限小的单元分配给各队列。
然而在实际系统中，调度器每一时刻只能为一个队列提供服务，而且分组也不能分解成更小的单元。
WFQ 算法正是作为一种可实现的PFQ （packet fair queuing ）算法来模拟实现GPS 调度器的工作。
我们首先介绍一下理想的GPS 算法。
假设有N 个通路（session ），用1，2，…，N 表示。
他们分享GPS 服务器的输出链路。
我们用r i 表示分配给第i 个通路的最小带宽（速率），i ∈{1，2，…，N}。
网络中的拥塞控制与流量调度算法随着互联网的快速发展和广泛应用，网络拥塞成为了一个不可忽视的问题。
在高负载情况下，网络拥塞可能会导致网络性能下降、延迟增加甚至连接中断。
为了解决这个问题，网络中的拥塞控制和流量调度算法应运而生。
本文将探讨网络中的拥塞控制和流量调度算法的原理、应用和发展。
一、拥塞控制算法1.1 简介拥塞控制是一种调节网络流量的机制，通过监测网络负载情况并采取相应的措施来避免或减轻拥塞。
主要目标是防止网络发生拥塞，保证网络的稳定性和可靠性。
1.2 原理拥塞控制算法基于TCP协议，通过监测网络中的数据包丢失情况和延迟情况来判断拥塞程度，然后采取相应的措施来调整流量。
1.3 常用算法- AIMD(Additive Increase Multiplicative Decrease)算法AIMD算法通过线性增大拥塞窗口来增加发送速率，而在发生拥塞时将拥塞窗口减半，从而实现拥塞控制。
- 慢启动算法慢启动算法在初始阶段以指数方式增加拥塞窗口，然后逐渐切换到线性增长。
当发生拥塞时，拥塞窗口会减半。
- 基于队列的拥塞控制算法这种算法通过监测网络中的队列长度来判断网络的拥塞程度，然后动态调整发送速率或阻塞部分流量，以实现拥塞控制。
二、流量调度算法2.1 简介流量调度算法用于根据不同的需求和优先级来调度网络中的数据流量，以实现资源分配的公平性和高效性。
2.2 原理流量调度算法根据各个数据流的优先级和服务需求，动态地调整网络中的带宽分配和流量转发策略，以实现流量的均衡分配和高效处理。
2.3 常用算法- 公平队列算法公平队列算法根据每个流的优先级和需求，为每个流分配相应的服务质量，并采取公平的调度策略，以实现公平的带宽分配。
- 加权公平队列算法加权公平队列算法引入了流的权重参数，使得优先级高的流可以获得更多的带宽资源，从而实现不同流的差异化服务。
- 优先级队列算法优先级队列算法根据各个流的优先级将流量分成多个队列，然后按队列的优先级进行调度，以实现流量的有序处理。
QOS各种队列详解(FIFO,FQ,CBWFQ,PQ) 对于拥塞管理，一般采用队列技术，使用一个队列算法对流量进行分类，之后用某种优先级别算法将这些流量发送出去。
每种队列算法都是用以解决特定的网络流量问题，并对带宽资源的分配、延迟、抖动等有着十分重要的影响。
这里介绍几种常用的队列调度机制。
1. FIFO（先入先出队列，First In First Out Queuing）图9 先入先出队列示意图如上图所示，FIFO按照时间到达的先后决定分组的转发次序。
用户的业务流在某个设备能够获得的资源取决于分组的到达时机及当时的负载情况。
Best-Effort报文转发方式采用的就是FIFO的排队策略。
如果设备的每个端口只有一个基于FIFO的输入或输出队列，那么恶性的应用可能会占用所有的网络资源，严重影响关键业务数据的传送。
每个队列内部报文的发送（次序）关系缺省是FIFO。
2. PQ（优先队列，Priority Queuing）图10 优先队列示意图PQ队列是针对关键业务应用设计的。
关键业务有一个重要的特点，即在拥塞发生时要求优先获得服务以减小响应的延迟。
PQ可以根据网络协议（比如IP，IPX）、数据流入接口、报文长短、源地址/目的地址等灵活地指定优先次序。
优先队列将报文分成4类，分别为高优先队列（top）、中优先队列（middle）、正常优先队列（normal）和低优先队列（bottom），它们的优先级依次降低。
缺省情况下，数据流进入normal队列。
在队列调度时，PQ严格按照优先级从高到低的次序，优先发送较高优先级队列中的分组，当较高优先级队列为空时，再发送较低优先级队列中的分组。
这样，将关键业务的分组放入较高优先级的队列，将非关键业务的分组放入较低优先级的队列，可以保证关键业务的分组被优先传送，非关键业务的分组在处理关键业务数据的空闲间隙被传送。
PQ的缺点是如果较高优先级队列中长时间有分组存在，那么低优先级队列中的报文将一直得不到服务。
加权轮训队列调度算法加权轮询队列调度算法是一种用于网络设备上多个任务调度的算法。
在传统的轮询调度算法中，所有任务被按照相同的权重进行调度，因此每个任务被分配的时间片是相等的。
但是在实际应用中，不同的任务可能具有不同的优先级和重要性，因此需要使用一种更为灵活的调度算法。
加权轮询队列调度算法将所有的任务分为几个队列，并为每个队列分配一个权重。
在每个调度周期内，调度器会按照队列的权重依次调度任务，每个任务被轮询的时间片长度与其所处的队列的权重成正比。
例如，系统中有三个队列，其权重分别为3、2、1。
在每个调度周期内，调度器会首先调度队列1中的任务，每个任务被分配的时间片为10ms（假设一个调度周期为30ms）。
接下来调度队列2中的任务，每个任务被分配的时间片长度为20ms。
最后调度队列3中的任务，每个任务被分配的时间片长度为30ms。
这种调度算法的优点在于可以根据实际需要灵活地分配任务的时间片，更精细地控制任务的优先级。
同时，由于任务被分配的时间片长度与队列的权重成正比，因此可以根据任务的重要性和优先级来确定其所处的队列和权重，从而更好地实现资源的优化利用。
然而，加权轮询队列调度算法也存在一些缺点。
例如，由于任务被划分为多个队列，因此会出现任务被分配到不同队列的情况，对于一些需要连续执行的任务来说，可能会造成执行效率的降低。
此外，由于任务的划分和调度需要消耗一定的资源，因此对于一些资源紧张的系统来说，可能不太适合采用这种调度算法。
综上所述，加权轮询队列调度算法是一种在特定场景下能够更为精细地控制任务优先级和时间片分配的调度算法，但它也存在一些局限性和缺陷，需要根据实际应用情况进行综合考虑。
网络速率控制技术中的排队策略优化方法随着互联网的快速发展，网络通信扮演着人们日常生活中不可或缺的角色。
然而，在网络中传输数据的过程中，由于网络带宽有限和网络拥堵等原因，常常会导致网络速度的下降和延迟。
为了解决这一问题，研究者们提出了各种网络速率控制技术，其中排队策略优化方法扮演着关键角色。
一、排队策略的重要性在网络传输中，数据包可能会在传输的过程中积压在网络节点中，等待进一步的处理。
这时，排队策略的优化就显得非常重要。
合理的排队策略可以避免网络拥堵，提高网络吞吐量，并降低延迟。
二、基本的排队策略最基本的排队策略为先进先出（FIFO）策略。
这种策略是按照数据包进入队列的顺序进行处理，可以确保数据包的公平性。
然而，在高负载情况下，FIFO策略存在明显的缺点，一旦网络中出现拥堵，数据包的延迟会急剧增加。
三、优化方法一：加权公平队列（WFQ）为了提高网络的公平性和吞吐量，人们提出了加权公平队列（WFQ）策略。
在WFQ策略中，每个数据包都会被分配一个权重值，高权重的数据包会被优先发送。
这样可以避免某些数据流占用过多的带宽资源，提高了网络的公平性和性能。
四、优化方法二：公平队列调度（Fair Queueing）公平队列调度（Fair Queueing）策略是一种比较先进的排队策略。
在这种策略中，不仅基于FIFO原则，还根据数据包的大小和优先级进行调度。
公平队列调度可以避免长数据包拖累整个网络的传输速度，提高网络的实时性和吞吐量。
五、优化方法三：主动队列管理（Active Queue Management）在传统的排队策略中，当网络拥堵时，数据包会被不断积压在队列中，导致网络延迟的增加。
而主动队列管理（Active Queue Management）策略则尝试在队列溢出之前即时地丢弃一些数据包。
其中，最著名的算法是随机早期检测（Random Early Detection，RED）算法。
该算法可以根据队列的长度适时丢弃部分数据包，从而有效降低网络的延迟和拥堵。
加权公平队列（weightedfairqueuing）wfq是cisco⾸要的队列技术，它⼀种基于流(flow)的队列算法，做两件事：它与留交互式流量给队列的前⾯来减少响应时间，另外还公平地在剩余的⾼带宽流之间的共享(share)带宽.⼀个流(flow)可以理解为⼀个从源到⽬的的会话。
它是配置在接⼝上的。
配置举例：要求-丢弃门限为100消息。
500个动态队列。
20 rsvp队列。
interface serial 0fair-queue 100 500 20 //这3个数字分别为：丢弃门限，默认为64。
动态队列默认为256。
rsvp队列默认为0 基于类的加权公平队列(class-based weighted fair queuing) ⽐wfq更加强⼤，流量(traffic)由⽤户定义的类(class)进⾏排队。
⼀个队列包留给每个类。
队列⽤于为丢弃或者wred(加权随机早期检测)。
其他未分类的流量是基于流的。
配置cbwfq(1)步骤1-定义流量分类全局配置模式下：class-map uptmd //class-map的uptmd是名字。
class-map match-all uptmd //匹配“与”的关系。
class-map match-any uptmd //匹配“或”的关系。
class-map match-any uptmd match ? //在这打个问号可以得到帮助信息。
就是可选择匹配的内容access-group 访问控制列表组any任何所有。
class-map 某个class mapcos ieee802.1q/isl 的服务类别(class of service)/优先级别值。
destination-address ⽬的mac地址。
input-interface 选择⼀个输⼊接⼝进⾏匹配。
ip 指定 ip，具体选项可以继续定义.mpls 多协议标签交换指定的值not 否定这个匹配结果protocol 协议qos-group qos组source-address 源mac地址。
路由器流控技巧路由器作为网络通信的核心设备，扮演着至关重要的角色。
在网络通信中，路由器流控技巧是确保网络运行高效稳定的关键。
本文将介绍一些路由器流控技巧，帮助读者更好地管理和优化网络流量。
一、流控概述网络流量的正常传输离不开流控技巧的应用。
流控技巧通过合理分配和控制网络流量，提高网络性能、保证服务质量、降低网络拥堵等问题。
因此，熟练掌握流控技巧对于网络管理员至关重要。
二、识别和分类数据流要实施有效的流控技巧，首先需要对数据流进行识别和分类。
路由器通常根据数据包中的源IP地址、目的IP地址、端口号等信息对数据流进行分类。
通过识别和分类，可以更准确地应用流控策略，提高网络性能。
三、流量调度策略1. 公平队列调度算法（Fair Queueing）公平队列调度算法可以在多个数据流之间实现公平的带宽共享。
它通过计算每个数据流的最小带宽需求，根据每个流的需求按照一定规则分配带宽资源。
这种调度策略可以避免某个数据流过分占用带宽，保证整体网络流量的公平性。
2. 优先队列调度算法（Priority Queueing）优先队列调度算法是根据数据流的优先级来决定带宽分配的策略。
优先级高的数据流将获得更多的带宽资源，优先处理。
这种调度策略适用于一些对延迟要求较高的应用场景，如实时语音、视频会议等。
3. 加权公平队列调度算法（Weighted Fair Queueing）加权公平队列调度算法是对公平队列调度算法的改进。
在多个数据流之间根据流的优先级进行带宽分配时，加权公平队列调度算法可以根据具体应用需求，为不同数据流设置不同的权重。
通过合理的权重设置，可以更灵活地满足不同应用的带宽需求。
四、拥塞控制拥塞是网络流量过大导致网络性能下降的一种情况。
要避免拥塞，路由器可以通过拥塞控制机制来限制流量的输入，防止网络负载过大。
1. 慢启动慢启动是一种常见的拥塞控制机制。
当检测到网络出现拥塞时，慢启动机制会逐渐增加数据流的发送速率，直到达到一个网络可以正常处理的速率为止。
加权公平排队wfq算法例题
加权公平排队（Weighted Fair Queuing，WFQ）算法是一种流
量调度算法，它可以根据流量的权重来实现对流量的公平分配。
在WFQ算法中，每个数据流都被分配一个权重，数据包根据其流的权
重来进行排队和调度。
下面我将通过一个例题来解释WFQ算法的工
作原理。
假设有3个数据流A、B、C，它们的权重分别为2、3、1。
现在
有一批数据包到达路由器进行排队和调度。
根据WFQ算法，数据包
将根据其流的权重来进行排队和调度，具体步骤如下：
1. 首先，路由器会根据数据包的到达顺序将它们分配到相应的
队列中，每个队列对应一个数据流。
2. 接下来，路由器会根据每个队列中数据包的权重来进行调度。
假设在某个时刻，队列A中有4个数据包，队列B中有3个数据包，队列C中有2个数据包。
那么在这个时刻，路由器会先调度队列B
中的一个数据包，然后调度队列A中的两个数据包，最后调度队列
C中的一个数据包。
3. 调度完成后，路由器会继续监测各个队列中的数据包情况，
并根据权重进行下一轮的调度。
通过上述例题，我们可以看到，根据WFQ算法，不同数据流的
数据包可以按照其权重进行公平调度，从而实现了对流量的公平分配。
除了上述例题，WFQ算法还涉及到细节问题，比如如何处理队
列溢出、如何处理低优先级流量等，这些细节问题也是实际中需要
考虑的。
希望这个例题可以帮助你更好地理解WFQ算法的工作原理。
2008年2月February 2008—28—计 算 机 工 程Computer Engineering 第34卷 第4期Vol.34 No.4 ·博士论文·文章编号：1000—3428(2008)04—0028—03文献标识码：A中图分类号：TP391一种新的加权公平队列调度算法尹德斌，谢剑英(上海交通大学自动化系，上海 200240)摘 要：传统公平队列调度算法(WFQ 、WRR 等)普遍存在基于数据包的权重参数计算问题，由此产生的高复杂度使其难以获得广泛应用。
该文提出一种新的加权公平队列调度算法，使用服务概率和随机数实现加权公平调度，显著降低了算法的复杂度。
同时使用自适应服务概率计算解决了数据包变长度带来的不公平性。
通过队列管理技术有效地提高了交换机的缓冲区利用率，并减小了排队延迟抖动。
仿真结果证明了算法的有效性和实用性。
关键词: 队列调度；加权公平排队；自适应队列管理；分组交换网络New Weighted Fair Queue Scheduling AlgorithmYIN De-bin, XIE Jian-ying(Department of Automation, Shanghai Jiaotong University, Shanghai 200240)【Abstract 】Traditional weighted fair queue algorithms have the main drawback: the calculation of the weight parameters according to each packet.The paper proposes a new weighted fair queueing algorithm(SPFQ), which uses service probability to schedule packets and a random number to decide which packet to be served next. In addition, a novel adaptive service probability parameter calculation method is used to solve the unfair problem induced by the variable packet length and an adaptive queue management technology to improve the utilization of the server's queue buffer and reduce the delay burstiness. Simulation results demonstrate the validity and practicability of SPFQ.【Key words 】queue scheduling; weighted fair queueing; adaptive queue management; packet switching network1 概述队列调度是当前互联网技术领域的一个研究热点。
WRR：（Weighted Round Robin，简称WRR）加权循环调度算法。
加权循环(WRR)所有业务队列服务，并且将优先权分配给较高优先级队列。
在大多数情况下，相对低优先级，WRR将首先处理高优先级，但是当高优先级业务很多时，较低优先级的业务并没有被完全阻塞。
加权循环调度算法WRR（Weighted Round Robin）是一种较强的队列调度算法,它能够有效地区分队列中所有的业务。
对于所有的业务流在排队等待调度的队列,WRR是根据每个队列配置的权值与所有的业务流在排队等待调度的队列的权值总和的比来平等地分配带宽。
因此，在处理多个用户的高优先等级的业务时,WRR 确保每个用户都不会过度地占用网络带宽。
而且WRR算法容易在硬件中实现。
所以WRR算法能够实现带宽分享的公平性、恶意流的隔离能力和带宽的利用率等性能指标
工作原理：
WRR队列调度将每个端口分为多个输出队列，队列之间轮流调度，保证每个队列都得到一定的服务时间，WRR可为每个队列配置一个加权值（依次为 w3、w2、w1、w0），加权值表示获取资源的比重。
如一个100M的端口，配置它的WRR队列调度算法的加权值为50、30、10、10（依次对应 w3、w2、w1、w0），这样可以保证最低优先级队列至少获得10Mbit/s带宽，避免了采用PQ调度时低优先级队列中的报文可能长时间得不到服务的缺点。
WRR 队列还有一个优点是，虽然多个队列的调度是轮循进行的，但对每个队列不是固定地分配服务时间片—如果某个队列为空，那么马上换到下一个队列调度，这样带宽资源可以得到充分的利用。
2008年2月February 2008—28—计 算 机 工 程Computer Engineering 第34卷 第4期Vol.34 No.4 ·博士论文·文章编号：1000—3428(2008)04—0028—03文献标识码：A中图分类号：TP391一种新的加权公平队列调度算法尹德斌，谢剑英(上海交通大学自动化系，上海 200240)摘 要：传统公平队列调度算法(WFQ 、WRR 等)普遍存在基于数据包的权重参数计算问题，由此产生的高复杂度使其难以获得广泛应用。
该文提出一种新的加权公平队列调度算法，使用服务概率和随机数实现加权公平调度，显著降低了算法的复杂度。
同时使用自适应服务概率计算解决了数据包变长度带来的不公平性。
通过队列管理技术有效地提高了交换机的缓冲区利用率，并减小了排队延迟抖动。
仿真结果证明了算法的有效性和实用性。
关键词: 队列调度；加权公平排队；自适应队列管理；分组交换网络New Weighted Fair Queue Scheduling AlgorithmYIN De-bin, XIE Jian-ying(Department of Automation, Shanghai Jiaotong University, Shanghai 200240)【Abstract 】Traditional weighted fair queue algorithms have the main drawback: the calculation of the weight parameters according to each packet.The paper proposes a new weighted fair queueing algorithm(SPFQ), which uses service probability to schedule packets and a random number to decide which packet to be served next. In addition, a novel adaptive service probability parameter calculation method is used to solve the unfair problem induced by the variable packet length and an adaptive queue management technology to improve the utilization of the server's queue buffer and reduce the delay burstiness. Simulation results demonstrate the validity and practicability of SPFQ.【Key words 】queue scheduling; weighted fair queueing; adaptive queue management; packet switching network1 概述队列调度是当前互联网技术领域的一个研究热点。
其中，加权公平队列调度算法由于能够根据各业务流的权重进行区分服务而受到广大研究者的广泛关注[1-9]。
其中最著名的是加权公平WFQ [1]和加权轮询WRR [6]两类算法。
WFQ 及其改进算法[3,5,7]都基于通用处理机共享模型[2]，使用虚时间(virtual time)进行数据包转发。
WFQ 算法在业务流受漏斗约束的情况下可以提供精确的带宽保证和最大时延上限，并且数据包的转发不受其他业务流特性影响。
但是它的计算复杂度太高。
WRR [2,6]是另一类复杂度相对较低的常用加权队列调度算法；各业务流在一次轮询中所允许发送的数据包个数由队列权重决定。
DRR [4]引入了差额计数器(dificit conter)，记录由数据包长度不同引起的服务量差。
轮询类算法复杂度较低，但无法提供确定的带宽保证和时延上限。
国内的研究者近年来也提出了许多队列调度算法。
文 献[8]针对SS 和BF 两种业务流，提出了一种对数自适应调度算法，但该算法对类内各业务流之间如何调度并没有说明，且不能提供公平服务和隔离特性。
文献[9]提出了一种用于区分服务网络的虚时钟核心无状态队列调度算法，各数据包自身携带虚时钟状态信息，中心服务器根据虚时钟进行转发，但需要根据虚时钟将入队列数据包插入到转发队列中，这无疑是一项沉重的计算负担。
另外，该算法并未考虑虚时钟清零问题。
本文提出了一种新的加权队列调度算法SPFQ 。
由于采用了指数移动平均算法和阀值触发的平均数据包长度更新，使得服务概率计算频度大大降低，从而显著降低了算法的复杂度。
2 SPFQ 队列调度算法2.1 SPFQ 的基本原理SPFQ 算法依据各业务流的平均数据包长度将它们的权重转换成归一化服务概率，通过该参数实现加权服务。
为了降低算法的复杂度，系统采用事件触发方式计算队列的平均长度。
在算法实现中，使用单独模块计算服务概率，以减轻调度器的负荷。
2.2 SPFQ 的结构数据包分类器图1 SPFQ 算法结构基金项目：国家自然科学基金资助项目(60572157)；国家“863”计划基金资助项目(2003AA123310)作者简介：尹德斌(1978－)，男，博士，主研方向：包交换网络的队列调度和管理；谢剑英，教授、博士生导师收稿日期：2007-03-10 E-mail ：yin_db@SPFQ 算法结构主要包括：(1)数据包分类器；(2)队列管理器；(3)SPFQ 调度器；(4)数据包长度观察器；(5)自适应服务概率计算器；(6)随机数发生器。
随机数发生器生成一个在区间[]0,1内均匀分布的随机数。
为了消除数据包长度变化时的服务量差异问题(参见4.2节)，在调度器输出端设计了数据包长度反馈环节，下面分别介绍其余4个模块。
(1)RN 2.3 队列管理器SPFQ 的队列管理器为各业务流维护一个独立的缓冲区;根据各业务流的时延和速率要求，动态调整其缓冲区长度，最优化缓冲区利用。
对于具有带宽、时延要求的数据流，定义队列缓冲区长度满足下式：max i i bl bl ≤ (1) max min max ()max{, }i j i i kk AQ N w BLbl bw w τ∈×=×∑ (2)其中，是要求的最小带宽；是最大时延；min bw max i τBL 是缓冲区总长度；()AQ N 为当前活动队列集。
对于没有明确QoS 要求的数据流，基于“尽力而为”服务要求，并考虑对其他业务流的保护和网络拥塞控制的要求，定义队列缓冲区长度满足下式：max j j bl bl ≤ (3) max ()jjkk AQ N w bl BL w ∈=∑× (4)其中，j w 是队列权重。
服务器使用统一缓冲区管理策略，即各业务流共享同一空闲缓冲区。
当有数据包到达时，如果缓冲区有足够的空闲空间，验证式(1)或式(3)，满足则分配缓冲区，数据包入队列；否则丢包。
2.4 数据包长度观测器长度观测器监测新业务流，根据长度反馈和设定阀值更新各队列的平均数据包长度；自适应服务概率计算器根据数据包平均长度和权重参数动态调整各业务流的服务概率，以消除数据包变长度引起的不公平性。
观测器从数据包长度反馈环节接收当前被转发数据包的长度，用于更新相应的平均数据包长度。
为了降低计算复杂度，SPFQ 使用指数移动平均(Exponential Moving Average, EWMA)来估计数据包平均长度curr 1jˆˆ(1)j l l µµ+=×+−×jl (5)其中，ˆj l 是当前数据包平均长度估计值；1ˆj l +是更新后的估计值；是当前被转发数据包的长度；curr j l µ是权重因子，本文取7/8。
单位时间内有大量数据包离开服务器，如果对平均长度进行实时更新则计算量太大。
因此，SPFQ 使用下列平均长度更新算式1ˆˆ, ˆ, j j j j j j j l l l l l l l l l νν+⎧−×⎪=⎨−<×⎪⎩≥j j(6) 其中，v 是阈值因子，本文取0.1，它决定了更新精度。
2.5 自适应服务概率计算器考虑如图1所示的单服务器系统，假设有N 个队列通过该节点转发数据包，其中第个队列的服务权重为，则如果各队列数据包长度相同，则每个队列的服务概率定义为i (1)i w i N ≤≤()()() 0 i jj AQ N i i AQ N i AQ N w w p ∈∉∈⎧⎪=⎨⎪⎩∑ (7) 对于变长度数据包网络，式(7)修正为()()() 0 i ij i j AQ N j i AQ N i AQ N w l w p l ∈∉∈⎧⎪⎪⎪=⎨⎪⎪⎪⎩∑ (8) 其中，i l 是数据包长度观测器给出的平均长度。
当i l 发生变化时，长度观测器通知服务概率计算器重新计算各业务流的服务概率。
服务概率计算器按下式维护一个服务概率表供调度器使用(1) 1 2 1 i i i i p i P p i P i N −=⎧⎪N +<=⎨⎪=⎩≤ (9)这样为闭区间内的递增序列。
(1)i P i N ≤≤1[,1]p 2.6 SPFQ 队列调度器SPFQ 算法是非抢占的，它依据各队列的服务概率进行数据包转发。
同一队列中的数据包按先来先服务(FCFS)原则转发。
调度器基本原理是：在一次转发中，调度器从随机数发生器中获取随机数，查询服务概率表，找到满足下式的(1)RN i P (1)(1)i P RN −i P <≤ (10) 则队列i 的头数据包被转发。
当所有服务队列都为空时服务器进入空闲状态(服务保持)。
3 SPFQ 算法复杂度分析分析图1中SPFQ 算法的结构，长度观测器和自适应服务概率计算器以及随机数发生器都可用单独模块实现；它们只和调度器交换数据，不增加调度器的计算负荷。
与其他调度算法相比，SPFQ 增加了一个队列管理器。
对于一个实际运行的路由器，这是必不可少的。
这样算法的主要改进集中在SPFQ 队列调度器。
队列调度器的任务是将随机数与按照式(9)计算得到的服务概率表中的数据相比较，找到符合式(10)式的队列，然后转发它的头数据包。
这样，调度器的实现便是一个线性表查询问题。
由于服务概率表单调递增，因此可以使用二分查找法。
唯一不同的是查找目标不是和随机数相等，而是符合式(10)。
