基于两级交换的负载均衡调度方法

摘要

一种基于两级交换的负载均衡调度方法，第一级输入端口将到达信元按照目的端口缓冲在VOQ队列，调度器通过第一级交换网络将报文交换至第二级输入端口，VOQ队列中来自同一条流的k个信元称之为一个单位帧；第一级每个输入端口根据流量分布矩阵执行最小长度分派，在k个连续的外部时间槽，通过第一级交换网络将同一条流的单位帧发送至该流固定的映射区域；N个第二级输入端口被依次划分为N/k组，每组含k个连续的第二级输入端口构成一个区域，各区域按照目的端口将信元缓冲在OQ队列，通过第二级交换网络交换至目的输出端口。本发明具有调度过程简单、无需任何计算或者通信、易于硬件实现、实现了100％的吞吐率并能保证报文的顺序等优点。

主权项

一种基于两级交换的负载均衡调度方法，其特征在于：第一级输入端口将到达信元按照目的端口缓冲在VOQ队列，调度器通过第一级交换网络将报文交换至第二级输入端口，VOQ队列中来自同一条流的k个信元称之为一个单位帧，单位帧是最小调度单元；第一级每个输入端口根据流量分布矩阵执行最小长度分派，在k个连续的外部时间槽，通过第一级交换网络将同一条流的单位帧发送至该流固定的映射区域；N个第二级输入端口被依次划分为N/k组，每组含k个连续的第二级输入端口构成一个区域，各区域按照目的端口将信元缓冲在OQ队列，由于流到区域的映射关系固定，来自同一单位帧的k个信元将依次到达OQ队列头位置，通过第二级交换网络交换至目的输出端口；第一级输入端口调度时根据流到区域的映射关系分派信元以轮询方式服务于N/k个流分支，所述第一级输入端口在每个外部时间槽的操作流程如下：(2.1)若流分支VOQ队列、VOQ_i,j存在满帧，则优先调度满帧，即中0≤f<N/k,f初始化为0，VOQ_i,j中kf≤j<kf+k；赋予该满帧N/k个单位帧最高调度优先级，查找流量分布矩阵L，截取满帧第一个单位帧，发送到目前L_g,j最小的区域R_g，即执行步骤(2.1.1)～(2.1.k)，若不存在满帧则转步骤(2.2)；队列VOQ_i,j均衡系数等于其映射区域R_g输出队列j的长度，记作L_g,j；(2.1.1)若第一级输入端口i到第二级输入端口S_g,1的内部链路空闲，则将VOQ_i,j队列头信元发送到区域R_g第二级输入端口S_g,1，否则f＝(f+1)modN/k，转步骤(2.1)；(2.1.2)发送VOQ_i,j队列头信元到区域R_g第二级输入端口S_g,2；(2.1.3)发送VOQ_i,j队列头信元到区域R_g第二级输入端口S_g,3；依此类推至(2.1.k)发送VOQ_i,j队列头信元到区域R_g第二级输入端口S_g,k，g＝(g+1)modN/k，转步骤(2.1)；(2.2)若流分支VOQ队列、VOQ_i,j，其中kf≤j<kf+k存在最高调度优先级单位帧，则查找流量分布矩阵L，将该单位帧发送到目前L_g,j最小的区域R_g，即执行步骤(2.1.1)～(2.1.k)，否则转步骤(2.3)；(2.3)若流分支VOQ队列存在一个或多个单位帧，则查找流量分布矩阵L，根据查找结果选择最小均衡系数VOQ队列的单位帧，将其发送到流分支的固定映射区域R_g，即执行步骤(2.1.1)～(2.1.k)，若仅含一个单位帧则可跳过流量分布矩阵查找操作，直接将流分支唯一的单位帧发送到其固定映射区域R_g，否则流分支不含任何单位帧，g＝(g+1)modN/k，转步骤(2.1)；其中，VOQ_i,j表示第一级输入端口i的虚拟输出队列j；表示第二级输入端口l的输出队列j；f(i,j)表示从第一级输入端口i到输出端口j的流；k为聚合粒度，表示连续调度同一条流信元的数目，k为端口数N的因数；VOQ_i,j队列的每k个信元构成一个单位帧，第一级输入端口i处N/k个不同VOQ队列的单位帧构成一个聚合帧，共计N个信元；VOQ_i,j队列的N个信元，构成一个满帧；第二级输入端口1,2,....,N被依次分成N/k组，每一组含k个连续的第二级输入端口，第g组的k个第二级输入端口构成一个区域，记作R_g，S_r,z表示区域r的第z个第二级输入端口；每个第二级输入端口的N条流被划分为N/k组与N/k个区域相对应，每组含k条流，第二级输入端口i第f组的k条流构成一个流分支，记作所述外部时间槽为在速率为R的链路发送或接收一个信元所耗费的时间。