（计算机应用技术专业论文）基于微分流量模型的路由器队列控制研究.pdf

硕士学位论文 摘要 随着 n t e r n c t 的飞速发展，由于竞争网络资源而导致的网络拥塞问题越来越 严重。在路由器等交换设备上应用有效的队列管理算法对于提高网络性能来说显 得愈发重要。近年来，各类多媒体实时业务流的应用不断拓展，对网络传输的延 时和抖动提出了更高的要求。队列的长度及其变化是影响网络的延时和抖动的重 要因素，使用有效的方法对队列的长度进行控制并降低队列长度的变化幅度和范 围，是控制延时和抖动问题的关键。 由于端到端的拥塞控制作用有限。i e t f 推荐在路由器上使用主动队列管理 ( a q m ) 技术与t c p 拥塞控制相配合来避免拥塞，并推荐r e d 作为候选算法。 r e d 算法目前已经成为使用最为广泛的主动队列管理算法。由于缺少系统性的 理论和分析，调整r e d 算法的参数十分困难。不合适的参数配置将导致r e d 算 法的性能比单纯的队尾丢弃的性能更差。 本文在分析t c p 流量控制微分方程模型的基础上，提出一种新的队列波动分 析方法。将r e d 队列管理看作一种扰动作用下的单位反馈控制系统，将期望队 长作为系统的输入，即时队长作为系统的输出，将队列的波动，即期望队长和即 时队长之差作为系统的误差，对系统的稳态误差进行分析。分析结果认为r e d 算法分组丢弃函数的斜率对队列的波动有较大影响。针对以窗口控制机制为核心 的流量模型无法对u d p 流量的变化进行描述的问题，本文在路由器队列长度变 化中加入u d p 流量的影响，建立了t c p 和u d p 捏合流量的随机微分方程模型， 实现了对原有t c p 微分流量模型的扩展。通过求解路由器在稳定状态下的分组 丢弃概率，改进了原有基于t c p 流的r e d 队长控制方法，使之能适用于t c p 和u d p 的混合流的队长控制。 本文使用n s 2 作为网络仿真实验平台，对研究结果进行验证和分析。实验结 果表明：稳定状态下，在路由器上进行r e d 队列控制时，适当调整分组丢弃函 数的斜率，将显著降低队列的抖动。另一方面，改进后的面向t c p 和u d p 混合 流的r e d 队列长度控制方法对于t c p 以及t c p 和u d p 的混合流均具有较好的 适应性，采用该方法可以使得路由器的实际队列长度保持在期望控制队列长度附 近波动。 关键宇：队列控制；流量模型：稳态误差；r e d ：延时；抖动：n s 2 基于微分流量模型的路由器队列控制研究 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h e i n t e r n e t ，n e t w o r kc o n g e s t i o nw h i c hi sc a u s e d b yc o m p e t i n gn e t w o r kr e s o u r c eb e c o m e sm o r ec r i t i c a l i no r d e rt oi m p r o v en e t w o r k p e r f o r m a n c e ，i ti sf a ri m p o r t a n tt h a ta p p l y i n ge f f e c t i v eq u e u em a n a g e m e n ta l g o r i t h m o nr e u t e r s a l lk i n d so fm u l t i m e d i ar e a l t i m ea p p l i c a t i o n sh a v eb e e nm a d ew i d e l y a v a i l a b l ed u r i n gr e c e n ty e a r sa n dr e q u i r es h o r t e rd e l a ya n dl o w e rj i t t e rt os a r i s f y t h e i rd e m a n d s b e c a u s et h el e n g t ha n df l u c t u a t i o no f q u e u ea f f e c tn e t w o r kd e l a ya n d j i t t e rd i r e c t l y , t h ek e yp o i n to fh o wt oc o n t r o ld e l a ya n dj i t t e r i st om a k eu s eo f e f f e c t i v em e t h o dt oc o n t r o lt h eq u e u e l e n g t ha n dd e g r a d et h eq u e u ef l u c t u a t i o nl e v e l f o rs o m el i m i t a t i o n so fe n d - t o - e n dc o n g e s t i o n c o n t r o l ，i e t fs u g g e s t su s i n g a c t i v eq u e u em a n a g e m e n t ( a q m ) o nr e u t e r sa n dr e c o m m e n d sr e da st h ec a n d i d a t e a l g o r i t h m r e dn o w h a sb e e nm o s tw i d e l yi m p l e m e n t e da so n eo f t h ea q m s b e i n g l a c ko f s y s t e m a t i c a lt h e o r ya n da n a l y s i s ，i ti st o od i f f i c u l tt oa d j u s tt h ep a r a m e t e r so f r e d i m p r o p e rp a r a m e t e r ss e t t i n gw i l ll e a dt ob a dn e t w o r kp e r f o r m a n c ew h i c hm a y b en ob e t t e rt h a nd r o p t a i l s b a s i n go na n a l y s i so ft c p f l o wc o n t r o ls t o c h a s t i cd i f f e r e n t i a le q u a t i o nm o d e l ， t h i sp a p e rp r e s e n t san e wm e t h o dt oa n a l y s i sq u e u ef l u c t u a t i o n i tr e g a r d sr e da sa u n i tf e e d b a c kc o n t r o l s y s t e m b yt a k i n ge x p e c t e dq u e u el e n g t h a s i n p u t a n d i n s t a n t a n e o u sq u e u el e n g t ha so u t p u t ，w ea n a l y s e st h es t e a d ys t a t ee r r o ro ft h i s s y s t e m t h ea n a l y s i sr e s u l t ss h o wt h a tt h es l o p eo ft h ep a c k e t sd i s c a r d i n gf u n c t i o n i n f l u e n c e dt h eq u e u ef l u c t u a t i o ns i g n i f i c a n t l y i na d d i t i o n ，b e c a u s eu d ph a s1 1 0f l o w c o n t r o lm e c h a n i s ml i k e c o n g e s t i o nc o n t r o l ，d i f f e r e n t i a le q u a t i o n w h i c ht a k e s w i n d o w - b a s e dc o n t r o la sm a i nc h a r a c t e rc o u l dn o td e s c r i p tu d p r u n n i n gp r o c e s s ， t h i sp a p e rm o d i f i e st h eo r i g i n a lt c pf l o wc o n t r o ls t o c h a s t i cd i f f e r e n t i a le q u a t i o n b y m e a n so f a d d i n gu d p a f f e c t i o n st ot h ec h a n g i n go fr o u t e r sq u e u el e n g t h ，w es e t u pan e w m o d e lt oa n a l y s i st h em i x t u r ef l o w so ft c pa n du d p a f t e r g e t t i n gt h e r o o t o f s t e a d ys t a t ep a c k e t sd i s c a r d i n gp o s s i b i l i t y , t h eo r i g i n a lr e dq u e u el e n g t hc o n t r o l m e t h o df o rt c pf l o wc o u l db ea p p l i e dt ot h em i x t u r ef l o w so ft c pa n du d e w eu s en s 2a st h es i m u l a t i o n p l a t f o r m t o v e r i f y t h er e s e a r c hr e s u l t t h e e x p e r i m e n t ss h o wt h a t ，u n d e rt h es t e a d ys t a t e ，a d j u s t i n gt h es l o po f t h ep a c k e t s d i s c a r d i n g f u n c t i o n p r o p e r l y w i l ld e c r e a s et h e q u e u e f l u c t u a t i o n s i g n i f i c a n t l y i m p r o v e dm e t h o d o fr e d q u e u el e n g t hc o n t r o li sf i tf o rn o to n l yt c p f l o w sb u ta l s o 硕士学位论文 t h em i x t u r ef l o w so ft c pa n du d p u s i n gt h i sm e t h o dc o u l dm a k ea c t u a lr o u t e r q u e u el e n g t hk e e p i n g o nf l u c t u a t i n ga r o u n dt h ev i c i n i t yo fe x p e c t e dq u e u el e n g t h k e yw o r d ：q u e u e c o n t r o l ：t r a f f i cm o d c hs t e a d ys t a t ee r r o r ；r e d ；d e l a y ：j i t t e r ： n s 2 h i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：面、佑日期：如铲年弓月冲日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名：西仁 导师签名乞钐眵及：v 、 日期：冽“年弓月砷日 日期：如印年3 月砷日 硕士学位论文 第1 章绪论 1 1 课题来源 本课题得到国家自然科学基金项目( 6 9 9 7 4 0 3 1 ) 资助。 1 2 研究意义 1 2 1 排队算法对网络性能的影响 随着i n t e r n e t 规模的不断扩大和宽带网络连接的普及，网络用户数量呈现指 数级的增长【1 ，2 1 。网络资源的有限性与互联网日益增长的用户需求之间的矛盾愈 发突出，从而导致越来越严重的网络拥塞问题。产生拥塞的原因主要在于应用 对于资源的需求超过网络资源所能提供的可用部分，即对资源的需求 可用资 源。一旦发生拥塞，网络的性能将受到极大的影响，表现为数据包时延增加、 丢弃概率增大、上层应用系统性能下降等。 网络中的资源主要有以下几种：链路容量，交换节点的缓存区和处理机等。 通过高速骨干网的架设来增加链路容量，在一定程度上缓解了低带宽所带来的瓶 颈问题。硬件厂商不断推出具有高速处理能力的路由器等网络设备，以保证c p u 在执行排队缓存和更新路由表等功能时，其处理速度能够匹配高速链路。增加缓 存空间在某种程度上可以缓解突发流量的分组由于缓存容量有限雨被强制丢弃 这一问题，然而如果路由器缓存容量过大时，拥塞只会变得更坏。而不是更好p j 。 因此，研究有效的排队规则和队列管理算法对交换节点缓存进行调度和管理对网 络的性能的影响就显得尤为重要。 近年来，互联网的主营业务在逐步发生着变化和转移。传统的w w w 网页浏 览、f t p 文件传输一类的非时延敏感的网络应用已经不能满足人们的需求，各 类视频点播v o d 、音频v o i p 和实时监控等实时多媒体网络应用飞速增长。新 兴业务流的服务质量q o s l 4 j 以及区分服务d i f f e r e n t i a t e ds e r v i c e s l 5 , 6 j 控制对于网 络传输的延时和抖动的控制提出了较高的要求。 假设交换节点的c p u 处理能力不受限( 即不存在处理延时) ，那么网络的延 时主要由传输延时和排队延时两个部分构成。传输延时依赖于通信双方的物理 连接距离和传输介质，一般来说比较固定。路由器上的捧队延时则与其缓存区 的队列长度有关。因此，如何使用有效的排队算法对队列的长度进行控制并降 低队列长度的变化幅度和范围，是控制延时和抖动问题的关键。 基于微分流量模型的路由器队列控制研究 1 2 2 研究网络流量模型的必要性 从系统工程的科学观点来看，任何排队规则和策略都需要以数学模型作为其 研究的基础。排队论( q u e u i n g t h e o r y ) 或称随机服务系统理论，作为运筹学研 究的一个有力手段，在计算机网络和计算机系统性能评价中占有相当重要的位 置1 7 “。传统的网络流量模型将网络中的分组到达和服务时间分布假设为泊松过 程。泊松过程对于网络传输的性能评价具有简单、有效等显著特点并曾成功地 用于电话网的设计和操作中。在泊松到达条件下，集群( c l u s t e r ) 和突发( b u r s t ) 在较小的时间尺度内发生。因而随着业务源数量的增加，其突发性将会被吸收， 集群业务会变得越来越平滑。这种长期的平滑性意味着队列在较短时阆建立起 来，并在一个较长的时间内排空，因此系统只需要中等大小的缓存容量。 9 0 年代以来，大量的证据显示实际网络中的数据传输具有统计上的自相似 性( s e l f - s i m i l a r ) 1 ，1 引，自相似过程与传统的泊松或马尔可夫业务模型相比具有许 多不同的统计性质，最主要的一点是反映业务流量在任意时间范围内的统计自 相似性，突出表现为：突发没有明确长度，集群突发在所有时间尺度上发生， 不可将其平滑掉，导致队列缓冲容量远大于泊松到达的缓冲容量。传统的基于 m a r k o v 模型的性能评价结果对于自相似传输已不再适用，需要新的模型与基于 新模型的新工具。 目前，t c p i p 协议族成为互联网事实上的协议标准。为解决网络的拥塞问题， v a nj a c o b s o n 于2 0 世纪8 0 年代引入了t c p 拥塞控制机制【3 】。随着t c p i p 的协 议族版本的不断更新，慢启动、拥塞避免、快速重传和快速恢复等机制也逐步加 入其中。t c p 为每个连接维护一个新的状态变量，称为拥塞窗口 ( c o n g e s t i o n w i n d o w ) 。源端依据拥塞窗口大小来限制给定时间允许传送的数据 量。t c p 将超时作为发生拥塞的标志，使用确认信息( a c k ) 来协调分组的传 送，并按累次增a l l 成倍减小( a i m d ) 算法调整拥塞窗口大小。因此，网络流量 变化并不是一种纯粹的随机过程，而是在很大程度上受着拥塞控制这种自同步的 反馈机制的影响和制约。研究表明，源端、用户行为和t c p 协议拥塞控制机制 是导致传统排队论无法适用的主要原因i ” 1 6 1 。 网络拥塞控制已经成为当前规模最大的人工反馈系统之一。然而单纯的端到 端拥塞控制作用毕竟有限，为此i e t f 在r f c 2 3 0 9 t ”j 中建议在路由器中使用主动 队列管理( a c t i v eq u e u em a n a g e m e n t ) 技术并推荐r e d l l 8 l 为候选算法。主动队列 管理是指路由器在缓存区满之前主动丢弃一些数据包，促使终端节点尽快对拥塞 作出响应，降低发送速率，以避免路由器缓存区的溢出，从而降低路由器的丢包 率，并提供较低的服务延迟。 综上所述，路由器上的队列长度变化受到网络流量的变化和主动队列管理算 法的影响；而另一方面，网络流量的变化情况又依赖于t c p 拥塞控制机制和路 2 硕士学位论文 由器主动队列管理的交互行为。 深入地了解网络动态行为，对网络进行设计管理，利用队列管理算法对路由 器的队列长度和抖动进行控制，提高网络的性能，需要针对主动队列管理算法与 拥塞控制机制的交互行为建立适当的数学模型。 1 3 研究背景 1 3 1 路由器排队算法概述 旦流量的到达速率超过路由器的转发能力，如果路由器没有足够的缓存容 量来接纳这些分组，它们将会由于暂时无法得到服务而被强制性地丢弃。因此， 无论资源分配机制的其它部分是否复杂，任何路由器都必须应用某种排队规则来 决定如何缓存等待发送的分组。根据排队服务所面向的对象，可以将路由器的排 队算法分为队列调度算法和队列管理算法。 1 311 队列调度算法 队列调度算法主要用于带宽的分配，它控制着数据流实际占有的带宽资源。 队列调度发生在端口出口处，通常包括：先进先出( f i f o ) 、加权公平排队( w f q ) 、 优先级排队( p q ) 和客户化排队( c o ) 等等1 1 9 i 。由于带宽和公平性问题不是本 文的重点，因此只对f i f o 、f q 和w f q 进行简单的介绍，其它算法细节可参考 相关文献。 1 ) 先进先出( f i f o ) ： 也称先来先服务排队算法，是目前i n t e r n e t 使用最广泛的队列调度方式。它 的最大优点在于实施较为简单。当缓存区满时，该方式对分组采用“丢尾” ( d r o p t a i l ) 算法进行处理，即强制丢弃。该算法对于具有突发性的存在包丢失 的连接来说，公平性较差1 2 0 1 。 2 ) 公平排队算法( f a i r q u e u i n g ，f q ) ： 路由器对当前控制的每个流建立并维护一个排队队列。路由器以轮转方式为 这些队列进行服务。公平排队算法的带宽分配独立于数据包大小，各服务在队列 中几乎同时开始。所以该算法在提供公平性的同时，仍具有较好的统计复用特性， 能够与端到端的拥塞控制机制较好地协同工作。其缺点主要在于实现起来比较复 杂。需要对每个数据流进行捧队处理、状态统计、数据包的分类( c l a s s i f y ) 以 及数据包调度等额外开销。 3 ) 加权公平排队算法( w e i g h t e d f a i rq u e u i n g ，w f o ) ： w f q 是公平排队f q 的改进算法。不同的连接和应用对于带宽的要求亦有不 同。为了改善算法对于不同应用的适应性，w f q 允许为每个队列制定并分配一 个权值，该权值逻辑上用来描述路由器为该队列服务一次所传送的比特数。通过 3 基于微分流量模型的路由器队列控制研究 该权值，路由器可以有效的控制数据流可获得的带宽的比例，从而满足不同的应 用需求。 1 3 1 2 队歹l j 管理算法 队列管理算法控制着数据流潜在占有的带宽资源、当前占有的内存资源或队 列的深度。队列管理算法管理着队列容量，其主要功能是给突发性数据业务一个 缓冲，降低丢包率。流行的算法有髓机早期侦测( r e d ) 、加权随机早期侦测 ( w r e d ) 和显式拥塞通告( e c n ) 等。 1 ) 随机早期检测算法( r a n d o me a r l yd e t e c t i o n ，r e d ) ： r e d 算法以平均队列长度作为衡量网络拥塞程度的指标，并以此为依据。按 照一定的概率丢弃新到达路由器的数据包。r e d 设计的早期思路是为了避免连 续丢弃属于同一连接的数据包。r e d 算法按概率随机丢弃数据包，可以在各连 接之间实现分摊丢包率，因而在一定程度上保证在各连接之间获得较好的公平性 i 2 m ，并且对突发业务有较强的适应性。然而该算法的性能对于网络状况比较敏 感，不合适的参数设置将使得路由器吞吐量显著降低、丢包率增加以及队列剧烈 振荡f 2 。r e d 算法详情可见第三章t c p 拥塞避免机制。 2 ) 显示拥塞通告算法( e x p l i c i tc o n g e s t i o nn o t f c a t i o n ，e c n ) e c n 2 2 】由以前d e c b i t 算法得到启发，通过在源端所发送的数据包中嵌入 e c n 使之能发送比特位，而路由器则根据网络状况设置c e ( c o n g e s t i o n e x p e r i e n c e d l 比特位。源端按照所接收的反馈回来的c e 置位的数据包，调整发 送速率，将随后发出的数据包标记为可丢弃的数据包。e c n 可以和队列管理算 法结台使用，但是要求t c p 端均支持e c n 。e c n 的优势在于不需要超时重传， 也不依赖于粗粒度的t c p 定时机制，因而对于一些对时延有一定要求的应用效 果较好。 针对已有的队列管理机制的不足，相继提出了一些新的主动队列管理算法以 及相应的改进算法，例如b l u e 【2 3 】、g r e e n l 2 4 1 、r e m 2 5 1 、r i o 2 6 j 和f r e d 2 7 】等等。 与之前将路由器中平均队列长度作为拥塞判别标准的算法不同。b l u e 将分组丢 失率和链路有效利用率来衡量网络拥塞的程度。r e m 算法则将队列即时长度、 目标队列长度、链路的输入速率和输出速率的加权求和作为拥塞的测度。f r e d 和r i o 都是r e d 算法的改进算法和变种算法f r e d 对每个业务流分别实施一 个r e d 独立的算法，以保证更好的公平性；r i o 贝i j 在r e d 算法基础上又增加了 一个门限值，一般用于区分服务的研究。算法详情可参考文献 2 3 2 7 。 1 3 2 常用网络排队分析方法 1 3 2 1 传统排队分析方法 传统的排队论以泊松过程为假设条件。泊松过程的无后效性使得数学分析过 4 硕士学位论文 程大为简化，并得到漂亮的数学结果。但根据排队论分析所得到的预测结果与实 际观测到的性能差异很大，这说明排队论与实际网络的队列问题有一定的差距， 不能适用于实际网络的分析与设计。基于排队论的主要排队分析方法如下： 1 ) 生灭过程： 对于输入或到达过程为泊松过程，服务时间为负指数分布的排队系统，其到 达过程和服务过程均存在无后效性。一般采用生灭过程( b i r t h d e a t hp r o c e s s ) 来进行描述和分析。 2 ) 扩大状态空间法： 对于输入和服务不具有无后效性的排队系统，可以采用扩大空间状态方法将 非马尔可夫过程转化成多维状态空间马尔可夫过程求解。例如处理m 压r l 8 和 e r m 1 8 排队系统时可采用该方法。 3 ) 嵌入式马尔可夫过程： 当个排队系统的服务过程不是马尔可夫过程，但到达或服务中有一个过程 符合无后效性时。可采用嵌入式马尔可夫链来进行处理。当可以使用半马尔可夫 过程描述排队队长变化过程时，或者服务时间本身即为半马尔可夫过程，或者可 嵌入一个半马氏过程时，往往采用半马尔可夫理论对这类系统进行分析。 1 3 3 2 现代通信研究的捧队分析方法 自发现网络传输存在自相似性后，传统的排队分析方法逐渐被淘汰。现代通 信系统的研究大部分都是基于自相似的长相关性来进行分析。目前还没有一套完 整的技术能够解决长相关下队列性能的分析问题，因此许多研究只能采用仿真实 验分析的方法。当然，现代通信的分析方法研究也取得了一定进展，其主要和常 用的分析方法有以下两种： 一种方法是使用m p 模型；使用基于p a r e t o 分布的o n o f f 源对泊松到达过 程进行监控，来描述自相似过程的产生，并以此对足够大的队列中的分组丢弃进 行分析； 另一种思路则是使用m a r k o v 方法来近似地描述自相似过程，即通过多个两 状态的马尔科夫调制泊松过程m m p p ( m a r k o vm o d u l a t e dp o i s s o np r o c e s s ) 模型的 迭加在若干个时间尺度上近似逼近具有长相关( l r d ) 特性的自相似分组传输， 其优点是可以利用整套的m a r k o v 性能评价方法对具有自相似特性的传输完成队 列近似理论分析。 1 3 3 网络流量控制模型 流量模型是网络性能分析和通信网络规划设计的基础，精确的流量模型对设 计高性能网络协议、高效网络拓扑结构、业务量预测与网络规划、高性能价格比 的网络设备与服务器、精确的网络性能分析与预测、拥塞管理与流量均衡都有重 s 基于微分流量模型的路由器队列控制研究 要意义。 尽管拥塞控制早己在网络中广泛的实施并对流量的控制取得显著的效果，但 对于网络的行为和流量的分析一直是研究的难点。近年来，在网络的分析模型的 研究上出现了较大的进展，针对拥塞控制的反馈平衡结构、延时、丢包、动态性 和稳定性的各类分析模型先后被提出1 2 8 】。 使用极限理论对网络进行分析现在受到越来越多的重视。极限理论建模有三 个优点，首先。利用极限理论可以过滤相关的某些细节来对模型进行简化，而不 需要专门或特定的假设；其次，由于极限理论的知识和内容是概率论的核心，因 此现有的极限理论只需要较弱的假设即可应用于流量模型；第三，当网络出现较 高利用率即用户数较大时，资源分配问题的研究就显得更有意义。在这些情况下， 随着用户数的不断增加，利用极限行为来描述网络则愈发准确。文献1 2 9 1 3 0 1 分 析了e c n r e d 网关上维持大量t c p 流的极限行为以及r e d 队列的动态变化情 况，文献 3 h 则对使用极限理论对t c p 流量建模的方法进行了综述。 拥塞控制利用a c k 作为信号来协调分组的发送，对发送的流量大小进行控 制。由于从发生分组丢弃到实行拥塞控制存在一定的延时。其本质上是一个非线 性时变反馈控制系统。为了研究其动态行为，一般需要先建立网络流量的微分方 程模型【3 2 日4 1 。v i s h a lm i s r a 等人使用随机微分方程( s d e ) 对t c p 窗口行为建立 数学模型【35 1 ，随后将s d e 转换为常微分方程来分析r e d 主动队列管理机制【3 6 】。 h o l l o t 则将该非线性时变模型进行线性化，运用经典线性控制理论分析了r e d 算法的稳定性，并给出了算法的稳定条件【”。 1 4 本文的主要工作 本文以t c p 流量控制微分方程模型为基础，以路由器排队队列为研究对象， 结合r e d 主动队列管理算法，研究在稳定状态下如何控制队列长度以及稳定队 列波动的方法，以降低网络传输的抖动并实现对网络延时的控制。主要工作有： 1 )通过对t c p 流量控制微分方程模型的深入分析，将主动队列管理算法与 拥塞控制机制的交互行为看作一种反馈控制系统，结合r e d 算法建立r e d 队列管理的反馈控制方块图。 2 )以r e d 算法的单位反馈控制系统为基础，提出一种将即时队长和期望队 长之差作为系统误差的队列波动分析方法。并以系统的稳定条件为前提， 利用终值定理和相关研究结果对r e d 队列反馈控制系统的稳态误差进行 分析。 3 )针对现有微分流量模型无法描述u d p 流量变化的问题，在路由器的队列 变化中加入u d p 流量，建立t c p 和u d p 混合流的随机微分方程模型，实 现对t c p 微分流量模型的扩展。 6 硕士学位论文 4 ) 利用新模型求解稳定状态下路由器的分组丢弃概率，实现对原有的基于 t c p 流的r e d 队列长度控制方法的改进。改进后的队长控制方法对t c p 以及t c p 和u d p 的混合流均具有较好的适应性。 5 )将网络模拟器n s 作为仿真实验环境，对研究结果进行分析与验证。 1 5 论文的结构 第1 章 绪论 第2 章 仿真实验环境 n s 第3 章 t c p 流量控制徽 分方程横型 图1 1 论文结构图 7 第4 章 一种新的队列波动分 析方法 第5 章 t c p 和u d p 混合流队 列长度控制方法 结论 基于镀分流量模型的路由嚣队列控制研究 2 1 引言 第2 章仿真实验环境n s 网络分析与设计的常用方法主要有三种：数学分析、实际测量和仿真实验。 数学分析将分组到达和服务时问做相应的假设，建立排队服务的数学模型，进行 分析和求解。实际测量包括主动测试和被动测试。其中主动测试方法是指在网络 中捅入一些数据包，根据这些数据包的响应来测定性能指标，而被动测试则是在 网络的某些固定节点上采集数据包，然后做离线分析。仿真实验方法则是通过构 造发送数据源，建立模拟的拓扑结构，利用仿真工具跟踪网络的行为进行网络分 析和设计。 构建测试环境在实际网络中测试，一方面代价过高而结果不可再现，另一 方面测试结构搭建之后，拓扑难以改变，因而对于大规模测试比较困难，一般作 为验证辅助手段。随着网络流量自相似性现象的发现，原有的m a r k o v 模型对于 高速网络性能评价领域已不再适用，然而建立自相似流量模型的数学难度较大。 现在对于网络的研究和分析主要采用模拟和仿真实验的方法。 2 2n s 介绍 网络仿真软件的可控制，可重现和可扩展性使其得到了广泛应用。n e t w o r k s i m u l a t o r i ”1 ( 以下简称n s ) 是由l b n l ( l a w r e n e eb e r k e l e yn a t i o n a ll a b o r a t o r y ) 开发的一个基于事件驱动模型的面向对象的网络模拟器。所谓面向对象是指系统 的建模过程与对客观世界的认识过程尽可能的一致，也就是说系统是对象的集 合；而系统的状态行为就是对象的属性和方法。对象的属性和对于属性的操作方 法完全封装在对象内部，外部的作用必须通过对象的操作接口来实现。面向对象 的仿真系统通过对象之间互相发送消息来执行，即以事件为驱动。n s 支持的协 议基本包括了t c p i p 协议域的所有协议：各类t c p 版本( 如s a c k 、t a h o e 、 和r e n o ) 、u d p 、r t p 、多播、无线和移动网络等等，以及发展中的i n t e r n e t 协 议( 如s r m ) 模型。n s 的源代码全部公开。并提供开放的用户接口。用户可以 参与n s 的协同开发，也可以对n s 的源码进行修改，以适应不同的网络模拟和 仿真实验的需求。n s 的另外一个特点是可以将实际网络流量导入到网络仿真环 境【3 ，使得用户能构建近似真实环境的网络平台来测试和分析协议的性能。 8 硕士学位论文 2 3n s 的基本结构和建模流程 2 3 in s 文件组织与类的层次划分 图2 1n s 文件组织结构图 n s 按目录方式来组织和管理文件和相应的文档。如图2 1 所示，在模拟器根 目录下，n s 按工具包和模拟器主要文件的类别来建立子目录。绝大部分c + + 和 o t c l ( 一种面向对象的t c l 脚本语言) 脚本编写的模拟器实现以及o t c l 测试脚 本和示例脚本均保存在n s 2 目录下。其中所有的o t c l 代码和测试以及示例脚本 位于l l s 2 的子目录t c l 下。除实现w w w 的相关代码之外，其它用于实现事件调 度器和基本网络组建对象类的所有的c + + 源代码则位于主目录n s 2 下。 目录t c l 包括e x 、t e s t 和l i b 等若干个子目录。l i b 目录包含了n s 的实现的基 本和关键部分的o t c l 源码，例如代理、节点、链路、包和路由等等。用于实现 局域网、w e b 和多播的代码则位于t c l 中的其它独立子目录。通过修改l i b 中的 某些脚本文件，可以实现对某些成员函数、属性和参数的默认值以及数据包的格 式修改。 n s 采用面向对象的设计方法，将网络组件对象进行了封装，其类的层次关 系如图2 2 所示。在n s 中，绝大部分类都是t c l o b j e c t 类的子类，同时t c l o b j e c t 类也是所有o t c l 库对象如调度器、网络组件、计时器以及包括n a m ( n s 的 动画演示工具) 相关对象在内的其它对象的超类。t c l o b j e c t 用一个静态链表来 记录用户所创建的所有对象，而每个对象都有唯一的标识来记录其所属的类名。 使用公用基类可以将各种对象存储在同一个链表中。函数可以方便的使用和处理 对象并按需要进行强制类型转换。n s o b j o c t 一方面是t d o b j e c t 的子类，另一方 面又是全部基本网络组建对象的父类，包括节点、链路、代理、跟踪记录和数据 发送源等等。基本网络对象按照输出数据的路径数进一步被分为连接器 ( c o n n e c t o r ) 和分类器( c l a s s i f i e r ) 两个子类。脚本文件的修改方法和网络对 9 基于微分流量模型的路由器队列控制研究 象间通信方式见文献 4 0 - 4 2 。 图2 2n s 的类层次结构图 节点( n o d e ) 表示网络中实际的节点和路由器设备。虽然节点的端口数有限， 多业务源可以连接到一个节点的不同端口。节点维护一个路由表，依据设置的路 由算法和目的地址转发数据包。节点本身无法产生分组，必须靠代理来进行分组 的生产和消费。代理( a g e n t ) 是产生和消费分组的对象，属于传输层实体。代 理运行于节点上，节点上的代理被自动分配一个唯一的端口号。建立连接后，源 端和目的端的代理之间进行分组的传输，直到其运行时间结束。链路( l i n k ) 用 于连接节点和路由器。节点可以有多条输出链路。所有的链路均以队列的形式来 管理分组的到达、离开和丢弃。链路可以统计并记录所传输的字节数和分组数， 利用t r a c e 对象还可以对队列进行监视并记录队列日志。n s 的其它对象定义和 功能可参考文献【4 2 】。 2 3 2n s 的建模方法和设计流程 n s 使用两种设计语言：o t c l 和c + + 。为了能提高模拟器对数据包和网络事 件的处理的效率，n s 对于事件调度器和基本的网络组件对象使用c + + 语言编写。 c + + 对象编译后可以通过在脚本程序中使用o t c l 链接来进行调用。o t c l 是一种 面向对象的描述性脚本语言，需要o t c l 解释器对其解释执行。o t c l 主要用于 n s 建模和模型的参数配置，其使用简单方便。o t c l 链接可以建立一个与为c + + 对象相匹配的o t c l 对象。用户在使用o t c l 的成员函数与成员变量进行操作时， 实际上直接调用所对应的c + + 对象的控制函数和可配置的变量。而从用户视角来 看，n s 的运行方式屏蔽了c + + 实现细节。 作为面向对象的仿真器，n s 通过c + + 和o t c l 两种语言的使用，形成了编译 和解释两个层次。用户以o t c l 的脚本作为前台使用，然后映射到对应的编译层 次对象，从而在保证效率的同时，为建立仿真实验提供了极大的方便和灵活性。 使用n s 进行网络的模拟和仿真实验，需要使用o t c l 脚本编写程序来来初 1 0 硕士学位论文 始化事件调度器，使用网络对象和库函数建立网络拓扑结构，定义流量源端开始 和停止发送数据包的时间。主要分为以下三个步骤：定义网络拓扑结构、添加流 量发生源与接收端以及路由协议选择。 1 ) 生成网络拓扑结构 n s 支持使用图形工具( 如g t - i t m 、t i e r s ) 以图形描述的方式先产生网络的 拓扑结构，然后通过相应的工具转化为n s 的描述格式，以便应用于n s 的仿真 实验。n s 也支持以手工方式用o t c l 语言直接进行定义。网络的拓扑结构包含两 个方面的内容，即节点和链路。也就是说，在生成网络拓扑结构时，需要产生网 络的节点，节点之间链路、定义链路的带宽和延时以及路由器的队列管理策略。 o t e l 脚本命令定义如下： 节点生成 s e tn ( $ i ) 【$ n sn o d e 】 单向链路定义 $ n ss i m p l e x l i n kn ( $ i ) n ( s j ) 指链路带宽， 指链路延时， 是路由器的队列 管理策略，如d r o p t a i l ，r e d ，c b q ，f q ，s f q ，d r r 等。 双向链路定义 s n sd u p l e x - l i n k ( $ i ) n ( $ j ) 其中参数定义与单向链路相同。 2 ) 流量源的添加 所谓流量源的添加包括添加传输层代理和上层应用。首先，需要在网络节点 上添加传输协议的代理( t c p - - t a p 、u d p - - n u l l 等) 来定义传输层协议。然 后，在传输协议代理上添加上层应用。最后在源端和目的端建立连接来完成整个 通信流的定义。n s 中定义的应用包括h t t p 、t e l n e t 、f i p 和e b r 等等。o t e l 脚本 命令定义如下： 建立t c p 连接 s e tt c p 【n e wa g e n t t c p 】建立t c p 源端 s e tt c p s i n k 【n c wa g e n t t c p s i n k 】建立t c p 接收端 s n sa t t a c h a g e n t $ n o $ t c p 将t c p 源端与节点n o 绑定 $ n sa t t a c h a g e n t $ n l $ t e p s i n k 将t c p 接收端与节点n l 绑定 s n sc o n n e c ts t e p $ t e p s i n k 建立源端与接收端的t c p 连接 建立u d p 连接 s e tu d p 【n c w a g e n t u d p 】 建立u d p 发送端 s e tn u l l n e wa g e n t n u l l 建立u d p 接收端 $ n sa t t a c h a g e n t $ n os u d p 将u d p 发送端与n 0 节点绑定 1 1 基于微分流量模型的路由器队列控制研究 s n sa t t a c h - a g e n t $ n l $ n u l l将u d p 接收端与n 1 节点绑定 s n sc o n n e c t $ u d p $ n u l l 建立u d p 接收端与发送端之间的传输连接 产生盯p 应用 s e tf t p 【n e wa p p l i c a t i o n f t p 】建立f 1 p 应用 s f t pa t t a c h a g e n t $ t c p 将f t p 添加到t c pa g e n t 产生u d p 流量 s e ts r c 【n e wa p p l i c a t i o n f r r a f f i c c b r 】建立c b r 应用 $ s r ca t t a c h a g e n t $ u d p 将c b