一种适用于反馈制两级交换结构的调度算法

摘要

本发明公开了一种适用于反馈制两级交换结构的调度算法，适用于FTSA结构中任意输入端口i依据算法自身规则选择满足条件VOQ2(j,r)为空的非空VOQ1(i,r)的队首信元，并将其转发至下一时槽与输入端口i相连的中间端口j。采用r=i-2,i-3,…,0,N-1,N-2,…,i,i-1的顺序搜索第一个满足VOQ2(j,r)为空的非空VOQ1(i,r)并将其队首信元转发在任意输入端口；包括建立映射、信息过滤和优先级位图算法调度等步骤，最后将调度结果反映射为子队列号。本发明使FTSA结构算法复杂度从O(N)降低为O(1)，提高了FTSA的高速交换能力和可扩展性。

说明书

技术领域

本发明属于互联网信息传输技术领域。

背景技术

互联网用户的迅猛增长和多媒体业务流的激增使Internet面临越来越大的数据传输压力，虽然密集波分复用技术使单个波长的数据传输率高达160Gbps，但中继系统的交换速率却远远低于光域内的数据传输率，这就使中继系统因交换速率过低而成为Internet的瓶颈。此外，长期的流量监测表明Internet数据流具有自相似性，其典型特征是数据具有突发性。因此，能够适应自相似业务流的高速交换结构就成为下一代Internet的核心技术之一。

传统的交换结构因为复杂度或加速比等原因均无法满足未来的交换需求。近年来，反馈制两级交换结构FTSA利用输入端口i和输出端口i位于同一线卡这一特性，通过一种错列对称特性(staggered symmetry)的crossbar连接模式将中间缓存的状态信息反馈到输入端，输入端基于该反馈信息选择一个信元传输至中间缓存，这种“有的放矢”的工作模式可以有效降低中间缓存的下溢(underflow)问题，从而获得了极其优异的时延性能。

但适用于该结构的现有算法的计算复杂度较高，过高的算法复杂度使整个交换流程迟滞，降低了FTSA结构的高速交换能力和可扩展性。

对该问题的详细介绍如下：

(1) FTSA结构

FTSA由两级crossbar(分别记为XB1和XB2)和两级VOQ(Virtual Output Queue)缓冲(分别记为VOQ1和VOQ2)组成，任意VOQ2(j,k)只有1个信元空间，如图1所示。XB1和XB2采用一种特殊的错列对称连接模式，其关键特征在于若t时槽中间端口j与输出端口k相连，则t+1时槽必有输入端口k与中间端口j相连，如图2所示。不至于引起混淆的情况下，文中“输入端口”均指XB1的输入端口，“中间端口”均指XB2的输入端口，“输出端口”均指XB2的输出端口。

由于输入端口k和输出端口k位于同一线卡，FTSA借助于这种特殊的连接模式，在t时槽结束前将中间端口j的缓存状态信息经由XB2传输至输出端口k后反馈至输入端口k，而t+1时槽恰有输入端口k与中间端口j相连，故输入端口k可在中间端口j的缓存信息到达之后且t+1时槽开始之前的这段时间内根据已知的输入缓存信息和反馈得到的中间缓存信息进行“有的放矢”的信元转发调度。这种“有的放矢”的工作模式能够显著降低中间缓存的“underflow”问题，从而获得了极其优异的时延性能。此外，FTSA中任意VOQ2(j,k)缓存容量仅设置1个信元空间的策略也保证了信元的有序转发。

(2) 现有算法的计算复杂度

适用于FTSA的现有算法有三种：RR(Round-Robin)、EDF(Earliest Departure First)及LQF(Longest Queue First)。

LQF算法性能最优但复杂度最高，搜索最长队列的计算复杂度为O(logN)，不妨设VOQ1(i,r)为搜索算法得到的最长队列，但该队列并不一定是符合要求的(可能VOQ2(j,r)非空)。考虑较为一般的方法，FTSA中的LQF算法在最坏情况下需要搜索所有的N个队列，即LQF的计算复杂度为O(N)。

RR算法被视为相对易于实现，但同样基于Round-Robin规则的下一个队列并不一定是符合要求的，故最坏情况下RR算法也需搜索全部的N个队列。

由图2所示的crossbar连接模式可知，对于任意输入端口i，任意时槽与之相连的中间端口j在下一个时槽必与输出端口i-2相连(端口号的加减操作最终都需要对N取模，即实质上是(i-2)mod N，下同)。这就意味着，若VOQ1(i,r)中的信元被转发至VOQ2(j,r)，则该信元需在VOQ2(j,r)等待i-r-2时槽后被转发。依据这种特性，EDF算法每次调度都选择能在最短时间内离开交换机的信元，即对于任意输入端口i，EDF算法按照r=i-2,i-3,…,0,N-1,N-2,…,i,i-1的顺序搜索第一个满足VOQ2(j,r)为空的非空VOQ1(i,r)并将其队首信元转发。虽然仿真结果表明EDF算法的时延性能较为优秀，但最坏情况下，EDF算法也需要搜索全部N个队列，故最坏情况下的计算复杂度也为O(N)。

