（计算机应用技术专业论文）面向二级运营商的qos研究、设计与实现.pdf

四川大学硕士学位论文 面向二级运营商的q o s 研究、设计与实现 计算机应用技术专业 研究生吴芄臻指导老师李志蜀教授 进入2 0 世纪9 0 年代后，以因特网( i n t e r n e t ) 为代表的计算机网络得到 飞速发展。它所取得的巨大成就和未来所蕴涵的巨大发展潜力几乎没有人怀疑。 i p 业务多样化和快速增长已经成为一个不争的事实。使用它的人也越来越多， 并且用户发展速度已经大大超过网络设施和技术的发展速度。正因为这样，网 络资源变得很珍贵。如何充分利用有限的资源，如何在i p 网络上保证用户信息 传输质量就成为一个热门的，实际并且不容忽视的重要问题。为了解决这一问 题，i pq o s 应运而生。 i pq o s ( q u a li t yo fs e r v i c e ) 是指i p 的服务质量，也是指i p 数据流通 过网络时的性能。它的目的就是向用户提供某种业务服务质量的保证。它有一 套度量指标，包括业务可靠性、延时、延时抖动、吞吐量和分组丢失率。 当前可用的基于优先级的q o s 策略一般对于各种级别的数据流都有严格的 带宽分配机制或者抢占机制。这些机制对于小型运营商来说就不是很适合，这 些运营商同时运营了很多的业务：网络游戏、v o i p 等，这些服务都要求低延时， 无丢包。对于这种情况传统的c q ，p q ，1 f q 都无法满足他们的要求，于是满足 这些要求的一种新的q o s 策略便产生了。 本文从整个网络的性能着手，讨论一种结合流量整形功能的全新的q o s 理 念。不仅在本级路由器提高了各种不同的高优先级数据的服务质量。而且考虑 到下级路由器的负载能力，加上了流量整形功能，在流量高峰时期将来不及发 送的数据进行存储转发，避免了在网络发生拥塞的时候进一步加剧网络的拥塞 状况，这样就将原来在网络上其他路由器上出现的瓶颈消除，为我们后面的q o s 的实现提供了物理基础；而在后面的q o s 的设计过程中，以排队论作为理论基 础，设计实现了基于优先级的排队算法。使得高优先级的数据能够享受到一个 比较高的服务质量。 婴型盔堂堡主兰垡堡兰一 关键词：路由器，q o s ，拥塞管理，流量整形，优先级，排队管理，调度 坚型奎堂堡主堂垡堡奎 t h er e s e a r c h i n g ，d e s i g n l i n ga n dr e a l i z i n go fq o sf o rt h e s e c o n d a r yi s p p o s tg r a d u a t ew u p e n g z h e n s u p e rv i s o r l i z h i s h u a b s t r a c tf r o mt h eb e g i n n i n go ft h e2 1 t hc e u t l l r y + t h ec h a r a c t e r so ft h es o c i e t y s e 圮mt ob ed i 百t a i ，n e t w o r k , a n di n f o r m a t i o n i t sc l e a r l yt h a tt h eg l o b a le c o n o m yw i l lt u r ni n t ok n o w l e d g ee c o n o m y a n dt h e t w oi m p o r t a n tc h a r a c t e r so fi tw i l lb ei n f o m a t i o n a la n dg l o b a l t om a l i z a t et h e m , w e s h o u l tg e tt h ew e l ls u p p o r to f t h ec u r r e n tn e t w o r l a f t e rt h e9 0o ft h e2 1c e n t u r y , t h ei n t e r n e th a sg e tad a z z l i n ge v o l u t i o n n o b o d y w i l ld o u b l ea ti t sa c h i e v e m e n ta n dt h ep o t e n t i a l i t si m p f i c i tt h a tt h eo p e r a t i o no nm i sd i v e r s e da n di n c r e a s e dq u i c k l y m o r ea n dm o l ep e r s o nb e g i nt ou i t , a n di t s d e v e l o p m e n ts p e e dh a v eb yf a rb e y o n dt h ei n t e m e tt e c h n o l o g ya n dt h en e t w o r k e s t a b l i s h m e n t f o rs u c hr e a s o n , t h en e t w o r k e s o t i r c 七b e c o m er a r i t y s o h o w6 0 u t i l i z et h e ms u f f i c i e n t , h o wt og i v eo u ru s e rah i 曲q u a l i t ys e r v i c e ，b e c o m eab i g q u e s t i o n t or e s o l v ei t , q o sc o m e s i n t ob e i n g q o si st h eq u a l i t yo fs e r v i c eo fi p i t so r d e rt op r o v i d et h ec e r t a i nu s e rw i t h t h er e l i a b l es e r v i c et ot h ec e t t a i ur e q u i r e m e n t i ti sj u d g e db ys u c hp a r a m e t e ra s u s a b i l i t y , l a t e n c y , j i t t e r ，e t ca 1 1 t h et r a d i t i o n a lq o sf o c u so r t h el o n e l ym u t e ri t s e l f w h i l et h ed a t as t r e a mp a s st h r o u g hi t , i tw i l ls e r v et h eh i g hp r i o r yd a t af i r s t b u t i m p r o v i n gi t s e l fw i un o ti m p r o v e t h ew h o l en e t w o r kc a p a b i l i t yg r e a t l y a n dt h e m p l si st o oe x p e n s i v ef o rm a n yc o m p a n yt ol l s ci t t h i st h e s i sf o c u so nt h ec a p a b i l i t yo ft h ew h o l en e t w o r k o u rq o sn o to n l y i m p r o v ei t s e l f , b u ta l s oc o m b i n e w i t ht h em o n i t o rc o n t r o lf u n c t i o nt oi m p r o v et h e w h o l en e t w o r k i tb a s e do nt h et h e o r yo fq u e u e i tc a l lc o n t r o lt h ef l u xw h e ni tg e tt o ah i g hs p e e d w i t ht h a tw ec a l li m p r o v eo u rn e t w o r kg r e a t l y k e yw o r d s ：r o u t e r , q o s ，f l u xc o n t r o l , p r i o r i t y , q u e u em a n a g e m e n t , a t t e m p e r m 四川大学硕士学位论文 第一章引言 进入2 0 世纪9 0 年代以后，以因特网( i n t e m e t ) 为代表的计算机网络得 到飞速发展，已从最初的教育科研网络逐步发展成为商业网络，并已成为仅 次于全球电话网的第二大网络。然而，随着人们对i n t e m e t 的要求与日俱增， 计算机网络这条令人振奋的“信息高速公路”却出现了许多无法解决矛盾问 题。 作为一个给人以深刻印象的、世界范围内网络互连的集成，i n t e r n e t 以各 种速度将大量的信息传送到各种不同的地点，因此可以说i n t e r n e t 真的就像高 速公路一样。但是，大多数人都有过这样的经历，这个所谓高速公路却常常 会给我们带来不可预料的服务，因此我们几乎不能否认i n t e m e t 发展中出现的 “世界范围的等待”的存在f 1 1 。这条信息高速公路有时候就好像是一条到处 是积水而且正在施工中的街道，为减轻交通流量，通常会根据其重要性选择 一些分组，对其进行延迟发送或彻底丢弃。服务质量( q u a l i t yo f s e r v i c e ，q o s ) 就是要最大限度减少这类问题的发生【1 1 。 1 1 如s 产生的原因 我们为什么需要服务质量? 这是因为i pq o s 是未来口网络发展的关键技 术，之所以这样说，是因为i pq o s 是口网络增加服务内容、提高服务质量 的关键技术，也是未来网络运营商竞争的一个焦点【2 】。为了充分利用有限的 带宽提供最大最好的服务，q o s 便在这种情况下产生了吲。 1 1 1i p 的基本问题 与生活中的大多数事情一样，人们对q o s 也存在着不同的看法。对于一 个具有传统网络操作背景的人来说，q o s 是网络的一个长期可靠性和可甩性 的问题。( 连接网络的时间是一天几个小时、一星期几天还是一年几个月? ) 其引申的含义是用户在相当短的时间内一即保持网络连接和传输分组的过程 中对网络行为的看法【n 】。这时，q o s 就变成了一系列问题，包括传输速度、 四川大学硕士学位论文 分组传送的及时性、网络给分组流带来的抖动总量以及分组丢失的概率【1 9 1 。 这些问题其实就是关于在网络内部出现设备失效的时候如何使网络性能 实现平稳降级的工程性问题。网络中单个组件( 如路由器、交换机或链路) 的可靠性到底有多高，关键设备是否都需要进行冗余配置以保证其连接可靠 性当冗余设备投入运行的时候，其连接的质量如何( 包括可用的带宽、延迟、 突发性以及分组丢失的概率等) 。在一个网络连接质量由短期问题转变成一个 连接性丢失的长期性问题以前，可以容忍多大程度的网络性能下降。 当般用户发送其分组的时候一般都不会去注意口网络的内部情况。然 而，在能够决定什么技术适于增强网络的q o s 能力之前，必须了解现有m 网络的弱点。这些弱点可以总结如下： 在发生瞬时拥塞时，路由器提供的响应时间是不可预测的。 对不同的业务流类型不能提供优先级的服务。不能动态地请求( 或修改) 端到端的服务质量。 只有有限的蛆制可以用于审计网络资源使用情况。 1 1 2q o s 的概念 所谓q o s 是网元( 如主机、路由器或网关) 在一定条件和程度上能够满足流 量及业务需求的能力。q o s 并不能增加网络的带宽资源，只是根据业务的需求 和网络。当网络比较繁忙的时候，牺牲一部分用户的利益保证另外一些特殊 用户的利益。 当然，为了区别这些不同的用户级别，以及为这些用户分别提供不同质量 的服务，会为系统带来额外的一些开销。 1 2 需求分析 当前，在社会中大量存在着一些小型网络运营商，他们从类如电信，网通 之类的大型i s p 那里购买了一些带宽，然后为他们的用户提供类似于大型运 营商所能提供的服务，只是他们的能力以及规模要小得多，同时，他们会利 用他们的带宽提供一些其他的业务为自己赢乖j 。 然而当用户规模以及业务不断的增多的时候，带宽会变的相对自q 越来越狭 窄。当然，购买更多带宽可以很好地解决上面的问题。然而，带宽昂贵的价 2 四川大学硕士学位论文 格并非是所有人都能够承担的了的。 在这种情况下，这些小型运营商就提出了这样一些要求：在网络流量不繁 忙的时候，各个级别数据正常发送；当网络很繁忙的时候，尽量利用用户对 各种数据的忍耐极限，尽量优先满足高优先级数据的服务质量。例如：据统 计，用户对旺b 数据延时的最大可忍耐0 5 秒。也就是说，当网络流量达到 峰值，来不及发送的时候，可以将w e b 数据尽量延后发送，以保证高优先级 数据的服务质量。 据调查，现在的小型运营商一般运营的业务般有以下这些：网络游戏， 语音电话，用户，以及般的普通用户。 1 3q o s 最关键的几个因素 ( 1 ) 业务可靠性：用户与i n t e r n e t 业务连接的可靠性，包括建立时间和保持时 间等： ( 2 ) 时延：也称延迟，指在两个参考点问，某口包从发送到接收之间的时间间 隔： ( 3 ) 延时抖动：是指沿同一路径传输的一个数据流中，不同分组传输延时的变 化： ( 4 ) 吞吐量：网络中口包的传输速率，这一参数可用平均速率或峰值速率表 示： ( 5 ) 包丢失率：业务在网络中传输时，允许的最大丢包率。 现有的q o s 路由算法可以分为链路优化、链路约束、路径( 或组播树 ( m u l t i c a s t t r e e ) ) 最优化、路径( 或组播树) 约束等相关问题以及它们的组合问 题：按照算法的性质，可以分为单播( u n i e a s o 源路由、单播分布式路由、组播 f m u l t i c a s t ) 源路由、组播分布式路由、分层路由等。为了解决容错性问题，还 需要诸如多路路由、重路由等算法。针对网络服务质量控制的要求，目前已经 形成了一些相应的q o s 网络协议。如r s v p ，i n t e r 2 s e r v ，d i f f s e r v ，m p l s 等，用 于解决碑网络、a t m 网络、光网络、无线网络、卫星网络等各种网络的服 务质量控制问题。以下将先介绍当前网络状况和需求分析，再对各种路由方式 逐一分析并将近年来国内外比较出色的q o s 路由算法和路由协议作了分类 介绍，结合对最近该领域的些新的研究热点的剖析，在总结现有问题的基础 3 四川大学硕士学位论文 上，展望了未来q o s 路由算法的发展趋势【7 1 。 分组沿着由链路和路由器构成的通路传输。路由器和链路的互连可能构 成任意的拓扑结构，它们需要使用路由协议来为每个分组寻找其合适的通 路到达目的地。路由器本身就像是一个数十、数百以至数千不相关分组流的 汇聚点和分支点。数据应用程序可能产生许多具有数据突发( 其中存在静态 的间隔时间) 或者有着均匀分组间隔的分组流。当突发的分组同时到达时， 其数据量会超过路由器的瞬时分组传送能力，这些试图通过该路由器的分组 都将经历一个附加的延迟时间。( 这与飞机起飞前机场检票以及在交通高峰期 试图通过拥挤的交叉路口、收费站公路或隧道的等待情形没有什么不同。) 路 由器和交换机要承受瞬时的网络拥塞，并缓冲到达的过量分组，直到它们被 发送出去。( 当瞬时的网络拥塞变得很严重时，缓冲区可能溢出导致分组被完 全抛弃) 1 1 0 1 。在提供q o s 时最关键的三个因素如下： 在发生瞬时网络拥塞时，路由器如何处理不同种类的分组。 路由器如何利用底层链路的q o s 特性。 在本身实现q o s 的时候，还要考虑，自己下面一级路由器的接受能力。 任何分组所经历的延迟时间都是由经过每一条链路的传输延时以及在每 一个路由器中的处理延时( 包括缓冲延时和排队延时) 组成的。 抖动是路由器中由拥塞导致的不可预料的缓冲延时造成的，缓冲延时每时 每刻都是不断变化的，即使是对那些去往同一个目的地的分组也是同样。为 尽力而为的i n t c m e t 而建造的路由器并不能区分来自不同应用程序或不同用 户的分组。但是，我们所需要的是路由器能够对不同种类的分组提供不同的 延时和抖动特性参数。 1 4 排队论在o o s 中的应用 机场的登机检票过程是一个很好的例子。有若干检票员一起尽可能快地向 乘客提供服务。但机场中有许多等级不同的旅客，他们希望得到更快捷的登 机服务。为了达到这个目标，机场必须在登机柜台前建立多个队列针对 航班中的每一个服务等级有一个队列( 通常可根据乘坐航班的频繁程度) 。把 乘客分成不同的队列，这可以使服务员能够加速处理那些航班中付出了额外 费用的旅客的登机手续。这样的机制所达到的效果就是，与那些经济舱的旅 4 四川大学硕士学位论文 客相比，付出了额外费用的旅客可以得到更快捷的( 排队短，因此延迟小) 和更可预测的( 更小的延时抖动) 检票和登机服钳3 7 】。为了建立一个具有q o s 能力的i n t e r n e t ，网络的设计者必须开发和配置新型的路由器，这些路由器能 够将分组划分成不同的类型，在网络拥塞的时候对不同类别的分组分别进行 排队，并为每一类别分配唯一的处理优先级。有了这些工具以后，网络的设 计者就可以开始控制那些付出了额外费用的客户的端到端的延迟和抖动。 然而，仅仅在单个路由器中提供区分的分组处理能力还是不够的。在把具 有q o s 能力的i n t e r n e t 变成现实以前还需要进行两种功能的开发：信令和统 计计费。从最广泛的意义上说，信令是指在端到端的通路上建立流分类和服 务规则的过程。( 实际中存在多种机制，在操作的不同时期其功能是不同的。) 除此以外，还必须对每一个人使用资源的情况进行计费。路由器容量和链路 的带宽既不是免费的也不是无限的。任何对某些业务类别提供优先服务都意 味着对其他的业务类别进行了与之相当的限制。如果没有一种相应的机制对 用户使用的各种资源进行统计计费和控制，那么每一个人都会请求最好的服 务，这将使网络回到最初的那种没有q o s 的时代。 对资源的使用进行计费由两个组成部分。首先，申请使用特定资源的请求 必须要经过鉴别( 目的是要精确记录合法的请求，防止那些没有相应权限的 用户恶意破坏资源分配过程) 。其次，应当对用户使用资源的实际情况进行监 视和跟踪( 目的是记录用户对网络的实际需求) ，在可能情况下还要进行鉴别 ( 以确保使用了特定用户所申请的资源的分组确实是来自于该用户) 。服务提 供商最终将利用这些统计信息根据其市场和营销计划来对他们的客户进行计 费。 为什么我们在本身实现了q o s 君，还要考虑到对方的接受能力? 仍然以机场的登机检票过程为例子。假设在进入机场的剪票窗口有足够多 的剪票员，让来到的旅客几乎没有排队就被检查并通过，而在每个飞机的登 机口只有一个剪票员，所有的游客几乎按来到机场的顺序在登机口排队。这 样的话，堵塞依然存在，只是存在的地点不同。这个时候，高优先级游客仍 然没有享受到应该享受到的高质量服务。如果我们在剪票1 3 限制了迸场平均 人头流量，在这个基础上实现我们的q o s ，那么到达登机1 2 1 的旅客的顺序是 已经经过排队的流量，这个时候高优先级的用户就能够优先登机。如果我们 5 婴删奎堂堡主堂垡堡壅一 在路由器中也加上同样机制的o o s 策略，那么在网络发生拥塞的时候，我们 就可以将来不及发送的数据存储在路由器缓存中，并在路由器中进行排队整 形，先保证高优先级的数据优先被发送出去，低优先级的数据就可以等到网 络不拥塞的时候发送出去。这样，虽然在我们本级路由器增加了开销以及延 时，但是从整个网络来看，就能起到高优先级数据享受高质量服务的一个q o s 作用。 6 四川大学硕士学位论文 第二章系统设计与数学模型设计 通常来讲，提供高性能网络保证途径有：过度建设，消除拥塞，软件实现 q o s 。 1 过度建设：这个方案靠提供大量带宽来满足用户的业务需求。在局域 网中，相对较低的成本提供高的带宽是可能的，过度建设方案在l a n 中也有 广泛应用。但是，在广域网中，w a n 带宽价格对于大多数用户来说，仍然太 高，所以现阶段，过度建设方案在w a n 中并不是很适用。 2 消除拥塞：包括拥塞控制与避免机制。拥塞控制机制使终点站在网络 发生掉包时降低传输流速度。该方案适用于终点站，而不适用于中间路由器。 以上两种种方案由于成本等各方面原因，并不适用于当前的疋电话传输的 q o s 保证2 ”。 3 软件实现q o s ：i e t f 已经建议了很多服务模型和机制，以满足q o s 的需求。其中比较有名的有：综合业务模型( i n t - s e r v ) ，区分业务模型 ( d i f f - s e r v ) ，多协议标记交换( m p l s ) ，流量工程和约束路由【2 3 1 。 综合业务的特点是资源预留，实时应用在传输数据前必须首先建立通道和 预留资源。r s v p 是用来建立通道和预留资源的协议【2 7 1 。 在区分业务模型中，把包加以标记，产生不同的级别，每个级别的包得 到不同的服务级别。 m p l s 是一种前向转发策略，在进入m p l s 作用域时给包赋予一定的标 签，随后包的分类、转发和服务都将基于标签完成f 1 3 】。 流量工程是一种安排通信流量如何通过网络的过程。 约束路由在寻径路由时会受到一定的约束，如带宽或延时的要求。 如果考虑成本的因素，那么把区分业务模型与流量工程结合起来，以设定 优先级和队列方法替代过度建设成为q o s 发展的重要途径。 优先级是指对每个m 数据包的级别进行分类，不同级别的数据包在网络 进行预留带宽，通过顺序，延时抖动，丢包等方面的处理时，所受到的待遇 是不同的，这样可以确保类如语音，视频等对实时性要求比较高的数据包享 受高的服务级别，从而提高其传输质量。 数据的优先级体系在特征上可分为隐式和显式两种。当具有隐式q o s 时， 7 四川大学硕士学位论文 路由器或交换机自动根据管理员制定的规则分配服务标记，制定的规则包括 应用类型，协议或源地址路由器或交换机对每个接收到的包进行检查或过滤， 判断它是否满足规则规定的要求。而显式q o s 是用户或应用通过请求得到特 定优先级的服务，交换机和路由器努力满足该服务请求。m 优先级( i p p r e c e d e n c e ) ，即所谓的m 服务类型( i p t y p eo f s e r v i c e ，t o s ) 可能会成为最 广泛应用的显式q o s 技术【3 6 1 。 队列：队列和队列算法是在已经应用了优先级的前提下采用的一种q o s 方案。队列实际上是路由器或交换机内部的一块缓存区，用来存储带有优先 级别的碑数据包。队列算法是一种特定的算法，用来确定存储在队列中的数 据包的发送顺序，算法的思路是，对优先级高的包将提供更好的服务。 由此可以看出优先级和队列的方法比较适合我们路有器的q o s 方案。在 此，我们采用两者结合，即基于队列的优先级竞争方法。 我们所设计的这个系统是为用户提供一种可以按照用户不同需求而实现 不同调度机制的q o s 策略。该策略是基于优先级的，对不同数据提供不同级 别服务。 整个系统至少需要包括下面三个部分：提供给用户的可操作接口，路由器 中入口数据包优先级识别以及添加标志部分，路由器出口部分数据包转发模 块。 用户可操作接口可以为用户提供相应的接口，主要实现如下功能：配置静 态路由、配置q o s 参数、设置路由转发功能启动选项、设置q o s 启动选项。 入口数据包优先级识别以及添加标志部分，主要实现如下功能：根据用户 的配置，或者是系统默认的配置，识别出不同优先级的数据包，并且加上标 志。 路由器出口部分数据包转发模块，主要实现如下功能：对不同级别的数据 包进行排队，并且根据q o s 策略从各个队列中取出数据包交到低层发送队列 中。 系统结构如图2 1 所示。 ， 8 堕型查堂堡主兰篁堡壅 癣 錾 囊 一王一一一一 摩 嚣 疆 图2 - l 系统结构图 9 四川大学硕士学位论文 下面对各个功能模块进行详细的分析和设计。 2 1 用户控制模块 该模块的功能是为用户提供操作接口。用户可以通过一些预先定义的操作 来修改一些q o s 的配置参数和一些路由器所必须的一些信息。 但是需要注意的是，用户操作是在用户空间完成的。而这些操作最终需要 达到的结果是要对操作系统内部的网络模块的一些参数进行修改，所以这里 必须要实现用户空间以及l i n u x 操作系统内核空间的切换。 2 2 数据包优先级识别以及添加标志 2 2 1 数据包优先级的识别 数据的优先级的识别可以通过两种方式实现：通过软件实现让路由器自己 识别和人为干预的手工识别。 根据现在的网络实际情况，对游戏数据和v i p 数据通过人为干预的方式 帮助路由器识别它们。这是因为基于现在的网络通用协议，我们没有办法从 内容上识别出一个数据包到底是什么包。这样的话，路由器是没法知道某一 个包是不是游戏包。 所以我们就采用用基于地址的方式来判断，而且这个方法对v i p 数据及 游戏数据进行识别相当有效。为了实现这个方法，我们会在用户空间提供一 个配置文件，里面保存了网络游戏服务器的m 地址，v i p 用户的口，以及一 些用来标志游戏数据的参数，然后再输入延时，丢包率，抖动等信息，这些 数据在内核空间被识别，再由我们的程序来打上优先级标记。然后送入队列 中排队，等待发送。 对于语音显然用上面的方法不是很完善，因为p 电话不象游戏有个通 用的服务器。更多的情况下，我们不能预先知道通话双方的口地址。所以要 识别语音我们需要单独的模块，让路由器自己来识别语音信号，并且打上标 记。具体过程如下： 根据目前制定的协议和各标准组织的工作重点，与m 电话相关的协议主 1 0 婴型盔兰堡主兰竺垒塞 要可分为两大类：h 3 2 3 协议和s i p 协议。目前对i p 网络上承载实时业务( 话 音等) 的方式大体相同，均是利用了源自i e t f 的r t p 协议，但是在呼叫建 立和控制方面有不同的方案，其代表即为h 3 2 3 和s i p 。它们的框架如图2 - l 所示。 圈2 - 1i 3 2 3 与r t p 框架图 对于话音服务，其基本的通信过程可分为呼叫建立和通话两个部分。在呼 叫建立过程中需要完成用户身份认证，确定网关路由，协商话音编码方法等 工作：在通话过程中，应建立r t p 话音分组流及进行带宽管理，通话质量管 理等【6 1 。 一般地，p 电话系统提供三种基本业务：电话到电话( p h o n e t op h o n e ) ， 计算机到电话( p c t op h o n e ) 和计算机到计算机( p c t op c ) u p 电话的网络拓扑图如图2 - 2 所示( 以p h o n e t o p h o n e 为例) ： 四川大学硕士学位论文 关守 ( 混合i p 网络结构图) 图2 - 2 口电话的厢络拓扑图 l 棚j b 现在以电话到电话( p h o n c t o p h o n c ) 为例简单介绍整个通话流程2 。 该语音系统包括一个在现实中应用很广泛的增值服务：记费系统。 它的通信流程图如图2 3 所示。 ( p h o n et op h o n e 流程示惫罔) 图2 - 3 电话到电话( p h o n e t o p h o n e ) 各个步骤的解释如f ： 用户使用电话a 呼叫网关_ a 。用户根据i v r ( 交互式语音提示) 的提示 输入认证信息和被叫电话的号码； 网关a 向关守发送呼叫业务请求( 根据h 3 2 3i l l sa r q ) ，并把用户的信 息，业务类型和业务信息传递给关守； 关守检查用户的授权情况，确定该用户是否有权使用此种业务。授权认证 可以通过记帐系统的认证组件来进行，也可以由关守内部的功能完成； 结构返回允许，不允许接通的应答； 关守向记帐系统发送消息，请求用户的记帐信息，也包含呼叫的信息； 婴型查兰堡圭堂垡堡奎 记帐系统返回该用户的记帐信息； 关守向网关a 发送可供连接的目的网关的地址信息； 网关a 和网关b 连接，初始化通话进程，网关b 向电话b 发送呼叫应答 消息( h 3 2 3a r q ) 。通话进程开始； 当网关a 和网关b 检测到通话进程真正开始以后，网关a 向关守发送一 个呼叫开始信息( h 3 2 3r a si r r ) 并附带上唯一的记帐标志d ； 关守向记帐系统发送呼叫开始信息；记帐系统返回确认消息作为应答； 应答消息传送给网关a ； 网关a 或者网关b 检测到呼叫的结束； 网关a 和网关b 向关守发送呼叫结束消息，并发送关于该呼叫的相关信 息； 关守向记帐系统发送呼叫结束消息； 记帐系统返回确认信息； 确认信息送到网关a 和网关b 。 我们的识别方案是基于语音包的源地址和目的地址以及包的类型来识别 的。该方案的依据是：将我们带q o s 功能的路由器放在通往关守必经的链路 上。用户在进行语音通信或中断通信时，首先要发送一个基于若干固定端口 号的呼叫请求，请求中包含了双方的m 地址。这个信号可以被我们的路由器 捕获。根据用户的心态，由于语音属于大数据量的传送。为了保证语音质量， 用户一般不会在打电话时同时进行其他占大量带宽的流媒体传输操作，比如： 网上看电影，听歌等。而现阶段的语音包都是通过u d p 传输，除上述的情况 外，基于u d p 传输的数据就是一些即时通信的数据，比如：q q 等。 所以我们可以认为当用户开始打口电话时，对应同一源和目的地址且与 呼叫请求建立的链接匹配的u d p 数据包都是语音包。 具体的识别过程如下： 基于我们的检测方法，数据可以分为两类：呼叫的请求厢 放信号。而回 传的请求信号都会发送到关守，可以很容易地被识别。 用户开始进行语音呼叫时，会先到关守注册，以及告诉关守被叫方的号码， 然后，关守会返回确认信息，以及被叫方的腰地址。这个时候我们的路由器 可以捕获该来回关守和网关之间的连接建立请求信号，并且分析回传的数据 1 4 四j i i 大学硕士学位论文 包，如果呼叫被确认，我们可以在数据包中分析出主叫方和被叫方的口地址， 并将该记录添加到一个保存通话链路的表里，而这个表就是后面我们识别某 个数据包是否语音包的依据。 当通过开启了q o s 策略路由器的数据包不是上述的呼叫请求，释放信号时 做以下操作。因为语音包是以u d p 方式发送的，所以我们要判断一个数据包 是不是语音包，需先判断是不是u d p 包。当一个数据包经过开启了q o s 功 能路由器转发时，路由器将首先检查是否是u d p 包。如果不是，则按照路由 器的普通选路规则转发或丢弃；如果是，则按以下操作来进行识别。 如果该包是一个u d p 包：则可以对该数据包进行识别。在此就用到我们 刚才在呼叫请求过程时所建立的连接表。将包的特征值在链路表中检索，若 该数据包的源目的地址与链接表中的某个项匹配，则我们认为该数据包是语 音包，并为之加上标签，以便后面的转发识别；如果不是，则按照路由器的 普通选路规则转发或丢弃。 2 2 2 为数据包加上可识别标签 考虑到数据包本来就是为了减少延时，则在越低层加标签越好。在传统的 l p v 4 协议中，包的格式预留了一个4 比特的优先级域，可以指示1 6 种优 先级别。在此区域中，用户可以指定延时，吞吐量以及可靠性服务等优先级 属性( 参考：服务类型( t 0 s ) 字段共8 位，包括一个3 b i t 的优先权子字段 ( 现在已被忽略，通常不用) ，4 b i t 的t o s 子字段和lb i t 未用位但必须置0 。 4 b i t 的t os 分别代表：最小延时、最大吞吐量、最高可靠性和最小费用。4b i t 中只能置其中1b i t 。如果所有4b i t 均为0 ，那么就意味着是一般服务) 。虽然 现在许多路由器不支持t o s 字段的识别，但是这种基于t o s 优先级的方案正 在迅速的为广大路由器厂家采用。所以我们考虑在 l o s 字段加数据的优先级 标志。 在后面路由器作数据包转发的时候，将t o s 的值赋给s k _ b u f f e r 的p r i o r i t y 成员。那么后面路由器在作取包操作的时候，就可以按照不同的p r i o r i t y 作相 应的入队列和出队列操作。 2 3o o s 调度过程 四川大学硕士学位论文 数据包的排队转发 随着i n t e r n e t 规模不断增大，各种各样的网络服务争相涌现，先进的多媒 体系统层出不穷。由于实时业务对网络传输延时、延时抖动等特性较为敏感， 当网络上有突发性高的f t p 或者含有图像文件的h r r p 等业务时，实时业务 就会受到很大影响；另一方面，多媒体业务占去了大量的带宽，这样，现有 网络要保证的关键业务就难以得到可靠的传输。 解决这些问题的最简单的办法当然是增大带宽，但是，由于这种方法代 价高昂，所以并不十分可行。这就要求网络管理者对不同的服务区别管理， 而不能对所有的数据包一视同仁。于是，各种q o s 技术应运而生。 最简单地说，q o s 能够对数据包进行合理的排队，对含有内容标识的数 据包进行优化，并对其中特定的数据包赋予较高的优先级，从而加速传输的 进程，并实现实时交互。由于每种应用系统对网络的要求有所不同，这使得 带宽本身并不能解决网络拥塞的问题。q o s 所追求的传输质量在于：数据包 不仅要到达其欲传输的目的地址，而且要保证数据包的顺序性、完整性和实 时性。通过q o s ，网络可以按照业务量的类型或级别加以区分，并能够依次 对各级别进行处理。优秀的q o s 可以提供创建业务量级别的方法，把应用系 统或用户的邮件分配到某一级别中作系统管理。所以一个q o s 是成功还是失 败，主要取决于它对网络的分析、算法的设计以及模型的建立。 一个数据包所经历的端到端延时由其在各链路上的传输延时以及其在各 路由器处理延时所组成。由链路所引起的延时相对来说比较容易被估计出来。 但是，由于各路由器为解决拥塞问题而引入缓冲造成的延时就不是很容易被 估计出来了。这种延时随着拥塞模式的变化而波动，即使对于有相同目的地 址的数据包，其延时在不同时刻也是变化的。 关于数据丢失的问题。路由器中的缓冲( 或队列) 长度是有限的，长时间 的拥塞会导致缓冲达到最大容量。如果数据包到达路由器时，路由器的缓冲 已满，则该数据包就会被丢弃，直到路由器中的缓冲有空闲。 任何一个口网络的延时，抖动，分组丢失等特性最终都可归结为链路的 q o s 特性以及各路由器中所采用的排队策略和队列管理的动态特性。 如果网络流量超过了服务速率，在每一个内部拥塞点上配置单一的队列显 然是不够的。在这种情况下就需要为每一种可识别的数据流按其优先级配置 婴型盔堂堡主兰堡丝苎 个队列。而每个队列有自己独立的延时，抖动，丢包率要求。然后路由器 可以根据这些需求参数来进行发送调度，如图2 - 4 所示。 图2 - 4 路由器调度示意图 这些队列中的每一个都应该有自己的分组丢失策略。 q o s 的目标在于提供高品质的话音，高质量话音通信所依赖的三点要素 是：带宽，延时和抖动。电话呼叫需要一个相对固定的带宽。对于普通文件 传输而言，文件传输将随着可用带宽的增加而提高传输速度。但对于实时语 音文件传输而言，它所产生的网络负载是固定的，并不需要多余的带宽。相 反，普通文件传输能够根据网络带宽的可利用情况进行适应性的调整：而对 于实时语音文件的传输，当两端带宽低于需求带宽时，将出现影响话音质量 的包丢失现象。显然，一个高品质的v o 疋解决方案关键应当在三个方面进行 努力，即保证带宽、延时最小并是延时变化最小，因j 比，解决电话的q o s 问题也应该从着三个方面进行考虑。 该方法的基本思路是：将数据分为四个不同优先级的队列，优先级高的队 列享有高的服务质量( 比如有限转发，在网络繁忙的时候，优先保证最小的 丢包率等) 。而在同一队列中则按照先进先出的法则( f o ) 。在保证高优先 级数据的的服务质量被满足的前提下尽量转发低优先级数据。 研究表明，现在网络中的数据流量是个自相似的分布。所谓自相似分布 就是说，无论将时间间隔取得很小还是取的很大，流量波形都是相似的。然 而，由于现在还没有找到一个很好的模型来描述它，一般来说还是用泊松分 1 7 四川大学硕士学位论文 布来代替它，加以研究，并且能取得一个比较好的结果。所以我们可以作这 么一个假设，数据都是以泊松流到达排队系统，来到的被服务单元的是否要 被服务与队列是否已经到达上限有关、都有被服务的延时等。所以语音质量 的参数在排队论的排队模型中都可以得以体现。 根据以上叙述，以及排队论理论，我们可以得到下面结论。 数据包的发送延时由数据包的到达速率，当前队长，数据的被处理的速 率所决定。 数据的丢包率由当前的队长以及数据的到达速率，以及队列的最大长度 决定。 数据的延时抖动由数据的被发送时间，以及到达的速率所决定。 对这些影响到q o s 的质量的参数进行分析： 首先，众所周知，数据包的来到是突发性很强的，如果想知道数据的来 到速率是很困难的。但是作为泊松流，它也是有迹可寻的。比如说，话音包 的速率就是典型的突发性很强的数据流，但是大量的统计数据说明，电话信 号在一般情况下( 除去节假日外) 在每天的相对时段是可以统计出平均流量 的。而在这个时段中的电话流量就是个均值为x 泊松流；其次，电话数据 的流量应该是一个连续波形图，而不是一个离散的量。所以如果我们在某一 个时刻，取一个足够小的时问闯隔，统计在这个间隔中传送的数据包。算出 来的速率就是一个很接近当时传输速率的近似值，当然间隔越小越精确。 具体的取值方法类似于t c p i p 的连接机制：在某一时刻我们可以算出该 时刻的数据流量r ，假定前一时刻的数据流量为7 可。如果这两个流量比值 近似为1 ，或者说没有太大的差别，则认为流量较稳定，则隔两个取值时间间 隔再计算流量，以此类推。但如果出现了较大的差别，则说明当前流 量很不稳定，或者说有突变。则间隔减小一半再取值，以此类推，我 们就可以在尽可能少浪费时间和其它资源的情况下算出当前的流量速率。对 于各个队列的当前队列长度，可以在程序中直接知道，所以在此不讨论。 由于数据包都很小，发送时间也很小，所以很难确切地知道某一个包被 发送需要多少时间。所以我们的算法假定每个包( 不管普通包，游戏包还是 语音包) 发送所需时间都是一样的。该时间可做实验得到，在一个很长的时 间内，连续不停的发包，然后统计在这个时间段中一共发送了多少包即可得 1 8 婴型盔堂堡主兰垡堡苎一一 到平均的发包时间。 四川大学硕士学位论文 第三章排队模型的建立 q o s 是网络管理者提高服务质量的重要手段之一。在类似于二级网络运 营商行业圈中。如何尽量利用用户对不同数据的要求不同来减少运营成本一直 是业界研究的热点。 不同运营商之间的网络布局不同，购买的带宽不同的影响，更增加了实现 q o s 的难度。如何表达和捕捉网络状态的繁忙状态，确定一个q o s 方案，并 最终找到能解决网络突发高流量造成拥塞问题的q o s 调度算法是当前实际网 络进行q o s 时所面临的关键问题。 本章将讨论一个可以忽略运营商之间差别的，具有自适应功能并且以排队 论为理论基础的基于优先级的排队调度算法 仿真实验表明，这种算法与当前未加算法的路由器相比，能解决较大的突发 高峰流量和进行动态的优先级服务质量判断并且动态分配带宽 考虑在任意网络拓扑中，通过路由器中的数据分为v i p 用户数据，语音数 据，游戏游戏和普通数据。语音与游戏包的优先级都比较高，它们对延时的 要求很高，尤其是游戏，它对丢包率的要求也很高。其中v i p 用户的数据拥 有最高的级别，它的数据需要优先转发。而且它的优先级大于其他数据的优 先级。 相对于各个不同优先级的数据，分别有自己的一些判断服务质量的参数： 延时b ，丢包率凸等。 现在的要求是，在发生冲突的状态下，优先满足优先级高的数据服务质量。 在高优先级的数据的服务质量得到满足的情况，再考虑其余优先级数据的服 务质量和状态。而且对它的发送要求是，在用户看来，这些数据的带宽是可 变的，即数据流量大时，数据占用带宽较大，而在数据流量小的时候，所占 用的带宽小，是一个动态的自适应过程。 3 1 基于优先级服务质量的网络模型及求解目标： 定义1 ：为了方便后面的讨论，现在以字符来代替各种数据。q 1 为v 口数 四川大学硕士学位论文 据，q 2 为语音数据，q 3 游戏数据为，其它普通数据则为q 4 。 定义2 ：在前面章节的叙述中我们了解到，数据流进入路由器时流量分布 其实是一个自相似分布，但是因为现在没有找到一个很好的数学模型来描述 它，所以一般还是以泊松分布来代替它进行研究。 定义3 ：数据流q 以速率为 ；的泊松流到达路由器；路由器处理q 的速 率为p j ；路由器希望数据包q f 发送延时不超过互。q 队列长超过就会丢失。 定义4 ：q o s 机制本质即是以牺牲一部分人的利益来换取享受q o s 的用 户的服务质量。那么在这个前提下，我们可以有如下结论，所有的低优先级 数据的服务质量都在高优先级数据的服务质量得以保证的前提下，才实施考 虑。 足： 现要求设计一种排队机制，给出一个发送系数墨，使得下列条件得以满 数据包q 的平均延时霉，其中互为用户能忍受的该数据的最大延时。 数据包q 的丢包率只只，其中只为用户能忍受的该数据的最大丢包率。 v m 数据是被优先考虑的，由于要求它所占用的带宽是独立的动态调整， 所以它的发送不