（应用数学专业论文）高速路由器的排队网络分析.pdf

l 荔建路由器的排队刚络分析 摘要 d t r ( d e t e r m i n e dt u n n e la n dr o u n d - r o b b i n ) 也称固定通道算法，是路由器在组台输入， 输出排队( c i o q ) 结构下可以使用的一种新调度算法。本文所做的主要工作是对在c i o q 结 构下，采用d t r 调度算法所形成的系统进行行为分析，内容安排如下： 第一章回顾了高速路由器的发展情况，对路由器的基本模式、结构设计、调度算法等进 行了较为全面的阐述。 第二章是本文的核心部分。通过对d t r 算法的研究，把该系统的行为近似用一个四维 的马尔可夫链来描述得到了该马氏链正常返的充要条件。用矩阵几何方法进行求解，再利 用求解结果分析出各项性能指标，如时延、队长、溢出率等。本章具体内容包括：1 问题背 景；2 模型建立；3 模型求解；4 模型数值结果。所有程序附录在后，以供参考。 分析模型的数值结果表明，系统的上述各项性能指标均有很好的表现，且与仿真结果吻 合得比较好，说明这种近似的分析结果相对准确可靠。由于该数学模型对各系统参数具有较 强的适应性和可移植性，因此可以用于系统参数的优化设计，从而降低了设计中对仿真结果 的依赖性，这在很大程度上提高了设计效率，缩短了设计的周j j j 。 塑望些虫堂堕型坠型塑坌塑 a b s t r a c c i n t h i sp a p e r , w eh a v ea n a l y z e dt h ep e r f o r m a n c eo ft h es c h e d u l i n ga l g o r i t h m ( d e d i c a t e dt u n n e la n dr o u n d - r o b b i n ) f o rc i o q ( c o m b i n e di n p u t - o u t p u tq u e u i n 曲 s y s t e ms i m u l a t i o nh a sp r o v e di t sg o o dp e r f o r m a n c e ，w ef o c u so f fp e r f o r m a n c ea n a l y s i s o fd 1 r s w i t h e s b yd e e p l yc o m p r e h e n s i o nt od t r ，i n p u tq u e u e sc a l lb es i m i l a r l ym o d e l e db ym a r k o vp r o c e s s c o n c e p tb a s e do nt h ea s s u m p t i o nt h a ti ti sp o s i t i v er e c u r r e n t i t ss t a t et r a n s i t i o np r o b a b i l i t ym a t r i x i n d i c a t e si ti sq u a s ib i r t ha n dd e a t hp r o c e s s e s t h es t a t i o n a r yp r o b a b i l i t yv e c t o rc a nb eo b t a i n e db y m a r t r i x - g e o m e t r i cs o l u t i o n s t h e nw eo b t a i nt h ed i s t r i b u t i o no fi n p u tq u e u el e n g t h ，p a c k e tl o s s p r o b a b i l i t ya n dm e a nw a i t i n gt i m e sa n ds oo n t h i sp a p e ri so r g a n i z e da sf o l l o w s ，i nc h a p t e r l ，w es u m m a r i z et h ed e v e l o p m e n to fr o u t e r i n c l u d i n gb a s a lp a t t e r n ，s y s t e m i cd e s i g n ，p e r f o r m a n c em e a s u r e da n ds c h e d u l i n ga l g o r i t h m s a n d t h e o r e t i c a la n a l y s i sa c h i e v e m e n tr e c e n t l y i nc h a p t e r 2 ，w ep r o p o s eag e n e r a ls w i t c h i n gm o d e lc o n s t r u c t i o n ，s y s t e md e s c r i p t i o n t h e o r e t i c a lb a s i sa n dm o d e lc o n c l u s i o n s t h e nw ec o m p a r e dt h ep a r a m e t e rt os y s t e ms i m u l a t i o n i ns e c t i o n1 ，t h ep r o b l e mb a c k g r o u n d ；i ns e c t i o n2a n d3m o d e l c o n s t r u c t i o n ，r e a l i z a t i o na n d s o l u t i o n s ；t h ec o n c l u s i o n sa r em a d ei ns e c t i o n4 f i n a l l y , t o t a lp r o g r a mh a sb e e no f f e r e df o ry o u t or e f e r e n c ei na p p e n d i x k e y w o r d ：s c h e d u l i n ga l g o r i t h m ；m a r k o vm o d e l ；m e a nl e n g t h ；d e l a y ；l o s sr a t i o 高速路由器的排队删络分析 引言 在当前我国网络基础建设和信息建设方兴未艾之际。探讨路由器在互连网络中的地位及 其发展方向，对于国内的网络技术研究、网络建设具有重要的意义。随着计算机网络互联规 模不断扩大，以及各种火数据量传输应用的出现，传统的共享内存式或总线结构的路由交换 设备己远远满足不了技术发展的需要于是交叉开关交换内核的研究应运而生。 路由器的主要_ 丁作就是为经过路由器的每个数据帧寻找一条传输路径，并将该数据有 效地传送到目的站点。由此可见，选择最佳路径的策略即路由调度算法是路由器的关键所在。 随着网络技术的发展必须提出效率更高功能更完善的交换调度算法。目前些路由交换设 备的主要厂商以及大学研究机构都正在进行这方面的研究。 纵观交换技术的研究背景和白该研究开展以来所提出的主要调度算法，可以发现，目前 尚无一个很好的算法，能在保证服务质量的前提下提供高转发速率，而且在解决算法的实际 运行效率方面也还存在问题。调度算法的进一步研究目标包括如何在提供高的转发速率的前 提下支持服务质量，如何支持组播通信，如何在突发网络流量的情况下保证调度的公平性， 对支持服务质量的算法进行优化，降低其复杂度以便于实际使用等等。 本文所分析的d t r 算法，其迭代过程和1 s l i p 算法类似。d t r 算法，也称为【翻定通道 算法，利用三迭代米进行匹配，而匹配的对象从i s l i p 算法的每一非空队列缩小为向同一目 的地有4 个以上信元传输的队列，也就是说只有队长超过4 才能进行二部图匹配，剩下的队 列进行b r r ( r o u n d r o b i n ) 轮询。在主干网的路由器，数据流的输入强度很大，并且网络 流的不均匀特性和突发特性都导致了某输入端口一旦接收到数据包，经常就需要传很久，所 以有传输需要的队长一般长时问都能达到4 个信元，这时d t r 算法就能表现出它的巨大优 势，匹配对并没有减少，从而提高了路由器的转发效率。 一般来说，比较算法的优劣有儿个常j | 而有效的指标：时延( d c l 3 y ) ，抖动a i t c e r ) ，丢包 率( r o s sr a t i o ) 。时延是指数据从进入系统到离开系统整个过稗需要的时间，很显然时延越短， 效率越高，特别是对语音服务；抖动相对流媒体来说更为重要，它影响数据的稳定性，如果 各个数据包时延都较人，但是假设他们相著甚微，虽然传输速度延缓，但却不会影响整个数 据的稳定传送：筇三个指标是指：当排队和调度h i 优良，数据阻塞内存有限，旨定会有数 掘溢出现象，这样数据丢火率也必定要成为我们衡量系统的际准。 d 1 l 并法，通过系统逻辑仿真发现它的时延、乔吐 溢出率等性能较之其他算法有 4 高速路山器的排队刚鲳分析 明显的优越性，并h 已经做成芯片，进行了物理仿真，进一一步要投入市场。物理仿真的复杂 年代价不言而喻，即使只做逻辑仿真，当仿真结果表明该设计方案有问题，技术人员仍需要 根据仿真结果进行调牲，甚至重新i 歧计，然后再做新一轮的仿真，如此反复多次，才能得到 较好的设计方案。但是对这种复杂的系统进行模拟既耗费时问义很不经济，效率较低。如果 能对这种系统的性能评估给出一种相对准确且效率高的分析模型，用逻辑仿真验证它的准确 可靠性，然后只需要根据参数设置对该模型进行调整修正，将会大大提高设计效率。这正是 本文要做的工作。 针对d t r 算法，我们考虑用降维的办法，把数据传输过程近似等效为一个马尔可夫链 模型，其中的状态空间是无数个四维水平集各个水平集之间的转移概率阵跟拟生灭过程十 分类似。我们运用n e u t s 的矩阵几何解的方法，得到平稳概率向量，然后运用已有的知识结论 分析或者估算出路由器的各个性能指标，如时延，抖动，队长，溢出率，空队率等。 本文先概述了高速路由器的发展趋势及瓶颈所在，简单介绍了路由器的模型，和目前高 速交换技术所采用的主要体系结构，并收集了在交换内核研究领域取得的最新成果，包括各 种调度算法。然后针对新提出的d t r 算法，建立台适的数学模型，运用矩阵几何解等理论， 用m a t l a b 程序设计语言编程实现，最终分析出相应的各项性能指标。 该分析模型的数值结果从理论上根本支持和呼应了系统仿真的结论，从而为该算法提 供强有力的理论保障。这种具体的行为分析，大大降低了仿真的成本，缩短了修正周期，当 发现结果不很理想，只需要在程序里修改某些参数设置，就能迅速纠正偏差，最终得到理想 的设汁方案。相对于系统的逻辑仿真，更为准确可靠，适应性和可移植性更强。 硒速路由_ ；| 的排队网络分析 第一章路由器的发展与算法综述 第一节路由器的发展概况 当今社会，任何一个有一定规模的计算机网络( 如企业网、校园网、智能大厦等) ，无 论采用快速以太网技术、f d d i 技术，还是a t m 技术，都离不开路由器，否则就无法正常 运作和管理。路由器是互联网络的枢纽、”交通警察”。目前路由器已经广泛应用于各行各业， 各种不同档次的产品已经成为实现各种骨干网内部连接、骨干网间互联和骨干网与互联网互 联互通业务的主力军。 路由器作为i n t e m e t 的骨架。它的处理速度是网络通信的主要瓶颈之一，它的可靠性 则直接影响着网络互连的质量。因此，在网络各个研究领域中，路由器技术始终处于核心地 位，其发展历程和方向，成为整个i n t e r n e t 研究的一个缩影。 由于多媒体等应用在网络中的发展。以及a t m 、快速以太网等新技术的不断采用，网 络的带宽与速率飞速提高，传统的路由器已不能满足人们对路由器的性能要求。因为传统路 由器的分组转发的设计与实现均基于软件，在转发过程中对分组的处理要经过许多环节，转 发过程复杂，使得分组转发的速率较慢。另外，由于路由器是网络互连的关键设备，是网络 与其它网络进行通信的一个“关口”，对其安全性有很高的要求，因此路由器中各种附加的安 全措施增加了c p u 的负担，这样就使得路由器成为整个互联网上的“瓶颈”。 随着i n t e r n e t 的飞速发展和宽带技术的不断出现，对i n t e m e t 互连的核心设备路 由器的性能提出了越来越高的要求，传统的基于总线和中央处理器结构的路由器由于其体系 结构上的局限，已经无法满足组建高速主干网络的需求。近年来，国际上对宽带i p 路由器 技术的研究也日益活跃，提出了用交换结构( s w i t c hf a b r i c ) 提高备接v i 单元之间的数据通 信速度的基本思想。从研究趋势来看，交换技术已经成为高速路由器的核心技术。 现在，路由器的设计方案总体趋势表现为：第一，数据交换带宽越来越大；第二数 据处理能力越来越强：第三，控制服务质量的能力越来越强；第四，扩展能力越来越强。而 控制信息的传输已经成为调度算法性能提高的主要瓶颤。 高速踣山器的排队h 络分析 第二节路由器的结构简介 目前，大多数路由器采用以c r o s s b a r 交换开关为核心的分布式结构。交换开关机制在 现有的c m o s 工艺下已经能够实现l t e r a b i t s 的交换速率。交换内核连接个输入端口和 个输出端口，如下图所示： 图1 交换式路由结构 c r o s s b a r 交换开关中广泛采用了缓冲队列技术。根据缓冲区在交换结构所处位置不同， 可以分为输山排队结构o q ( o u t p u t q u e u i n g ) 、输入排队结构i o ( i n p u t q u e u i n g ) 和组合 输x 输出o i c q ( c o m b i n e d i n p u t o u t p u t q u e u i n 曲结构。 最早期多采取o q 结构，信元到达后立即通过高速交换网络送到正确的输出端口，并 被存储在输出队列里，这时可以采用不同的队列管理策略，例如，虚拟时钟算法，它理论上 可以实现1 0 0 的吞吐量( t h r o u g h p u t ) 有很好的q o s 保证，但由于输出队列和共享内存对内存 读写速度( t o o ) 要求很高，需要对缓冲区进行n 倍加速当时硬件很难实现。随着网络流量 的增加，出现i o 结构，它虽然降低了带宽要求，但出现了队首堵塞，虚拟输出端排队结构 v o q ( v i r t u a lo u t p u tq u e u i n g ) 克服r 队首堵塞并保持了i q 的容量优劣，但缺乏自适应性的调 度n i 产生输入端数据溢出。总之，o q 有高速要求而不切实际，单纯的i q 订没有q o s 保证， 丁是，随着物理链路传输速率的不断提高和服务要求的多样化，基丁v o q 的：t t b 队方案，出 现，在输, k , 2 7 , 1 l l 输山端同时缓存排队的机制即c i o q 结构。理论已经证明，c l o q 排队方式 z ，土d n 述b l 2 , = f2 ( s p e e d “p2 ) 时，能够很好地模拟o q 的性能( 见参考文献【7 1 ) ，闭此可以在 输入端和输端采取适当的分纰删度算法米刘4 i 同的应用提供服务质埘保汪。 7 高速路由 的排队网络分析 第三节路由器的算法综述 交换内核的体系结构包括数据通道和调度器。设计一个高带宽的数据通道比较容易，困 难的是如何为调度器设计一个效率高的调度算法。算法设计的基本要求是： ( t ) 效率高，高效率的调度算法能够同时匹配尽可能多的输入队列。 ( 2 ) 稳定性，无论输入队列的情况如何，调度算法都应该迅速找到可行的调度。 ( 3 ) 公平性，不会出现某些队列永远得不到响应的情况。 ( 4 ) 快速易于势行，调度算法必须快速执行。 ( 5 ) 易于实现，调度算法应该易于用硬件实现。一般来说使用硬件很难快速计算出 最大匹配，因此在设计调度算法时总是采用计算复杂性较低的启发式算法以找出次优结果。 调度算法其实就是研究二部图的最佳匹配，即如何在n 个输入端口和n 个输出端口之间 寻找一种最佳路径匹配方案，实现步骤为：( 1 ) 申请( r e q u e s t ) ：输入端向有信元要去的输出端 发送传送申请。( 2 ) 响应( g r a n t ) ：输出端必须根据优先级别选择个申请予以响应。( 3 ) 确认 f a c c e p t ) ：输入端口必须在多个允许中按一定规则选择接收一个。 按是否考虑加权l i p o o s 保证，可以分为最大数量匹配算法( 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 l i t e r a t i v e m a t c h i n 9 1 、d r r m ( t h eo u af r o u n d r o binm a t c hir i g ) 、r r m ( r o u n dr o b i n m a t c h i n g ) 、i s l l p ( 1 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 z em a t c h i n g ) ，但由于这些近似算法用于模拟最 人数量匹配算法，冈此这些算法也可能出现不稳定性和不公平性。f 面将简单介绍一些典型 算法。 最大双向匹配( m a x i m u mb i p a r t i t em a t c h i n g ) ，即在输入利输出之问达到最人匹配， 高速路由器的排队列络分析 复杂度为o ( n ”) ，虽然能保证找到个最大匹配，但实现过丁i 复杂，运算时间太k 。而实 际中最大匹配并不是必要的，容易引起不稳定和不公平，而且能导致饿死。 并行迭代匹配算法p i m ( p a r a i1 e il 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 in g ) 以及l s l t p ( i t e r a t i r er o u n d r o b i nm a t c h i n gw i t hs | i p ) 算法都是迭代 类的匹配算法。所有的输入输出都初始化为未匹配，所不同的是响应和确认的规则，并行迭 代用的是随机选择，基本轮转算法是按固定轮转顺序表进行而i s l i p 则是在轮转顺序的指 针更新上更为优化。在性能上，对均匀输入负载，单次迭代i s l l p 就能达到1 0 0 的吞吐率， 也能保证公平；对非均匀输入负载，1 s l i p 一次迭代吞吐率较小，p i m 虽有欠公平，但多次 迭代的吞吐率比i s l i p 高。最大匹配类算法的复杂度为o ( n ”) ，p i m 的复杂度为 o ( n x l , o g n l 。实际中应用较多的是易于用硬件实现的i s l i p 算法。 双向轮转匹配d r r m ( t h ed u a ir o u n d - - r o b i nm a t c h i n 曲，双向轮转匹配是可扩展 性好，低复杂度的一种较新的算法。该算法中在每个输入端也放j | i ! n 个v o o 队列，输入调 度器按照固定轮转顺序选择非空v o o 队列向输出端发送请求，输出端最多接收n 个请求， 从轮转顺序中选择一个应答。 轮询先到先服务算法( f c f sl 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 在最坏的情况下服务一个请求需要 2 + ( 一1 ) 2 个周期，f i r m 算法对它做了改进，只是f i r m 在更新应答指针时有所不同， 它比1 s l i p 更加公平，它所提供的服务，保证在最坏的情况下服务一个请求只需n z 个周期， 而且与i s l i p 相比，f i r m 的单次迭代在高负载f 大于0 9 5 ) 的情况下平均延迟性能提高了5 0 ，更让人注意的是h r m 在一次迭代的短时间内就能达到比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 o f ( t h el o n g e s tq u e u ef ir s t ) 和o c f ( t h e0 | d e s tc e l if irs t ) 算法，是较早的最火 权重类算法但在硬什上实现拥3 _ 复杂而且运行时间较& ，所以考虑用多次迭代的方式在垃 什上实现，调度步骤蚓i s i l p 算法一样也使川请求一响j 母一确认的三个步骤，不同之处越 高速路由器的排队嘲络分析 l q f 在请求时指明等待队列的k 皮，( 即权重设为队列容量) ，输山端选择权重值最人的响应， 但l o f 有饿死现象。o c f 把权重值殴为头信元的等待时问，在请求时指明等待时间，输山 端选择等待时间最长的响应，o c f 排除了饿死现象。l q f 与o c f 复杂度为0 ( n 3 l d g n ) 。 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 o c f 的基础上提 出来的一种权重匹配类算法，使用请求一应答一确认模式的迭代匹配方法。对均匀输入， i m r f 的性能与其他最大匹配类算法( 如i s h p ) 基本相同，能达到1 0 0 的吞吐率。在某些非 均匀输入时性能也很好，也能达到1 0 0 的吞吐率，但在其他一些非均匀输入情况则性能不 如擐大匹配类算法。另外i s l i p 还有几种变形算法也属于晶大权重类算法，如i t e r a t i v el a s t r e c e n t l yu s e d ( i l r u ) ，基本步骤与i s l i p 相同，不同之处是迭代中选择最近使用最少的为最 高优先级，使用最多的为晟低优先级，按此轮转顺序进行一r 一轮的迭代。 p m w m 算法( p i p e i i n e dm a x i m u m w e i g h tm a t c h i n g ) ，d m w m 算法( d e i a ym a x i m u m w e i g h t m a t c h i r i g ) ，d m w m 算法同非延迟的l q f 平i s l i p 相比，在高负载时的性能很好( 端口数 较少情况) ，但当交换端口大于3 2 时，性能明显f 降。p m w m 算法是在d m w m 算法基础上 的改进，它与d m w m 相比，性能要优化很多。与i s l i p 算法相比，在均匀输入负载时，总 体性能一般都不如比i s l i p ；但对非均匀输入负载，当负载增加时，i s l i p 延迟明显增加， 而p m w m 则较稳定，且在中高负载时性能要优于s l i p 很多。所以总体来看，p m w m 在高 负载时性能占很大优势。p m w m 的硬件实现复杂度为0 ( 3 ) 。 纵观交换技术的研究背景和自该研究开展以来所提出的主要调度算法，可以发现，目前 尚无一个很好的算法，能在保证服务质量的前提下提供高转发速率，而且在解决算法的实际 运行效率方面也还存在问题。调度算法的进一步研究目标包括如何在提供高的转发速率的前 提下支持服务质量，如何支持组播通信，如何在突发网络流是的情况下保证调度的公平性， 对支持服务质量的算法进行优化，降低其复杂度以便于实际使用等等。 高速路由器的排队删络分析 第二章d t r 算法性能分析 篼一节问题背景 最近提出的组合输入输出排队( c i o q ) ，理论上已经证明了2 - 1 n 加速比是c i o q 能模 仿f i f o o q 功能的充要条件，并提出了一种目前最简单的组台输入输出算法，临界信元优 先算法( c r i t i c a lc e l l s f i r s t ，c c f ) 。但目前来说这方面的研究还停留在理论研究阶段，要在实 际中用硬件实现高速交换还需要做更多的工作。 本文分析的d t r 算法，输入排队算法采用v o o ，输出算法采用p f o ( p f i o r i t yf i f o q u e u e l ，其迭代过程和i s l i p 算法类似。它利用三迭代来进行匹配，而匹配的对象从i s l i p 算法的每一非空队列缩小为向同一目的地有4 个以上信元传输的队列，也就是说只有队长超 过4 才能进行二部图匹配，剩下的队列进行b r r ( r o u n d - r o b i n ) 轮询，从局部看似乎d t r 算法比i s u p 算法反而更减少了匹配，但是从整体上看，在一次匹配后，所有匹配队连传4 个信元，提高了传输效率。它综合了b r r 轮询和i s l i p 迭代，是多年实践中针对网络流的非 均匀性和突发特性提出来的，而且并不需要更高的硬件支持。它与i s l i p 算法不同的地方在 于，后者每次匹配后传送一个c e l l ，而d t r 每次匹配后可以连续传送四个c e l l ，每次匹配用四 个t i m e s l o t 去完成，足够它实现1 0 0 的吞吐量。尽管每次执行的是上一次的调度算法，由于 网络流的长相关、自相似、突发性等特点，相邻两个阶段的波动几乎很小，相比于其它算法， 仍然有很大的优势。但是我们必须通过建立合适的模型，把这一结果定量地分析出来。 第二节模型建立 在输入端i ( 1e ig n ) ，每个缓冲库都有个队列。记z 。0 ) 为第j 个队列上在时刻n 的队长，爿。0 ) = ( x 0 ) ，x 啦) ，x 。0 ) ) 及爿0 ) = ( 爿。0 ) ，x ：0 ) ，盖。 ) ) ，我 们希望通过对这个n n 维的随机过程x ( n ) 的行为进行分析，来得到我们所关心的数值结 果，这个高维随机过程求解f f = 目当复杂r 但是当我们把注意力集中到其中的一个队列盖。0 ) 上时情况就订所改变。记x 。( ，f ) 为x 。，此时x 。讧。，h o 还不是马氏链，需要补充 高速路由器的排队| 叫络分析 一些变量，先对输入流和服务规【| ! | j 进行假设： ( 输入流的贝努利( b e m o u l l i ) 假改：假设在每个时问片( t i m es l o t 或c e l l t i m c ) 的开始 时刻，以概率p 有一个信元进入输入端f ( 1 s is n ) ，以概率】一p 没有信元进入，每个进 入输入端瑚信元以概翱，进入该输入端的第一队列其中荟驴1 0 服务规则假设：d t r 算法在i s l i p 算法上做点小改进，用( o ，1 ) 状态矩阵取代以前的 虚拟排队只有当不少于4 个队列在等待时才置之为1 ，否则都为0 。这些用i s l i p 算法， 留作固定通道，其余在小范围内作轮询( r o u n dr o b i n ) ，机会均等，概率至少是l n 。火于 或者等于4 个被留做固定通道的概率为1 r 。 根据算法的特点，需要补充三个变量t 现在该四维向量表示为( x 。，k ，z ，睨) ，其中 x 。表示队长，可取任意自然数；k 为状态变量，表示它处于第几个状态，从0 取到3 ，因 为每个状态都要4 个时间片才能完成；z 表示上个阶段是否被留作固定通道，取0 或者1 ， ( 1 表示肯定，只有当队长大于或者等于4 才有可能，o 反之) ；睨表示这个阶段是否被 留作了固定通道，同样取0 或者1 。这样该模型f 各状态只跟当前状态有关，无记忆性，故 能近似等效于一个马尔可夫链。它的状态空间为：s ：每，i ，乏，n ， o 苫0 ) ，其中的各 个水平集为： h。 捉n ，0 ，0 ，o ) ， ，0 ，0 ，1 ) ，0 ，o ，1 o ) ，0 ，0 ，1 ，l ) ，0 ，l o ，0 ) ，0 ，1 ，0 ，1 ) ，( n ，1 ，1 ，o ) ，0 ，1 ，1 ，1 ) ， 0 ，2 ，0 ，0 ) ，0 ，2 ，0 ，1 ) ， ，2 ，1 ，0 ) ，0 21 】，) ，0 ，3 ，o ，o ) ，o ，3 ，o ，1 ) ，0 ，3 ，l o ) ，0 ，3 ，1 ，1 ) ) 根据d t r 算法的规则及对输入流的假设，可以写出这个四维马氏链( 石。，匕，z 。，比) 各 个状态之问的转移概率矩阵，它的分块形式为： 尸= 爿曰 cde cde c d4 0 c 爿14 a 2a 1a f j 爿爿， 高速路由器的排队刚络分析 其中每个子块爿，b ，c ，d ，e ，a 。，a 1 ，a 2 都是一个1 6 1 6 阶稀疏矩阵，而且都可以刚p q ，n ，r 这些量表示山来，令口= p q ，b = 1 一p q ，c = 1 n ，d = 1 1 n ，e = 口c + b d ，则有 4= b= 6 口 口 口 6 n 6 盘 6 立鎏堕虫竖堕型坠堕竺坌! ! c d = e e 已 6 1 4 垒垩堕虫堂些型坠型塑坌堑 e = a o = a d a d 0 0 o o 0 0 口d n 一1 r ) a d r 口d n 一1 r ) a d r 0 o 0 0 o o 0 0 0 0 0 o 一鱼望堕虫堂竺苎坠型塑坌塑 一 a 1 ； 4 = e 口 e ( 1 i 0 e r e ( 1 1 r ) e r 4 ( 1 1 r ) a r ( 1 1 r ) a r b c ( 1 - 1 r ) b c r b o 一1 r ) b r b c o l r ) b c r b o 一1 r ) b r e 口 口 口 壹垄些虫丛塑堡坠坚堡坌塑 一 第三节 模型求解 ( 1 ) 求马氏链( x 。，k ，z 。，) 正常返的条件 令a = a ( j + a l 4 - a 2 ，则 爿； 1 1 ，1 ， 1 1 r1 ， 1 1 ，l r 1 1 ，1 r 最然j 是一个不可约的随机矩阵，它相当于是一个有1 6 个状态的转移概率矩阵。设对应 _ 丁爿的平稳概率向量为玎= ( o 玎1 耳2 玎3j r4 玎5 石 万7 石8 汀9 汀l o 玎1 1 玎1 2 石，3 口。z ，；) ，利用j 州2 ”( 注：本文中的p 都是指元素全为1 的维数白适应的列 j 石e = 1 向量) ，可以解出 ( r 一1 ) 2 ” 节 r 一1 ，一11 ( ，一盯r 一1 ，一1 1 p 一1 ) 2r 一1 r 一11 ( i 一1 ) 2r 一1r 一1 1 l 4 r 2 4 r 2 驴矿4 r 2 如2 4 r 2 4 r 2 4 r 2 4 r ”矿4 r 2 廿2 4 r ”4 r 2 i 再令p = ( 一，+ 2 a ：) e ，计算出口： 2 一j ) g 1 一p g + 丙1 2 一，g l 一，g + 万1 2 - p q2 - p q 2 一p q2 一p q 2 一p q 2 一p q1 7 ，一一 g g p p 一 一 1 1 ，一，一 + + 叮 g p p 一 一 i 【 ，一 附 一 一 一，、1 高速路由_ ； 的排队刚络分析 丁| 是我们有虫下的结论： 结论l 马氏链正常返的充要条件是：口q 1 是马尔可夫链正常返的充分条件即 ( 2 ) 求马氏链的平稳概率向量工： 将x 按照概率矩阵p 做相应的分块，则有x = 。，工。，工：，x 3 ，) ，其中 x i = b ，x i 工，x i 拍) ，( fz o ) ，并满足 譬鲁 z o ；x o a + c x 1 暑x o b + d + x 2 c x 2 穹e + z 2 d + z 3 c x 3 ；x 2 e + x 3 d + 工4 c ( ) 工4 童工3 爿o + x 4 a 1 + x 5 a 2 弘”1 i x l = x q h 工x ，2 ：= 。x ：l g f 其中h = b ( i - d - g c ) 一，g = ( 1 - d - f c ) 一， i x i + 3 = x 3 r2 ( i 1 ) ( i - d - r c ) - 1 黼组簖燃肼广h 一 壶矍些虫堂竺堡坠型塑坌塑 的稳态队长，则当j l ，q = 1 0 e 一6 ) ( i = e 丌( k = e r r ) ( k = 1 o e 一6 ) ( i = k + 1 ) h ( i + 1 ) = s u m ( x i ) ) ： i = i + l ： e n d m = li n s p a c e ( 0 ，0 ，i 一1 ) ： f o rj = l ：i 一1 m ( j ) = h ( j ) ： e n d 2 7 高速路由器的排队叫络分析 致谢 本文在我的导师徐德举老师的悉心指导得以完成。从师三年来，徐老师言传身教，对我 耐心指导，悉心帮助，使我不仅得以顺利完成硕士研究生的学业及毕业论文的写作，还从中 获得了许多做学问和做人的道理。徐老师知识渊博，谦虚严谨，思维敏捷，对学生平易近人， 使我终身难忘，在此对徐老师深表感谢! 此外，还要感谢焦宝聪、陈兰萍、谌稳固、吴宪远、戴爱见等老师给予我的教导! 感谢首都师范大学研究生部以及数学系各位领导和老师的关一f l , 和帮助! 二零零五年四月 ! 童垄些虫堡竺塑坠型塑坌型! 【1 】 【2 】 【3 】 【4 】 【5 】 【6 】 参考文献： m a l r isg e o m e t r i cs o l u t i o n si ns t o c h a s t i cm o d e ls ，m a r c e lf n e u t s ，1 9 8 1 随机过程，中国统计出版社，s m 劳斯，1 9 9 7 年7 月 随机服务系统，科学出版社，徐光辉，1 9 8 0 年2 月 精通m a t l a b65 ，中国水利水电山版社，张瑞丰，2 0 0 4 年2 月 m a t l a b5 x 与科学计算，清华大学出版社，王沭然，2 0 0 0 年5 月 n i c km c k e o w n “i s l i p ：as c h e d u l i n ga l g o r i t h mf o ri n p u t q u e u e ds w i t c h e s ”，i e e e t r a n s a c t i o n so nn e t w o r k i n g ，v o 7n o 2 ，a p r i i1 9 9 9 【7 】p g r is h n a ，n p a t e l ，a c h a r n e y ，a n dr s i m c o e “o n w o r k c o n s e r v i n g c r o s s b a rs w it c h e s ”p r e s e n t e d i w q o s 9 8 ，n a p a ，c a l i f o r n i a m a y1 9 9 8 t h es p e e d u p a t6 t h r e q i r e df o r i e e e i f i p 【8 】a d i s a km e k k i t t i k u l ，n i c km c k e o w n ，“ap r a c t i c a ls c h e d u l i n ga l g o r i t h mt oa c h i