（通信与信息系统专业论文）面向区分服务的可扩展缓存管理算法研究.pdf

华中科技大学硕士学位论文 = ：= = = = = ：= = = = ：= = = = ；= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 摘要 随着网络应用需求的日益丰富和技术的不断发展，完全依赖传统的终端系统上的 策略与算法是很难满足诸如网络q o s 这样复杂的应用需求，迫切需要网络中的中间设 备参与到实现网络拥塞控制中来。然而目前提出的许多方案都需要路由器保存每个流 的状态信息，破坏了i n t e m e t 赖以成功的基本特性可扩展性。新的研究希望在不 破坏网络可扩展性的前提下，在路由器上提供流保护、带宽公平分配，甚至支持区 分业务。本文正是在这个指导思想下提了新的面向区分服务的可扩展缓存管理算法 部分区分丢弃算法( p a r t i a l d i s t i n c t i v e l y d r o p p i n g ，p d d ) 。 p d d 算法利用了c h o k e 算法对业务流的惩罚力度较大的特点，控制不同优先级 的业务流进入到路由器缓存时，执行部分丢弃的概率，以实现对业务流的区分服务。 当完成部分丢弃比较之后，没有被丢弃的数据包再次根据r e d 算法实施拥塞控制， 利用r e d 算法的优点，控制网络拥塞的发生。 该算法能够较好的实现流的公平性，对发送速率高的流的具有较强的抑制能力， 并能够在一定程度上保护t c p 流。该算法对于不同优先权的流量有着不同的对待方 式，保证优先权高的流量获得更好的服务质量。更重要的是p d d 不需保存任何业务 流信息，实现简单，不会对路由器增加额外的负担，保持了现有印网的可扩展性。 同时，本文扩展了网络仿真平台n s ，添加了新的仿真元素，并在此基础上完成 了对p d d 的仿真试验，结果表明p d d 缓存管理算法可以实现本文的设计目标。在对 整个网络的宏观整体考虑的情况下，采用复杂的小世界网络拓扑结构，p d d 算法同样 能够实现本文的设计目标，具有很好的应用性能。 关键词：i pq o s ，区分服务，可扩展，缓存管理，n s 扩展，小世界网络 i 华中科技大学硕士学位论文 a b s t r a c t w i t hm o r ea n dm o r ea p p l i c a t i o n sd e p l o y i n ga n dt h et e c h n o l o g yd e v e l o p i n go nt h e i m e m e t ，p e o p l ec a n n o to n l yr e l y o nt e r m i n a l s y s t e mt oi n c o r p o r a t ep r o p e rc o n g e s t i o n c o n t r 0 1 r o u t e rm e c h a n i s m sm u s tb ep a r t i c i p a t e di n t op r o t e c t i n gr e s p o n s i v ef l o w sf r o m n o n - r e s p o n s i v e o n e s a tt h es t a r t r e s e a r c h i n g o fn e t w o r kc o n g e s t i o n c o n t r o l ，m a n y m a n a g e m e n tm e c h a n i s m sn e e dt om a i n t a i ns t a t ea n dp e r f o r m p a c k a g es c h e d u l i n go n ap e r f l o wb a s i si no r d e rt oa c h i e v ef a i rb a n d w i d t ha l l o c a t i o n a n dt h i sc o m p l e x i t yr u i n st h e c h a r a c t e ro f i n t e r n e t s e a l a b i l i t y t h en e ws t u d yw a n tt op r o v i d ef l o wp r o t e c t i o na n df a i r b a n d w i d t ha l l o c a t i o nw i t h o u td e s t r o yt h en e t w o r k s c a l a b i l i t y , a n de v e l ls u p p o r tt h ed i f i s e r v m o d e l t h i sp a p e rp r o p o s e san o v e ls e a l a b l eb u f f e rm a n a g e m e n ta l g o r i t h mn a m e dp d d 0 a t r i a ld i s t i n c t i v e l yd r o p p i n g ) i nt h ed i r e c t i o no f t h i sg u i d i n gp r i z l c i p l e t h ep d da l g o r i t h mt a k et h ea d v a n t a g eo fc h o k et h a tc a np e n a l i z ef l o w st h a t p e r s i s t e n t l yo v e r u s e db a n d w i d t h w h e n ap a c k e tc o m e si n t ot h eb u f f e r , i td r o p st h ep a c k e t w i t hd i f f e r e n c ep a r t i a ld i s t i n c t i v e l yd r o p p i n gp r o b a b i l i t yf o rd i f f e r e n c ep r i o r i t yf l o w a f t e r t h a t , t h ep d da l g o r i t h mp r e v e n ti n t e g e rm e l t d o w nb yd r o p p i n gt h ep a c k e t si nt h eb u f f e r u s e dt h er e d a l g o r i t h m t h i sa l g o r i t h ma c 艟e v e sf a i l n e s sa n d 雕舶址扬e sb a d - b e h a v i o r f l o w s ，a n dp r o t e c t st c p f l o w su n d e rv a r y i n gd e g r e e so fa t t a c kf r o mn o n - a d a p t i v ef l o w s i tc a nt r e a td i f f e r e n c e 面o n t yf l o ww i t hr e l a t i v ed r o pp l 州e n c et ok e e pt h eh i g h e rp r i o r i t yf l o wa c h i e v eb e t t e r q u a l i t y o f s e r v i c ei nt i m eo f n e t w o r k c o n g e s t e d m o r ei m p o r t a n t , t h ea l g o r i t h m sc a np r o v i d e f a i rs h a r i n ga m o n gd i f f e r e n tf l o w sw i t h o u ti m p o s et o om u c hd e p l o y m e n tc o m p l e x i t yt o r o u t e r a ts 刮n et i m e t h i sp a p e re x t e n d st h en e t w o r ks i m u l a t o rp l a t n sb ya d d i n gn e w e l e m e n t s i m u l a t i o ne x p e r i e n c e sh a v eb e e n i m p l e m e n t e d a n dt h er e s u l t ss h o wt h a tp d dh a s r e a c h e dt h e a n t i c i p a f l v eo b j e c t s m o r e o v e r , p d da l s oh a v eb e t t e rp e r f o m m c ei nt h e c o m p l e x n e t w o r k t o p o l o g y , s u c h a ss m a l lw o d dn e t w o r k k e y w o r d s ：i pq o s ，d i t t s e r vm o d e l ， s c a l a b i t i t y ， b u f f e r m a n a g e m e n t ， n s e m e n d i n g ， s m a l lw o r l dn e t w o r k 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的 研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名：考皤龟牟 日期：蟛年f 月i o 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 保密口，在 本论文属于不保密i ( 请在以上方框内打“”) 学位论文作者签名：肖幸乏拿 日期：滞1 年f 月，护日 年解密后适用本授权书。 指导教师签名：霹殳兰茹乐， 日期：) o 悼f 月( 日 华中科技大学硕士学位论文 1 绪论 作为商业联系的基本设施之一，i n t c m c t 网正扮演着越来越重要的角色，流量的 几何级数增长迫使网络操作要高效地利用网络资源，同时各种实时业务与多媒体业务 的引入，还要求网络提供具有q o s 保证的服务。口协议薄弱的q o s 能力已经逐步成 为制约i n t e r a c t 业务发展的障碍。dq o s 是i p 网络增加服务内容、提高服务质量的关 键技术。本章综合介绍网络q o s 的概念，支持的口q o $ 问题的主要网络业务模型以 及复杂网络拓扑结构的最新研究方向小世界网络结构。 1 1 网络服务质量 网络的服务质量( q u a l i t yo fs e r v i c e ，o o s ) 【i 2 】是指服务性能的聚集效应，它决 定用户对特定服务的满意程度。用户的业务在网络传输的过程中所表现的各种性能， 可以用一组性能参数对它进行具体地描述。这些性能参数包括：连接的可用性 ( a v a i l a b i l i t yo ft h ec o n n e c t i o n ) 、到达速率或带宽、吞吐量( r a t eo rb a n d w i d t h ， 吐u 曲p m ) 、丢失率( 1 0 s s ) 、延时( d e l a y ) 、延时抖动( d e l a y j i t t e r ) 、安全性( s e c u r i t y ) 、 可靠性( r e l i a b i l i t y ) 。它们共同构成q o s 参数集，常用的q o s 参数是前五项。这些服 务性能的聚集效应，决定了用户的某一业务对网络所提供的通信服务的满意程度f 3 j 。 不同的业务对q o s 参数集的不同分量有不同要求。交互式的实时应用程序( 如 语音通信等) 对端到端延迟和抖动很敏感。非交互式的实时应用程序( 如单向广播等 对端到端延迟不敏感，但对抖动敏感。非实时应用程序往往对延迟不敏感。当前的以 i n t e m e t 为代表的口网络只提供尽力而为的服务，并不能保障用户业务的这些q o s 要 求，i p 网的q o s 保障【4 】功能则需要通过对i p 网控制机制进行扩展而实现。 业务所获得的q o s 取决于其实际占用的网络资源。网络上最重要的资源是路由 器的缓存容量和输出链路带宽。几个输入数据流共享同一个输出链路。其最大数据传 数速率为c 。路由器的转发速率r 必须小于或等于信道容量c 。如果r c ，则在理论 上无差错传输就是不可能的。如果总的分组到达速率超过r ，多余的分组在这个端口 就会建立排队等待。如果没有足够的缓存空间存储，分组就会丢弃。而分组的排队延 1 华中科技大学硕士学位论文 迟和丢弃是影响q o s 的主要因素。因而，网络的资源分配是q o s 保障机制的核心问 题。网络的资源分配是用户端的流量控制和网络上路由器的控制机制综合作用的结果， 本文主要集中讨论路由器上的控制机制。 1 2 网络服务模型5 l 最初设计的i n t e m e t 是面向无连接的分组交换网络，所有的业务分组被不加区分 地在网络中传输，网络能给出的唯一承诺就是尽自己最大努力传输进入网络的每一个 分组一一尽力而为地传输数据报，没有任何可控制的服务质量保证。这种体系结构上 的传统网络应用与网络协议具有较强的灵活性和适应性，同时使得路由器是状态无关 的，即除了高度聚集的路由信息外，网络上的路由器无需保持任何关于业务流的状态 信息。这使得今天的 n t e r a e t 具有很好的可扩展性和鲁棒性。 流量的几何级数增长追使网络操作要高效地利用网络资源，同时各种实时业务与 多媒体业务的引入，还要求网络提供具有q o s 保证的服务。但是尽力而为服务方式的 如下缺点使其很难满足网络的q o s 的需求：( 1 ) 在发生瞬时拥塞时，路由器提供的时 间响应是不可预测的。( 2 ) 对不同的业务流类型不能提供优先级服务。( 3 ) 不能动态地 请求( 或修改) 端到端的服务质量。( 4 ) 只有有限的机制可以用于审计网络资源使用情 况。 尽力而为的服务方式是m 网络得以迅速发展的重要原因，但是在m 网络日益承 担各种各样服务的今天，尽力而为已成为p 网络向综合业务网络发展的一个重要障 碍，i p 网络迫切需要q o s 的保证。如何在口网络中实现服务质量q o s 的保证，是计 算机网络中亟待解决的一个热点问题，i e t f 曾为此提出过几种服务模型，各有优缺点， 下面简要探讨主要的服务模型。 1 _ 2 1 综合服务模型 i e t f 在服务区分方面提出的第一个模型是综合服务( h t s e ) 模型嘲，综合服务模 型对传统互连网体系进行扩展以支持多媒体实时应用。它的目标在于对殂网络上传输 的每个流( 丑o w ) 的服务质量( 包括延迟、抖动和带宽) 进行控制。 2 华中科技大学硕士学位论文 目前综合服务模型已经相当成熟，其基本实现方法是：( 1 ) 以资源预留协议 7 1 ( r e s o u r c er e s e r v a t i o np r o t o c o l ，r s v p ) 信令向网络提出业务流传输规格，并建立和 拆除传输路径上业务流状态。( 2 ) 主机和路由器节点建立和保持业务流状态信息。 i n t s e r v 模型建议采用资源预留协议来完成资源预留。r s v p 使用端到端信令，传 送应用程序对网络的要求和在网络中传送q o s 管理信息。对于要求q o s 的会话，在 接收端和发送端之间所经过的每一个路由器上都进行了资源预留，因此在路由器中维 护了每一会话的状态信息m 一路黼 预蠢息 一划黼 ( a ) 用r s v p 进行资源预留( b ) i n t s e r v 中路由器的功能部件 图1 _ 1 综合服务模型 资源预窘建立具体过程如下( 如图1 1 ( a ) ) ：发送端发送r s v p 路径“p a t h ”信息 到接收端，接收端收到后沿与“p a t h ”信息相反的路径返回r s v p 预留“r e s v ”信息， “r e s v ”信息经过的每个路由器对r s v p 的资源预留请求进行“接纳控制”( a d m i s s i o n c o n t r 0 1 ) 和“监督控制”( p o l i c yc o n t r 0 1 ) 。接纳控制根据申请的资源参数和预留方式确 定本路由器是否有足够的资源来实现q o s 请求；监督控制则确定q o s 申请者是否具 有申请预留的权利( 如图1 1 ( b ) ) 。如可满足，则将所需的资源预留下来，向前一个节 点继续转发“r e s v ”信息，直至发送者，双方即可通信。如不满足，则可拒绝，再通 知接收者，则对话结柬。 i n t s e r v 在经过几年的研究和发展以后，其中的问题不断显现。i n t s e r v 是面向流 的、与状态相关的服务模型。在l n t s e r v 模型中，几乎任何一项功能都将涉及到所有的 网络节点，这种完全分布式的控制造成了极大的复杂性，导致了i n t s e r v 的可扩展性问 华中科技大学硕士学位论文 题和鲁棒性问题，使得在纯粹数据网络的分层结构之上实现i n t s e r v 和r s v p 信令机制 及其相关的功能需要大量的投资，需要在遍布世界范围的网络中引入繁重的软件和硬 件修改，实现难度大。这些严重妨碍了h a t s e r v 在大型网络，特别是重负载网络中的应 用。 1 _ 2 2 区分服务模型 区分服务( d i t t s e r v ) 9 1 与综合服务模型在技术上有很大差别，具有简单、易于实现、 与其它服务质量保障技术相互兼容等众多优势。它通过一种可伸缩方式加强了传统p 协议对服务质量的支持能力，不用增加复杂的信令协议，也不用收集每个流的相关信 息，而是将具有相同或相近质量需求的服务划分到同一服务类中，并对每种服务类采 用相同的“每一跳转发方式”( p e rh o pb e h a v i o r ，p h b ) 【。 区分服务是一种适合于大型路由器网络的集中式通信量处理机制，其目标在于设 计、实现、管理方面的简单有效，以克服i n t s e r v 所遇到的难题。d i 筋e r v 提供一种对 各种应用的服务级别进行划分的方法，它在核心路由器中仅仅保存少量的流聚集的信 息，而大量业务流的状态信息则保存在端系统中，核心路由器则专注于数据包的转发， 从而也就提高了网络的可扩展性。其基本实现方法是： ( 1 ) 简化网络内部节点的服务机制。在网络内部的核心路由器中只保存简单的区 分服务代码点( d i f f e r e n d a t e ds e r v i c e sc o d ep o i n t ，d s c p ) 与逐跳行为的对应机制，在数 据流进入核心路由器时只根据报文头部区分服务( d i f f e r e n t i a t e ds e r v i c e s ，d s ) 域中的 d s c p 进行简单的转发服务。 ( 2 ) 聚合网络内部核心路由器的服务对象。网络内部路由器的服务对象为宏流， 而不是单流。 根据用户的需求将服务分为多种类型，并将i p 包头中的t o s 域( i p v 4 ) 重新定 义为d s 标识域( d s c p ) 。网络节点根据数据包的d s c p 值选择相应的每一跳转发方 式( p h b ) 对数据包进行处理。不同的p h b 1 1 】可以采用不同的排队策略，丢包策略， 路由规则以及资源分配和预留策略。将采用相同或相近的策略实现p h b 方式合并为一 类，并将其称为p h b 组。每个p h b 组中可以包含一个或多个p h b 方式，它们共享数 华中科技大学硕士学位论文 据包调度和资源管理等策略，只在这些策略实施中采用不同优先级来区别每个p h b 方 式。目前i e t f 只定义了三种标准的p h b 组，即缺省转发方式组，快速转发方式组和 确保转发方式组。 在区分服务模型中，多个相互连接并基于相同网络策略和p i - i b 类型的路由器组 成的子网称为d s 子网区域。这些路由器可分为边缘路由器和核心路由器两种，同时 边缘路由器又可根据应用的流向分为流入路由器和流出路由器。图1 2 是区分服务模 型的框架示意图。 圈1 2l 苎分服务模型的框架示意图 d s 边缘路由器连接不同的d s 子网区域，应用流通过流入路由器进入d s 子网并 通过流出路由器到达下一个子网。它们按照本区域的相关策略和p h b 方式对流入流 出的流量进行调节和转发。d s 核心路由器用于连接同一个d s 子网区域的其它核心或 边缘路由器，它们的功能比较简单，主要是按照数据包头中d s c p 值映射相应的p h b 方式转发数据包。当然，核心路由器也可以进行一些简单的流量调节操作。区分服务 体系模型与以往提出的各种服务质量保障技术相比，具有许多优点【1 2 1 ： ( 1 ) 由d s 域所表示的服务类别非常有限，因此在数据传输路径上所保存的状态 信息也就很少，而且不随业务流数量的增加而改变，这大大增强了网络的可扩展性。 ( 2 ) 复杂的分类器、标记器、控制器以及整形器只需要布置在网络边界节点，而 华中科技大学硕士学位论文 核心网络节点只需要布置简单的分类器和整形器，这使得核心网络节点能专注于数据 包的转发。 ( 3 ) 与其它服务质量保障技术也有极好的兼容性，如支持局部的t o s 方式；可以 利用综合服务体系和r s v p 技术提高d s 子网的服务质量保障能力；还可以与多协议 标签交换( m p l s ) ，a i m 等其它网络技术结合使用等。 ( 4 ) 由于区分服务体系分段分数据包处理的特殊技术，可以采用局部递增的方式 在实际网络中实施，也就是说可以逐步过渡。 当然，区分服务体系也有很多需要改进和完善的地方，如：区分服务体系仍然是 基于无连接的网络技术，只能在每个子网中尽量提供服务所需的质量，但不容易保障 全网各处的服务质量，可能会由于局部网络较差影响全网的性能；子网间的s l a 需要 一种体系化的协商机制，便于网络管理者进行全局管理。 1 2 3 多协议标签交换 多协议标签交换( m u l t i - p t o c o ll a b e ls w i t c h i n g ，m p l s ) 1 3 q4 】是一个可以在多 种第二层媒质上进行标签交换的网络技术。这一技术综合了第二层的交换机制和第三 层的智能、灵活性的特点，将第二层基础设施和第三层路由有机地结合起来，第三层 的路由在网络的边缘实施，而在m p l s 的网络核心采用第二层交换。标记交换技术则 将交换机和路由器的优点完美地结合在一起了，如图1 - 3 所示。 +逛兰岁 - 路由器a r m 交换机标记交换路由器 图1 3 标记交换路由器 m p l s 这种基于标签的交换方式允许路由器在作转发决定的时候仅仅以简单的 标签为基础，而不是基于目标p 地址作复杂的路由查找。 在一个m p l s 网络当中，进入m p l s 区域的报文在“标签边缘路由器n a b e le d g e r o u t e r ，l e r ) ”处被分配一个标签，报文沿着“标签交换路径o a b c ls w i t c hp a t h ，l s p ) ”进 6 华中科技大学硕士学位论文 行转发，路径中的每个标签交换路由器( 1 a b e is w i t c hr o u t e r ，l s r ) ”仅仅根据标签内容 来做出转发决定。 标记分发协议 图1 4m p l s 网络的结构 m p l s 网络的典型结构如图1 4 所示。m p l s 网络的基本组成单元是标记交换路 由器l s r ，m p l s 域内部l s r 之间使用m i l s 协议进行通信，而在m p l s 域的边缘 由m p l s 边缘路由器进行与传统口技术的适配。 目前m p l s 的最主要功能是流量工程( t r a f f i ce n g i n e e r i n g ，t e ) ，即在多条可能的 转发路径中进行负载平衡。流量工程是指为业务流选择路径的处理过程，以在网络中 不同的链路、路由器和交换机之间平衡流量负载。流量工程的主要目的是提供有效可 靠的网络操作，同时优化网络资源的利用和业务流性能。 1 3 复杂网络拓扑结构 目前对大型计算机网络( 如i n t e m e t ) 拓扑的研究表明：大型计算机网络的拓扑具 有小世界网络( s m a l l - w o r l dn e t w o r k s ) 的特征，即在网络节点数目非常大的情况下， 网络特征路径长度短，聚集系数大。由于网络结构的特征必然会影响到网络功能，因 而有必要在复杂网络拓扑结构下研究网络拥塞控制机制的性能。 华中科技大学硕士学位论文 1 3 1 复杂网络拓扑结构的统计参数 首先定义两个描述复杂网络结构特征的统计参数： ( 1 ) 特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 在网络中任选两个节点，连通这两个节点的最少边数，定义为这两节点的路径长 度。网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。很明显， 特征路径长度是网络的全局特征。 1 2 ) 聚合系数( c l u s t e r i n gc o e f f i c i e n t ) 假设某个节点有k 条边，则这k 条边连接的节点( k 个) 之间最多可能存在的边 数为k ( k 1 ) 2 ，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这 个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。很明显，聚 合系数是网络的局部特征。 根据文献【1 5 l 的统计，有表1 1 的结论： 表1 1 网络统计特征 网络类型大小平均随机网络平均随机网络 最短距离最短距离聚集程度聚集程度 r w ，1 5 3 1 2 73 13 3 5o 1 0 7 80 0 0 0 2 3 i n t e r a c t3 0 1 53 76 3 50 1 80 0 0 1 i n t 血- n c t6 2 0 93 7 66 1 8o 3o 0 0 0 2 7 从上表中可以得出，计算机网络具备特征路径长度小和的聚集系数大这两种特性， 数学上把具有这两种特性的网络称为小世界网络。 1 3 2 复杂网络拓扑结构的模型 对复杂网络拓扑的研究目标之一就是建立能够产生具有特定统计特征的网络结构 模型。目前已有的复杂网络拓扑结构模型大致分为三类：一是随机图，二是规则模型， 三是由w a t t s ( c o l u m b i au n i v e r s i t y ) 和s t r o g a t z ( c o m e du n i v e r s i t y ) 在1 9 9 8 年提出 的著名的w s 模型【1 6 1 。 ( 1 )随机图 华中科技大学硕士学位论文 假设总数为的群体，平均每人有世个邻居( 即每个点平均与芷个点相连，芷 称为网络配位数) ，与每个邻居的连接都称为一个键或边，这里的连接都是双向对称的， 网络中共有n k 2 个键。于是选取个点，随机连接其中一些点形成n k 2 条边代 表他们之间的联系，就构成了一个随机图。随机图在数学领域己得到深入的研究( 特 别是e r d 6 s 和r 6 n y i ，1 9 5 9 ) 。 从表1 _ 1 可知：随机图模型的特征路径长度非常逼近于小世界网络的结果，但聚 集系数就差得较远，不能作为小世界网络的数学模型。 2 ) 规则网络 与随机图相反的是规则网络。规则网络相当于一个规则的有迹可循的晶格点阵， 可以用直线尺寸来计量，模型中各点的连接相同。图1 5 是最简单的规则模型完 全有序一维点阵。如果将一维点阵中各个点的足个邻居连接起来( 如图1 5 中置= 6 ) ， 很明显各个点的邻居又互为邻居，体现了集团化特征。对这个点阵采用循环边界条件 使之形成环( 如图1 6 ) 。 图1 5 一维点阵模型图1 6 环状规则模型 规则网络能够较好地反映小世界网络聚集系数大的特点，但其特征路径长度也 大，不能作为小世界网络的数学模型。 ( 3 ) w - s 模型 w a t t s 和s t x o g a t z 在前两个的基础上提出了著名的w s 模型。本质上说，w s 模 型是在环状规则模型中用“断键重连”的方法引入一定随机性的网络结构。 对于有n 个节点的网络，先构造每个节点有k 条边的规则网络，以概率p 重连它 的边( r e w i r i n g ) ，显然，当p = 0 时，相当于各边未动，还是规则网络：当p = l 时， 就变成了随机网络。这里要研究的是0 t a g g e d 0 ) s p r i n t f ( p t _ - b u f f e r0 ， c t i m ef o p , 姒t 一s d - d d - p 齄一e d c d i9 6 d a d x s 。s s 。 s d s s l7 ， t t ， s c h e d u l e r ：i n s t a n c e0 c l o c k ( ) s ，d ，n a m e ， t h 一 s i z e 0 ， i p h 一 f l o w i d0 ， t h - u i d 0 ， i p h 一 f l o w i d ( ) ， a r cn o d e a d d r ， s r cp o r t a d d r d s tn o d e a d d r ， d s t _ p o r t a d d r ， s e q n o ，f l a g s ，s r l s e ) ； ) 以下是仿真实例市场的跟踪输出文件o u t x r 的部分 一1 2 4 5 5 0 401 t c p1 0 4 0 一一1 10 1 0i 1 01 1 51 9 5 1 ri 2 4 5 6 4 801c b r1 0 0 0 10 01 07 3 81 9 3 5 r1 2 4 5 7 9 210a c k4 0 一1 01 9 0 97 52 0 2 4 + 1 2 4 5 7 9 20i t o p1 0 4 0 一1 00 9 1 98 02 0 4 3 + 1 。2 4 6 40lo b r1 0 0 0 一一10 0i 07 7 92 0 4 4 d1 2 4 6 401c b r1 0 0 0 一10 01 07 7 92 0 4 4 一i 2 4 7 1 6 801 t o p1 0 4 0 1 10 1 01 1 01 1 61 9 5 4 ri 2 4 7 2 4 801c b r1 0 0 0 10 0 1 07 3 91 9 3 6 3 9 华中科技大学硕士学位论文 r1 2 4 7 4 5 6l0a c k 4 0 一1 0 190 97 62 0 2 7 + l 2 4 7 4 5 60l t a p1 0 4 0 一一1 00 9 i 98 12 0 4 5 + l2 4 801c b r1 0 0 0 一1o 01 _ o7 8 02 g 4 6 dl - 2 4 801c b ri 0 0 0 一一l0 。01 07 8 02 0 4 6 1 2 4 8 8 3 201 t c p1 0 4 0 l l0 1 0 1 1 01 1 71 9 5 7 r1 2 4 8 9 1 201 t c p1 0 4 0 一1 10 1 01 1 01 1 11 9 3 8 + 1 2 4 8 9 1 210a c k4 0 1 11 1 00 1 01 1 12 0 4 7 一l _ 2 4 8 9 1 210a c k4 0 l ll _ 1 0o 1 01 1 12 0 4 7 对应t r a c e ：f o r m a t 从第1 列到第1 2 列将其含义解释如下：第1 列表示特定的 跟踪对象实现的跟踪类型，+ ( 进队列) 、一( 出队列) 、r ( 接 国、d ( 丢弃) ；第2 列表示事 件发生的时间( s ) ；第3 列、第4 列分别表示跟踪的源和目的节点号；第5 列表示包类 型名称；第6 列表示包大小；第7 列是一个标志字符串，当前进支持e c n ；第8 列是 i p v 6 的口流标识号：第9 列、第1 0 列包的源和目的节点地址；第1 1 列表示流内的顺 序号；第1 2 列表示一次仿真中每个新生成包的唯一标识号。 对跟踪输出文件进行分析可得到想要的任何数据，如某个流成功发送的包数目、 丢弃的包数目、或关于某个队列的统计数据等，这样就可评价一个协议或队列机制的 性能。 队列监视指的是跟踪一个队列或是其它对象中包的到达、发出、丢弃的统计数据 以及其平均值，监视可以基于所有的包或基于单个流。一般在支持队列监视的链路上 有包到达时，包传递给s n o o p q u e u e 对象，该对象包含一个q u e t m m o n i t o r 对象的引用， 从而可以记录包的统计数据。 也可通过编写实例r e c o r d 过程定期获取所需数据，存储于指定的磁盘文件做进 一步分析。 p r o cr e c o r df ) g l o b a ln sfn u l l 0 s e tt i m e0 1 a 设定时间间隔为0 1 s s e tb w l $ n u l l os e t b y t e s 一 s e tn o w $ n sn o w p u t ss f s n o w e x p rs b w l $ t i m e * 8 1 0 0 0 0 0 0 ：晦数器记录与文件 s n u l l 0s e tb y t e s0 s n sa t e x p rs n o , + $ t i , e 3 。r e c o r d “重复调用r e c o r d ) 4 0 华中科技大学硕士学位论文 对以上各种方式获得的数据结果分析以后，可得到我们所需要的有用数据，并可 将其装换成便于比较的各种形式的图形( 在l i n u x 下可采用n s 带的x g r a p h ，在w i n d o w 下可采用e x c e l 、o r i g i n 等绘图软件) ，以得到简单直观的实验结果，利于分析评价。 4 4 试验脚本编写 进行n s 实验时，其中重要的一步就是编写相应的实验脚本，是采用t e l 这种开 放式脚本语言实现的。主要是设置实验拓扑结构、实验参数、实验控制等。一个实验 脚本一般包括以下内容： ( 1 )定义实验环境的拓扑结构，包含节点，以及节点之间的连接； ( 2 )设置保存试验结果的文件，包含实验数据文件和实验运行示例文件； ( 3 )定义各链路带宽、时延、选取的调度算法； ( 4 )设置缓存管理算法的各项参数( 不设置时即为采用n s 平台的默认设置) ( 5 )定义链路的缓存队列大小( 不设置时即为采用n s 平台的默认设置) ； ( 6 )定义不同的流的权重，在某些实验时需要； ( 7 )定义产生的流量的类型； ( 8 )编写记录过程，并设置记录的时间间隔和所需记录的参数； ( 9 )定义实验开始和结束的时间。 利用l i n u x 下的文本编辑器v i 编写实验脚本，并保存为+ t e l ，保证文件的可执行 性，在l i n u x 的虚拟终端运行n s + t e l 即可。 4 5 本章小结 在网络迅速膨胀的今天，网络研究人员一方面要不断思考新的网络协议和算法， 为网络发展做前瞻性的基础研究；另一方面也要研究如何利用和整合现有的网络资源， 使网络达至4 最高效能。无论是哪一方面都需要对新的网络方案进行验证和分析，期望 总是在现实的网络中达到这个目的是不现实的，仅仅进行理论分析也不能转化为成果， 网络仿真无疑提供了一个方便、高效的验证和分析方法。n s 作为一种免费的，开放 的网络仿真平台，功能强大，灵活，并提供了很好的可扩展性，无疑是一种科研人员 4 1 华中科技大学硕士学位论文 强有力的工具。本章对其层次结构作了详细的分析，对其扩展性进行了细致的研究， 详细的说明了如何在n s 环境下开发用户自己的仿真对象的方法及步骤，对于需要在 n s 中加入新的仿真元素的仿真试验来说是具有很切实的意义。 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = ；= = = = = = = = = = = = = = = = = = = = = = = = = = 5 基于n s 平台的p d d 算法仿真 在前一章中本文提出了新的实现区分服务可扩展的缓存管理算法p d d ，并且作 了相关的数学分析，本章将在网络仿真平台n s 对其进行网络仿真研究，主要考查p d d 三个方面的性能：能否实现业务流之间的公平性，能否实现区分服务的要求，同时检 测p d d 算法在复杂世界网络中的适应能力。本章在n s 平台上设计了网络模拟试验进 行仿真验证，同时与其他的缓存管理算法比较。 5 1 。p d d 算法的公平性 网络中各业务流竞争网络资源时，网络中的控制机制的基本目的就是在无特殊要 求的情况下尽量保证各业务流之间的公平性。作为路由器上的缓存管理算法，p d d 需 要能够满足这一要求。为了验证p d d 的公平性，本文设置以下试验： 5 1 1 i c p 与u d p 的竞争 t c p ，u d p 是网络上两种主要的业务流形式，t c p 本身具有拥塞控制机制，在网 络拥塞时能够自动的作出反应，降低发送速度以缓解网络的拥塞；而u d p 则不顾网 络是否拥塞，始终按照同一速率发送数据，这样，在t c p 与u d p 竞争时，t c p 流将 处于不利的地位，可能让u d p 占据全部的网络资源。本试验则是为了验证在t c p 与 u d p 竞争时，p d d 对t c p 流的公平性。 网络的拓扑结构如图5 1 所示，瓶颈链路位于两个核心路由器之间。从s 1 ， s 2 s 1 2 一共1 2 个网络终端发出1 2 个具有相同优先级的业务流，竞争核心路由器间 带宽为5 m b s 的瓶颈链路，s 1 节点上为u d p 流，其发送速率分别为5 m b s 。s 2 s 1 2 节点上为t c p 流，1 2 个业务流均通过一条5 m b s 接入链路连接到边缘路由器，边缘 路由器与核心路由器之间的链路带宽为1 5 m b s 。仿真时间为1 0 s 。 4 3 华中科技大学硕士学位论文 毫r 0 路l 三i 器麟o 掩辩帮 试验结果如图5 2 所示。 图5 1网络仿真拓扑图 沉数目 图 5 2u d p 与t c p 之间的竞争 图中x 辘对应不同的业务流，y 轴为实际获得的平均带宽( m b s ) 。第1 个业务 流为u d p 流，发送速率为5 m b s ；第2 个到第1 2 个业务流为t c p 流。 从图5 2 中可以看出，u d p 流占用的带宽高于t c p 流的占用带宽，但是同u d p 的发送速率5 m b s 相比，u d p 流占用的带宽不到发送速度的一半，较好的得到了抑制， 华中科技大学硕士学位论文 t c p 流也分得了一定的带宽，同r e d 等算法相比可以在一定程度上实现u d p 与t c p 流之间的公平性。 5 1 2 u d p 之间的竞争 网络的拓扑结构设置同上，如图5 1 所示，瓶颈链路位于两个核一t l , 路由器之间。 从s 1 ，s 2 s 1 2 十二个网络终端发出十二个具有相同优先级的业务流，竞争核一l h , 路由 器间带宽为1 0 m b s 的瓶颈链路，十二个节点上的业务流均为u d p 流，发送速率从 o 5 m b s ，1 0 m b s ，1 。5 m b s 依次等量递增至6 0 m b s 。十二个u d p 流均通过一条1 0 m b s 接入链路连接到边缘路由器，边缘路由器与核心路由器之间的链路带宽为3 0 m b s 。仿 真时间为1 0 s 。试验结果如图5 - 3 所示。 u 馥 鞋 e 上 图5 3u d p 流之间的竞争 图中x 轴对应不同发送速率的u d p 业务流，y 轴为带宽( m b s ) 。系列1 代表 各流在竞争时获得实际平均带宽，系列2 代表备流的发送速率。 从图5 - 3 中可以看出，不同速率的流分得的带宽相差并不大，随着u d p 流发送 速率的增加，u d p 流占用带宽并未成比例增加，相