第3卷第3期 智能系统学报 Vol 3 Na 3 2008年6月 CAA I Transactions on Intelligent Systems Jun 2008 基于输入排队的高速交换调度算法研究 张重洋，申金媛，刘润杰，张文英，穆维新 郑州大学信息工程学院，河南郑州450052) 摘要：高速交换网络一般采用基于定长信元的交换结构，其性能决定于排队策略和信元调度算法.输入排队策略 只有和一个有效的调度算法相结合，才能保证交换结构具有良好的吞吐率和时延等性能.主要阐述了基于VOQ的最 大数量匹配算法，最大权重匹配算法，稳定结合算法，神经网络算法等输入排队调度算法，分别从技术特点，性能指 标和实现复杂度等多个方面进行比较和分析.分析了分布式和集中式两大类调度算法的工作方式，并根据各类算法 的特点提出，神经网络算法可以通过定义其优先级函数实现其余各类算法」 关键词：输入排队；虚拟输出队列；二部图匹配；调度算法 中图分类号：1P18文献标识码：A文章编号：16734785(2008)03-0265-05 A study on scheduling a lgorithm s for high-speed switching networks ba sed on nput-queung ZHANG Chong-yang,SHEN Jin-yuan,L U Run-jie,ZHANG Wen-ying,MU Wei-xin (Institute of Inmation Engineering.Zhengzhou University,Zhengzhou 450052,China) Abstract:Most high-speed switching networks adopt a switching fabric with fixed-length cells,and their perfom- ance depends heavily upon queuing strategies and the cell scheduling algorithm.Only when the input-queuing strat- egy is combined with a proper switching algorithm can throughput and tme delay for the switching fabric be opti m ized This paper mainly discusses virtual output queuing (VOQ)-based algorithms,among them the maxium number matching algorithm,the maxmum weight matching algorithm,the stable combination matching algorithm, and the Hopfield neural netork(HNN)scheduling algorithm The mechaniss,perfomance and mplementation- al comp lexity of these algorithms are compared and analyzed The working modes of distributed and centralized scheduling algorithms are analyzed Finally,from the findings in our research,it is concluded that the HNN algo- rithm can realize other algorithms by defining a priority functon Keywords:input-queuing virtual output queuing bipartite graph matching scheduling algorithm 在高速信元交换中，为消除或减小队首(head of 0586.采用虚拟输出队列(virtual of queuing,. lie,HOL)阻塞和解决信元对交换线路的竞争造成VOQ)的输入排队方法不需要更高的加速比，可以 的丢失问题，必须对信元进行缓冲排队，在时间上将 消除队首阻塞，并使吞吐率达到100%2).目前，许 冲突信元分开.根据缓冲队列相对于交换结构的位 多产品都采用基于Crossbar交换结构的“输入排队 置，调度算法可分为输入排队(input-queued,Q)算 +VOQ"排队系统，如Tiy-Tea太比特路由器原 法、输出排队(ouput-queued,OQ)算法以及组合输 型和Cis0GSR12000系列的P路由器I) 入输出(combined input/output-queued,CDQ)排队 1基本问题与算法 算法三大类.目前研究的重点，应用最多的是输入排 队算法.传统的输入排队采用简单的FO(先进先 在信元交换中，每一个信元周期开始时，输入端 出)机制，因为存在队首阻塞，其吞吐率只有 口向调度器请求与相应的输出端口建立连接，调度 器根据调度算法确定无冲突的端口配置方案.调度 收稿日期：2007-11-15 基金项目：河南省杰出青年基金资助项目(512000400)，教育部留学 算法所寻求的结果就是在一个信元时隙内通过多次 回因人员科研启动基金资助项目. 迭代达到输入和输出端口的最优匹配，从而使吞吐 通讯作者：申金媛.Emaik jyshen@z四edu cn 率接近100%.因此调度问题可以看成解决二部图 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 3期 智 能 系 统 学 报 Vol. 3 №. 3 2008年 6月 CAA I Transactions on Intelligent System s Jun. 2008 基于输入排队的高速交换调度算法研究 张重洋 ,申金媛 ,刘润杰 ,张文英 ,穆维新 (郑州大学 信息工程学院 ,河南 郑州 450052) 摘 要 :高速交换网络一般采用基于定长信元的交换结构 ,其性能决定于排队策略和信元调度算法. 输入排队策略 只有和一个有效的调度算法相结合 ,才能保证交换结构具有良好的吞吐率和时延等性能. 主要阐述了基于 VOQ的最 大数量匹配算法 ,最大权重匹配算法 ,稳定结合算法 ,神经网络算法等输入排队调度算法 ,分别从技术特点 ,性能指 标和实现复杂度等多个方面进行比较和分析. 分析了分布式和集中式两大类调度算法的工作方式 ,并根据各类算法 的特点提出 ,神经网络算法可以通过定义其优先级函数实现其余各类算法. 关键词 :输入排队 ;虚拟输出队列 ;二部图匹配 ;调度算法 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2008) 0320265205 A study on scheduling algor ithm s for high2speed switching networks based on input2queuing ZHANG Chong2yang, SHEN Jin2yuan, L IU Run2jie, ZHANGW en2ying, MU W ei2xin ( Institute of Information Engineering, Zhengzhou University, Zhengzhou 450052, China) Abstract: Most high2speed switching networks adop t a switching fabric with fixed2length cells, and their perform2 ance depends heavily upon queuing strategies and the cell scheduling algorithm. Onlywhen the input2queuing strat2 egy is combined with a p roper switching algorithm can throughput and time delay for the switching fabric be op ti2 m ized. This paper mainly discusses virtual output queuing (VOQ ) 2based algorithm s, among them the maximum number matching algorithm, the maximum weight matching algorithm, the stable combination matching algorithm, and the Hopfield neural network (HNN) scheduling algorithm. The mechanism s, performance and imp lementation2 al comp lexity of these algorithm s are compared and analyzed. The working modes of distributed and centralized scheduling algorithm s are analyzed. Finally, from the findings in our research, it is concluded that the HNN algo2 rithm can realize other algorithm s by defining a p riority function. Keywords: input2queuing; virtual output queuing; bipartite graph matching; scheduling algorithm 收稿日期 : 2007211215. 基金项目 :河南省杰出青年基金资助项目 ( 512000400) ,教育部留学 回国人员科研启动基金资助项目. 通讯作者 :申金媛. E2mail: jyshen@zzu. edu. cn. 在高速信元交换中 ,为消除或减小队首 ( head of line, HOL)阻塞和解决信元对交换线路的竞争造成 的丢失问题 ,必须对信元进行缓冲排队 ,在时间上将 冲突信元分开. 根据缓冲队列相对于交换结构的位 置 ,调度算法可分为输入排队 ( input2queued, IQ )算 法、输出排队 ( output2queued, OQ )算法以及组合输 入输出 ( combined input/output2queued, C IOQ )排队 算法三大类. 目前研究的重点 ,应用最多的是输入排 队算法. 传统的输入排队采用简单的 FIFO (先进先 出 ) 机 制 , 因 为 存 在 队 首 阻 塞 , 其 吞 吐 率 只 有 0. 586 [ 1 ] . 采用虚拟输出队列 ( virtual of queuing, VOQ)的输入排队方法不需要更高的加速比 ,可以 消除队首阻塞 ,并使吞吐率达到 100% [ 223 ] . 目前 ,许 多产品都采用基于 Crossbar交换结构的“输入排队 +VOQ ”排队系统 ,如 Tiny2Tera太比特路由器原 型 [ 4 ]和 Cisco GSR 12000系列的 IP路由器 [ 5 ] . 1 基本问题与算法 在信元交换中 ,每一个信元周期开始时 ,输入端 口向调度器请求与相应的输出端口建立连接 ,调度 器根据调度算法确定无冲突的端口配置方案. 调度 算法所寻求的结果就是在一个信元时隙内通过多次 迭代达到输入和输出端口的最优匹配 ,从而使吞吐 率接近 100%. 因此调度问题可以看成解决二部图
·266· 智能系统学报 第3卷 匹配问题(bipartite graph matching). 输入端口可能收到多个响应信号，随机地从中选择 G 一个输出端口并向其发送接受信号.每个信元时隙 输入输出都重新开始并预设为未匹配，在某次迭代 ●2 中完成的连接在后面的迭代中继续保持（卿使存在 更多的匹配数).一次迭代的PM算法吞吐率只能 达到63%，多次迭代可达到100% PM在硬件实现上复杂度比较高，对于一个 16Ⅺ的交换结构，要实现PM算法，就需要将近 图1二部图G及其匹配图M 64000个复杂的门器件」 Fig 1 B ipartite graph G and its'matching graphM 过P每次迭代也是请求、响应、接受3个步骤， 不同的是，在第2步的响应中，输出端口收到请求 如图1所示，G=Y,E,为顶点集，包括2个 后，从它的固定循环列表里选择当前Gant指针指 子集：左侧输入端口集和右侧输出端口集，分别代表 向的输入端口，输出端口通知所有输入端口说明其 输入和输出端口：E为边集，表示从输入端口到输出 请求是否被响应，当且仅当该响应在第3步里得到 端口可能的连接边，其权重记为W,例如：在PM和 确认接受后，Grant指针才增加1（模N)指向下一输 设P中W,=0或1，表示队列Q是否有信元传输； 入端口；在第3步接受中，输入端口按照固定循环列 在LQF和OCF中，W表示Q的长度或信元等待时 表选择响应信号，当某个输出端口被接受时，Accept 间.二部图G的匹配图M定义为边集E的子集，且 指针模N加1指向下一输出端口.这种指针更新方 M中没有2条边有公共定点.这就说明一个匹配图 法克服了PM的不公平性，不仅可以预防端口出现 满足交换结构的传输限制条件，即在同一时隙内，输饥饿现象，还使响应仲裁器趋向于非同步工作，可快 入端口传送的信元和输出端口接收的信元个数最多速实现端口间的最大匹配， 为一个 实现汉P算法的硬件需要包含2W个仲裁器： 实现二部图匹配的算法有最大数量匹配算法 N个用于输出端的响应仲裁器，N个用于输入端的 (maxium size matching,.MSM)6),最大权重匹配 接受仲裁器，每个仲裁器有N个可编程的输入优先 算法(maxmum weight matching,.MWM)-y,稳定结 级解码器.实现过P算法需要的门器件数量比PM 合算法)，神经网络算法等.设计调度算法的基本 少了一半 要求包括：公平性稳定性时延小、易于实现等 12最大权重匹配算法 11最大数量匹配算法 最大权重匹配算法的目标是使匹配边的总权重 最大数量匹配算法的目标是使匹配的边的数量 达到最大，除考虑输入队列是否为空外，还要考虑队 达到最大.M9M采用1位的请求信号长度作为边的 列长度或排队时间等权重因素，因此请求信号长度 权重，当某虚拟队列中有信元时，相应的边的权重为 由1位变为多位.在容许的信元流量下，不论是否均 1,否则为0仿真实验表明，在独立均匀和容许的 匀，最大权重匹配算法都可以达到100%的吞吐量. 信元流量时可以获得100%的吞吐量，对于非均匀 常用的迭代近似MWM算法有：最长队列优先算法 流量可能出现饿死现象，存在不稳定性和不公平性. (iterative lng queue first,LQF)、等待最久信元优先 由于实现的复杂性，常用多次迭代的方法近似MM 算法(iterative old cell first,CF)),最久端口优 算法，其实现的迭代算法有PM(parallel iterative 先算法(iterative ng port first,LPF)a&o等 matching)(iterative round obin matching LQF是LQF的迭代算法，也包括请求、响应、接 wi油LP)6等. 受3个迭代步骤，权重W,()等于输入队列长度 PM是一种并行迭代匹配时序算法，在一个时 Ly(.其输入端发送的请求信号为该队列的长度 隙内多次迭代产生不会冲突的匹配.每次迭代包括 信息，该请求信号字宽2b,其中b由输入队列的最 3个步骤：1)请求(Request):每个未匹配的输入端 大长度Lma决定，即2b≤Lma,LQF算法有可能出现 口向有输出要求的未匹配的输出端口发送请求信 饿死现象.DCF是OCF的迭代算法，算法权重 号；2)响应(Gran):一个未匹配的输出端口可能收 Wg(n等于输入队列队首信元的等待时间T,(. 到多个请求信号，随机地从中选择一个输入端口并 DCF算法不会出现饿死现象，因为如果有队首信元 向其发送响应信号；3)接受(Accep):一个未匹配的 得不到服务的话，那么它的权重T,(n)会一直增加 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
匹配问题 ( bipartite graph matching). 图 1 二部图 G及其匹配图 M Fig. 1 Bipartite graph G and its’matching graphM 如图 1所示 , G = [V, E ], V为顶点集 ,包括 2个 子集 :左侧输入端口集和右侧输出端口集 ,分别代表 输入和输出端口; E为边集 ,表示从输入端口到输出 端口可能的连接边 ,其权重记为 W ij . 例如 :在 PIM和 iSL IP中 W ij = 0或 1,表示队列 Qij是否有信元传输; 在 iLQF和 iOCF中 , W ij表示 Qij的长度或信元等待时 间. 二部图 G的匹配图 M 定义为边集 E的子集 ,且 M 中没有 2条边有公共定点. 这就说明一个匹配图 满足交换结构的传输限制条件 ,即在同一时隙内 ,输 入端口传送的信元和输出端口接收的信元个数最多 为一个. 实现二部图匹配的算法有最大数量匹配算法 (maximum size matching, MSM ) [ 627 ] , 最大权重匹配 算法 (maximum weight matching,MWM ) [ 8211 ] ,稳定结 合算法 [ 12 ] ,神经网络算法等. 设计调度算法的基本 要求包括 :公平性、稳定性、时延小、易于实现等 [ 10 ] . 1. 1 最大数量匹配算法 最大数量匹配算法的目标是使匹配的边的数量 达到最大. MSM采用 1位的请求信号长度作为边的 权重 ,当某虚拟队列中有信元时 ,相应的边的权重为 1,否则为 0. 仿真实验 [ 9 ]表明 ,在独立均匀和容许的 信元流量时可以获得 100%的吞吐量 ,对于非均匀 流量可能出现饿死现象 ,存在不稳定性和不公平性. 由于实现的复杂性 ,常用多次迭代的方法近似 MSM 算法 ,其实现的迭代算法有 PIM ( parallel iterative matching) [ 2, 6 ] , iSL IP ( iterative round robin matching with SL IP) [ 627 ]等. PIM是一种并行迭代匹配时序算法 ,在一个时 隙内多次迭代产生不会冲突的匹配. 每次迭代包括 3个步骤 : 1)请求 (Request) :每个未匹配的输入端 口向有输出要求的未匹配的输出端口发送请求信 号 ; 2)响应 ( Grant) :一个未匹配的输出端口可能收 到多个请求信号 ,随机地从中选择一个输入端口并 向其发送响应信号 ; 3)接受 (Accep t) :一个未匹配的 输入端口可能收到多个响应信号 ,随机地从中选择 一个输出端口并向其发送接受信号. 每个信元时隙 输入输出都重新开始并预设为未匹配 ,在某次迭代 中完成的连接在后面的迭代中继续保持 (即使存在 更多的匹配数 ). 一次迭代的 PIM 算法吞吐率只能 达到 63% ,多次迭代可达到 100%. PIM在硬件实现上复杂度比较高 ,对于一个 16 ×16的交换结构 ,要实现 PIM 算法 ,就需要将近 64 000个复杂的门器件. iSL IP每次迭代也是请求、响应、接受 3个步骤. 不同的是 ,在第 2步的响应中 ,输出端口收到请求 后 ,从它的固定循环列表里选择当前 Grant指针指 向的输入端口 ,输出端口通知所有输入端口说明其 请求是否被响应 ,当且仅当该响应在第 3步里得到 确认接受后 , Grant指针才增加 1 (模 N )指向下一输 入端口 ;在第 3步接受中 ,输入端口按照固定循环列 表选择响应信号 ,当某个输出端口被接受时 , Accep t 指针模 N 加 1指向下一输出端口. 这种指针更新方 法克服了 PIM的不公平性 ,不仅可以预防端口出现 饥饿现象 ,还使响应仲裁器趋向于非同步工作 ,可快 速实现端口间的最大匹配. 实现 iSL IP算法的硬件需要包含 2N 个仲裁器 : N 个用于输出端的响应仲裁器 , N 个用于输入端的 接受仲裁器 ,每个仲裁器有 N 个可编程的输入优先 级解码器. 实现 iSL IP算法需要的门器件数量比 PIM 少了一半. 1. 2 最大权重匹配算法 最大权重匹配算法的目标是使匹配边的总权重 达到最大 ,除考虑输入队列是否为空外 ,还要考虑队 列长度或排队时间等权重因素 ,因此请求信号长度 由 1位变为多位. 在容许的信元流量下 ,不论是否均 匀 ,最大权重匹配算法都可以达到 100%的吞吐量. 常用的迭代近似 MWM 算法有 :最长队列优先算法 ( iterative long queue first, iLQF)、等待最久信元优先 算法 ( iterative old cell first, iOCF) [ 9211 ]、最久端口优 先算法 ( iterative long port first, iLPF) [ 3, 6, 10211 ]等. iLQF是 LQF的迭代算法 ,也包括请求、响应、接 受 3个迭代步骤 , 权重 W ij ( n )等于输入队列长度 Lij ( n). 其输入端发送的请求信号为该队列的长度 信息 ,该请求信号字宽 2b,其中 b由输入队列的最 大长度 Lmax决定 ,即 2b≤Lmax . iLQF算法有可能出现 饿死现象. iOCF 是 OCF 的迭代算法 , 算法权重 W ij ( n)等于输入队列队首信元的等待时间 Tij ( n). iOCF算法不会出现饿死现象 ,因为如果有队首信元 得不到服务的话 ,那么它的权重 Tij ( n)会一直增加 ·266· 智 能 系 统 学 报 第 3卷
第3期 张重洋，等：基于输入排队的高速交换调度算法研究 ·267 到得到服务为止.DCF其余性质和LQF一样 先清单.信元的紧急值定义为在仿真的FOOQ队 LPF是LPF的迭代算法，其权值定义为 列中，排在该信元前面的信元的个数.输入端口根 R,(n)+C;(n),Li(n)>0. 据队首信元的紧急值为每个输出端口赋一个优先值 Wg(n) (0,J,(nl=0 并建立相应的优先清单 式中：Lg(n)是第n时隙队列Q,的长度.Rg(n)= 在JM(jined preferred matching)liJ和CCF (critical cell first)us1算法中，输入优先清单的信元 ,()为输入占有，表示输入端口在第n时隙 分别按等待时间和输出占有排列.与MUCFA算法 所有缓冲队列总和：C,(n= ∑Lg(n)为输出占 一样，JM和CCF算法的输出优先清单的信元按紧 急值排列」 有，表示所有要发送到输出端口的信元缓冲队列 LOOFA lowest output occupancy first algo- 长度总和，LP℉匹配总权重等于所有已匹配输入与 rim)161算法的输入优先清单与CCF算法相同，输 输出的总和.LP℉迭代有2个步骤：1算法按输入与 出优先清单按信元等待时间排列，LOOA可以在传 输出的占有率建立一个排序表：2从最大占有端口 输流级限制每个分组的传输延迟 开始至最小占有端口，通过循环迭代，找到最大容量 表2稳定结合类算法综合比较 匹配.由于在第一步中己已经将请求信号按权重排序， Ta ble2 The com prehensive com parison of GSAs 因此在第2步中无需对请求权重进行比较，使得算 算法输入优先清单输出优先清单加速比时间复杂度 法容易由硬件实现 表1M9M类与MWM类算法的综合比较 MUCEA 紧急值 紧急值 0w2) Tablel The com prehensive com parison of MSM and JMM 等待时间 紧急值 2 0w2) MWM algor ithms CCF 输出占有 紧急值 0N2) 最大吞 算法 权重 时间复杂度 稳定性公平性 LOOFA输出占有 等待时间 0N2) 吐率% MM 100 010w23) 表2列出了稳定结合类算法的一些特性比较 从表中可以看出，与最大匹配类算法相比，稳定结合 PM 100 0/1 O(N*bgN) 本 算法除需要加速比外，还有以下特点：)某些输入 iS P 100 0/1 O(i*N*logN) 是 输出端口的优先清单可能是不完全的，结果有可能 MWM 100 W尊 O(N3*bgN) 导致稳定结合数降低，算法性能下降；2)在算法中， LQF 100 O(i*b*bgN) + 否 一个已建立的连接在随后的迭代中可能被拒绝，这 OCF 100 Ty o(i*b*bgN) + 是 是与最大匹配算法的显著区别：3)目前没有证明稳 LPF 100 R:+C,0W2) 定结合算法带宽的利用效率及是否会导致饿死现 MWM算法需要2W个仲裁器和一个权重寄存 象，但算法会偏重于输入或输出的某一方：4)稳定 器，每个响应仲裁器需要2N个比较器，按信号权重 结合不一定有最大权重，而最大权重也不一定是稳 信息给予优先匹配.MWM算法的硬件复杂度要比 定结合1 改P高 14神经网络算法 13稳定结合匹配算法 人工神经网络具有高度的并行处理能力和快速 稳定结合问题2/(stable marriage matching)最 收敛的特性，特别是HNN(hopfield neural netork) 早由Gale和Shap ley提出，因此该算法称为GSA 擅长解决优化问题，因此可以用HNN实现信元调度 (Gale-Shap ley algorithm),GS4算法利用输入输出端 器功能18201 口定义的优先级清单寻找稳定的输入输出匹配.如 采用的HNN包含NW个神经元，分别对应于 果在没有完成匹配的输入输出端口集合中不能发现 VOQ输入端口NW个缓冲器队首信元的服务状 一个端口，其优先级比己匹配的端口高，那么就称己 态，整个网络的状态可用NW矩阵表示.NN经 完成匹配的输入输出端口是稳定的 过迭代收敛到稳定状态时，若矩阵元素(；为1，则 MUCFA(most urgent cell first algorithm)算法 表示对应的神经元处于激发状态，相应的队首信元 利用GS4和输入输出优先清单寻找稳定结合匹配. 被送入交换结构，为0则表示神经元处于抑制状态 输出端口根据队列Q,队首信元的紧急值(urgent 相应的队首信元不被送入交换结构， vaue)为输入端口i赋一个优先值并建立相应的优 神经元的输入输出关系为 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
到得到服务为止. iOCF其余性质和 iLQF一样. iLPF是 LPF的迭代算法 ,其权值定义为 W ij ( n) = Ri ( n) + Cj ( n) , Lij ( n) > 0, 0, Jij ( n) = 0 . 式中 : Lij ( n)是第 n时隙队列 Qij的长度. Rij ( n) = ∑ N j=1 Lij ( n) 为输入占有 ,表示输入端口 i在第 n时隙 所有缓冲队列总和; Cij ( n) = ∑ N i =1 Lij ( n) 为输出占 有 ,表示所有要发送到输出端口 j的信元缓冲队列 长度总和 , iLPF匹配总权重等于所有已匹配输入与 输出的总和. iLPF迭代有 2个步骤 : 1算法按输入与 输出的占有率建立一个排序表; 2从最大占有端口 开始至最小占有端口 ,通过循环迭代 ,找到最大容量 匹配. 由于在第一步中已经将请求信号按权重排序 , 因此在第 2步中无需对请求权重进行比较 ,使得算 法容易由硬件实现. 表 1 MSM类与 MWM类算法的综合比较 Table1 The com prehen sive com par ison of M SM and MWM a lgor ithm s 算法 最大吞 吐率 % 权重 时间复杂度 稳定性 公平性 MSM 100 0 /1 O (N 2. 5 ) - P IM 100 0 /1 O (N 3 logN ) - 否 iSL IP 100 0 /1 O ( i3 N 3 logN ) - 是 MWM 100 W ij O (N33 logN ) + iLQF 100 Lij O ( i3 b3 logN ) + 否 iOCF 100 Tij O ( i3 b3 logN ) + 是 iLPF 100 Ri + Cj O (N 2 ) + 是 MWM 算法需要 2N 个仲裁器和一个权重寄存 器 ,每个响应仲裁器需要 2N 个比较器 ,按信号权重 信息给予优先匹配. MWM 算法的硬件复杂度要比 iSL IP高. 1. 3 稳定结合匹配算法 稳定结合问题 [ 12 ] ( stable marriage matching)最 早由 Gale 和 Shap ley提出 ,因此该算法称为 GSA (Gale2Shap ley algorithm) , GSA算法利用输入输出端 口定义的优先级清单寻找稳定的输入输出匹配. 如 果在没有完成匹配的输入输出端口集合中不能发现 一个端口 ,其优先级比已匹配的端口高 ,那么就称已 完成匹配的输入输出端口是稳定的. MUCFA (most urgent cell first algorithm) [ 13 ]算法 利用 GSA和输入输出优先清单寻找稳定结合匹配. 输出端口 j根据队列 Qij队首信元的紧急值 ( urgent value)为输入端口 i赋一个优先值并建立相应的优 先清单. 信元的紧急值定义为在仿真的 FIFO2OQ队 列中 ,排在该信元前面的信元的个数. 输入端口 i根 据队首信元的紧急值为每个输出端口赋一个优先值 并建立相应的优先清单. 在 JPM ( joined p referred matching) [ 14 ] 和 CCF ( critical cell first) [ 15 ]算法中 ,输入优先清单的信元 分别按等待时间和输出占有排列. 与 MUCFA 算法 一样 , JPM和 CCF算法的输出优先清单的信元按紧 急值排列. LOOFA ( lowest output occupancy first algo2 rithm) [ 16 ]算法的输入优先清单与 CCF算法相同 ,输 出优先清单按信元等待时间排列 , LOOFA可以在传 输流级限制每个分组的传输延迟. 表 2 稳定结合类算法综合比较 Table2 The com prehen sive com par ison of GSA s 算法 输入优先清单输出优先清单 加速比 时间复杂度 MUCFA 紧急值 紧急值 4 O (N 2 ) JPM 等待时间 紧急值 2 O (N 2 ) CCF 输出占有 紧急值 2 O (N 2 ) LOOFA 输出占有 等待时间 2 O (N 2 ) 表 2列出了稳定结合类算法的一些特性比较. 从表中可以看出 ,与最大匹配类算法相比 ,稳定结合 算法除需要加速比外 ,还有以下特点 : 1)某些输入 输出端口的优先清单可能是不完全的 ,结果有可能 导致稳定结合数降低 ,算法性能下降; 2)在算法中 , 一个已建立的连接在随后的迭代中可能被拒绝 ,这 是与最大匹配算法的显著区别; 3)目前没有证明稳 定结合算法带宽的利用效率及是否会导致饿死现 象 ,但算法会偏重于输入或输出的某一方; 4)稳定 结合不一定有最大权重 ,而最大权重也不一定是稳 定结合 [ 17 ] . 1. 4 神经网络算法 人工神经网络具有高度的并行处理能力和快速 收敛的特性 ,特别是 HNN ( hopfield neural network) 擅长解决优化问题 ,因此可以用 HNN实现信元调度 器功能 [ 18220 ] . 采用的 HNN包含 N ×N 个神经元 ,分别对应于 VOQ输入端口 N ×N 个缓冲器队首信元的服务状 态 ,整个网络的状态可用 N ×N 矩阵表示. HNN 经 过迭代收敛到稳定状态时 ,若矩阵元素 ( i, j)为 1,则 表示对应的神经元处于激发状态 ,相应的队首信元 被送入交换结构 ,为 0则表示神经元处于抑制状态 , 相应的队首信元不被送入交换结构. 神经元的输入输出关系为 第 3期 张重洋 ,等 :基于输入排队的高速交换调度算法研究 ·267·
·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.net
V = [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卷
第3期 张重洋，等：基于输入排队的高速交换调度算法研究 ·269· com. [17]KAM A C,SU K Y.LinearComplexity algorithms for [6 ]MCKEOWN N.The isL IP scheduling algorithm for input- QoS support in input-queued switches with no peedup queued svitches[J ]IEEE/ACM Transactions on Netor [J].IEEE Joumal on Selected A reas in Communications, kmg,1999,7(2):188-201 1999,17(6):1040-1056 [7]MCKEOWN N.A fast switched backplane for a Gigabit [18 ]AL IM.NGJYEN H Neural netork mp lementation of an switched router J ]Business Communications Review, input access scheme in a high speed packet switch [C]// 1997.27(12):1-30. IEEE GOBECOM.Dallas,USA,1989:1192-1196. [8 ]HOPCROFT J E,KARP R M.An O(n5/2)algprithm for [19张便利，常胜江，李江卫，等.实现虚拟输出队列调度的 maxium matching in bpartite graphs[J].Society for I- 神经网络算法[J]光电子·激光，2005,161316-1320 dustrial and Applied Mathematics Comput,1973(1):225- ZHANG B ianli,CHANG Shengjiang,L I Jiangvei et al 231 A neural nework method achieving virtual ouput queuing [9 ]MCKBOWN N,MEKKIITIKUI A,ANANTHARAM V, scheduling[J ]Joumal of Op toelectronics Laser,2005, WALRAND J.Achieving 100%throughput in an input- 16:1316-1320 queued switch [J]EEE Transaction Communication, [20]SU XX,CHANG S J,MA TB.A neural network model 1999,47(8):1260-1267. for traffic prediction in AIM netorks[J ]Joumal of Op- [10 ]MCKEOWN N.Scheduling algorithms for input-queued toelectronics.Laser,2003.14(8):842-850 cell switch [D ]Berkeley:University of Califomia at [21 MARRAKCHIA,TROUDET T A neural net arbitrator or Berkeley,1995 large crossbar packet-switches[J]EEE Transactions on [11 TARJAN R E Data structures and nework algorithms Circuits and Systems,1989(7)1039-1041. [C]//Conference on society or Industrial and Applied [22 1B ANCO A,FRANCESCH N ISM,GH ISOLFIS,HLL A Mathematics,Pennsylvania,1983:105-109 M,LBONARDI E,NER I F,WEBB R.Frame-based [12 GALE D,SHAPLEY L S College adm ission and the sta- matching algprithms for input-queued switches [J ]IEEE bility of marriage [J ]American Mathematical Monthly, Communications ociety,2002,2(2):69-76 1962.69:9-15 [23 ]KAR K,LAKSHMAN TI Reduced comp lexity input buff- [13 PRABHAKAR P,MCKEOWN N.On the speed-up re- ered switches[EB /OL ]2007-07-11 ]htp://www.bell- quired or combined input and ouput queued switching labs com user/stiliadi/publications [RJ.Sanf6rdC9-1R-97-738,1997 作者简介： [14 ]STO CCA I ZHANG H Exact emulation of an output queu- 张重洋，男，1984年生，硕士研究 ing switch by a combined input and output queuing switch 生，主要研究方向为人工神经网络与通 [C ]//Proceedings of the IEEE WQoS Napa:IEEE 信信息系统」 Communications Society,1998:218-224. [15 ]CHUANG S T,GOEL A,MCKEOWN N Matching ouput queuing with a combined input/ouput-queued switch[J] EEE Joumal on Selected A reas in Communications,1999. 17(6):1030-1039 申金媛，女，1966年生，教授，博士， [16]KR ISHNA P,PATEL N,CHARNY A,SMCOE R On 主要研究方向为人工神经网络、光电通 the speed-up required for work-conserving crossbar swit- 信及信息处理、模式识别.已在国内外 ches[J].IEEE Joumal on Selected A reas in Communica- 核心学术期刊上发表论文70余篇，其 tions..1999,17(6):1057-1066 中被SC和E收录引用达60多篇次 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
com. [ 6 ]MCKEOWN N. The iSL IP scheduling algorithm for input2 queued switches[ J ]. IEEE /ACM Transactions on Networ2 king, 1999, 7 (2) : 1882201. [ 7 ]MCKEOWN N. A fast switched backp lane for a Gigabit switched router [ J ]. Business Communications Review, 1997, 27 (12) : 1230 . [ 8 ]HOPCROFT J E, KARP R M. An O ( n5 /2) algorithm for maximum matching in bipartite graphs[J ]. Society for In2 dustrial and App lied Mathematics Comput, 1973 ( 1 ) : 2252 231. [ 9 ] MCKEOWN N, MEKKITTIKU I A, ANANTHARAM V, WALRAND J. Achieving 100% throughput in an input2 queued switch [ J ]. IEEE Transaction Communication, 1999, 47 (8) : 126021267. [ 10 ] MCKEOWN N. Scheduling algorithm s for input2queued cell switch [ D ]. Berkeley: University of California at Berkeley, 1995. [ 11 ] TARJAN R E. Data structures and network algorithm s [C ] / /Conference on society for Industrial and App lied Mathematics, Pennsylvania, 1983: 1052109. [ 12 ] GALE D, SHAPLEY L S. College adm ission and the sta2 bility of marriage [ J ]. American Mathematical Monthly, 1962, 69: 9215. [ 13 ] PRABHAKAR P, MCKEOWN N. On the speed2up re2 quired for combined input and output queued switching [R ]. Stanford CSL2TR2972738, 1997. [ 14 ] STO ICA I, ZHANG H. Exact emulation of an output queu2 ing switch by a combined input and output queuing switch [ C ] / /Proceedings of the IEEE IWQoS. Napa: IEEE Communications Society, 1998: 2182224. [ 15 ]CHUANG S T, GOEL A, MCKEOWN N. Matching output queuing with a combined input/output2 queued switch[J ]. IEEE Journal on Selected A reas in Communications, 1999, 17 (6) : 103021039. [ 16 ] KR ISHNA P, PATEL N, CHARNY A, SIMCOE R. On the speed2up required for work2conserving crossbar swit2 ches[J ]. IEEE Journal on Selected A reas in Communica2 tions, 1999, 17 (6) : 105721066. [ 17 ] KAM A C, SIU K Y. L inear2Comp lexity algorithms for QoS support in input2queued switches with no speedup [J ]. IEEE Journal on Selected A reas in Communications, 1999, 17 (6) : 104021056. [ 18 ]AL IM. NGUYEN H. Neural network imp lementation of an input access scheme in a high speed packet switch [ C ] / / IEEE GLOBECOM. Dallas,USA, 1989: 119221196. [ 19 ]张便利 ,常胜江 ,李江卫 ,等. 实现虚拟输出队列调度的 神经网络算法 [J ]. 光电子 ·激光 , 2005, 16: 131621320. ZHANG Bianli, CHANG Shengjiang, L I Jiangwei, et al. A neural network method achieving virtual output queuing scheduling[J ]. Journal of Op toelectronics·Laser, 2005, 16: 131621320. [ 20 ] SU X X, CHANG S J, MA T B. A neural network model for traffic p rediction in ATM networks[J ]. Journal of Op2 toelectronics·Laser, 2003, 14 (8) : 8422850. [ 21 ]MARRAKCH IA, TROUDET T. A neural net arbitrator for large crossbar packet2switches[J ]. IEEE Transactions on Circuits and System s, 1989 (7) : 103921041. [ 22 ]B IANCO A, FRANCESCH IN ISM, GH ISOLF I S, H ILL A M, LEONARD I E, NER I F, W EBB R. Frame2based matching algorithm s for input2queued switches[ J ]. IEEE Communications society, 2002, 2 (2) : 69276. [ 23 ] KAR K, LAKSHMAN Tl. Reduced comp lexity input buff2 ered switches[ EB /OL ]. 2007207211 ]. http: / /www. bell2 labs. com / user/stiliadi/publications. 作者简介 : 张重洋 ,男 , 1984 年生 ,硕士研究 生 ,主要研究方向为人工神经网络与通 信信息系统. 申金媛 ,女 , 1966年生 ,教授 ,博士 , 主要研究方向为人工神经网络、光电通 信及信息处理、模式识别. 已在国内外 核心学术期刊上发表论文 70余篇 ,其 中被 SCI和 EI收录引用达 60多篇次. 第 3期 张重洋 ,等 :基于输入排队的高速交换调度算法研究 ·269·
