基于CROSSBAR的ISLIP调度算法及其硬件实现

维普资讯

电子科技 20 04年第 9期 (第 10 )总 8期

基于C OS B R S I调度算法及其硬件实现 R S A的iL P占建国，蔡文晖 ,王晓磊，曾兴雯( .中兴通讯股份有限公司技术中心研究部，广东深圳 1 2 .西安电子科技大学通信工程学院，陕西西安 5 85 107 70 7 ) 10 1

摘

要

iLP一种高效的队列调度算法，并且易于硬件实现。该文主要介绍基于C O S A S I是 R S B R交换结构的

调度算"i I原理和及其在硬件中的实现；给出了i I算法和算法的性能分析；并在结构上实现了一个l 6 )S P L L - S P L 6×l的交换仲裁器。 关键词交换结构；调度算法；C O S A LP仲裁器 R S B Ri I; S中图分类号 T 1 .5 N9 50

1前

言

2 C rs a交换结构 os r Bc 0sa rsbr结构可以支持高带宽的原因主要是它采用硬件的交叉开关式的互连网络实现交换。交换

当前，高性能的大容量路由器和交换机所用核心交换技术都可以归结为交换结构 ( w t ar ) s i h bi cF c和调度算法 ( c eue g rh S h d lAl i m)两个方面。交换 ot

结构是宽带I路由器中的关键部分，是解决高速报 P文转发的主要方式，它的性能直接决定了路由器的

控制主要由交叉开关和控制逻辑实现，交叉开关负责提供从源端口到相应目的端口信息交换的物理链接，而控制逻辑则用以控制这些物理链接的建立和拆除。所以 C osa交换结构是宽带路由器、交 rsb r

性能。交换结构一般可采用总线型、共享存储器型及交叉开关型方式实现。虽然计算机工业在近几年引入了越来越高速的共享式总线( S从IA到ES现 IA,在的P I C),但仍然跟不上网络发展的步子。首先，

换机中的一个核心部分，保持它的高效率非常重要。C osa结构在原理上是能够无阻塞的，但是 rs r b

共享总线不可避免内部冲突；第二，共享总线的负载效应使得高速总线的设计难度太大。共享存储器型实现简单、也可以达到比较高的速率 ( 0 b s 2G p ),

在实际的应用中存在线头位置阻塞( O,H a f H L ed o Ln lcig i Bo k )等因素影响其效率，其中最主要的 e n是 H L的影响

。例如在×N的交换结构中，每 O一

但是速率的进一步提高将受到内存存取速度的限制，很难有更大的突破。而交叉开关型 ( rsbr C o saS th N够达到比较高的速率并且扩展性好，已经 wl )￣ c…

个输入端口的所有数据都存放在一个先进先出

( IO) FF队列中，只有当数据到达队列头部的时候， 调度器才考虑进行调度。输出端口相同的数据包会

被广泛地用在高速路由器、交换机中，但是

竞争输出端口，这时由调度器进行调度。由于调度器只能对各个输入 FF队列头部进行判决，在 IO FF队列中，当队首的分组受阻时，跟在其后的 IO所有准备发送的分组也都将受阻。即使当前时隙该

C o sa wi h rsb rS t的速度需要完善的调度算法并用 c高速硬件实现调度器 (c e u )来实现。执行高 sh d l e效调度算法的调度器是C o sa交换结构的核心， rsb r

它在每个调度时隙内收集各输入端口有关数据包队列的信息，经过相关调度算法得到输入端口和输出端口之间的一匹配，提供输入端口到输出个 端口的通路。

分组指向的输出端口处于空闲状态也无法参与交换，分组被挂起在输入端口中，而让此时空闲的输出端口处于“饥饿”( a i )态。因此 H L会 sr n状 tv g O严重影响交换性能，导致性能下降到 5 . 1 8%【。可 6】

见 H L等阻塞将浪费交换结构近半的带宽。为克 O基金项目： 6 8 3基金项目资助 ( 0 2 2 0 AA1 1 5 ) 2 0 1收稿日期：2 0—60 0 40—9

服 H L所产生的影响，出现了许多消除 H L阻塞 O O

维普资讯

基于 C O S A R S B R的 iLP调度算法及其硬件实现 SI

现象、提高吞吐率的调度算法【 IJ q。尽管目前可以

提高交换结构吞吐率，减小交换结构的延时技术已趋成熟，但易于在硬件中实现的、高效的队列调度算法仍然是一项值得研究的课题。

3 iL算法及其性能 siLPi rt e ru dbnma hn i l ) S I(ea v o n—i t i t i w t sp首 c g h i图2接收，输入最多选择一个相应的输出

次见于斯坦福大学教授N. ko n 19年在5 Mc

ew在 9 5月在加州大学伯克利分校的博士论文。其优点就是简●卜————.●一 1 .●●

洁和高效；能很容易地用硬件加以实现；在通信量完全均衡的前提下，吞吐率可达 10 0%。 ( )IL P法 I S I算

iLP算法每次迭代由三个步骤组成：第一步 SI请求( eu s, R q et每个输入端口向每一个具有分组( )信元)队列缓冲的输出端口发出一个最高优先级的请求信号；第二步响应( rn) G at,如果一个未匹配的输出端口收到任何请求信号，它必须选择一个。 R R M调度算法从最高优先级的端口位置开始，固定地从下一个出现的R q et号中选择，出端口通知每 eu s信输一

图3匹配完成

第一步：请求，输入端口1、4、3分别向具有分组队列缓冲的输出端口 (、 ), (、 )和 ( ) 12 2 4 4

发出请求信号。第二步：响应，输出端口1向输入端口1发出响应信号，输出端 H2向优先级最高的输入端口1发出响应信号。同理，输出端口4向优先级

个输入端口其请求是否被响应。 rn信号发出当G at

后，只有在第三步中响应信号被输入端口所接收， 在输出端口指向最高优先级位置的指针按模Ⅳ增

最高的输入端口3出响应信号。注意，当响应信发号发出后，按照 …… 此处隐藏：6920字，全部文档内容请下载后查看。喜欢就下载吧 ……