相对于O(1)复杂度的crossbar连接模式，在整个交换流程过程中，任意一处的计算复杂度高于O(1)都会导致整个交换流程迟滞，进而损害了负载均衡结构原本的高速交换能力。FTSA作为负载均衡结构的一种解决失序问题的方案，其现有三种调度算法在最坏情况下的计算复杂度均为O(N)。这种复杂度较高的调度算法必然会降低FTSA的高速交换能力，同时算法复杂度和交换规模N有关势必增加扩展交换规模的难度，降低FTSA 的可扩展性。

  

发明内容

本发明的目的是解决FTSA结构现有算法复杂度过高的问题，创造一种基于优先级位图的最早离去信元优先算法，使计算复杂度从O(N)降低为O(1)，提高FTSA的高速交换能力和可扩展性。

本发明的目的是通过如下的手段实现的。

一种适用于反馈制两级交换结构的调度算法，适用于FTSA结构中任意输入端口i依据算法自身规则选择满足条件VOQ2(j,r)为空的非空VOQ1(i,r)的队首信元，并将其转发至下一时槽与输入端口i相连的中间端口j；采用r=i-2,i-3,…,0,N-1, N-2,…,i,i-1的顺序搜索第一个满足VOQ2(j,r)为空的非空VOQ1(i,r)并将其队首信元转发在任意输入端口；包括以下步骤：

1）首先将任意输入端口的N个子队列的缓存状态信息映射为优先级状态数据,建立如下映射：

A：任意子队列VOQ1(i,r)映射为优先级为i-r-2的任务；

B：VOQ1(i,r)由空状态转为非空状态映射为优先级为i-r-2的任务就绪；

C：VOQ1(i,r)由非空转为空状态映射为优先级为i-r-2的任务执行完毕;

2）在每个时槽之初利用反馈得到的中间缓存状态信息V过滤优先级就绪表OSRdyTbl而生成临时优先级就绪表TmpRdyTbl，随后根据TmpRdyTbl生成临时优先级就绪组TmpRdyGrp。

3）依据2）生成的临时优先级就绪组TmpRdyGrp和临时优先级就绪表TmpRdyTbl，采用优先级位图算法进行调度，并将调度结果——最高优先级号反映射为子队列号。

采用本发明方法——基于优先级位图的最早离去信元优先算法PB-EDF(Priority Bitmap-based Earliest Departure First)，在任意输入端口，将N个子队列映射为N种优先级固定不变且各不相等的任务；若某个子队列由空转为非空状态则视为一个就绪任务到达；若某个子队列由非空转为空状态，则视为一个处于执行状态的任务结束。依据这种映射规则，任意输入缓存的状态可用一个优先级就绪表来表征。在每个时槽之初，利用反馈的中间缓存状态信息将优先级就绪表中所记录的无效信息过滤，生成实时有效的优先级状态数据并利用优先级位图算法进行调度，最后将调度结果反映射为子队列号。本发明使FTSA结构算法复杂度从O(N)降低为O(1)，提高了FTSA的高速交换能力和可扩展性。

 

附图说明

图1现有技术基于反馈的两级交换结构FTSA结构图。

图2是现有技术错列对称的crossbar连接模式示意图。

图3是本发明实施例优先级就绪表OSRdyTbl。

图4是本发明实施例优先级映射表OSMapTbl。

图5是本发明实施例生成TmpRdyTbl的逻辑电路图。

图6是本发明实施例生成TmpRdyGrp的逻辑电路图。

图7是本发明实施例临时优先级就绪组TmpRdyGrp和临时优先级就绪表TmpRdyTbl。

图8是本发明实施例优先级判定表OSUnMapTbl。

具体实施方式

下面结合附图和实施例对本发明作进一步说明。

实施手段可概括为三个步骤：

①映射：建立子队列与优先级的映射关系，用优先级就绪表记录任意输入缓存的状态信息。

②过滤：利用反馈的中间缓存状态信息过滤优先级就绪表中的无效优先级并生成有效的优先级状态数据。

③调度：基于②的结果利用传统的优先级位图算法进行调度并将调度结果反映射成子队列号。

具体的实施过程如下：

(以下说明以交换端口数N=64为例，0为最高优先级，63为最低优先级)

①映射

对于任意输入端口i，EDF算法总是按照r=i-2,i-3,…,0,N-1,N-2,…,i,i-1的顺序搜索第一个满足VOQ2(j,r)为空的非空VOQ1(i,r)并将其队首信元转发。基于EDF算法的这种特性，本发明PB-EDF算法建立如下映射：

A：任意子队列VOQ1(i,r)映射为优先级为i-r-2的任务；

B：VOQ1(i,r)由空状态转为非空状态映射为优先级为i-r-2的任务就绪；

C：VOQ1(i,r)由非空转为空状态映射为优先级为i-r-2的任务执行完毕。

依据这种映射方法可将任意输入端口的缓存状态信息映射为优先级状态数据，具体使用图3所示的优先级就绪表OSRdyTbl表示。

 

