（计算机应用技术专业论文）交换调度算法仿真软件的设计与实现.pdf

硕士论文交换调度算法仿真软件的设计与实现 摘要 当前网络交换设备的发展方向是研究如何在高负载情况下实现高速交换。对现有 的交换设备进行硬件升级是很好的选择，但是也带来了成本的增长。为了在现有的工 艺水平上提高设备的性能，大量的工作集中在交换调度算法的研究上。输入排队类的 调度算法因为其能在内部交换结构加速比为l 的情况下实现1 0 0 9 6 的吞吐率成为了研 究热点，很多各种各样的输入类调度算法被提出。输出排队类调度算法要求很高的内 部加速比，即对硬件要求较高，在此基础上具有低延迟高吞吐量等优点。 本文的主要目的是设计出一种通用的调度算法仿真软件，该软件主要对几种常见 的输入和输出排队类轮询算法进行仿真研究，其中输入类算法包括p i m 、r r m 、i s l i p 、 d r r m 、i l q f 、i o c f ，输出类算法包括w r r 、d r r 。软件将各个算法设计成独立的模块， 并且对其仿真结果进行对比分析，从而得到在不同网络条件下各种算法的性能比较， 这样能够对算法有比较深入的认识，在高加速比情况下，输出类算法具有低延迟高吞 吐量的优点；设计良好的输入类算法在低加速比情况下也可以有很好的性能。仿真结 果显示仿真曲线的变化趋势和实际网络中算法性能曲线比较接近，说明软件的仿真效 果良好，达到了设计要求。 关键词：调度算法，轮询，通用算法仿真软件。 硕士论文变换调度算法仿真软件的设计与实现 a b s t r a c t n o w a d a y s ，t h en e t w o r ke q u i p m e n t ss u c ha st o u t e r sa n ds w i t c h e sa l er e q u i r e dt 0w o r k f a s t e rt oa c h l e v eah j 【g ht h r o u g h p u t h a r d w a r eu p g r a d i n gs o u n d sl i k eag o o di d e a , b u ti t a l s om a k e st h e s ee q u i p m e n t sm o e x p e n s i v e i n p u t - q u e u i n gs c h e d u l i n ga l g o r i t h m sc a n a c h i e v e1 0 0 t h r o u g h p u t 吖e ni ft h es p e e d u po fs w i t c h i n gf a b r i ci sl o w , s ot h e s e a l g o r i t h m sa t es t u d i e dal o t a l t h o u g ho u t p u t - q u e u i n gs c h e d u l i n ga l g o d t h n 强c a na l s o a c h i e v e1 0 0 t h r o u g h p u tw i t ha v e r yl o wd e l a y , b u tt h e yr e q u i r et h es p e e d u pt ob c n ( ni s t h en u m b e ro f i n t e r f a c e so f as w i t c ho rr o u t e r ) 。 t h ep u r p o s eo f t h i sp a p e ri st od e s i g nag e n e r a ls c h e d u l i n ga l g o r i t h ms i m u l m o r , ：s ow e c a ns i m u l a t es o m eo ft h em o s ts t u d i e di n p u t - q u e u i n ga n do u t p u t q u e u i n ga l g o r i t h m s ， e s p e c i a l l yr rs c h e d u l i n ga l g o r i t h m s , s u c ha sp i m ，r r m ，i s l i p , d r r m ，i l q f , i o c f , w r ra n dd r i la l lo ft h ea l g o r i t h m sa r ed e s i g n e da si n d e p e n d e n tm o d u l e s ，a n dt h e n a n a l y z et h e i rp e d o r m a n c e si ns o m ek i n d so ft r a f f i cm o d e l s f r o mt h er e s u l to fs i m u l a t i o n , w es e et h a to u t p u t - q u e u i n gs c h e d u l i n ga l g o r i t h m sh a v ea d v a n t a g e so fl o wt r a n s m i s s i o n d e l a ya n dh i g ht h r o u g h p u tw h e n t h es p e e d u po fs w i t c hf a b r i ci sh i g h , a n d 缸i n p u t - q u e u i n g s c h e d u l i n ga l g o r i t h mc 勰w o r kw i t hah i g hp e r f o r m a n c ei fi ti sd e s i g n e dw e l l f r o mt h e r e s u l t so fs i m u l a t i o n , w ec a ns e es i m u l a t o rt h a tt h i sp a p e ri m p l e m e n t e di sw e l ld e s i g n e d b e c a u s et h ep e r f o r m a n c e so f s i m u l a t e da l g o r i t h m sa r es i m i l a rw i t hp e r f o r m a n c eo f t h e mi n r e a ln e t w o r k k e yw o r d s ：s c h e d u l i n ga l g o r i t h m ，r o u n d - r o b i n , s i m u l a t o r 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：选生k 7 年6 月矽日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。 对于保密论文，按保密的有关规定和程序处理。 研究生虢监 叼年月嗲日 硕士论文 交换调度算法仿真软件的设计与实现 1 绪论 1 ，1 研究现状 i n t e r n e t 是由各种不同的传输和交换系统组成的一个非常庞大的分组交换网络。 通过网络传送的信息首先被封装成一个个的分组，然后每个分组都通过分组交换系统 被独立的转发和交换，并且到达它的目的地。实际上，i n t e r n e t 中最重要的交换设备 就是路由器和交换机，其核心任务就是从输入端口接收分组，并根据分组的目的地址 信息把分组转发到相应的输出端口。其中包括两个重要的功能，即路由和交换。路由 功能负责运行路由协议，计算路由转发表，运行软件对路由器进行配置和管理，它一 般由高性能的c p u 来实现。交换功能主要完成不同端口之间的分组交换，主要由交换 结构及其调度算法配合完成。 随着信息化社会的发展和i n t e r n e t 用户爆炸式的增长，用户对网络带宽的需求越 来越大，尤其是多媒体业务的不断引入，使得传统路由器已成为网络发展的瓶颈。因 此，设计高性能的连接骨干网的路由器也就尤显其重要性。随着1 i d m 技术的发展，骨 干网的链路速率基本上是以3 0 的增长速率递增，已经从0 c - 4 8 ( 2 5 g b p s ) 发展到 0 c - 1 9 2 ( 1 0 g b p s ) 和o p 7 6 8 ( 4 0 g b p s ) i l l 。对于最短长度的4 0 b y t e s 的t c p i p 分组来说， 每秒处理的分组数目也就从8 百万增加到3 千2 百万和l 亿2 千5 百万。因此，处理每个分 组的时间也就从1 2 5 n s 减少到3 0 n s 和8 n s 。这也就对交换结构的处理速度和扩展性提出 了更高的要求1 2 1 。一般认为，采用a t m 交换机可解决网络带宽的需求。大多数高性能 a t m 交换机均采用输出排队机制，而这种输出排队交换结构中由于交换结构和存储器 的速率必须为端口线速的n 倍( n 为端口数) ，当端口速率和数量增加时其硬件实现比较 困难。另一方面，传统的路由器往往采用通用的c p u 和软件方法来实现各种路由协议， 因此，c p u 的性能和操作系统的选取决定着系统的处理速度；同时，路由器各个端口 之间通过共享总线相连接，而共享总线方式决定了同一时刻只能有一个数据包在传 送，因此，总线的吞吐能力也就决定了路由器的最大吞吐率。但总线的发展却远远不 能满足网络发展的需要。在这种形式下，由于输入排队结构( i n p u tq u e u i n g ) 可以在 内部交换结构加速比为1 的情况下通过调度算法的仲裁达到1 0 0 的信元吞吐量，所以 它成为了目前的一个热点研究对象。对输入排队结构调度算法的研究也层出不穷，目 前的主要研究方法是通过计算机仿真来研究算法在各种流量模型下的性能p ”。 在输入排队结构中，最早使用的是f i f 0 队列，这种队列结构简单，易于用硬件实 现，但是存在h o l 阻塞，使得吞吐量比较低嘲；文献汹】提出了一种v o q 结构，这种结 构在每一个输入端口建立n 个逻辑队列，对应n 个输出端口，从而消除了h o l 阻塞。v o q 结构由于其实现无需额外硬件支持等优点得到了广泛应用。在输入排队类算法的研究 硕士论文 交换调度算法仿真软件的设计与实现 中，p i m ! l 、r r m 【l q 、i s l i p p 6 1 等r r 类算法由于复杂性低且硬件实现简单而且通过多 次迭代能够达至0 1 0 0 吞吐量，成为研究的热点。输出排队类调度算法相比较输入排 队类，虽然对硬件要求比较高，但是其信元延迟比较低，也就是说能够提供比输入类 算法更高的性能，如w r r l 9 1 、d r r 唧1 、w f q l l o l 、盯2q 【”l 等。 在这些算法的基础上，人们提出了很多改进方法，文献i 驺1 在i s l i p 算法的基础上 对调度步骤进行改进，提出了一种两步i s l i p 算法，在减少了延迟时间的同时保证了 良好的吞吐率；文献l 提出了一种新的基于预测的输入排队调度算法。该算法研究 了每次轮转指针的更新规律，在此基础上可以预测下一时隙某些输入和输出端口的信 元发送情况，从而提高算法性能。文献m ，针对现有r r 算法的问题，提出了调度决策 在时隙间进行迭代的思想，设计了i s l o t 算法。 1 2 常用算法仿真软件 目前使用比较多的是n s 2 网络仿真软件岬1 ，它是e h l b n ( l a w r e n c eb e r k e l e y n a t i o n a ll a b o r a t o r y ) 网络研究小组开发的仿真工具。n s 2 是一种可扩展、易配置、 可编程的事件驱动的网络开源仿真软件。文献【删详细介绍了如何在n s 2 环境中进行队 列调度算法的扩展。 i 3 主要内容和组织结构 本文旨在研究现有的各种交换调度算法的原理及性能，并在此基础上通过设计一 个通用调度算法仿真软件对常用的几种r r 类算法进行仿真。 第一章是讨论了调度算法的研究现状以及本文的主要内容和组织结构。 第二章说明了信元交换的相关概念以及信元交换结构，通过对输入输出排队交换 结构的比较来分析其性能。 第三章讨论了目前比较常见的多种输入和输出排队类调度算法，阐述了算法原 理，在理解其调度过程的基础上对其性能进行理论分析。 第四章介绍了传统的流量模型以及自相似o n o f f 突发流量模型，并对常用的网络 仿真工具n s 2 做出简单介绍。 第五章设计了通用的调度算法仿真软件，对p i m 、r 贼、i s l i p 、d r p , m 、i l 舒、i o c f 、 w r r 、d r r 等几种r r 类调度算法进行仿真研究，并给出设计流程。 第六章给出软件的算法仿真结果，在对比分析的基础上讨论各种算法的性能，从 而对算法有进一步的深入认识。 最后是全文的总结、致谢以及参考文献。 2 硕士论文交换调度算法仿真软件的设计与实现 2 分组交换结构 分组交换结构实质上是一个能将输入端口中的分组，按照其路由标签送到它所要 求的输出端口的功能块；可以说分组交换最主要的功能是路由功能。在进行交换时会 出现几个输入端口的分组竞争同一输出端口的情况，有时这种竞争还会发生在交换结 构的内部，因此交换结构必须提供分组缓存功能。根据缓冲器的位置可分为输入缓存、 输出缓存、内部交叉点缓存、共享缓存以及上述几种缓存的组合等。交换结构又有时 分和空分之分，前者包括共享媒体( 总线或环) 和共享存储器，后者则包含交叉开关结 构( c r o s s b a r ) ，n 2 分离通路( n 为输入输出端口数) 和b a n y a n 类网络等。 八十年代末，分组交换结构的研究主要集中在缓存策略的优化、构成大规模交换 网络的多级互连策略以及组播方法等，处理的单位为定长的信元。第一代a t m 交换机 的特点是缓存容量小、缓存器管理简单、无优先级调度等。经过多年的研究，a t m 交 换结构设计己趋于成熟，普遍认为：为了处理突发业务需要大的缓冲容量，应采用共 享存储器以减小整个交换机的体积。然而，由于i n t e r n e t 的迅速发展，光纤传输技术 的不断进步，传输带宽越来越高，当然对交换结构的速度也提出了更高的要求。以前 对交换结构的研究大都集中在输出排队方式，面临越来越高的带宽震求，输出缓存方 式的交换结构因其速度是端口速度的n 倍( n 为端口数) 而实现困难，越来越多的研究集 中到了长期被冷落的输入排队交换结构，这种交换结构能取得高性能，并不是采用了 什么先进的c m o s 技术，而是采用新的信元调度算法。 2 1 分组交换的相关概念 1 加速比( s p e e d u p ) ：如果每个输出端口在一个时隙内可同时接收s 个信元，就说 这种交换结构具有加速功能，s 称为加速因子。可通过时分和空分两种方法实现加速， 前者指交换结构的内部速率是外部端口的s 倍；后者则是为每个输出端口提供s 条并行 路径。 2 性能：通常用三个参数描述信元交换结构的性能：吞吐率( t p ) 、交换时延( d ) 和信元丢失率( c l ) 。t p 定义为每输入端口、每时隙成功传送到目的端口的信元平均数， 最大吞吐率( t p m ) 则是最大负荷下的t p 值。d 指的是一个信元从进入输入端口封传送到 输出端口所经历的平均时间，它由缓冲器平均排队时延和一个信元的传输时间组成。 c l 定义为交换结构信元丢失的数目与总到达数目之比，信元丢失是由于阻塞或缓冲器 溢出造成的，显然降低c l 的一个直接办法就是增加缓冲器的容量。此外，延时抖动也 是描述交换结构性能的一个重要指标，它指的是一个信元在交换结构中经历的最大时 延和平均时延的差值，通常用差值出现的概率表示；该指标对于实时业务具有重要影 响。不难看出，一个理想的交换结构应具有尽可能大的t p 、较小的时延、信元丢失率 3 硕士论文 交换调度算法仿真软件的设计与实现 和延时抖动。 3 阻塞：当两个以上信元竞争同一内部链路时，即发生内部阻塞，如传统的b a n y a n 网络就是一个内部有阻塞的网络。当两个以上信元在同一时隙指向同一输出端口时， 就会出现输出阻塞，所以必须在交换结构内放置缓冲器，以增加信元时延为代价来消 除输出阻塞。在传统的输入缓冲交换中，在一个时隙内，当f i f o 队列的队首信元参与 输出端口竞争失败后，即使排在它后面的信元指向的输出端口是空闲的，该信元也无 法输出，这种现象称为队头阻塞( h o l ) 。这种阻塞在本文中会多次提到。 4 业务量模型：到达输入端口的业务特性通常用两个随机过程描述【2 q ：一是信 元到达输入端口的随机过程，另一个是信元目的端口地址分布。信元到达的真实过程 随着业务种类的不同而变化，在进行交换结构的性能分析时一般采用随机和突发两种 业务模型。随机业务模型是假定信元到达输入端口是一独立同分布b e r n o u l l i 过程， 即在任意给定的时隙内，信元到达某一输入端口的概率为p ( o s p 1 ) ，无信元概率为 ( 卜p ) ，p 也称为输入负荷。描述突发业务的常用模型是o n o f f 模型，这种模型虽然简 单但很流行，而且在分析上可行。该模型由交替的活动( o n ) 期和沉默( o f f ) 期组成， 活动期内产生信元，沉默期不产生信元。o n 和o f f 被认为是相互独立的，而且这些时 问间隔服从几何分布。 信元目的端口地址分布有均匀分布( u n i f o r m ) 、非均匀分布( n o n - u n i f o r m ) 和组播 o m l t i c a s t ) 分布三种。当每个时隙到达输入端口的信元到达每个输出端口的概率为 l n 时，则称为均匀分布，否则就是非均匀分布。热点业务( h o t - s p o t ) 就是一种非均 匀分布，所谓热点业务就是指每个时隙到达的所有信元总有一个固定概率到达一个热 点输出端口。若设h 表示到达热点端口的概率，则输入负荷p 可表示为p = p h + p ( 1 - h ) ， 其中p h 为指向热点的信元数。目前对交换结构的分析大都采用上述模型。 2 2 输入排队结构 输入排队( i n p u tq u e u i n g ) 无阻塞信元交换结构以其高速、易于实现、便于扩展， 而成为当前研究的热点之一，而且许多高速路由器也开始采用这种输入排队交换结构 代替原来的共享总线输出缓存方式。采用信元交换结构的路由器其端口速度已经可以 和a t m 交换机一样快；同时，采用路由器代替a t m 交换机还可以增加链路带宽的利用 率、简化协议的复杂度，减轻网管的负担。 输入排队早期一般采用简单的先进先出( f i r s ti nf i r s to u t f i f o ) 的排队规 则。这样，当每个输入端口的每个时隙到来时，各个非空输入队列的队首信元如去往 同一输出端口则要进行竞争的仲裁，在竞争中失败的信元暂留在输入队列中，等待下 一时隙的竞争和传送。然而，这种交换结构存在队头( h o l ：h e a do fl i n e ) 阻塞，即 在一个时隙内当f i f o ( 先进先出) 的链头信元参与输出端口竞争失败后，即使排在其后 4 硕士论文交换调度算法仿真软件的设计与实现 面的信元指向的输出端口空闲也无法输出。在均匀b e r n o u l l i 流量下，链头阻塞使得 输入排队交换的吞吐率只有5 8 6 闸。面当输入业务量为周期性的时候，哟l 阻塞将使 交换结构性能进一步降低。 ：| ：! 坦卜一 二叶 二叶 交挽 结构 _ w 沣一 图2 2 ，1h o l 阻塞模型 为了消除h o l 从而提高输入排队交换的吞吐率，人们进行了大量的研究，相继提 出了窗口接入、群输出结构以及虚拟输出排队交换结构( v 0 0 ) 等。其中以v o o 最为有效 可行。它是通过在每个输入端口放置n 个f i f o 缓存队列，不同的f i f 0 存放p u n 个不同输 出端口的信元，通过调度算法将无冲突信元交换到输出端口。这种结构可以显著消除 h o l 。近年来提出的许多输入排队类算法都是基于v 结构的，对它们进行多方面的比 较研究并具体实现是领域内的热点问题之一。带v o q 队列的输入排队结构如下图所示； 输入l 4 固 一l ，少 l ： i输入m 皇 - 如 输出1 i三 l 输出n b 幻 峥+ 一一j 图2 2 2 输入排队结构 传统路由器大都采用共享总线和输出排队方式，输出排队方式虽然能很好地实现 对输出分组的控制从丽提供目匪务质量( q o s ) 保证m l ，但由于总线积存储器的速率必须 为端口线速的n 倍( n 为端口数) ，当端口速率和端口数量增加时实现困难。例如，对于 平= 一 硕士论文交换调度算法仿真软件的设计与实现 一个3 2 3 2 输出缓存交换机，当其端口速率为1 0 6 b s 时，即使采用5 1 2 b i t 数据宽度的 存储器其读写周期也只有1 6 n s 。同时共享总线的速率也受到负载等因素的限制。两 另一方面，输入排队无阻塞交换结构中存储器和交换结构速率与端口线速相等，非常 适用于高速和大容量交换，若仍以上述3 2 3 2 、端口速率为l o g b s 的交换机为例，当 采用输入缓存时存储器的读写周期就为5 1 2 n s ，这在目前技术水平下是可行的。因此， 近年来许多高速交换机和路由器均倾向于采用输入排队无阻塞交换结构，并将变长数 据分组在输入端截成定长的称为信元的分组，通过交换结构后重组。这里的信元指的 是类似于a t m 信元的定长分组，但可以是任意格式、任意长度。 2 3 输出排队结构 输出排队( o u t p u tq u e u i n g ) 是在每条输出端口上设置缓冲器。输出排队系统没有 队首阻塞，所以其吞吐率高于输入排队系统。理想的输出排队系统吞吐率可达1 0 0 。 但是，由于在同一时隙可能有多个信元同时到达一个输出端口，使输出排队区更容易 发生溢出而造成信元丢失，导致高的信元丢失率，这在突发业务流下尤其严重。模拟 表明1 2 1 1 ，当每个输出端口缓冲区大小一定时，输出排队系统在一定负载区问内，信 元丢失率要高于输入排队系统。另外，输出排队系统的硬件复杂度要高出不少。但是， 输出排队策略可以通过增加缓存器容量来降低信元丢失率；而输入排队因为队首阻塞 的原因，即使增加缓存容量也无法降低信元丢失率。 输出排队方式一般分为三种类型：1 、完全分隔缓存：2 、完全共享缓存；3 、混合 缓存。 ( 1 ) 完全分隔缓存：是指在每个输出端口独立设置缓存。信元到达输入端口后， 根据目的输出端口号进入相应的输出端口排队。如果对应的输出端口缓存己满，则该 信元以及以后到达的具有相同目的输出端口的信元都将被丢弃，直到该输出端口有空 闲空间为止。不同输出端口的等待信元互不影响。 ( 2 ) 完全共享缓存：是指在输出端口设置缓存，所有的输出端口共享这个缓存空 间。信元至达输入端口后，如果共享缓存有空闲空间，则该信元可以进入，并根据目 的输出端口号进入相应的逻辑队列排队。如果整个共享缓存都满了，则以后到达的所 有信元，不论其目的输出端口如何，都将被丢弃，直到共享缓存有空闲空问为止。 ( 3 ) 混合缓存：是指在输出端口不仅设置共享缓存，同时还在每个输出端口设置 独立的缓存。信元到达输入端口后，根据其目的输出端口号进入相应的独立缓存排队， 如果对应的输出独立缓存已满，则进入共享缓存排队；如果对应的独立缓存以及共享 缓存都满了，则该信元以及以后到达的相同的目的端口号的信元都将被丢弃；如果所 有的独立缓存和共享缓存都满了，则以后的到达的信元都将被丢弃，直到对应的目的 输出端口的独立缓存或共享缓存有空闲空间为止。 6 硬士论文 交换调度算法仿真软件韵设计与实现 由于输出完全分隔共享在每个端口设置独立的缓存，不同端口的信元互不干涉， 因此具有良好的公平性；但是可能造成某些端口的信元丢失率很高，而某些端口缓存 较空闲的情况，因此缓存的利用率不高。输出完全共享缓存由于所有的输出端口共享 一个缓存空间，因此缓存的利用率很高，从而降低信元丢失率。但它也存在这种可能： 菜一个端口在一段时间接受了大量信元，导致缓冲区耗尽。这样，其它端口的信元丢 失率会上升，容易造成少数几个输出端口的信元占据整个缓存空间，造成整体性能下 降，因此其公平性较差。并且它的硬件代价较高，要求共享缓冲器的存取速度为端口 链路速率的2 n 倍，n 为共享端口数。而输出混合缓存的性能，则介于以上两者之间。 2 4 组合输入输出排队结构 组合输入输出排队结构( 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 q 结构结合了输入排队和输出排队的特点。在输入端，仍然使用了v o q 结构， 同样是为了消除h o l 阻塞；在内部交换结构的交叉点设置小缓存结构，这样使得输入 和输出调度分开。其中输入调度主要解决多个v o q 对输入端口到交叉节点链路的竞争， 而输出调度主要解决一个时隙内c r o s s b a r 的一列有多个交叉点缓存非空时，输出链 路竞争问题。可以看出，这两种调度分别就是在输入排队结构和输出排队结构中的主 要解决问题，所以c 1 0 q 结构从理论上来说能够克服输入排队和输出排队的不足从而达 到非常好的性能。 2 5 本章小结 本章主要介绍了信元交换的相关基本概念以及两种基本的交换结构：输入和输出 排队结构。虽然输出排队能够很好的实现低延迟和1 0 0 的吞吐量，但是它对内部的 交换部件加速比要求比较高，其硬件实现比较复杂。而输入排队在好的调度算法基础 上即使加速比为1 也能实现1 0 0 的吞吐量，所以得到了业界的广泛关注。另外组合输 入输出排队结构理论上具有输入和输出排队的优点，目前处于研究之中。 7 硕士论文交换调度算法仿真软件的设计与实现 3 分组调度算法 3 i 调度算法的定义和分类 调度算法是按照一定的规则对交换节点的不同业务进行缓存、调度和服务，同时 实现流量的管理与控制、冲突处理、带宽的分配与管理等功能。简单来说，调度算法 是通过解决一个二部图的匹配问题来找到匹配。下图为二部图匹配的示例。 图3 1 i 定义g = i v y 为顶点集合v 与边集合e 所构成的无向图，连接项点i ，( 1 i 日1 ) 和j ( 1 j s n ) 的边权重为1 。左图为匹配之前。右图为匹配完成以后。在图g 上的匹配m 是在m 中 任意两条边没有公共顶点的边集合e 的子集。 在一个二部图的最大规模匹配可以解决一个同等的网络流量问题。称这个算法为 最大规模算法。现在有许多算法解决这些问题，现今已知最有效的聚合复杂度为 o ( n ”2 ) 。这个算法虽然可以找到最大值的匹配，但它复杂度太高，难以实现，而且 执行时间太长。 认识到最大规模匹配是不尽人意的，这是重要的。仿真实验表明，最大规模匹配 在均匀的独立到达下可以实现1 0 0 的吞吐率【“，然而其缺点也很明显。第一，在可 接受的流量下，特别在非均匀的流量模式下，它会导致不稳定性与不公平性。图3 l2 左图就是2 x 2 交换机的这种行为的示例。到达交换机的流量模式为标准的柏努利流 量，性能是通过仿真来获得的。虽然流量是可接受的，但维持最大规模匹配算法是不 可能的。第二，在不可接受的流量下，最大匹配算法可导致饿死现象。图3 1 2 右图 就是这种行为的示例。很明显，由于所有的三个队列被永久地占用，算法总是只选择 输入1 到输出2 和输入2 n 输出l 的匹配。现在的调度算法大多数只要求达到极大匹配即 可。 8 颈士论文交换调度算法仿真软件的设计与实现 2 o 镐 脚2 o 柏 丸= 1 托2 0 知= 0 4 4绚= o 4 4 5 1 如= 1 图3 1 2 左图显示了流量到达情况：右图则显示了在不可接受的流量下，最大规模匹配总是只服 务两个队列，而把从输入1 到输出1 的队列饿死 调度算法的性能主要由吞吐量、时延特性、公平性和复杂性这四个方面的特性决 定，下面分别介绍这四个性能指标。 吞吐量：吞吐量是单位时间内传送通过网络的给定点的平均比特数，一般来说， 将吞吐量除以信道传输速率，可使其归一化，其值通常在0 和1 之间。作为路由器性能 指标的吞吐量通常指的是归一化的吞吐量。吞吐量决定路由器处理数据包的能力，好 的调度算法应该具有高的吞吐量。 时延特性：时延特性分平均时延和时延抖动两个方面。好的调度算法应可以为特 定的业务流提供端到端的对延保障。时延速率调度器( l r s ：l a t e n c y - r a t es e r v e r ) 模型可用于分析网络中不同调度算法带来的端到端时延 1 4 1 ，对于定长分组情况，应 用速率分隔时签调度器( r s t ：r a t e - s p a c e t i m e s t a m ps c h e d u l e r ) 模型分析会更有效 嘲。 公平性：公平性是指链路带宽必须以公平合理的方式分配给共享链路带宽的业务 流。因此高性能的调度算法应可以隔离不同的业务流，这样即便发生高突发型业务也 不至于影响其他正常业务流。单位时间内不同业务流因为约定的服务速率不同因而获 得的服务量也不相同，因此通常采用归一化服务量( 单位时间的服务量与分配服务速 率的比值) 服务公平指数( s f i ：s e r v i c ef a i r n e s si n d e x ) 1 9 1 来衡量。另外最坏公 平指数( w f i ：w o r s t - c a s ef a i r n e s si n d e x ) p o 】也用来衡量调度算法的公平性，较大 的w f i 意味着调度输出业务存在较大的突发性。 复杂性：复杂性指的是算法复杂度和工程中的易于实现性和易于扩展性。高速网 络中传输一个分组的时间很小，所以调度算法必须能在很短的时间完成对分组的调 度，因此调度算法必须有很小的复杂度。而且好的调度算法应该易于硬件实现。且具 有良好的可扩展性。 按照系统的工作模式划分，调度算法可以分为尽职工作型( w o r k - c o n s e r v i n g ) 和 非尽职工作型( n o nw o r k - c o n s e r v i n g ) f 4 11 5 1 。采用尽职工作型调度算法时，只有缓存 器中没有待发送的包时，输出链路才会空闲，典型算法包括：一般处理机共享 6 p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 1 6 1 、加权公平排队w f q l 7 1 又称p g p s ( p a c k e t 9 颈士论文交换调度算法仿真软件的设计与实现 g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 、加权轮询调度w r r t * j ，和差额轮询调度d r r l 9 1 ；而 非尽职工作型调度算法则可能在缓存器中还有包时输出链路空闲，典型的算法包括： 分层轮询h r r ( h i e r a r c h i c a lr o u n dr o b i n ) p o ，s t o p - a n d - g o 调度算法【1 1 1 和 l i t e r - e d d ( j i t t e re a r l i e s td u ed a t e ) 【1 2 1 。 尽职工作型调度算法可以最大限度地利用输出链路的带宽资源，丽非尽职工作型 调度算法在控制时延抖动时往往是一种较好的选择，即数据包可以进行时延以满足特 定的时延要求。尽职工作型调度算法具有平均队列时延最小的特征，而且对所有尽职 工作型调度算法，平均队列时延是一样的。不同的调度算法可以采用不同的函数去选 择最合适的包发送顺序，但平均队列对延总是相同的，这表现，采用不同的调度算法 时，各种业务受到的服务优先级不同引起的一般是排队时延大小的不同，由此也可看 出调度算法在保证业务的q o s ，特别是实时业务的时延特性方面起着举足轻重的作用。 按照处理单元分类，分组调度算法分为基于时标t s ( t i m e - s t a m p ) 的调度算法和 基于轮询r r ( r o u n dr o b i n ) 的调度算法。基于时标的调度算法是根据一个系统虚拟时 间( v i r t u a lt i m e ) 为每个分组维持两个表明开始服务和结束服务时间的时标，系 统选择最小结束服务时间的分组服务。典型的基于时标的调度算法包括加权公平排队 唧，虚拟时钟v c p n 和自时钟公平排队s c f q 【9 1 等。其中w f q 调度算法最为引入注目， 并衍生出许多变体，如盯2 q ( w o r s t c a s ef a i r w e i g h t e d f a i rq u e u i n g ) 0 0 和w f 2 q + n 1 】 等。 基于轮询的调度算法是调度器循环地对每个队列进行轮流服务，不需要进行时标 比较，实现比较简单。典型的r r 调度算法包括w r r 例和d r r ”1 等。w r r 采用不同的实 现方法平滑了大权重数据流的输出，减少了流输出的突发性；而d r r 考虑的分组大小 和业务流权重的不同，因此它被认为是公平的，并且可用于变长分组的网络中。但是 d r r 服务一个流的时间与这个流权重的大小成比例，因此会导致流的输出产生较高的 突发性。 所有r r 类调度算法的实现都很简单：而且大多数都具有o ( 1 ) 的算法复杂度和可 扩展性。但这类算法业务流的时延是和业务流数目相关的，无法提供和t s 算法相比拟 的时延性能。所以，调度算法的时延性能和算法复杂度是一对矛盾，时延性能好的调 度算法，其算法复杂度都比较商；而算法复杂度简单的调度算法，其时延性能往往无 法令人满意。 调度算法又是和交换结构紧密相关的，目前的交换结构主要包括四种：基于输入 排队交换结构、基于输出排队的交换结构、基于联合输入输出排队的交换结构、基于 并行分布式结构模拟输出排队的调度策略。 1 0 硕士论文交换调度算法仿真软件的设计与实现 3 2 输入捧队调度算法 最大匹配类输入排队调度算法主要考虑的是在每一次的匹配过程中如何在输入 和输出之间达到n 对n ( n 是端口数目) 的最大匹配，但是一般来说这种最大匹配比较 难以达到，所以算法实际考虑如何达到极大匹配，即使得满足算法规则的匹配达到最 大，如p i 粥3 、r r m 、i s l i p t 6 、d r r m ! 捌等。而最大权重类算法则考虑如何在输入和 输出之间找到使得权重最大的匹配，这个匹配有可能是极大匹配。权重的选择可以是 队列的长度，如i l o f 算法【恻；也可以是队首信元的等待服务时间，如i o c f 算法【4 8 1 。 3 2 1p i m 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 为1 6 端口，i g b p s 的a n 2 交换机开发的。p i m 算法的随 机性避免了某些端口的资源匮乏性。 p t m 算法的基本思想是：在每个信元发送的时隙，通过多步迭代，在输入端口和 输出端口之间匹配尽可能多的发送通道。它利用随机数来防止仲裁中的不公平性，并 加快收敛，减少所需要的迭代步数。在信元开始发送时，所有的输入和输出端口状态 都标为空闲；在每一步迭代之后，都有一部分输入端口和输出端口被随机匹配上；在 每一步迭代中，都只考虑尚未匹配上的端口。 文献1 1 6 】的仿真结果显示，p i m 因为其随机选择的局限性，算法性能并不高，上限 为6 3 左右；同时这一特性也使得算法的公平性不好，同一端口很可能在多次信元时 隙内都得不到调度。 p i m 算法的特点如下： 1 如参考文献【l q 所分析的，每一步迭代，该算法平均可以匹配到余下的可能匹 配数目中的3 4 ，因此，该算法能够在o ( i o g ：n ) 次迭代内收敛到最大匹配结 果。 2 它可以确保所有的发送请求最终总能得到授权，因此，没有端口会由于得不 到发送机会而阻塞。 3 这种算法是时间独立的，每一次的仲裁都是独立的。与前后各次仲裁没有关 系，也不需要存储器来记录以前的仲裁中各个端口获得发送机会的频度。 4 硬件实现比较困难，或者成本过高。 5 单次迭代时，p i m 算法的性能并不好，仅比单纯的f i f o 缓冲方式略好一点。 3 2 2r 融l r r m ( r o u n d - r o b i nm a t c h i n g ) 算法是迭代循环算法中最简单和最直观的算法，它 1 1 硕士论文 交换调度算法仿真软件的设计与实现 形成一个循环判定的二维数组，信元在每个输入和每个输出由循环调度。r r m 算法潜 在地克服t p i m 算法中的两点不足：复杂性与不公平性，它用更快的循环仲裁器代替 p i m 中的随机仲裁器，优先级的轮循调度使算法均匀地分配带宽，也使请求连接更加 公平。r r m 的问题在于其输出端轮转指针的更新规则带来的输出端指针同步问题，使 得算法无法达到1 0 0 吞吐率。 文献呻1 给出了r r m 算法的仿真结果。从结果可以看到，负载较低的时候，r r m 算 法的性能和i s l i p 算法类似；随着负载的增加，输出端口指针同步问题使得r r m 的最大 吞吐量大约在6 5 左右。 r 硼算法的特点如下： 1 由于其轮转指针的轮转规则，最低优先级最先连接。 2 最多经过n 次迭代就能达到最大匹配。 3 在较重的负载下，同一输出端口队列有同样的吞吐量。 3 2 3i s l i p 为了减少r r m 算法中输出端口仲裁同步的问题，文献f 圳提出了i s l i p 算法。这里 的i 是迭代( i t e r a t i v e ) 的意思，当迭代的次数为n 时，称之为n _ s l i p 。i s l i p 算法的目 的是为了有效、公平、快速地匹配一个输入队列调度器的输入端口和输出端口。它在 每个时隙采用多次迭代来选择交叉开关的配置，使输入端口和输出端口尽量达到极 大匹配。i s l i p 算法采用轮循匹配来轮流调度每个有效输入端口和输出端日，而且 i s l i p 是一种优先级轮循匹配算法，用于仲裁输入和输出端口之间的匹配。 算法的基本思想是：一个新时隙开始时，所有的输入和输出端口都没有匹配；在 每次匹配之后，只有尚未匹配的端口有资格参加下一轮的匹配，传送通道一旦建立， 就不会在后面的迭代中被取消，即便重新匹配能够得到更多的匹配数目；算法在迭代 收敛时或迭代次数达n n 次后停止。其中，迭代收敛是指在新一轮的迭代中没有匹配 出任何新连接。 文献【嘲同时也给出了i s l i p 算法的详细仿真结果，如图3 2 3 1 所示。从结果上 可以看出，相比较r r m 、i s l i p 输出端口的轮转指针同步次数减少很快，从而性能比r r m 提高不少，能够达到1 0 0 的吞吐率。多次迭代的s l i p 算法在高负载率的情况下能够 显著降低信元平均延迟从而提高系统的性能。在突发流量模型下，算法的表现不尽如 入意。 硕士论文 交换调度算法仿真软件的设计与实现 图3 2 3 ii 溯均匀b e r n o u l l i 流量下p l l l 、瑚搠i s l l p 算法性能比较 算法的特点如下： 1 如果某对输入输出匹配成功，该输入输出在下一次匹配中具有最低优先权。 2 没有连接会“饿死”。因为要求指针在第一次迭代后不修改，一个输出将继 续授权给最高优先权的请求输入直到成功。 3 具有一次迭代的i s l i p ，在重负荷下，具有公共输出的排队有相同的吞吐量。 4 具有多于一次迭代的i s l i p ，在重负荷下具有公共输出的排队有不同的吞吐 量。 5 算法至多n 次迭代收敛，每次迭代将调度0 个、1 个或多个连结。假如在一次迭 代中有0 个连结被调度，那么算法已经收敛，如果迭代只有一个连结被调度， 那是最慢的收敛发生了。 双向轮转匹配g h ed u a lr o u n d r o b i n 赫a t c h i n g ) 【3 7 1 是一种较新的算法，具有 可扩展性好，低复杂度的特点。该算法中在每个输入端也放置n 个v o q 队列，输入调度器 按照固定轮转顺序选择非空v o q 队列向输出端发送请求。输出端最多接收n 个请求，从 轮转顺序中选择一个应答。 d r 铷与i s l i p 相比有两个变化，其一是i s l i p 的输入端向输出端共发送n x n 个请求， 硕士论文交换调度算法仿真软件的设计与实现 而d r 眺只发送n 个请求；其二是i s l i p 最后需要输入端向输出端发送确认信号，而d r 跏 则不需要此步骤，这样既节省了操作步骤，又节省了数据的传送。医此就使得n r 蹦更如 简单，可扩展性能好。d r r m 调度算法是公平的，而且不会出现饿死现象。 文献田1 同样给出了d r r m 算法的仿真结果。在均匀输入负载的情况下，它同i s l i p 一样能够达到1 0 0 9 6 的吞吐率。对均匀输入负载，同一次迭代i s l i p 相比，低负载时平均 延迟稍稍高