（计算机应用技术专业论文）aqm算法的稳定性与改进算法研究.pdf

南京邮电大学硕士研究生学位论文 摘要 a q m 算法的稳定性与改进算法研究 摘要 随着网络多媒体技术的飞速发展，i n t e r n e t 上的多媒体应用层出不穷，传 统的i n t e m e t 仅提供尽力而为的传送服务，但因其中路由器没有q o s 保证而影 响了i p 网络向综合业务网络发展。i pq o s 是指i p 数据流通过网络时表现出 来的特性，如：传输服务的可靠性、延时、延时抖动、吞吐量和丢包率等。 大多数网络提供的负载容量大于它实际的处理能力。如果没有对业务流进入 网络的约束标准，瓶颈链路的队列长度会增加从而增大了数据包的时延，最 终，网络因缓存空间耗尽而将丢弃到达的数据包，即产生了拥塞现象，这就 可能不符合规定的最大延迟和丢包标准值。 i n t e m e t 的主要互联协议t c p i p 的拥塞控制机制对于预防或减轻拥塞具 有特别重要的意义。t c p 层使用基于窗口的端到端的拥塞控制。然而，随着 i n t e m e t 规模的迅速扩大，仅依靠端到端的拥塞控制很难使网络保持在高效且 公平的运行状态，于是在路由器中实现的主动队列管理( a q m ) 的拥塞控制 应运而生。本文介绍了针对t c p 的拥塞控制形成的一些t c p 的实现版本，讨 论了基于i p 层的a q m 拥塞控制方案，分析了t c p 和i p 拥塞控制结合的方 案的稳定性。目前，在路由器中普遍使用的a q m 算法为f l o y d 等人提出的随 机早期检测( r e d ) 算法，并且r e d 算法被r f c 2 3 0 9 推荐作为主动队列管理 的唯一候选算法。本文详细介绍了r e d 算法的实现，并基于自动控制理论分 析了r e d 算法自身存在的缺陷，即响应时间与系统稳定性的矛盾，和稳定状 态时的队列长度依赖于网络的负载水平；然后，针对以上缺陷提出改进，形 成了r e d 算法的改进方案c p d 算法。c p d 算法具有：( 1 ) 响应时间短，( 2 ) n 南京邮l b 大学顶士研究生学位论文 摘要 抗干扰性高且稳定性好，和( 3 ) 网络效用高。最后，本文通过仿真实验，比 较了r e d 算法和c p d 算法的q o s 性能( 时延和丢包率) ，验证了c p d 算法 方案的有效性和对r e d 算法稳定性的改善效果。 关键词：拥塞控制，q o s ，t c p 层，i p 层，主动队列管理，稳定性 i i i 南京邮l 乜大学硕：卜研究生学位论文摘要 r e s e a r c ho ns t a b i l i t yo fa q ma l g o r i t h ma n d i m p r o v e m e n t a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n t o fi n t e m e t ，m o r ea n dm o r ea p p l i c a t i o no f m u l t i m e d i ae m e r g e c u r r e n t l y , t h et r a n s m i t t i n gm e c h a n i s mo f ”b e s t - e f f o r t ”，w h i c h i s a d o p t e db yt h et r a d i t i o n a li pn e t w o r k ，c a nn o ts a r i s f yt h eu s e r sr e q u i r e m e n t s i n c et h er o u t e r so ft r a d i t i o n a li pn e t w o r kc a n n o tp r o v i d ea n yq u a l i t yo f s e r v i c e ( q o s ) g u a r a n t e ef o ru s e r s i ti sd i f f i c u l t yf o ri pn e t w o r kt ob e c o m ea i n t e g r a t e ds e r v i c e sn e t w o r k t h eq o so f i pn e t w o r km e a n st h ep r o p e r t i e so f i pd a t a f l o w sp a s s i n gt h r o u g han e t w o r k ，f o re x a m p l e ，r e l i a b i l i t y 、d e l a y 、t h r o u g h p u t 、 p r o b a b i l i t yo fd r o pa n d s oo n i nm o s tt i m e ，t h el o a di nn e t w o r ki s l a r g e rt h a nt h e c a p a b i l i t yo fp r o c e s ss u p p o r t e db yn e t w o r k t h i sw o u l de x h a u s tt h eb u f f e ro f r o u t e ra n dr e s u l t si nt h ea p p e a r a n c eo fc o n g e s t i o n ，i ft h e r ei sn os t a n d a r do f r e s t r i c t i o n t h ec o n g e s t i o nc o n t r o lm e c h a n i s mb a s e dt c p h ph a s s i g n i f i c a n c e t c p c o n g e s t i o nc o n t r o li se n d t o - e n dm e c h a n i s mb a s e dw i n d o w s ，w h e r e a si tc a nn o t e n s u r et h en e t w o r kh a sh i g hu t i l i z a t i o na n df a i ra m o n gd i f f e r e n tt r a f f i c f l o w , a s i n t e m e t e x p l o d e t h e a c t i v e q u e u em a n a g e m e n t ( a q m ) c o n g e s t i o nc o n t r o l m e c h a n i s mi m p e l e m e n t i n gi nr o u t e re m e 唱e sa st h et i m e sr e q u i r e t h i s p a p e r i n t r o d u c es o m et c pa l g o r i t h m so fc o n g e s t i o nc o n t r o la n ds o m ea q m a l g o r i t h m s t h e nd i s c u s st h e s t a b i l i t yo fs y s t e mw i t ht c p a q mc o n g e s t i o ns c h e m e s t h e r a n d o me a r l yd e t e c t i o n ( r e d ) a l g o r i t h mi sap o p u l a ra q mu s i n gi nr o u t e ra t i v 南京邮电大学硕士研究生学位论文摘要 p r e s e n t t h i sp a p e ra n a l y s e st h es h o r t so fr e da l g o r i t h mb a s e dc l a s s i c a lc o n t r o l t h e o r i e s ，t h el i m i t a t i o n sa sf o l l o w s ：( 1 ) t r a d e o f fb e t w e e ns p e e do fr e s p o n s ea n d s t a b i l i t y ；( 2 ) t h es t e a d ys t a t eq u e u el e n g t hd e p e n do nt h el o a dl e v e l t h e nw e p r o p o s eac p da l g o r i t h mt oi m p r o v er e d ，t h es t r o n g p o i n ta sf o l l o w s ：( 1 ) r a p i d r e s p o n s e ；( 2 ) g o o ds t a b i l i t y ；( 3 ) h i g hu t i l i z a t i o n f i n a l l y , s i m u l a t i o nr e s u l t s a r e s h o w e df o r c o m p a r i n gt h eq o sp e r f o r m a n c e s o fr e dw i t ho fc p d ，a n d d e m o n s t r a t et h e a v a i l a b i l i t y a n d i m p r o v e m e n tf o r r e da l g o r i t h mo fc p d a l g o r i t h m k e yw o r d s ：c o n g e s t i o nc o n t r o l ，q o s ，t c pl a y e r , i p l a y e r , a c t i v eq u e u e m a n a g e m e n t ，s t a b i l i t y v 南京邮电人学硕士研究生学位论文 前高 前言 本人的硕士学位论文 a q m 算法的稳定性与改进算法研究对i p 捌塞控制算法r e d 进行了相关研究。 本人按照南京邮电大学硕士学位论文开题报告所规定的研究任务和工作计划，经过一 年半的课题研究，本人的学位论文基本完成了研究生论文开题报告所预定的计划及要求。 本人郑重声明：所呈交的学位论文( ( a q m 算法的稳定性与改进算法研究，除文中特 别加以标注的地方外，不包含其他人已经取得的或已经发表的研究成果。本人的学位论文 指导教师，在本人攻读硕士学位期间，每个学期都多次强调科研工作中学术道德的重要性， 禁止不严肃、不真实的行为；本人对本人学位论文 a q m 算法的稳定性与改进算法研究 所使用的o p n e t 网络仿真软件以及所获得的仿真数据的真实性负全部责任。 南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机应用技术 研究方向：计算机通信与网问互连技术 作 者：翌堕级研究生章奕指导教师壁查选 题目： a q m 算法的稳定性与改进算法研究 英文题目：r e s e a r c ho ns t a b i l i t yo fa q ma l g o r i t h ma n d i m p r o v e m e n t 主题词：拥塞控制q u st c p 层i p 层主动队列管理 稳定性 c o n g e s t i o nc o n t r o lq o s a c t i v eq u e u em a n a g e m e n t t c pl a y e ri pl a y e r s t a b i l i t y 南京邮电大学硕士研究生学位论文引言 论文背景 引言 拥塞控制是一种协调发送端的发送速率和接收端的接收速率一致性的数据传输同步 技术。在数据传输中，若发送速率大于接收速率，接收站就会来不及处理接收到的数据帧 而产生接收缓冲区溢出，造成数据帧的丢失，这种现象称为同步失调，也就是发生了拥塞。 若发送速率远小于接收速率，接收站就会一直处于等待状态，造成介质空闲，介质利用率 过低。通过捌塞控制技术可以有效地解决同步失调和高效利用介质问题。在处理网络的拥 塞问题时一般采用两种方法：是采取措施防止网络拥塞；二是采取措施减少已拥塞时的 拥塞程度，即减少拥塞时间以及防止拥塞扩散，直至搠塞的消失。 i n t e m e t 主要互联协议t c p f i p 的拥塞控制机制( c o n g e s t i o nc o n t r 0 1 ) 对于控制拥塞具有 特别重要的意义。拥塞控制是确保i n t e r n e t 的鲁棒性( r o b u s t n e s s ) 的关键因素，因此成为 当前网络研究的一个热点问题。网络产生拥塞的根本原因在于用户提供给网络的负载 ( 1 0 a d ) 大于网络资源容量( 如存储空间和带宽) 和处理能力( o v e r l o a d ) ，表现为数据包 时延增加、丢包率增大、吞吐量( t h r o u g h p u t ) 下降等。使用t c p 协议可以实现端到端的 揣塞控制。在t c p 协议中，每个源结点缓慢地增加数据传输的速率，一旦发现捌塞就减小 速率。当缓冲区溢出而出现丢包时可探知拥塞已经发生。此时，目的结点负责通知源结点 发生丢包，并告知中间结点不要再直接给源结点提供任何反馈信息。i p 拥塞控制是在路由 器中实现的，在每个数据包到达路由器时使用排队策略和丢包算法进行控制，主动队列管 理( a q m ) 方案正是为了解决i p 拥塞控制问题所提出的。目前在i n t e r n e t 上实际使用的拥 塞控制机制基本上是建立在t c p 的窗口控制基础上的。然而，在i n t e m e t 如此复杂的异构 网络中，让所有用户在i n t e m e t 应用中都能兼容这种端到端的拥塞控制是很困难的。因此， 网络必须参与资源控制工作。i p 层的拥塞控制研究也就成为目前研究的热点。r e d ( 随机 早期检测) 算法是由f l o y d 等人提出的，作为r f c 2 3 0 9 推荐的a q m 唯一候选算法，也是 目前路由器中普遍使用的q o s 拥塞控制算法。当大量通信是自适应形式时( 如t c p 流) ， r e d 是一种非常有效的i p 拥塞控制算法。本文主要在对a q m 方案的深入研究基础上，运 用经典控制理论，提出了对r e d 算法的改进方案c p d 算法，然后使用网络仿真软件o p n e t 对r e d 算法及其改进算法进行了大量的仿真，并基于仿真实验对两种算法进行性能比较 和分析。 南京邮电大学硕士研究生学位论文q 言 论文的章节安排与主要工作 第一章介绍了网络中的q o s 的定义，不同业务流的q o s 需求，以及q o s 的关键指标、 主要技术和控制方法。 第二章介绍了t c p a q m 协议的相关理论，包括t c p 拥塞控制机制及其实现算法，并 讨论了t c p a q m 协议的稳定性。 第三章介绍了a q m 算法方案，包括a q m 拥塞控制方案的提出以及a q m 的实现算 法，并详细描述了r e d 算法的实现。 第四章基于经典控制理论分析了r e d 算法，并在此基础上提出了改进方案c p d 算法， 并基于控制理论对c p d 算法的稳定性迸行了讨论。 第五章使用网络仿真软件o p n e t 对r e d 算法及其改进方案c p d 算法进行仿真实验， 并对仿真结果进行了比较和分析，得出c p d 算法的稳定性优于r e d 算法的结论。 结束语 2 南京哪电大学硕士研究生学位论文第一章网络中的q o s 控制 第一章网络中的q o s 控制 1 1 业务类型与q o s 需求 一、业务类型 网络是一组结点( n o d e ) 和链路( l i n k ) 的集合。其中，每个结点可以作为一个业务 流的源点或宿点：每条链路作为传输的介质。链路的容量就是我们常说的带宽或者数据速 率。业务流可以是音频，视频或数据等形式。一般来说，如今的网络是各种传输链路、结 点和业务流的混合。 在网络中的通信是通过以“数据包”( p a c k e t ) 的形式来传递信息的，包的大小是固定 的还是变化的取决于网络本身。例如，在a t m 网络中“数据包”叫做信元，它有5 3 个字 节的固定大小。一个t c p 包经过一个a t m 网络的时候，它会被分割成若干个5 3 个字节大 小的信元。当业务流的数据包经过一个网络，就会产生信息的延迟( d e l a y ) 和丢失( l o s s ) 。 造成延迟的原因有两个：一个是在结点处排队造成的，这是可控的因素；另一个是原因是 由于不可控的物理学规律，因为数据包从一个结点到另一个结点不可能比光速还快。造成 数据包丢失的原因是：每个结点的缓存大小是一定的。因此，延迟和丢包率可以作为衡量 业务流的q o s 的两种标准。根据业务流对q o s 的要求可以将其分为两类：对延迟敏感的 业务流和对丢包敏感的业务流。对延迟敏感的业务流以速率和持续时间为特征，需要被实 时传送，但对于丢包率的要求则是视具体的应用而定，所以又被称为实时业务流。比如声 音、视频等，对传送时延有严格的限制，同时允许一定程度内的丢包，是属于实时业务流。 对丢包敏感的业务流需要传送的信息总量为特征，对丢包率有严格的要求，而对延迟的要 求不是非常高，所以又被称为非实时业务流。比如邮件、浏览网页等，对数据的丢失有严 格的要求，而对传送的时间没有严格的限制，是属于非实时业务流。 传统的i n t e m e t 仅提供尽力而为( b e s t e f f o r ts e r v i c e ) 的传送服务，业务量尽快传送，没 有明确的时间和可靠性保障。随着网络多媒体技术的飞速发展，i n t e m e t 上的多媒体应用层 出不穷，如i p 电话、视频会议、视频点播( v o d ) 、远程教育等多媒体实时业务、电子商务 在i n t e r a c t 上传送等。i n t e m e t 已逐步从单一的数据传送网向数据、语音、图像等多媒体信 息的综合传输网演化。这些不同的应用需要有不同的q o s ( q u a l i t yo f s e r v i c e ) 要求，q o s 通常 用带宽、时延、时延抖动和分组丢失率来衡量。各种应用对服务质量的需求在迅速增长。 i n t e m e t 上一些主要应用的业务特征及其q o s 如表1 所示。 南京蛸电大学碗上研究生学位论文第一章网络中的q o s 控制 第一章网络中的q o s 控制 1 1 业务类型与q o s 需求 一、业务类型 网络是一组结点( n o d e ) 和链路( l i n k ) 的集合。其中，每个结点可以作为一个业务 流的源点或宿点；每条链路作为传输的介质。链路的容量就是我们常说的带宽或者数据速 率。业务流可以是音频，视频或数据等形式。一般来说，如今的网络是各种传输链路、结 点和业务流的混台。 在网络中的通信是通过以“数据包”( p a c k e t ) 的形式来传递信息的，包的大小是固定 的还是变化的取决于网络本身。例如，在a t m 网络中“数据包”叫做信元，它有5 3 个字 节的同定大小。一个t c p 包经过一个a t m 网络的时候，它会被分割成若干个5 3 个字节大 小的信元。当业务流的数据包经过一个网络，就会产生信息的延迟( d e l a y ) 和丢失( l o s s ) 。 造成延迟的原因有两个：一个是在结点处排队造成的，这是可控的因素；另一个是原因是 由于不可控的物理学规律，因为数掘包从一个结点到另一个结点不可能比光速还快。造成 数据包丢失的原因足：每个结点的缓存大小是一定的。因此，延迟和丢包率可以作为衡量 业务流的q o s 的两种标准。根据业务流对q o s 的要求可以将其分为两类：对延迟敏感的 业务流和对王包敏感的业务流。对延迟敏感的业务流以速率和持续时间为特征，需要被实 时传送，但对于丢包率的要求则是视具体的应用而定，所以又被称为实时业务流。比如声 音、视频等，对传送时延有严格的限制，同时允许一定程度内的丢包，是属于实时业务流。 对丢包敏感的业务流需要传送的信息总量为特征，对丢包率有严格的要求，而对延迟的要 求不是非常高，所以又被称为非实时业务流。比如邮件、浏览网页等，对数据的丢失有严 格的要求，而对传送的时间没有严格的限制，是属于非实时业务流。 传统的i n t e r a c t 仅提供尽力丽为( b e s t - e f f o r ts e r v i c e ) 的传送服务，业务量尽快传送，没 有明确的时问和可靠性保障。随着网络多媒体技术的飞速发展，i n t e r n e t 上的多媒体应用层 出不穷，如i p 电话、视频会议、视频点播( v o d ) 、远程教育等多媒体实时业务、电子商务 在i n t e r a c t 上传送等。i n t e m e t 已逐步从单一的数据传送网向数据、语音、图像等多媒体信 息的综合传输网演化。这些不同的应用需要有不同的q o s ( q u a l l t y o f s e r v i c e ) 要求，q o s 通常 用带宽、时延、时延抖动和分组丢失率来衡量。各种应用对服务质量的需求在迅速增长。 i n t e r n e t 上一些主要应用的业务特征及其q o s 如表1 所示。 i n t e r n e t 上一些主要应用的业务特征及其q o s 如表1 所示。 南京邮电大学硕士研究生学位论文第一章网络中的q o s 控制 表1 1 一些应用的业务特征及q o $ 需求 应用 业务特征q o s 需求 电子邮件文件数据量小、批文件的传输容许时延，带宽需求低；尽办 传输远程终端而为传送 h t m l 网页浏览一序列小的、突发的文件容许适当的时延；变化的带宽 传输需求；尽力而为传送 客户服务器许多小的双向传输对时延、丢失率敏感；带宽需 电子商务求适当；必须可靠传送 基于i p 协议的连续或变化的传送对时延、抖动非常敏感；带宽 语音实时视频需求低；需要可预计的时延和 丢失率 流媒体变化的位速 对时延、抖动非常敏感；带宽 需求高；需要可预计的时延和 丢失率 显然，现有的尽力传送服务已无法满足各种应用对网络传输质量的不同要求，需要 i n t e m e t 提供多种服务质量类型的业务。而尽力而为的服务仍将提供给那些只需要连通性的 应用。 服务质量q o s 系指用来表示服务性能之属性的任何组合。为了使其具有价值，这些属 性必须是可提供的、可管理的、可验证和计费的，而且在使用时它们必须是始终如一的、 可预测的、有的属性甚至是起决定性作用的。为了满足各种用户应用的需要，构建对i p 最优并具备各种服务质量机制的网络是完全必要的。专线服务、语音、文件传递、存储转 发、交互式视频和广播视频是现有应用的一些例子。 二、q o s 需求 q o s 的关键指标主要包括：可用性、吞吐量、时延、时延变化( 包括抖动和漂移) 和丢 失。 可用性 是当用户需要时网络即能工作的时间百分比。可用性主要是设备可靠性和网络存活性相结 合的结果。对它起作用的还有一些其他因素，包括软件稳定性以及网络演进或升级时不中 断服务的能力。 吞吐量 是在一定时间段内对网上流量( 或带宽) 的度量。对i p 网而言可以从帧中继网借用一些概念。 堕塞墼生查兰堡主堕壅生兰垡堡兰笙二童塑塑主塑旦! ! 堡墅 根据应用和服务类型，服务水平协议( s l a ) 可以规定承诺信息速率( c i r ) 、突发信息速率( b i n ) 和最大突发信号长度。承诺信息速率是应该予以严格保证的，对突发信息速率可以有所限 定，以在容纳预定长度突发信号的同时容纳从话音到视像以及一般数据的各种服务。一般 讲，吞吐量越大越好。 时延 指一项服务从网络入口到出口的平均经过时间。许多服务，特别是话音和视像等实时服务 都是高度不能容忍时延的。当时延超过2 0 0 2 5 0 毫秒时，交互式会话是非常麻烦的。为了 提供高质量话音和会议电视，网络设备必须能保证低的时延。 产生时延的因素很多，包括分组时延、排队时延、交换时延和传播时延。传播时延是 信息通过铜线、光纤或无线链路所需的时间，它是光速的函数。在任何系统中，包括同步 数字系歹t j ( s d h ) 、异步传输模式( a t m ) 和弹性分组环路( r p r ) ，传播时延总是存在的。 时延变化 是指同一业务流中不同分组所呈现的时延不同。高频率的时延变化称作抖动，而低频率的 时延变化称作漂移。抖动主要是由于业务流中相继分组的排队等候时间不同引起的，是对 服务质量影响最大的一个问题。某些业务类型，特别是话音和视像等实时业务是极不容忍 抖动的。分组到达时间的差异将在话音或视像中造成断续。所有传送系统都有抖动，只要 抖动落在规定容差之内就不会影响服务质量。利用缓存可以克服过量的抖动，但这将增加 时延，造成其他闯题。 漂移是任何同步传输系统都有的一个问题。在s d h 系统中是通过严格的全网分级定 时柬克服漂移的。在异步系统中，漂移一般不是问题。漂移会造成基群失帧，使服务质量 的要求不能满足。 丢包 不管是比特丢失还是分组丢失，对分组数据业务的影响比对实时业务的影响都大。在通话 期间，丢失一个比特或一个分组的信息往往用户注意不到。在视像广播期问，这在屏幕上 可能造成瞬间的波形干扰，然后视像很快恢复如初。即便是用传输控制协议( t c p ) 传送数 据也能处理丢失，因为传输控制协议允许丢失的信息重发。事实上，一种叫做随机早丢( r e d ) 的搠塞控制机制在故意丢失分组，其目的是在流量达到设定门限时抑制t c p 传输速率，减 少拥塞，同时还使t c p 流失去同步，以防止因速率窗口的闭合引起吞吐量摆动。但分组丢 失多了，会影响传输质量。所以，要保持统计数字，当超过预定门限时就向网络管理人员 告警。 堕壁塑里查兰堡主型塑兰兰些堡兰 1 2 网络中的q o s 技术 第一章嘲络中的q o s 控制 i n t e r n e t 如何提供q o s 支持( 即i p q o s 问题) 已成为业界关注的焦点。i p q o s 是指i p 数据流通过网络时表现出来的特性，这种特性可以用- l r y l j 指标来表示：传输服务的可靠性、 延时、延时抖动、吞吐量、丢包率。目前，应用于i n t e m e t 的主要q o s 技术有集成服务 ( i n t s e r v ) ，区分服务( d i f f s e r v ) ，q o s 路由和多标签交换( m p l s ) 。这些技术都是基于 互联协议( i p ) 网络的。 1 2 1 集成服务( i n t s e r v ) 集成服务的基本思想是在传送数据之前，根据业务的q o s 需求进行网络资源预留，从 而为该数据流提供端到端的q o s 保证。 资源预留协议r s v p 是集成服务的核心。这是一种信令协议，用来通知网络节点预留 资源。如果资源预留失败，r s v p 协议会向主机发回拒绝消息。 集成服务能够在i p 网上提供端到端的q o s 保证。但是，集成服务对路由器的要求很 高，它对每个数据流都要进行包调度和缓冲管理，当网络中的数据流数量很大时，路由器 的存储和处理能力会遇到很大的压力。因此，集成服务可扩展性很差，难以在i n t e r n e t 核 心网络实施，目前业界普遍认为集成服务有可能会应用在网络的边缘上。 1 2 2 区分服务( d i f f s e r v ) 区分服务体系结构( d i f f s e r v ) 定义了一种可以在互联网上实施可扩展的服务分类的 体系结构。一种“服务”，是由在个网络内，在同一个传输方向上，通过一条或几条路径 传输数据包时的某些重要特征所定义的。这些特征可能包括吞吐率、时延、时延抖动，和 丢包率的量化值或统计值等，也可能是指其获取网络资源的相对优先权。服务分类要求能 适应不同应用程序和用户的需求，并且允许对互联网服务的分类收费。 区分服务的目的是在i n t e m e t 上为流量提供有区别的业务级别，它针对的是流聚合后 的每一类q o s 控制，而不是像集成服务那样针对每个流。区分服务的基本思想是将用户的 数据流按照服务质量要求来划分等级，任何用户的数据流都可以自由进入网络，但是当网 络出现拥塞时，级别高的数据流在排队和占用资源时比级别低的数据流有更高的优先权。 区分服只承诺相对的服务质量，而不对任何用户承诺具体的服务质量指标。1 e t f 定义了区 分服务的体系结构。目前，区分服务是业界认同的i p 骨干网的q o s 解决方案。 6 南京邮电大学坝士研究生学位论文第一章i 奄l 络中的q o s 拧制 1 2 3 q o s 路由 现在的i n t e r n e t 路由协议( o s p f 、r i p 等) 都采用单个测度( 如跳数、成本) 来计算 最短路出，没有考虑多个q o s 参数的要求。q o s 路由根据多种不同的度量参数( 如带宽、 成本、每一跳丌销、时延、可靠性等) 来选择路由。q o s 路由包括三个主要功能：链路状 态信息发布，路由计算和路由表存储。 q o s 路由能够满足业务的q o s 要求，同时提高网络的资源利用率。但是q o s 路由的 计算十分复杂，增加了网络的开销，目前实用的q o s 路由算法还不多见。 1 2 4 多标签交换( m p l s ) m p l s 起源于i p 交换和标记交换技术。因为m p l s 定义了用新的路由协议封装i p 流 量的体系结构和协议，而d i f t s e r v 只关注与现有路由协议独立的i p 包字段，所以它对传统 i p 网络的改变比d i f f s e r v 深刻得多。 i p 是无连接的网络，每台路由器根据所收到的每个包的地址查找匹配的下一跳，并做 相应的转发。但路由器使用的是最长前缀匹配地址搜索( 即搜索匹配前缀最长的一个作为 入口) ，无法实现高速转发。m p l s 在网络的入口边缘路由器为每个包加上一个固定长度的 标签。核心路由器根据标签值进行转发，在出口边缘路由器再恢复成原来的i p 包。因为根 据固定长度的标签搜索目的地址，所以m p l s 能够实现高速转发。根据标签确定的转发路 径称为标签交换路径( l s p ) 。 多协议标签交换m p l s 并不是主要的q o s 机制，也不是q o s 的体系结构，但m p l s 的显式路由功能大大增强了在i p 网络中实施流量工程的能力。对于骨干网业务提供者来 说，这是目前使用最普遍，可实现性最强的一种q o s 机制。 解决i p 网的q o s ，仅仅依靠这四种技术仍然不够，还需要拥塞控制技术( 如r e d ) 、 排队调度技术( 如w f q ) 、约束路由、应用层流量重定向和流量均衡技术等协同工作。 1 3q o s 控制方法1 1 服务质量( q o s ) 是一个用来指定网络可保障的吞吐量水平的一个术语，达到这个吞 吐量水平，网络服务提供商就可以向用户保证端到端的时延不会超过指定的标准。q o s 是 一个依赖于业务流的统计特征的参数。业务流管理的目标是最大化网络资源的效用，同时 满足每个独立用户的q o s 需求。比如，加载在网络上的负载水平应该低于某个标准，从而 堕皇! ! ! ! ! ! ! 叁兰塑圭! ! 塑圭兰垡堡苎笙= ! 型塑堕望竺丝塑 避免产生拥塞，否则，就会导致网络吞吐量的下降和延迟的增大。 考虑网络中两个用户间的数据通信。这两个被网络中的路由器或交换机隔丌的用户简 称结点。如果信源需要发送一条信息，这条信息的长度大于数据包的最大值，那么信源就 会把消息分割成若干个数据包，并逐个发送数据包。每个数据包包含了一部分消息和包头 的控制信息，路由信息是控制信息中的基本成分，因为网络只有通过路出信息爿晴自把数据 包发送到楣应的目的节点。 数据包最初被发送到源端系统指定的第一跳结点。每个数据包到达后，第一跳结点在 对应端口的输入缓冲中暂时存储它们，并根据数据包包头的路由信息查找路由表以确定该 数据包的下一跳结点，然后把数据包送入对应输出端口的发送链路。当链路可用时，每个 数据包被尽快发送到下一跳，再由下一跳进行路由、转发，最终所有数据包通过网络被传 送到相应的目的节点。 路由是包交换网络运行的基本要素。通常网络中采用一种自适应的路由技术，当网络 条件发生变化时，就会改变路由。比如，当一个结点或条通信线路失效时，它们就不能 继续作为路由的组成部分；或者当网络的某个部分发生严重的拥塞时，理想的方式是数据 包的路由绕过这部分发生拥塞的区域。 为了最大化网络资源效用的同时满足每个独立用户的q o s 需求，需要提供专门的q o s 控制机制来划分访问网络结点的资源的优先级。比如，实时排队系统是任何提供q o s 控制 服务的网络实现的核心。提供一类q o s 控制服务需要协同使用接纳控制，业务量访问控制， 包调度和缓存管理技术，以及t c p 层的流量控制技术。 在大多数网络中，网络环境提供的负载容量大于它实际的处理能力。如果没有对业务 流进入网络的约束标准，瓶颈链路的队列长度会增加从而增大了数据包的时延。最终，耗 尽缓存空间，将到达的数据包丢弃，这就可能不符合规定的最大延迟丢包标准值。流量控 制用来调节网络中数据包的数量。流量控制有时也可用于解决两个用户间的速率匹配问 题，比如，当发送端的发送速率大于接收端的处理能力时使用流量控制来确保发送端以适 当的速率发送信息。我们将在第二章中介绍基于t c p 协议实现的流量控制( 也称拥塞控制) 机制及算法 缓存管理提出了缓冲的分配策略和丢包策略。所以，缓冲区的管理对于网络性能的优 劣非常重要。我们将在第三章中介绍基于i p 协议实现的主动队列管理( a q m ) 机制及算 法。 3 南京邮电大学硕士研究生学位论文第二章t c p a q m 协议介绍 第二章t c p a q m 协议介绍 2 1t c p a q m 协议概述 t c p 使用基于窗1 2 1 的拥塞控制。其最初的拥塞控制机制仅为“s e l f - - c l o c k i n g ”。1 9 8 8 年v a nj a c o b s o n 在文献 2 】中指出了t c p 控制方面的不足，并提出的动态调节窗口大小的 拥塞控制算法，使得互联网的拥塞崩溃( c o n g e s t i o n c o l l a p s e ) 镊到有效的控制。这使人们 普遍意识到，捌塞控制算法对提高互联网的性能的重要性。此后，针对t c p 的拥塞控制进 行的大量研究工作以及由此形成的一些t c p 的实现版本，如t c p t a h o e 、t c p r e n o 和t c p v e g a s ，其中最具代表性的是后2 个版本。不同的t c p 版本允许用户用不同的指标测量估 计拥塞程度，r e n o 及其修改版用丢包率( l o s sp r o b a b i l i t y ) ，而v e g a s 用排队时延( q u e u e i n g d e l a y ) 。但是，在用户能够推测出网络拥塞之前，高丢失或高延迟等坏事件已经发生。这 也是目前互联网不能为用户提供q o s 保证的原因之一。为此，r e d ( r a n d o me a r l y d e t e c t i o n ) 方案被提出。r e d 算法允许路由器向用户通报网络中出现的早期拥塞，使得用 户能够基于来自路由器的反馈信息去适应网络拥塞。i p 层的拥塞控制在路由器中采用a q m ( a c t i v eq u e u em a n a g e m e n t ) 方案来实现，目前r e d ( 随机早期检测) 算法是r f c 2 3 0 9 推荐的a q m 难一候选算法。a q m 算法的参数的选择根据网络的当前状态而定，并在低丢 失率和高利用率这些要求中进行折衷。 我们把拥塞控制作为业务流竞争的共享网络资源的分布算法，即网络上每个结点只是 在它知道的局部信息的基础上来处理本地业务流。算法由两部分组成：基于聚合( a g g r e g a t e ) 的价格( q ) 调整速率( x ) 的信源算法和基于聚合的速率( y ) 调整价格( p ) 的链路算法 ( 这里的价格p 即为路由器中的丢包率) 。如图2 1 所示( 其中r 表示路由矩阵，r 是r 的转置) 。t c p 实现信源算法，a q m 方案实现链路算法。任何t c p a q m 协议都可以看作 是解决i n t e m e t 上聚合效用函数最大化问题的分布式的原始算法或其对偶算法f 3 1 。通常，由 t c p 算法来定义用户的效用函数。 ( ，) = r 。+ 一( 卜f 。7 ) ( 2 一1 ) 础) = r 。+ p r1 - - t r i b ) ( 2 - 2 ) f 1 ， 月”2 1 0 ，否贝j 每个信源i 的传输速率为x ，( f ) ，每个路由器r 的传输速率为y r 0 ) ，r f l 7 是从信源i 到 9 查重唑旦查兰堡主塑壅圭兰垡堡苎笺三雯堡型! 旦坚塑堡坌塑 路由器r 的前向传输时延，l j 是信源i 的数据包经过的路由器的集合，每个路由器的丢包 率为p ，( t ) ，信源i 的丢包率为q i ( t ) ，f 。6 是返回路径上的后向传输时延。当网络达到平衡状 态时，每个信源i 的发送速率为确定值x ，则信源i 的效用函数为u ，( x ，) ，拥塞控制的目 的就是达到全局聚合效用函数最大化，即”赂c u ，( 一) 。 s o u r c e c o n t r o l 图2 1 一般的流量控制结构 2 2t c p 拥塞控制机制 l i n k c o n t r o i t c p 的拥塞控制采用的是基于窗口的端到端的闭环控制方式。目的结点正确地接收到 包后将向信源发出确认( a c k ) 信息。每个信源有一个大小可变的窗口，使用窗口大小来 确定还没有收到确认信息的包的数量。当窗口已满，信源在发送一个新包前必须等待个 确认信息。t c p 算法有两个重要特征：一个是“自定时”特征，当网络出现拥塞且确认信 息出现延迟时自动放慢信源的发送速率：另一个是使用窗口大小来控制信源速率，大约每 个往返时间发送一个窗口的数据包。t c p 拥塞控制由慢启动( s l o ws t a r t ) 、拥塞避免 ( c o n g e s t i o na v o i d a n c e ) 、快速重传( f a s tr e t r a n s m r ) 和快速恢复( f a s tr e c o v e r y ) 四个核心 部分组成。t c p 使用的是加式增加积式减少( a i m d ) 的基于窗口的端到端的拥塞控制机 制，即如果一个数据包丢失，发送窗口就要减半；否则就简单的增加一个数据包的发送量。 大量的实践证明，这种拥塞控制机制对i n t e r n e t 上大批量文件传输等尽力型( b e s t - e f f e c t ) 服务具有较好的适应性。t c p 拥塞控是通过控制一些重要参数的改变来实现的，t c p 用于 拥塞控制的参数主要有： ( 1 ) 拥塞窗口( c w n d ) ：拥寨控制的关键参数，它描述源端在拥塞控制情况下次最 多能发送数据包的数量。 ( 2 ) 通告窗口( a w i n ) ：接收端给源端预设的发送窗口大小，它只在t c p 连接建立的 1 0 查室些皇盔兰堡主堕塞生兰垡垒兰 蔓= 里：! ! ! 竺旦坚塑坚坌塑 初始阶段超作用。 ( 3 ) 发送窗口( w i n ) ：源端每次实际发送数据的窗口大小。 ( 4 ) 慢启动闽值( s s t h r e s h ) ：拥塞控制中慢启动阶段和拥塞避免阶段的分界点，初始 值通常设为6 5 5 3 5 b y t e s 例 ( 5 ) 往返时间( r t f ) ：一个t c p 数据包从源端发送到接收端，源端收到接收端确认 的时间问隔。 ( 6 ) 超时重传计数器( r 1 1 0 ) ：描述数据包从发送到失败的时阳j 间隔，是判断数据包 丢失与否、网络是否拥塞的重要参数。通常设为2 r t t 或5 r t t 。 ( 7 ) 快速重传阈值( t c p r e x m t t h r e s h ) ：能触发快速重传的源端收到重复确认a c k 的 个数，当源端收到重复的a c k 的个数超过t c p r e x m t t h r e s h 时，网络进入快速重传阶段。 t c p r e x m t t h r e s h 的缺省值为3 。 2 3t c p 拥塞控制实现算法 2 3 1t c pt h h o e 没有拥塞控制的t c p 在启动一个连接时，会向网络中发送许多数据包，由于一些路由 器必须对数据包排队，所以这样就有可能耗尽存储空间，从而导致t c p 连接的吞吐量急剧 下降，避免这种情况发生的算法就是慢启动。1 址o e 【6 】算法在新的t c p 连接开始建立时， 将捌塞窗口( c w n d ) 初始化为1 个数据包大小，信源按拥塞窗口的大小来发送数据包。信 源每收到一个a c k 确认，就把它的拥塞窗口值增加1 ，即信源增加一个数据包的发送量。 这样，拥塞窗口会随着往返时间( r t t ) 成倍( 呈指数级) 的增加；1 个、2 个、4 个、8 个。这个过程就叫叫慢启动。慢启动阶段信源向网络发送的数据将急剧增加，当发现 超时或收到3 个相同的a c k 确认时，网络即发生拥塞( t c p 这一假设是基于由传输引起 的数据包损坏和丢失的概率很小( 小于l ) 1 2 ) ，此时就进入了拥塞避免阶段。如图2 - - 2 所示，慢启动闽值( s s t h r e s h ) 被设为当前拥塞窗口值的一半；如果是超时，捐j 塞窗口还要 被黄为1 。如果此时的拥塞窗口值不大于阈值，t c p 就重新进入慢启动过程；如果拥塞窗 口值大于