基于网络处理器平台实现的综合队列管理方法

摘要

基于网络处理器平台实现的队列综合管理方法属于队列管理和分组调度技术领域，其特征在于：它是在Intel公司的Intel IXP 2400网络处理器上实现的；它在分组进入队列时，采用平均分组丢失率比例控制，确保分组丢失速率和分组到达平均速率之比为常数；在分组出队列时，采取平均排队延时比例控制方法，确保各队列中分组平均排队时延之比为常数。它降低了丢失率比例缓冲管理和平均时延分组调度方法的复杂度，而且根据到达分组的丢失行为来动态调整阈值，保证获得预期的相对公平性，提高了缓冲资源的利用率，他的转发性能达到了千兆高速。

说明书

技术领域

缓冲管理和分组调度领域。

背景技术

在比例区分服务(proportional differentiation services)模型中，任意两个服务类在每一跳(per-hop)所获得的服务满足确定的比例，比例参数由网络管理者设定而且与类的负载无关。即对于任意1＜i，j＜N，有q_i(t，t+τ)/q_j(t，t+τ)＝c_i/c_j其中q_i(t，t+τ)为数据类i在时间段[t，t+τ]内所获得的服务，c₁＜c₂＜…＜c_N为网络管理者设定的比例参数。PLR缓冲管理(Proportional LossRate Buffer Management)方法和PAD分组调度(Proportional Average Delay Packet Scheduling)方法都属于比例区分服务。

q_i(t，t+τ)使用丢失率作为标准，则衍生出PLR缓冲管理方法。它是缓冲管理方法的一种，针对比例区分服务模型设计的方法，其控制目标是使得任意两个服务类的分组丢失率保持在恒定的比例。它的方法复杂度是O(logN)。

q_i(t，t+τ)使用时延作为标准，则衍生出PLR缓冲管理方法。它是分组调度方法的一种，针对比例区分服务模型设计的方法，其控制目标是使得任意两个服务类的平均排队时延保持在恒定的比例。它的方法复杂度是O(logN)。

PLR缓冲管理方法和PAD分组调度方法存在的问题：这两种法属于基于动态优先级方法，基本思想总结如下：为每个队列计算一个索引值(动态优先级)，每次选取具有最大或最小索引值的队列进行调度。因此，查找/排序是动态优先级方法的另一个重要的基本操作，并具有O(logN)的复杂度，其中N代表队列数量。一般来讲，索引值存储在片外存储器(比如SRAM)中，或片内存储器(比如Scratchpad，如果其容量足够大的话)中。但不管怎样，都需要大量的内存访问操作。而内存访问通常是一个性能瓶颈，因此对于大多数方法而言，O(logN)的复杂度会使得方法实现的效率非常低。PLR缓冲管理方法和PAD分组调度方法不适用于高速网络设备。

本发明研究并实现了一种新的RR-PLR缓冲管理方法和WRR-PAD分组调度方法，极大地提高了缓冲管理和分组调度的速度。

发明内容

本发明的目的是：设计一个适应网络处理器的，低时间复杂度的，遵循比例区分的服务模型的队列管理方法。在分组入队列时实现丢失率控制的缓冲管理方法，在分组出队列时实现时延控制的分组调度方法，分别实现平均分组丢失率和平均排队时延的成比例控制。名词解释如下：

1)服务质量(Quality of Service)控制

服务质量(QoS)控制是一系列控制机制的总称，包括诸如队列缓冲资源管理、分组调度、QoS路由等控制，旨在为使用网络的用户提供端到端的，包括带宽、延迟、分组丢失率等在内的性能保证。现有的Internet网络只能提供一种“尽力做好”(best-effort)的服务，无法支撑越来越多的网上实时交互应用。因此，服务质量(QoS)控制问题应运而生，成为下一代网络需要解决的关键技术。

2)缓冲管理(Buffer Management)

缓冲管理研究的主要内容是缓冲区如何分配和当缓冲区占用率到达一定程度时如何选择分组进行丢弃，所影响的性能参数主要是分组丢失率。

