（通信与信息系统专业论文）对基于rpr技术的城域网方案中公平算法的改进与研究(1).pdf

摘甏 随着i n t e m e t 的超常规发展，网络所承栽的业务流量发生了很大的 变化。面临着这蟪改变，现有的城域网技术也渐渐暴露出了很多问题。 远鼹年泰各葶孛裁一代畿城域跨技术屡交不穷，其中殍蛙分组数据环 ( r p 瓢r e s m e n t p k e t r i n g ) 技术以其技术的先进性，投资的有效性，一 盘 能的优越性，支特业务的多样性，提供了一介很好的解决方案。 本论文以r p r 的公平算法为研究对象，研究了几种不同的公平参考 模型的优缺点，从理论务仿真蕊方面分析了r p r 草案算法的公乎杖及 英他挂镌。蓰垂了一静改透的公平算法，莠鼠仿真结果上分斩了改进秘 算法的可取之处。祈算法在空间重用，抖动和收敛性上都有所改进。雷 先，它能够为肿r 网络提供觅好的公平性。其次，改进的算法能够迭 到更好的空间重用。最后，它在搏动和收敛性上比起g a n d a l f 算法有所 改进。 关键词：弹性分组环城域网公平算法定间复用环回 a b s t i 认c t a l o n 譬w i t hm e 廿；m s n o m l a ld e v e l o p m e n to fi m e m e t ， t h e r ea r e t r e m e n d o u sc h a n g e si nt h en u x e so f 吐l eo p e r a t i o nw h a t 廿1 en e “v o r kb e a rt h e 、e i g h to f _ f a c et l l e s ec h a n g e s ，t h ec u r r c l l tt e c h n i q u eo fm a ne x p o s e dal o t o fp r o b i e m sg r a d u a l l v n e a rt w oy e a r s ，a l l 王【i n d so fn e wt e c l l i l i q u e so fm a n e m e r g e di ne n d l e s s l y a m o n g 恤e m ，m et e c h n i q u eo fr e s i l i e n tp a c k e t r i n g ( r p 鼬p r o v i d eap r e f e r a b l es o l u t i o nb e c a u s eo fi t sa d v a n c e dt e c h n i q u e t h eu s e 如l n e s so ft h ei n v e s 恤1 e n t t h ea d v a m a g eo ft h ec a p a b i l i t y ，a n dt h e v a r i e t yo f m eo p e m t i o ni ts u p p o r t s t h et e c h n i q u eo fr p ri s l er e s e a r c h m lo b i e c to ft h i sd i s s e r t a t i o n ，i n t h i sd i s s e n a t i o nis t l j d i e dt h em e r i ta n dm ed e m e r i to fs e v e f a ld i f f b r e m r e f e r e n c e dm o d e lf o rf a i ra r i m m e t i c ，a n da n a l ) r z e dt 1 1 ec a p a b i l i t i e so ft h ef a i r a r i t h m e t i co ft h ed r a rf b mi t st l l e o r e t i c sa n d 协er e s u l to ft l l ee m l u a t o r t h e nip u tf o n v a r dan e w 锄e l i o r a t i n gf 撕ra r i m m e t i c ，a n da n a l y z e di t s s a v i n gg r a c ef r o mt h er e s u ho ft l l ee m l u a t o r t h en e wa r i 也m e t i ch a sm a n v a m e l i o r a t i o n si n s p a t i a lr e u s e ，d i t h e r i ng a n da s t r i n g e n c y f i r s t ，i tc a n p m v i d eab e t t e rc a p a b i l 岫o ft h c 筋ra r i t l l i n e t i cf o rm en e tw o r ko fr p r s e c o n d ，i tc a l ld ob e t t e ri ns d a t i a lr e u s e l a s t ，i tm a k e sa m e l i o m t i o ni n d i m e r i n ga n da s t r i n g e n c yt l l a i lm ea r i t l l m e t i co fg a n d a l k e yw o r d s ：r e s i l i e n tp a c k e tr i n gm a n f a i ra r i t h m e t i c s p a t i a lr e u s ep r o t o c o lr i n gw r a p 第一章绪论 1 - 1 下一代城域网简介 城域鼢溉念是由诗箕机网络演化螽采的，是臻余于广域嘲和局域网 之闻，丧城市及郊区范圈蠢实瑰信息待输与交换镌一辩两绦。从较严格 的定义来看，城域网跨接于长途网与接入网之问，它们在城域范围内( 即 企业间、局问的城域连接) 疏通业务以及传送出入汇接点( p o p ) 的业 务。其结果是，城域网受两个关键因素的推动，即用户要求和支持这些 要豢婚凌拳。城域塔境是逶售霹中蔽复杂戆嚣境，城域网的葶每点是，必 须包客各种不同的网络协议和信i 鼓速率。 今天的城域网威在发生巨大的变化，技术和用户的机制发生了转 变，城域市场正在迅速成为一个激烈竞争的场所。长途d w d m 容量与i p 带竟需求鲢剖增把城城斓掺到了十字路口。近每来，城域网中；l 入多秘 先透技拳，速率幂虢疑离，监务趋于多祥化。城域弼所提供的带宽已胰 15 5 m b p s 、6 2 2 m b p s 向2 5 g b p s 以技10 g b p s 发展。一些运营商不仅提供 更大带宽而且还向用户做出服务质量承诺。城域网正在朝替一个能够 承载话音、数据和视频等所有比特流的多业务嘲演变。要变成一个如须 包容鹭有协议、逮率务蓝务的孛阕环节，羹地姣炎得越券越蘩要。西毙， 曲须用新的思路、新的方案、新的技术去支持窀，不让城域网成为处在 a n 与w a n 之间妨碍发展的瓶颈。总的来说，下一代城域网应该满足以 下几个披术特点： ( 1 ) 域络侮系臻襁镪对i p 优化。 ( 2 ) 对i p 分组转发的优化一l 2d o m a l n 的扩展。 ( 3 ) 有效承载传统专线业务。 ( 4 ) 提供不同等级的q o s 服务。 ( 5 ) 具有可靠的稳定挂，自愈巍力葶口可扩展能力。 ( 5 ) 动态带宽分酝。 ( 7 ) 具有严格的搠寒控制和服务保障机制。 目前，城域网的解决方案十分活跃，有基于s 0 n e t s d h 的、基于 a t m 的，也有基于以太随或w d m 的以及m p l s 和胂r ( 弹性分级环技术) 等，其中，基于r p r ( 弹t 鎏分经蒡| ：技术) 酾城域鹅鼹决方案在来拳吴有 非常广阀的应用前景。 蕞1 2 基于r p r 的城域霹结橡及特性 众所周知，s 铡驸和以太斓都不是环形网络土处理数掇业务的理想 方式。s o n e t 在环形拓扑上既无优势可言，也不能有效的处理数据业务， 同时还浪费带宽。以太网尽管天生适合于数据传送业务，事实上却难以 虚环上实现，也幂绽充分引用瓤形拓 的藏络容量。 弹挫分组环正楚为满足双包为基砖鹤城城斓的需求蕊设诗戆一种 网络体系结构和技术。与建立在泓太交换或s 0 n e t 分叉复用基础上的 正规体系结构不同，弹性分组环以一种清洁的平台解决了城城网的瓶颈 问题。 露l ，l 基于r 摊爨城域残癌1 拜l 窭倒 r p r 在城域棱心被周来改进s o n e t s 醐或d w 陇环的数据处理特槛， 并具静非常快( 小于50 m s ) 的保护切换能力，更重要的怒它同时传送 m p l s 标签交换信息。r p r 核心使得网络的中心部分极具特包。除了传输 的可靠幢，它还能有效地保证中央环上疑各个节点公平地共享带宽。最 君，它减少了广播娩务对带霓姆要求，并且提供有效麓本魏e o s 争q o s 能力，是构成端到端q o s 解决方案的一部分。 r p r 物理层的烫活性允许它与旧的技术( s o n e t 、d w d m 甚至裸光纤) 很好地集成。在有s o n e t s d h 环存在的地方，r p r 能在s o n e t 环上全 部或爱部分逸狡部署。吝运营辩安装了瓣粼羧备畿，渚况下，r p 爻能麓 单运行在一个或者几个波长土。最后，在只有裸光纤的情况下，r 豫也 能直接运行在裸光纤上。所有情况中，在建立一个为数据优化网络的同 时，它都保持了一个独立的基础设施以支持谐音业务，我们可以认为基 础设施在物理层“收敛”了。这是一秘既切合实际又成本低窳戆声音和 2 数据融合方法。r p r 的协议栈层次如图所示： 0 ；l 参考模型胛r 分麒艇型 图1 2r p r 协议栈结构图 r p r 技术具备了新一代城域接入网应有的特点，其中包括： 技术的先进性 弹性分组数据传送以i p 业务为核心，适用网络发展的方向。r p r 充分简化网络层次，避免了a t m 和s d h 层的开销，提供了空间复用技 术和统计复用功能，保证高带宽的高利用率，相对t d m 网络可提高带宽 利用率3 4 倍。 网络的可靠性 r p r 的网络具有完善的网络性能监测、错误定位等网管功能。现在 的r p r 的设备都采用数据通道和控制通道冗余备份设计，保证了网络设 备运行具有电信级的可靠性。当光纤中断或网络设备发生故障时，通过 50 m s 的环自愈和快速倒换保护关键业务，并按服务等级依次倒换非关 键性的业务。 可管理性 r p r 能根据配置信息自我设置， 设置、计费、动态的带宽管理功能、 还支持综合电信管理标准的故障、 性能监测和安全( f c a p s ) 要求。 质鼹保证( q o s ) r 拣提供多等级、可靠戆分级黢务，q o s 抵裁可以在高速竞网络层 入口出口的接臂处提供延时控制、数据包丢失和各种混合业务类型的 运营横式，并提供必要的带宽保证。 支持传统业务 r p r 支搪语音业务，可以对囊搂支持t l e l ，或孝对语音信号分纽 暑( 倒如i p 纯后) 傍输，满足缔统韭务需要的q o s 和接昝燕拳，使得 传统业务能逐步地转移到为专门为传输数据而优化的光网络上，网络运 营商在建设了面向i p 为核心的城域网的同时，既可提供v o i p 业务，又 可承载传统的p s t n 业务。 谯成拳 弹性分组环技术通过最恍路径选择、空问再剥用、统计复用和两个 同时工作的环路，最大程度地提离光环路的工作能力，将初期和增长投 资都降到最低。r p r 设备高度集成，能提供了低成本的运行管理、维护 争操馋费焉。 蓑容性 各厂家弹性分组设备都支持标准的接口1 0 1 0 0 b as e t 和千兆以太 网接口，有的还支持e 1 t 1 和s t m n 。 以游性分组环技术为基础的城域网可以提供语音、专线赃务、各释 数据蓝务的支耱，提铥了三圈合一秘乎台基硪，对于电信簿绔运营孝， 尤其是不断涌现的新电信运营商来说，弹性分组数据环( r p r ) 技术以 其各方面的优势提供了一个良好的i p 城域网蛆网方案。虽然目前众多 厂家产器都有着自己特点，相曩之间存在兼容互通问题，但随着 i e 疆8 2 1 7 协议括漆戆更蘸寿蠢密，颈诗r 熬技术将以英备方面疑优 势，在新一代城域嗣妁建设中得到广泛应用。 1 3r p r 的关键技术 ( 1 ) 网络拓扑结构 瓣r 麓拓卦鳃稳是一纽滔藩双巍环路菇联溺酶突羧节点，与 s o n e t s d h 不同的是，它的反方向传输的双环都是工作环。r p r 环最基 本的优点就是每个节点都能假设认为环上所传避的包最终娜能到达目 的节点丽无论到底是选取环上哪一条路径。既然节点“知道”在环上只 需要三释包楚理功穗：撞凡( 巍环蠹增加包) ，嚣囊( 黄向发送龟) 争 分离( 扶环上取出包) 。这减少了筚个节点闻的相互通信研必须进行的 工作蚤，尤其是相对于网孔网中静个节点都必颓决定对每个包的出口端 口做出决定。 蹲1 3 双向分璧珏环 为了在r 粮环路上连赣翱邻秘节点，可缓采强各释底层臻龠，如如 一对裸光纤、一对自w d m 链路分插出的波长、一个s o n e t s d h 可拆卸 o c n 电路以及其它双向连接媒介。以该喜莓扑结构为基础，每个r p r 节 点支持两个环端珏：一令支捻与左逮邻近节点的连接，薅一令支持与右 边节点餐连臻，节点设霉掌穗赫争端口鳃竞路狡态。 在网络初始化或者拓扑燕新的过程申，r p r 进入自动拓扑识别横式， 所有节点基于4 8 b i t 物理编码模式向环中赫余各节点发避信令分组，告 知自己所掌握的据扑信息。每个节点据此来磷定此时的逻辑拓扑结构， 并遗过一定黩确认瓿巷 傣证所鹰节点信急的一致蛙。这和 p 中0 s 疆煮 类似之楚，不麓患在于嚣者建l 8 y e f 2 渣惠，对h y e r 3 路由表没有影响， 并且更新速度更快。拓扑更新过程结束詹，每个节点都掌握了到其它所 有节点的链路擞阿与状态，因此当故障发生时，r p r 环可以进行基于滁 路由砖故障嘲换。 骚环还支持其它灵活的组露影式。在楚莩霹蕊络环境下，圣。丧一 个很小的范圈内或者对网络盘存性要求较低的情况下，可以采用单丸纤 工作方式，当然这时没有自愈劝能。r p r 环除了可以遴明地支持w d m 传 送方式，还可髓通过适当的设计应用w 喇波长选路方裳，大大增加隈婚 蕙带宽。在鬟交给8 2 7 工嚣纽薛各静苹索中筑毒秘美姆方案设计。 ( 2 ，r 魏的蔑葳和保护机制 网络的生存性( 或称弹性) 是指网络能承受设备和线路故障的能力。 业务恢复时间和范围是度量生存性的两个爨要尺度，不同的业务等级对 莰复对阕套范嚣蠢不舄戆要求，大量鲢瑟究袁甥，如暴照务中鼙霹瓣幂 超过50 m s ，对于多数电路交换网的实时话音业务和中低速数据业务来 说不会造成服务质量( q o s ) 的下降，因此把5 0 m s 作为衡量传送网生存 性的重要指标。 在各种能够提供不同程度生存能力的通信技术中，只有s 0 n e t s d h ( 或者借鉴了s o n e t 自愈技术的w d m 光交叉连接网络) 能够提供50 m s 中断期内电路通信服务的能力，其基本思想是按双光纤配置环网络，其 中一个是工作环，另一个备用。当工作环断开时采用高效a p s 通信协议， 通过s d h 开销中的k 1 ，k 2 字节通知上下游节点，业务在光纤中断处两端 节点通过保护光纤环回。这样的不足之处在于备用光纤的带宽没有充分 利用，同时环处于保护状态时连接没有选择最佳路径。 在r p r 环网中，两根光纤都是工作纤，没有主备用之分。在一般情 况下，给定两节点之间的数据分组和信令分组反向传送，当发生光纤中 断时，节点光纤入口物理层设备检测到错误并将该信息通知m a c 层。如 果该错误信息确认，那么每个受影响的r p r 节点将会执行一个故障覆盖 ( f a i 卜o v e r ) 动作，把故障路径方向的数据流到切换到反方向光纤， 同时发出一个l a y e r 2 控制信令分组通知其它节点。其余节点收到这个 信令分组后( 有可能不只一个节点发出此分组) 也把所有业务转移至有 效环上。r p r 的这种基于源路由的保护倒换机制可以实现把数据转换到 最佳路径上去，另外，由于r p r 支持空间重利用协议，可以节省出 s o n e t s d h 复用段保护倒换所经过的环回路由的带宽供其它业务使用。 同时，在保护切换过程中，会按照业务流的不同服务等级决定倒换次序 和带宽分配策略。警报通知和重定向数据流都将在故障发生后的5 0 m s 内完成，弹性分组数据环中的“弹性”就是指这一特点。 图1 4 光纤断裂时的恢复 ( 3 ) 空间重利用协议( s r p ) 顾名思义，s r p 的基本思想是在空间上没有重复的业务流可以互不 影响地利用各自线路的带宽。s r p 与以往的令牌环和f d d i 的一个重要 区别就是单播分组在其到达目的节点之后即从环上剥离，只使用源与目 节点间的线路，并不锁定整个环，其它节点间的通信可以同时进行。这 样使得许多节点可以同时发送分组，提高了环带宽利用率，特别是环上 节点较多的情况下，带宽利用率的改善尤为明显。图1 5 所示为运行 s r p 协议的r p r 环网。由图1 5 中容易看出，在不影响其它节点通信的 情况下，3 5 的通信可以使用这两个节点间光纤链路的全部带宽。 图1 5s r p 示例 ， 凭借源路由保护倒换机制和空间重利用协议，r p r 处理业务的速度 有可能达到s o n e t s 明双向线路倒换环或单向通路倒换环，原因有两 个，一是选择了分组传送路由的最佳路由，二是同一时隙在不同网段上 可以传送不同的数据。 ( 4 ) 公平带宽 为了适应城域网客户种类繁多、交换粒度差异大的特点，r p r 必须 有一套灵活的带宽动态管理、拥塞控制和多等级承载业务o o s 保证机 制，能够比s o n e t s d h 更加有效地分配带宽，处理数据，从而降低运营 商和客户的成本。 r p r 环同时具有内在的优势来实现公平带宽算法来管理带宽使用。 环内带宽作为一种共享资源易于被单个用户或网络节点所占用，造成 “公共悲剧”。公平带宽算法就是一种能让每个用户公平享用环内带宽 的机制，能理想地不受支持电路的束缚。环一级的公平带宽算法能够也 应该是带宽这种全局资源分配环内带宽。 带宽政策在无拥塞时能在任意两个节点之问最大限度的利用最大 环内带宽得以实现，且具备以固定电路为基础的s o n e t 系统所不具备的 灵活蛀，霜露，比点戴点救太强更葵效率。 s 0 琵l 存在鳆阕题楚：虽然窀龟巍实魂魄羲鬟点电薅为穗互联缭分 配争预定溺定戆带宽，经帮缺厄灵活牲。增加或减少带宽需要对静电路 进行手工分配，翻对预留屯潞也套造成带宽浪费。 在一个业务模式动态变化的网络中( 典型的如所有以包交换形式传 输业务的网络) 在不丢弃此务数据的情况下具有一种方式使网络得到最 佳利用，即网络具有内建的反馈机制。这种反馈机制提供网络可用业务 客量，以便调节进入网络的业务速率。 每个节点上的m a c 实体j 荛视其上即时链接的使用情况，同时将信息 通知环内所有节点。每个节点就能决定是接受更多数据或是减少进入节 点的业务量。这种高效的带宽使用能使r p r 达到其总带宽利用的9 5 。 以太网交换或s o n e t 分插复用结棉不具备带宽管理能力，因此，不 能最大限度酶剥用甄络容黧能力。 如下图，在左边的交捩链审，我们奄到节点d 易于受到节点a 、8 、 e 带竞搜塌方式的影嚷。疆太网交换典鍪戆在鹭有臻八端曰申公平分鹣 输蛊端口带宽。镧知，如麓每令节点惩在上午8 点翻1 2 点之间窃蔗联 熬发送2 g b p s 的韭务，群么，节点e 、d 倪匏传送l g b p s ，节点b 将能 传送5 0 0 m b p s ，而节点c 、d 倪能传送2 5 瓤b p s 了。随着链申节点数的 增加，以太网交换对节点的幂公平性变得更加显著，尤其是对上游的节 点。 豳1 7 套廊秘平和公共“恶剧” 一个解决方案就是在数据键路层实现每个节点的数据限制。例如， 每次交换进入通道的业务可能限制在5 0 0 m b p s 。但是数据链路层的数据 限制政策并不能转化成奎局公平政策，同时产生了一种支持和效率问 题，即s o n b t 电路一样面对的尽力而为数据业务问题。如果在凌晨4 点， 没有其他人在占用带宽，那么节点d 的业务速率就无须限制在5 0 0 m b p s 。 在右边的r p r 环上，将十分容易的实现全局公平政策，因为r p r 环 在整令繇一级实现公乎政篡，赫幂是在单独的链接楚。服务露熊够嘲定 女霆弼疆管理麸上游或下游节点而来并与嚣节点包穗关砖包燕务戆耱发 速率，知诧，知暴鞲建带宽蜜澜，剩d 节点能鑫由转发馥需要蛹包。另 一方面，如果节点a 到c 都冬是使用1 0 0 淞p s 速率，那么r 拣环熊遗过 控制源一一转发关系自动限削节点d 发出的包的数量。 ( 5 ) 广播或多点广播业务 r p r 环天生适合于广播和多点广播业务，如上图所示，对于筚播且k 务，r p r 环上的节点通常可以选择从环上分离出包或转发它们。然潲， 对于多播业务，节点仅能简单的收包并转发，直到源节点分离出包。遮 使得在环上仅传送一份复制电就能实现多点广播或广播功能。 此侧中，源节点s 想以广播方式将一个包传到目的节点d 1 一一d 4 。 若使用p o s 网络，s 必须特此包复制并分别送至各个供应电路。而农一 个r p r 环内，潦节点s 只需在环上传送一个包，各d 节点接收并转发。 在此倒中，r p r 环穗对于k 瓣环对于相同酶多点广播业务，仅使用了 驾分之一砖带宠。 图1 88 0 n e t 与r p r 环多点广播业务 ( 6 ) 简化的服务配置 定制数据服务砖客户遗渗会匏怨等待运营商霞运服务镌嚣孛壤太长， 逶掌蹿于b s i 争b s 3 袋务，繁德簿翘一觳爰6 令星襄蜀5 令冀琴擎，而 狂一3 速率或曼毒速率戆簸务到要等更长。 这种等德服务提供的惩辩童要可归因于基破s o n e t 结鞠和妫n 驸以 电路为基础的供应模式。创建一个端到端电路需要采取许多步骤：首兜， 网络运营商要使电路物理端点尚管理系统一致。然后，运营商要队环内 每个节点对所有请求和进行插分五联进行配置。这种供应的操作楚极为 耗时且劳动密集的。 新型的s o n e t 系统能自动究成一些供应步骤，但是网络运菅商仍然 需要对环内带宽的优化利用避行手工业务工程操作。而且运营商必须清 楚地认识到网络拓扑、环内业务分发和每次链接由电路遍里的可用带 宽。以太网交换网络上服务供应会好一些，因为它们不需要在每个节点 提供电路。但是，节点上有时仍要供应电路。另外，如果服务商希望在 网络上提供s l a s ，运营商仍然需要采取手工网络通信业务工程的工作。 与此相比，一个弹性分组环系统则能提供简化的服务模式。在一个 r p r 系统，环作为一种共享媒质，环上所有节点共享分组环上的所有带 宽。各个节点对环上可用容量都可见。因此，提供一种新服务简单得多， 而不需要进行逐点、逐段的容量计划。工程计算和供应演习。网络运营 商只要当业务通过环的时候简单鉴定出数据流，并专注于应有的服务质 量。 1 4r p r 的特点与发展现状 从国内外网络技术发展趋势来看，采用分组环技术组网开始成为城 域网建设的发展趋势。弹性分组环技术是一种全新的为i p 数据业务设 计的光纤传输技术，采用环行组网技术，将数据、话音、图象业务合一， 并解决了q o s 分类、环保护等问题。在具备了千兆以太网比较经济的特 点的同时，帧封装比p o s 更为简化和更灵活，同时具有空间复用机制和 5 0 m s 环自愈保护特性，分组环设备可以承载具有突发性的i p 业务，有 的设备还能支持传统语音传送，是适用于中小型城域网骨干到接入和大 型城域网接入的技术。 目前，虽然r p r 工作组还在进行r p r 标准指定和测试工作，r p r 的 正式商用还要在一年以后，但由于预期的良好市场前景，许多公司都已 推出了不同的非标准r p r 城域交换产品，以期在激烈的市场竞争中占的 先机。最具代表性的产品有c is c o 的d p t s r p ，n o r t e l 网络的i n t e r w a n ， 以及l u m i n o u s 的p a c k e t w a v e 等。相应地，一些大的半导体生产厂商也 推出或即将推出r p r m a c 层芯片，比如v i t e ss e 与n o r t e l 合作，推出的 支持g f p 的r p r 芯片v s c 9 12 9 ，c o n e x a n t 推出了c x 2 9 9 5 0 r i n g m a k e r 环 路处理单元。但在正式标准未出台前，以上方案都属于前瞻性的技术。 虽然每个供应商都承诺，一旦新标准出台，就改造其产品以符合新标准， 但在规范形成前造就事实上的工业标准以影响标准的制定也是所有厂 商的目的。 弹性分组环技术都采用环状拓扑，双环结构。外环顺时针和内环逆 时针同时双向传输数据，有的r p r 技术支持各环分别传输各自的数据和 控制信息，有的厂家则支持各环传输另外一个反向环的控制信息。 r p r 是一种新型的网络结构和技术，是应下一代m a n 的要求而设计 的。r p r 一经提出，便受到各方面的青睐。然而，该技术还处于早期研 究与探索阶段，相关的m a c 和p h y 还需进一步的标准化。但是由于其集 i p 的智能化、以太网的经济 生和光纤环网的高带宽效率和可靠于一身， 业界普遍对它的市场前景表示乐观。相信随着标准化工作的进一步开展 和市场的进一步扩大，r p r 妊将成为满足新一代带宽i pm a n 所采用的 最佳技术之一。 1 5 本文工作简介 在对r p r 工作组所提出的草案算法的改进工作中，重点在于找到导 致草案算法收敛时间长、抖动性大的原因，这也是本论文中的难点之一。 由于算法草案在佘平控制速率的设置上存在不足，使草案算法在不平衡 业务条件下网络的可靠性与传输质量降低。 基于草案算法中存在的问题，通过细致的研究工作，本论文在大量 仿真试验的基础上对草案算法进行了改进，改进后的公平算法在信道利 用率、收敛时间、算法抖动性各个方面均有很显著的改善，结论以仿真 试验的方式加以证明。 1 、在第二章，论文中介绍了几种因特网中常用的公平参考模型， 并选择了e dk n i g h t l y 的r i a s ( r i n gi n g r e ss a g g r e g a t e dw i t h s p a t i a lr e u s e ) 公平机制参考模型作为本论文中的参考模型， 以便在此基础上对草案算法和改进后的公平算法进行比较和研 究。 2 、在第三章，在前一章的基础上，论文详尽的讨论了草案算法， 并以g a n d a l f 算法为主，在o p n e t8 o c 上，对草案算法进行仿 真试验，找出草案算法的不足之处，并分析了产生这些问题的 原因。 3 、在第四章，针对上一章中的分析，提出了一种改进的公平算法， 以c 语言完成了算法的编程，详尽的描述了改进后的公平算法 的流程。 4 、在第五章，介绍了仿真软件n s ( n e t w 0 r ks i m u l a t o r ) ，并在这 个仿真软件环境下，对算法草案中的公平算法和没有公平算法 控制的千兆以太网与改进后的公平算法进行仿真和比较，通过 实验证明，改进后的公平算法在信道占用率、收敛时间和算法 的抖动性各方面均有很大程度的改进。 5 、在第六章，对论文的全文进行了总结，并对将来的可行性工作 提出几点建议和参考。 本论文比较详细的研究了r p r 技术中的公平算法，改进后的公平算 法通过仿真试验证明取得较大的成功，对草案算法的改进非常显著，希 望我的工作能够在r p r 技术的普及和推广中有所帮助。 第二耄基于r p r 的公平参考模型 公平疆是一令跑嫒镁壤黩溉念，霹予网络资嚣拳巍，知留分配来 说才是公平砖，并没有一个比较统一的定义。本章在r p r 环璃的基础上， 研究了环网中的带宽分配公平参考模型，从而为公平算法的设计确立一 个熬准。 2 ，l 因特网中的公平带宽分配奉几制 因特网的带宽分配一向是个非常重要的研究课题，在因特网的网络 应用中，占用带宽的多少直接影响到了它所能获得的服务质爨。因特网 警宽资源共享的主要秘标是集成链路上的滤营采统计复用带宽。通常带 宪共享有旺下死毋影式： 多协议链硌共事：在多种协议共存的翔特网中，应该劳止巢令协议 族在使用共有带宽时得到额外的收蘸，从而使其他协议旋爱到排 斥。 多服务共享：在同一个协议族内存在不同种类的业务，各种业务之 闭符合一定规则的带宽分配原则。 多实体链路共享：一条链路被凡个髑户共箴攘有争使用，莠丧共同 争霸带宠霉雩受鬟菜葶争协毒好的控铡；筠不发生争躅露，装令髑户可 以使用全部空阉的带宽。 在各种带宽共享的模式下，尽可能使用网络的带宽资源并做到在共 事的各方中的公平是一个很重要的目标。但是，从不同的角度出发，对 公平性都有其不同的理解，几个比较著名的公平模型是m a x m i n 公平模 型和p r o p o r t i o n a l 公乎模型。 2 1 。2m a x m i 珏公平横激 m a x m i n 公平模慰 13 【1 4 】【15 】 1 6 】是数据网络中经典的共享原 则，其目标是要在客蚤限制下使最小的带宽需求用户获得尽可能大的网 络带宽。m a x m i n 公平分配机制规定：( 1 ) 用户不能占用超过其自身需 求的带宽，2 ) 没有冀他的分配方式能在满足条件一的情况下嚣更小鲍 带宽分配率，( 3 ) 当我们把最小需求的用户从网络中移除，同时相应把 系统资源总量减小，条件( 2 ) 仍能得到满足。假设网络带宽的总量为 u 。每个用户的带宽需求为p 。，每个用户最后得到的带宽份额为u ， 那么m a x m i n 公平模燃用式子表示即：u 。，一u 。，u 。把谈奈件简 化屠，弦为：u ；= 赫i * ，p ；) ，这里鲢。被设为满足u 。；，；u ：。 2 + 1 3p r o p o “o n a 】公平模型 这是一种由f k o l l y 提出的公平分黼机制 12 】。他假设用户在带 宽分配为r 。时的收益岛l o g 成正比，当带宽分配r t 满足约束条件i e e 鸯菠_ 黪总容量) 并婕l 。g # 最大托舜，舔英带宪满足 p f o p 。r t i o n a l 公平。在有限的链路和路径下，存在唯一符合 p r o p o r ti o n a l 公平的带宽分配，且对其他可行的非负带宽分配_ 符合 p r o p o r ti o n a l 公平的带竞分配有以下性质： y 亟二塑 _ r ( 2 。i ) 这两种公平模型都是以链路的多察体共享作为考虑前提的， m a x m i n 公平模型保证了首先满足带宽需求小的用户的利益，而 p r o p o r t i o n a l 公平横型则优先考虑对网络资源消耗最小的用户利益。 2 。2 颦网孛的公平謦宽分配撬翻 2 2 1 全局公平与链路公平 由于网络之间的蔗挎性，因特网的公平带宽分配机制与环网中的公 乎带宠分配祝截所考虑螗侧重点是有爨不麟的。因特网申的协议争流量 酶复杂洼安定了其实筑公手带宽分配的潮雄。而嚣网虫于葵蟊0 结麓砖 特点也决定了有其特殊的媒质访问控稍，从而新生出自己的公平机制。 环网的公平带宽分配机制可以分为全局公平机制和链路公平机制 ( s 】。传统的媒质访问控制协议是基于全局公平的。每个工作站都会得 到相同的带宽，不考虑它是否会影响到其他的工作站。而链路公平机制 ( 本地公平f 3 】) 能更好的保证节点间的公平及带宽的有效利用。下面 我们给出这两种公平机制的定义： 全局公平机制的定义：全局公平性基于这样一种机制，每个在环上 的节点都能获得相同的带宽，不考虑是否会影响到他们自己的流量。 链路公平机制的定义：链路公平 生是基于这样一种机制，只有那些 在传输过程中发生相互作用的节点会共享环网带宽，而其他的节点不需 要降低它们的吞吐性能。 图22 基于数据流带宽争用的链路公平 f 越s 鑫嚣n n 吣n2 d 4 挎e 捌h 舟嘲 e n o te 舯 &a m o 舶e 。 5 口 e瓣le 鲋 ， l0 0 0 1o ， 幢n 10 强镗$ t 图2 3 基于瓶颈链路上的数据流的争用的链路公平 壤摄不冠酌定父，链路公平可姨毒许多释方法来实现。一秘方法是 基于数捂流的带宽争用，辑有的数褥流都按比倒调整其带宽，如圈2 2 。 另一种方法是基于在瓶颈链路上的数据流的数日，如图2 3 。 另外还要区别主动和被动的调控机制。在主动调控中，一旦一个节 点捡测到盎己的输出链路上发生了拥塞，它就会席4 用反向环向上游节点 发送一令控裁包，旋它翻婷正发逡或者洚低英发送速率。在毅动调控孛， 一般是会有一个环绕全网发送的控制报文，使得各个节点之阐能够互相 合作而避免拥塞的发生。控制报文的内容可以多种多样，取决于具体的 实现。一种可能的实现是，每个节点在控制报文环绕网络一周的时间 t e 里，都会维护一令袁，这个表强录蓑在节点秘输虫链路上每条坟嚣 节点i 翻嗣的节点j 的链路f i j 上所传送的字节数。耋控钢报丈到这节 点i 胎，节点i 会计算出自己在输出链路i 上的公平速率r i ，并把它 写入摭制报文的相应地方。因为所有的节点都会进行同样的动作，因此 所有鲢节点都能够锉环遣更裁饿键农链路i 上镌公乎速率。 2 3 基于r p r 的公平参考模型分析 虽然环网的公平问题得到了广泛的研究，但大家研究的所谓公平都 是基于各自的标准。现在，在空问重用的条件下达到有权萤的公平性已 经成为了r 摊蛰议中秘一争鼹重要砖霉标。嚣姥，g e 2 17 工镩纽为r 鼹 的公平性定出了一个统一的目标：1 ) 在理想化的条件下对公平参考模 型给出一个严格和精确的定义。2 ) 给出一组标准，使得利用这组标准， 可以测试一个实用化的产品是否已经达到了r p r 的公平性要求。 因此，给出一个定义严格的公平参考模型对实现r p r 的公平性就显 得很重要队了。有了这样一个参考模型，可以使公平算法的设计目标能 够更加清晰。而各个厂家在设计自己的产品时，能够根据不同的价格生 产出不同等级的，满足参考模型不同条件的产品。同时，在比较不同算 法时，可以根据同一个参考模型做出更准确的判断。本论文中将引入 e dk n i 卧t l y 的r i a s ( r i n gi n g r e ss a g g r e g a t e dw i t hs p a t i a lr e u s e ) 1 1 公平机制参考模型。 2 3 2r j a s 公平性的两个主要部分 r i a s 公平性有两个主要的部分。第一个部分规定了在一个具有公 平性能的链路中流量的粒度的表示方法：i a 流，即所有源自于同一个 源流出节点的流量的集合。在我们的网络应用中，带宽的需求通常是由 到达网关的数据流来表示的。然而，一个构成带宽需求的“用户”到底 应该怎么来确定呢? 通常，一个网络带宽的“用户”可以是源数据流， 目的数据流，源一目的数据流对，甚至是运行于某个主机上的一个独立 的进程。这些不同的“用户”定义都有各自的不足。比如，在一个t c p i p 网络中，以同源数据流为单位分配带宽，则会限制某些需要消耗大量网 络带宽的数据源，比如f t p 服务器。虽然在理想情况下网关应该能知道 某些数据源需要更多的带宽，从而在带宽分配上加以保证，但在现实条 件下却还没有一种比较成熟的技术能够做到这点。以同目的地数据流为 单位分配带宽，则会因为某些恶意的或无意的数据源向该目的节点发送 过量的无用数据，使得该目的数据流的有用带宽无形中被减少了。而以 独立进程为单位分配带宽，则会鼓励用户去开辟大量进程，同样达不到 广泛意义上的公平。以源一目的数据流对为单位分配带宽，虽然也无法 阻止某个源数据流通过向不同的目的端发送大量数据而获得额外的带 宽，但在t c p i p 网络上，这似乎是以上几种中的一种比较有效的方法。 但在类似于r p r 的环网上，由于只考虑在第二层的性能，因此以i a 流 为带宽分配和管理单位的方法更能够体现公平性。这样，这个参考模型 就保证了在同一条链路上，一个源流出节点的流量在与其他相关的源流 出节点相比时，能得到相对公平的带宽。 r i a s 公平性的第二个部分则保证了在第一个条件的约束下，网络 能够达到最大的空间重用。也就是说，空余的带宽可以被i a 流加以重 用。为了简化起见，论文中把所有的源流出节点的权值都设为相同的。 下面，将给出r i a s 公平性的比较严格的定义。 23 3 a s 韵数攀模型定义 为了讨论的方便又不失一般性，论丈中只考虑双环中的一环里的 流量，并假设流煮到达一个节点劳被服务是一个理想化的i 建程。而以下 论炙申簖提载戆辑有速率怒表示戆是流量的耱跨速李。论文中还毂出如 下定叉：f l o w 表示在一个源流出乖目的流入节点对之间的单向流量， 而f l o w ( i ，j ) 则表示在源流出节点i 和目的流八节点j 之间的单向流蚤。 为了简化概念，论文中定义一个有n 个节点和n l 条链路的网络，并规 定如爨有节点n ，显 n j 畦，f l o w ( i ，j ) 将经过节点n 争链路n 。 诎谢f 1 朝 n o w 雌q n 3 ) n j 1 0 ， = = = = = = = = = = = = = = ：= = = = = = ；_ i 磊磊_ 虢每衰 - - 蕞静城 氟静疯 圆2 。4r l a s 中的舶w 及链路定义 考虑这徉一耪圣萋况，环躅中毒一令节点子嶷，在速令子集孛戆节点 对问存在的都是嚣求网络最失可用带宽的数据流，而不在该子集中的节 点对网络带宽没有需求。令r ；j 农示在节点i 和j 之间的候选r i a s 公平 速率。则环网上键路n 上所分配的速率为： 嚣，= 许# * 鞋肄。h 。蚝。r q( 2 2 ) 令e 表示环上所有链路的总参萋，羹我稍可踞给盎如下一个公平速率向 量为： r = ： 戤， 0 ，对于所有的f l w ( i ，j )( 2 3 ) 魏 o ，否则i a ( i ) i a ( i )( 2 7 ) 现在把定义一分成3 种情况加以讨论。首先，在公式( 4 ) 中，由 于f l o w ( i ，j ) 和f l o w ( i ，j ) 具有相同的源流出节点，故r 。，和r ，v 的不等性保证了对于同一个i a 流里的流向不同目的流入节点的九o w 之 间的公平性。第二种情况是，在公式( 2 6 ) 中，f l o w ( i ，j ) 和f l o w ( i ，j ) 具有不同的源流出节点和不同的瓶颈链路，但它们都要同时经过瓶颈链 路b 。( i ，j ) 和b 。，( i ，j ) 。这个不等式就保证了i a ( i ) 在瓶颈链路b 。( i ，j ) 和b 。( i ，j ) 上的总速率不会超过i a ( i ) 在瓶颈链路b 。( i ，j ) 和b 。 ( i ，j ) 上的总速率。第三种情况是，f l o w ( i ，j ) 和f l o w ( i ，j ) 具 有不同的源流出节点，且f l o w ( i ，j ) 和f l o w ( i ，j ) 都只经过瓶颈链 路b n ( i ，j ) 和b 。( i ，j ) 中的一个或不经过这两个瓶颈链路。这样， 不等式( 2 7 ) 就保证了不同的i a 流问的公平性。 在图2 5 中可以看到以上定义的图解示例。 牌船= = = = = = = = = = = = = = = = 叫 f l o n o h 图2 5r t a s 图解示例 如图2 5 ，首先假设所有对链路带宽的需求都是无限的，且链路的 容量经过了标准化。那么根据以上的定义，可以得出各条链路间的r i a s 公平速率为：r 。3 = r 。= r ，；= o 2 ，r 。：；r ，= r 。；= o 4 。考虑f l o w ( 1 ，2 ) ， 8 如果增加其速率，而又不想减少f l o w ( 1 ，3 ) ，( 1 ，4 ) 或( 1 ，5 ) 的速率，则 链路上的可行性将被打破，这符合论文中的定义一。再来考虑 f 1o w ( 2 ，5 ) ( 以凰( 2 ，5 ) 为其瓶颈链路) ，可以得出，若想增加其速率，则 必须减少f l o w ( 1 ，5 ) 的速率( f l o w ( 1 ，5 ) 的瓶颈链路为b ：( 1 ，5 ) ) ，这里， i a ( 1 ) 在瓶颈链路凰( 2 ，5 ) 和b ：( 1 ，5 ) 上的总速率等于i a ( 2 ) 在瓶颈链路 b 。( 2 ，5 ) 和b ：( 1 ，5 ) 上的总速率。因此，这对于它们来说是公平的。最后 考虑f l o w ( 4 ，5 ) ，同样的，无法在保持其可行性的同时增加其速率而又 不减小f l o w ( 1 ，5 ) ，f l o w ( 2 ，5 ) 的速率。 推论一：一个可行的速率向量被称为是具有r i a s 公平的，当且仅 当对于与r 关连的每一条f l o w 都存在一个瓶颈链路。 证明：假设r 是r i a s 公平的，利用反证法，则存在一条f l o w ( i ，j ) 不具有瓶颈链路。那么，根据定义一，对于任何一条f l o w ( i ，j ) 经过的 其f 。= c 的链路而言，曲然存在某夸f l o w ( i ，j ) ( i ，j ) 会违反公式 ( 3 4 ) ，( 3 5 ) 或( 3 6 ) ( 具体是哪条f