（计算机软件与理论专业论文）网络qos控制中的网络预测和分组标记算法研究.pdf

摘要 随着i n t e r n e t 的不断发展并深入到社会生活的各个角落，对用 户来说，希望网络能提供更优质、有保障的服务；而对网络运营商来 说，希望能够优化网络资源的使用，使网络具有更好的可控和可管理 性。因此，网络的q o s 控制研究引起了广大的研究者的重视，而实现 o o s 控制也成了下一代i n t e r n e t 的重要特征之一。网络预测和区分 服务中的分组标记算法是网络q o s 控制体系中的重要研究点，同时也 是本文的核心内容。 本文首先对网络流量测量中相关参数s c v 和分组数的预测模型迸 行了研究，通过理论分析和模拟实验得出了s c v 和分组数的预测模型 中相关参数结果，从而对于在网络流量测量中真正应用该模型提供了 重要依据。 随后，研究了针对小时间粒度的网络流量自相似特性，并提出了 网络流量自回归预测模型，通过理论分析和模拟实验得出了预测模型 中相关参数结果，对于在网络流量预测中真正应用该模型提供了重要 依据。 最后，研究了区分服务体系结构下分组标记算法，重点分析了标 记算法在公平性方面的表现，并且针对同一个聚集流中可能包含不同 类型的单个流的情况( 比如存在自适应t c p 流和非适应u d p 流、不同 速率的多媒体u d p 流、采用不同t c p 协议的数据流、不同分组大小的 数据流) ，提出了一种基于聚集流内部公平性的标记算法f a t m 。大 量模拟实验结果表明，标记算法f a t m 在保持聚集流之间的公平性和 网络吞吐量的基础上，提高了聚集流内部单个流之间的公平性。 关键词：网络服务质量，网络预测，区分服务网络，分组标记， 公平性 a bs t r a c t w i t ht h e d e v e l o p i n g o fi n t e r n e t ，t h e r eh a sb e e na ni n c r e a s i n g d e m a n df o ri n t e r n e tt os u p p o r tq o sc o n t r o lt om e e tv a r i o u ss e r v i c e r e q u i r e m e n t sf r o md i f f e r e n tn e t w o r k i n ga p p l i c a t i o n sa n dt ob e r e ru t i l i z e n e t w o r k i n gr e s o u r c e s o no n eh a n d ，e n du s e r sw a n t t og e tq o sg u a r a n t e e w h e nt h e yu s ei n t e r n e t ；o nt h eo t h e rh a n d ，t h ei s p sw a n tt oo p t i m i z et h e u s i n go fn e t w o r kr e s o u r c e s ，a n d h a v eam o r e c o n t r o l l a b l e ，m o r e m a n a g e a b l e i n t e m e t u n d e rt h i s b a c k g r o u n d ，n e t w o r kq o s c o n t r o l a t t r a c t sl o t so fr e s e a r c h e r s n e t w o r kp r e d i c t i o na n dp a c k e tm a r k i n g a l g o r i t h mi nd i f f s e r va r et h em o s ti m p o r t a n tr e s e a r c hp o i n t so fq o s c o n t r o ls y s t e m ，w h i c ha r ed i s c u s s e di nt h i sd i s s e r t a t i o ni nd e t a i l 。 f i r s t l y ，t h i sp a p e ra n a l y z e st h ea u t o - r e g r e s s i v ep r e d i c t i o nm o d e lw i t h t h et w op a r a m e t e r ss c v ( t h es q u a r e dc o e f f i c i e n to fv a r i a t i o no fp a c k e t s i z ed i s t r i b u t i o n ) a n dp a c k e tn u m b e ro fas a m p l i n gb l o c ki nd e t a i l u s i n gt h e o r ya n a l y s i sa n ds i m u l a t i o n ，w eg e tt h e r e l a t i v ep a r a m e t e r s v a l u ei nt h ep r e d i c t i o nm o d e l ，w h i c hi si m p o r t a n ti nt r a f f i cm e a s u r e m e n t m o r e o v e r , w es t u d yt h es e l f - s i m i l a r i t yo ft r a f f i cl o a di ns m a l lt i m e g r a n u l a r i t ya n dp r o p o s ea na u t or e g r e s s i v ep r e d i c t i o nm o d e l w eg e tt h e r e l a t i v ep a r a m e t e rv a l u ei nt h ep r e d i c t i o nm o d e lb yu s i n gs i m u l a t i o n ， w h i c hi sv e r yi m p o r t a n ti nr e a lt r a f f i cp r e d i c t i o n f i n a l l y , w ea n a l y z et h ef a i m e s sp e r f o r m a n c ei nm a r k i n ga l g o r i t h m si n d i f f s e r v n e t w o r k c o n s i d e r i n g r e a l a g g r e g a t i o n t r a f f i c p o s s i b l y c o m p r i s e sd i f f e r e n tt y p et r a f f i c ( s u c ha sa d a p t i v et c pa n dn o n a d a p t i v e u d pt r a f f i c ，u d pf l o w sw i t hd i f f e r e n tr a t e s ，t c pt r a f f i cw i t hd i f f e r e n t t c pp r o t o c o l ，d a t at r a f f i cw i t hd i f f e r e n tp a c k e ts i z e ) ，w ep r o p o s eaf a i r a g g r e g a t et r a f f i cm a r k e r ( f a t m ) b a s e do nf a i r n e s sa m o n gt h ei n d i v i d u a l f l o w sw i t h i na na g g r e g a t i o n s i m u l a t i o nr e s u l t ss h o wt h a to u rm a r k i n g a l g o r i t h mc a ni m p r o v et h ef a i m e s sa m o n gt h ei n d i v i d u a lf l o w sw i t h i na l l a g g r e g a t i o n ，w h i l ek e e p i n gt h ef a i r n e s sa m o n gt h ea g g r e g a t et r a f f i cf l o w s a n dt o t a ln e t w o r kt h r o u g h p u t k e yw o r d s ：q o s ，p r e d i c t i o n ，d i f f s e r v , p a c k e tm a r k i n g ，f a i r n e s s 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名；料日期：扯年 月尹日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：二馘导师签名陋日期：丛年三月垃日 亟堂位论塞 簋二童绪迨 第一章绪论 1 1q o s 概述 自从计算机系统诞生开始，就一直存在提高系统的服务性能和服务质量的问 题，因此，q o s 问题实际上由来已久。 早在2 0 世纪8 0 年代初期，s e i t z 和w o r t e n d y k e 等人在研究a p p a n e t 中的 x 2 5 通信时已提出基于用户的性能评价问题，这也许是关于计算机网络q o s 研 究的最早文献1 2j 。在早期的o s i 协议制定中，也为服务质量的一些参数留有相应 的表示手段，但一直空缺未用p 】。很长的一段时间，由于计算机网络的性能所限， 人们对q o s 的关注只停留在数据流传输中的正确率、吞吐量和延迟等单一服务 质量的评价和控制上【4 】。直到2 0 世纪8 0 年代末期，随着b i s d n 技术以及a t m 交换网的出现和分稚式多媒体应用的急剧增加，人们爿开始系统地对q o s 管理 和控制进行较为深入的研究。一些实验性系统也应运而生，代表性的有英国兰开 斯特大学的q o s a 工程1 5j 、美国哥伦比亚大学的扩展的集成化参考模型( x r m ) 系统【6 1 、国际合作项目t i n a c 工程1 7 1 、美国加州伯克利大学的t e n e t 工程【8 】 和i b m 黑森伯格欧洲网络中心的h e i p r o j e c t 工程1 9 i ，等等。 随着i n t e r n e t 的不断发展并深入到社会生活的各个角落，对用户来说，希望 网络能提供更优质、有保障的服务；而对网络运营商来说，希望能够优化网络资 源的使用，使网络具有更好的可控和可管理性。因此，网络的q o s 控制研究引 起了广大的研究者的重视，而实现q o s 控制也成了下一代i n t e r n e t 的重要特征之 一o i n t e m e t 工程任务组( i n t e m e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 于1 9 9 7 年9 月 开始制定了有关网络q o s 定义与服务的一系列r f c 标准，典型的工作是提出了 两种不同的i n t e m e tq o s 控制模型：集成服务( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) i l “j 和区分服务( d i f f e r e n t i a t e ds e r v i c e s ，d i f f s e r v ) 1 1 2 1 3 。 1 2 集成服务和区分服务 1 2 1 集成服务( 1n t s e r v ) i n t s e r v 服务模型在i e t fr f c l 6 3 3 中进行了定义。r f c l 6 3 3 将资源预留协议 r s v p 1 4 】作为i n t s e r v 结构中的主要信令协议。其基本思想就在于以资源预留的方 式来实现q o s 保障，r s v p 是其核心部分。r s v p 是主机用来从应用程序获得特 亟堂位丝窑箍二重绪迨 定的q o s 的一种控制协议，完成综合服务需要定义的呼叫接纳控制功能和资源 预留功能。端点应用程序利用r s v p 消息向网络提出完成数据传送必须保留的网 络资源( 如带宽及缓冲区大小等) ，同时也确定沿传送路径的各个节点传输处理 策略，从而对每个业务流实现逐个控制。 在服务层次上，i n t s e r v r s v p 提供了3 种级别的业务： 端到端的质量保证型服务( g u n t e e ds e r v i c e ) ：保证带宽、限制延迟和无 丢包。 可控负载型服务( c o n t r o l l e d - - l o a ds e r v i c e ) ：类似于在当前的一个负载较 轻网络中实现的尽力而为业务的服务质量。 尽力而为的服务( b e s te f f o r ts e r v i c e ) ：类似当前i n t e m e t 在提供的尽力而 为的服务。 在结构层次上，i n t s e r v r s v p 服务模型主要由四个部分构成：资源预留协议 r s v p ，接纳控制器( a d m i s s i o nc o n t r o lr o u t i n e s ) ，分类器( c l a s s i f i e r ) 以及分组 调度器( p a c k e ts c h e d u l e r ) 。 在实现层次上，集成服务需要所有路由器在控制路径上处理每个流的信令消 息并维护每个流的路径状态和资源预留状态，在数据路径上执行流的分类、调度 和缓冲区管理。具体而言，资源预留协议r s v p 负责逐跳地建立或者拆除每个流 的资源预留软状态，也即建立或拆除数据传输路径；接纳控制器将决定是否接受 一个资源预留请求，其根据是链路和网络节点的资源使用情况以及q o s 请求的 具体要求；分类器则对传输的数据分组进行分类成传输流，i n t s e r v 常用的分类 器是多域( m u l t i f i e l d ，m f ) 分类器，当路由器接收到数据分组时，它根据数据 分组头部的多个域( 如5 元组：源i p 地址，目的i p 地址，源端口号，目的端口 号，传输协议) ，将数据分组放入相应的队列中；调度器则根据不同的策略对各 个队列中的数据分组进行调度转发。 使用r s v p 信令建立数据发送路径以及为业务流预留资源的过程如下： 如图1 一l 中所示，发送端向接收端发送一个包含业务流规格况明( t s p e c ) 的p a t h 消息，其中包含了业务流标识( 即目的地址) 及其业务特征，包括所需要 的带宽的上下限，延迟以及延迟抖动等。 如图1 一l 中、所示，该消息由沿路径的路由器逐跳传送，并且每个路由 器都被告知准备预留资源，从而建立一个”路径状态”，该状态信息包含p a t h 消 息中的前一跳源地址。 如图1 - 1 中所示，接收方收到此消息后从业务特征和所要求的q o s 计算 出所需要的资源，向其上游节点发送一个资源预留请求r e s v 消息，该消息中包 含了t s p e c 、r s p e c 以及f i l t e rs p e c ，其主要包含的参数就是要求预留的带宽。 2 亟主堂僮迨塞 簋二童绪论 如图l 一1 中所示，r e s v 是沿p a t h 的发送路径原路返回的，沿途的路由 器收到r e s v 消息后，调用自己的接入控制程序以决定是否接受该业务流，如果 接受，则按要求为业务流分配带宽和缓存空间，并记录该流状态信息，然后将 r e s v 消息继续向上游转发；如果拒绝，则向接收端返回一个错误信息给接收端 以终止呼叫。 如图1 一l 中所示，当最后的路由器收到r e s v 消息并且接受该请求时，它 向接收端发回个确认消息。 图l - ir s v p 建立传输路径以及预留资源的过程 在此过程中，可以看到，和电信网络中的呼叫建立过程相反，r s v p 是由接 收端驱动的资源预留。当通信结束或者一方退出会话后预留的资源可以由超时机 制释放。r s v p 还定义了显式的释放机制，通过p a t h t e a r 由启动点沿下游方向传 送至接收端，通知沿途各路由器释放资源。r e s v t e a r 则反向传送，功能相似。它 们可由端系统发出，也可由路由器在状态超时时发送出。至此，业务流的传输路 径已经建立起来了，数据流可以进行发送了。 从理论上讲i n t s e r v r s v p 模型完全可以保证为i p 网络提供q o s 保障。但随 后在些网络上的实验表明这种服务模型有很明显的局限性，这些问题主要表现 在i n t s e r v 服务模型存在严重的可扩展性问题，因为它要求核心路由器必须保持 经过它的每一个单个数据流的状态，这将给核心路由器带来极大的负担。 另外，在i n t s e r v 模型中，对路由器的要求过高，网络中所有的路由器都必 须支持r s v p 信令协议，接纳控制器，分类器以及调度器。 r s v p 中引入每流状态( p e r f l o ws t a t e ) 的概念，对于数据通信和实时应用 亟堂位控塞 箍= 重绪诠 通信而言，i p 网络同时扮演了面向无连接和面向连接网络的两个不同角色，提 供两种功能，这与其简化设计原则相抵触。 因此，要实现i n t s e r v 的q o s 保证是很困难的，它需要基于流的、复杂的资 源预留、接纳控制、q o s 路由和调度机制。在诸如互联网这种复杂的、大规模的 网络中，链路状态是不确定的，有效地预留带宽资源非常困难。而且资源预留本 身就与i p 网络的最大特点“无连接”相冲突。更重要地问题就是i n t s e r v 面临地 可扩展性问题和健壮性问题，这主要是因为在分布式网络环境中，很难维持动态 的、可复制的传输流状态一致性。 早期的i n t s e r v 是面向单流的，在路由器配置和使用多域分类准则，这给路 由器尤其是主干网络核心路由器带来了巨大负荷。为了增加i n t s e r v 的扩展性， 近期r s v p 已经开始支持流聚集，即将沿相同业务流传输路径流聚合成宏流 ( m a c r o f l o w ) ，按宏流来预留资源。这虽然减轻了核心路由器的一些负担，但 i n t s e r v 本身的体系结构已经决定了其高复杂性，而且由于路径数是边界节点数 的平方，宏流数仍然很庞大。 1 2 2 区分服务( d i f f s e r v ) 针对i n t s e r v 中的不足，i e t f 又提出了一种新的q o s 控制模型，即d i f f s e r v 。 d i f f s e r v 的最大特点就是简单有效、扩展性强。其实施特点是采用聚合的机 制将具有相同特性的若干业务流聚合起来，为整个聚合流提供服务，而不再面向 单个业务流。也就是说在d i f f s e r v 网络边界路由器上保持每流状态，核心路由器 只负责数据分组的转发而不保持状态信息。其基本实现方法是： 简化网络内部节点的服务机制。在网络内部的核心路由器中只保存简单的 d s c p ( d i f f s e r vc o d e p o i n t ) 与p h b ( p e r h o bb e h a v i o r ) 的对应机制，在数据流 进入核心路由器时只根据数据包头部d s ( d i f f e r e n t i a t e ds e r v i c e s ) 域中的d s c p 进行转发，而业务流状态信息的保存与流监控机制的实现等都在网络边界节点进 行，内部节点是状态无关的。 聚合网络内部核心路由器的服务对象。采用流聚集的方式进行传输控制，具 有相同d s c p 的业务流组成一个宏流( m a c r o f l o w ) ，核心路由器的服务对象即 是宏流而不是单流( m i c r o f l o w ) ，单流信息只在网络边界节点保存和处理。 实际上，按照d s 域的标记，以相应方式提供不同质量的数据包转发服务， 也正是区分服务名字的由来。美国正在开展的下一代互联网计划i n t e r n e t 2 便是 选择d i f f s e r v 作为其q o s 实现策略。 虽然d i f f s e r v 仍在不断的发展，一些标准仍在制定、完善之中，但经过几年 的发展，d i f f s e r v 的相关概念及模型已经比较成熟了，d i f f s e r v 体系结构也已经 亟堂僮途室 簋二童缮监 比较明确了。在此基础上，与服务提供有关的问题，如d s c p 的定义、p h b 服 务的定义等等已逐步完善。 区分服务体系结构如图1 - 2 所示，其中的d i f l s e r v 区域是由一些相连的 d i f f s e r v 节点构成的集合，它们有统一的服务提供策略，且实现一致的p h b 组， 比如某个i s p 的网络或者内部网。每个d s 区域通过边界节点( b o u n d a r y n o d e ) 与非d s 区域相连，根据不同的数据流传输方向，边界节点可以分为入口节点和 出口节点。 图卜2区分服务体系结构示意图 为了保证用户能从i s p 那里获得所需要的服务质量，用户必须和i s p 之间签 订有服务等级协定( s e r v i c el e v e la g r e e m e n t ，s l a ) ，而i s p 之间也必须建立业 务流调节协定( t r a 硒cc o n d i t i o na g r e e m e m ，t c a ) ，s l a 规范了i s p 对客户端 网络所支持的业务类别以及每种类别的业务流数量，t c a 则规范了i s p 之间的 数据流应该满足的一些约定。 这样，当有数据流进入d s 区域时，入1 1 1 节点对其进行分类( c l a s s i f i e r ) ， 调节( c o n d i t i o n ) ，保存流( 单流或聚流) 的状态信息，根据事先和用户约定的 流规格对流进行计量( m e t e r i n g ) ，标记( m a r k i n g ) ，整形( s h a r p i n g ) ，丢弃 ( d r o p p i n g ) 等，以使输入流符合s l a ，同时在包头标记d s c p 值，并将其加入 相应的行为聚集b a ( b e h a v i o ra g g r e g a t e ) 。出口节点也可能需要对输出流进行 调节，以保证其与下游d s 区域的t c a 相符。 d i f f s e r v 区( r e g i o n ) 则是由连续的d s 区域构成。一个d s 区内的d s 区域 可以支持不同的p h b 组，并且各自区域的d s c p 到p h b 的映射函数也可能不相 同。在不同的d s 区域之间，必须对s l a 和t c a 进行调节，以协调彼此之间的 亟堂焦诠窑簋二童绪论 服务语义。这样，通过在上游d s 区域和下游d s 区域之间建立s l a 或t c a ， 区分服务可以扩展到多个d s 区域。 在图1 2 中，假设客户端网络已经和i s p 建立了相应的s l a ，i s p 之间也建 立了t c a 。如果客户端网络中的主机a 向另一客户端网络的主机b 发送数据流， 则数据包在客户端网络中路由到达与它直接相连的i s p 的网络n i ，边界路由器 e l 根据用户与i s p 之间的s l a 通过查看数据包的头部信息对它进行分类、监控、 标记以及整形，以使它符合s l a 。被标记了d s c p 的数据包在n 1 中传输，直到 到达n 1 的出口节点。在n i 的出口节点，边界路由器根据n 1 与n 2 之间的t c a 对业务流进行整形，使它符合n 1 与n 2 网络之间的t c a 。业务流依次通过中间 的每个i s p ，最后到达接收端所在的客户端网络。 与i n t s e r v 类似，d i f f - s e r v 也定义了三种服务类型： 尽力而为的服务：类似于目前i n t e r n e t 上尽力而为的服务。 奖赏服务( p r e m i u ms e r v i c e s ，p s ) ：为用户提供低延迟、低抖动、低丢包 率和保证带宽的端到端或者网络边界到边界的传输服务。p s 是目前区分服务模 型中定义的级别最高的服务种类。这种”三低一保证”的服务类似于传统运营商网 络的专线业务，因此也称为”虚拟专线”服务。 确保服务( a s s u r e ds e r v i c e s ，a s ) ：确保服务是从统计上保证用户的带宽， 其初衷是在网络拥塞的情况下，也能保证用户有一定量的预约带宽。a s 的着眼 点是带宽和丢包率，而不太注重延迟和抖动。a s 最具吸引力的是其实现机制较 为简单，只要采用简单的标记和丢弃机制就能实现i pq o s 。在发生拥塞时，确 保服务通过控制丢包优先级，提供了比“尽力而为”服务更好的服务。确保服务 的基本思路是：边界路由器对进入d s 域的数据包进行标记，预约带宽内的包标 为1 n ( i np r o f i l e ) ，否则标为o u t ( o u tp r o f i l e ) 。发生拥塞时，核心路由器根 据包头的标记决定丢包概率，o u t 包的丢弃概率大于1 1 1 包。从而在统计意义上上 保证用户的预约带宽。 区分服务虽然在可扩展性方面较i n t s e r v 大大提高，但在q o s 的保证上却有 所下降。由于在最初的d i f f s e r v 模型中没有考虑接纳控制机制的引入，对不同类 别的聚集流只提供相对优先级的q o s 保证，因此很难绝对保证聚集流或每个微 流的q o s 。由于没有接纳控制的存在，当过多的流量进入网络后，甚至会导致网 络中所有的流的q o s 都降级。在r f c 2 6 3 8 中，提出了d i f f s e r v 下基于带宽代理 ( b a n d w i d t hb r o k e r ，b b ) 的体系结构，但是b b 的引入又带来了可扩展性问题 等。所以在d i f f s e r v 中建立一套合理的接纳控制机制以提高d i f f s e r v 对q o s 保 证的能力是非常必要的。 6 亟鲎僮途塞簋二童缮诠 1 3q o s 控制技术 事实上，网络q o s 控制的本质在于资源的管理。因此，在确定了q o s 控制 模型后，关键的工作就是：一方面可以通过预测模型对网络资源实施有效的预测， 动态获取网络资源状况；另一方面，可以通过分组标记算法对网络资源实施有效 的分配和控制，或通过队列调度、队列管理、接纳控制以及q o s 路由技术平衡 网络负载。 目前，在国际上和国内都有许多的研究者在系统地开展网络q o s 控制方面 的研究，其中主要研究集中在q o s 控制模型、网络q o s 控制的关键技术，如网 络资源预测、区分服务分组标记算法、队列调度、队列管理、接纳控制以及q o s 路由等。 1 3 1 队列调度 队列调度算法是保证网络q o s 的关键技术之一，其主要功能是通过调度策 略来实现网络资源的分配，从而对预留带宽或延时进行较为严格的保证。在 i n t s e r v 及类似模型中，与接纳控制配合实现严格的q o s 保证。 根据不同的服务规则，队列调度算法可以分为先来先服务( f c f s ) 、轮循 调度( r r ) 、处理机共享( g p s ) 和随机服务等。根据调度算法的调度目标， 又可分为基于速率的和基于延时的这两类。根据调度算法的工作状态，又可以分 为持续工作( w o r k i n g c o n s e r v i n g ) 算法和非持续工作算法 ( n o n w o r k i n g c o n s e r v i n g ) 。其中持续工作算法表示只要系统中有等待分组，调度 算法就一定会工作；而非持续工作算法则意味着即使系统中有等待分组，调度算 法也可能暂时不对其进行调度，这类调度算法一般要求在输入业务流被调度之前 需经过一个整形器进行整形处理。持续算法具有更高的链路利用率，而非持续算 法能对端到端延时抖动进行很好的控制。 队列调度算法性能的好坏主要涉及到延时性能、公平性和复杂性等几个方 而。队列调度算法可能在不同环境中有不同的应用。例如，队列调度算法可能被 用于隔离恶意业务流来为正常业务流提供服务质最保证；队列调度算法还可能用 来让用户平等地共享链路的可用带宽；或者用来实现分级的链路共享等。实际上， 有效的队列调度算法应该拥有诸多好的特性。 1 3 2 主动队列管理 在分组传输过程中，其流经的网络传输节点通常采用队列缓存、延迟转发的 服务方式以提高输出链路的带宽利用率。主动队列管理机制在分组到达队列前端 亟堂位逾塞 蓥二重绪途 时依据一定的策略和信息决定是否允许该分组进入缓冲队列，从另一个角度看， 也就是做出是否丢弃该分组的决策。主动队列管理在网络传输控制中发挥着相当 大的作用，是网络q o s 控制的核心技术之一，也是实现网络拥塞控制的重要手 段。 就单个网络传输节点而言，其控制目标在于解决输出链路的带宽资源分配问 题，把有限的资源公平而有效地分配给不同的服务类别( 或用户流) 。而在众多 网络传输节点构成传输网的基础上，网络传输控制需要整合、规划所有的网络带 宽资源的使用，为用户提供端到端的有服务质量保障的网络传输服务，这也就是 q o s 控制的目标。主动队列管理直接涉及到的是节点中的队列缓冲资源，直接影 响到的也只是分组丢失率性能，然而其对系统带宽分配的性能有着不可忽视的影 响。合理的系统队列缓冲容量，对于平衡系统吞吐量和分组排队延迟起着至关重 要的作用。如何解决网络带宽资源的有效、公平分配问题是主动队列管理机制设 计的关键。 1 3 3 接纳控制 接纳控制作为一种预防性的流量控制手段是实现网络q o s 保障的重要手段， 实施连接接纳控制的网络，要求用户在请求接入网络时将自己的通信量传输特征 和要求的服务质量告诉网络，网络根据用户的通信量特征和网络现存的资源情 况，决定是否接纳用户的连接请求。 在过去的研究中，提出了许多的接纳控制算法，主要可以分为如下几类。 ( 1 ) 基于测量的接纳控制机制 一般来说，基于测量的接纳控制主要包括两个组成部分，一是测量单元，另 一部分是接纳控制决策单元。测量单元根据不同的测量策略动态测量网络运行状 态并将测量得到的信息提供给接纳控制决策单元；接纳控制决策单元则根据来自 测量单元的测量信息以及预先定义好的一些接纳控制准则做出接纳控制决策。 ( 2 ) 基于端到端探测的接纳控制机制 基于端到端探测的接纳控制机制最本质的特征就是依靠端到端的探测包的 发送来决定目前的网络中是否有足够的资源来满足一个新的通信流的q o s 请求。 ( 3 ) 基于带宽代理的接纳控制机制 基于带宽代理的接纳控制的基本思想是通过一个集中控制的带宽代理来保 持整个网络的状态信息，并在网络状态发生变化时进行实时更新，当一个流到达 需要进行接纳控制时，都要访问带宽代理，根据带宽代理保持的网络状态信息来 做出接纳决策。 亟堂位逾塞簋= 童绪论 1 3 4 网络预测 实现网络o o s 控制需要及时了解网络当前的运行状况，以便及时采取相应的 措施，这就需要进行网络流量测量。因此网络流量测量是实施有效的q o s 控制的 基础。由于网络的实时性非常强，在网络中进行测量就必须考虑测量所带来的代 价，确保测量工作不会给网络的实时性能带来太大的损害。因此，进行网络测量 需要着重考虑的一个问题就是可扩展性。当前，为了提高网络测量的可扩展性的 一个重要措施就是使用分组采样技术。而根据文献 1 5 ，网络流量估计所需的最 小采样数跟分组大小分布的方差平方系数( s c v ) 成正比，流量估计中的相关参数 ( s c v 和总的分组数m ) 是可以由自回归模型来预测的，其预测值影响了网络流 量估计的准确性。基于这些预测值，可以确定采样概率，从而估计网络流量。 随着计算机网络的迅速发展，目前的网络规模极为庞大和复杂，因此发生各 种问题的可能性也越大，同时管理网络的难度也增大。传统的网络管理是在告警 之后，解决潜在的问题，即为一种响应式的行为，这时候网络服务很可能已经受 到影响。而如果在网络o o s 管理和流量工程中，能够根据实际采集的网络流量观 测值序列，建立该流量参数的正常行为，然后平稳化该序列，建立网络流量预测 模型，对网络流量进行预测，并检测在将来超越阈值的可能性和发生时问。这样， 在网络过载发生之前，可以预先采取防范措施，来保证网络的正常服务。这种方 法改变了以往的网络管理响应方式，使得网络过载的预警成为可能。所以研究 较好的网络流量预测模型，并分析其性能，以及研究网络流量预测的实际应用， 就显得尤为重要。 1 3 5 分组标记算法 在现今异构网络i n t e m e t ，区分服务体系结构通过对不同应用和不同要求的数 据流部署不同等级的服务，以提供较大粒度的服务质量q o s 保证。不同流之间的 公平性问题是区分服务中的研究热点，而标记策略是提高公平性的有效方法。在 近些年分组标记算法是一个很热门的研究课题。标记算法的核心就是：首先测量 聚集流跟服务规格s l a 是否一致，低于服务规格的聚集流分组将会被标记成低丢 弃优先级，在核心将会受到高等级的服务；高于服务规格的聚集流分组将会被标 记成高丢弃优先级，在核心将会受到低等级的服务。基于测量聚集流跟服务规格 是否一致的机制，可以将标记算法分为两大类：基于令牌桶标记器和基于平均速 率估计的标记器。目前许多标记算法只考虑了聚集流之间的公平性，而忽略了聚 集流内部流之间的公平性。如果标记算法能够在保持聚集流之间的公平性和网络 吞吐量的基础上，提高聚集流内部单个流之间的公平性，那么将有效提高整个 q o s l 拘保证。 亟堂僮迨塞 筮二童绪i 佥 网络预测和区分服务中的分组标记算法是网络q o s 控制体系中的重要研究 点，同时也是本文的核心内容。 1 4 论文的组织 网络预测和区分服务中的分组标记算法是网络q o s 控制体系中的重要研究 点，同时也是本文的核心内容。具体来况，本文的内容安排如下： 第一章绪论；这一章主要介绍网络服务质量( q o s ) 的产生和重要性、集成 服务和区分服务体系结构，以及q o s 控制相关技术。网络预测和分组标记算法 是我们的研究重点。 第二章网络流量测量中相关参数的预测；主要对网络流量测量中相关参数 s c v 和分组数的预测模型进行了研究，通过理论分析和模拟实验得出了s c v 和 分组数的预测模型中相关参数结果，从而对于在网络流量测量中真正应用该模型 提供了重要依据。 第三章网络流量预测；主要重点研究了针对小时间粒度的网络流量自相似 特性，并提出了网络流量自回归预测模型，通过理论分析和模拟实验得出了预测 模型中相关参数结果，对于在网络流量预测中真正应用该模型提供了重要依据。 第四章区分服务中分组标记算法；主要研究了区分服务体系结构下分组标 记算法的历史以及发展现状，重点分析了标记算法在公平性方面的表现，并且提 出了种f a t m 标记算法，旨在保持聚集流之间的公平性和网络吞吐量的基础 上，提高聚集流内部单个流之间的公平性。 第五章结束语；对所做的研究与设计工作进行了总结，并阐述了将来进一 步的工作计划。 亟堂位途塞 筮三童圆终速量型量虫担羞叁熬的塑型 第二章网络流量测量中相关参数的预测 2 1 网络流量测量 实现网络q o s 控制需要及时了解网络当前的运行状况，以便及时采取相应 的措施，这就需要进行网络流量测量。因此网络流量测量是实施有效的q o s 控 制的基础。 由于网络的实时性非常强，在网络中进行测量就必须考虑测量所带来的代 价，确保测量工作不会给网络的实时性能带来太大的损害。因此，进行网络测量 需要着重考虑的一个问题就是可扩展性。当前，为了提高网络测量的可扩展性的 一个重要措施就是使用分组采样技术。 i n t e m e t 上数据传输的最小单位就是分组，因此要想获得网络的运行状态， 最好的办法就是对分组进行监控和分析，但是若对所有流经网络的分组都进行监 控和分析，则会带来巨大的处理开销，从而影响到网络转发数据的性能。因此通 过分组采样，依靠部分数据来估计网络的当前运行状态就非常重要了。然而，对 于今天的高速链路，测量流进链路的每个分组，其开销是很巨大的，将i f ：重影响 路由器的性能，耗尽处理资源。 在工程实践领域，目前用得最多的采样方法是“1o u t o f n ”( 从n 中取1 ) ， 这种方法由于实现的简单而在实践领域广为应用，如c i s c o 和j u n i p e r 的路由器， 以及i n m o n 的s f l o w 都采用了“1o u t o f n ”采样。 以流量大小测量为例，“1o u to f n ”采样粗看的确是一种有效的方法。因为， 一般来说，网络的流量变大时，流经网络的分组数也会增多；因此，当网络流量 变大时，在相同时间段内，“1o u to f n ”采样能对更多的分组进行采样：当网络 流量变小时，采样的次数变少，从而依据采样得到的流量估计似乎是合理的。 然而，根据对采样理论的仔细研究发现，为了达到对网络负载的精确估计( 使 得误差率被控制在一个较小的范围内) ，所需的采样次数实际上并不取决于总体 所包含的个体数，而只取决于总体的数字特征( 分组大小的方差与均值的比值) 。 即在一个给定的精度下，若总体是1 0 0 0 0 0 ，采样次数若为1 0 0 0 就可达到给定精 度；那么，在总体的数字特征不变的情况下，总体变为1 0 0 0 0 0 0 ，采样次数仍为 1 0 0 0 就可达到给定精度。因此，采用“1o u to f n ”采样机制的合理性就大受置 疑了。因为，在总体很大时，采用“lo u t o f n ”就会导致采样次数远远大于所需 次数，造成不必要的浪费；而在总体较小时，则采样次数太少，从而严重影响最 后的估计精度。根据文献 1 5 】，网络流量估计所需的最小采样数跟分组大小分布 亟堂位逾塞簋三重圆鳖速量测量虫担苤蓥数的亟i ! ! 1 9 的方差平方系数( s c v ) 成正比。流量估计中的相关参数( s c v 和总的分组数m ) 是 由一个自回归模型来预测的，其影响了网络流量估计的准确性。基于这些预测值， 可以确定采样概率，从而估计网络流量，且采样概率随着网络流量的动态变化而 变化。 两个网络流量参数的定义为： ( 1 ) s c v ( t h es q u a r e dc o e f f i c i e n to fv a r i a t i o no fp a c k e ts i z ed i s t r i b u t i o n ) ：采样 周期分组大小分布的方差平方系数，数学表达试为s = b “) 2 ，其中“和盯分别 为总体均值和分组大小分布的标准差； ( 2 ) 分组数：单个采样周期分组数。 2 2s c v 自回归预测 预测的效率取决于这些参数在时间序列上先后值的相关性。通过对实际的网 络流量进行分析，发现两个连续采样周期中的s c v 是强相关的。 我们使用的实验数据主要来源于美国n l a n r ( n a t i o n a ll a b o r a t o r yf o r a p p l i e dn e t w o r kr e s e a r c h ) 国家实验室在不同地点采集的i p 流量数据( i ph e a d e r t r a c e s ) 1 1 9 1 ，在本文中使用的主要数据见表2 。1 。 表2 - 1 实验数据说明 n a m et r a c ed u r a t i o n s a m p l i n gp e r i o d 几a u c k l a n d i i1 9 9 9 1 2 0 1 1 9 2 5 4 8 02 4 h3 0 0 s 兀2 a u c k l a n d i i1 9 9 9 1 2 0 7 1 2 5 0 1 9 01 6 h3 0 0 s n ， a u c k l a n d i i1 9 9 9 1 1 2 9 1 3 4 2 5 8 01 5 h3 0 0 s 兀。 n z l x 1 1 2 0 0 0 0 7 0 5 1 5 2 9 0 02 5 h3 0 s 兀。 b e l ll a b s - i 2 0 0 2 0 5 1 9 - 1 0 0 0 0 01 h1 0 s 图2 1 ( a ) 描述了a u c k l a n d - i i1 9 9 9 1 2 0 1 1 9 2 5 4 8 - 0 数据源的s c v 的自相关 性，其中s c v ( k ) 为第k 个采样周期的s c v 。 很明显，它们在时间序列上前后两个取值是强相关的，其相关系数非常接近 于1 。实际上，这些值之间有种强的线性关系。在文献 1 6 中，作者分析了对 于一个给定的误差区间，可以预测多少个周期以后的值，通过研究