（通信与信息系统专业论文）ip网络质量路由路径动态绑定研究.pdf

北京交通大学硕士学位论文l p 嘲络质量路由路径动态绑定研究 摘要 随着网络中多媒体应用的急剧增加，越来越多的应用要求网络提供良 好的服务质量( q 岫i i t y o f s e n ，i c e ，q o s ) ，由于用户需求的波动性，使 得提供稳定的质量路由路径，保证可靠的服务质量，成为当前的一大难题。 本文从网络和用户间的供求关系出发，研究了质量路由路径的动态绑 定问题。主要工作与创新如下： 首先，深入分析了供需平衡的涨落函数、质量路由算法和核心无状态 网络体系结构，提出了供需平衡的核心无状态网络服务模式，并对该网络 服务模式的体系结构及其实现机制进行了详细论述。 其次，深入分析了服务当量分配原理和分配方案，提出了质量路由路 径动态绑定算法，对该绑定算法进行了详细的理论分析，证睨了它保证服 务质量的一致性和稳定性。 然后作为质量路由绑定的核心技术，本文提出了快速_ a x 一_ i n 公平 分配算法，对该算法进行了摄动分析和仿真实验，从理论和实践上均证明 了该算法的稳定性。 最后，在n s 2 网络仿真软件上设计并搭建了供需平衡的核心无状态网 络环境，进行了对质量路由路径动态绑定的仿真实验。实验结果表明，该 绑定算法能够为用户提供稳定的服务质量。 本文的研究来源于国家自然科学基金项目“基于ip 、，6 动态服务质量 理论及其应用的研究( 6 0 2 7 2 们2 ) ”。 关键词：服务质量，供需平衡，核心无状态，服务当量，公平分配 北京交面大学硕士学位论文 l p 网络质量路由路径动态绑定研究 a b s t r a c t w i t ht h ei n c r e a s co fm u i t i m e d i aa p p l i c a t i o ni nt h en e t w o r k s ，m o r ea 1 1 d m o r ea p p “c a t i o n sr e q u i r et h a tt h en e t 、o r k sc 柚s u p p i yh i g hq u a l i t yo fs e r v i c e d u et om e 玎u c t l i a t i o no fu s e r s d e m a n d ，j ti sd i 伍c u j tt op m v i d es t a b l eq u a 】i t y o f m u t ep a t h ，蛐dr e l i a b l eq u a l i 妙o f s e r v i c e t h ei s s u e sw i md y l l a t n cb i n d i n go f t h eq u a j t yo f r o u t ca r er e s e a r c h e di n t 1 1 i st h e s i sb a s c do nt i l es u p p i y 柚dd e m a n d 陀i a t i o n sb 咖e n 咖0 r ka 1 1 dt h e u s e r s ，f o o w j n ga r ct h em a i nw o r k sa n di n n o v a t i o 玎s ： f r r s t i y t h ef l u c m a t o j nf u n c t i o no fe q u i l i b r i u m ，q u a i j t yo fm u t ea l g o r i t h m ， 粕dt 1 e5 t n l c t t _ eo f c o r es t a t e l e s sn e t w o r k sa r c 卸a l y z e d ，t h e nt h ec o r es t a t e l e s s n 姗r ks e f v i c em o d eo fe q u i l i 瞒姗i sp f o p o s e d ，o fw h i c ht h es 廿c t u e 锄d m e c h a n i s m sa r ed e s c r i b c dj nd e 纽钉 s e c o n d l y t l l ea s s j g l l m e n t l e o r ya n ds c h e m ao f 蚓叫c ew o r k l o a d i s 柚a i y z e di nd e i a j t h ed ”姗i cb j n d i n ga i g o r i t h mo fq u a l 时o fr o l l t ep a t l li s p r o p o s e d 柚d 卸a l y z e d ，锄d “c 锄g u a r 锄o t i l es 油玎时粕dc o n s i s o 曲c yo f q u a i i # o f s e f v 溉 t h i r d j y ，w mt i l e 锄a i y s i so f 诋n u 曲i a l i o i l w j i g l l t e dm 双- m i nf a j r aj 1 0 c a t i o na l g o r 孙m ，an e wf a s ti m p j e m c n t a t i 彻斯w b i 曲t e dm a x m nf a r a l l o c a t i o n ， i sp m p o s e da n dp r o v e ds 岍c l l y 1 1 1 es i m u o nw i t hn s - 2i s p r e 辩n t e d 粕d 恤er c s u s 1 1 0 wt h es t a b i i 时o f o u ra l g o r i t i i m t h e 燃a 代hmm i st h e s i si sb a s e do nn a t u 豫ls c i e n c ef o u n do fc h i n a ”r e a r c ho nt 1 1 e o r y 柚da p p l j c a t i 伽o f d ”枷i cq u a l 时o f s c r v i c ei ni p v 6 ” k e y - o r d s ：q u a 酊t yo fs e r v j c e ，b a l a t l c eo fp v i s i o n c o 他s t ；n e l e s s ，s e r v i c e w o r k i o a d f a j ra l l o c a t i o n 北京交通大学硕士学位论文 y 8 7 9 0 2 1 i p 网络质量路由路径动态绑定研究 独创性说明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京交通 大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：趁出如日期：坦丝绝 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论 文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学电信学院网络实验室和华为技术 有限公司共同所有。未经许可，任何单位和个人不得拷贝。版权所有，违 者必究。 签名：盈d ! 翕努师签名 期： 北京交通大学顸士学位论文i p 网络质量路由路径动态绑定研究 第一章绪论 1 1 选题背景与研究现状 在早期计算机网络和分组交换网中，网络只提供尽力而为( b f l b e s t e f f o r t ) 的业务。对进入网络的业务流，都以先来先服务的方式对业务 流分组进行转发。随着传输和处理能力的增强，以及多媒体业务的引入， i n t e r n e t 已经逐步由单一的数据传输网络向数据、语音、图像、视频等 多媒体信息的综合传输网演化”1 。视频点播、视频会议、i p 电话、远程教 育等实时多媒体业务已经大量涌现，当前的b f 服务模式已经不能提供对 这类实时业务的支持“。于是，提出新的l p 网络服务模式，为实时应用 提供稳定、可靠的服务质量”1 ( q u a i t yo fs e n ，i c e ，q o s ) 保证已经成 为i f i t e r n e t 迫切需要解决的闻题。 国内外同行已经在网络服务质量的各个层面展开了大量深入的研究 和探索，并取得了不错的成绩。代表性的研究成果包括： 在体系结构方面，提出了一些新的q o s 服务模型，如i 盯f 的集成服 务( i n t s e r v ) 和区分服务”( d i f f s e n ，) 模型、多协议标记交换”( 娌l s ) 服务模型、l 佣s t o i c a 提出的核心无状态网络服务模型”、l 明公司的 i d e l b e r g q o s 模型“、美国哥伦比亚太学c 0 眶t 研究组提出的x 阴模型 ”、美国宾西法尼亚大学的明e g a 体系结构【“、美国加利福尼亚大学伯克 利分校的t e n e t 模型”等。 在资源分配和调度方面，提出了轮询调度算法”、广义处理器共享模 型g p s 、基于包的处理器共享模型陟p s l “1 、h x 一- i n 公平分配算法m 。o 、 加权公平分配算法”、基于核心无状态网络体系结构的虚时钟调度算法 北京交通大学硕士学位论文 i p 同络质量路由路径动悉绑定研究 m w 、改进的抖动虚时钟调度算法”3 和基于服务曲线的调度。”等。 在队列管理方面，提出了主动队列管理算法，如r 印”2 1 和以此为基础 的多种变体，包括f r e d ，s r 印m 和b l u e 拉5 1 等。 在q o s 路由方面，已提出的算法主要有q o s p f p q c 以及基于 b e l l 帕n f o r d 算法或者d i j k s t r a 算法”1 的，在多约束条件下对源路由、 分布式路由和链路状态路由算法的改进路由算法”。1 。 在支持q o s 的高性能路由器产品开发方面。国外著名的研发公司有 j u n i d e r 、l u c e n t 、c i s c o 、3 c 硼和a l c a t e i 等。国内的一些公司也在开 发高性能q o s 路由器，如华为、神州数码、大唐、清华比威、烽火、巨龙 和迈普等公司。各大公司均推出了支持d 0 s 的系列高性能路由器，如c j s c 0 的1 2 0 0 0 系列、1 2 8 0 0 系列路由器；j u n i p e r 的_ 系列、t 系列高端路由 器；神州数码的d c r 一6 0 0 0 ；华为眶系列高端路由器；烽火r 8 0 0 0 系列高 端路由器等。 尽管在o o s 研究领域的各个方面都取得了很大进展，但是，由于用户 需求的波动性”3 ”，当前的资源分配算法和q o s 路由算法都容易引起网络 振荡”于是，为用户数据流提供稳定的质量路由路径，保证可靠的服务 质量，成为本研究领域的一大难题。 当前，人们提出的解决上述问题的机制与策略大都是从公平或有效地 利用网络资源来进行考虑的。然而，网络和用户之问直接互动的供求关 系没有得到应有的重视。一般地如果供大于求，则服务资源充裕，网络 能够给用户提供良好的服务质量，但是网络的资源利用率却趋于下降，引 起资源的浪费；反之，如果供小于求，则服务资源趋于紧张，网络趋于拥 塞，提供给用户的服务质量下降，造成用户满意度的下降。服务资源的有 限性与用户需求的无限性决定了在用户需求与资源供给之间必然存在着 矛盾冲突嘲。 2 北京交通大学硕士学位论文 i p 网络质量路由路径动态绑定研究 受到商品市场上价格围绕价值上下波动的启发，我们在国家自然科学 基金项目一基于i p 、，6 动态服务质量理论及其应用的研究( 6 0 2 7 2 们2 ) 一 的研究过程中创新性的提出了资源分配围绕公平资源值上下波动的构 想，来调和网络和用户间的供求矛盾，以实现网络和用户间的供需平衡。 以此为出发点，在项目负责人胡九川博士的带领下，本科学基金项目 根据用户与网络之间就服务资源形成的动态供求关系，提出了基于服务资 源供给平衡与冗余的资源分配策略。供给平衡与冗余的含义是网络划分给 用户的资源量( 如带宽等) 以满足用户合理需求为基准，允许资源分配量或 需求量在一定合理范围内浮动，以限制用户过度消耗或违规侵占资源，并 确保对用户的基本资源供给，从而为保证用户服务质量提供资源条件。 还研究提出了描述资源供给量围绕平衡值上下涨落浮动轨迹的质量水平 涨落函数。为了在网络节点上按照平衡与冗余的原则划分服务资源，在改 进一般处理器共享模型”的基础上提出了计算服务当量的资源服务器 模型。给出了一个基于服务资源供给平衡与适当冗余的动态服务模式。该 服务模式在确保用户服务质量方面借鉴了集成服务模式的优点；在提高资 源利用率、满足用户个性化需求方面，吸取有区分腰务模式的长处；在保 持互联网的可扩展性和鲁棒性方面继承了尽力服务模式的优势；在适应各 种用户需求、网络服务资源环境动态变化方面具有独特的优势。 在上述科学基金项目的研究基础上，本论文研究了质量路由路径的动 态绑定问题。 1 2 本论文的主要工作和创新性 本文的工作属于国家自然科学基金项目( 基于i p v 6 动态服务质量理 论及其应用的研究，项目编号：6 0 2 7 2 0 1 2 ) 研究内容的部分。是在课 3 北京交通大学硕士学位论文 i p 刚络质量路由路径动态绑定研究 题负责人胡九川博士的研究内容上的深入扩展研究。主要研究了质量路由 路径的动态绑定和与其相关的服务当量分配问题，主要工作与创新如下： 1 ) 提出了供需平衡的核心无状态网络服务模式 深入分析了供需平衡的涨落函数【4 3 ”和核心无状态网络体系结构”3 ， 提出了供需平衡的核心无状态网络服务模式。该服务模式下，边缘路由器 维持每流状态信息，对数据流进行业务定形、速率估计和标记，而核心路 由器不需要维持每流状态信息，只需要根据数据包头中携带的流状态信息 进行转发服务。由于核心路由器不需要维护流状态信息，于是，整个服务 模式具有较强的可扩展性和鲁棒性。 2 ) 提出了质量路由路径动态绑定算法 深入分析了服务当量分配原理和分配方案，提出了质量路由路径动 态绑定算法，对该绑定算法进行了详细的理论分析，证明了它保证服务质 量的一致性和稳定性。 3 ) 提出了快速m a m i n 公平分配算法 作为质量路由绑定的核心技术，提出了快速_ a x _ i n 公平分配算法“1 ， 该算法用多次平均值来快速逼近公平资源值，巧妙的回避了渐次填充算法 步长和收敛速度问的矛盾，大大提高了收敛速度。最后，对该算法进行了 摄动分析和仿真实验，从理论和实践上均证明了该算法的稳定性。 为了提供有区分的服务，本文改进了快速x 一i n 公平分配算法，提 出了带权公平分配算法，通过设置各个流的权重，可以实现多优先级的 4 北京交通大学硕士学位论文 j ph 络质量路由路径动态绑定研究 m a x m i n 公平分配。然后对改进算法作了类似的摄动分析和仿真实验，证 明了改进算法的稳定性。 4 ) 对质量路由路径动态绑定进行了仿真分析 改进了n s 2 网络仿真工具，在n s 2 网络仿真软件上搭建了供需平衡的 核心无状态网络实验平台，设计并进行了对质量路由路径动态绑定的仿真 实验。实验结果表明，该绑定算法能够为用户提供稳定的服务质量。 北京变通大学硕七学位论文l p 网络质量路由路径动态绑定研究 第二章供需平衡的核心无状态网络 随着网络的发展，其应用领域不断拓展，应用模型不断丰富，加之商 业化进程的推动，越来越需要对网络所传输的业务类型有一个较为具体和 明确的定义，即所谓的网络业务模型，从最早的i s d n ，到i n t s e r v “1 ， 再到后来的d i f f s e r v l 5 1 ，这些都是结合应用的需求和技术的发展提出来 的，无论最终采用哪一种业务体系结构，其技术的核心都需要在恰当的层 次和粒度上对流量进行必要的管理，其中包括接纳控制、流量整形、队列 管理、调度和拥塞控制等诸多方面，但最核心和最基本的应该依旧是拥塞 控制，因为很难想象一个时常可能出现严重拥塞而且无法及时加以恢复的 网络能够实现良好的q 0 s 。实施拥塞控制应该是其它q o s 机制正常工作的 必要前提。 拥塞控制的核心技术是资源的公平分配，一个好的公平分配算法，能 保证每条接入的数据流都分配到它所需要的最低资源，以保证其服务质 量，并且也能在资源不够的情况下拒绝新数据流的接入：好的公平分配算 法，即使在资源富余的情况下。也不分配给用户超过其最高需求的资源量， 以免造成资源浪费；好的公平分配算法，就是要在网络和用户之间达成资 源的供需平衡，保证网络分配给用户的资源既不过多，造成资源浪费，也 不过少，不能保证其服务质量。正是基于这一观点，我们提出了供需平衡 的涨落函数。 2 1 供需平衡的涨落函数 随着互联网应用越来越广泛，每时每刻接入的用户数量在不断增长。 6 北京变通大学硕士学位论文i p 同络质量路由路径动态绑定研究 服务资源的相对有限性与用户对服务资源需求的无限性之间的差距不断 增加。网络交换速率的不断提高为提供快捷的服务，允许更多的用户能够 接入网络创造了条件。但是，在很多情况下，在某一个网域，甚至在某一 个网络节点上用户的需求远远超过了网络服务资源的拥有量。因此，一味 地，单方面地扩充资源，比如不断提高网络的带宽或增加路由器上的缓存 空间等，仍然没有从根本上解决问题。网络拥塞典型地反映出了服务资源 不能满足用户需求的实际情况。数据延迟或丢包往往发生在此环节。减少 延迟，降低数据包的丢失率，使用户的数据流能够顺畅地通过网络节点， 必然成为问题的焦点。在高速主干网上，单位时间内需要通过路由器的用 户的数据量巨大，路由器能否在尽可能短的时间内将用户的数据包交换转 发出去成为确保用户服务质量的关键。 关于依据供需平衡分配服务资源的思想及其研究已经在近几年出现。 r a l l u lg a r g ，a b h i n a vk 锄r a 和v a n mk j l u r a i m l ”】在2 0 0 2 年提出根据对策 论的理论实现拥塞控制的技术途径：其出发点是：在非合作的竞争环境中， 用户追求资源的动机是自私的，是以获取资源最大化为目的的。用户能否 获取到所需的资源，完全取决于用户的竞争能力和其参与竞争的环境，竞 争的结果便是j 0 l l nn a s h 所说的n a s i l 平衡。在n 鹊h 平衡状态下，每个用 户不再有进一步获取更多服务资源的愿望。因为，如果某个用户敢于再向 前迈进一步，那么他不但不能因此而进一步获利，而且可能会为此而丧失 已经占有的资源或获取资源的优势。因此，n a s h 平衡是非合作环境下和 服务资源有限的条件下的所有用户共同行为的结果。从博弈论的角度，推 算n a s h 平衡值是很困难的，复杂的。目前，大多数工作还停留在理论探 讨上。从理论上讲，n a s h 平衡是供求关系处于平衡的一种形式。如果说 处于n a s h 平衡状态下的各个用户所分得的服务资源量能够满足每个用户 的需要，那么，此时的供求平衡状态是理想的。然而，这仅是理论上的一 7 北京交通大学硬士学位论文 i p 嗣络质量路由路径动态绑定研究 种情形。在将n a s h 平衡应用到实际中来之前，还存在很多理论问题需要 解决。在n a s h 平衡状态下，不一定每个用户获得的服务资源量都能够满 足其需求。 所以，我们从面向用户需求确保服务质量的角度，提出兼顾公平性与 有效性，以服务资源供需平衡与适当冗余为基础的涨落函数，来实现资源 公平分配的构想。服务资源供给平衡与冗余的含义是，分配给用户的服务 资源是在尊重用户的合理需求基础之上，按照供需平衡的原则予以分配 的。为了适应用户需求或网络资源状况韵动态变化，在分配给用户其合理 需求数量资源的基础上，另外为用户划拨适当冗余的资源量。 根据用户的偏好，资源分为两类。一类如带宽越多越好，记为掣；一 类如延迟、抖动越短越少越好，记为q 。所以，资源的判别函数定义为： 脚) 皇饿： 眩d 其中，“为资源变量。 定义2 1 设资源变量“的取值范围为实数区间 【k ，1 ( 2 2 ) 平衡值g ( ，k ) ：用户获得的瞬时资源量为z ：则资源变量h 的 质量水平涨落函数定义为： 卢b “) 皇 ! 二! ! ! ! ! 兰二墨! ，x g ； g 一，m m ( 2 3 ) 鲤：坠啦，g 。一g 变量x 称为资源量。对任意的非负实数日e 【o l 】，设 型生堡型型苎望型苎塑! 坠一 ! ! 竖竺壁墨堕宴堕堡垫查塑塞塑窒 ( 毋) 皇i n f ，i 口卢( y ，越) 口1 ， ( 2 4 ) ( 口) 皇s u p ，j 一目( ，) 口l ， ( 2 5 ) 则实数区间n ( 口) ，( 口) 称为资源变量”的口约束条件。 定理2 l 质量因素”的质量涨落函数卢似“) 具有以下性质： 1 如果“甲，则“m 声( “) = 一1 ： 1 4 k 、 2 如果“甲，则i i m 卢( 五h ) = l ； 一 3 如果”o ，则l i m 卢( 五“1 = l ： o + k 4 如果“q ，则l i mp ( 墨1 ：一l ； “_ 、 5 当_ r = g 时，则卢( “) = o ； 6 “) 在区间【，g 】，f g ，k 】上关于资源变量x 单调； 7 一l ( l ) l 。 证明2 1 ： 1 如果甲，则，根据( 2 1 ) ，有 f ( “) = ( 一1 ) o = 1 ( 2 6 ) 当t 譬，则 于是， 卢( ) 2 惹 ( 2 7 ) 炮卢( 五“) = ( 一1 ) 恕嚣= - 1 ( 2 - 8 ) 9 北京交通大学硕士学位论文l p 网络质量路由路径动态绑定研究 2 让明万j 去与l 相l 司a 3 证明方法与l 相同。 4 证明方法与l 相同。 5 显然得证。 6 首先，当”甲时，善( ”) = o 。 对任意的，屯【，g 】，且兰墨，有： ( ，”) = 1 1 三 s ! i 三互= 卢( 恐，”) ( 2 9 ) g 一。 g 一，m 。 对任意的，毛【g ，。】，且 屯，有： 口( ) 2 嚣嚣2 卢( 蚺 ( 2 1 0 ) 二。一g 。一g 所以，口) 在区间 。，g j ，【g ，。j 上关于资源变量x 单调递增。 其次，当“q 时，喜0 ) = l 。 对任意的五，毛【，g 】，且 恐，有： ( 玉，u ) = 导李r 二芋2 _ = 卢( 毛，“) ( 2 1 1 ) g 一7 ：血窖一“ 对任意的，毛g ，r m 。】，且兰屯，有： 卢( 卅) 2 基嚣2 卢( ) - ( 2 1 2 ) “一g ，m “一g 所以，卢( z ，”) 在区间【，g 】，f 舀，帆1 上关于资源变量x 单调递减。 综合上述，有卢b ”) 在区间【。，g 】，【g ，r 帕。】上关于资源变量x 单调。 7 南6 。首先当甲时， 1 0 北京交逋大学硕士学位论文 i p 网络质量路由路径动态绑定研究 口( k 。，“) 卢( t ”) 卢( ，) ( 2 1 3 ) 而纯，”) 。筹2 j ；( r m “，“) 生二墨：l 。 “一g 卢( ，m 。，“) 声( t n ) 卢( 。，“) ( 2 1 4 ) 而，) 2 慧= l ；卢( n ) 2 篡= - l 。 i 笔竺雕1 6 3 0 ； 以训卜 墨= ，： 眩 i8 9 0 。 f - o 7 2 2 ，x = 1 1 0 0 ； 卢( h ) z o ，x = 1 6 3 0 ； ( 2 1 6 ) 【o 3 9 3 ，j = 1 9 踟 北京交通夫学硕士学位论文 p 网络质量路由路径动态绑定研究 大的浪费：涨落幅度接近一l 表明服务质量对该用户而言非常糟糕，分得 的带宽仅为用户需求的最低限，用户长期处于资源分配不足的境地中；涨 落幅度为o ，则瞬时带宽为平衡值，此时网络提供的带宽正好满足用户需 求，既不多也不少，不存在波动，服务质量最好【3 2 l 。 例2 1 说明了函数卢( “1 反映了质量水平涨落幅度，可用于调控资源 分配和服务水平。限定涨落幅度，即可控制资源分配：控制资源分配，即 可限制质量水平的涨落幅度。卢( ”) = o 说明瞬时资源量x 为平衡值，正 好满足用户需求。当“为带宽时，如果x 趋于。，则( “) 单调下降趋 于一1 说明用户获得的带宽递减，最终少于平衡值，趋于最低需求；当x 趋于。，则卢( “) 单调上升趋于i ，说明用户获得的带宽递增，直至高 于平衡值，趋于最高需求：当“为延迟时，如果x 趋于o 。，则卢( x ，) 单 调下降趋于一l ，说明数据分组经历的延迟递增，直至高于平衡值，趋于 最大时延；当x 趋于i 日则卢( 五“) 单调上升趋于】，说明数据分组经历 的延迟递减，直至低于平衡值，趋于最少时延。 总之，质量涨落函数的意义归纳如表2 1 ： 质量因素质量涨落函数效果 带宽 l i m 卢k “) = 一l 趋于紧张 i 叶 、 带宽 l i m 卢( 暑) = l 趋于充裕 ，螂 、 延迟l i m 卢k ) = l 趋于减小 j _ ，_ 延迟l i m 卢b ”1 = 一l趋于增加 j _ k 质量涨落函数的意义 北京交通大学硕士学位论文i p 嗣络质量路由路径动态绑定研究 质量水平涨落函数是刻画蜘络服务过程中服务资源供求关系变化轨 迹的工具，是从服务资源供给量或消耗量透视网络服务质量水平的工具。 由于质量水平涨落函数揭示了资源供给量与服务质量水平之间的关系，所 以，该函数可以作为按照用户需求为用户划分资源的工具，或根据服务资 源的分配状况估计服务质量水平的工具。 质量水平涨落函数描述了网络服务用户过程中，用户享用服务资源的 数量变化的相对轨迹。如果以用户占用服务资源的数量等于供需平衡值为 参照，那么，资源数量超过平衡值时，表明用户此刻获得的资源量超过了 其合理需求量。于是，网络此时对用户的服务质量水平当然要比处于供需 平衡状态时要好。反之，如果资源数量低于平衡值，则说明用户此刻获得 服务资源少于其合理需求量。于是，此时网络对用户的服务质量要低于平 衡状态下的服务水平。正是通过资源占有量的相对参照关系来反映服务质 量的状态。质量水平函数值的变化起伏，反映了服务质量水平的涨落起伏。 2 2 供需平衡的质量路由算法 借助质量水平涨落函数，我们可以通过指定供需平衡的资源量，服务 资源供给的上界与下界，以及期望服务质量水平的涨落幅度来反求对用户 的资源分配。该资源分配通常表示为允许资源变化波动的实数区间，平衡 值仅是该区间中的一点。显然，用户可以获得的资源是冗余的，因为，除 了平衡值以外，用户还有其他选择。 与服务资源供给平衡与冗余的分配思想一脉相承的质量路由策略，为 在路由路径的发现过程中限定资源分配出现脱离用户的实际需求状况而 片面追求最大化的做法，并平衡网络负载和稳定质量路由路径上的服务质 量水平创造了条件。依据此质量路由策略，我们对质量路由算法进行了推 北京变通人学硕士学位论文l p 网络质量路由路径动态绑定研究 广，并内嵌了检测服务质量水平的接口。正是利用这样的接口，才使得在 利用n s 一2 仿真的过程中，我们能够有效地检测网络的服务质量水平。 设嘲络节点集合为v ，链接集合为e 。l 矿i ，l e l 分别为网络的节点和 链接数。对任意的，矿“，以为从节点到节点，链接上的带宽和 延迟，掣，p ? 为从源节点s 出发，经过存步转跳到节点，的路径上的带 宽和延迟。为检验质量水平的时间间隔，儿( 曲，芦。( y ) 分别为瞬时带宽 取和瞬时延迟取j ，的可能性程度，卢( e x ) ，卢( d ，y ) 为相应质量水平涨 落函数。于是，质量路由问题归纳为：在质量水平涨落幅度不超过口带 宽和延迟围绕其平衡值分布的可能性不低于口的条件下，即，带宽和延迟 的约束条件为区间分别为【中( p ) ，尊( 占) 】，和【f ( 既( 口) 】，计算源节点为 s 、目的节点为d 满足此约束条件的路径，具体算法描述如下： ( 1 ) 取 = o ，群= o ，四= 佃，f 5 ； ( 2 ) 选择节点仉，使从源节点s 出发，依次途径集合m = “，啦， 中的所有节点，最后跳到节点珀0 路径带宽口和延迟d 分别满足： 口2 罂品( m i n ( 霹，钆 畔 a ) ，f 以蜊。， d 2 毋辫m i n 骘+ d _ ，i ) g 晡p ，口) ，宁( 以a ) n 若m = 中，则路由路径不存在； ( 3 ) 取矿1 = 口，印“= d ； ( 4 ) 如果 爿e i ，算法结束。否则，取 = 矗+ l ； ( 5 ) 转移到步骤2 。 1 4 北京交通大学硕士学位论文 l p 网络质量路由路径动态绑定研究 2 3 供需平衡的核心无状态网络 核心无状态( s t a t e l e s sc o 琏s c o r e ) ”j 网络是基于状态的结构和无状 态的结构的一种折衷。与d i f 8 e r v 类似，一个s c o r e 域是一个连续的信任 的网络区域，其中只有边缘路由器维护数据流的状态，而核心路由器不维 护数据流的状态。由于边缘路由器同核心路由器相比，运行速度低得多， 处理的数据流也少得多，这种结构的可扩展性非常好。 由于核心盂状态服务模型在保持i p 网络鲁棒性和可扩展性特征的前 提下能保证数据流获得较好的服务质量，因此本文借鉴核心无状态服务模 式的基本思想提出了供需平衡的核心无状态网络体系结构。 2 3 1 网络体系结构描述 图2 1 供需平衡的核心无状态网络体系结构 与区分服务模式和核心无状态模式相类似，s c 0 r e 网络由边缘路由 器和核心路由器组成，如图2 1 所示。边缘路由器维持每流状态信息，核 心路由器不需要维持每流状态信息。因为边缘路由器运行的速率比核心路 由器小，处理的数据流量也小。这种结构与区分服务和核心无状态服务模 北京交通大学硕士学位论文 i p 网络质量路由路径动态绑定研究 式一样都具有较强的可扩展性。 图2 2 边缘路由器和核心路由器结构 边缘路由器基本结构和功能：如图2 2 所示，边缘路由器的主要功能 是业务流定形。该功能主要包括分类器( c i a s s i f i e r ) 、测量器( t e r ) 、 标志器( r k e r ) ，定形器( s h a p e r ) 。在这里路由器需要对每一数据流占用 的带宽资源进行调度分配，即对到来的数据流还需要进行速率估计和数据 包丢弃，最后采用动态包技术将数据包获得的实际速率写入数据包头中， 然后对数据包进行转发。 核心路由器基本结构和功能：采用先进现出( f i f o ) 的队列管理调度机 制。在路由器中对到来的数据流进行总的速率估计，然后根据数据包头中 携带的流状态采用适当的p h b 。接着，将数据流获得的公平速率重新写 入数据包头中，然后将数据包发送到下一个节点。由于核心路由器不需要 维持每流状态信息，使得s c o r e 具有极强的可扩展性。 2 3 2 网络体系结构的实现 为了在实施服务质量保证时不需要核心路由器维持每流状态信息， s t a t e i e s sc o r e 采用核心无状态网络的动态包技术( d p s ) ，d p s ( d y n a l t i i c 1 6 北京交通大学硕士学位论文p 网络质量路由路径动态绑定研究 p a c k e ts t a t e ) 是实现核心无状态网络的关键技术。它的思想非常简单，就 是用数据包携带所属数据流的状态，来代替在路由器中维护数据流的状 态。这样，核心路由器依据数据包头中携带的状态和路由器内部的状态来 处理数据包。在转发数据包到下一跳之前，核心路由器既更薪路由器内部 的状态，又更新数据包头中的数据流状态。通过在一条数据通路上的边缘 路由器和核心路由器中使用d p s ，设计分布式的算法，可以达到有状态 ( s t a t e 如1 ) 网络的效果。 通过该技术，边缘路由器将数据流获得实际速率等相关状态信息( 数 据流的预留速率、数据包的时问戳、数据包长度等) 存储在数据包头中， 当携带状态信息的数据包进入核心路由器时，核心路由器首先根据数据包 的状态信息以及速率保证时钟计算出数据包需要获得资源服务量，然后核 心路由器根据计算出的资源服务量对数据包进行调度转发，同时将相关的 新的状态信息写入数据包头中。通过边缘路由器和核心路由器的协调工 作，保证数据包获得相应的服务质量。最后数据包通过边缘路由器传输输 出该域时，状态信息将会被取消。 核心无状态网络模式为保证用户服务质量得到满足，在核心路由器中 采用了基于供需平衡的m a x - m m 公平分配算法。该算法能够对网络资源 进行稳定的公平分配，确保网络分配给用户的资源既不太多，也不太少， 正好在用户需求的范围之内。还能回避网络热点，平衡网络负载，避免网 络拥塞。此外对核心无状态网络也有良好兼容性，因此该算法能够更好地 满足用户q o s 需求的同时，为数据流提供稳定的服务质量。 在边缘路由器上，一个关键的功能是对到来的数据流进行流量定形。 使得数据流的需求和网络服务资源的供给之间建立动态平衡关系。不仅满 足数据流服务质量的需求，同时保护友好流对服务资源的需求的同时限制 非友好流对网络资源的过度侵占。保证网络的稳定性。 1 7 北京交通大学硕士学位论文i p 网络质量路由路径动态绑定研究 在核心路由器中，p h b 功能的实现同边缘路由器相比要简单得多， 只需要根据标签和公平速率决定是否转发此数据包，并修改数据包头中的 标签即可，同时计算新的公平速率。这样省却了复杂的包分类算法和数 据流到达速率的估算这些基于流的计算，实现大大简化。从而节省出大量 的c p u 时间，大大提高了处理效率。 2 4 本章小结 本章深入分析了供需平衡的涨落函数和核心无状态网络体系结构，提 出了供需平衡的核心无状态网络服务模式。该服务模式下，边缘路由器维 持每流状态信息，对数据流进行业务定形、速率估计和标记，而核心路由 器不需要维持每流状态信息，只需要根据数据包头中携带的流状态信息进 行转发服务。由于核心路由器不需要维护流状态信息，于是，整个服务模 式具有较强的可扩展性和鲁棒性。 北京交通大学硕士学位论文i p 网络质量路由路径动态绑定研究 第三章基于服务当量的质量路由路径动态绑定 3 1 服务当量 在数据交换网络中，需要解决网络资源在众多用户之间合理共享的问 题。根据统计多路复用，时分多路复用，以及频分多路复用等交换方法， 在任一时刻，使用服务资源的用户只有一个。如果将分配服务资源，调控 服务资源等相关工作的执行者抽象为一个资源服务器( i k s o u r c es e r v e r ) ， 那么该服务器在其工作的任一时刻仅能服务且只能服务一个用户。因此， 公平与效率自然成为首要问题。所谓公平是对用户而言的。即，每个用户 对服务资源拥有相同的享有权利。 在共享资源服务器的模型中，每个用户被分配或指定适当的资源份 额，用户超出份额的需求将被忽略掉。按照一定的秩序，这些服务资源份 额被提供给用户以兑现服务的承诺。耳前的共享资源服务器模型，还不支 持将用户需求纳入其中。为此，我们提出服务当量思想，并据此实现满足 用户需求，提高资源利用率，最终确保对用户的服务质量的服务资源共享。 3 1 1 广义共享服务器 在数据交换网络中，广义共享服务器的工作原理【2 6 】如下：设服务器 为n 个用户提供一条带宽为r 的链路，只要网络节点上滞留有需要转发交 换的数据包，则服务器将不能停止转发交换数据包的具体操作。 ，五，如为正实数。设在时间区间( f ，f 】内，服务器对每个有数据包滞 留堆积在缓存区里的用户f ( f = l ，2 ，3 ，) 的服务量记为s ( r ，f ) 。般地， 1 9 北京交通大学硕士学位论文 i p 网络质量路由路径动态绑定研究 服务量可通过转发交换数据包的数量或服务的时间来计量。于是按照公平 性的原则，服务器对这些用户的服务量分配必须满足 湍扣啦， 限t ， 对式( 3 1 ) 两边关于_ ，求和，有： s ，( r ，f ) 乃( f - f ) 一 ( 3 2 ) ，l 冈此，从占用链路带宽份额的角度，用户f 可以分得的带宽为： 舻疚7 式( 3 3 ) 表明，每个用户分得的资源量由三方面因素所决定： a ) 、每个用户申请或被指定的资源量丑 ( 3 3 ) b ) 、全体用户申请或被指定的资源总量c ，以及申请服务的用户总数 n ： c ) 、实际兑现的资源量必须按式( 3 1 ) 所决定的公平原则予以确定。 因此，用户实际享用的资源量是由其个人独立的要求、在同一时间共 同分享资源的其他用户的数量、以及他们对服务量的总体需求按照公平的 原则综含决定的。 由式( 3 1 ) 所代表的公平性原则表明：每个用户具有同等占有服务 资源机会的权利，而不是占用相同数量服务资源的权利。所以，式( 3 1 ) 所代表的同等机会权利的公平性为满足各个用户的不同需求创造了条件。 因此，由式( 3 3 ) 所决定的每个用户分配的带宽份额是否满足用户的需 求成为问题的关键。 2 0 北京交通太学硕士学位论文 i p 网络质量路出路径动态绑定研究 3 1 2 服务当量分配原理 如果式( 3 3 ) 决定的带宽份额能够满足用户的需求，比如在大多数 情况下用户的数据流的平均速率。则此时对用户的服务资源分配是在机会 公平原则下的满足用户需求的资源分配，因此，依据此资源分配，网络对 用户的服务质量水平是好的。下面我们首先给出一般条件下根据用户需求 为用广分配服务资源的基本方法，然后，给出满足用户质量标准，确保服 务质量的资源分配方法。 为了讨论方便，称满足式( 3 1 ) 的非零实数数组 ，土，厶为服务器 的正则服务当量，他代表一个服务器资源分配方案，表明各个用户在分享 服务资源的过程中，资源服务器对各个用户的服务工作量。因此，如果 丑= 0 ，则服务当量便失去其意义。服务当量既可以由独立的第三方根据 公平原则指定，也可以依据用户的要求予以确定。 假设已知用户所要求的带宽份额为，b ，j h ，则根据式( 3 3 ) ，获 得如下的线性方程组( 3 4 ) 。线性方程组( 3 4 ) 的解便是资源服务器的对牲 个用户的服务当量。 毛r气毛 七2 毛一， 屯 岛墨屯一r ( 3 4 ) 根据矩阵的初等变换，线性方程组可被等价地变换为解线性方程组： 志知 viii巩 丘岛缸；矿 北京变通大学硕士学位论文 l p 网络质量路由路径动态绑定研究 t r oo 七一ro 缸0一， h 0o 0 0 o ： 五 五 ： 厶 根据文献，线性方程组具有非零解的充分必要条件是矩阵 r t 一，o k 一r 七0 k 。 o o o 0 0 一r o 0 _ ， ( 3 5 ) ( 3 6 ) 的秩女( r ) 。 定义3 1 ：给定一组用户对服务资源的请求，k ，h ，如果 v f ( ， l ，2 ，3 ，| v ) ) ，_ o ，则称用户对服务资源的请求为正则服务请求。 因此，面对一组用户的服务请求，我们希望通过求解线性方程组以获 得相应的正则服务当量，从而决定对用户的服务资源分配。 定理3 1 ：给定正则服务请求_ ，k ，h ，则每个用户能够获得正则服务 当量的必要条件为备一，= o 。 证明3 1 ：假设二。七j r o ，则矩阵 r o 0 o ： ( 3 7 ) 的秩，女( r ) = 。根据文献，线性方程组存在唯一的平凡解：零解 o o f ；o o f o ；o r一 咎屯屯；b 北京交通大学硬士学位论文l p 网络质量路由路径动态绑定研究 ( ，五，“) = ( o ，o ，o ) ( 3 8 ) 因此，矛盾。所以有定理3 1 结论成立。 此定理表明，当链接的带宽为0 时，用户对服务资源的请求只能是零 请求。即， = q 一- h = o ( 3 9 ) 换言之，当链路的带宽为零时，用户不能对此链路提出服务资源请求。 然而，当链路带宽不为零时，所有用户请求的总和必须等于链路的带宽， 否则，用户没有可能获得正则服务当量。 定义3 2 ：设用户对服务资源的正则服务请求为实数数列_ ，k ，h ，链 路带宽为r ，称表达式乌q r = o 为正则当量条件( r e g u i a r r k i o a d c o n d j t i o n ) 。 因此，有以下定理成立。 定理3 2 ：一组用户正则请求决定一组正则服务当量的必要条件是该请求 满足正则当量条件。 证明3 2 ：根据定义3 2 ，结论成立。 综合分析在同一时刻所有用户的请求，考察他们是否满足正则当量条 件，或者对用户的请求进行适当的分组以使之满足正财当量条件，即可确 定资源服务器对每个用户分配的服务当量。 3 1 3 服务当量分配方案 设n 个用户请求平均资源量( 如带宽数量等) 为玛，t ，h ，则对 任意用户f ( f = 1 ，2 ，) ，只要其请求的资源数量限于区问 北京交通大学硕士学位论文p 网络质量路由路径动态绑定研究 豫( g ，口) 皇 g ，一舅j ，蜀十p a j ( 3 1 0 ) 内t 则该用户的请求