第24 卷第9 期2003 年9 月
小型微型计算机系统
考试培训机构M IN I- M ICRO SYST EM S
V o l124 N o. 9
Sep. 2003 i SL IP 调度算法研究及其实现
刘化君1, 刘斌2
1(南京工程学院计算机工程系, 江苏南京210013)
2(清华大学计算机科学与技术系, 北京100084)
摘要: 目前, 为提高交换系统吞吐率, 设计开发高性能网络交换机或路由器内部交换结构的技术已趋成熟. 但易于在硬件中实现的、高效的队列调度算法仍然是一项值得研究的重要技术. 文章首先讨论了对于输入缓冲采用 F IFO 队列交换系统, 其吞吐率主要受HOL 队首阻塞的影响. 然后研究了iS L IP 调度算法的基本原理、迭代仲裁步骤及它在硬件中的实现. 针对硬件交换转发判决这一关键问题, 给出了在输入队列交
换机中采用虚拟输出队列的交换结构和多优先级调度算法的硬件实现方案. 最后, 对iS L IP 算法的性能进行了分析比较, 证明iSL IP 算法的实现方案不仅实现简单, 而且具有良好的特性.
关键词: 队列调度; 交换结构; HOL 阻塞; 迭代匹配调度算法
中图分类号: T P 393 文献标识码: A文章编号: 100021220 (2003) 0921593204
Rearch of an iSL IP Schedul in g A lgor ithm and its I m plem e n ta t ion
L IU H ua2jun1 , L IU B in2
1(D ep artm ent of C om p u t er S cience and T echnology , N anj ing Institu te of T echnology , N anj ing 210013, China) 2(D ep artm ent of C om p u t er S cience and T echnology , T sing hua U niversity , B eij ing 100084, Chin a)
Abstract: Cu r ren t techno logy developm en t m akes it feasib le to bu ild ex t rem ely h igh th roughp u t sw itch and rou ter, w h ich exp licit emp loys sw itch ing h igh2p erfo rm ance fab ric. Ho w ever, the rearch of schedu lin g algo rithm w ith h ig h efficiency and easin ess is still a challenge. In th is paper, w e firstly discu ss that the facto r of th roughp u t is affected
m o stly by HOL (h ead of line b lock ing) , fo r inpu t buffered w ith F IFO queues p er inpu t po r t. T hen, w e in t roduce the p rincip le of iS L IP schedu ling algo rithm , step arb it rat io n of iS L IP fo r one iterat io n and its im p lem en tat io n in hardw are. W e describe the im p lem en tat i o n of a schedu lin g algo rithm fo r configu ring cro ssbar in inpu t2queued sw itches th at sup 2 po rt virtual o u tpu t queues an d m u lt i p le p r i o ritie s.In the end of pap er, analy sis an d compar ison of iSL IP algo rithm per2 f o rm ance ar e m ade, the resu lts show s it s easiness to be im p lem en ted and good perfo rm ance.
Key words: queue schedu ling; sw itch ing fab ric; HOL b lock ing; iterative m atch ing schedu ling algo rithm
1 引言
在分组交换网络中, 队列调度算法运行在网络节点中发生冲突需排队等待调度之处, 它按照一定的服务规则对交换节点的不同输入业务流分别进行调度和服务, 使所有的输入业务流能按预定的方式共享交换节点的输出链路带宽. 目前, 网络交换系统的交换方式主要有交叉开关型、共享存储器型及总线型三种. 其中交叉开关型交换方式又称C ro ssbar Sw itch, 它采用硬件的交叉开关式的互连网络实现交换.
C ro ssbar Sw itch 的交换控制主要由C ro ssbar 交叉开关和控制逻辑实现. 交叉开关负责提供从源端
zoom怎么读口到相应目的端口信息交换的物理链接, 而控制逻辑则用以控制这些物理链接的建立和拆除. 由于C ro ssbar 结构是所有输出线卡之间的一个集中资源, 保持它的高效率非常重要. 当然C ro ssbar 结构在本质上是无阻塞的, 但实际存在队首位置阻塞(HOL : H ead of L ine B lock ing) 等影响其执行效率. HOL 产生的原因在于输入端口等待交换的分组使用 F IFO 输入排队策略. 即当一个分组移动到输入队列的队首时, 如果目标输出端口正忙, 则它将在该队列中等待, 直到目标端口空闲. 当某一个输出端口空闲时, 它交换最先处于等待位置的分组. 也就是说, 每个时隙到达时, 只有在缓冲器队首位置的分组才能参与输出端口的竞争, 且每个输出端口最多只能接受一个分组. 显而易见, 在F IFO 队列中, 当队首的分组受阻时, 跟在其后的所有准备发送的分组也都将受阻. 即使当前时隙该分组指向的输出端口处于空闲状态也无法参与交换, 分组被挂起在输入端口中而让此时空闲的输出端口处于“饥饿”( starving). 从理论分析和计算机模拟研究可知, 对于输入缓冲采用F IFO 队列的N 3 N 交换机, 由于HOL 阻塞的影响, 在相同随机流量情况下, 交
收稿日期: 2001211213 基金项目: 国家自然科学基金课题(60173009) 和985 项目资助作者简介: 刘化君, 教授, 主要研究方向为计算机网络体系结构, 宽带网数据交换技术及In ternet Q oS 服务质量保证; 刘斌, 教授, 博士生导师. 主要研究方向为宽带网数据交换技术理论与方法学, 高速信息网络控制协议和性能评价, Q oS 控制和多媒体业务量行为分析.
k k 1594
小 型 微 型 计 算 机 系 统
2003 年
换 端口能达到的最大吞吐率被限制在 ( 2 -
2 ) = 58.
6%〔1〕. 可见 HOL 阻塞将浪费 C ro ssbar 一半多的带宽.
为克服 F IFO 输入队列所产生的影响, 出现了许多旨在 消除 HOL 阻塞现象、提高吞吐率的排队规则和调度算法. 当 然, 目前为提高交换系统吞吐率, 设计开发高性能网络交换机 或路由器内部交换结构的技术已趋成熟. 但易于在硬件中实 现的、高效的队列调度算法仍然是一项值得研究的重要技术. 尤其是在 C ro ssbar 交换系统中更是如此. 本文将就如何实现 硬件交换转发判决这关键问题, 探讨研究一种高效、易于实现 的队列调度算法, 并给出其硬件实现方案.
2 滑动迭代轮循匹配 ( iSL IP ) 算法
匹配算法研究在输入与输出端口之间建立双向匹配的问 题. 所谓匹配是指能够在输入端口与输出端口之间建立起连 接的最大匹配数量. 最初D EC 系统研究中心在研究 16 端口 的 1Gbp s AN 2 交换机时,
为解决HOL 阻塞问题, 提出了一种 基于时序的并行迭代匹配 (P I M : Par allel Iterative M atch ing ) 算法. 对采用 P I M 算法的一个 N 3 N 交换网络在一次迭代
后, 其最大吞吐率为 63% , 平均迭代次数 (即时间复杂度) 为 O ( l og 2N ). 通过计算机模拟表明它具有高吞吐率. 对于 163 16 的交换系统, 只需要迭代 4 次, 数据吞吐率可达 97%〔2〕. 但
联系人的英文缩写是 P I M 算法在硬件实现上的复杂性会带来时间上的开销. 为
了改进 P I M 算法中存在的复杂性和非公平性问题, 提出了 iS L IP 算法.
2. 1 iSL IP 算法
iS L IP ( iterat ive ro un d 2ro b in m atch in g w ith sli p ) 算法的 目的是为了有效、公平、快速地匹配一个输入队列调度器的输 入端口和输出端口. 它是一种迭代 ( iterat i o n ) 算法, 在每个时 隙, 采用多次迭代来选择交叉开关的配置, 使输入端口和输出 端口尽量达到匹配. iS L IP 算法采用轮循匹配 RR M (Ro un d 2 Ro b in M atch in g ) 算法来轮流调度每个有效输入端口和输出 端口, 而且 R R M 是一种优先级轮循匹配算法, 用于仲裁输入 ƒ输出端口之间的匹配.
例如, 对于一个支持 4 优先级的 16 端口调度器保持的队 列, 在每个时隙开始, iS L IP 算法调度器检查所有队列的内 容. 所有的输入端口和输出端口在每次迭代开始时都是未建 立匹配的. 在每次迭代过程中未被匹配的输入输出端口才能 参加下次匹配, 即每次成功的迭代增加额外的连接. 为了跟踪 下面支持哪个连接, 每个输出端口为优先级保持一个单独的 允许 (gran t ) 指针 g j , j 为输出端口号, k 为优先级, j = 1, 2, , 16; k = 1, , 4. 每个输入端口为每个优先级保持一个单独的 接受
(accep t ) 指针 a i , i 为输出端口号, k 为优先级, i = 1, 2, , 16; k = 1,
, 4. 与 P I M 相似, iS L IP 算法每次迭代也由三
个步骤组成:
① 请求 (R equest ). 每个输入端口向每一个具有分组 (信 元) 队列缓冲的输出端口发出一个最高优先级的请求 ( r e 2 quest ) 信号.
② 准许 (Gran t ). 如果一个未匹配的输出端口收到任何
请求信号, 它必须选择一个. RRM 调度算法从最高优先级的 端口位置开始, 固定地从下一个出现的 R equest 信号中选择, 输出端口通知每一个输入端口其请求是否被准许. 当 Gran t 信号发出后, 按照 RRM 调度算法, 只有在第三步中准许信号 被输入端口所接受, 在输出端口指向最高优先级位置的指针 g j 按模N 增加, 指向向输入端口发出准许信号的下一个输出 端口位置.
③ 接受 (A ccep t ). 如果一个未匹配的输入端 口 收 到 Gran t 信号, 它只能接受一个. RRM 调度算法从最高优先级 的端口位置开始, 固定地从下一个出现的 Gran t 信号中选择. 按照 RRM 调度算法, 指向最高优先级元素的指针 a i 按模 N 增加, 指向接受端口信号的下一个位置.
注意, 为了避免饥饿, 指针只在第一次迭代后被更新.
2. 2 iSL IP 算法调度过程及调度实例
我们以图 1 作为一个调度实例, 说明 iSL IP 调度算法在 一次迭代中的实际调度过程〔3〕. 图中 g 2、g 4 是输出端口 2、4 的 Gran t 仲裁器, a 1 是输入端口的A ccep t 仲裁器. 开始时, 所有 的输入端口与输出端口是未建立匹配的.
图 1 iS L IP 算法在一次迭代中的三个步骤
F ig . 1 T he th ree tup s that m ake up one iter at i o n
of the iSL IP algo r ithm
① 请求 (R equest ). 输入端口 1 和输入端口 3 各有一个 以上的分组向具有分组队列缓冲的输出端口 1、2 和 4 发出请
求 ( r equest ) 信号, 其它端口亦如此.
② 准许 (Gran t ). 由于输出端口仲裁器的指针 g 2 = 1、g 4
= 1, 输出端口 1 和 2 都向输入端口 1 发出 Gran t 信号. 同理, 输出端口 4 向输入端口 3 发出 Gran t
信号. 注意, 当 Gran t 信 号发出后, 按照 RRM 调度算法, 只有在第三步中准许信号被 输入端口所接受, 在输出端口指向最高优先级位置的指针 g 1、g 2、g 4 才能得到更新, 并按模增加, 指向下一个接受 R e 2
quest 信号的输出端口位置.
③ 接受 (A ccep t ). 未被匹配的输入端口从 Gr an t 信号中
选择其一. 由于这时 a 1 = 1, 输入端口接受了输出端口 1 的 gran t 信号, 两端口之间的匹配成功后, 指针 a 1 按模增加指向 输出端口 2, 这时已匹配的输出端口指针 g 1 和 g 4 随之更新, 指向下一个向输入端口发出 Gran t 信号的位置. 注意, 未成功 匹配的指针 g 2 不更新. 同理, 输入指针 a 1 按模增加并指向 2.
9 期刘化君等: iSL IP 调度算法研究及其实现1595
在一次迭代结束后, 如果仍有未匹配的请求, 那末将在下次迭代中匹配. 例如输入端口1 与输出端口2 或输入端口 3 与输出端口2 将在下一次建立匹配.
3 iSL I P 算法的实现
iS L IP 算法的主要特点是它的简单性, 可以比较容易地在硬件中实现并高速执行, 能均等地分配带宽, 并且更公正地实现请求连接.
2020考研英语一答案
3. 1 iSL IP 算法调度器的硬件实现列的内容, 并且在输入端口与输出端口之间寻找一个无冲突的匹配. 实现框图如图3 所示.
理论上, 如果使用VOQ , 对一个具有简单F IFO 队列的C ro ssbar 交换机来说, 能够使其吞吐率从60% 增加到100%. 这是由于HOL 阻塞已经被完全消除了: 没有分组会因为前面有不同输出端口的分组而被阻塞. 显然实现VOQ 方式的代价是硬件控制复杂. 在硬件条件允许的情况下, 可以在设计中采用VOQ 机制消除HOL 影响.
3. 3 iSL IP 算法调度器的流水线方案
图2 iS L IP 算法调度器的硬件实现框图
F ig. 2 B lock diagram of the iSL IP algo rithm schedu ler
3. 2使用虚拟输出队列调度算法
消除输入队列交换机的HOL 现象, 提高系统的吞吐率, 一个有效地办法是采用虚拟输出队列(V irt ual O
u tpu t Q ueuein g, VOQ )〔5〕.即在每个输入端口, 对应每个输出端口都设有一个 F IFO 队列. 输入端口接收到一个分组时经过决策判定它的目的输出端口, 这个分组(信元) 就被放在对应的
图3 用VOQ (虚拟输出队列) 消除H OL
F ig. 3 HOL is elim inated by u sing a VOQ
F IFO 队列中. 然后, 由一个集中的调度算法检查所有输入队3. 4 iSL IP 算法的快速轮循仲裁机制
由图 2 所示调度器框图可知, 来自于准许2接受仲裁的延迟会直接影响调度算法的速率. 为了做到快速仲裁, 需设计一个保存轮循指针的可编程优先级译码器PP E (P rogramm ab le P r io rity Encoder) , 形成快速轮循仲裁机制, 如图5 所示. 图中
图5 快速轮循仲裁机制框图
F ig. 5 B lock diagram of a round2rob in arb iter
P_ enc 为轮循指针, 宽度为log2N 比特, 指向当前最高优先级的输入端口.
4 结束语
iS L IP 算法是一种针对定长分组(信元) 的输入排队调度算法, 采用虚拟输出队列和优先机制, 可有效地消除HOL 阻塞, 提高系统的吞吐率. 在均衡流量负载情况下, 将iSL IP 算
iS L IP 算法的一个重要特性〔4〕就是易于实现, 一个163
16 端口的调度器硬件实现框图如图2 所示. 图中队列调度器
算法的请求、准许和接受三个步骤对应三个方框. 调度器设计
为163 16 端口、每次调度时隙51n s, 由多轮循仲裁器实现iS2
L IP 调度算法.
设计调度器的运行速度为175 M H z, 每一个时隙由9 个
blow
时钟周期构成, 这样大约用51n s 可完成iS L IP 的三次迭代.
调度器的迭代过程用流水线方式实现. 一次迭代的“接受”过
程与下一次迭代的“准许”过程重叠. 显然, I 次迭代仅需要2 I
+ 2 个时钟周期. 调度器的“准许、接受”流水线方案如图4 所
美籍华人英语示. 注意, 迭代的每一步骤花费2 个时钟周期, 最后一个时钟
周期用于更新轮循指针并准备下一个时隙.
图4 调度器的准许2接受流水线方案
F ig. 4 T h e gran t2accep t p i p e lin e o f sch edu ler
1596 小型微型计算机系统2003 年
法与P I M、i L R U 、i L Q F 在不同迭代次数中的最大吞吐率进行比较可知, iS L IP 算法具有以下良好特性〔6〕.
高吞吐率. 通过模型仿真表明, iSL IP 算法在均衡流量负载下的性能非常好, 当分组均衡地以Bern o u li 分布到达输入端口时, 通过仔细控制仲裁器材的指针, 在一次迭代中, iS L IP 算法的吞吐率可达100%.
不会产生端口饥饿. 如果一个输入端口未收到某个输出端口的准许(Gr an t) 信号, 它将不断地向这个输出端口发出请求(R equest) 信号, 直至匹配成功为止, 因此没有端口连接饥饿.
在重负载下, 所有具有同一输出端口的队列具有相同的吞吐率.
快速. iSL IP 算法保证在最多N (端口数) 次迭代后收敛. 然而, 实际中iSL IP 算法通常少于L og2N 次迭代后收敛. 就是说对于一个16 端口的调度器4 次迭代足够了.
易于硬件实现. iSL IP 算法可以快速有效地匹配一个输入队列调度器的输入和输出, 不仅具有高吞吐率, 而且易于在硬件中实现. 一个iS L IP 算法调度器由2N 个可编程优先级译码器构成. 对于一个16 端口的调度器可以设计在一个单片FPGA 中, 如A ltera 公司的EP F 10K100A 21, 使用资源约为5 万门. 实验设计证明, 所提出的iSL IP 队列调度算法实现方案不仅能较好地解决硬件交换转发判决问题, 而且具有很好的功能特性.
References:
familiarization1Karo l, M. and M o rgan, S. Input versus out put queuing on a space division sw itch 〔J〕.IEEE
游学夏令营T rans, Comm unicat ion s, 1987,
35 (12) : 1347～1356.
2Gee N ong, Jogrsh K. M upala, M ounir H a m d i. A nalysis of non2 block ing A TM sw itches w ith m ult i p le i nput queues 〔J 〕. I EEEƒ
A CM T ransact ion s on N etwo rk ing. F eb. 1999, 7 (1) : 60～63.
3N ick M ckeow n and M artin Izzard. T he T iny T era: A Packet Sw itch Co re 〔J〕.IEEE M icro M agazine, Jan. 2Fe b. 1997, 17
(1) : 26～33.
4Pankaj Gup ta and N ick M ckeow n. D esign and im p le m ent at i on of
a f ast cro ssbar scheduler 〔J〕.IEEE M icro M agazine, Jan. 2Feb.
1999, 19 (1) : 20～28.
妙狗拯救圣诞节
5Karp R , V azirani U , V azirani V. A n op t im al algo rithm f o r on2 line b ip artit e m at ch ing 〔C〕.
In: P roc. 22nd A CM Symp. on T he2 o ry of Com puting, M aryl and, 1990, 352～358.
楚门的世界英语影评6N ick M cke ow n. i SL I P: A scheduling algo rithm f o r input 2 queued sw itches 〔J 〕. I EEEƒA CM T ransact ion s on N etwo rk ing, A p ril 1999, 7 (2) : 188～201.
