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

摘要

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

主权项

1.基于网络处理器平台实现的综合队列管理方法，其特征在于，所述的综合队列管理方法是在Intel IXP 2400网络处理器上实现的，所述方法分别把分组接收模块、分组发送模块、RR-PLR即轮循-比例丢失率缓冲管理程序模块、WRR-PAD即加权轮循-比例平均时延分组调度程序模块，各自分别配置在所述网络处理器的1个微引擎上，即分别分配在第0，第7，第1和第2个微引擎上；而把IPv4协议处理程序配置在所述网络处理器的4个微引擎上，即分配在第3，4，5，6个微引擎上；当分组进入队列时，RR-PLR即轮循-比例丢失率缓冲管理，采用平均分组丢失率比例控制，依次含有以下步骤：步骤1A：初始化每个队列的丢弃分组计数器：设队列i分配的丢弃分组计数器Ci＝ki·δi，i＝0，1，…，n-1；初始化指针变量i＝0；其中n为队列总数，ki为预先确定的参数，它是各队列的分组平均到达速率的比：a0(t)/a1(t)/…/an-1(t)＝k0/k1/…/kn-1；ai(t)为队列i在时间段[0，t]内到达的分组数；δi为预先确定的参数，它是各个队列分组丢失率的比：L0/L1/…/Ln-1＝δ0/δ1/…/δn-1，L1 为队列i的平均分组丢失率；所述Li＝di(t)/ai(t)＝di(t)/(λi·t)；其中，di(t)为队列i在时间段[0，t]内丢弃的分组数；λi为队列i的分组平均到达速率，在程序中以ki的形式表现出来；ki·δi为队列i的丢弃分组数；各个队列的丢弃的分组数保持与(k0·δ0)/(k1·δ1)/…/(kn-1·δn-1)的值相等的比例；步骤2A：等待，一直到有新的分组p到达，记该分组属于队列t，为该分组打上到达队列的时间戳T入队列，转步骤3A；否，转步骤2A；步骤3A：判断各个队列的分组长度之和是否小于缓存可以存放分组总个数：若是，将分组p放入相应的队列t，对于该分组的处理结束；若否，转步骤4A；步骤4A：判断队列i的丢弃分组计数器Ci是否大于零，且队列i非空：若是，从队列i中丢弃一个分组；并且使得Ci＝Ci-1；i＝i+1；将分组p放入相应的队列t，对于该分组的处理结束；重新转到步骤2A；若否，判断i是否小于n：若是，i＝i+1；转入步骤4A；若否，对于j＝0，1，…，n-1，使队列j的丢弃分组计数器Cj＝Cj+kj·δj；指针i＝0；转到步骤4A；当分组出队列时采用WRR-PAD即加权轮循-比例平均时延分组调度，即平均排队时延的比例控制方法，使得各个队列中各分组的时延满足以下比例关系：$\underset{j=0}{\overset{s_0\left(t\right)}{\Sigma }}{d}_0^j/\underset{j=0}{\overset{s_1\left(t\right)}{\Sigma }}{d}_1^j/···/\underset{j=0}{\overset{s_{n-1}\left(t\right)}{\Sigma }}{d}_{n-1}^j=({\xi }_0·w_0)/({\xi }_1·w_1)/···/({\xi }_{n-1}·w_{n-1});$ 其中，si(t)为队列i在时间段[0，t]内发送的分组数，i＝0，1，…，n-1；di j为队列i中的第j个分组排队所需要的时延；队列i的平均排队时延为$D_i=\frac{\underset{j=0}{\overset{s_i\left(t\right)}{\Sigma }}{d}_i^j}{s_i\left(t\right)},$各个队列平均排队时延的比保持一致，即D0/D1/…/Dn-1＝ξ0/ξ1/…/ξn-1；ξi为预先确定的参数；各个队列发送的分组数满足以下比例关系：s0(t)/s1(t)/…/sn-1(t)＝w0/w1/…/wn-1，wi为预先确定的参数；以上所述的WRR-PAD即加权轮循-比例平均时延分组调度，含有以下步骤：步骤1B：给每个队列分配3个不同功能的计数器，队列i的所述3个计数器记为：CSi为记录需要发送的分组数量的计数器；CDi为记录需要经历的排队时延之和的计数器；COi为根据队列平均排队时延的变化情况，记录提前或推迟其队列i分组的发送的辅助计数器；COi＞0表示队列分组被提前发送，发送次数被“透支”；COi＜0表示队列分组被推迟发送，发送次数有“盈余”；COi＝0表示正常情况；φi＝ξi·wi，wi、ξi为预先确定的参数；初始化CSi＝wi，CDi＝φi，COi＝0；初始化域值thdi＝φi；指针i＝0：步骤2B：读取计数器CSi，COi，CDi的值；根据下列a-h8种情况，判断是否需要调度，调度指的是，将该分组从等待队列中取出并发送：若是，转步骤3B-1；若否，转步骤4B；根据以下CSi，COi，CDi三个计数器的8种不同情况，判断是否调度：情况a，当CSi＝0，COi≥0，CDi-d＜0时：调度；并改变计数器，使得CSi＝CSi+wi，CDi＝CDi+φi，COi＝COi+1；情况b，当CSi＝0，COi≥0，CDi-d≥0时：不调度；情况c，当CSi＝0，COi＜0，CDi+(-COi·φi)-d·(CSi+(-COi·wi))≥thdi时：不调度；情况d，当CSi＝0，COi＜0，CDi+(-COi·φi)-d·(CSi+(-COi·wi))＜thdi时：调度；并改变计数器，使得CSi＝CSi+wi，CDi＝CDi+φi，COi＝COi+1；情况e，当CSi＞0，COi＜0，CDi+(-COi·φi)-d·(CSi+(-COi·wi))≥thdi时：不调度；情况f，当CSi＞0，COi＜0，CDi+(-COi·φi)-d·(CSi+(-COi·wi))＜thdi时：调度；并改变计数器，使得CSi＝CSi-1，CDi＝CDi-d；情况g，当CSi＞0，COi≥0，CDi-d＜0时：调度；并改变计数器，使得CSi＝CSi-1，CDi＝CDi-d；情况h，当CSi＞0，COi≥0，CDi-d≥0时：不调度；其中，d为分组在队列中的时延，d＝T出队列-T入队列；对于上述CDi+(-COi·φi)-d·(CSi+(-COi·wi))和thdi的比较解释如下：在COi＜0情况下，表明该队列的分组曾被推迟发送，其发送次数尚有“盈余”，因此需要判断“盈余”被“补足”之后的CDi值；(-COi·φi)为“盈余”轮数所对应的总时延数；(CSi+(-COi·wi))为总共“盈余”的分组数减去这轮已经发出的分组数；CDi+(-COi·φi)-d·(CSi+(-COi·wi))即按照d的时延发送还剩下的“盈余”时延，将之与域值thdi比较，判断是否调度；步骤3B-1：根据上述不同的情况，改变计数器CSi，COi，CDi的值；步骤3B-2：从队列i中取出一个分组；从所述RR-PLR即轮循-比例丢失率缓冲管理程序模块中取得T入队列；取当前时间得到分组的出队列时间T出队列；计算这个分组在队列中的时延d＝T出队列-T入队列，并发送；步骤3B-3：使CSi＝CSi-1；CDi＝CDi-d；i＝i+1；转步骤2B；步骤4B：i＝i+1；判断CSi＝0并且CDi≤0：若是，转步骤5B；若否，转步骤6B；步骤5B：CSi＝CSi+wi；CDi＝CDi+wi·ξi；转步骤2B；步骤6B：COi＝COi-1；转步骤2B。