（计算机应用技术专业论文）三类主要网络业务的时间指标和调度机制研究.pdf

摘要 随着计算机网络和通信技术的发展，在许多网络环境中，除了要 上网实现i n t e m e t 服务外，可能还包括一定数量的实时要求和带宽保 证用户。在这种环境下主要涉及三类主要网络业务：实时、带宽保证 和尽力服务业务。随着网络规模的膨胀以及人们对业务种类和质量要 求的上升，如何同时实现多类业务的网络q o s 控制成为了一个值得 研究的课题。 在q o s 控制机制中，调度算法决定了被服务的分组接受服务的 顺序，使其所在的数据转发设备能够智能地控制数据转发的优先级、 每条链路的带宽以及平均时延等特性以满足一定程度上的服务质量。 而为了进一步提高网络服务质量，满足用户的需求，引发了很多调度 算法的研究。 本文首先从q o s 的发展现状出发引入了q o s 有关定义和技术指 标，然后分析了q o s 的控制机制，并且就几种重要机制的发展进行 了讲述，其中包括分组调度算法。 其次本文提出了三类主要的网络业务实时、带宽保证和尽力 服务业务流，并且例举了拥有三类主要网络业务的应用环境。然后基 于t c p 和u d p 协议对出现三类主要业务的网络环境的时间性能指标 进行了研究，得到了计算带宽保证业务流和实时业务流的最大时延计 算公式。 最后本文以经典的单处理器调度算法：最早时限优先( e d f ) 算 法为依据，针对现阶段网络用户的需求，提出了一种基于实时和带宽 保证、尽力服务业务并存的改进e d f 调度算法一一r a b e d f ( r e a l t i m ea n db a n d w i d t ha s s u r 锄c ee d f ) ，在这种改进e d f 调度算法 中，提出了新的带宽保证策略，并且依据三种不同模型给出了 r a b e d f 算法的调度过程，然后对论文中所提出算法在s i m 网络仿 真环境下进行了仿真实验。 本文得出的最大时延计算公式为基于交换队列的改进e d f 调度 机制和基于优先级的带宽保证策略都提供了很好的判断依据。仿真结 果表明改进的调度机制在一定程度上降低了业务流的时延，提高了带 宽保证业务流的带宽保证率，总体上来说改善了网络q o s 性能。 关键词：服务质量，分组调度，e d f 调度，带宽保证策略，s i m 仿真 软件 i i a bs t r a c t w i t ht h e d e v e l o p m e n t o ft h en e t w o r ka i l dc o m m u n i c a t i o n t e c h n o l o g y t h e r ea r en o to n l ys o m eu s e r sw h on e e dt h es e r v i c eo ft h e i n t e m e t ，b u ta l s op e o p l ew h on e e dp r o 听d i n gr e a l t i m er e q u i r e m e n t sa n d b a n d w i d t ha u s s u r a n c ei nm a i l yn e m o r ka p p l i c a t i o n s i i lt h i sw a y ，w eh a v e t h r e ek i n d so f p n n l a i 。y n e t w o r kb u s i n e s s e s ：r e a l - t i n l e ，b a n d w i d t h a s s u r a n c ea i l db e s t - e f f o r tb u s s i l l e s s e s w i t hm ee x p a n d i l l go fn e t 、o r k s c a l ea n dt h ei n c r e a s i n go ft h eb u s s i n e s sc l a s sa i l dq u a l i 够r e q u i r e m e n t ， h o wt or e a l i z et h ec o n t r o lo fq u a l i t yo fs e r v i c e ( q o s ) f o rm u l t i - s e r v i c ei s ap r o b l e m w o n h i n g r e s e a c h h lt h ec o n 仃o lm e c h a n i s m so f q o s ，t h es e h e d u l i n ga l g o r i t h l 璐d e c i d e t h eo r d e ro ft h es e r v i c e dp a c k e t sa n dm a k ed a t at r a i l s f e i t i n gd e v i c e s c o n t r d ls o m ec h a r a c t e r i s t i c si n t e l l i g e n t l y ，w h i c hi n c l u d et h ep r i o r i t yo f d a t a 仃a n s f e 币n g ，i n d i v i d u a l l i n l ( b a n d w i d t ha n da v e r a g ed e la y t h e s ec a n s a t i s 矽q o si nac e r t a i ne x t e n t t i oi n l p r o v en e t w o r l ( q o sa n ds a t i s 母t h e u s e r s ，m a n yr e s e a r c h e so ns c h e d u l i n ga l g o r i t h m sa r ee m e 略e d f i r s t l y ，t h i sp 印e ri n 仃o d u c e sa s s o c i a t e dd e 缸n i t i o n sa n dt e c h n i q u e p e r f o m a n c e s 丘o mt h ec u r r e n tr e s e a c hs t a t l l so fq o s a n dt h e n ，i t a n a l y z e st h ec o n t r 0 1m e c h a n i s mo fq o s a l s o ，t h ed e v e l o p m e n to fs e v e r a l i m p o r t a n tm e c h a n i s n l si sd e s c r i b e d ，i n c l u d i n gt h ep a c k e ts c h e d u l i n g a l g o r i t h l t l s s e c o n d l y t h ep 印e rp o i n t so u tt h r e ek i n d so fp r i m a r yn e 觚o r k b u s i n e s s e sa 1 1 dl i s t st h e 印p l i c a t i o n e n v i r o n m e n t o 、) m i n g t h em r e e b u s i n e s s e s a r e rt h i s ，t h et i m ep e r f o n n a n c e sb a s e do nt h et c pa n du d p i nt h en e 帆o r kw i t ht h r e ep n m a r yb u s i n e s s e sa r er e s e a r c h e d ；t h ef o n n u l a s i i i f o rc a l c u l a t i n gt h em a x i m 啪d e l a yo f b a n d w i d t ha s s u r a n c ea n dr e a l t i m e s e i c e sa r eg i v e no u t l a s t l y a c c o r d i n gt om ec l a s s i c a lu n i - p r o c e s s o rs c h e d u l ea l g o r i t m 1 n a m e dm ee 砌i e s t d e a d l i n e - f i r s ta l g 嘶t h 矾t h ep 印e rp u t sf o m a r dt h e i m p r o v e de d fa l g o 甜i n lb a s e do nm er e a l - t i m e ，b a l l d w i d mg u 黝t e e a n db e s t - e 肋r ts e v i c e sr e g 砌协gt l l en e e do fn e t w o r ku s e r si nt h ec l m e n t s t a g e h 1m i sa l g o 打t h 驰an e wb a l l d w i d t ha s s u r a l l c es 臼a t e g ya n dm e s c h e d u l ep r o c e s sb a s e do nt h r e ed i 虢r e n tm d d e l sa r ep r o v i d e d a n dt h e n ， t h ep r e s e n t e d a l g o r i t l l n li ss i m u l a t e d 谢t ht h ee x p 舐m e n tt o o ls i m 1 1 1t h i sp a p e r ，t h ef o m u l a so ft h em a x i m u m d e l a yp r o v i d et h eb a s i s f o rm ei m p r o v e de d fs c h e d u l i n gm e c h a l l i s mw m c hi sb a s e do n l e e x c h a l l g eq u e u e s a n dt 1 1 e p r i 耐t y b a n d 而d t ha s s u r 锄c e s t r a t e g y s i m u l a t i o nr e s u l t ss h o wt h a tt h ei m p r o v e da l g 耐t h n lc a i lr e d u c et h ed e l a y a n di n c r e a s et h eb a n d w i d t ha s s u r a n c er a t eo ft h er e l e v a n tn o w a sa w h 0 1 e ，t h ep e r f o r m a n c e so fn e t w o r kq o sa r ei m p r o v e d k e yw o r d s ：q u a l i t yo fs e r v i c e ，p a c k e ts c h e d u l i n g ，e a l i e i - - d e a d l i n e f i r s t s c h e d u l e ，b a n d w i d t ha s s u r a l l c es 仃a t e 鼢s i ms i 枷1 a t i o ns o f h a r e 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：御芟多少7 年月y 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ) 日期：卅年6 月驴日 日期：呻年月年日 三类主要网络业务的时间指标和调度机制研究 1 绪论 随着高速网络技术和多媒体技术的飞速发展，人们越来越多地提 出了包括多媒体通信在内的综合服务要求，在很多的工业特殊环境 下，出现了实时控制与上网服务多种综合性的服务要求。传统的分组 交换网络，如i n t e m e t ，是面向非实时数据通信( 如f t p 和e m a i l 的 传输) 而设计的，采用的t c p i p 协议主要是为了优化整个网络的数 据吞吐量并保证数据通信的可靠性。而当今的综合网络环境中，除了 有实时系统以外，还包括上网服务和分布式多媒体应用( 如视频会议、 视频点播、i p 可视电话、远程教育) ，不仅包括实时数据、文本数据 信息，还包括语音、图形、图像、视频、动画等多媒体信息。在这种 综合性网络环境中，用户对带宽、数据传输率、数据传输延迟等网络 服务质量相关参数提出了新的要求。 因此，在综合性网络环境下的网络服务质量( q u a l i t yo fs e r v i c e ， q o s ) 控制方面的研究是目前计算机网络中的热点领域。 1 1q o s 概述 1 1 1q o s 的发展现状 自从计算机系统诞生开始，就一直存在提高系统的服务性能和服 务质量的问题，因此，可以说计算机系统的q o s 问题由来已久。 对计算机q o s 的研究可以追溯到2 0 世纪8 0 年代初期。那时， 尽管网络的性能还比较低，提供的服务种类也比较少，但一些有远见 的研究者已经认识到服务质量的重要性。s e i t z 和w 6 r t e n d y k e 等人在 研究a r p a n e t 中的x 2 5 通信时已提出基于用户的性能评价问题， 这也许是关于计算机网络q o s 研究的最早文献【1 】。在早期的o s i 协议 制定中，也为服务质量的一些参数留有相应的表示手段，但一直空缺 硕士学位论文 未用。很长一段时间，由于计算机网络的性能所限，人们对q o s 的 关注只停留在数据流传输中的正确率、吞吐量、延迟等单一服务质量 的评价与控制上。直到2 0 世纪8 0 年代末期，随着b i s d n 技术以及 a t m 交换网的出现和分布式多媒体应用的急剧增加，人们才开始系 统地对q o s 管理和控制进行较为深入的研究。一些实验性系统也应 运而生，代表性的有英国兰开斯特大学的q o s a 工程【2 】、美国哥伦比 亚大学的扩展的集成化参考模型( x r m ) 系统【3 】、国际合作项目 t i n a c 工程【4 1 、美国加州伯克利大学的t e n e t 工程式【5 1 、i b m 公司 黑森伯格欧洲网络中心的h e i p r o j e c t 工程【6 】，等等。 随着h l t e m e t 商业化的巨大成功，网上传输的多媒体信息迅速增 多，网络拥塞现象日益严重，i n t e m e t 的q o s 问题研究也随之开始深 入，i e t f 于1 9 9 7 年9 月开始制定了有关q o s 定义与服务的一系列 i u c 标准，典型的工作是提出了两种不同的1 1 1 t 锄e tq o s 体系结构： 综合服务( i n t e 铲a t e ds e r v i c e s ，i n t s e r v ) 【j 7 】和区分服务( d i 仃e r e n t i a t e d s e r v i c e s ，d i 髑e ) 【8 】o 截至目前，q o s 控制技术的研究和开发都进展 得非常迅速，并且已经取得了很多基本的成果。国内也于近些年开始 了有关q o s 控制方面的研究。 1 1 20 0 s 的定义 服务质量( q o s ) 的提出是独立于宽带网络的，因为它泛指所有通 信业务的服务质量，但是宽带网络的发展使q o s 这个概念变得格外 重要。这有多种等价或互补的定义形式。 i 珂c 2 3 8 6 【9 】中描述为：q o s 是网络在传输数据流时要求满足的一 系列服务请求，具体可以量化为带宽、延迟、延迟抖动、丢失率、吞 吐量等性能指标。此处的服务具体是指数据包( 流) 经过若干网络节点 所接受的传输服务，强调端到端( e n d t o e n d ) 或网络边界到边界的整体 性。q o s 反映了网络元素( 例如，应用程序、主机或路由器) 在保证信 三类主要网络业务的时间指标和调度机制研究 息传输和满足服务要求方面的能力。 另一种描述【1o 】为：q o s 是指发送和接收信息的用户之间以及用户 与传输信息的综合服务网络之间关于信息传输的质量约定。该约定可 以被理解为服务提供者与用户之间的一份服务契约，即服务提供者承 担支持给定的服务质量，当且仅当用户按照约定的信息流特征产生数 据。换句话说，服务质量包括用户的要求和网络服务提供者的行为两 个方面，是用户与服务提供者两方面主客观标准的统一。用户的要求 是指用户在h l t e m e t 上进行多媒体通信时所要求的服务类型以及相应 的传输性能和质量等；网络服务提供者的行为则指1 1 1 t e m e t 针对某一 类服务所能提供和达到的性能与质量。 从以上两种描述不难看出，对q o s 的理解总的来说可以总结为 两类看法：一类从网络的角度出发，认为q o s 最终体现为网络性能 n p ，对应于第一种描述；另一类从用户的角度出发，认为q o s 是业 务的质量要求，对应于第二种描述。 1 1 3q o s 的技术指标 q o s 的技术指标包括多个方面的内容，如可用带宽、时延、时 延抖动、丢包率、可用性等。每种业务都对q o s 有特定的要求，有 些可能对其中的某些指标要求高一些，有些则可能对另外一些指标要 求高些。衡量q o s 的技术指标主要有以下几个方面： ( 1 ) 可用带宽 可用带宽指网络的2 个节点之间特定应用业务流的平均占用带 宽，主要衡量用户从网络取得业务数据的能力。所有的实时业务对带 宽都有一定的要求，如对于视频业务，当可用带宽低于视频源的编 码速率时，图像质量就无法保证。 为保证一些关键业务的可用带宽，在带宽设置上一般采用轻载的 方式来保证其相应的需求。对于商业用户的普通业务，带宽设计是其 硕十学位论文 实际需求的1 5 倍；对于商业用户的商业数据业务，带宽设计是其实 际需求的2 倍；对于商业用户的语音视频业务，带宽保证采用优先 队列的方式，只要有商业用户语音和视频数据过来就传送，但限制 最大可使用链路的总带宽；对于普通互联网业务，不作带宽保证， 使用剩余带宽。 ( 2 ) 时延和时延抖动 时延指数据包在网络的2 个节点之间传送的平均往返时间。所 有实时性业务都对时延有一定要求，如v o i p 业务，一般要求网络单 向时延小于1 0 0 瞄，当网络单向时延大于2 0 0i n s 时，通话就会受到 影响。时延抖动指时延的变化。有些业务，如流媒体业务，可以通 过适当的缓存来减少时延抖动对业务的影响；而有些业务则对时延 抖动非常敏感，如语音业务，稍许的时延抖动就会导致语音质量迅 速下降。 ( 3 ) 丢包率 丢包率指在网络传输过程中丢失报文的百分比，用来衡量网络正 确转发用户数据的能力。不同业务对丢包的敏感性不同。在多媒体业 务中，丢包是导致图像质量恶化的最根本原因，少量的丢包就可能使 图像出现马赛克现象。丢包通常是拥塞造成的。 在i p 网络拥塞时，对不同业务应采用不同的丢包策略。商业用 户的语音和视频业务等级最高，实施不参与w r e d 丢包策略，采用 最大带宽的方式限制对其他业务级别带宽占用；对商业用户的商业数 据、普通数据和普通互联网业务等级实施啪d 丢包策略，以预防 拥塞。为了实现各业务等级服务质量的差异性，不同等级的队列采用 不同的w r e d 参数进行丢包。总的来说，等级越低，丢包越早。 ( 4 ) 网络可用性 网络可用性是指网络节点之间在能够保证质量要求的前提下传 4 二类主要网络业务的时间指标和调度机制研究 输数据的时间占总时间的百分比，是衡量网络质量的最重要的指标。 决定网络可用性的关键技术包括路由快速收敛技术、快速重路由 ( f i 水) 技术、软硬件在线升级技术、协议平稳重启技术和设备自身可 靠性技术，另外，还与传输网络的可用性相关。 为提高网络可用性，一般建议在网络核心节点之间启用m p l s f r r ，通过m p l sf i 汛对核心链路作毫米级别快速保护；同时，在 设备条件允许的情况下，可实施路由快速收敛技术和协议平稳重启技 术，保证i g p 的快速收敛和设备路由引擎切换时不影响网络流量。 1 20 0 s 的控制机制 q o s 控制的目标是为1 1 1 t 锄e t 应用提供服务区分和性能保证：服 务区分是指根据不同应用的需求为其提供不同的服务；性能保证则要 解决诸如带宽、丢失、延迟、延迟抖动等性能指标的保证问题。 基本的q o s 控制机制包括信息流的整型机制、调度机制、监控 机制、控制机制和同步机制。到目前为止，已经提出了许多q o s 控 制机制，包括综合服务体系结构模型( i n t s e ，i n t e g r a t e ds e i c e s ) 与资源预留( 如r s v p ) ；区分服务体系结构模型( d i f ! f s e ， d i 仃e r e n t i a t e ds e r v i c e ) ；拥塞控制机制；分组调度和队列管理算法等等。 下面就这几个方面的研究状况分别作简要的介绍。 1 2 1 综合服务与区分服务体系结构 q o s 研究的目标是提供有效的端到端的服务质量控制或保证。 q o s 就是网络单元( 例如，应用程序，主机或路由器) 能够在一定级别 上确保它的业务流和服务要求得到满足【1 。q o s 并没有创造带宽， 只是根据应用程序来实现q o s 的一种方法是按照服务水平的要求 分配资源给每一个数据流。这种采用“资源预留”进行带宽分配的方 法并不适合“尽力而为型应用。由于带宽资源是有限的，q o s 的 设计者引入了优先级概念，使得在资源预留后“尽力而为”服务的数 硕士学位论文 据流的传输也能得到一定的保障。因此，i pq o s 可以分为两种基本 类型： ( 1 )基于资源预留：网络资源按照某个业务的q o s 要求进行 分配，制定资源管理策略。互联网工程任务组( i n t e m e te n 百n e 嘶n g 协k f o r c e ，i e ) 提出的综合服务( i n t s e r v ) 【1 2 】体系结构便是基于这种策略， 资源预留协议( r e s o u r c e r e s e n ，a t i o np r o t o c o l ，r s v p ) 【1 3 】是其核心部分。 h l t s e r v 通过r s v p 能够提供很好的确定服务质量保证，但是它需要 在整个路径上进行资源的预留，这种资源预留是基于软状态机制对每 个业务流实施的，软状态需要周期性地进行更新，当业务流数目很多 时，扩展性受到很大的影响，这是i i l t s e n ，最大的缺陷。 ( 2 )基于优先级：网络边界节点对业务流进行分类、整形、标 记。核心节点按照资源管理策略分配资源，对q o s 要求高的业务给 以优先处理。i e t f 提出的区分服务( d i 腮e r v ) 【1 4 】【1 5 】便是基于这种策略。 d i f j f s e 是为解决h l t s e r v 不足和缺陷提出的，它在业务的q o s 保证 和算法的复杂性方面做了一定的折衷。在d i f 俗e n ，里，引入了d i 胚e r v 域的概念，把支持相同规则d i 您e r v 功能的路由器集合称为一个 d i 船e 域。d i 髑e 域由边界路由器和中间路由器组成。边界路由 器主要完成业务量调节的功能，包括业务的测量、标记和丢弃处理， 经过边界路由器后，i p 分组被打上相应的标记( 称为d i 腮e r v c o d e p o i n t ，d s c p ) ，然后进入d i f j f s e r v 域内。中间路由器每收到一个 i p 分组，就查看其d s c p 值，然后进行相应的调度处理，这种调度处 理与d s c p 值是一一对应的，在d i 髑e r v 体系结构里，称为逐跳行为 ( p e r - h o p b e h a v i o r ，p h b ) 【1 6 1 ，逐跳转发行为p h b 是一个d s 节点调 度转发特定流聚集行为的外特性描述，p h b 可以调度转发流聚集时 的一些流特性参数( 如延迟、丢失率) 描述，当某个p h b 可能与其它 p h b 共存于一个节点时，还心须指出在分配资源( 如缓冲区、带宽) 时与其它p h b 的相对优先级。本质上，p h b 就是单个d s 节点根据 收到的分组包头的d s c p 为特定流聚集分配资源的方式。d i 腩r s e r v 体系的整体资源分配策略也就通过这个一个个单点资源分配实现的。 应该注意的是，p h b 仅是外特性描述，而不是涉及具体的实现 三类主要网络业务的时间指标和调度机制研究 机制。这类似于对象封装后的外部接口描述。p h b 的实现可以用于 队列调度与缓冲管理等各种算法，如优先队列、分类队列等。多个 p h b 定义为一个p h b 组，其中每个p h b 使用同样的缓冲区管理和分 组调度机制。厂商通过对标准p h b 的组合，可以实现自己所专用的 业务。 ( 1 )尽力而为p h b ( b e s te 肋r tp h b ) ：b e 是缺省的p h b ，对应 的是传统的尽力而为的网络传输业务。显然任何一个d s 节点都支持 b e 。i 珂c2 4 7 2 规定：当d s c p 为全零( 编码点为：“o o o 0 0 0 ) 时，也 采用b e 服务。b ep h b 具有最低的优先级。 ( 2 )快建基转发p h b ( e x p e d i t e df o r 、a r d i n g ，e fp h b ) ：e fp h b 描述的是一组用于实现低丢失率、低延迟、具有带宽保证的，以及在 d s 域中具有端到端服务质量保证的业务传输。被定义为e fp h b 的 优先级最高。e fp h b 对应的d s c p 编码为：“1 0 1 1l o ”。 ( 3 )确保转发p h b ( a s s u r e df o 懈a r d i n gp h b ，a fp h b ) ：a fp h b 实际上是一种根据相对带宽可用性和多种分组丢失优先级定义的端 到端服务的p h b 组。在业务流开始转发之前，发送方与网络节点之 间将对业务流的速率作一定的约定，这种约定称为业务流的轮廓。在 a fp h b 中，网络节点将允许业务流的速率大于这一轮廓，但是，网 络节点将对超出轮廓的业务流分组采用较大的丢弃优先级。根据这一 思想r f c 2 5 9 7 对a fp h b 定义了4 个服务类和3 级优先级，并用 a f x y 表示a f 服务类x 具有丢弃优先级y 。服务类提供了分组用于 选择适当的队列的依据，而每个队列的分组丢弃器则可以根据分组的 丢弃优先级来进行拥塞处理。 本文主要研究这种基于优先级( 即区分服务) 的q o s 保证策略。 1 2 2 分组调度算法 当前在分组调度算法方面的研究很多。各种文献中提出的分组调 度算法有：p q 算法、e d f 算法、帆r 算法等；队列管理算法主要 是主动队列管理算法：r e d 算法，w r e d 算法、r e dg e n t l e 算法等。 硕士学位论文 分组调度的好坏直接影响着q o s 性能指标的实现，因此在因特网中 采用合适的算法是非常重要的。 分组调度的目的在于提供不同等级的q o s ，满足不同业务流的 带宽、延迟等要求。概括地说，算法性能的好坏主要涉及到时延性能、 公平性和复杂性【17 】这三个因素。 ( 1 )时延性能 分组调度算法应为不同的业务流提供端到端的时延保证，而且只 与此业务流的某些参数( 如带宽需求等) 有关，而与其它业务流无关。 本文在第三章主要考虑不同业务流的时延。 ( 2 )公平性 公平性是一个非常重要的因素。由于多个流共享资源，既要保证 每个流的q o s 需求，又要尽量使各流之间不受彼此影响，保证流的 分割性，这样可以避免恶意攻击者占用大量的共用信道。关于公平性 的定义主要有三种： 服务公平指数s f i 【1 8 1 、最坏公平指数岍i 【1 明； r 刮j a i n 公平度量因子2 0 】； 比例公平原则以及林闯等提出的综合性能评价标准【2 1 】。 ( 3 )复杂性和可扩展性 复杂性直接决定算法能否实现。速度的不断提高和规模的不断扩 大是网络发展的一个趋势。在高速网络中，交换机构必须能够在很短 的时间内完成调度转发，这就要求调度算法在调度计算过程中应该尽 量简单。此外，当业务流数量增加和链路速率变化范围较大时，调度 算法仍能有效地工作，即要求算法具有良好的可扩展性。无线调度中 由于必须考虑到很多的信息，算法的复杂性很高。设计一个有效的算 法并降低实现的复杂性是调度研究领域追求的目标。 三类主要网络业务的时间指标和调度机制研究 1 2 3 拥塞控制 在计算机网络中的链路容量( 即带宽) 、交换结点中的缓冲和处 理机等，都是网络的资源。在某段时间，若对网络中某一资源的需求 超过了该资源所能提供的可用部分，网络的性能就要变坏。这种情况 就叫做拥塞( c o n g e s t i o n ) 【2 2 1 。可以把出现网络拥塞的条件写成以下 的关系式： 罗对网络资源的需求 网络可提供资源 ( 1 1 ) 拥塞导致的直接结果就是分组丢失率提高，端到端延时加大，甚 至可能使整个系统崩溃。 所谓拥塞控制就是防止过多的数据注入到网络中，这样可以使网 络中的路由器或链路不致过载。 拥塞控制算法包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制 ( c o n g e s t i o nc o n 仃0 1 ) 这两种不同的机制【2 3 1 。拥塞控制是“恢复”机制， 它用于把网络从拥塞状态中恢复出来；拥塞避免是“预防”机制，它 的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延迟的 状态下。根据算法的实现位置，可以将拥塞控制算法分为两大类：链 路算法( 1 i 1 1 1 ( a l g 嘶t h m ) 和源算法( s o u r c e a l g 嘶t h m ) 2 4 1 。链路算法在网络 设备( 如路由器和交换机) 中执行，作用是检测网络拥塞的发生，产生 拥塞反馈信息。源算法在主机和网络边缘设备中执行，作用是根据反 馈信息调整发送速率。拥塞控制算法设计的关键问题是如何生成反馈 信息和如何对反馈信息进行响应。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是 目前在i n t e m e t 中使用最广泛的传输协议。根据m c i 的统计，总字 节数的9 5 和总报文数的9 0 使用t c p 传输。近年来，t c p 中采 用了很多新的算法，包括慢启动( s l o ws t a n ) 、拥塞避免、快速重传( f a s t r e t r a n s m i t ) 、快速恢复( f a s tr e c o v e 啪、选择性应答( s a c k ) 等，大大提 硕士学位论文 高了网络传输的性能。t c p 中使用的拥塞控制算法已经成为保证 i n t e m e t 稳定性的重要因素【2 5 】。 1 3 论文组织及主要研究内容 本文基于同时具有实时、带宽保证和尽力服务三类主要业务流的 综合性网络环境，提出了在此环境下的e d f 改进算法_ r a b e d f 算法，围绕改进算法进行了一系列研究。论文章节组织如下： 第一章在分析当前q o s 发展状况的基础上，阐述了网络的服务 质量，包括q o s 的定义、技术指标；然后重点介绍q o s 的控制机制， 最后指出了本文的主要研究内容及论文组织情况。 第二章分析了当前网络环境中三类主要的网络业务一实时、带 宽保证和尽力服务。而后在本章结尾例举了具有三类主要网络业务的 应用环境。 第三章从t c p 和u d p 协议入手，根据初步设定，得出了计算实 时业务流和带宽保证业务流时延的公式，为改进算法的判断条件提供 了很好的依据。 第四章描述了基于交换队列的e d f 调度机制黜惦e d f 算 法。首先介绍了交换结构，重点讲述了c r o s s b a r 结构，为第五章的仿 真结构做下铺垫，而后从传统e d f 调度算法出发，提出了一种新的 带宽保证策略，根据这种策略，提出了改进的调度算法，利用三种不 同的模型对凡心e d f 调度算法进行阐述。 第五章首先简单介绍了s i m 仿真平台，然后根据s i m 平台的特 殊性，提出了算法的设计与实现，最后给出了仿真环境的构建和通信 量的模拟过程，根据模型的构建进行模拟实验，对仿真结果做出了分 析。 结束语总结了本文的主要研究工作，并阐述了将来进一步的工作 计划。最后是参考文献和在攻读硕士期间发表的论文。 三类主要网络业务的时间指标和调度机制研究 2 三类主要网络业务 对现阶段的大多数网络用户来说，伴随着多媒体技术的飞速发 展，i n t 锄e t 已经逐步由单一的数据传送网向数据、语音、图像、视 频等多媒体信息的综合传输网演化。而在许多的工业化控制系统中， 还包括多个实时系统和一定数量的带宽保证用户，所以既包括实时数 据传递、又包括带宽保证数据和i n t e m e t 尽力服务的综合性网络环境 开始大量出现。而在这种环境中主要涉及到三类主要网络业务：实时 业务、带宽保证业务和尽力服务业务。 2 1 实时( r e ai _ tim e ) 业务 近年来，随着互联网( i n t e m e t ) 的迅速发展，i n t e m e t 已由单一的 数据传输网向多业务承载网演进。以前那种以e m a i l 、文件传输等为 主的单纯的数据传输业务已远远不能满足用户的需求，一些实时应用 如视频点播( v i d e oo nd e n l a n d ，v o d ) 、i p 电话( v r o i c eo v e ri p ，v o i p ) 、 远程教学不断涌现。业务对网络性能的要求直接来源于业务对端到端 客户感知的满意程度的需求，而实时业务的最大特点就是对时延和抖 动非常敏感。 2 2 尽力而为( b e s t e f f o r t ) 业务 在尽力而为服务( b e s t e 肺r ts e r v i c e ) 模型下，所有的业务流被 “一视同仁 地公平地竞争网络资源，路由器能够对所有的i p 包都 采用f c f s ( 先来先服务) 的工作方式，它尽最大努力尽力而为地把 i p 数据包从发送方送达接收方，但对i p 包传送的可靠性、延迟等不 能提供任何保证，这种服务很适合e m a i l 、f t p 、w w w 等业务。 硕士学位论文 2 3 带宽保证( b a n d w id t ha s s u r a n c e ) 业务 白区分服务概念出现以来，奖赏服务p s 【2 6 】与确保服务a s 【2 刀是讨 论最为集中的两种典型服务，最初分别由j a c o b s o n 和d a v i d d c l 砒提出，文献【2 8 】首次将两者统一在一个框架中。正是对这两种 服务的深入讨论导致了e f 与a f 两种p h b 的产生。 a s 的初衷是：在网络拥塞的情况下仍能保证用户拥有一定量的 预约带宽，使用户摆脱在单一尽量做好时无法把握自己实际占有带宽 量的无奈窘况；着眼点是带宽与丢失率，不涉及延迟、抖动。 在a s 服务框架下，i s p 和用户之间签定服务简本r 0 6 1 e ) ，规 定了合约带宽，网络将保证用户获得约定的带宽。实现原理是：网 络通过“令牌桶算法对用户发送到网络的分组包进行测试，在合 约带宽之内的分组标记为i n ( i np r o f i l e ) ，之外的分组标记为 o u t ( o u to fp r o f i l e ) ；当网络某节点发生拥塞时，网络通过o ( r e d w i t h 仆o u t ) 等算法对分组进行丢弃。网络通过适当的带宽规划 和带宽过提供，可以向用户提供带宽保证服务。 带宽保证业务是d i f j f s e r v 模型中的一种基于分组标记和丢弃机 制的转发服务。 带宽保证业务原则是：无论是否拥塞，保证用户占有预约的最低 限量的带宽；当网络负载较轻而有空闲资源时，用户也可以使用更多 的带宽。则用户最终实际得到的带宽分为两部分，预定最小保证值以 及与其他a s 流或b s 流竞争剩余资源获得的额外带宽。 2 4 应用环境举例 某些工业环境往往有一个或多个用于监测和或控制的周期性实 时系统，而今，这样的环境也难以抵御i n t e m e t 的吸引和渗透。如果 在单个系统中，既能保证实时数据的正常传递，又能与i n t 锄e t 连通 三类主要网络业务的时间指标和调度机制研究 实现尽力服务，应该是一个值得研究的课题，这就是本课题中提到的 一种综合性网络环境。 如在一个分布式化工控制系统中，现场的实时信息周期性地被采 集，然后送到现场控制柜和或控制室显示，并可能要根据事先的设 定实时对现场进行控制例。如果地理范围较大( 如数公里) ，工厂可能 还要安装火灾报警系统、电话系统甚至视频防盗系统。由于历史原因， 这些系统往往自成体系，安装和维护难以统一，费用较高。另外，随 着1 1 1 t e m e t 这一精彩世界的吸引，在现场某些场所能够上网的要求自 然出现。例如，有些车间主任的办公室就在现场附近，既要求随时能 对现场工业参数进行监测，中午休息甚至工作时又要上网，这样的地 方离生活区和闹市又远，那么，i n t e m e t 将以一名新成员的身份出现 在厂区，怎么办? 单独布线，设置交换设备，恐怕不是最佳的长远选 择，尤其对于新上马的工厂。可以考虑将这里提到的众多系统与互联 网归并在一起，在适当的地点设置i n t e m e t 交换机，尽量采用与i n t e m e t 相关的一些成熟软硬件技术，从而降低整个工厂的安装和维护工作 量，且可以容易实现远距离( 如外地出差) 监测。 这样，自然想到在互联网中进行实时数据传递的问题。所以在这 样一种综合性的工业环境中，既提供了实时业务，也提供尽力而为的 上网业务，还可以有一定特殊服务的带宽保证业务。这就是本论文中 调度机制的环境基础。 2 5 小结 在本章中主要介绍了三类主要网络业务实时、带宽保证业务 和尽力服务业务，并且就这三类业务的主要特点进行了简单介绍。 在现实网络应用环境中，特别是在很多工业控制环境下，同时具 备了三类主要业务流的网络环境比比皆是，本章最后例举了一个常见 的应用环境，为以后章节的研究环境作了很好的铺垫。 三类主要网络业务的时间指标和调度机制研究 3 基于t c p 和u d p 协议的有关性能指标研究 因特网的迅速发展，特别是大量实时多媒体业务的出现，都在不 同程度上对网络服务质量( 哪a l i t yo f s e r v i c e ，q o s ) 提出了要求。目 前，i n t e m e t 正逐步由单一的数据传输网向数据、语音、图像等多媒 体信息综合传输网发展，但是现有的i n t e m e t 仍然只提供传统的基于 f i f 0 的尽力而为( b e s t e 肋r t ，b e ) 服务，无法满足实时多媒体应 用和各种用户在带宽和时延等方面的具体需求。近年来，提供不同业 务q o s 支持，并满足用户多样的需求，一定程度上满足某些性能指 标将是m t e m e t 网络能否成功商用化的一个关键性和挑战性课题。 在这种提供多种业务的网络中实时数据的实时传递也是不可忽 略的。所以服务的时间成为要考虑的一个重要性能指标【s o 3 1 。而实 时性保证一般要参照最坏情况，即要对最坏情况的最大延迟心中有 数。因此，在这种多种业务并存的网络中实时队列的最大时延即最长 等待时间是需要解决的问题。本章以t c p 和u d p 协议为基础，利用 t c p 拥塞控制方法，提出了带宽保证业务流和实时业务流的最大时延 计算公式。 3 1 协议概述 在当前常用的网络中，特别是因特网，为网络用户的应用程序提 供了两类服务：无连接服务和面向连接的服务。面向连接服务称为传 输控制协议( t r a j l s m i s s i o nc o n 仃0 1p r o t o c 0 1 ，t c p ) 。t c p 提供给用户 的服务包括可靠传送、流控制和拥塞控制。无连接服务称为用户数据 包协议( u s e rd a t a g r a mp r o t o c o l ，切) p ) ，无连接服务没有流控制和 拥塞控制的功能。 硕士学位论文 3 1 1t c p 协议 该协议主要用于在主机间建立一个虚拟连接，以实现高可靠性的 数据包交换。在该协议传输模式中在将数据包成功发送给目标计算机 后，t c p 会要求发送一个确认；如果在某个时限内没有收到确认，那 么t c p 将重新发送数据包。另外，在传输的过程中，如果接收到无 序、丢失以