基于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出响应信号。注意，当响应信发号发出后，按照iLP S I调度算法，只有在第三步中响

加，指向向输入端口发出响应信号的下一个输出端口位置；第三步接收( ce t,如果一个未匹配的 A cp)

应信号被输入端口所接收，在输出端口指向最高 优先级位置的指针 g、 g、 g才能得到更新，并 l 2 4按模增加，指向下一个接收请求信号的输出端口位置。第三步：接收，未被匹配的输入端口从响应信

输入端口收￣G a t号，只能接收一个， l rn信 J它从最高优先级的端口位置开始，固定地从下一个出现的 G at r信号中选择。指向最高优先级的指针按模N n N加，指向接收端口信号的下一个位置。为了避免饥饿，指针只在第一次迭代后被更新。以图1 3~作为一

号中选择其一。由于这时 a:1输入端口接收了输 .,出端口1的响应信号，两端口之间的匹配成功后，

指针 a按模增加指向输出端口2 .,这时已匹配的输出端口指针 g。和 g随之更新，指

向下一个向输 4入端口发出响应信号的位置。注意，未成功匹配的指针 g不更新。,同理，入指针 a按模增加并指向输 .

个实例说明iLP S I在一次迭代中的实际调度过程。

图中 g、g是输出端口2 4的G at裁器，口是 2 4、 r仲 n l输入端口的Acet cp仲裁器。开始时，所有的输入端口与输出端口是未建立匹配的。

2。在一次迭代结束后，如果仍有未匹配的请求，

习-1●.

k ' 2J r一

那末将在下次迭代中匹配。例如输入端口1与输出 端口2或输入端口3与输出端口2在下一次建立匹将配。

( )iLP 2 S I算法性能

在一个 1×1的交换结构中，输入分组到达为 6 6伯努利平稳随机过程时，iIP SL在进行 1、4、2次迭代时的最大匹配率和负载率的关系，平均信元延时图l请求，每个输入向其有信元传输的输出发出请求

和负载率的关系分别如图4 5~所示。

J I Ag/e . 5 2 0 6 T eS p 1 . 0 4

维普资讯

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

斟

甚

茁1

略

逛

负载率 ( %)

图4匹配率和负载率关系

图5平均信元延时和负载率关系

从图中可以看出iL P S I算法在高负载的条件下都台达至优良的性台。皂 0皂 ( )S I算法的硬件实现 3 LP