3)分组调度(Packet Scheduling)

分组调度则是指按照一定的规则来决定从多个等待队列中选择哪个分组进行发送，它影响的主要性能参数包括带宽分配、时延和时延抖动。

4)网络处理器(Network Processor)平台

网络处理器是介于通用处理器和专用处理器(ASIC)芯片之间的一种可编程芯片，网络处理器采用了如下技术以适应网络数据处理：

(1)多内核结构，使用多线程或者并行处理两种机制组织；

(2)优化的内存管理和DMA单元；

(3)优化的运算逻辑单元ALU；

(4)网络专用的协处理器(co-processors)；

(5)硬件多线程技术。

INTEL IXP 2400是Intel公司在一款高性能的网络处理器，我们基于它来实现本综合队列管理方法。

它的特点如下：

●本方法改进了PLR缓冲管理方法和PAD分组调度方法，将方法复杂度由原有的O(logN)降低为O(1)；

●本方法使用轮循机制，消除了除法运算以及排序操作，适于网络处理器的实现；

●RR-PLR和WRR-PAD方法根据到达分组的丢失行为来动态调整阈值，可以保证获得预期的相对公平性能，并能一定程度上适应网络流量的变化，提高系统缓冲资源的利用率；

●性能仿真和基于Intel IXP2400网络处理器的性能实测结果表明：综合队列管理方法的转发性能达到了千兆线速。

基于网络处理器平台实现的综合队列管理方法，其特征在于，所述的综合队列管理方法是在一款Intel公司生产的Intel IXP 2400网络处理器上实现的，所述方法分别把网络分组接受模块、网络分组发送模块、RR-PLR即轮循-比例丢失率缓冲管理程序、WRR-PAD即加权轮循-比例平均延时分组调度程序，各自分别配置在网络处理器的1个微引擎上，即分别分配在第0，第7，第1和第2个微引擎上；而把IPv4协议处理程序配置在所述网络处理器的4个微引擎上，即分配在第3，4，5，6个微引擎上；

当分组进入队列时，采用平均分组丢失率比例控制，该控制方法依次含有一下步骤：

步骤1_A：初始化每个队列的分组计数器：

设队列m分配的计数器C_m＝k_m·δ_m，m＝0，1，…，n-1；指针i＝0；

其中，k_m为预先确定的参数，它是各队列的分组平均到达速率的比：

a₀(t)/a₁(t)/…/a_n-1(t)＝k₀/k₁/…/k_n-1；a_m(t)为队列m在时间段[0，t]内到达的分组数；

δ_m为预先确定的参数，它是各个队列分组丢失率的比：L₀/L₁/…/L_n-1＝δ₀/δ₁/…/δ_n-1，L_m为队列m的平均分组丢失率；

所述L_m＝d_m(t)/a_m(t)＝d_m(t)/(λ_m·t)；

其中，d_m(t)为为队列m在时间段[0，t]内丢弃的分组数；

λ_m为队列m的分组平均到达速率，在程序中以k_m的形式表现出来；

k_mδ_m为队列m的丢弃分组数；各个队列的丢弃的分组数保持比例，即保持(k₀·δ₀)/(k₁·δ₁)/…/(k_n-1·δ_n-1)的设定比例；

步骤2_A：等待，一直到有新的分组p到达，记该分组属于队列t，为该分组打上到达队列的时间戳T_入队列，转步骤3；否，转步骤2；

步骤3_A：判断各个队列的分组长度之和是否小于或等于缓存可以存放分组总个数：

若是，将分组p放入相应的队列t，对于该分组的处理结束；

若否，转步骤4_A；

步骤4_A：判断队列i的分组计数器C_i是否大于零，且队列非空：

若是，从队列i中丢弃一个分组；使分组计数器C_i＝C_i-1；i＝i+1；将分组p放入相应的队列t，对于该分组的处理结束；重新转到步骤2_A；

若否，判断i是否小于n：若是，i＝i+1；转入步骤4_A；若否，对于j＝0，1，…，n-1，使队列j分组计数器的做C_j＝C_j+k_j·δ_j；指针i＝0；转到步骤4_A；

