（计算机应用技术专业论文）基于islip算法的fifo特性研究.pdf

摘要 交换结构是路由器和交换机中的关键部分，在如何保证服务质量 q o s ( q u a l i t yo fs e r v i c e ) 的前提下进行高速转发，是近年来网络研 究的一个热点。相关的调度算法负责将输入端口的信元通过交换内核 发送至输出端口，所以它在提高交换设备的带宽利用率和服务质量方 面起着关键性作用。i s l i p 算法是一个经典的调度算法，主要用来解 决路由器交换结构调度问题，它具有高的吞吐率，良好的时延特性， 并且易于在硬件上实现，在实际中广泛应用，同时也是当今学者研究 的热点。 论文首先对交换机的交换结构和排队结构进行了介绍，主要是对 输入排队结构和交叉开关( c r o s s b a r ) 交换结构进行了重点阐述。接下 来对现有的典型分组调度算法p i m 、r r m 和i s l i p 等算法进行阐述，揭 示了每种算法的调度过程和优缺点，特别是i s l i p 算法，将对其性能 进行深入分析。 先来先出机常i j f i f o ( f i r s ti nf i r s to u t ) 在很多场合是一种基 本要求，可以看作是一个最基本的q o s 指标。比如同一优先级的数据， 一般要求先来先服务。我们通过深入分析i s l i p 算法的调度过程，揭 示该算法不能保证f i f o 要求，因此提出了改进算法：f i f o - i s l i p 算法。 此改进算法在保持i s l i p 算法原有优先级调度机制的同时又能保证 f i f o 特性，确保业务实时有序的传输，而不会过多地增加原算法的复 杂性。文章对f i f o - i s l i p 算法进行构想设计，并对性能进行分析计算， 尤其是传输时延等指标。同时把性能与纯粹的i s l i p 算法进行对比。 从理论上分析了许多时候f i f o - i s l i p 算法可以进一步降低业务的时 延。当然，对f i f o - i s l i p 算法的不足也进行了探求。 为了验证f i f o - i s l i p 算法，我们花大力气剖析了由斯坦福大学 开发的网络仿真软件s i m 。利用s i m 仿真软件对上述算法进行仿真实 现，通过对不同流量模型和不同端口数目的交换机进行模拟仿真，同 时对i s l i p 算法也进行仿真，得到一系列的数据。仿真结果表明了理 论分析的正确性。 关键词：交换结构；调度算法；i s l i p 算法；f i f o i s l i p ； s i m 仿真软件 a b s t r a c t as w i t c h i n gs t r u c t u r eisac r u c i a le l e m e n to fr o u t e r sa n d s w i t c h e s h o wt oo b t a i nah i g ht r a n s m i t t i n gs p e e dw h i l e g u a r a n t e e i n gq o s ( q u a l i t yo fs e r v i c e ) i sah o tt o p i co fn e t w o r k r e s e a r c hi nr e c e n ty e a r s t h es c h e d u l i n ga l g o r i t h m so fs w i t c h f a b r i ca r er e s p o n si b l ef o rt r a n s f e r r i n gt h ec e ll sf r o mi n p u t p o r tt oo u t p u tp o r t ，t h e r e f o r ei tp l a y sac r u c i a lr o l ei n i m p r o v i n gt h eb a n d w i d t hu t i l i z a t i o na n dq u a li t yo fs e r v i c eo f s w i t c hd e v i c e s t h ei s l i pa l g o r i t h m ，ac l a s s i c a ls c h e d u li n g a l g o r i t h mu s e dt os o l v et h es c h e d u li n gp r o b l e m so fh i g h s p e e d r o u t e ra n ds w i t c hf a b r i c ，h a sah i g ht h r o u g h p u t ，g o o dl a t e n c y c h a r a c t e r i s t i c s ，e a s yi nh a r d w a r ei m p l e m e n t a t i o n ，a n db e i n g u s e dw i d e l yi np r a c t i c e i ti sa l s oah o ts p o to ft o d a y s r e s e a r c h e s t h isp a p e rf i r s td e s c r i b e st h es w i t c hf a b r i ca n dq u e u i n g s t r u c t u r e ，f o c u s i n go nd e s c r i b i n gt h ep r a c t i c a la p p l i c a t i o no f ab r o a d e rs t r u c t u r eo ft h ei n p u tq u e u ea n dc r o s s s w i t c hf a b r i c ， t h e nd e s c r i b e ss o m ee x i s t i n gp a c k e ts c h e d u l i n ga l g o r i t h m ss u c h a sp i m ，r r m ，a n di s l i p ，r e v e a li n gt h e i rs c h e d u l i n gp r o c e s s e s ， a d v a n t a g e sa n dd i s a d v a n t a g e s a ni n d e p t ha n a l y s i sf o rt h e p e r f o r m a n c eo fi s l i pi se s p e c i a ll ym a d e f i f o ( f i r s ti nf i r s to u t ) i sab a s i cr e q u i r e m e n tc a nb e s e e na sab a s i cq o sr e q u i r e m e n to nm a n yo c c a s i o n s f o re x a m p l e ， b u s i n e s s e sw i t hs a m ep r i o r i t yg e n e r a l l yr e q u i r ef i f os e r v i c e s t h r o u g ht h ei n d e p t ha n a l y s i si nt h es c h e d u l i n gp r o c e s so ft h e i s l i pa l g o r i t h m ，i ti sf o u n dt h a tt h ea l g o r i t h mc a nn o t g u a r a n t e et h ef i f or e q u i r e m e n ta n dt h e r e f o r ean e wf i f o i s l i p n i a l g o r i t h mi sp r o p o s e d t h i si m p r o v e da l g o r i t h mm a i n t a i n st h e o r i g i n a li s l i pp r i o r i t ys c h e d u l i n gm e c h a n i s ma n da tt h es a m e t i m ee n s u r e st h ef i f of e a t u r e ，e n s u r i n ga no r d e r l yt r a n s f e rf o r r e a l t i m eb u s i n e s s e s ，w i t h o u tt o om u c hi n c r e a s ei nt h e c o m p l e x i t yo ft h eo r i g i n a la l g o r i t h m t h i sa r t i c l ep r o v i d e st h e d e s i g no ft h e f i f o i s l i p a l g o r i t h m a n dt h e a n a l y s e s o f p e r f o r m a n c e s ( e s p e c i a l l yt h et r a n s m i s s i o nd e l a y ) ，a n dc o m p a r e s t h e mw i t ht h ei s l i pa l g o r i t h m t h r o u g ht h e o r e t i c a la n a l y s i si t i sf o u n dt h a tt h ef i f o i s l i pa l g o r i t h mc a nf u r t h e rr e d u c et h e l a t e n c y o n m a n y o c c a s i o n s ，e s p e c i a l l yf o r 1i g h t l o a d b u s i n e s s e s o fc o u r s e ，t h ed i s a d v a n t a g e so ff i f o i s l i p a l g o r i t h ma r ea l s oe x p l o r e d i no r d e rt ov e r i f yt h ef i f o i s l i pa l g o r i t h m ，w es p e n ta g r e a te f f o r to na n a l y zi n gt h en e t w o r ksi m u l a tio ns o f t w a r es i m d e v el o p e db yt h es t a n f o r du n iv e r sit y w it hd if f e r e n tf l o w m o d e l sa n dd i f f e r e n tn u m b e ro fp o r t s ，w eu s et h i ss i m u l a t i o n t o o lt osi m u l a t et h ef i f o 。i s l i pa l g o r it h ma n dt h ei s l i p a l g o r i t h m t h es i m u l a t i o nr e s u l t sp r o v et h ea b o v et h e o r e t i c a l a n a l y s is k e y w o r d s ：s w i t c hf a b r i c ：s c h e d u l i n ga l g o r i t h m ；i s l i p a l g o r i t h m ；f i f o i s l i p ；s i ms i m u l a t i o ns o f t w a r e i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不合任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 豇触 i 冲年5 月；箩日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 善嘉篓耄i 乏蓉兰修三翥i ：辜三驾姜蓦 基于i s l i p 算法的f i f o 特性研究 1 绪论 1 1 引言 交换结构在提高交换系统的吞吐率中占有很重要的作用，而设计 高性能的交换结构的技术已经渐渐成熟，因此调度算法成为了一项重 要的研究技术，特别是那些易于在硬件中实现的调度算法，尤其是在 c r o s s b a r 交换系统中更是如此。i s l i p n l 是目前该领域应用较为成功 的个高速c r o s s b a r 调度算法，它由斯坦福大学m c k e o w n 教授研究组 提出，是一种针对定长分组的输入排队调度算法，采用了虚拟输出队 列和优先机制，可有效地消除h o l 阻塞，提高系统的吞吐率。它能够 快速地匹配一个输入队列调度器的输入和输出，具有高吞吐率，特别 是很容易在硬件中实现。当到达输入端口的业务流均匀分布于各个输 出端口时，i s l i p 算法能够提供1 0 0 吞吐量，并具有良好的时延性能。 关于i s l i p 有不少的补充和改进，如在文献心3 中，一种新的基于预测 的输入排队调度算法被提出，该算法研究了每次轮转指针的更新规 律，然后再预测下一时隙某些输入端口信元的情况，以此来达到提高 性能的作用。在文献聆3 中，通过在i s l i p 算法的基础上改进了其调度 步骤，提出了一种两步i s l i p 算法，不仅能够减少延迟的时间，同时 也保证了良好的吞吐率。对i s l i p 算法的研究和改进还有很多方面， 但是，通过在我们力所能及的范围内搜索文献的海洋，发现关于i s l i p 算法在f i f o ( 先来先服务) 机制上的改进，仍然有待研究，故本学位 论文定位于这一点。f i f o 在很多场合是一种基本的要求，可以看作是 一个最基本的q o s 指标，比如同一优先级的数据，一般要求先来先服 务，因此这一课题值得我们去研究。本文主要在i s l i p 算法研究和探 讨的基础上，揭示该算法不能保证f i f o 的特性，因此提出了改进算法： f i f o - i s l i p 算法。此改进算法在保持i s l i p 算法原有优先级的调度机 制，同时又实现了f i f o 的特性，能确保业务实时有序的传输，而不会 硕士学位论文 过多增加原算法的复杂性。然后对f i f o i s l i p 算法进行构想设计，对 其性能进行分析计算，包括传输时延和实现的复杂性等。并对比i s l i p 算法这些方面的性能。通过理论分析证明f i f o - i s l i p 算法可以进一步 降低业务的时延。当然，本文对f i f o i s l i p 算法的不足也进行探求。 1 2isl lp 算法概述 在输入与输出端口之间建立双向匹配是匹配算法研究的主要内 容。匹配就是在输入端口与输出端口之间寻找匹配，并建立连接，从 而达到最大匹配数量。s l i p ( s e r i a ll i n ei n t e r f a c ep r o t o c 0 1 ) 类型 算法是一种应用最多的匹配算法。n i c km c k e o w n 在s l i p 算法上提出 了一种新的算法i s l i p 算法，它是一种迭代的s l i p 算法，易于在硬 件中实现，能在一个输入队列调度器的输入端口和输出端口之间进行 公平、快速、有效的进行匹配。当是尽力而为的( b e s t e f f o r t ) 单播 业务调度时，它可以达到吞吐率为1 0 0 h 1 。由于它是一种迭代算法， 因此在每个时隙，都会采用多次迭代来对交叉开关的配置进行选择， 从而使输入端口和输出端口尽量达到匹配。 1 3 研究内容 在o o s 方面，分组调度算法起着至关重要的作用。为了提高交换 系统吞吐率并保证一定的o o s 支持，研究高效的易于硬件实现的队列 调度算法很有意义。本文主要是在研究i s l i p 算法的基础上，探讨其 调度的有序性问题，揭示它不能满足f i f o 特性，而f i f o 在很多场合 是一种基本的要求，可以看作是o o s 的一个最基本的指标，因此提出 了改进算法：f i f o - i s l i p 算法。并使用s i m 仿真软件进行实现和仿 真。本文主要在以下几个方面进行了研究： 第一：研究和探讨了i s l i p 算法的调度过程和性能。i s l i p 算法 是一种经典调度算法，主要用于解决高速路由器交换结构调度问题。 通过多重迭代完成输入输出端口之间的匹配。i s l i p 算法具有良好的 扩展性，并且易于在硬件中实现，吞吐率可以达到1 0 0 ，不会出现 基于i s l i p 算法的f i f o 特性研究 饿死的现象，并且具有稳定、高效、公平等特性。 第二：对于一般的业务，f i f o 是最基本的要求，可以看作是一 个最基本的o o s 指标。对于同优先级的数据，更应该要求先来先服务。 而根据i s l i p 的调度法则，经常使得后到的分组先得到服务，而先到 的分组后得到服务，在这种情况下，先到的分组就需要等待更长的时 间才能发送出去，平均时延就会增大。i s l i p 算法在调度的过程中不 能保证f i f o 特性。为了保证先到的先服务，我们提出了改进算法： 称为f i f o - i s l i p 算法，使i s l i p 算法具有f i f o 特性。我们对这一改 进算法进行了详细分析和描述。 第三：通过大力气剖析由m c k e o w n 教授研究小组开发的单交换机 仿真软件s i m 源代码，找出了深层次的仿真方法，用于对f i f o - i s l i p 算法进行仿真实现，同时也对i s l i p 算法进行仿真，然后对两种算法 的仿真数据进行分析研究。数据向我们显示了f i f o - i s l i p 算法由于 引入了f i f o 机制，平均时延等指标确实得到了改善。只要不过多地 增加原算法的复杂度，这种改善无疑是受欢迎的。 1 4 论文的结构 本文共分6 章。 第一章绪论主要对调度算法的现状进行研究，并介绍本文的主要 内容和组织结构。 第二章主要针对输入、输出和组合输入输出排队结构和不同的交 换结构进行研究和探讨。 第三章对现有的典型分组调度算法p i m 、r r m 和i s l i p 等算法进行 阐述，揭示了每种算法的调度过程和优缺点，特别是i s l i p 算法，研 究了其核心算法和性能。 第四章探讨i s l i p 算法调度的有序性，揭示其不具有f i f o ( 先 来先服务) 这一特性，提出改进算法：f i f o - i s l i p 算法，并进行新算 法的理论描述和性能分析。 硕士学位论文 第五章研究s i m 仿真软件，包括仿真软件的结构，仿真的环境以 及运行过程。然后将本文提出的f i f o - i s l i p 算法进行仿真实现，并 通过s i m 仿真软件对i s l i p 算法和f i f o i s l i p 都进行仿真，然后对 它们的仿真结果进行分析。 结束语总结了全文，分析了论文中的不足，并展望下一步的工作。 最后是参考文献和致谢。 基于i s l i p 算法的f i f o 特性研究 2 交换结构研究 2 1 交换结构及其参考模型的概述 交换结构是实现宽带交换机的关键技术之一，是交换系统中必不 可少的重要组成部分，它直接影响着交换机性能的好坏，对路由器的 总体性能和扩展性也有很大的影响。交换结构的组成部分包括输入端 口、输出端口以及连接输入和输出端口的交换内核组成。任意输入可 立刻交换为任意输出。目前，交换系统的交换方式主要有交叉开关型、 共享存储器型及总线型三种。现在从实现机制上大体可将其分为两 类：时分交换结构、空分交换结构。 每个输出端口在每个时隙只能输出一个信元，但是在同一个时 隙，来自不同输入端口的信元，有可能去往同一个输出端口，这样就 会出现输出冲突。交换内核会使用缓存队列对信元进行缓存，这些信 元就是那些来不及交换可能会丢失的信元。缓冲队列可以设置在不同 的地方，比如输出端，就是输出排队( o u t p u tq u e u e d ，o q ) ，设置在输 入端，由此形成输入排队( i n p u tq u e u e d ，i q ) ，还可以在输入端口和输 出端口都设置，这样就形成了联合输入输出排队( c o m b i n ei n p u t a n d o u t p u tq u e u i n g ，c i o q ) 交换结构。 交换结构由输入端口，输出端口和连接输入输出端口的交换内核 组成，参考模型如图2 - 1 所示。 输入端口先接收外部分组，然后再把分组切分为定长信元，最后 再把信元发送至交换内核。输出端口首先从交换内核接收信元，再 把这些分组进行重装，最后再把重装的分组发送到外部链路。作为交 换结构核心的交换内核，主要实现信元的交换功能。交换内核交换的 对象为信元，要求是定长的分组，但并不特指a t m 信元。时隙( t i m es l o t ) 通常是指交换结构中传输一个信元的时间。在每个时隙每个输出端口 只能输出一个信元，但是在同一个时隙，来自不同输入端口的信元， 有可能去往同一个输出端口，这样就会出现输出冲突。交换内核会使 s 硕士学位论文 用缓存队列对信元进行缓存，这些信元就是那些来不及交换可能会丢 失的信元。缓冲队列可以设置在不同的地方，比如输出端，就是输出 排队( o u t p u tq u e u e d ，o q ) ，设置在输入端，由此形成输入排队( i n p u t q u e u e d ，i q ) ，还可以在输入端口和输出端口都设置，这样就形成了联 合输入输出排队( c o m b i n ei n p u t a n do u t p u tq u e u i n g ，c i o q ) 交换结 构。 输入端口交换内核 输出端口 ! 目 醇2 v 阼 图2 1 交换结构的参考模型图 2 2 排队结构 在每个时隙，输出排队会要求对缓冲区进行的写操作需要n 次而 对读操作至少一次，所以对存储器的访问速度，至少是链路速率的n 倍。随着不断提高端口数和多链路速率，要达到如此快的访问速度， 这将成为系统的瓶颈。因此设计良好的缓冲交换系统很有必要。这也 是我们所研究的高速的交换结构。高速交换系统中的排队结构有三种 排队策略，有输出排队、输入排队和结合的输入输出排队晦。 2 2 1 输入排队 输入排队先使用输入端口的缓冲区把到达的信元保存在这里，然 后再通过交换结构把信元传送到输出端口，这个步骤主要是由调度算 法来决定。早期的输入排队采用的排队规则主要是简单的先进先出 ( f i r s ti nf i r s to u t f i f o ) 。当一个时隙到来时，就会有信元向 输出端口发送，如果在这个时隙中，这些排在队列前头的信元发往的 是同一个输出端口，这些信元就要进行竞争，到底谁先占用这个输出 基于i s l i p 算法的f i f o 特性研究 端口，把信元发送出去，而没有发送出去的信元，则会暂时停留在输 入队列中，等待下一时隙再竞争发送。然而，这种交换结构就会出现 这样一种现象，在一个时隙中，如果先来的信元参与输出端口竞争失 败了，就算排在它后面的信元所指向的输出端口是空闲的，它也无法 进行输出，这种现象我们通常称为队头阻塞( h o l ：h e a do fl i n e ) ， 如图2 - 2 所示： 图2 2 链头阻塞不惹图 输入排队虽然存在队头阻塞( h e a do fl i n eb l o c k i n g ) 问题，但 输入排队在许多高性能交换机和路由器依然得到了采用，因为它的内 部不需要加速。研究发现，所有输出如果是按贝努利均匀分布到达时， 又在端口数较多的情况下，输入排队只能达到5 8 6 的吞吐率3 。为 了解决队头阻塞问题，有人提出了v o q ( v i r t u a lo u t p u tq u e u i n g ) 结 构，如图2 - 3 所示。为了存储分别去往n 个输出端口的分组，会在每 个输入端设置n 个f i f o 队列，当有一个信元到达时，首先进行转发 判决，然后会把该信元置于相应的输出端口队列中。在任意一个时隙 开始的时候，中央调度算法将会检查所有输入队列中的信元，然后在 输入和输出间为其寻找一个不冲突的匹配。 通过理论研究和仿真实验表明，如果采用v o q 路由器的调度算 法，可以实现的吞吐率达到1 0 0 。虽然获得了高的吞吐率，但却不 能保证时延，因为时延还受到交换结构调度算法的影响，以及输入端 口的通信量的影响，这些也是q o s 性能所关注的。 一 一 o 1 一 i 2 3 硕士学位论文 端口1 端口n 输入端d n 图2 - 3 虚拟输出队列示意图 2 2 2 输出排队 如果把缓冲器设置在输出端口中，这样形成的排队为输出排队 ( o u t p u tq u e u i n g ) 。输出排队的吞吐率高于输入排队，这是因为它不 存在队头阻塞。如果这样设想的话，那么输出排队的吞吐率可以达到 1 0 0 。但是，输出端口还是会出现信元丢失，这是因为，在一个时隙 里，对于一个输出端口，可能会有多个信元到达，输出端口就发生溢 出，信元也就会丢失。特别是在突发业务流下，这种丢失的现象更为 严重。仿真模拟表明阳1 ，在一定负载区间内，并且当缓冲区大小一定 时，输出排队系统信元丢失率要高于输入排队系统，并且输出排队系 统的硬件复杂度要明显高于输入排队。但是为了降低信元的丢失率， 我们可以在输出排队中增加缓存器容量。 在输出排队中，任何的信元的延迟都是固定的，我们可以通过交 换结构来控制延迟。而输入端排队时延是不同的，也难以控制，因此 为了提供完全和统计意义上的性能保证国儿1 0 儿n 儿1 2 m 时，我们就会选择 输出排队。 输出排队需要内部带宽和输出队列速率必须n 倍于输入速率，也 就是n 加速比，才能实现高的吞吐率。但如果路由器有很多端口，并 基于i s l i p 算法的f i f o 特性研究 且端口速率又要达到g b i t s 时，要实现n 加速比，这是很难的，这 也是输出排队的缺点。 输出排队在很多场合还是得到了应用，比如许多商用的交换机和 路由器。信元到达后马上通过高速交换网络将到达的信元马上发送到 正确的输出端口，对于存储在输出队列中的信元，我们可以采用一些 不同的队列管理策略算法进行管理，虚拟时钟算法n 制、公平权重排队、 逆差轮转n 引、或者处理器共享n 嗣等等。 2 2 3 组合输入输出排队 因为输入排队和输出排队都各有其优缺点，如果把两种的优点都 结合起来，这样的排队结构应该能够实现高性能，因此就提出了在输 入和输出端口都设置缓存的想法，这样的交换结构被称为组合输入输 出排队结构c i o q n 刀( 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 ) 。 c i o o 结构在输入端，使用了v o q 结构，消除h o l 阻塞，为了使 得输入和输出调度分开，又设置小缓存结构，如图2 4 所示： v o o l l v u 厶l n 图2 - 4c i o q 排队结构示意图 在输入端口中，通过设置多个v o q ，从而消除了队头阻塞，而在 输出端口，为了避免信元的溢出丢失，可设置多个交叉点缓存。从理 论上来说，它能够克服前面两种排队结构的缺点，具有更好的性能。 2 3 交换结构的分类 根据交换技术，交换结构主要分为两大类：时分交换( t d s ) 和空分 一 ； 高 硕士学位论文 交换( s d s ) 1 8 o 时分交换又分为：共享存储类型和共享媒介类型。同样， 空分交换又分为：单路径交换和多路径交换，如图2 5 所示。 时分交换f i n s ) l 共点 介共享存储共享媒介 空分交换 s l i 广 单路径多路经 图2 5 交换机结构图 2 3 1 时分交换结构 时分交换结构通过内部底板或内存也就是一个共享的设施，把交 换信息从输入端口路由到输出端口，其中每个输入端口的数据都是串 行处理的，也就是在交换单元中，不能同时交换一个以上的输入端口 的数据。信元进行发送时，先进行请求，在获得批准后，才使用这个 共享的设施，进行发送。 由于在时分中，信元通过的是同一个通信通道，所以在组播和广 播中得到了应用。但是在时分中，一个设备的吞吐量又有一个固定的 上限，并且这种交换能力的限制，不能随端口的增加而增加，所以在 高速的交换结构中不适合使用。 2 3 2 空分交换结构 空分交换结构适用范围很广，它能够为交换构架提供多条路径。 空分交换结构具有良好的硬件扩展性，在不影响端口的吞吐率时，它 可以增加端口数，同时也不依赖共享设施，因此可以分为单通路结构 ( s i n g l ep a t h ) 和多通路结构( m u l t ip a t h ) 。单通路结构中比较常见 的c r o s s b a r 和b a n y a n 结构，它们只需要简单的路由控制，而多路结 基于i s l i p 算法的f i f o 特性研究 构则有更强的容错能力。 2 3 3c r o s s b a r 交换结构 一个c r o s s b a r n 们交换结构由n x n 交叉矩阵构成，因此也被称为 交叉开关矩阵或纵横式交换矩阵。c r o s s b a r 交换结构具有很强的扩 展能力，并且在容量方面也容易增大。它的内部不会出现资源不够而 产生阻塞，也不会出现带宽瓶颈等问题。c r o s s b a r 交换结构因其简 单性得到了更多的青睐和更广泛的采用，它可以同时提供多个数据通 路。在c r o s s b a r 交换结构中有许多的交叉点，这些交叉点通过调度 器来控制交叉点的开和关，并且也通过调度器来决定其速度。当开关 是闭合的时候，数据就从输入端x 传送到输出端y 。如图2 - 6 是一个 4 4 c r o s s b a r 的例子。每个交叉连接点存在两种状态，即“c r o s s ” 状态和“b a r 状态，当处于“b a r 状态时，左下、右上进行连接； 当处于“c r o s s ”状态时，上下、左右连接。 2 4 23 4 c r o s s 状态 b a r 状态 图2 - 64 x 4 c r o s s b a r 结构 随着核心交换机的交换容量发展到今天的几百个g b p s 乜们，越来越 多的核心交换机选择t c r o s s b a r 交换结构，这是因为它能很好的弥补 共享内存模式的一些不足。首先，实现相对简单，共享交换架构中的 线路卡到交换结构的物理连接简化为点到点的连接，实现起来更加方 硕士学位论文 便，保证大容量交换机的稳定性也更为容易。其次，内部无阻塞，当 多个交叉节点都闭合时，多个不同的端口就会同时传输数据。另外， 由于这两个原因，c r o s s b a r 交换结构可以在非常高的速率上运行。此 外，它在实际中也得到广泛的应用，本文研究和讨论的调度算法是基 于c r o s s b a r 交换结构。 基于i s l i p 算法的f i f o 特性研究 3 分组调度算法的研究 调度算法【2 q 是按照一定的规则对交换节点的不同业务进行缓存、 调度和服务，同时管理和控制流量、处理冲突、分配带宽等。分组调 度是实现网络服务质量控制的核心机制之一，是网络资源管理的重要 内容，通过控制不同类型的分组对链路带宽的使用，使不同的数据流 得到不同等级的服务娩幻。分组调度算法的实质是对在输入端口等待交 换的信元，通过算法找到一种输入与输出之间的匹配模式，抽象出来 就是双向图的匹配问题。 分组调度算法分类很多，可以根据调度目的划分，也可以根据不 同的服务规则划分。一般我们会根据算法的设计核心思想进行分类， 也就是根据调度规则进行分类。如果按调度规则分为：基于轮询、基 于时延、基于服务规则、其于优先级等等眩3 儿2 钔晗引。下文将对几种经典 的调度算法进行分析。 3 1plm 调度算法 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 ) 是较早提出的一种调度算 法。这是美国d e cs y s t e mr e s e a r c hc e n t e r 乜6 3 为1 6 端口，1 g b p s 的 a n 2 交换机开发的。p i m 算法通过随机性的选择避免了某些端口资源 匮乏性。 p i m 算法的基本思想是在每个信元发送的时隙，通过多步迭代， 在输入端口和输出端口之间匹配尽可能多的发送通道。它利用随机数 防止仲裁中的不公平性，并加快收敛性，减少所需要的迭代步数。在 信元开始发送时，所有的输入端口和输出端口状态都标为空闲。在每 一步迭代中，都只考虑未匹配的端口。在每一步迭代之后，都有一部 分输入端口和输出端口被随机匹配上。如图3 - 1 所示，描述了其匹配 的过程。 第一步：请求( r e q u e s t ) ，如果输入端口有信元并且没有匹配上， 它会向所有可能的输出端口发送请求服务，并等待响应。 1 3 硕士学位论文 说明： 陶 胡il j 朗 表示响应指针，表示确认指针 俐咄，蚪 ： ： r ；：“种：卜 蚪 2 蝌幻 蚪豳 圳i r i j 。 j 2 j l j 2 1 - - j j 2 j ! 1g i ：卜z 图3 1p i n 调度算法的三个步骤 第二步：响应( g r a n t ) ，如果输出端口接收到请求，并且它也没有 匹配上，输出端口就会随机选择一个输入端口进行响应。 第三步：确认( a c c e p t ) ，输入端口在接收到响应后，它会从所有 响应中选择一个输出端口给予确认，表示将向该输出端口发送数据。 在每次的迭代中，只会考虑前面的迭代中没有连接没有匹配上的 输入端口和输出端口。 根据上面的调度过程，我们发现输出端口会在请求中随机选择一 个输入端口，总会有一个输入端口会接受响应，向输出端口发送数据， 这样每次迭代将平均匹配至少减少剩余的3 4 ，在经过0 ( 1 0 9 2 n ) 次 迭代后，算法就会收敛为一个最大规模匹配眩 。没有输入被饿死，所 有的请求最后都将被响应。如果在每个信元时间一开始，就进行匹配， 惕谢响响确确 一一一一 托印端喘端端螨籼耥鼽鼽 n 肛 a a 屹 u 卜厂l 匕匕 h h g g r-叫 一一 引叫引叫 一一一二一一一 r r h 屹 u 您 ，ljir1j 2 2 l l 2 2 。l。ll = = = 翻翻翻广。1_l广_，l广_l 2 3 4 问 问 问 时 时 时 一兀 一兀 一兀 信 信 信 基于i s l i p 算法的f i f o 特性研究 这样就不需要存储器或者状态来记录刚才的连接情况。 采用随机机制，容易实现，算法简单，但也带来了其它一些问题， 首先，硬件实现比较困难，成本过高；第二，每个调度器必须在一系 列不同的变化端口中做出随机选择，如果想高速的实现它很难很昂 贵。第三，单次迭代时，p i m 算法的性能并不好，仅比单纯的f i f o 缓冲方式略好一点。 3 2r r m 调度算法 r r m ( r o u n d - r o b i nm a t c h i n g ) 算法是迭代循环算法中最简单和最 直观的算法，它形成了一个循环判定的二维数组，信元在每个输入和 每个输出之间循环调度。该算法克服了p i m 算法中的两点不足，即不 & 勘 1 ) 步襄王：薄藏每个罐 端向有跌烈言! j 动宴| ；出蔬发i 粼旁凝：箍 端3 向辐；出端2 稻4 发送释戴 步暮敬：稳应撼出藕根燕当前藐持谣度器中璃应搓针的位置选叠箍入崩台予璃应以壤出赫笏哟噔 蒜入j 融和3 誊院籀出赫残疆孑涛隶，由于麓入端2 奇璺l 藿留譬钟农- l ，所以籀出端2 l 寄予蛲入端l 孵 应。然后嚣萧璃应指铬& 指向被璃应镰入端缒下骨崆置瑶出赫铂蟪翳琏趱出端瑚螺翳& 警既k 2 ) 步景5 ：t i l l 臻 拣遴鳍娥 指钝嗣譬黼3 ) 港窟 蘸，完鹾露偶 出赫给予确认俄姬辘入蓑i ，确认指针a l - , 1 所艺l 臻 端l 网辘出赫】笈违辅靛然后更藏穗沃 箱锕旨同辟i 翟瞄蠢l 嫌出葫的下二听螳 图3 - 2r r m 调度算法的三个步骤 公平性与复杂性，它用更快的循环仲裁器代替了p i m 中的随机仲裁 器，采用优先级的轮循调度，可以公平的进行请求连接，并且可以均 匀地分配带宽，r r m 算法调度过程如图3 - 2 所示： 1 5 丑丑丑瓢黔 硕士学位论文 第一步：请求( r e q u e s t ) ，每个输入端向有信元需要发往的输出端 发送请求。 第二步：响应( g r a n t ) ，输出端收到输入端的请求后，它不是随机 的选择，而是选择优先级最高的请求。这个优先级可以从固定的轮转 顺序的优先级列表里找到。然后输出端会通知所有向它发送过请求的 输入端是否被响应。固定轮转顺序表里指向最高优先级的指针g ；比响 应的输入增加1 个单元( 模n ) 。 第三步：确认( a c c e p t ) ，输入端收到响应后，它通过固定轮转顺 序表里的当前优先级指针选择确认的输出端。同时将固定轮转顺序表 里指向最高优先级的指针a ；指向确认的输出端的下一个位置( 模n ) 。 r r m 是较简单的循环匹配算法，会因为同步问题使得吞吐率低， 并且该算法也不稳定，当负载达到大约6 3 时，就出现了这种情况。 3 3isl lp 调度算法 r r m 算法由于同步问题使得它的吞吐率很低，为此m c k e o w n 对 r r m 算法进行了改进，从而提出了s l i p 算法。s l i p 算法采用循环优 先级( 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 ” ( i - s l i p ) e 2 9 os l i p 只进行了一次迭代，因此也称为1 - s l i p 。再一次迭 代时可以对上一次没有匹配上的分组进行再一次的匹配，因此可以提 高算法的性能。每个信元周期中运用多次迭代算法，所有的输入输出 都将处于非匹配状态，对输入输出进行重新配对，但在迭代中完成的 连接就算后面可能存在更多的匹配数，也依然保持原来的状态。i s l i p 算法和先前的调度算法一样，依然由三个步骤组成。 步骤1 ：请求( r e q u e s t ) ，每个输入端向对它有信元需要发往的输 基于i s l i p 算法的f i f o 特性研究 出端发送请求。 步骤2 ：响应( g r a n t ) ，输出端收到输入端的请求后，选择当前优 先级最高的请求，优先级可以从固定的轮转顺序优先级列表中获得， 输出端通知所有请求过的输入端是否被响应。等到步骤3 完成后，若 输出端得到响应，则固定轮转顺序表里指向最高优先级的指针g ；比响 应的输入增加1 个单元( 模n ) 。 步骤3 ：确认( a c c e p t ) ，输入端收到响应后，依据当前优先级指 针选择确认的输出端，同时将固定轮转顺序表里指向最高优先级的指 针a ；指向确认的输出端的下一个位置( 模n ) 。 i s l i p 算法只有当响应被确认后，才会改变响应指针，这样不仅 减少了输出调度器的同步，也提高了性能。 1 ) 步器l 彝i 求舞趴舞向有弧雕彭鞠嗾出旄巍叁菊巍嘲：象柏觳l 磁蝴融稻砣疆i 障毪柚融 # 噍出菇2 4 发遘 蓍求 步蚕殴璃应藏出羲铱舞粥；裁器镌袭寿拍舅茧曼基叠裱入端劳横予l l 应铡知初鲐 檄簖育约蝣鼋港l 蓄铃 考8 孽于1 所以麓出畿喇；出赢搿i 撮 蘸嘴予璃应。同蠖出旃皎鹰 费3 给予翡应。迥是此2 ：手# 不 要象悔麓器的指针。具有誊劳酗籀束箍出旒氯饿a 端蠢认斑，才崩酣播同璃固 藏 位置的下一 惭 n u m i t e r a t i o n s = a t o i ( o p t a r g ) ： 基于i s l i p 算法的f i f o 特性研究 c a s es c h e d u l i n g _ e x e c 算法的运行 s e l e c t g r a n t