径之一[。随着在单个芯片中总线控制器数目的提印高，高速和有效的仲裁器得到越来越多的注意。特别是在网络交换结构中，仲裁器显得尤为重要。图6是一个 1 X 1的网络交换结构框图。 6 6 文献【介绍了一款轮询仲裁产生器R G, 5】 A该产

iLP算法的一个重要特性就是易于硬件实 SI现，而在其实现中具体调度器的实现又是关键路引

图6 1 6×1网络交换结构 6

生器的基元是2和4的交换仲裁单元。基于×2×4 A R G,给出l×l仲裁单元的实现见图7 6 6。其中4 ×

裁单元是由环形计数器和优先级逻辑单元构成，环形计数器每移位一次，优先级逻辑单元就根据相应规则从输入的请求中选取一个优先级最高的，并给出对应的响应。

4s i h￣b e和2 o A w t c ir×2r t结构类似，都是由总 t o S线仲裁单元和外围

逻辑电路构建成，其中，总线仲

电子科技， 0 2 4年 9月 1 0 5日 1 7

维普资讯

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

aCKUl l J aCKU

l

a Ku u e[J

I m ic l thr 1 a hi r l r t -

. m. . 1 u0卜_ _—

r 1 m ic I th

■I be il rt l A ir

1 sl h 0 a .ra1日 1

mO L q _=mq3一

4 I x - 4广一ar

u an p c _k

= I g th一 wi ci

I

mq2

”‘。

l

_一

[ 1 m￣ c I th

4 l x

ll

司 a ir l rt be

墅 _: - ! 墼卜厂—

u囹l p一 _ 嗍

J

广

l si l w h t一 l I . aJ U5

图7 1 6×1仲裁单元的实现 6

4结束语iL P算法是一种针对定长分组的输入排队调 SI度算法，采用虚拟输出队列和优先机制，可有效地

C mp t y tms 19, 4:1￣ 3 2 o ue S s r e, 9 3 1 () 9 5 . 1 3

3李胜磊，张德运，刘刚 .于匹配预测德交换调度算法 .基 西安交通大学学报，0 33 ( )1 1￣ 1 1. 2 0,71:0 6 09 04 P n a Gu t a d Nik k o . D s n a d ak j pa n c Mc e wn ei n gi lme tto f a fs r s a c e u e.I EE mp e nai n o a tcosb r s h d lr E M ir co

消除H L O阻塞，提高系统的吞吐率。在负载均衡情况下，S I算法具有良好特性， iL P当分组以贝努利分布到达输入端口时，通过控制仲裁器，其吞吐率可达 10 0%,并且不会产生端口饥饿。在重负载下，所有具有同一输出端口的队列具有相同的吞吐率。 iL P S I算法保证在最多N (口数 )次迭代后收敛。端 然而，实际中iLP S I算法通常少于L g N次迭代后 o2收敛。就是说对于一个 1端口的调度器4 6次迭代足够了。S I算法可以快速有效地匹配一个输入队列 iLP调度器的输入和输出，不仅具有高吞吐率，而且易

Ma a ie 1 9, 9()2￣ 2 . g zn

, 9 9 1 1: 0 85 Eu g S.S i.Vi c n .M o n y IIa d Ge re F n hn n e tJ e I n o g .Rie ly Ro n—o i Ar ie De i n n d u dr b n btr sg a Ge e ain S h o o n rt . c o l f o Elcrc la d e tia n Co ue E g n ei g mp tr n ie rn Ge r i n tut f o ga I si e o t Te h o o y Ata t, c n l g l a GA, 0 3 n 33 2 6 Gu t M c o De in a dI lme tt no st paP, Ke wn N. sg mpe n i faFa n a o Cr sb c e u e.t/ iy tr . a f r .d,0— 0 . o s a S h d lr t/ n—eas n o de u2 02 1—1 r h p:t t 8

7刘化君，刘斌.S I调度算法研究及其实现. i P L小型微型计算机系统， 0 3 2 () 19￣ 1 9 . 2 0, 49: 5 3 5 6

于在硬件中实现。对于一个 1端口的调度器可以 6设计在一个单片FG P A中，如 A t a司的P 1 lr公 e F0 K10使用资源约为5门¨。以， 0 A,万 J所基于C osa rs r b

作者简介占建国 (9 0),男，硕士研究生。主要研究方向： 18 - 扩频通信和移动通信。 曾兴雯 (9 6),男，教授。主要研究方向：扩频通 15 -信和移动通信。

交换结构的iLP S I调度算法具有良好的性能和易于用硬件实现等优点，可以充分用在像 T L路由器 L特等高性能大容量路由器和交换机的交换实现中。 参考文献1M c o Ke wn N.S h d ln el i n i p tq e e wi h c e uig c l n a n u— u u d s t . s c Bek ly U S U nv ri f l o i t r ee,1 9 . r ee, A: i est o i r aa k ly 9 5 y Ca f n Be

蔡文晖 (9 4),男，系统工程师。主要研究方向： 17 -

高速结构设计设计。王晓磊 (9 3),男，主任工程师。主要研究方向： 17 - 数据通信系统、超大规模集成电路设计。

2 An es n T,Owik S a e J ta .Hih s e d s th d ro c i,S x ,e 1 g

p e wi csh d l g f rlc lae ewo k .ACM a sc in n c e u i o o a r a n t r s n Tr n a t so o

(下转第2页 ) 3

J I eS p 1 . 0 4 TAg/e . 5 2 0

维普资讯

扩展 I/ O通道的存储连接技术

网 ( 2版 ).北京：机械工业出版社， 0 2第 20 .

2郭御风，黄金锋，琼等 . I李 P存储技术研究.计算机工程与科学， 02 2()9~ 7 20,45,4 9 .3 I F wo k r u、 DAF ET r g o p S. Die t rc Ac e s F l S se c s i e y tm

作者筒介

张正维 (92 )男，四川大学计算机学院硕士研究生。 17.,研究方向：计算机网络。

Poo o(es n .0 0 r tc l ri 0 )2 0 . v o1 14 J m e S Re i a sH., co ER、Die tDaa Plc me to e l b e rc t a e n v rRe i l a

王韩 (99)女， 1 -,四川大学计算机学院硕士研究生。 7研究方向：计算机网络。

Ta s ot ( es nl )2 0 . rn p r V ri、 . 0 2 s o 05 Re i R, Cu l co l y Gaca D . An RDM A P o o o ri r t l c

吕光宏，男，四川大学计算机学院教授，博士后。研究方向：计算机网络。

S e i ct n( es n1 )rf, 0 2 p cf ai V ri . dat 2 0 . i o o 06 Culy l e E z rU,Re i M ak rP lu co R. r e DU l n d F a n A i e r mi g g

fr C p cf ain( e s n 1 ) r f 2 0 . o P S e i c t T i o V r i . d at 0 2 o 0,

TheEx n i n o / Pa s y St r g nn ci c n l g pa so ft IO s wa o a eCo e tngTe h o o y heZh n e g e, a gYi L a g o g a gZh n w i W n , v Gu n h n( c o l f o ue ce c n n i e r g S c u nUnv ri, 0 5 C ia S h o mp t S i ea dE g n ei, ih a ie sy 6 0 6, hn ) o C

r n n t 1

Ab ta t Th sp p rf s ay e h rd t n l I Itc n lg, n e td e h e tc n l ge re p n ig teIO sr c i a r t e i n a l z steta i o a S e h o o y a dt n su isten w h o o isf x a d n / i S h e o h

p swa, ih i ek y tc n lg nn t r tr g . b eCh n e fesg o/ p ro ma c, u t lo ioae ANs a s y whc st e e h o o y i ewo k so a e Fir a n l f r o d IO fr n e b t s s ltsS h o e ia . I CS, o v r c mbn st eS Itc n lg n te e e h oo y t u o n cig io ae ANs I fnBa d h sag o S I h we e, o ie CS e h oo y a d eh m t c n lg, sc n e t s ltd S h t h n . n i n a o d i

IO ro a c n x a d b ly b sn o/ p f r n e a de p e m n a i t y u i gc mmo d pe st n e r t aiu trg e ie . i a rp t mp a i n i n a a tr O itg aev ro sso a ed v c s Th sp p u se h so e sh t tr,c a ce,a d te a p i t n so a e o t e sr cu e h a tr n h p l ain i trg fRDM A.I n rd c s t e c n e to eo c p d b eks te I0 u r c o tito u e h d c p fz r—o y a r a h/ n b t e e ki oss S h tt so d p l ai ni tr g . ot n c nh t, Ota f l ii wiea p i t so a e c o n K e wo d so a en t r; C S I ifnBa d RDM A y rs trg ewo k F i CS;n i n; i

(第 1页)上接 8

TheCROS BAR s d i S Ba e SLI Al o ih nd isI p e e t to P g rt m a m lm n a i n ti r n Ha dwa e rZh nJa g o一，

i e h i, a gXio e Ze gXi g n a in u Ca n u W n a li, n n we W( . c o l f ee o mu ia o s n ie r g XiinUnv ri,’n7 0 7, h n; 1Sh oo T l m c nc t n g n e n, d a iest Xi 1 0 1 C i a i E i y a

2 De at n f ee c T roain S e z e 10 4 Chn ) . pr me t sa hi Z ECop rt, h n h n5 0, ia o R r n o 8

Ab ta t Thsp p rito u e e i L P s h d l lo tm d l d p e nCROSS sr c i a e n d c st S I c e ue ag r h wiey a o td i r h i BAR wi h fb c wi t p ro a c s t a r t i f r n e c i h se ma ay e . t lop e e t h ad reb s di pe nai no ei LI lo tm . n z d I s r s nsteh wa ae l a r m lme tt f h S P ag r h o t i

Ke wo d s th fb c s h d l lo tm; y r s wi a r;c e ueag r h CROSS c i i BAR;S P; btr i LI a i r e

电子科技/ 0年 9月 1 2 4 0 5日 2 3

本文来源：https://www.bwwdw.com/article/zjw1.html