当分组出队列时，采用平均排队时延的比例控制方法，即使得各个队列中各分组的时延满足一下比例关系：

$>>>\Sigma >>j>=>0>>>>s>0>>>(>t>)>>>sup>>d>0>jsup>>/>>\Sigma >>j>=>0>>>>s>1>>>(>t>)>>>sup>>d>1>jsup>>/>·>·>·>/>>\Sigma >>j>=>0>>>>s>>n>->1>>>>(>t>)>>>sup>>d>>n>->1>>jsup>>/>=>>(>>\xi >0>>·>>w>0>>)>>/>>(>>\xi >1>>·>>w>1>>)>>/>·>·>·>/>>(>>\xi >>n>->1>>>·>>w>>n>->1>>>)>>;>>>$

其中，s_i(t)为队列i在时间段[0，t]内发送的分组数，i＝0，1，…，n-1；

d_i^j为队列i的中第j个分组的延时；

队列i的平均排队时延为 $>>>D>i>>=>>>>\Sigma >>j>=>0>>>>s>i>>>(>t>)>>>sup>>d>i>jsup>>>>>s>i>>>(>t>)>>>>,>>>各个队列平均排队时延的比保持一致，即D$₀/D₁/…/D_n-1＝ξ₀/ξ₁/…/ξ_n-1；ξ_i为预先确定的参数；

各个队列发送的分组数满足以下比例关系：s₀(t)/s₁(t)/…/s_n-1(t)＝w₀/w₁/…/w_n-1，w_i为预先确定的参数；

以上所述的平均排队时延的比例控制方法采用轮循一次含有以下步骤：

步骤1_B：给每个队列分配3个计数器，队列i的3个计数器分别记为：

CS_i为记录需要发送的分组数量的计数器；

CD_i为记录需要经历的排队时延之和的计数器；

CO_i为根据队列平均排队时延的变化情况提前或推迟其队列i分组的发送的辅助计数器；

CO_i＞0表示队列分组被提前发送，轮循次数被“透支”；CO_i＜0表示队列分组被推迟发送，

轮循次数有“盈余”；CO_i＝0表示正常情况；

φ_i为队列i发送w_i个分组的延时之和，φ_i＝ξ_i·w_i；

初始化CS_i＝w_i，CD_i＝φ_i，CO_i＝0；

初始化域值thd_i＝φ_i；

指针i＝0；

步骤2_B：读取CS_i，CO_i，CD_i三个计数器；

根据下表判断该情况是否需要调度：若是，转步骤3_B；若否，转步骤4_B；

根据以下CS_i，CO_i，CD_i三个寄存器的8种不同情况，判断是否调度：

情况a，当CS_i＝0，CO_i≥0，CD_i-d＜0时：

调度；并改变寄存器，使得CS_i＝CS_i+w_i，CD_i＝CD_i+φ_i，CO_i＝CO_i+1；

情况b，当CS_i＝0，CO_i≥0，CD_i-d≥0时：

不调度；

情况c，当CS_i＝0，CO_i＜0，CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))≥thd_i时：

不调度；

情况d，当CS_i＝0，CO_i≥0，CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))＜thd_i时：

调度；并改变寄存器，使得CS_i＝CS_i+w_i，CD_i＝CD_i+φ_i，CO_i＝CO_i+1；

情况e，当CS_i＞0，CO_i＜0，CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))≥thd_i时：

不调度；

情况f，当CS_i＞0，CO_i＜0，CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))＜thd_i时：

调度；并改变寄存器，使得CS_i＝CS_i-1，CD_i＝CD_i-d；

情况g，当CS_i＞0，CO_i≥0，CD_i-d＜0时：

调度；并改变寄存器，使得CS_i＝CS_i-1，CD_i＝CD_i-d；

情况h，当CS_i＞0，CO_i≥0，CD_i-d≥0时：

不调度；