OSRdyTbl的维护规则如下(C语言表示)：

当VOQ1(i,r)由空转为非空状态(等价于优先级p=i-r-2的任务就绪)：

OSRdyTbl[p>>3]|=OSMapTbl[p&0x07]；

当VOQ1(i,r)由非空转为空状态(等价于优先级p=i-r-2的任务结束)：

OSRdyTbl[p>>3]&=~OSMapTbl[p&0x07]

OSMapTbl称为优先级映射表，是一个大小和内容均固定的表格，如图4所示。

②过滤

考虑到有些队列虽然具有较高的优先级，但可能因为目标缓存非空而不应被调度，故PB-EDF还需借助反馈的中间缓存状态信息将优先级就绪表OSRdyTbl中的无效优先级数据过滤，同时生成实时有效的临时优先级就绪表TmpRdyTbl和临时优先级就绪组TmpRdyGrp。

此外，由于反馈至输入端口i的64bit缓存信息是按照端口0~63的顺序排列的，为便于计算可将其按照优先级的顺序(i-2,i-3,…,0,N-1,N-2,…,i,i-1)的顺序重新排列并记为V。如在输入端口5， V的64bit分别记录VOQ2(j,3), VOQ2(j,2), VOQ2(j,1),VOQ2(j,0),VOQ2(j,63),VOQ2(j,62),…,VOQ2(j,4)的缓存状态信息。对任意输入端口而言这种逐位的重排列方式是固定的，故可通过布局布线来实现，无需额外的时间消耗。

过滤操作包含两步操作：

A：利用反馈信息V过滤优先级就绪表OSRdyTbl生成临时优先级就绪表TmpRdyTbl，方法如下：

TmpRdyTbl [0] =OSRdyTbl [0] & V [0]；

TmpRdyTbl [1] =OSRdyTbl [1] & V [1]；

……

TmpRdyTbl [6] =OSRdyTbl [6] & V [6]；

TmpRdyTbl [7] =OSRdyTbl [7] & V [7]；

这里V[0]~V[7]都是包含8bit的一组数据，如在输入端口5，V[0]包含VOQ2(j,3), VOQ2(j,2), VOQ2(j,1), VOQ2(j,0), VOQ2(j,63), VOQ2(j,62), VOQ2(j,61), VOQ2(j,60)的缓存状态信息。V[1]~V[7]按顺序依次类推。其逻辑电路图如图5所示。图中“V[0]_0”表示V[0]的第一个bit，其余类似，下同。

B：依据临时优先级就绪表TmpRdyTbl生成临时优先级就绪组TmpRdyGrp。

TmpRdyTbl [0]~ TmpRdyTbl [7]各自的8个bit进行“或”运算，产生的8bit运算结果存储于TmpRdyGrp，其逻辑电路图如图6所示。

临时优先级就绪组TmpRdyGrp和临时优先级就绪表TmpRdyTbl的关系如图7所示。

③调度

依据②生成的临时优先级就绪组TmpRdyGrp和临时优先级就绪表TmpRdyTbl利用优先级位图算法进行调度，不妨设调度获取的最高优先级为hp，其高三位用High3Bit表示，其低三位用Low3Bit表示，则：

high3Bit= OSUnMapTbl[OSRdyGrp]；

low3Bit=OSUnMapTbl[TmpRdyTbl[high3Bit]]；

hp=(high3Bit<<3)+low3Bit；

OSUnMapTbl称为优先级判定表，同样是一个大小和内容均固定的表格。如图8所示。

PB-EDF算法和FTSA现有的EDF算法的搜索路径完全相同，二者的调度结果是完全一致的。

 

本发明公开的基于优先级位图算法的EDF算法PB-EDF的优点有两个方面：

(1)：PB-EDF算法的计算复杂度降为O(1)

由上节叙述可知，PB-EDF算法的工作流程如下：

A：根据反馈到达的信息V过滤优先级就绪表OSRdyTbl中的无效优先级信息生成临时优先级就绪表TmpRdyTbl。

B：根据临时优先级就绪表TmpRdyTbl，生成临时优先级就绪组TmpRdyGrp

C：根据A和B的结果利用优先级位图算法进行调度，并将结果反映射为子队列号。

以上工作流程，如图5和图6所示，A流程耗时取决于“与门”的开关速度；B流程取决于“或门”的速度；C流程仅需四次存储器访问(包含反映射操作)及有限次“位运算”即可完成，可见PB-EDF的计算复杂度与交换端口数N无关，其计算复杂度为O(1)。

引入PB-EDF算法可使FTSA在整个交换流程实现O(1)复杂度，提高了FTSA的高速交换能力和扩展性。

(2)：PB-EDF算法的时间消耗依赖于固定次数的存储器访问操作，亦即对于确定的交换规模，其调度时间是固定的，调度耗时与输入端口的缓存状态信息及反馈信息无关。在确定时槽长度时，PB-EDF的这一特性可以避免考虑算法最坏情况下的耗时。