（通信与信息系统专业论文）弹性分组环多阻塞点公平性算法的fpga实现.pdf

重庆邮电大学硕士论文 摘要 摘要 网络宽带化和i p 化是当前通信发展的大趋势，对城域网的发展产生了巨大的 压力，也成为各大电信运营商的关注焦点。弹性分组环( r e s i l i e n tp a c k e tr i n g ) 技 术集i p 的智能化、以太网的经济性和光纤环网的高带宽效率、高可靠性于一体， 为宽带i p 城域网运营商提供了良好的组网方案，使得运营商在城域网内以低成本 提供电信级服务成为可能，因此具有广阔的市场前景。 r p r 环网采用双环结构，空间复用机制，拓扑自动识别机制，保护倒换机制， 统计复用技术等，但是其主要目标是实现高带宽利用率、空间重用和带宽的公平 分配。这些都需要通过合理有效的公平性算法来实现。 具体来说，本文的工作主要包括下述几个方面： 首先，本文根据i e e e s 0 2 1 7 协议全面地介绍了弹性分组环背景知识，协议模 型及网络结构等，并详细分析了r p rm a c 协议中与公平性算法密切相关的一些 问题，包括帧结构的定义、业务等级划分等； 第二，研究分析现有的具有代表性的公平性算法，对各个算法进行分析并对 它们作出详细的性能比较，为多阻塞点公平性算法的设计提供了宝贵的参考思路 和方向； 第三，提出了多阻塞点公平性算法的f p g a 设计的总体框架结构，并且说明 了总体框架中各个模块间的通信流程； 第四，对多阻塞点公平性算法，系统地介绍了各个模块的功能，并且用f p g a 进行实现； 第五，通过对各个模块的仿真，分析仿真结果表明了各个模块完成了预期的 目标，具有很好的性能；同时将模块组合起来，针对几种典型的停车场景进行仿 真，证明了设计地多阻塞点公平性算法f p g a 实现是可行的，且具有良好的稳定 性和可扩展性； 最后，指出下一步研究工作的难点和方向。 关键词：r p r ，公平性算法，多阻塞点，f p g a a b s t r a c t i nr e c e n ty e a r s t h et r e n d so fc o m m u n i c a t i o na r et h eb a n d w i d t ha n di pi n t e l l i g e n c e w i t ht h er a p i dd e v e l o p m e n to fa c c e s sn e t w o r k ，m e t r o p o l i t a na r e an e t w o r k ( m a n ) m u s t f a c eu pt ot r e m e n d o u sp r e s s u r e s ot e l e c o m m u n i c a t i o nc a r r i e sp a ya l la t t e n t i o n st o s u p p l y i n ga b u n d a n tb a n d w i d t hf o ru s e r sq u i c k l y r p rp o s s e s s e s e x c e l l e n tp e r f o r m a n c e w h i c hi s i n t e g r a t e dw i t hm a n ya d v a n t a g e s ，s u c h a se c o n o m yo fe t h e m e t ，t h e i n t e l l i g e n c eo fi n t e r n e tp r o t o c o l0 p ) ，a n dh i g hb a n d w i d t ha n dr e l i a b i l i t y o fo p t i c a l f i b e r r i n g n e t w o r k s t h e s ea d v a n t a g e sm a k e r p r p o s s i b l e t o p r o v i d e t e l e c o m m u n i c a t i o ns e r v i c e s 、i t hl o wc o s t s m o r e o v e rr p rc a nd e a lw i t hd a t as e r v i c e s a n dm u l t i s e r v i c e sb e c a u s eo fi t sr e l i a b i l i t y t h e r e f o r e ，r p rh a sap l e a s a n tm a r k e t p r o s p e c t r p rh a sad u a l r i n gc o n f i g u r a t i o n ，a n ds u p p o r t ss p a t i a lr e u s ep r o t o c o l ( s r p ) ， d y n a m i cb a n d w i d t h a l l o c a t i o n ，c l a s so fs e r v i c e ，a u t o m a t i ct o p o l o g yd i s c o v e r y , i n t e l l i g e n tp r o t e c t i o ns w i t c h i n g ，e t c t h e r e f o r e ，t h es p a t i a lr e u s e ，b a n d w i d t he f f i c i e n c y a n df a i r n e s sa l et h ea i m so fr p r f a i m e s sa l g o r i t h mi si m p o r t a n t i tm e a n st h a tu s i n g f a i r n e s sa l g o r i t h m sc a na d j l a s tb a n d w i d t ho nl i n k sb e t w e e nt w on o d e sw h e nc h o k e h a p p e n e di nr p rn e t w o r k s t h e r ea r ea l s of a i m e s se v a l u a t i o nr u l e sa n di n d e x f i r s t l y , a c c o r d i n gi e e e 8 0 2 17p r o t o c o l ，t h i sp a p e ri n t r o d u c e st h eb a c k g r o u n do f t h er p i 乙e x p l a i n st h en e t w o r ks t r u c t u r ea n dp r o t o c o lm o d e lo fr p r w ea n a l y s es o m e p r o b l e m sw h i c ha l er e l a t i o n s h i p w i t ht h ef a i r n e s sa l g o r i t h m ，i n c l u d i n gd e f i n i t i o no f f r a m ef o r m a ta n dd i f f e r e n c eo ft l l es e r v i c el e v e l s e c o n d l y ，t h et h e s i sa n l y s e st h et y p i c a lf a i r n e s sa l g o r i t h m s ，a n dc o m p a r et h e i r p e r f o r m a n c e b yc o n t r a s t ，i tg i v e su ss o m eg o o di d e a st op r o p o s ean e w m u l t i c h o k e f a i r n e s sa l g o r i t h m t h i r d l y , t h i sp a r ti si m p o r t a n tt ou s ，a n da l s oi st h e i n n o v a t i o n w ep r o p o s ean e w f p g ad e s i g ni nr p rn e t w o r k s ，a n de x p l a i nt h ec o m m u n i c a t i o nb e t w e e nt h em o d u l e s i nt h ef r a m e f o u r t h l y , w ed e s i g nf p g a f o rt h em u l t i - c h o k ef a i m e s sa l g o r i t h m ，i n t r o d u c et h e p e r f o r m a n c eo fe v e r ym o d u l e a n dt e s t f i f t h l y , t h es i m u l a t i o nf o re v e r ym o d u l e ，h a sp r o v e di t sg o o dp e r f o r m a n c e t h e n t h em o d u l e sa r ei n t e g r a t e di n t oaw h o l ep a r t t od e s i g nf p g as i m u l a t i o nf o rs e v e r a l s c e n e s ，i th a sp r o v e dt h ef p g ad e s i g nf o rm u l t i - c h o k ef a i r n e s sa l g o r i t h mi sf e a s i b l e i i 重庆邮电大学硕士论文 摘要 a n dh a sg o o ds t a b i l i z a t i o n f i n a l l y , w ea l s op o i n to u tt h ed i f f i c u l t yo ft h en e x tr e s e a r c ha n dt h ef u t u r et r e n d k e yw o r d s ：r p r ，f a i r n e s sa l g o r i t h m ，m u l t i - c h o k e ，f p g a i i i 第一章绪论 1 1 引言 第一章绪论 近年来，随着信息化的不断发展，人类对于通信提出了越来越高的要求，尤 其是对于数据方面综合信息服务的需求更是迅猛地增长。用户的需求已经不仅仅 停留在普通电话业务，因特网浏览和有线电视的观看，更多的要求网络能够提供 很多的公众服务项目，如远程医疗、远程教育、电子商务等等。所有这些，迫使 传统的电信运营商努力寻求增值业务作为新的利润增长点。为了在激烈的竞争中 取得商机，保持优势，电信运营商都把数据业务作为了突破口，大力进行城域网 的建设。 在现有的城域网中，光网布局大都为环状，多采用s d h 和s o n e t 技术。以 太网可以很方便的扩容局域网到较高的速率，但是在城域网的环状光纤布局上， 以太网还不能直接利用环状网络的优势，例如快速的路径保护等。因而在城域网 中以太网应用受到了一定的限制，必须与其他技术进行结合，如e t h e m e to v e r s d h 。而传统的s d h 网络是为了传输话音业务而设计的，其固有的特性限制了它 在传输数据业务上的效率，因此迫切需要发展一种基于数据的城域网络技术。 在i p 领域人们很早就认识到了环形网络结构的价值，并且已在这方面作了大 量的工作，发展了像令牌环和光纤分布式数字接口( f d d i ) 这样的解决方案；但 这些方案还是无法满足m 流量和光纤带宽增长的需要，也无法满足在阻塞情况下 维持高的带宽利用率和转发量、保证节点迅速从传输媒体故障中恢复、可即插即 用等疋传输和业务传递发展的需要。所以像令牌环这样的环网并不适合用于城域 网。运营商需要一种扩展性好、能够健壮地应用在城域网和广域网上，以千兆的 速度传输数据信息的技术。 因此，2 0 0 0 年1 1 月正式成立了i e e e 8 0 2 1 7 弹性分组数据环工作组，希望开 发一个r p r ( r e s i l i e n tp a c k e tr i n g ) m a c 标准，优化在l a n 、m a n 和w a n 拓 扑环上数据包的传输。而本文所研究的弹性分组环技术对于现代网络的发展具有 实际的指导意义。 1 2 弹性分组环概述 弹性分组环( r p r ，r e s i l i e n tp a c k e tr i n g ) 1 1 】- 【5 1 ，是一种基于城域网的新型网 络结构和优化数据传输技术，它是对以太网中点到点、点到多点的通信机制和环 重庆邮电大学硕士论文 状网络拓扑应用的进一步扩展。在此之前，城域网主要采用了三种技术： s o n e t s d h 技术阡【l l j 、以太网( e t h e m e t ) 技术7 1 【l l 】及a t m 技术【7 】【8 】【1 2 】【1 4 1 。一 般而言，以往广泛应用于i p 数据业务主要是以太网技术，而可靠性好且广泛应用 的网络基础结构是s d h 技术和a t m 技术，但是这些技术都有自身的缺点。a t m 技术复杂，成本昂贵且随着数据业务的不断增长而最终被淘汰：s o n e t 技术对数 据业务的支持能力差，且点对点的连接方式浪费了大量的带宽资源；以太网则缺 乏对q o s 的有效支持，其系统的可靠性和网络安全性得不到保证，网络的恢复能 力也比较差。 u p s t r e a ms t a t i o n f r a m e d o w n s t r e a ms t a t i o n r i n g l e t 0 图1 - 1r p r 双环结构示意图【4 l r p r 以其技术的先进性、投资的有效性、性能的优越性、支持业务的多样性 为城域网的组建提供了一个良好的解决方案。同时r p r 采用双环结构、空间复用 机制、自动拓扑实现机制、基于源路由的保护倒换机制、带宽的动态分配、统计 复用等，是当前的城域光环网络上优化数据包传输的首选技术，且具有良好的拓 展性，可以有效地应用到广域网中来。此外，作为一种新的光环网技术，r p r 利 用环网中大部分数据业务的实时性不如话音业务那样要求高的特点，采用双环并 行工作的方式使之获得比s o n e t 环网大一倍的可用带宽，极大地提高环路带宽 资源的利用率，从而降低了运营商、企业及客户的成本。可以说r p r 是集i p 技 术的智能化，光纤环网的可靠性，以太网技术的高效性和经济性以及业务的普遍 性于一体，从而使得r p r 网络成为了一个高效率、高可靠性的宽带承载网。因此， r p r 成了优化城域网中数据传输的首选技术，而且必将成为下一代p 业务的主 流技术。 国内外研究与应用现状： 目前，许多公司都已推出了不同的r p r 城域交换产品，以期在市场竞争中占 得先机。代表性的产品有c i s c o 的d p t s r p 系列、n o r t e ln e t w o r k s 的 i n t e r w a n p a c k e t t r a n s p o r t 、l u m i n o u sn e t w o r k s 的p a c k e t w a v e 系列。以l u m i n o u s n e t w o r k s 的p a c k e t w a v e 系列产品为例，l u m i n o u sn e t w o r k 提供了整套完全基于。 弹性分组环的城域解决方案，并提供丰富的接口：用于专线的t 1 e 1 和d s 3 ，用 于数据的1 0 1 0 0 1 0 0 0 m b 以太网口，以及用于a t m 或者s d h s o n e t 的 s t m - n o c - n 接口。我国的多家公司也进行r p r 的研究与应用，并且参与了标准 2 第一章绪论 化工作，华为公司推出的q u i d w a yn e t e n g i n e 4 0 系列通用交换路由器( u s r ) 支 持r p r 协议机制，可以提供r p r 保护功能。运营商，部分新建或在建的城域网 采用弹性分组环组网，如：广州电信r p r 试验网和广州联通城域数据接入网。组 网实践表明，目前厂商的产品基本上符合r p r 标准提出的要求，弹性分组环基本 上实现了其所宣称的各种功能，但是支持t d m 业务方面还不能与s d h 网络相比， 并且不同厂商设备之间的互通互连存在问题。 1 2 1r p r 分层模型 根据i e e e 8 0 2 1 7 协议f 4 】，r p r 主要包括了四个层面【1 辄1 6 】f 17 j ：物理层及其适配 层，m a c 数据子层，m a c 控制子层，m a c 客户子层，如图1 2 各层的功能简要 讨论如下： o s i 参考模型 r p r 分层模型 高层 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 l l c ( m a c 客户子层) m a c 业务接口 m a c 控制子层 臣圃 圈 预两r 蕊订卜丽酮 m a c 数据通路 p h y 业务接口 协调子层 e t h e m e t s d h 朋d m 物理层 ( 介质 ( 重庆邮电大学硕士论文 该层主要完成m a c 子层的控制，包括自动拓扑发现控制，保护倒换控制， o a m ( 运营，维护，管理) 控制，以及完成最优环路选择和m a c 子层数据业务接入 的流量控制。 ( 4 ) r p r 的客户子层 该层主要实现对来自网络层的业务数据进行r p r 帧格式的封装，对各种不同 的业务数据进行不同优先级适配，同时完成r p r 环网上出现链路阻塞时为充分利 用环路资源而实现虚目的地队列( v i r t u a ld e s t i n a t i o nq u e u e ，v d q ) 算法，也称之为 虚输出队列( v i r t u a lo u t p u tq u e u e ，v o q ) 算法。同时m a c 客户子层还将完成高优 先级数据业务的承诺信息速率( c o m m i t t e di n f o r m a t i o nr a t e ，c i r ) 控制。r p r 技术 在m a c 客户子层和m a c 控制子层均进行流量控制( 其控制的层面和范围不同) ， 以优化网络中的分组数据传输效果。 1 2 2r p r 所能提供的业务类别 与以往的数据传输协议相类似，r p r 所传送的业务等级分为a 、b 、c 类， 其对应的服务质量保障依次降低。a 等级的时延和抖动都最小，可以用于传送诸 如视频、话音等实时业务，它又进一步分为a 0 、a 1 两个等级。b 等级允许一定 的抖动和时延，又分为b c i r ( 承诺速率) 和b e i r ( 额外速率) 两个等级。c 等级业务的优先级最低，是属于尽力而为( b e s t e f r o r t ) 型的。以上业务等级中， b e i r 和c 等级一起构成了r p r 中定义的f e 业务等级，也就是受公平算法约束 的业务等级，这类等级的业务所占用的带宽由公平性算法进行分配。值得注意的 是，f e 等级的业务并不是在发生拥塞时就可以丢弃的业务。r p r 在传输时，不 会因为拥塞而丢弃已经在环上运行的业务，所以只要光纤或节点不出现故障，环 上的业务都最终会被传送到目的节点，只是不同等级的业务，带宽分配方式有所 不同。 表1 1r p r 的业务等级划分 等级 业务 带宽时延和抖动速率限制 a 低时延保证保证低保证 带宽业务 b 有界时延承诺不超过承诺的带宽保证 有上界 带宽业务 超过承诺的带宽不保证无上界公平算法 c 尽力而为( b e )不保证 动态限制 业务 第章绪论 1 2 3r p r 帧格式定义 r p r 采用类似以太网的帧格式，环上所有节点被赋予唯一的逻辑m a c 地址， 可以基于m a c 地址进行快速的二层交换，简化i p 传输。当物理层采用 s d h s o n e t 时，与p o s 技术相比，r p r 帧封装更简化、更灵活，可以直接将i p 数据包通过r p r 帧格式适配到光纤上，无须进行i p 包的拆分和重组，避免了协 议的复杂性和过高的开销，大大提高了交换机的处理能力，降低了设备的价格。 r p r 标准【4 】共定义了四种帧结构：数据帧、控制帧、公平帧和空闲帧。 1 数据帧 帧格式如图1 - 3 a 所示。数据帧用来封装来自m a c 客户的数据包，帧头携带 t t l 、目的地址、源地址等信息，并进行1 6 位c r c 校验。其中控制( b a s e c o n t r 0 1 ) 中各位的定义如图1 - 3 a 所示，各位域的定义见表。负载除了包含来自上层的数 据包，还有协议类型域，指示上层协议类型、帧尾是3 2 位f c s 校验码。 表1 2b a s e c o n t r o l 字节中各位的意义 域意义 子环标示 n f e是否受公平算法制约 n帧类型 s c服务等级 w e是否允许进行环回操作 r e s保留域 2 控制帧 帧格式如图1 - 3 b 所示，控制帧用来传递弹性分组环内的拓扑发现、故障保护、 o a m 等控制消息，帧头与数据帧相同，负载域指示控制消息类型、版本号和控 制消息内容，已定义的消息类型有四种，其长度最小为2 4 b i t ，最大为1 5 2 2 b i t 。 表1 - 3 控制帧中控制类型字节的取值与意义 数值宏定义 类型作用 0 1 c t s t a t i o n t l v节点发现帧更新拓扑信息，发现新接入节点 0 2 c 飞j o p o p r o t故障保护帧通告故障发生 0 3c to a mo a m 控制帧o a m 控制 0 4c tv e n d o rt l v拓扑发现帧 拓扑更新 保留 保留 3 公平帧 帧格式如图1 3 c 所示，用来传递带宽分配消息( 公平信息) 。 重庆邮电大学硕士论文 4 空闲帧 帧格式如图1 - 3 d 所示，它不包含地址信息，长度为固定的1 6 字节，只在相 邻节点之间传递。如果各个节点各自维持本地时钟，由于时钟的问题差异，本地 的发送速率可能小于上游的发送速率，导致本地转发队列溢出，这时上游节点就 需要空闲帧插入到数据帧中间，维持节点间收发速率的同步，避免转发队列溢出。 b n 4 p r o t o c o l t y p e h e a d e r p a y l o a d b n 4 n i e x t e n d e d c o n t r o i c o n t r o l t y p e a 数据帧结构 b 控制帧结构 h e a d e r p a y l o a d c 公平帧结构d 空闲帧结构 图1 - 3 各帧结构图 1 2 4r p r 公平性算法概述 1 2 4 1 公平性算法功能 公平性算法的基本功能主要包括链路的拥塞检测、公平速率的计算以及f c m 帧的生成和传送、允许传送速率的确定等步骤。 f c m 帧结构 公平性算法通过f c m 帧在各节点间传送公平速率信息。下图l - 4 为f c m 帧 结构 4 1 。其中，“源m a c 地址”为发送f c m 帧的节点的m a c 地址；“公平性控 制头 中的“f c m 类型”用来表明f c m 帧的类型；“控制值 则为公平速率值。 6 1_ m 一 一 一： t 一 一 一e n 一 一翱oaaacd一鳓一b e 一 一 一n 蠹| 一 一钥 军一 型二睇o aaacd一岛一旧 e 一 一 一u 勰一 一 一。 军一 第一章绪论 l 字节 l 字节 6 字节 2 字节 2 字节 4 字节 m s b l s b r r l r if ef rs cw ep 源m a c 地址 3 比特5 比特 ，7 f c m 类型预留 公平性控制头 预留 控制值 帧校验 图1 4f c m 帧结构 链路的阻塞监测 当r p r 网络中的节点出现下述任何一种情况时，就认为与其相连的链路出现 了阻塞： 曲经处理后，等级c 和等级b 超额流的总速率大于链路的可用带宽 ( u n r e s e r v e d r a t e ) ，即f w d r a t e n 】+ a d d r a t e n 】 u n r e s e r v e d r a t e ； b ) 等级c 或等级b 超额流量的接入时延超时； s t q 的队列长度超过了缓存器的低拥塞门限( s t q l o w t h r e s h o l d ) 即 s t q d e p t h n 】 s t q l o w t h r e s h o m ： c ) 等级c 和等级b 超额流量的总速率超过了速率的低拥塞门限 ( r a t e l o w t h r e s h o l d ) ，f w d r a t e n 】+ a d d r a t e n 】 r a t e l o w t h r e s h o l & 公平速率计算及f c m 帧的生成和传送 公平性算法的f c m 帧存在两种类型，分别用于支持单拥塞点( s c ) 和多拥 塞点( m c ) 。支持s c 的f c m 帧以老化间隔( a g i n g i n t e r v a l ) 周期性地传送，携 带着最拥塞节点的地址信息，在反向环上以“跳( h o p ) 的方式传送，最后在接 收节点由公平性控制单元( f c u ) 处理。其实现方式如下文的公平性算法实现流 程所述。 支持m c 的f c m 帧每隔十个计算周期生成一次，每隔十个发送周期在反向 环上以“广播”的方式传送一次，并在接收端由f c u 接收后将信息传给m a c 客 户层处理。它包含了网络上所有拥塞节点的源m a c 地址信息，实现方式如下： 当计算周期超时达到十个后，只要运行于某节点的公平性算法监测到拥塞，就会 在接下来的恰当的发送周期将计算的公平速率值和该节点的m a c 地址置入f c m 帧，并发送给网络中的其它节点；如果未监测到拥塞，就将f u l lr a t e 和该节 点的m a c 地址置入f c m 帧，并发给网络中的其它节点。 允许传送速率的确定 在公平性算法中，节点的允许传送速率由收到的f c m 帧中的公平速率值、 上一计算周期内节点的允许传送速率以及节点归一化因子和斜率因子等决定。 7 重庆邮电大学硕士论文 1 2 4 2 公平性算法研究现状 r p r 标准【4 j 中采用了基于反馈拥塞机制的公平控制算法：当拥塞发生时，将 拥塞站点( 检测到拥塞发生的站点被称为拥塞站点) 的本地发送速率作为反馈控 制速率广播给上游站点，上游站点用接收到的反馈控制速率来控制环上的注入速 率。由于上游站点接收到的反馈速率均相等，保证了它们向环上注入相同的流量， 从而实现了带宽分配的公平性。但此算法存在一些未解决的问题：首先，当环上 存在非平衡流1 3 2 i 时，该算法存在永久性的振荡，振荡性降低了吞吐量，增加了延 时抖动和丢包率；其次，由于控制包在环路上的周期广播和链路的传播时延，此 算法会经历较长的收敛时间：同时单发送队列的设置还会造成h o l l 3 3 】问题等。为 了解决这些问题，有许多研究工作对该算法进行了改进。其中文献 3 2 】提出了 d b r r 算法【3 2 】，基本思想是拥塞站点对经过的所有汇聚流进行基于g p s 2 0 1 的虚时 间计算，虚时间的计算是为了准确得到每个汇聚流的公平速率。在理论上d b r r 是一种很好的公平性算法，但是由于它是通过定期对经过拥塞站点的所有会聚流 统计字节计数来估算会聚流的到达速率和虚时间，这种估算存在较大的误差，同 时也带来了额外的处理开销。文献 3 4 】提出了m c s r p 算法，其基本思想是在每 个站点构造接入树以及拥塞链路相关的树干集合，同时拥塞站点将来自不同接入 树的数据包放入不同的虚拟输出队列，再对这些虚拟输出队列采用d r r 公平调 度保证接入树在拥塞链路处公平分享带宽，该算法采用非线性控制来减少业务量 振荡，提高稳定性。但由于该算法要求拥塞站点为所有连接树设置输出队列，同 时在它们之间进行公平调度，大大增加了站点的处理负荷，这使得该算法在高速 r p r 网络中难以实现。 1 ) d v s r 环网分布式虚时间调度d v s r l 2 0 ( d i s t r i b u t e dv i r t u a l t i m es c h e d u l i n gi nr i n g s ) 的思想就是为每个节点都设置一个远程公平队列，即每个节点通过发送分组包通 知上游节点来远程控制它的上游节点。该反馈速率就是分组包在g p s 系统中接收 到的服务速率。 图1 5 是d v s r 单节点理想模型【2 0 1 。它表示了节点缓存排队速率控制器的站点 业务和调度缓存器排队发送业务的相对关系，图1 5 中的g p s 是一个理想的可变的 服务器复用器。当进入节点的业务流超过某一范围时，业务以速率控制器的速率 进入调度缓存器。当g p s 服务速率小于d v s r 中的速率限制器的值时，调度缓存器 将实时发挥作用。 8 第一章绪论 r a t ec o n t r o l l e r n o d eb u f f e rs c h e d u l e rb u f f e r 一一一一一一一一一一一： f e e d b a c k 图1 5d v s r 单节点模型 ( n o d eb u f f e r ：节点缓存：r a t ec o n t r o l l e ，：速率控制器；s c h e d u l e rb u f f e r ：调度缓存) 。 为了达到这种公平速率控制，d v s r 要知道每个节点的业务需求。然而，由 于带宽分配的分布式特性，及业务的动态性和链路广播时延，使获得每个节点的 业务需求信息非常困难。因此，节点使用每个入口字节计数器来计算上游节点的 到达速率和本节点的速率。d v s r 认为计算得到的到达速率就是上游节点的要求碍 速率，公平速率就是基于计算得到的到达速率。这一使用改善了带宽的振荡，收 敛时间和吞吐量。 d v s r 算法中对于公平速率的计算复杂度为o ( n l o g ，n ) 【2 0 】，此处是一节 点处流的数量，而r p r 算法的复杂度为o ( n 1 3 5 l 。而且，在下游节点计算的业务? 量可能不是上游节点带宽需求的准确值，因为上游节点带宽需求还受到广播公平黔一 速率和可用带宽的限制。此外，像r p r 一样，d v s r 仍然依赖于速率的反馈控制 来达到公平性接入，不可避免地引入了较大的接入时延。 2 ) v q 为了减少d v s r 的计算复杂度，提出了v q 3 5 】( v i r t u a lq u e u i n g ) 算法。一个 v q 节点使用与d v s r 相同的计数器来计算上游节点到达的速率。而且，v q 通 过从前一控制间隔发送小于和大于公平速率确定节点的数量。到达速率小于公平 速率的节点称为输入受限节点，而到达速率等于公平速率的节点称为速率受限节 点。v q 从可用带宽中减去输入受限节点的速率后，将剩余带宽除以速率受限节 点的数量，结果就是公平速率。此过程除了不需要对到达速率排队外，与最大最 小算法相同p 5 j 【3 6 1 。v q 在到达速率和现有公平速率间，应用了线形比较，因此v q 的复杂度是o ( n ) 。而且v q 还减少了d v s r 的不公平性问题。当未使用带宽为6 ， 速率受限节点数量为s ，v q 就以舳增加公平速率，而d v s r 以6 增加公平速率 9 1 。在文献 9 r p 的结果表明下游节点的不公平性比d v s r 少。但是，由于v q 使 用了与d v s r 相同的机制来估计用户的需求量和速率广告值，因此v q 也具有与 d v s r 相同的缺点，如需求估计的不准确和大的接入时延。 9 重庆邮电大学硕士论文 3 ) v s q v s q ( v i r t u a ls o u r c eq u e u i n g ) 3 8 】不仅确保了公平的接入而且还最大化了环网 每段链路的吞吐量，解决了r p r 中的饥饿问题。v s q 算法为每条流分配虚队列， 通过每条流控制接入，达到了各种流的分离。对于节点的环网，每个节点在转 发缓存器处最多有- 1 条虚队列，且根据节点的优先级为各节点分配不同的权值， 以达到保证q o s 的目的。v s q 这种接入控制机制中，“虚”是指在实际中所有的 队列都共享同一条物理缓存，而“源队列 则是指虚队列通过它们的业务源节点 来标识的。 v s q 的拥塞控制采用o h b ( o n e h o p b a c k p r e s s u r e ) 方法。由于r p r 标准中 要求转发通道无损，即一旦分组包进入网络，在正常运行下就不允许随意丢弃， 因此也保证了转发缓存器不会溢出。在v s q 中，转发缓存器是由多条基于源的虚 队列组成，且该机制了解每个源对转发缓存器的占有量，能够有效避免拥塞。这 样，就不需要像r p r 有明确的公平速率估计和反馈。 算法中为每个虚队列都设置两个门限：高门限和低门限，且高门限大于低门 限。如果每个节点以它的公平速率发送信息，就不需要建立队列和进行拥塞控制。 反之，如果节点发送的业务超过了它的公平共享部分，该节点的队列长度会增长， 而且机制直接控制此源队列。当节点刀的队列，长度超过高门限时，节点n 就会 向节点刀1 发送反馈控制信息o f f i 。o f f o 表示在节点力1 处队列f 的业务过多， 会导致下游节点n 的缓存溢出【l2 1 。即流f 超出了它在节点玎1 和n 间链路的公平 共享部分，因此节点仃1 停止为队列服务，以减少流f 的传输速率直到节点疗1 接收到从节点刀来的o n i 信号。当节点玎的队列f 长度低于低门限时就触发了 o n i 信号。o h b 机制的控制非常简单有效，仅需要在接收和传输分组时检查队 列长度。 但是，对于动态转发缓存的管理和映射q o s 参数到转发缓存器的门限设置， 该算法仍需进一步的研究。 4 ) l a o f r 基于站点粒度的线性逼近最佳速率的公平算法l a o f r 3 9 1 ，该算法不是直接 将反馈控制速率作为本地限速速率，而是控制本地限速速率逼近一个最佳的公平 速率。它符合r a s 公平性评价准则。基本思想是在所有站点都设置了高低两个 速率阈值，算法只是用接收来的反馈速率作为判断拥塞是否出现的依据，并不直 接将它作为本地的限速速率。即如果接收到的反馈速率小于链路速率，则判断出 现了拥塞：如果接收的反馈速率等于链路速率，则判断未出现拥塞。每一次的拥 塞状态向非拥塞状态的转换都会使低阈值( l o w t h r c s h o l d ) 提升到当前的本地限 速速率，而每一次非拥塞状态向拥塞状态的转换到会使高阈值( h i g h t h r e s h o m ) 1 0 第一章绪论 降低到当前的本地限速速率，这样经过几次有限的状态转移，高阈值和低阈值会 逐渐相互逼近，最终高低阈值、本地限速速率会收敛到同一个值，即为站点的公 平速率。本地限速速率的递增和递减过程都是由一个线性经验公式来控制的。 线性经验公式的表达式如下式所示： l n c r e a s e ：x = x + ( h i g h t h r e s h o l d - x7 ) y ( 1 1 ) d e c r e a s e ：x = x - ( x 一l o w t h r e s h o l d ) z ( 1 2 ) 其中：x 为本地限速速率，勋新计算出来的本地限速速率。瞒递增控制因 子，z 为递减控制因子。 因此算法的时间复杂度为o ( k ( m + ) ) ，其中k 为迭代次数，m 、n 分别为 每次迭代过程中递增或递减次数的最大值。该算法控制了本地限速速率变化的幅 度，通过阈值的相互逼近导致变化幅度的迅速减少，从而收敛到稳定状态。改善 了非平衡流情况或h o t r e c e i v e r 情况下永久振荡的问题，而且具有较快的收敛时 间，实现了站点之间公平分享带宽。 5 ) 几种算法比较 r p rm a c 协议公平性的具体实现，都是依靠m a c 协议公平性算法来协调多 个节点对报文流的控制来完成的。因此， 作从对链路带宽的静态分配到动态调整， 从国内外的大量文献可以看到，研究工 各算法都针对不同的性能指标进行了改 进。下面主要针对r p r 、d v s r 、v q 和v s q 进行比较，如表1 - 4 和表1 - 5 1 4 0 1 。 表l - 4 不同m a c 方案间的复杂度分析 r p rd v s r v qv s q l a o f r 公平接入 的速率控需要需要需要不需要需要 制 r p r - a m ：使用 线性经验公式 最拥塞点的始约为最大最小 约为最大最小 x = x + ( 1 噎g h t h , e o d d - x ) ro 公平速率发速率；公平速率公平速率 不需要 x f x - - ( x - 上c m 7 ，i 陀幻矗o ，z ； 的计算r p r c m ：可用 ( m 缸m i n ( m a x _ r a i n y 、z 分别为递增和递减控 带宽活跃节点 f a i rr a t , )f a i rr a t e ) 制因子 的数量 拥塞控制明确的速率明确的速率明确的速率不明确的明确的速率 机饲控制控制控制速率控制控制 v d q 的 最大数量 2 5 62 5 6 2 5 6o o 转发队列 的最大 22 22 5 62 致日 算法 复杂度 o ( n )。n l 0 9 2 n )o ( n )o ( n ) 。( k ( m + ) ) 重庆邮电大学硕士论文 l 入口计数无 有 有 无无 i 调度策略 优先级 优先级优先级 公平优先级 表1 5 不同m a c 方案间的性能比较 、 i 冲rd v s r v qv s q l a o f r 支持。 通过预留支持高优 是否支持多等级业务先级业务，同r p r同砌) r同r p r同r p r 通过公平共享支持 低优先级业务 是否满足空问重用是是是是是 是否存在l p 节点业务的饥饿现象是是是否是 是否公平性保证否否否是是 接入时延大大大小大 收敛时间大 中中 小小 转发缓存的占有量大大大小小 转发缓存占有变量大大大小小 从上面的表1 4 、1 5 可以看出各算法有不同的特点，较g a n d a l f 和a l l a d i n 算法都能够达到有效地公平性。对于d v s r 算法，由于其采用了良好的公平速率 计算方法和有效的信息传递方式，使得其在公平性、效率以及稳定性方面都得到 了明显改善，而且能够较好的处理输入负载不平衡的情况。对于v q 和v s q 算法， 它们都采用了虚队列模式，但是转发队列的容量明显不同，v s q 在公平性、稳定 性和收敛时间等上有比较理想的表现。而且对于l a o f r 算法，是基于传统线性 经验，较多的依赖于控制因子的选择。 1 2 5r p r 多阻塞点公平性机制 多阻塞( m u l t i c h o k e ) 机制应用于一个节点业务流的目的节点与阻塞链路相 邻的情况下，只要某个发送速率满足( 不大于) 源节点和目的节点之间所有拥塞 点的公平速率，就允许源节点以此速率向目的节点发送数据。多阻塞机制与单阻 塞机制最大的不同点是：多阻塞机制的m a c 客户层中包含有上游阻塞节点的信 息，而且能够利用这些信息来提高带宽和空间的重复利用。多阻塞机制知道并能 使用环路中相关的拓扑信息以及每一个m a c 客户层的目标队列。当某个阻塞节 点采用多阻塞算法后，在这个阻塞节点之后的所有v d q ( v i r t u a ld e s t i n a t i o n q u e u i n g ) 队列的a d dr a t e 值的总和被定义为t o t a la d dr a t e 值。这个值被看为与 阻塞点相关的a l l o wr a t e 的值。为了确定源节点是否能够发送业务到目的节点， 从源节点到目的节点所有拥塞点的计算值必须得到满足。为了进一步确定源节点 的业务流能够准确地发送到目的节点，多阻塞节点的公平值必须在源节点与目的 1 2 第一章绪论 节点之间的每一个阻塞节点间进行相关处理。而且，所有队列的总速率还须再与 m a xr a t e 进行比较。然后通过m a c 层把阻塞的最大范围的公平性告知所有相关 的节点。 一旦接收到使用信息( 多阻塞点公平帧m c f f ) ，上游节点调整它们的传输速 率，以避免超过传播的带宽使用值。这主要通过扼制环路上始发的数据包来实现。 阻塞节点接收广播的使用值，传播最小的传输使用值和广播的使用值。 多阻塞概念处理了“希望向距离出现拥塞的链路更近的节点发送流量 这一 情况。假定节点l 希望向节点2 发送流量f l o w o ，2 ) ，而同时节点2 和节点3 之间 的链路为拥塞链路，此时r p r - f a