·268· 智能系统学报 第3卷 V=11 +exp(-gu) 神经网络算法的迭代是通过能量函数完成的， 式中：U为输入，V为输出，g为增益系数 能量函数的初始状态相当于分布式算法中的第一个 为实现最优的无阻塞信元传输，确定HNN在一 步骤情求：能量函数等式右端的第1项和第3项 个时隙内的调度规则为：1)每个输入端口最多发送 完成分布式算法中的响应步骤功能，即每个输入端 一个信元：2)选出的信元必须有不同的目的地址： 口只传送一个信元.不同的是，分布式算法只响应优 3)优先传送优先级别高的信元，4)使网络快速收 先级最高的请求，而神经网络算法从全局的角度选 敛.根据调度规则写出HNN的能量函数： 择；等式右端第2项相当于接收步骤，即每个输出端 口只接收一个信元；最后一项则加速了网络运算速 度.其中优先级P(Q)如果采用长队列优先原则 NNNN 则可实现权重为队列长度L的LQF算法；如果采 用信元等待时间原则，则可实现DCF算法；当然也 csperDv.v 可以采用多种优先级的有效融合原则.因此，具有灵 活优先级定义的神经网络算法更能适应复杂的高速 式中：A、B、C和D是正常数；V是神经元(i)的输 交换系统 出：是神经元(1的外部输入，若第(1个缓存 器中有信元等待交换，其值为1，否则为0：Hm为2 3结束语 个不同的神经元(i)与(pq之间的连接权重矩 本文讨论了交换技术中调度算法的基本问题 阵，若2个神经元所对应的信元目的地址有冲突，其 介绍了当前比较重要的几类基于Crossbar结构的输 值为1，否则为0：P(Q)是缓存器中等待传输的信 入排队调度算法，并分别从技术特点，性能指标和实 元优先级函数.可以推导出dE/d1≤0，证明系统能 现复杂度等多个方面进行比较和分析.尤其是HNN 量是随着时间收敛到稳定状态，此时神经元的状态 算法具有大规模并行处理能力和快速收敛的特性， 就代表在一个时隙内传送的一组最优或接近最优的 如果有效地定义其优先级参数，将非常适合大规模 无阻塞信元集」 复杂高速交换系统.此外，在文献〔22-23冲还提出 通过仿真实验2可以看到，与最大匹配算法性 了基于帧(frame)或包(envebpe)的输入排队调度算 能相近，但神经网络算法硬件复杂度仅为·用 法.其原理是将同一队列中相邻的若干信元组成帧 CMOS VLSI技术实现的HNN收敛时间只需 100ns),并且处理速度基本不受网络规模扩展的 或包，从而增加算法时间.使复杂调度算法的实现成 为可能.总之，未来的调度算法既要适应网络带宽和 影响 网络规模的快速增长，具有良好的技术性能和扩展 2算法比较与结合 性，同时在延迟、公平性和服务多样性等方面也要有 很好的保证」 MSM、MWM以及稳定结合算法属于分布式调 度算法，这种算法的特点是在每个输入输出端口都 参考文献： 存在一个仲裁器，由仲裁器决定本端口和哪个端口 [1 ]KAROL M,HLUCHYJ M,MORGAN S Input versus out 进行交换，并且各个端口的处理是独立的.比如PM put queuing on a space-division packet switch [J]IEEE 算法，一个未匹配的输出端口只响应它所接收到的 Trans on Communications,987,12(35):1347-1356 请求信号而不管其他输出端口的响应情况.因此分 [2 ]ANDERSON T,OW CKIS,SAXES J,THACKER C High 布式算法的优点就是迭代次数少，计算速度快，但调 speed switches scheduling fr bcal area netork [J ]ACM 度方案复杂，硬件实现难度大.分布式算法性能分析 Transactions on Computer Systems,1993,11(4):319-352 见表1和表2 [3 ]MEKKIITIKU IA,MCKBOWN N.A practical scheduling 神经网络算法属于集中式调度算法，算法存在 algorithm to achieve 100%throughout in input-queued swit- 一个中央调度器，对所有端口进行集中处理，各端口 ches[C ]//IEEE NFOCOM 98 San Francisco,CA,1998: 23-28 的参数作为神经网络的输入，输出结果就是所要的 [4 MCKBOWN N,IZZARD M,MEKKITTIKUL A,et al The 最优或接近最优的配置矩阵.神经网络算法的优点 tiny-tera:a packet switches core [J]IEEE Mico Maga- 是调度方案简单，易于硬件实现.而通过CMOS VL- zine,1997,17(1):26-33 S技术实现的神经网络算法完全克服了迭代次数 [5]Cisco Inc Cisco 12000 series-Intemet Router ProductO- 多，计算速度慢的缺点 verview EB /OL ]2001-10-10 ]htp://www.Cisca 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netV = [1 + exp ( - gU ) ] - 1 . 式中 : U为输入 , V为输出 , g为增益系数. 为实现最优的无阻塞信元传输 ,确定 HNN在一 个时隙内的调度规则为 : 1)每个输入端口最多发送 一个信元; 2)选出的信元必须有不同的目的地址; 3)优先传送优先级别高的信元; 4 )使网络快速收 敛. 根据调度规则写出 HNN的能量函数 : E = A 2 ∑ N i =1 ∑ N j=1 ( lij - ∑ N q =1 Viq ) 2 + B 2 ∑ N i =1 ∑ N j =1 ∑ N p =1, p≠i∑ N q =1 H ij, pqVijVpq - C∑ N i =1 ∑ N j=1 P (Qij ) Vij + D ∑ N i =1 ∑ N j=1 Vij (1 - Vij ). 式中 : A、B、C和 D是正常数; Vij是神经元 ( i, j) 的输 出; Iij是神经元 ( i, j)的外部输入 ,若第 ( i, j)个缓存 器中有信元等待交换 ,其值为 1,否则为 0; H ij, pq为 2 个不同的神经元 ( i, j)与 ( p, q)之间的连接权重矩 阵 ,若 2个神经元所对应的信元目的地址有冲突 ,其 值为 1,否则为 0; P (Qij )是缓存器中等待传输的信 元优先级函数. 可以推导出 dE / dt≤0,证明系统能 量是随着时间收敛到稳定状态 ,此时神经元的状态 就代表在一个时隙内传送的一组最优或接近最优的 无阻塞信元集. 通过仿真实验 [ 20 ]可以看到 ,与最大匹配算法性 能相近 , 但神经网络算法硬件复杂度仅为 . 用 CMOS VLSI 技 术 实 现 的 HNN 收 敛 时 间 只 需 100 ns [ 21 ] ,并且处理速度基本不受网络规模扩展的 影响. 2 算法比较与结合 MSM、MWM以及稳定结合算法属于分布式调 度算法 ,这种算法的特点是在每个输入输出端口都 存在一个仲裁器 ,由仲裁器决定本端口和哪个端口 进行交换 ,并且各个端口的处理是独立的. 比如 PIM 算法 ,一个未匹配的输出端口只响应它所接收到的 请求信号而不管其他输出端口的响应情况. 因此分 布式算法的优点就是迭代次数少 ,计算速度快 ,但调 度方案复杂 ,硬件实现难度大. 分布式算法性能分析 见表 1和表 2. 神经网络算法属于集中式调度算法 ,算法存在 一个中央调度器 ,对所有端口进行集中处理 ,各端口 的参数作为神经网络的输入 ,输出结果就是所要的 最优或接近最优的配置矩阵. 神经网络算法的优点 是调度方案简单 ,易于硬件实现. 而通过 CMOS VL2 SI技术实现的神经网络算法完全克服了迭代次数 多 ,计算速度慢的缺点. 神经网络算法的迭代是通过能量函数完成的 , 能量函数的初始状态相当于分布式算法中的第一个 步骤 (请求 ) ;能量函数等式右端的第 1项和第 3项 完成分布式算法中的响应步骤功能 ,即每个输入端 口只传送一个信元 ,不同的是 ,分布式算法只响应优 先级最高的请求 ,而神经网络算法从全局的角度选 择;等式右端第 2项相当于接收步骤 ,即每个输出端 口只接收一个信元;最后一项则加速了网络运算速 度. 其中优先级 P (Qij )如果采用长队列优先原则 , 则可实现权重为队列长度 Lij的 iLQF算法;如果采 用信元等待时间原则 ,则可实现 iOCF算法;当然也 可以采用多种优先级的有效融合原则. 因此 ,具有灵 活优先级定义的神经网络算法更能适应复杂的高速 交换系统. 3 结束语 本文讨论了交换技术中调度算法的基本问题 , 介绍了当前比较重要的几类基于 Crossbar结构的输 入排队调度算法 ,并分别从技术特点 ,性能指标和实 现复杂度等多个方面进行比较和分析. 尤其是 HNN 算法具有大规模并行处理能力和快速收敛的特性 , 如果有效地定义其优先级参数 ,将非常适合大规模 复杂高速交换系统. 此外 ,在文献 [ 22223 ]中还提出 了基于帧 (frame)或包 ( envelope)的输入排队调度算 法. 其原理是将同一队列中相邻的若干信元组成帧 或包 ,从而增加算法时间 ,使复杂调度算法的实现成 为可能. 总之 ,未来的调度算法既要适应网络带宽和 网络规模的快速增长 ,具有良好的技术性能和扩展 性 ,同时在延迟、公平性和服务多样性等方面也要有 很好的保证. 参考文献 : [ 1 ] KAROL M, HLUCHYJ M, MORGAN S. Input versus out2 put queuing on a space2division packet switch [ J ]. IEEE Trans on Communications, 987, 12 (35) : 134721356. [ 2 ]ANDERSON T, OW ICKI S, SAXES J, THACKER C. H igh speed switches scheduling for local area network [J ]. ACM Transactions on Computer Systems, 1993, 11 (4) : 3192352. [ 3 ]MEKKITTIKU I A, MCKEOWN N. A p ractical scheduling algorithm to achieve 100% throughout in input2queued swit2 ches[C ] / / IEEE INFOCOM ’98. San Francisco, CA, 1998: 23228. [ 4 ]MCKEOWN N, IZZARD M, MEKKITTIKUL A, et al. The tiny2tera: a packet switches core [ J ]. IEEE M icro Maga2 zine, 1997, 17 (1) : 26233. [ 5 ]Cisco Inc. Cisco 12000 series2Internet Router. Product O2 verview [ EB /OL ]. [ 2001210210 ]. http: / /www. Cisco. ·268· 智 能 系 统 学 报 第 3卷