摘 要:提出了一种硬件实现的优先队列算法,可以在常量时间内完成插入和解压操作,达到OC3072线速要求。

关键词:常量时间的优先队列 OC3072线速 QoS

　　随着网络的高速发展,用户对网络质量的需求也越来越高,调查显示用户对网络的抱怨主要体现为速度慢,质量没有保证。要解决这个问题需要对网络路由节点进行QoS(Quality of Service)改造,完善已有的QoS功能,用新的具有QoS能力的路由器逐步替代老一代产品。目前IETF等组织提出的QoS方案有2类,即路由器节点的QoS和路由器网络的QoS(如MPLS和Traffic Engineering)。路由器节点的QoS还可以细分为公平的需求和不公平的需求。前者主要包括各种公平调度算法,后者包括公平调度算法的不公平配置、BES、RVSP、IS和DS算法。节点QoS中的很多算法(如调度算法和DS算法)最终都归结为传统的优先队列算法。由于纯软件实现的优先队列算法不能满足高速路由器的需求,本文提出了一种硬件支持的常量时间的优先队列存取算法,能够达到OC3072(即160Gbps)线速要求。

1 相关工作

　　目前有2类常量时间的优先队列算法:(1)基于通用内存的算法,如P-Heap算法。(2)基于专用内存的算法,这种算法起源于vEB(van Emde Boas)优先队列结构,一般被称作STT(Split Tagged Tree)算法。P-Heap算法提出了一种称之为P-Heap的数据结构:每次插入和解压至少经过3次内存操作,而且它使用流水线隔行工作,相当于进行6次内存操作才能获得1次结果。这种机制是提高效率的主要瓶颈,最高支持OC192(即10Gbps)线速。STT算法得益于vEB提出的优秀结构,它的速度足够支持OC768(即40Gbps),但它必须采用专门定制的内存,这种内存因为产量很小而导致成本无法降低。受到P-Heap的启发,提出一种B-Heap结构,单一队列可以实现OC768线速。如果把4个B-Heap优先队列组合起来,则可以满足OC3072线速的要求。

2 B-Heap的工作原理

2.1 基本操作

　　硬件B-Heap的操作特点是在各个分层之间使用流水线工作,插入元素的同时也完成了解压元素的操作。这一点和P-Heap有所不同,虽然P-Heap也是流水线工作,但需要隔层操作。假设插入的元素序列为{0,3,4,2,

6,8,1,9,1,7,5,3,2,8,0,-1,-1,-1,-1,2,-1,5,3,9},则初始阶段的插入解压过程如图1所示,对应前8个元素;有空闲情况下的插入解压过程如图2所示,对应最后8个元素,说明流量减小时插入占位数据-1的过程;255是-1的一种表达方式,其中涉及到比较模式切换问题,中间8个元素的插入解压类似于图1的无空闲情况下的操作。上述3个过程虽然各自代表实际操作中的各种情况,但是三者之间设计成连续的,便于观察。元素从下向上流经该结构,方框代表针对堆结构每一层的数据寄存器,最下端的寄存器为插入输入,灰色寄存器为解压输出。

　　主要的工作机制是每次操作选择一条最小路径,每一次操作按最小路径进行,比较后进行流水线上移。这里的最小路径是指从上到下依次选择上层入选节点的子节点中较小的元素所构成的路径。其中有2种特殊情况:(1)最上面一层只有一个节点,因此入选。(2)如果子节点中元素大小相等则左手子节点入选。每一层所对应的寄存器作为该层的比较输入,与该层最小路径上的元素作比较,将较小者放入上一层寄存器的缓冲器。每层寄存器都包括一个寄存器的缓冲器。寄存器读取前打开,写入前关闭,以满足流水线操作时的同步要求。规定当前没有输入时用-1模拟1个输入,即所谓的空闲情况。对最下面一层的输入寄存器为-1的状态需要进行一次特殊的操作,即结构中所有比较器进行模式切换,将-1认为是与255进行比较,这样有助于空闲情况下将原来元素按从小到大的顺序解压出来。在具体实现中将-1认为是255的模式切换很容易办到,因为对于一个有符号字节-1,如果用无符号字节对其进行识别就是255。有了这种机制,在空闲情况下也可以保证空闲之前进入堆中的数据能够正常流出。输出结果显示,图中的B-Heap结构实现了排队空间n=8的在线优先队列。

2.2 最小路径查找