其中，d为分组在队列中的延时，d＝T_出队列-T_入队列；对于条件D和D的意义解释如下：条件D和D是在出现在条件B之下需要进一步判断的，这种情况下，表明该队列的分组曾被推迟发送，其轮循次数尚有“盈余”，因此需要判断“盈余”被“补足”之后的CD_i值；(-CO_i·φ_i)为“盈余”轮数所对应的总延时数；(CS_i+(-CO_i·w_i))为总共“盈余”的分组数减去这轮已经发出的分组数；CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))即按照d的延时发送，“盈余”的总延时能不能被消耗的足够多；

步骤3_B-1：根据上述不同的情况，改变计数器的值；

步骤3_B-2：从队列i中取出一个分组；从RR-PLR模块取得T_入队列；取当前时间得到分组的出队列时间T_出队列；

计算这个分组在队列中的延时d＝T_出队列-T_入队列，并发送；

步骤3_B-3：使CS_i＝CS_i-1；CD_i＝CD_i-d；i＝i+1；转步骤2_B；

步骤4_B：i＝i+1；

判断CS_i＝0并且CD_i≤0：若是，转步骤5_B；若否，转步骤6_B；

步骤5_B：CS_i＝CS_i+w_i；CD_i＝CD_i+w_i·ξ_i；转步骤2_B；

步骤6_B：CO_i＝CO_i-1；转步骤2_B。

我们在Intel IXP2400网络处理器上实现了RR-PLR缓冲管理方法和WRR-PAD分组调度方法，并对方法性能进行了测试。

测试参数设置如下：输入的数据流共分为八个类。其中第一类到第四类的丢失率和时延的比值均设置为1/2/3/4，第五类到第八类的丢失率和时延比值设置均为2/2/3/4。我们测试的是重负载情况下系统的性能，总的输入速率为2Gbps，分组设置为最小以太网分组，分组大小为64Byte，即总的输入速率为4Mpps，八个服务类分组到达的速率相等，均为256Mbps(即0.5Mpps)。

RR-PLR和WRR-PAD方法在Intel IXP2400网络处理器上协同工作的性能如图5至图8所示。可见，方法能够在适当的参数配置下对平均分组丢失率和平均排队时延进行成比例区分控制。在测试平台运行稳定之后，系统的总吞吐率达到了1.125483Gbps(即2.250966Mpps)，在实现成比例的区分服务的基础上达到了千兆线速转发。

附图说明

图1 Intel IXP 2400网络处理器结构图；

注：在图1中，ME表示微引擎(Micro Engine)；网络分组接受模块、网络分组发送模块、RR-PLR即轮循-比例丢失率缓冲管理程序、WRR-PAD即加权轮循-比例平均延时分组调度程序，各自分别配置在网络处理器的1个微引擎上，即分别分配在第0，第7，第1和第2个微引擎上，而把IPv4协议处理程序配置在所述网络处理器的4个微引擎上，即分配在第3，4，5，6个微引擎上。

图2综合队列管理方法的整体实现图；

图3 RR-PLR方法流程图；

图4 WRR-PAD方法流程图；

图5 RR-PLR方法丢失率曲线实施例1；

图6 RR-PLR方法丢失率曲线实施例2；

图7 WRR-PAD方法时延曲线实施例1；

图8 WRR-PAD方法时延曲线实施例2。

具体实施方式

网络处理器主要完成网络分组的接受、存储和转发功能。接收模块在接收到网络分组时，将其按RR-PLR缓冲管理方法策略存储于分组队列中；转发模块则从分组队列中，按WRR-PAD分组调度方法取出网络分组并转发。

RR-PLR方法是PLR方法针对网络处理器的近似方法，主要是通过消除原有方法中的除法、排序，降低计算复杂度。另外，RR-PLR只是把长期的平均丢失率比例作为控制目标，即只考虑了大时间尺度的情况。

在本方法中，我们的控制目标不是分组到达速率的绝对值和丢失虑的绝对值，而是不同队列之间的比例关系。

