（通信与信息系统专业论文）支持不同类型网络接口的非对称交换结构的研究.pdf

哈尔滨工业大学工学硕上学位论文 摘要 近年来数：手家电的迅速发展也促进了对家庭网络的研究。简单地说，家 庭网络就是将家用电器、个人电脑、p d a ( 个人数字助理) 以及其它的通信 设备连接在一起的一种新型网络。 同其它类型的网络相比，家庭网络具有一个显著的特点：不同的设备可 以通过不同的方式与家庭网络相连，如电力线，i e e e l 3 9 4 ( 俗称火线) ， u s b ，蓝牙，红外，8 0 2 1 1 等。另外这些设备所需的传输速率也是不同的。 要实现家庭网络中设备间高速有效的信息传输，必然要应用到交换设 备。各个端口容量相同的交换机称为对称交换机，而各个端口容量不同的交 换机称为非对称交换机。显然，对称交换机对家庭网络来说是不适用的。因 此对非对称交换机的研究具有十分重要的意义。就查到的文献来看，目前还 没有这方面的研究。 本文提出了一种c l o s 网络型的非对称交换结构，采用虚拟输出排队 结构和一种改进的i s l i p 调度算法。这里改进的i s l i p 调度算法是指对仲裁 器的优先级循吓表( r o u n d r o b i ns c h e d u l e ) 进行改进，使其适用于各端口容 量不同的非对弥交换机。 本文主要包括四部分内容。第一部分简要介绍了本文主要应用到的相关 理论：c l o s 网络，排队结构和调度算法。之后，给出了c l o s 网络型的非 对称交换结构模型，并对该模型无阻塞交换的最小内部连接容量的取值进行 了讨论。第三部分给出了确定第二级所包含的中间模块数量及各输入输出 模块同中间模块间连接数量的一种算法，并提出了一种适用于非对称交换的 改进的i s l i p 调度算法。最后一部分对c l o s 网络型的非对称交换结构的时 延特性进行仿真和分析，并与单一芯片构成的非对称交换结构进行对比。 理论分析及仿真结果表明，本文提出的c l o s 网络型的非对称交换结 构易于实现，且具有良好的时延特性。 关键词非对：际交换结构；c l o s 网络；虚拟输出排队；i s l i p 调度算法 ：一 堕堑鎏三些尘兰三兰堡圭兰堡丝圣 a b s t r a c t t h er e c e n 。r a p i da d v a n c e si nd i g i t a la p p l i a n c e sh a v ea l s or e s u l t e di na c t i v e r e s e a r c ho nh o m en e t w o r k s b r i e f l y , h o m en e t w o r ki san e wt y p eo fn e t w o r k w h i c hc o n n e c t s h o u s e h o l da p p l i a n c e s ，p e r s o n a lc o m p u t e r ，p d a ( p e r s o n a ld i g i t a l a s s i s t a n t ) a n d ：+ o m eo t h e rc o m m m f i c a t i o ne q u i p m e n t ad i s t i n c tc h a r a c t e r i s t i co fh o m en e t w o r kc o m p a r e dw i t ho t h e rn e t w o r k si s t h a td i f f e r e n td e v i c e sm a yc o n n e c tw i t hi tt h r o u 【g hd i f f e r e n tm e a n s ，s u c ha sp o w e r l i n e ，i e e e1 3 9 4 ( f i r ew i r e ) ，u s b ，b l u e t o o t h ，i n f r a r e d ，8 0 2 1 1 ，a n ds oo n a n d t h e s ed i f f e r e n ti t e v i c e sn e e dd i f f e r e n tt r a n s f e rs p e e d s as w i t c hm u s tb eu s e dt ot r a n s f e rd a t aa m o n gd e v i c e si nah o m en e t w o r k w i t hh i g hs p e e t as w i t c hw i t hs a m ec a p a c i t yo fe a c hp o r ti sc a l l e ds y m m e t r i c s w i t c h ，a n da 。w i t c hw i t hd i f f e r e n tc a p a c i t yo fe a c hp o r ti sc a l l e da s y m m e t r i c s w i t c h o b v i o u s l y , s y m m e t r i cs w i t c h e sa r en o ts u i t a b l ef o rh o m e n e t w o r k s s oi t i sv e r yi m p o r t a n tt od or e s e a r c ho na s y m m e t r i cs w i t c h e s u n f o r t u n a t e l y ，t h e r e s n or e s e a r c hh a sb e e nd o n eo nt h i sa r e a i nt h i s t , a e s i s ，w e i n t r o d u c e da na r c h i t e c t u r eo f a s y m m e t r i c s w i t c h s u p p o r t i n gh e t e r o g e n e o u s n e t w o r ki n t e r f a c e s ，w h i c hi sa t h r e e - s t a g e c l o s n e t w o r kw i t h1 4 r t u a lo u t p u tq u e u i n ga r c h i t e c t u r ea n du s eak i n do fi m p r o v e d i s l i ps c h e d u l i n ga l g o r i t h m i m p r o v e di s l i ps c h e d u l i n ga l g o r i t h mm e a n st h a tw e i m p r o v e dt h er o u n d r o b i ns c h e d u l et om a k e i ts u i tf o rh e t e r o g e n e o u s c a p a c i t yo f p o r t s t h i st h e s i ：；m a i n l yi n c l u d e sf o u rp a r t s i nt h ef i r s tp a r t ，w es u m m a r i z e dt h e m a i nt h e o r yv 。eu s e di nt h i st h e s i s ：c l o sn e t w o r k ，q u e u i n ga r c h i t e c t u r ea n d s c h e d u l i n ga l g o r i t h m t h e nw ei n t r o d u c e dt h em o d e lo fa s y m m e t r i cs w i t c ha n d d i s c u s s e dt h er ：f i n i m u mv a l u eo fi n n e rl i n kc a p a c i t i e s i nt h et h i r dp a r t ，w eg a v e a na l g o r i t h mt oc a l c u l a t et h en u m b e ro fm o d u l e si nt h es e c o n ds t a g ea n dt h e n u m b e ro fl i n k sb e t w e e nm o d u l e si nt h ef i r s t t h i r d s t a g ea n dt h es e c o n ds t a g e f i n a l l y , w e s i m u l a t e da n da n a l y z e dt h e l a t e n c yp e r f o r m a n c e o ft h i sc l o s a s y m m e t r i cs u i t c ha r c h i t e c t u r ec o n t r a c tw i t has i n g l e c h i p a s y m m e t r i c s w i t c h a r c h i t e c t u r e a n a l y s i sa n ds i m u l a t i o nr e s u l t s s h o wt h a tt h i sc l o sa s y m m e t r i cs w i t c h 。：。：一 丝尘堡三些奎兰三兰蝥圭i 竺鎏圣 a r c h i t e c t u r ei se a s yt oi m p l e m e n ta n dh a sg o o d l a t e n c yp e r f o r m a n c e k e y w o r d sa s y m m e t r i c s w i t c h a r c h i t e c t u r e ；c l o sn e t w o r k ；v i r t u m o u t p u t q u t m i n g ；i s l i ps c h e d u l i n ga l g o r i t h m i i i 哈尔滨工业大学工学硕士学位论文 1 1 课题背焉； 第1 章绪论 随着网络技术和通信技术的突飞猛进，人们不仅对家居的自动化和信息化 程度要求越来越高，而且对家用设备控制的灵活性以及对外部信息获取的方便 性提出了更高的要求。这些要求的实现都离不开家庭网络。 家庭网络是指在家庭内部通过有线或无线传播介质( 如电力线、双绞线、 同轴电缆、无线电、红外、蓝牙等) 将各种家用电器、通讯设备和个人电脑连 接起来，采用统一的通信协议，对内实现资源共享，对外能通过网关与外部公 网互连进行信息交换1 1 “。 通过智能冢庭网络主要可以实现以下功能： ( 1 ) 信息共享 实现家庭冈部各种信息终端的高速信息共享，比如p d a 、个人电脑之间的 数据共享。 ( 2 1 对电气设备的控制和管理 远程对各种家用电器设备的控制、调节和监测，比如对微波炉、洗衣机、 空调、热水器等的控制。 ( 3 ) 家居安全 家庭内部i d 现的紧急情况( 如盗抢和火灾) 能自动向主人手机或管理中心 报警；家庭成员的医疗求助信息能远传到社区医疗中心。另外也可以通过 i n t e m e t 监视家庭内部情况等。 ( 4 ) 能源管理 三表自动显示并抄送到管理中心，免除物业人员的入室干扰：定时开关供 暖通路及天然气，节约费用和保证安全。 ( 5 ) 多媒体服务 对内实现电视机与数码相机、摄像机、v c d 和d v d 等设备之问的视频音 频信号传输；对外实现可视电话、视频会议和视频点播等视频音频信息交流。 要实现家庭网络中的各个设备之间以及这些设备与外部公网之间的高速有 效的信息交换，必然要应用到交换设备。与其它类型的网络相比，家庭网络具 有一个重要的特点，网络中的不同设备对通信速率的要求差别很大，另外这些 堕查堡二些查兰三兰堡：! 兰堡丝耋 设备可能通过不同类型的接口与家庭网络相连。传统的交换机各个端口的接口 类型相同。每个端口的容量也是相同的。各个端口容量相同的交换机称为对称 交换机，而如果各个端口的容量不同，则称之为非对称交换机。显然，各个端 口的接口类型相同，容量相同的对称交换机是不适用于家庭网络的。因此对支 持不同类型网络接口的非对称交换结构的研究具有十分重要和现实的意义。另 外，可以预见，随着网络技术的发展，除家庭网络外，还将会出现要求采用非 对称交换机的其它类型的网络。 1 2 国内外发展概况 家庭网络一直被看作是潜力无限的新兴市场，多个国际和国内组织都开展 了对家庭网络技术和标准的研究f l o 】。影响比较大的家庭网络标准产业联盟主 要有i b m 、英特尔和微软等联手推动的d l n a 联盟，以及l g 和大宇电子等四 家巨头组成的l n c p 标准联盟。另外，国内的联想、海信、康佳、长城等组成 的“闪联”，海尔、清华同方等共同成立的“e 佳家”( i t o p h o m e ) 联盟也在 研究制定家庭网络技术的相关标准。但目前对家庭网络的研究还处在早期的探 索阶段。 高性能的家庭网络的实现，离不开高速的交换设备。因此对适用于家庭网 络的支持不同类型网络接口的非对称交换结构的研究具有非常重要的意义。就 查到的相关文献来看，目前还没有这方面的研究。现阶段对交换机各个方面的 研究均为各个端口容量相同的对称交换机。 用交换结构模块构成大容量交换系统的方法是目前国内外的研究热点，从 排队策略到大规模系统的网络形式都有不少研究课题。 这些年来，有很多不同的结构用于交换系统。最初的交换系统是围绕传统 计算机结构设计的，采用共享总线的结构：一个中央共享总线。一个或多个 c p u ，存储器a n # t - 围线路卡( l i n ec a r d ) 。每个线路卡实现m a c 层的功能， 将系统连接到每一个外部链路。从链路到达的信息包通过共享总线被传送到 c p u ，在那里做出一个转发判决。信息包然后被再次传送通过总线到达它的输 出线路卡，到外部链路。 共享的总线经常变得拥塞，限制了系统的性能。因此交叉开关交换结构越 来越多地代替了共享总线。在交叉开关交换结构中，多个线路卡可以彼此同时 通讯，大大增加了系统吞吐量。c i s c o 公司的千兆位交换路由器g s r l 2 0 0 0 是 一个1 6 端口i p 路由器，其交换结构使用的是交叉开关，允许多个信息包同时 哈尔滨t 业大学工学硕i 学位论文 传送。 由于芯片技术的迅速发展，使得高带宽存储器的使用成为现实，在高速交 换系统的设计中，也可以采用共享存储交换的技术【5 j 。例如i b m 的q 6 4 g 交 换系统就使用了单片带宽为3 2 g b p s 的存储器作为交换结构实现总带宽为 6 4 g b p s 的交换功能。 目前，高速交换系统设计基本上都采用交叉开关或共享存储器的交换结 构，使用共享存储器或交叉开关代替共享总线进行交换。 近些年，对于使用虚拟输出排队的开关交换器的调度算法也有很多的研究 工作l ”j 。在原理样机和商业产品的开发过程中，很多调度算法被研究者开发 出来。如极大规模匹配( m a x i m u ms i z em a t c h i n g ) 算法、神经网络算法 ( n e u r a ln e t w o r ka l g o r i t h m ) 、预先调度算法( s c h e d u l i n gi n t ot h ef u t u r e ) 、 并行迭代匹配( p a r a l l e li t e r a t i v em a t c h i n g ) 、循环匹配算法( r r m ：r o u n d r o b i nm a t c h i n g ) 以及i s l i p ( i t e r a t i v es l i p ) 算法等。其中i s l i p 算法由于具有 吞吐量高，快速，公平和易于实现的优点而被广泛采用。另外还有支持优先级 的i s l i p 算法以及支持多播( m u l t i c a s t i n g ) 的e s l i p ( e n h a n c e di s l i p ) 算 法。 波分复用( w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ) 的应用使得远距光纤传输得 到了广泛的应用。波分复用使一根光纤可以容纳几十个通道，其中每个通道的 速率为2 5 g b p s ，1 0 g b p s 或者4 0 g b p s 。信息包或信元在每一个通道上由工作 在不同通道间的交换系统进行交换或路由，交换系统的端口数可能多达1 0 0 0 多个。在这种情况下，单个交换系统很难满足如此高的带宽要求。为了使交 换系统的交换能力更高，目前多采用并行的设计办法。并行交换系统由3 级组 成，分别是多路分解器( d e m u l t i p l e x e r ) ，核心交换级( c o r es w i t c h e s ) 和多 路合成器( m u l t i p l e x e r ) 。每一个核心交换器位面( p l a n e ) ，它有自己独立的 交换结构和排队结构。在高速并行交换系统中，进入每个核心交换器的端口速 率为多路分解器的输入速率及多路合成器输出速率的l k ，其中k 是核心交换 器的数目，因此降低了对核心交换器的要求【m 1 7 】。 1 3 本文主要研究内容 本文提出了一种支持不同类型网络接口的非对称交换结构模型。 第一章绪论部分主要介绍了该课题的背景和国内外发展概况。 第二章简要介绍本文主要应用到的相关理论：c l o s 网络，交换系统的排 哈尔滨t 业大学工学硕上学位论文 队结构以及基于虚拟输出排队的调度算法，并比较了各种不同的排队结构及不 同的调度算法的优缺点。 第三章给出了支持不同类型网络接口的非对称交换结构模型，并给出了该 模型保证无阻塞交换的内部连接容量的最小取值及其证明。 第四章主要介绍了如何用硬件来实现第三章中提出的支持不同类型网络接 口的非对称交换结构，给出了确定中间模块的数量及各输入输出模块与各个 中间模块间的连接数量的一种算法，并提出了一种适用于非对称交换结构的改 进的i s l i p 调度算法及其具体实现方案。 第五章对本文提出的c l o s 网络型的非对称交换结构的时延特性进行了仿 真分析，并与单芯片构成的非对称结构进行了对比。 堕尘堡三些查兰三兰竺兰童堡尘兰 第2 章排队结构及调度算法相关理论 2 1c l o s 网络 由于超大规模集成电路技术和物理条件的限制，对于输入输出端口数目较 多的交换网络无法由单一的交换单元来实现。另外，交换网络的成本主要取决 于交叉接点的数目。由单级交换单元构成的n n 交换网络的交叉接点数目为 2 ，当输入输出端口数目较大时，交叉接点的数目增长很快。因此，为了降 低交换网络的成本，长期以来人们一直在寻求一种交叉接点数目随输入输出端 口数目增长较慢的交换网络，其基本思想都是采用多个较小规模的交换单元按 照某种连接方式连接起来形成多级交换网络1 1 ”j 。 输入模块中间模块输出模块 图2 - 1 三级c l o s 网络结构 在1 9 5 3 年，美国b e l l 实验室的c l o s 首次构造了一类如图2 1 所示的 n n 的无阻塞的交换网络( n = n k ) 。他指出：采用足够多的级数，对于输 入输出端口数目，能够设计出一种无阻塞网络，其交叉接点数的增长的速度 小于n 2 。c l o s 网络无阻塞的条件是m 2 n l 。也就是说，采用c l o s 网 络，既可以减少交叉点数，又可以做到无阻塞。c l o s 网络在构成大规模交换 网络时能显著减少实现复杂度，因此在实际中被广泛应用。 哈尔滨t 业大学t 学硕上学位论文 2 2 排队结构 对于一个基于信元传输的n n 的交换结构来说，如果在一个时隙内( 假 设时隙宽度等于单位信元的传输时阳j ) ，两个或两个以上的信元竞争同一个输 出端口，产生输出端口冲突，这时只有一个信元能竞争成功被交换至目的输出 端口，其它信元均被阻塞，交换机因无法在一个信元时间内同时完成所有信元 的传送而导致部分信元丢失。为了控制信元在交换单元中的丢失概率，必须对 阻塞信元进行缓冲，按照排队调度算法等待后续时隙处理。在实际的交换机内 部往往根据所采用交换单元的特性分别在输入、输出或中央位置设置相应的缓 冲存储区。根据信元缓冲所处的不同位置，交换单元采用不同的排队策略，可 分为输入排队、输出排队、虚拟输出排队和结合的输入输出排队等几大类。下 面分别介绍这几种排队结构。 2 2 1 输出排队 输出排队( o u t p u tq u e u i n g ) 是将信元在输出端缓存。输出排队的内部互 连带宽增加了，允许多个信元同时转发到同一个输出，并且在那罩排队等候传 输到输出链路上。输出排队的主要优点是信元被延迟一个固定量，可以通过交 换器来控制时延。输出排队的主要缺点是对于一个端口交换器，内部互连和 输出队列运行在倍线速率上。当端口数大或者线速率高时，输出排队的实现 是很困难的。 2 2 2 输入排队 长期以来，由于输入排队( i n p u tq u e u i n g ) 的低性能，人们认为它是不实 用的。如果在每个端口用f i f o 队列来排队信元，只有每个队列的第一个信元 有可能被转发。结果导致f i f o 输入队列被队首位置阻塞( h o l ：h e a d 。o f - l i n e ) 所影响：如果队列前面的信元被阻塞，队列中其它的信元不能被转发到 其它未被使用的输出。吞吐量是衡量交换结构性能的主要指标之一，它被定义 为每个时隙交换结构每个输入端上成功传送信元到达其目的输出端口的比率。 最大吞吐量( m a x i m u mt h r o u g h p u t ) 是指在最大负荷下的吞吐量的值。从理论 分析和计算机模拟研究可知，对于输入缓冲采用f i f o 队列的n n 交换机，由 于h o l 阻塞的影响，在相同随机流量情况下，交换端口能达到的最大吞吐量 被限制在5 8 6 “。 堕堡堡! ：些查兰：! ；薹丝：! ；耋堡堡兰 2 2 3 虚拟输出排队 消除输入队列交换机的队首位置阻塞现象，提高系统的吞吐量，一个有效 的办法是采用虚拟输出排队( v o q ：v i r t u a lo u t p u tq u e u i n g ) 1 2 0 l 。如图2 2 所 示，在每个输入端口，对应每个输出端口都设有一个f i f o 队列，输入端口接 收到一个信元时经过决策判定它的目的输出端口，这个信元就被放在对应的 f i f o 队列中。然后，由一个集中的调度算法检查所有输入队列的内容，并且在 输入端口与输出端口之间寻找一个无冲突的匹配。 i n p u t1 螋 田 4 ( t ) 。ih 。1 、。q q ) 矿。 二田 i n p u t n m a t c l m l g o u t p u t1 一一 旦塑， 跚 山 。 ： h 弋q ，) 夕 、二田 图2 - 2 虚拟输出排队结构示意图 i o u t p u t n ；鱼塑。 由于队首位置阻塞已经被完全消除，因此，理论上一个调度算法可以使采 用虚拟输出排队的开关交换器的吞吐量达到1 0 0 。 2 2 4 结合的输入和输出排队 输出排队在保证通信量的服务质量方面比输入排队和虚拟输出排队要强， 但输出排队对硬件的速度要求很高，在交换带宽很高时很难实现。在输出队列 哈尔滨工业大学工学硕：l 学位论文 的性能优越性和输入队列的易实现性之间做个折衷，就有了结合的输入和输出 排队( c i c q ：c o m b i n e di n p u ta n do u t p u tq u e u i n g ) 。 如图2 3 ，c i c q 在输入端设计有虚拟输出队列，在输出端设计有输出队 列。由于有输入缓存，对于端口数为的交换系统，c i c q 不要求输出队列和 内部交换互连的速度达到端口速率的倍，从而大大降低了设计的难度。 i n p u t1 q n l ) 二田、 一文意p 、二田7 i n p u t n 竺等理翌 l ，1 ， 、 一 叫o 儿卜 黜 盎，p ： 0 1 1 t r l u t n 扭皿 图2 - 3 结合的输入和输出排队结构示意图 在交换系统中，如果一个时隙内( 或称为信元时间，是输入端产生一个信 元的时间) 系统能将每个输入端口的s 个信元读入并传输s 个信元到每个输 出，则称该系统的加速比为s 。加速比为s 要求系统交换结构、输入队列的读 取速度均为端口速率的s 倍。对于n 的交换系统，不同的排队结构要求的 加速比如表2 1 所示。 表2 - 1 不同排队结构的加速比 排队结构加速比( s ) i n p u tq u e u i n g ，v o q s = 1 o u t p u tq u e u i n g s = n c i c q 1 s 哈尔演t 业 学t 学硕士学位论文 2 3 基于虚拟输出排队的调度算法 近些年，对于使用虚拟输出排队的交换器的调度算法有了很多的研究工 作。调度算法研究在输入与输出端口之间建立双向匹配的问题。所谓匹配是指 能够在输入端口与输出端口之间建立起连接的最大匹配数量。 评价一种调度算法的优劣，主要考虑以下特性： ( 1 ) 效率一个有效的算法是在每次匹配中可以服务尽可能多输入队列的 算法。 ( 2 ) 高吞吐量一个保证虚拟输出排队的积压很低的算法。理想情况下， 算法将保证每个输入和输出可提供的负载达到1 0 0 。 ( 3 ) 稳定性对于一个给定的允许的通讯模式，如果每个输入队列的期望 占有是有限的，就是说，我们定义这个算法是稳定的。对于一个给定的算法， 如果一个稳态的通讯模式不引起交换器的不稳定，我们称之为可以支撑的 ( s u s t a i n a b l e ) 。 ( 4 ) 无饿死如果对于个给定的通讯模式和调度算法，一个非空输入队 列无限期地未被服务，我们称之为饿死。 ( 5 ) 快速为了获得最高的交换带宽，调度算法不成为性能的瓶颈是非常 重要的。因此算法要尽快地找到一个匹配。 ( 6 易于实现如果算法在实用中快速运行，它必须在专用硬件中实现， 最好在单芯片中。实现的复杂度包括调度器必须保持的状态量。基于状态做出 一个判决所需要的逻辑量，在每个信元时间的丌始和结尾更新状态所需要的通 讯量。 下面简要介绍几种常见的采用虚拟输出排队的交换器的调度算法。 2 3 1 极大规模匹配算法 极大规模匹配( m a x i m u ms i z em a t c h i n g ) 算法试图在一次调度时间内找到 最大的输入输出端口间连接数，由此来增加所获得的带宽。这种方法相当于在 个顶点( 对于一个n x n 的交换机来说) 的二分图最大匹配问题【2 8 , 2 9 。然而 在通常情况下，很少，可以说几乎不采用这种调度策略，主要有两个原因。首 先，尽管现在已经有很多种方法用来优化二分图的最大匹配问题，但是这种方 法在硬件实现上太复杂，而且计算时间也太长。第二，这种方法会导致某些输 入输出对出现“饿死”现象( 如图2 - 4 所示) 。根据极大规模匹配算法的调度 堕尘堡三些奎兰三兰堡：! 耋堡丝兰 原则，总是找到从输入端口l 到输出端口1 ，和从输入端口2 到输出端口2 的 匹配对，而从输入端口2 输出到输出端口1 的信元将永远得不到服务。高性能 的调度算法必须具备以下两个特性：调度合理不会出现“饿死”现象，快速并 且实现简单。 图2 - 4 采t e i ；j 极大规模匹配算法导致“饿死”现象 2 3 2 并行迭代匹配算法 并行迭代匹配( p i m ：p a r a l l e li t e r a t i v em a t c h i n g ) 算法用随机策略来防止 “饿死”现象的出现 3 引。通常并行迭代匹配算法得到的匹配数要小于极大规模 匹配得到的匹配数，但是并行迭代匹配算法在实现上要简单褥多。并行迭代匹 配算法通过多次迭代来快速获得互不冲突的最优匹配，每一次迭代由三步组 成。这三步如下： 第一步：请求( r e q u e s t ) 。每一个没有匹配的输入端口对它所有的有数据 请求的输出端口发出调度请求。 第二步：准许( g r a n t ) 。如果一个未经匹配的输出端口接收到调度请 求，那么它就随机地从这些调度请求中选择一个，并且通知选择到的输入端口 一个分配确认的信号。 第三步：接受( a c c e p t ) 。如果输入端口接收到分配确认那么它就随机地 从这些分配确认中选择一个来接受。 图2 5 为一个并行迭代匹配算法执行过程的例子。 但是随机策略也有其局限性。首先，要设计一个高速的随机选择机制非常 困难并且代价昂贵。另外，如果迭代次数为1 ，那么并行迭代匹配算法的性能 就会大幅度降低，这是因为执行一次迭代，一个输入端口得不到分配确认的可 能性为( 一1 ) ”，当增加时，吞吐量接近于( 1 1 e ) = 6 3 ，只比f i f o 交 换器高一点。尽管在多次迭代后算法将收敛于一个好的匹配，但是收敛时间可 能影响交换器的运行速率。 n 日a t i o n1 哈尔滨工业大学二r 学硕十学位论文 蚕ii 1 趸 r e q u e s t r e a a t i o n2 1 l 2 2 3 3 4 - 4 r e c l u e s t 2 3 3 循环匹配算法 o r a n t g a a n t m a t c h i n g r e s u l t 图2 - 5 并行迭代匹配算法举例 a c c e p t a c c e p t 循环匹配( r r m ：r o u n d r o b i nm a t c h i n g ) 算法解决了p i m 的两个问题： 复杂性和不公平性。以优先级编码器实现循环仲裁器更简单，可以比随机仲裁 器运行更快。循环优先级帮助算法在连接请求中公平地安排带宽。r r m 算法 和p i m 一样由三步构成，如图2 - 6 所示。 夏 蚕 窒尘鎏三些尘茎三兰竺尘兰竺丝兰 i i l p u r l 一 “| 1 ，；| “1 。甜e4 i n l m j l3 。 “3 2 2 - 2 t 1 3 冉，t i h i p 畦4 一 u 4 , 4 ，= 3 例2 - 6 循环匹配算法举例 2 4 叫 、 ( c ) 这三步仲裁是： 第一步：请求( r e q u e s t ) 。每个输入向每一个有队列信元的输出发送一个 请求。 第二步：准许( g r a n t ) 。如果一个输出接收很多请求，它选择其中优先级 最高的那一个。输出通知每个输入它的请求是否被准许。指向循环调度的最高 优先级元素的指针g ，( g r a n tp o i n t e r ) 比准许的输入增加1 个单元( 取模n ) 。 第三步：接受( a c c e p t ) 。如果一个输入接收到准许，它接受其中优先级 最高的那一个。指向循环调度的最高优先级元素的指针口( a c c e p tp o i n t e r ) 比 接受的输出增加1 个单元( 取模n ) 。 图2 7 显示的是在独立同分布贝努里流输入时，算法平均时延与负载的关 系曲线。交换系统的端口数为1 6 。从图中可以看到，当负载只有大约6 3 时，r r m 就变得不稳定了。这和p i m 算法相似。但是比单次迭代的p i m 算法 的性能更葺。 啥尔滨工业大学工学硕1 学位论文 f 一 i 一 i j ， i 。 2 i3 04 05 07 0孽o9 0螂 o f f e r e dl o a d ) 图2 7 算法的平均时延与负载关系图【4 2 】 t m 性能不好的原因是输出仲裁器更新指针的规则。我们举例说明，示 于图2 - 8 中。输入1 和2 负载都很重，在每个信元时间，对两个输出中的每一 个都接收一个新信元。但是因为输出调度器变得锁步( 1 0 c k s t e p ) ，在每个信元 时间只有一个输入被服务。四个连续信元时间的请求，准许，接受顺序示于图 2 - 9 。注意准许指针( g r a n tp o i n t e r ) 锁步变化：信元时间1 都指向输入1 ，信元 时间2 都指向输入2 ，等等。这种同步现象导致对于这种通讯量模型最大吞吐 量仅有5 0 。 岔耳uiu呈嘎h_弓u雠 堕尘堡三些查童三耋丝圭兰堡堡三 k ，i = 灭i ，2 ：l u ) ，l = p = 0 2 5 kt = k ：= l 1 t 2 。i = “2 2 。o ，2 5 图2 - 82 2 交换使用r r m 算法在重负载下吞吐量只能达到5 0 删，：净4 ： 叫 c e l l 2 ：限 b ： e l = 田圈尺置翻一翻g 豳一 目e j = 圈翻r 置驾圈g 圈一 q 随罡i = 田。豳= 图图r 驾一翻g 豳一 c “一：b i = 圈。豳t 图圈r 良习一+ 翻g 嘲一 图2 - 9r 醐算法的输出仲裁器的同步机制导致低吞吐量 一 4 f la j a ， f a 矗 屯a 矗 窒丝堡! ；些查兰! ：兰些：；兰堡耋兰 2 3 ，4 滑动迭代轮循匹配算法 r r m 算法导致的同步问题使得它的吞吐量很低。m c k e o w n 改进了r r m 算法，提出s l i p 算法【3 ”。s l i p 算法使再j 循环优先级( r o u n d r o b i n ) 仲裁来轮 流调度每个有效输入和输出，其主要特点是简单，易于在硬件中实现，可以高 速运行。对于均匀分布通讯量( u n i f o r mt r a f f i c ) ，s l i p 的性能很好；对于独立 同分布的贝努利流，s l i p 可以得到1 0 0 吞吐量。这是因为s l i p 的仲裁器彼 此之间有一个“失步”趋势。 s l i p 算法通过减少输出仲裁器的同步来提高r r m 算法性能。除非准许被 接受，否则s l i p 算法不改变准许指针。除了准许指针的更新条件s l i p 和 r r m 是一样的，将r 鼬以算法的准许一步改为： 第二步：准i q ：( g r a n t ) 。如果一个输出接收到很多请求，它选择其中优先 级最高那一个。输出通知每个输入它的请求是否被准许。只有在这个准许在第 三步被接受的情况下，指向循环调度的最高优先级元素的指针量( g r a n t p o i n t e r ) 比准许的输入增加1 个单元( 取模n ) 。 算法的这个小改动导致了s l i p 算法的以下一些特性： 特性1 ：最近得到的连接被赋予最低优先级。这是因为当仲裁器移动它们 的指针时，最近准许( 接受) 的输入( 输出) 将相应的输出( 输入) 变成最低 优先级。如果输入i 成功连接到输出，日。和吕被更新，从输入，到输出，的连 接在下一个信元时间内变成优先级最低。 特性2 ：没有连接被饿死。这是因为输入将持续对一个输出请求，直至成 功为止。输出首先最多服务一1 个其它输入。最多等候个信元时间被每一 个输入接受。因此，一个正在请求的输入在2 信元时间内总可以被响应。 特性3 ：在重负载下，所有的具有相同输出的队列有相同的吞吐量。这是 特性2 的推论：输出指针以固定次序移到每一个请求的输入，因此每个都有相 同的吞吐量。 但是更重要的是，这个小改动避免了输出仲裁器锁步，使性能有了很大的 提高。从图2 7 中可以看出s l i p 算法比r r m 性能的改善。 i s l i p 算法是迭代的s l i p 算法( i t e r a t i v es l i p ) 。在一个时隙中做多次 s l i p 算法，从而增加匹配的结果。 i s l i p 算法每次迭代操作在每个输出和输入并行操作的三步是： 第一步；请求( r e q u e s t ) 。每个输入向每一个有队列信元的输出发送一个 请求。 哈尔滨工业大学t 学预十学位论文 第二步：准许( g r a n t ) 。如果一个输出接收很多请求，它选择其中优先循 环级最高的的那一个。输出通知每个输入它的请求是否被准许。只有在这个准 许在第三步被接受的情况下，指向循环调度的最高优先级元素的指针g ，比准许 的输入增加1 个单元( 取模n ) 。 第三步：接受( a c c e p t ) 。如果一个输入接收到多个准许，它接受其中优 先循环级最高的的那一个。指向循环调度的最高优先级元素的指针皿比接受的 输出增加1 个单元( 取模n ) 。 i s l i p 算法具有以下特性： 特性l ：在最近一次迭代匹配的连接在下次迭代变成最低优先级。 特性2 ：没有连接被饿死。因为一个输入将持续向一个输出发出请求，直 到成功为止。等待的时间至多为n 1 个信元时间。 特性3 ：对于多于一次迭代的i s l i p ，在重负载下，有着相同输出的每个 队列可能有不同的吞吐量。 特性4 ：算法在至多次迭代后收敛。每次迭代将给出0 ，1 或者更多的 连接。如果在次迭代给出0 个连接，那么算法已经收敛，更多的迭代不会得 到更多的连接。因此，最慢的收敛将发生在每次迭代只有一个连接被调度。至 多调度个连接( 每个输入一个，每个输出一个) 意味着算法将在至多次 迭代后收敛。 特性5 ：算法不一定收敛到极大规模匹配。最好时，它将发现一个最大匹 配：最大匹配是指不改变早先迭代得出的连接时的最大规模匹配。 实现i s l i p ，我们需要决定每个信元时间内进行多少次迭代。理想情况 下，由上面的特性4 来看，我们应该进行次迭代。然而，实际上没有足够的 时间做次迭代，所以我们需要考虑只进行i 次迭代( f n ) 的损失。事实 上，因为仲裁器的失步，i s l i p 通常将在少于j v 次迭代后收敛。 一种选择是总是将算法运行完，结果是对于不同的信元流，调度时间不 同。在一些应用中，这是不可接受的，例如在a t m 交换中，希望保持一个固 定调度时间，努力尽可能在这段时间完成更多的迭代。 仿真表明，对于n n 开关，i s l i p 用大约l o g ，n 次迭代就会收敛。 图2 1 0 显示了1 6 1 6 交换器在独立同分布的贝努利流输入时，不同迭代 次数的平均队列时延与负载的关系。我们发现i s l i p 多次迭代有效增加了匹配 规模因而减少了队列时延“。 哈尔滨工业大学工学硕十学位论文 2 4 本章小结 图2 1 0 不同迭代次数的平均队列时延与负载关系”2 本章简要介绍了支持不同类型网络接口的非对称交换结构研究主要应用的 相关理论：c l o s 网络，交换系统的排队结构以及基于虚拟输出排队的调度算 法，并比较了各种不同的排队结构及不同的调度算法的优缺点。 卷已夸窖叠气h罨u嚣a 哈尔滨t 业人学t 学硕j ：学位论文 第3 章非对称交换结构模型 从理论上来讲，通常由单一芯片构成的交换结构在性能上要优于由多个：芯 片构成的多级交换结构。但由于集成难度及价格等因素，输入输出端口的数目 较多的交换结构无法由单一芯片实现。因此，我们考虑采用三级c l o s 网络来 实现无阻塞的非对称交换结构。 现有的交换芯片基本上都是按照三级c l o s 网络的结构来设计的。交换芯 片可以分为两类：一类为用于第二级的中心交换模块，另一类为第一级与第三 级结合在一起的的输入输出模块。 本文提出的非对称交换结构也采用三级c l o s 网络，第二级的中间模块采 用现有的交换芯片，因此只需重新设计用于第级与第三级的输入输出模块 即可。 3 1 非对称交换结构模型 假设网络中的设备共有肘种不同类型的网络接口，各种类型接口设备的 数量和容量分别为p 和q ( i = 1 ，2 ，m ) ，我们可以采用如图3 1 所示的交换 结构来实现网络中这些设备间的信息交换。 输入模块中间模块输出模块 图3 - t 非对称交换结构模型 日，q 卑，c ： 盛， 晗尔滨_ i = 业人学_ 丁学硕士学位论文 图3 1 所示的三级c l o s 网络中的第一级与第三级均包含m 个不同结构的 交换模块，且第一级与第三级的结构及与第二级的连接方式是对称的。第一级 中第i 个输入模块的输入端口数为p ，每个输入端口的容量为c ，。第三级中第 i 个输出模块的输出端口数为p ，每个输出端口的容量为c ，。第二级包含世个 相同结构的交换模块。第一一级中第f 个输入模块与第二级中的各个中间模块问 的连接容量均相同，这里用s 来表示( i = 1 ，2 ，m ) 。相应地，第三级中第i 个输出模块与第二级中的各个中间模块间的连接容量也为s 。 为避免输出阻塞，在输入端设置缓冲存储区，采用虚拟输出排队结构。 3 2 内部连接容量的最优值 本小节主要讨论图3 - 1 所示非对称交换结构模型中可以实现无阻塞交换的 最小的s ，( i = 1 ，2 ，m ) 取值。 首先定义m m 的二维矩阵z 为单位时间内从第一级中的各个输入模块传 输到第三级中的各个输出模块的数据量，即输入输出分布矩阵( i n p u t o u t p u t d i s t r i b u t i o nm a t r i x ) 。矩阵z 中位于第i 行第，列的元素z ( i ，) 代表单位时间内 从第i 个输入模块传输到第，个输出模块的数据量。 交换系统的外部