　　通过观察可以发现,每次操作都需要查找最小路径,这一环节是B-Heap算法进行高速处理的关键。查找的最小路径如图3所示。结构中每一层节点的地址可以表示为从0开始的二进制数,例如从上向下第4层的每一次操作的输入地址可表示为000,001,010,011,100,101,110,111。B-Heap的状态可以表示为X|XX|XXXX|……,其中X为0或1。0表示左手节点小于右手节点,1表示左手节点大于右手节点,|为层分隔符,区别从上到下每一层的状态。则图3中B-Heap的状态可表示为,每次操作在每一层中最多修改1bit。查找最小路径即求出从状态到每一层输入地址的转换结构。下面介绍如何设计该转换:由于每一层使用不同的内存,属于并行操作,因此可以在上一次操作结束时得到所有的状态位,而每次仅仅修改1bit,这样不会造成较大的总线宽度硬件耗费。要从状态中找出最小路径可以通过一个以状态为输入。多层地址为输出的地址编码器来完成。如果采用ASIC,则可以使用足够的寄存器存储状态,从而完全在片内实现编码器,对外只保留很小的总线宽度,能满足每层只修改1bit即可。

　　内部逻辑类似于前缀树,实际上是在前缀树结构基础上简化了一半的状态耗费。定义每个二叉树节点的左、右子节点的比较结果为b,称为路径选择变量。b是一个布尔量,为0表示左手子节点的值小于右手子节点的值,为1则恰好相反。从二叉树的根开始,判断路径选择变量,如果为1,则选择左子树;如果为0,则选择右子树。照此向下推进,直到叶节点为止,所形成的路径就是需要寻找的最小路径。路径选择变量存储在寄存器中,每个变量占用1bit。因为第一层并不需要该变量,所以路径选择变量总共占有n/2bit,使用m个寄存器,其中m=。为了区别每一层的数据寄存器数组T,这m个寄存器称为路径选择寄存器。

　　使用ASIC实现时,判断路径选择变量并选择一条分支的时间耗费t是门级,目前的硬件工艺可以做到十几到几十个皮秒(ps)。整条路径选择的时间耗费大约为t的倍。一般情况下<20,所以整条路径选择的时间实现不会超过1ns。输出的每一层的地址是可以复用的,如图3的状态字中最小路径对应每一层节点地址为{0,0,01,011,0111,……},上层的地址是下层地址的前缀。由此可知第一层不需要地址,因此所有输出数据的地址位数=。

　　综上所述,B-Heap算法的一次存取要完成以下步骤。

　　(1)根据每一层的比较地址找到比较节点,打开数据寄存器数组T中每个寄存器的缓存,刷新寄存器。(2)取出比较节点的值和本层数据寄存器中的值相比较,其中较小值写入上一层数据寄存器的缓存,较大值写入该节点。同时,输入寄存器和输出寄存器中都有了最新值。(3)将较大值和比较节点的兄弟节点进行比较,如果左节点大于右节点,则b=1;反之,b=0。将结果写入路径选择寄存器的相应位置。(4)将路径选择寄存器的值输入路径选择模块以选择一条最小路径。这一步由ASIC实现,输入n/2位,输出位。输出中含有所有层的下一次比较地址。

3 性能评估和合并队列

　　由于路径选择的时间在总的时间耗费中不占很大比重,因此B-Heap插入和解压的时间耗费约为P-Heap的1/4。其中逐行操作比隔行操作快一倍,插入和解压的同步进行比分别进行快一倍。所以按照P-Heap分析所依据的内存和ASIC工艺水平,B-Heap可以达到OC768线速。同时,可以使用4片B-Heap扩展排队长度和操作速度,对4片子优先队列进行RR(Round Robin)调度可以达到OC3072线速。

4 结束语

　　本文提出了一种硬件辅助的优先队列算法B-Heap,通过特殊的结构和操作策略可以达到OC3072线速,在使用普通内存的方法中优于P-Heap算法。B-Heap算法的主要不足是排队长度受到寄存器的限制,例如一个1024排队长度的B-Heap需要16个寄存器,目前的工艺完全可以承受。但是如果排队长度按几何比例增长,则B-Heap的实现依赖于能够集成的寄存器数目。

参考文献

1 Xipeng X,Lionel M N.Internet QoS:A Big Picture.IEEE Network,1999;(4)

2 Bhagwan R,Lin B.Fast and Scalable Priority Queue Architecture for Highspeed Network Switches.IEEE Infocom,2000;(3)

3 Brodnik A.Worst Case Constant Time Priority Queue.WCCTPQ,2000;(3)