如果记队列i(i＝0，1，…，n-1)在时间段[0，t]内到达和丢弃的分组数分别为a_i(t)和d_i(t)；记队列i的分组平均到达速率为λ_i，则a_i(t)＝λ_i·t；队列i的平均分组丢失率为L_i＝d_i(t)/a_i(t)＝d_i(t)/(λ_i·t)。则RR-PLR方法保证大时间尺度下，各个队列分组丢失率的比L₀/L₁/…/L_n-1维持不变，记这个丢失率的比：L₀/L₁/…/L_n-1＝δ₀/δ₁/…/δ_n-1。

如果记各队列的分组平均到达速率的比：λ₀/λ₁/…/λ_n-1＝k₀/k₁/…/k_n-1，则本方法就是要确保：的关系。也即说保证各个队列的丢弃的分组数保持比例(k₀·δ₀)/(k₁·δ₁)/…/(k_n-1·δ_n-1)即可。k_i，δ_i(i＝0，1，…，n-1)是预先输入的参数(在方法初始化时已经确定)。

RR-PLR方法步骤如下：

步骤1：给每个队列分配一个分组计数器，队列i分配的计数器记为C_i；

初始化每个队列的分组计数器C_i＝k_i·δ_i；

指针i＝0。

步骤2：是否有新的分组p(记该分组属于队列t)到达？是，转步骤3；否，转步骤2。

步骤3：为该分组打上入队列时间戳T_入队列；

各个队列的分组长度之和＜缓存可以存放分组总个数？是，转步骤4；否，转步骤5。

步骤4：将分组p放入相应的队列t；(对于该分组的处理结束)转步骤2。

步骤5：C_i＞0？是，转步骤6；否，转步骤7。

步骤6：从队列i中丢弃一个分组；

C_i＝C_i-1；i＝i+1。

转步骤4。

步骤7：i＜n-1？是，转步骤8；否，转步骤9。

步骤8：i＝i+1；转步骤5。

步骤9：对于j＝0，1，…，n-1，做C_j＝C_j+k_j·δ_j；

指针i＝0；

转步骤5。

WRR-PAD方法是对WRR方法的改进，在保持原方法简单性的基础上，使得方法能提供时延比例保证，即改善了WRR方法的时延特性。与PAD方法相比(复杂度O(logN)，其中N为队列数)，主要的优点是不含除法操作，并具有O(1)的复杂度。

如果记队列i(i＝0，1，…，n-1)在时间段[0，t]内发送的分组数为s_i(t)，记队列i的中第j个分组的延时为d_i^j，则队列i的平均排队时延为 $>>>D>i>>=>>>>\Sigma >>j>=>0>>>>s>i>>>(>t>)>>>sup>>d>i>jsup>>>>>s>i>>>(>t>)>>>>.>>>WRR-PAD方法的控制目标是使得各个队列平均排队时延的比保持一致，即D$₀/D₁/…/D_n-1＝ξ₀/ξ₁/…/ξ_n-1。如果记队列发送的分组个数满足比例关系s₀(t)/s₁(t)/…/s_n-1(t)＝w₀/w₁/…/w_n-1，则方法控制时延之和，满足比例关系 $>>>\Sigma >>j>=>0>>>>s>0>>>(>t>)>>>sup>>d>0>jsup>>/>>\Sigma >>j>=>0>>>>s>1>>>(>t>)>>>sup>>d>1>jsup>>/>·>·>·>/>>\Sigma >>j>=>0>>>>s>>n>->1>>>>(>t>)>>>sup>>d>>n>->1>>jsup>>/>=>>(>>\xi >0>>·>>w>0>>)>>/>>(>>\xi >1>>·>>w>1>>)>>/>·>·>·>/>>(>>\xi >>n>->1>>>·>>w>>n>->1>>>)>>>>即可。$

为达到这个目标，轮循是一种可行的方法：为每个队列分配需要发送的分组数量配额、分组排队时延和的配额，维护两个相应的计数器(初始化为相应的配额)，并使得轮循时每个队列发送的分组数和经历的排队时延和接近于相应计数器值。如果存在差值，则把差值补偿到下一次轮循，即每经过一次轮循就把计数器加上配额。

