（概率论与数理统计专业论文）三阶段路由器的性能仿真.pdf

摘要 本文的主要目的是在c i o q 型传统路由器的基础上提出一种新颖的三阶段路 由器，它能很好的支持优先级服务。本文所做的主要工作是完成这种路由器的结构 设计和性能仿真。 本文第二章通过对大量文献的收集和综述，对高端路由器的发展做了简单的回 顾，对路由器的基本模式、系统设计、性能评估等的发展现状进行了较全面的介绍， 给出了各种性能指标的概念，尤其对体系结构中的算法部分给出了较完整的论述。 第三章给出了三阶段路由器的结构设计，并建立模型，然后用数学程序进行仿 真模拟，重点是第二节的仿真模型和第三节的仿真的实现。 第四章进行仿真结果的统计和计算，给出这种新型路由器的一些性能指标参 数，主要包括时延( d e l a y ) 、丢包率( 1 0 s sr a t i o ) 、吞吐量( t h r o u g h p u t ) 等，并与 不支持优先级的两阶段路由器的性能进行了比较，其仿真结论是三阶段路由器能很 好的支持优先级，并在时延和吞吐量方面有一定的优越性，这一点在仿真结果部分 由数据表和图形可以清楚的体现出来 最后，附上部分仿真程序，以供参考。 关键词：仿真模拟；性能评估；时延；丢包率；吞吐量 a b s t r a c t i nt h i sp a p e r , w ed e s i g nan e wt h r e e s t a g er o u t e ri n s p i r e db yt h et r a d i t i o n a l c i c qt y p er o u t e r ，w h i c hi sb e t t e ri ns u p p o r t i n gp r i o r i t y t h e nw ec o n s t i t u t e 1 t s f a b r i c8 n de v a l u a t ei t sp e r f o r m a n c et h r o u g ht h es i m u l a t i o n i nc h a p t e r2 ，w er e v i e wt h ed e v e l o p m e n to fr o u t e r sa n dc o m p r e h e n s i v e l y 1 n t r o d u e eb a s i cp a t t e r n s ，s y s t e md e s i g na n dp e r f o r m a n c e e v a l u a t i o nr e l a t e dt ot h e m _ w 色d r e s e l l tt h ec o n c e p t i o n so fs o r t so fi n d e x e s ，e s p e c i a l l yd e t a i l e da n a l y s m o i lt h e a l g o r i t h m si ns y s t e ms t r u c t u r e i nc h a p t e r3 ，w et r yt om o d e la n d s i m u l a t es w i t h i n gf a b r i c s f i r s t l y , w ec o n s t r u c t t h r e e s t a g er o u t e ra r c h i t e c t u r e sa n d d i s c r i b ei t sc o m p o n e n t s t h e nw et r yt os l m u j a t e s w i t h i n gf a b r i c s i nc h a p t e r 4 ，w ef o c u so nd i s c u s s i n gi t sp e r f o r m a n c ea c c o r d i n gt ot h r o u g h o u t ， t i m ed e l a y ，l o s 乞r a t i oa n ds oo n w ec o m p a r et h ep a r a m e t e r sw i t ho t h e ra l g o r i t h m s j u d g i n gf r o mg r a p h e sa n dt a b l e s o u rd e s i g nh a sb e t t e rp e r f o r m a n c e t ot h ee n d ，w ea t t a c hp a r to fp r o g r a mc o d ei na p p e n d i x 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 ；p e r f o r m a n c em e a s u r e s ；d e l a y ；t h r o u g h p u t 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：朱朋 日期：二零零八年三月二十日 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文 的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版保密的 学位论文在解密后适用本规定。 学位论文作者签名：朱朋 e l 期：二零零八年三月二十日 第一章引言 随着网络在人们工作和生活中有价值的实际应用不断涌现，网络已成为加快社 会向信息化迈进不可缺少的基础设施。在计算机网络中，网络节点必须由高性能路 由器来承担，所谓路由就是通过相互连接的网络把信息从源点移动到目标点的活 动。路由器的主要任务就是为经过的每个数据包寻找一条最佳传输路径，并将该数 据快速有效地传送到目的点 高端路由器是i n t e r n e t 骨干网建设的核心设备由于网络规模和容量的飞速增 长，以及多业务的发展、网络用户规模的急剧膨胀、宽带用户业务需求日益迫切以 及人们对用户服务质量( q o s ) 要求的不断提高，网络的宽带化和高速化建设势在必 行。现在路由器设计要解决的不仅是支持高速链接速率，具备大容量的处理能力， 还要能提供一定的服务质量( q o s ) 保证。 在路由器的设计中，对于所采用的特定结构，设计路由调度算法是路由器研发 中的核心任务。如何设计出一种无阻塞、大吞吐量、算法复杂性低、易于并行处理、 易于硬件实现的路由调度算法，一直是路由器设计的重要组成部分一旦完成路由 器的结构设计及调度算法的设计，一个路由器的完整的设计方案也就基本形成了。 在对这个设计方案具体实施之前，通常还要对这个设计方案进行性能评估众所周 知，核心路由器的优化设计的最大难点就是：在结构设计及调度算法设计的前提下， 对系统的性能做出评估，其目的是发现结构设计的缺陷及检验众多参数设计的合理 性。就目前来说，仿真技术是对路由器性能评估的最直接、最稳妥的手段了如果 能通过数学技术的应用，具体来说，就是对既定的设计方案，通过建立适当的数学 模型，应用相关的数学技术对系统的性能定量地做出评估，由于数学模型具有通用 性、可移植性等优点，我们就能很快在众多的设计方案中找出较好的设计，并能对 各种参数的组合进行优化。 当前的i n t e r n e t 仅支持尽力发送业务，不能提供( q o s ) 服务，所以迫切需要研 究一种支持优先级的新型路由器，本文在c i o q 结构的基础上，提出t h r e e s t a g e 结 构的新型路由器，并对其进行了仿真，主要目标是通过对这种路由器的设计方案， 制定相应的仿真措施，在实践中探索出一套针对路由器性能评估的仿真技术，内容 包括：( 1 ) 信号源的构造( 网络流的模拟) 。如均匀流与非均匀流的模拟，即如何在 计算机上用数字方式产生均匀流与非均匀流，又如允许流的产生技巧等( 2 ) 并行 转发的处理技术路由器对数据包的转发往往是利用硬件的特性进行并行处理，以 缩短处理时间，提高处理速度在对系统仿真时，如果采用多线程技术编制并行算 法，需要很高的编程技巧，而且运行起来对计算机的配置要求也很高我们通过用 时间的串行来换取空间上的并行这种技巧，就可以在普通p c 机上对这种复杂系统 2 进行仿真。 这次仿真主要针对性能指标中的时延、吞吐量、平均队长、丢包率等做了统计 分析，并进行了简单计算，仿真结果表明，在这种模型下，有效支持优先级服务， 多项性能指标显示的结果很不错，排队交换系统可以达到1 0 0 的吞吐量，丢包率 几乎为0 。而且，从理论上讲，这种结果的出现并不需要过高的硬件支持。 虽然本文只是对某种特定的路由器的性能进行仿真，但上述仿真技巧及思路对 现行高端路由器的性能仿真都是有效的。理论上讲，利用统计学的原理对仿真获得 的数据进行处理，我们可以分析出人们共同感兴趣的路由器的所有性能指标，本文 择其要者加以仿真，其它的性能指标或者通过对程序稍加修改即可获得，或者利用 现有的数据进行统计分析而得到。所得到的结果，有的通过数据表格的方式显示， 有的则是利用计算机中可视化技术以图形的方式显示，以强化感性的认识。本文最 后附有部分仿真程序供参考。 3 第二章路由器的发展与设计 第一节路由器的发展过程 路由器是i n t e r n e t 网络中的关键设备，其主要功能是实现路由选择和网络互 连现代社会对于计算机网络的要求已经发生变化：多媒体数据的增加、群件技术 的发展、需要高带宽支持的各种应用都在某种程度上促进了路由器的加速发展。目 前，对于网络客户分布的越来越广，移动程度越来越高以及i n t e r n e t 服务要求不断 提高，传统的路由法则已经越来越不适应需要，随着科技的逐步发展，路由技术也 在不断提高。提高路由器的速度有许多方案，但基本都围绕两个基本原则：减少路 由计算和提高路由性能。 体系结构发展过程 从体系结构看，路由器经历了从单处理器到并行处理器，从共享总线到交换结 构的发展过程我们可以把它划分为4 种类型 第一代路由器：单处理器共享总线式结构 第一代路由器是在单处理机上基于软件实现的它由通用处理器和总线联接的 多个接口卡组成，如图1 所示。 总线 图1 传统的基于总线的路由器结构 由于数据要在存储器中予以缓冲，就使其接收、发送要两次通过总线，成为系统的 主要瓶颈这种结构性能低，其主要原因是 ( 1 ) c p u 必须处理所有过路的包，成为严重的处理瓶颈； ( 2 ) 路由器中某些处理任务要对存储器频繁的访问( 如查表) ，这就难以缩短包 处理时间； 4 ( 3 ) 数据包在两个路由器之间的转送时间超过包头处理时间，这就使计算机的 i 0 ( i n p u t o u t p u t ) 总线成为路由器吞吐量的约束 这些因素都使得这种结构的路由器不能适应千兆位网络接口卡的吞吐量的要 求 第二代i p 路由器：多处理器共享总线式结构 第二代i p 路由器使用了分布式包发送操作，分布式快速处理器和路由芯片减 轻了系统总线的负载此外，也可以使用并行方式的多重发送引擎在端口具有不 同运行等级时，这种方式可以对来自端口的负载进行平衡 在第一代路由器中，所有的路由计算都由中央处理器完成，在高速和动态变化 的网络环境下，路由计算的能力将制约路由器的转发速率。第二代路由器采用多处 理器共享总线式结构、把转发计算分布在各个处理器上，从而有效地解决了路由计 算能力的问题。 这种结构的主要问题是共享总线的容量直接限制了路由器的吞吐量，成为系统 无法避免的瓶颈。另一个问题是，这种结构很难用在主干网络路由器上由于主干 网络路由器具有很高的包转发速度因此在网卡上，路由一般不具有局部性。在这 种情况下，网卡上的高速缓存器很难发挥作用也很难减轻主c p u 的负担。 为了解决第二代路由器中的系统总线瓶颈问题人们提出了多处理器交换式结 构，在第三代和第四代中以交叉开关作为系统的基本结构，如图2 。 图2 交换式路由结构 第三代路由器：多处理器交换式结构 在这种结构中，系统总线被交换机所代替。用交叉开关代替共享总线，能提供 比共享总线高得多的带宽，这就为接口卡之间传送包提供了足够的带宽并使吞吐量 成数量级地增加，足以支持现有的高速网络接口，因此接口卡之间的连接单元不再 是瓶颈，干兆位级的路由器就是以这种结构实现的。 5 旧的问题解决了，新的问题又随之而来在这种路由器中，包处理成了新瓶颈， 为了提高处理的速度，人们又提出了新的体系结构。 第四代路由器：共享并行处理器交换式结构。 在第四代路由器中，为了对服务质量提供更好的保证，端口需要把包按预先定 义的服务类型予以分类由于全部处理和缓冲分布在可使用的接口和c p u 上因 此可以有效地解决处理和存储的瓶颈问题 第二节路由器的结构设计 现在，路由器的设计方案，都朝着以下几个方面在努力，第一，数据交换带宽 越来越大，第二，数据处理能力越来越强。第三，控制服务质量的能力越来越强。 第四，扩展能力越来越强 目前，控制信息的传输已经成为调度算法性能提高的主要瓶颈。所以，高性能 交换结构及其调度算法已经成为研制高速i p 路由器的核心内容 交换结构是宽带i p 路由器中的关键部分，是解决高速报文转发的主要方式，它 的性能直接决定了路由器的性能。交换结构一般可以采用交叉开关矩阵( c r o s s b a r ) 和共享内存结构两种方式来实现。交叉开关的速度受调度器的限制，而共享内存的 速度受内存访问速度的限制。交叉开关和共享内存都能够达到比较高的吞吐率，即 都能够达到每秒4 0 g b p s 以上的吞吐率 目前，大多数路由器采用以c r o s s b a r 交换开关为核心的分布式结构。c r o s s b a r 结构在使用时所面临的问题有：阻塞问题和吞吐率；服务质量保证，即队列的 调度应该考虑交换优先级比较高的信息，同时还要能够控制包的延迟发送以满足 q o s ( q u a l i t yo fs e r v i c e ) 的需求【7 】；算法实现的简单、有效 当多个连接请求共享一个物理通道时，必须对到来的信息包进行缓存，否则就 会发生丢包现象。因此，为了提高交换能力，c r o s s b a r 交换开关中广泛采用了缓冲 队列技术。 按照缓冲区在交换结构所处位置不同，可以分为输入排队结构i q ( i n p u t q u e u i n g ) 、输出排队结构o q ( o u t p u t q u e u i n g ) 乖组合输入输出c i o q ( c o m b i n e d i n p u t o u t p u t q u e u e d ) 结构。 最早期由于硬件等技术的限制，多采取1 q 结构，但由于其性能的局限性，很 快这种结构就被o q 结构替代，o q 结构的各项性能指标在正常条件下均优于i q 结构文献 3 】中已经对交换开关中的排队机制设置在输入端还是输出端进行了很 多研究。研究表明当较好的利用存储器实现共享缓冲区时，输出排队o q 可以比在 输入缓冲排队i q 提供更好的性能。与在输入排队相比，输出排队可以获得较高的 吞吐率，并且对各种信息包长度均可以提供较低延时等。这是文献 3 】的重要结论 6 之一。 在一段时间内，输出排队表现出极大的优越性。输出排队可以实现1 0 0 的吞 吐量以及时延控制和q o s 保证，但是由于输出队列和共享内存对内存吞吐量要求 很高，使用输出队列o q 和共享内存s m ( s h a r e dm e m o r y ) 的交换结构需要n 加速 比，在当时的工艺水平下很难实现高性能的输出排队交换结构f4 1 。 随着技术水平的提高，随着物理链路传输速率的不断提高和服务要求的多样 化，现在一般采用在输入端和输出端同时缓存排队的机制，即c i o q 结构。文献 1 5 】已经在理论上证明了c i o q 排队方式在加速比为2 的情况下就足以模拟任何 输出排队的输出效果，因此可以在输入端和输出端采取适当的分组调度算法来对不 同的应用提供服务质量保证。 路由器体系结构的设计方案一直受制于成本、端口数目、性能和可采用的技术 等因素，这也是高端路由器和低端路由器的区别所在。 第三节路由调度算法 输人类调度算法 在输入调度算法中分为最大数量匹配算法( m a x i m a ls i z em a t c h i n g ) 与最大 权重匹配算法( m a x i m u mw e i g h tm a t c h i n g ) 1 最大数量匹配类算法( 早期算法总结) 最大数量匹配可以通过求解等价网络流问题法来获得，有很多算法可以求解网 络流问题，目前最有效算法的时间复杂度为o ( n 2 。5 ) 最大数量匹配算法在流量独 立、均匀、允许时可以获得1 0 0 的吞吐量，但最大数量匹配算法在流量容许的请 求下可能存在不稳定性和不公平性，尤其是对于非均匀流，在流量非允许时可能出 现饿死现象 1 3 由于硬件实现复杂度和算法时间复杂度过高，因此采用一些迭代 算法来作为近似算法，如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 r r m ( t h ed u a l r o u n d r o b i nm a t c h i n g ) 、r r m ( r o u n dr o b i nm a t c h i n g ) 、i s l i p ( i t e r a t i v e r o u n dr o b i nm a t c h i n gw i t hs l i p ) 等。这些算法易于硬件实现，并且能快速找到一 个极大数量匹配( m a x i m a ls i z em a t c h i n g ) ，但由于这些近似算法用于模拟最大数 量匹配算法，因此这些算法也可能出现不稳定性和不公平性下面将介绍一些典型 算法，并对其进行详细分析。 最简单的调度f i f o 排队算法，也称先来先服务( f c f s ) 排队，思想比较简 单：先到达路由器的分组先被发送，路由器中维持一个方式对待队列，系统每次发 送位于队列头部的数据包，新到的数据包则加到队列的尾部：理论上在一个头进尾 出的对待队列中每个到达路由器的数据包都有被发送的机会，实际却并非如此，路 7 由器本身的缓存空间是有限的，对待队列不可能无限大，无法存储每一到达的数据 包，当一个新的数据包到达，而路由缓存已满时，需要一个丢弃策略来决定丢弃哪个 分组。加入这个最新到达的数据包被丢弃，就是队尾丢弃( t a i ld r o p ) 策略。f i f o 排队方式引起的一个严重问题就是队首阻塞，即使缓存足够大，如果某一输入队列 的队首信元被阻塞( 由于被发往同一输出目的地的另一不同输入信元阻塞) ，则同 队列中其他的信元就不能被转发，甚至是不能被转发的其他信元的输出端口当前为 空闲。尤其在数据流突然增大或者同时去一个目的地的数据包大量增加时，路由器 的性能将会严重下降，时延增大，丢包率增加，吞吐率减小等等为了解决队首阻 塞问题，经过多次研究【1 3 】，产生了虚拟输出队列v o q ( v i r t u a io u t p u tq u e u e d ) 排队方式，即每个输入到每个输出都建立一个缓冲队列，这样自然就不会出现链头 阻塞问题。但是相对的，v o q 排队需要的缓存非常大。 随着技术提高，出现了各种各样的调度算法。在不同的硬件条件下，每种算法 或多或少有着一定缺陷，相对的，对于不同的性能指标，每种算法也有自己的优势 所在。 最大双向匹配( m a x i m u mb i p a r t i t em a t c h i n g ) ，即在输入和输出之间达到最大 匹配，复杂度为o ( n 2 。5 ) ，虽然能保证找到一个最大匹配，但实现过于复杂，运算 时间太长。而实际中最大匹配并不是必要的，容易引起不稳定和不公平，而且能导 致饿死。 并行迭代匹配算法p i m ( p a r a l l e ll 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 er o u n dr o b i nm a t c h i n gw i t hs l i p ) 算法都 是迭代类的匹配算法，每次迭代分为三个步骤，请求、响应和确认。所有的输入输 出都初始化为未匹配，所不同的是响应和确认的规则，并行迭代用的是随机选择， 基本轮转算法是按固定轮转顺序表进行，而i s l i p 则是在轮转顺序的指针更新上更 为优化。在性能上，对均匀输入负载，单次迭代i s l i p 就能达到1 0 0 的吞吐率， 也能保证公平；对非均匀输入负载，i s l i p 一次迭代吞吐率较小，p i m 虽有欠公 平，但多次迭代的吞吐率比i s l i p 高。最大匹配类算法的复杂度为o ( n 2 5 ) ，p i m 的复杂度为o ( n l o gn ) 。实际中应用较多的是易于用硬件实现的i s l i p 算法。 双向轮转匹配d r r m ( t h ed u a lr o u n d r o b i nm a t c h i n g ) ，双向轮转匹配 是可扩展性好，低复杂度的一种较新的算法。该算法中在每个输入端也放置n 个 v o q 队列，输入调度器按照固定轮转顺序选择非空v o q 队列向输出端发送请求， 输出端最多接收n 个请求，从轮转顺序中选择一个应答 双向轮转匹配与i s l i p 相比有两个变化，其一是i s l i p 的输入端向输出端共 发送2 个请求，而d r r m 只发送n 个请求；其二是i s l i p 最后需要输入端向输 出端发送确认信号，而d r r m 则不需要此步骤，这样既节省了操作步骤，又节省 8 了数据的传送。因此就使得d r r m 更加简单，可扩展性能好。 轮询先到先服务算法( f c f si nr o u n dr o b i nm a t c h i n g ) ，f i r m 算法也是较 新的一种算法，它是在i s l i p 算法的基础上改进提出来的。i s l i p 在最坏的情况 下服务一个请求需要v 2 + ( 一1 ) 2 个周期， f i r m 算法对它做了改进，它们的 共同之处是两者都采用分布式的迭代算法，每次迭代都分为三步，只是f i r m 在更 新应答指针时有所不同，如果输入请求没有被应答，那么轮转指针更新为指向未被 应答的请求，这样就保证了此请求在下次能被服务，类似于f c f s ( f i r s tc o m ef i r s t s e r v e ) ，这样它比i s l i p 更加公平，它所提供的服务，保证在最坏的情况下服务一 个请求只需2 个周期，而且与i s l i p 相比，f i r m 的单次迭代在高负载( 大于 0 9 5 ) 的情况下平均延迟性能提高了5 0 ，更让人注意的是f i r m 在一次迭代的短 时间内就能达到比i s l i p 四次迭代更优的性能( 负载大于o 9 5 ) 。f i r m 还可以做 为分布式调度算法的基础，在此基础上已经提出了p f i r m ( f i r mw i t hp h a s e s ) 和r f i r m ( f i r mw i t ht i m er e s e r v a t i o n ) 以及p r f i r m 算法i1 5 1 并行轮询虚拟输出排队算法( p a r a l l e l - p o l lv i r t u a lo u t p u tq u e u e ) ，p p v o q 算法是通过在输入端口间放置的n 个同步令牌而实现的，每个令牌与其对应 的输入v o q 队列和输出端口相连，用来在输入端口的一个v o q 和某个输出端口 建立匹配，在一次调度时，令牌遍历所有n 个输入端口，直到某个端口建立一个匹 配。在每次调度阶段，令牌从上一次的位置开始轮询，上一次被选择的v o q 队列 的下一非空v o q 队列将被选择。p p v o q 具有高吞吐率，延迟小，而且有固 定的调度延迟时间。队列的延迟比i s l i p 小，并且提出更重要的是它能支持变长包 交换而比内部基于信元的交换效率要高，复杂度反而可能低。 2 最大权重类算法( m a x i m u mw e i g h tm a t c h i n g ) 上面介绍的最大匹配类算法是在每个时隙都尝试在输入和输出之间达到最大 的匹配连接，它只考虑队列的一位性质( 如队列是否为空) ，而最大权重匹配类算法 则是在输入和输出之间找到一个能使“权重”达到最优的匹配连接，它考虑队列超 过一位的性质，如“权重”可以为队列容量或信元排队等待时间，即找到最大容量 的队列或者最长等待日寸l , - - j 的信元。 l q f ( t h el o n g e s tq u e u ef i r s t ) 和o c f ( t h eo l d e s tc e l lf i r s t ) 算法，是较早 的最大权重类算法，但在硬件上实现相当复杂而且运行时间较长，所以考虑用多次 迭代的方式在硬件上实现，调度步骤同i s i l p 算法一样也使用请求一响应一确认的 三个步骤，不同之处是l q f 在请求时指明等待队列的长度，( 即权重设为队列容 量) ，输出端选择权重值最大的响应，但l q f 有饿死现象o c f 把权重值设为头 信元的等待时间，在请求时指明等待时间，输出端选择等待时间最长的响应，o c f 排除了饿死现象。l q f 与o c f 复杂度为o ( n 3 l o g ) 9 i m r f ( t h ei t e r a t i v em o s tr e q u e s tf i r s ta l g o r i t h m ) 是在综合了i l q f 和i 0 c f 的基础上提出来的一种权重匹配类算法，使用请求应答一确认模式的迭代匹配方 法。算法主要有两步，第一步是特殊迭代，并不是每个输入v o q 队列都向输出端 发送请求，而是只有v o q 队列长度超出预定值的输入端才向输出端请求，输出端 匹配对列最长的，这一步同l q f 类似，最长队列有最高的优先级第二步是普通迭 代，即每个输入端口都向输出端发出请求，这一步与o c f 相同，即选择等待时间 最久的信元。对均匀输入，i m r f 的性能与其他最大匹配类算法( 如i s l i p ) 基本相 同，能达到1 0 0 的吞吐率。在某些非均匀输入时性能也很好，也能达到1 0 0 的 吞吐率，但在其他一些非均匀输入情况则性能不如最大匹配类算法另外i s l i p 还 有几种变形算法也属于最大权重类算法，如i t e r a t i v el a s tr e c e n t l yu s e d ( i l r u ) ， 基本步骤与i s l i p 相同，不同之处是迭代中选择最近使用最少的为最高优先级，使 用最多的为最低优先级，按此轮转顺序进行下一轮的迭代。 p m w m 算法( p i p e l i n e dm a x i m u mw e i g h tm a t c h i n g ) ，d m w m 算法( d e l a y m a x i m u mw e i g h tm a t c h i n g ) ，d m w m 的原理是，在时刻t 一0 时计算出的匹配 用在t = k 到t = ( k + k ) 时间段上，假定在较短时隙问的流量变化不是很大，那 么在时刻t = 0 计算出的匹配用于时隙k 则能提供一个较好的匹配d m w m 算法 同非延迟的l q f 和i s l i p 相比，在高负载时的性能很好( 端口数较少情况) ，但当 交换端口大于3 2 时，性能明显下降。p m w m 算法是在d m w m 算法基础上的改 进，它的原理是在t = n 时刻计算出的匹配用于t = n + k 时刻。它与d m w m 相 比，性能要优化很多，k 越大节省的延迟越多与i s l i p 算法相比，在均匀输入负 载时，p m w m 算法的平均延迟性能与k 有关，k 越大则延迟越大，性能越差，只 在k = l 时总体性能比i s l i p 稍好，其它都差；但对非均匀输入负载，当负载增加 时，i s l i p 延迟明显增加，而p m w m 则较稳定，平均延迟性能受k 的变化影响不 大，且在中高负载时性能要优于i s l i p 很多。所以总体来看，p m w m 在高负载时 性能占很大优势。p m w m 的硬件实现复杂度为o ( n 3 ) 。 输出排队类调度算法 输出排队是把同时发到一个输出端口的多个信元在输出端进行排队，所以同 输入排队相比，输出排队需要更大的内部带宽信元到达以后，在输入端不进行缓 冲，而是直接通过交换网络送到输出端口，在输出队列里缓冲这时可以采取不同 的队列管理策略，如虚拟时钟法( v i r t u a lc l o c k ) ，它模拟了时分复用系统，每个信 元都被分配了一个虚拟的时钟，每个信元就按照时钟顺序传递，服务器执行时分复 用输出排队算法的优点是它可以达到交换机的最大吞吐率，而且所有信元的延迟 是固定的，这样就可以通过使用不同的输出管理策略来控制信元的延迟，以提供不 同的服务质量保证。但输出队列也存在问题，就是内部需要n 倍的加速比，即交换 1 0 结构内部和输出队列速率必须是输入速率的n 倍，当输入端口速率很高且端口数 目很多时，n 倍的加速会很高，很难实现。 组合排队类调度算法 组合排队( c o m b i n e di n p u t o u t p u t q u e u e d ，c i o q ) 算法旨在综合输 入排队和输出排队的各自优点，设计既含有输入队列又含有输出队列的交换机，使 交换机运行在一定的加速比l ( 大于1 小于n ) 下，这样能够达到比纯输入排队更高 的吞吐率。在加速比为l 的情况下，最多可以有l 个竞争的队列头信元被交换并 缓冲到输出队列。 关于输出队列的溢出有两种机制： q u e u el o s s 和b a c k p r e s s u r e ，前一种会由 于溢出而丢弃信元，后一种当输出队列满时则拒绝接受输入信元。在相同负载情况 下，b a c k p r e s s u r e 机制要优于q u e u el o s s 机制。输入输出队列的非阻塞包交换中 加速比和最大吞吐率的关系，用很小的加速比就能使吞吐率有很大的提高：加速比 为1 时最大吞吐率仅为5 8 ，当加速比为2 时，最大吞吐率就提高到8 8 。也证 明了在加速比为4 的时候组合排队和输出排队在不同交换端口和任意数据流下的 功能是相同的。这些算法都是利用加速比来集中控制输出端的竞争问题。 总之，设计一个好的调度算法，在其高效、稳定、快速、公平性方面，以及如 何支持组播，支持服务质量，简化硬件实现复杂度等方面，调度算法仍有进一步完 善和发展的前景。 第四节路由器的性能评估 相对中低端传统路由器而言，高端路由器是可运营的电信级路由器设备，高可靠性、 高扩展性和高性能的“三高”特性是关键属性。由于能有效拓宽i n t e r n e t 骨干网的 原始带宽，消除网络节点的带宽瓶颈，解决i n t e r n e t 骨干网日益面临的流量压力， 新一代高端路由器正成为电信运营商核心网络建设的新宠，并将朝着以下几个方面 发展： 数据交换带宽越来越大。由于各端口的数据流量高达数千兆，因此系统内部就 需要更高的带宽来支持各端口之间的数据交换。 数据处理能力越来越强。系统内需要足够高的数据包处理能力，按照因特网上数 据包的平均长度1 0 0 0 b i t s 计算，每一千兆的带宽需求是1 m b p s 的包处理和转发能 力。 控制服务质量的能力越来越强。系统内控制有效的服务质量( q o s ) 手段更 强，以满足客户在不同场合对不同服务质量的要求。 扩展能力越来越强。支持多种现行协议标准和支持未来协议的能力更强。 路由器的高性能主要体现在用户数据的处理容量大和处理速度快，以及协议的 处理能力强三个方面随着网络的巨大发展，自然要求路由器性能不断提高。目前， 人们正致力于开发高速、高性能、高吞吐量、低成本的新一代路由器，以满足网络 的不断发展。 调度算法的性能主要由吞吐量、时延特性决定。吞吐量：指路由器包转发能力。 吞吐量是单位时间通过网络给定点的平均比特数，以吞吐量除以信道传输速率得到 归一化吞吐量( 取值在“0 ”和“1 ”之间) 。归一化吞吐量一般被用来判断交换机 和路由器处理数据包能力的性能。时延特性分为平均时延和时延抖动。高性能调度 算法应该为特定业务提供端到端的时延保障。另外平均匹配度被定义为得到调度端 口数与输入端口请求数比值的平均一般来讲平均匹配度越高调度算法的效率越高 1 丢包率：指路由器在稳定的持续负荷下由于资源缺少在应该转发的数据包中不 能转发的数据包所占的比例 转发时延：指需转发的数据包最后一比特进入路由器接口到该数据包第一比特 出现在输出接口链路上的时间间隔 要提高路由器性能，就要针对传输过程中出现的各种问题及时提出解决办法， 例如，从i q 到o q ，再到c l o q 的结构变化，各项性能指标均有不同程度的提高随 着结构的改进，算法的提高，硬件技术的发展等都能对路由器性能的提高产生影响。 1 2 第三章系统仿真 第一节仿真的意义 对高端路由器来说， c r o s s b a r 是最简单和最普遍的结构，多数商用路由器采 用c r o s s b a r 建立它们的路由器结构。 在高端路由器优化设计中，一个重要的特点是所设计的结构都采用输入端排队 ( i q ，i n p u tq u e u e i n g ) 方案或组合输入输出端排队( c i o q ，c o m b i n e di n p u to u t p u t q u e u e i n g ) 方案，而不是纯输出端排队( o q ，o u t p u tq u e u e i n g ) 方案 当采用o q 方案时，内部带宽必须被增加这是由于在相同时间内允许多个信 源( c e l l ) 被发送到同一个输出端缓冲库( o u t p u tb u f f e r ) 中输出端排队的主要好处 是所有的信源都能以固定时延发送到输出端缓冲库中，而交换机能控制这个时延 这也是为什么在调度信源时为了得到绝对的或者统计上的性能保证，而通常假设是 采用输出端排队方案 2 1 ， 2 2 ， 2 3 ， 2 4 】， 2 5 ， 2 6 ， 2 7 o q 方案的主要弊端是对于一 个有n 个端口的交换机，内部连接和输出端排队必须以n 倍线速进行在实际应 用中，当端口数量很多或线速很大时，这使得o q 方案是不切实际的例如，对一 个有3 2 个端口的交换机，每一个端口的线速都是4 g b p s ，因此每一输出端缓冲库的 带宽是1 2 8 g b p s 即使内存有一个信源的带宽，那么此内存一次接收时间也是3 n s ， 而这个接收时间对最昂贵的s r a m 技术也是几乎不可能达到的然而，对一个采 用输入端排队的交换机，这个接收时间仅仅需要l o o n s ，因此用低廉的d r a m 技术 也是容易达到的 随着网络吞吐量的攀升，路由器的端口增加。由于不需要加速，采用输入端排队 ( i q ) 的中央处理器广泛的应用于高速网上。众所周知，输入端排队的路由器有两 个问题：由于队首阻塞而造成的低通过率和难以控制时延这是因为如果每一个输 入端缓冲库( i n p u tb u f f e r ) 中数据都采用f i f o ( f i r s ti nf i r s to u t ) 排队规则，那么 仅仅只有队首才可能被发送因此如果队列中第一个数据被堵塞，那么队首后面的 数据都不可能被发送出去，即遭遇队首堵塞( h o lb l o c k i n g ，h e a do fl i n eb l o c k i n g ) 众所周知这种输入端排队的最大通过量恰恰只有( 2 一 2 ) = 5 8 6 1 8 】对一些周期性 的输入流，队首堵塞可能导致更遭的性能 1 9 ，因此标准方法已经放弃了i q 方案 队首阻塞问题可通过虚拟目的地排队( v o q ) 解决，时延问题可通过内部线速 2 倍加速解决 在高速网特别是在主干网( b a c k b o n e ) 上，为了克服前两种设计方案中的弊端， 现在采用了新的设计方案即c i o q 方案( 如图3 ) 此方案在路由器中设计了两级缓 冲库，每一级都有n 个缓冲库从外面端口以速率r 输进来的数据都输入到第一 1 3 级缓冲库即输入端缓冲库中，然后中央调度对各输入端缓冲库中的数据进行调度， 把输入端缓冲库中的数据传送到第二级缓冲库即输出端缓冲库中，并按优先级高低 排成各级队列为了使它的性能达到o q 的性能，在第一级与第二级之间采取了加 速的方案，只要使内部线速加速到外部线速的2 倍即可达到o q 的性能 2 8 】而这 2 倍线速对于现有的内存来说是可以达到的 一寻| i ? 叠 一 一 二卜 图3c i o q 结构路由器 = 三三三二， 一三l 三三三， 主要至 - i 二三二 三主主) 三要要三) 三三二三二 要三三三) - i 三三i 主主至) q m lq m 2 三一 i q m 3 图4 三阶段路由器 当前的i n t e r n e t 仅支持尽力发送的业务，但随着互联网应用业务种类的不断发 展，提供服务质量( q o s ) 控制是新一代互联网所追求的主要目标之一服务质量 ( q o s r ) 作为提供服务质量控制的一种重要手段，收到研究者的广泛关注 2 9 】 1 4 i n t e r n e t 中，大大小小的网络之间的相互连接是通过路由器来实现的，路由器 支持优先级成为必然要求 本文在c i o q 方案的基础上，提出了一种新颖的3 q m 结构( 如图4 ) ，并给出 了相应的组合算法通过建模进行的行为分析，发现它能很好的支持优先级服务， 特别是在输入强度较大，非均流，突发流等恶劣条件下，性能良好 第二节仿真模型设计 由于交换网络处理的信元长度固定，因此，仿真模型可以采用简单的时间驱动 的方法。模型建立的几点假设： ( 1 ) 交换网络交换一个信元的时间称为一个时隙( c e l lt i m e ) ； ( 2 ) 各输入端的信元的到达过程相互独立； ( 3 ) 输入输出队列缓冲库( b u f f e r ) 容量足够大； ( 4 ) 模型建立和仿真研究都基于单播数据流。 这个nxn 交换网络的模型是由信元产生器、输入输出队列、交换结构和 控制器组成，根据假设( 1 ) ，在仿真模型中，信元的产生、缓存、交换和输出都将 在一个时隙内同时进行。交换网络模型框图如图4 所示 信号源的产生 信元产生器负责为交换网络生成信元，是模型的数据源，在每个时隙到来时最 先运行。根据假设( 2 ) ，每个端口的信元产生器相互独立的工作，依据负载参数p ( 0 p 1 ) ，主要产生服如下到达过程的信元： 1 ) 独立同分布贝努利到达过程：每个时隙内产生信元的数目服从p 的( 0 ，1 ) 二 项分布。产生的信元如果均匀地到达各个输入端，称为均匀独立同分布的贝努利过 程，这是一种比较理想的业务流，可以衡量交换网络理想工作时的性能，但这种过 程在实际中很难实现。 2 ) 采用非均匀流输入，这样信元不均匀地到达各个输入端。不均匀程度的控制 函数在多次试验后，选定为e x p ( 一( a - ( n + 1 ) 2 ) “2 n ) ，其中a 为i s l i p 算法中的行指 针变量，这是一个正态型非均匀流如下图，是一个按照上述输入模型的1 6 端口 的路由器的输入流的仿真结果。 虽然信元流的输入不均匀，但它属于允许流范围，允许流是指符合网络流基本 特性的流，符合的条件如下：若用n i 表示第i 个输入端进入向第j 个输出端发送 信元的概率，则n j 满足 1 ) ：1r i j 1 ，i = 1 ，2 ，礼表示第i 个输入端e l 接收到的向礼个输出端口 传送信元的概率之和小于1 。 2 ) ：1r i j 1 ，i = 1 ，2 ，n 表示若共n 个输入端e l ，则每个输入端口接收 1 5 到向第j 个输出端发送信元的概率和小于1 显然可见，所有的均匀流都是允许流，仿真的做法中经常采用均匀流作为输入 流，最常见的均匀流就是用1 n 作为信号源的输入函数，那么自然有 墨lr i j = 釜1 等= p i ，p i 为第i 端口输入强度，同样第2 ) 条件也满足。 而本文，在仿真程序中，信元的产生由函数e x p ( 一( a - ( n + 1 ) 2 ) “2 n ) 控制， 再进行归一化，那么假设产生向第i 个输入端进入的概率为q i ，则e 仁n ，q i = 1 ，这 样产生的输入流显然满足允许流的条件，而且信元是随机的以不同概率进入不同的 端口，属于非均匀流，虽然它和真正的网络流还有不同，但其接近程度远远大于均 匀流。 在模型中，信元的产生只是生成一个复杂的数据结构，并没有类似现实的信元 的具体内容，释放这个数据结构的过程模拟了信元的输出过程 第三节三阶段路由器的排队模型 本文所仿