在实现中，为队列i(i＝0，1，…，n-1)维护3个计数器。前两个是：记录需要发送的分组数量的CS_i(主计数器)，记录需要经历的排队时延之和的CD_i(从计数器)，分别初始化为CS_i＝w_i和CD_i＝φ_i(其中φ_i＝ξ_i·w_i)。

为了维护主计数器CS_i和从计数器CD_i之间的同步平衡，还需要增加一个计数器CO_i。计数器CO_i的作用是根据队列平均排队时延的变化情况提前或推迟其分组的发送。CO_i＞0表示队列分组被提前发送，轮循次数被“透支”；CO_i＜0表示队列分组被推迟发送，轮循次数有“盈余”；CO_i＝0表示正常情况。CO_i初始化为0。

每次调度前，CS_i、CO_i、CD_i三个计数器的值必属于表3所列情况中的一种，根据不同的情况决定当前应该采取何种操作。

WRR-PAD方法步骤如下：

步骤1：给每个队列分配3个计数器，队列i的3个计数器分别记为CS_i，CO_i，CD_i；

φ_i＝ξ_i·w_i；

初始化CS_i＝w_i，CD_i＝φ_i，CO_i＝0；

初始化域值thd_i＝φ_i；

指针i＝0。

步骤2：读取CS_i，CO_i，CD_i三个计数器；

根据表3判断该情况是否需要调度？是，转步骤3；否，转步骤4。

步骤3：根据表3改变计数器的值；

从队列i中取出一个分组；

从RR-PLR模块取得T_入队列，得到分组的出队列时间T_出队列；

计算这个分组在队列中的延时d＝T_出队列-T_入队列，并发送；

CS_i＝CS_i-1；

CD_i＝CD_i-d；

i＝i+1：

转步骤2。

步骤4：i＝i+1；

CS_i＝0并且CD_i≤0？是，转步骤5；否，转步骤6。

步骤5：CS_i＝CS_i+w_i；

CD_i＝CD_i+w_i·ξ_i；

转步骤2。

步骤6：CO_i＝CO_i-1；

转步骤2。

表1归纳了CS_i，CO_i，CD_i三个寄存器的8种不同情况。表中简记的条件符号如下：

记CS_i＝0的情况为A，CS_i＞0的情况为A；

记CO_i＜0的情况为B，CO_i≥0的情况为B；

CD_i-d＜0的情况为C，CD_i-d≥0的情况为C；

CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))≥thd_i的情况为D，CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))＜thd_i的情况为D

其中，d为分组在队列中的延时，d＝T_出队列-T_入队列；对于条件D和D的意义解释如下：条件D和D是在出现在条件B之下需要进一步判断的，这种情况下，表明该队列的分组曾被推迟发送，其轮循次数尚有“盈余”，因此需要判断“盈余”被“补足”之后的CD_i值。(-CO_i·φ_i)为“盈余”轮数所对应的总延时数；(CS_i+(-CO_i·w_i))为总共“盈余”的分组数减去这轮已经发出的分组数；CD_i+(-CO_i·φ_i)-d·(CS_i+(-CO_i·w_i))即按照d的延时发送，“盈余”的总延时能不能被消耗的足够多。

  情况 条件1  条件2 条件3 条件4  是否调度  计数器改变  1  A B  C  调度  CS_i＝CS_i+w_i  CD_i＝CD_i+φ_i  CO_i＝CO_i+1  2  A B C  不调度  无  3  A  B  D  不调度  无  4  A  B D  调度  CS_i＝CS_i+w_i  CD_i＝CD_i+φ_i  CO_i＝CO_i+1  5 A  B  D  不调度  无  6 A  B D  调度  CS_i＝CS_i-1  CD_i＝CD_i-d  7 A B  C  调度  CS_i＝CS_i-1  CD_i＝CD_i-d  8 A B  C  不调度  无

                表1 CS_i，CO_i，CD_i三个寄存器的8种不同情况归纳