（计算机科学与技术专业论文）tcpip的公平性研究.pdf

摘要 t c p i p 网络提供的数据报传输是“b e s te f f o r t ”服务。然而随着i n t e m e t 商业化进程的 加快，用户对服务质量有了新的需求。基于“b e s te f f o r t ”服务原则在未米的许多年内将继 续得到整个i n t e r n e t 社团支持这样一个假设，本文认为在适当o v c r p r o v i s i o n i n g 网络带宽的 前提下，可以通过对带宽的公平分配来满足用户的需求；同时通过增加应用对网络环境的动 态适应能力，使它们能够达到用户满意的程度。因此，本文在两个方面对t c p i p 网络中的 公平性问题展开研究： 第一，网络如何对在其中流动的用户数据流提供保护和约束。使用户从网络接受的服 务，不依赖于网绺中其它j j 户的合作鞋度。第二，网络如何提供及时的，准确的关于网络使 用状况的信息给阁户，使他们有机会调整自身的网络使川行为公平地获取所需资源。 针对数据传输过程中带宽分配存在的问题，以及i t 前的研究现状，提出了两种公平的带 宽分配策略及算法，其主要内容如f ： 1 m b l u e 是一种面向数据流的活动队列管理算法，它的g t 标熊平均公平性。m b l u e 使； = 数据报丢弃的频率和队列空闲程度米管理网络拥塞；它只维护一个先进先山队列，以较 少的数据流状态信息，在不同流之间公平地分配网络带宽。 m b l u e 在n s 2 模拟试验中表现的性能证实了提高网络服务公平性两个重要原则的有效 性，为崩户公平的带宽分配研究奠定了基础。 2 基于t _ i j 户公平性概念，本文提山了用户公平的带宽分配策略，并且设计了相关的算 法u f q r 。 网络资源分配的用户公平性意味着，不仅是用户的接入，而且包括传输中的带宽资源分 配，都应该与用户所支付的费用相适应。 本文使用用户捌望的服务满意度米表征一个用户对网络资源的使用情况。j i _ j 户期望的服 务满意度通过预约与实际使用的比值来表示，方便了数据报的标记以及网络核心在资源分配 时的算法没计，使用户公平的带宽分配成为可能。 本文把用户期望的服务满意度作为主要的管理指标，设计了一种全新的活动队列管理算 法u f q r ，使拥塞时瓶颈连接处的带宽资源分配能够按照用户的预约体现出公平性，实现了 对不同用户数据流的保护和约束。该算法在网络边缘根据用户数据的流速和在i s p 处的预 约，计算并标记每个数据报，在网络内部的路由上对数据报进行管理。u f q r “边缘一核心” 的功能分布符台i n t e m e t 端到端的设计原则，以软小的代价保证了公平性，并且整体上提高 了网络的效率。 算法可以采用分阶段数据报标记和丢弃的方法，向用户及时准确地反馈网络的使用信 息。对于适应性的用户数据流，源端的 ；l 户因此能够较早地接收拥塞信息，做出相应的调整， 毒曩作毒、导烯弼纛 金文公宿 从而减少数据报的丢失；对于非适应性数据流，在标记阶段过而，使用数据报丢弃的方法， 直接限制其通过，达到控制的目的。由于结合了用户的使用信息，网络的反馈对于不同的用 户是有区别的：超过平均服务水平将得到负向的反馈，而低于平均服务水平的用户却是正向 的反馈。这样，结合用户端到端的努力，使网络带宽资源在所有用户之间公平地配置。 本文对用户公平的带宽分配策略作了深入的理论分析，从网络资源定价的角度说明了该 方法的合理性和均衡性。 本文通过n s 2 模拟试验分析，证实了u f q r 算法公平分配网络带宽的性能。在相同预 约或不同预约两种情况下，对于用户的适应性或非适应性数据流，证实其带宽分配的公平性 都保持在0 9 以上，高于d i f f s e r v 能够达到的水平。 关键字：t c p i p 服务质量公平性 i i a b s t r a c t t c p ，i pn e t w o r k i n gp r o v i d e so n l yo n es e r v i c e ：b e s te f f o r td a t a g r a md e l i v e r y h o w e v e r , w i t h t h ed e v e l o p m e n to f , s u c ha s ，c o m m e r c i a l i z a t i o na n dt h ed i v e r s i t yo f a p p l i c a t i o nr e q u i r e m e n t s ， m o r ec o n c r e t ed e f i n i t i o no fq u a l i t yo fs e r v i c ei s n e c e s s a r y t r a d i t i o n a l b a n d w i d t ha l l o c a t i o n m e t h o da n dc o n g e s t i o nc o n t r o lp r i n c i p l ew i l ln o ts a t i s f yt h e c h a n g i n gd e m a n d s o nt h ea s s u m p t i o nt h a ti n t e r n e ts o c i e t yw i l lc o n t i n u et os u p p o r tt h eb e s te f f o r ts e r v i c em o d e l i nt h ef u t u r e ，t h ed i s s e r t a t i o nb e l i e v e st h a tm o s to fa p p l i c a t i o n s ，w i t h a p p r o p r i a t e b a n d w i d t h o v e r p r o v i s i o n i n ga n ds o m ec o n t r o lo v e rd a t af l o w , i na d d i t i o nw i t ht h e i ra b i l i t i e so fa d a p t a t i o nt o d y n a m i cn e t w o r kc o n d i t i o n s ，w i l lp e r f o r ms u f f i c i e n t l yw e l l u n d e rm o d e r a t ec o n g e s t i o nl e v e l s t h e r e f o r ew ec o n d u c ts o m er e s e a r c hb a s e do nt w op r i n c i p l e s ： f i r s t ，n e t w o r km u s tp r o t e c tf l o w sb ye n f o r c i n gr e s t r i c t i o n so nr e s o u r c eu s a g e ，s e c o n d ，t h e n e t w o r km u s tp r o v i d ef e e d b a c k st ou s e r si nt i m e t h ed i s s e r t a t i o n p r o p o s e st w of a i r b a n d w i d t ha l l o c a t i o na l g o r i t h m s ：m b l u e ( m o d i f i e d b l u e ) a n du f q r ( u s e r f a i rq u e u i n gw i t hr e s e r v a t i o n ) 1 m b l u ea i m sa ta v e r a g ef a i r n e s s i tu s e sp a c k e tl o s sa n dl i n ku t i l i z a t i o nh i s t o r ya sa l l e s t i m a t o ro fc o n g e s t i o nt od e t e c ti n c i p i e n tc o n g e s t i o n ，a n dt on o t i f yr e l a t i v ec o n n e c t i o n s m b l u e w o r k sw i t ha nf i f oq u e u ew i t h o u ta s s u m p t i o n sa b o u tq u e u i n ga r c h i t e c t u r e t h r o u g hl i t t l es t a t e i n f o r m a t i o no fe a c hf l o wm b l u ea c h i e v e sf a i rb a n d w i d t ha l l o c a t i o na m o n gf l o w ss h a r i n gt h e b o t t l e n e c k s i m u l a t i o nr e s u l t sd e m o n s t r a t et h ef a i r n e s so fm b l u e i ta l s ov a l i d a t e st h ee f f e c t i v e n e s so f t w o p r i n c i p l em e n t i o n e da b o v e 2 b a s e do nt h ec o n c e p to f u s e rf a i m e s s ，t h ed i s s e r t a t i o np r o p o s e su f q r ，w h i c hc a na l l o c a t e b a n d w i d t ha m o n gu s e r sa c c o r d i n gt ot h e i rp a y m e n t s d u r i n gc o n g e s t i o n f o re a c hp a c k e ta tt h ee d g eo fan e t w o r k ，u f q ri n s e r t sal a b e lw i t hu s e r su t i l i t y , w h i c hi s t h er a t i oo fi t sr e a lt r a f f i ci n t on e t w o r ka n di t sr e s e r v a t i o n i tu s e sa v e r a g eq u e u el e n g t ha st h e i n d i c a t o ro f t h es e v e r i t yo f c o n g e s t i o n ，a n du s e su t i l i t ya sm a i ni n d e xo f p a n k e t s d r o p p i n g au s e r , w h o s et r a f f i ci sh i g h e rt h a nt h ea v e r a g es e r v i c el e v e l ，w i l lr e c e i v en e g a t i v ef e e d b a c k s f r o mu f q r d u r i n gc o n g e s t i o n ，a n db en o t i f i e dt or e d u c eh i sp a c k e bs e n d i n g ；w h e r e a sau s e r w h o s et r a f f i ci sl o w e rt h a na v e r a g e ，w i l lr e c e i v ep o s i t i v ef e e d b a c k sa n db en o t i f i e dt oi n c r e a s eh i s p a c k e t ss e n d i n g i fau s e ri g n o r e sn e g a t i v ef e e d b a c k sf r o mn e t w o r k ，p a c k e t so u to fh i sf a i rs h a r e w i l lb ed r o p p e db yu f q r s ow i t he n d - t o - e n de f f o r t s ，t h eb a n d w i d t hi sa l l o c a t e df a i r l yd u r i n g c o n g e s t i o n i 王i t h ed i s s e r t a t i o na n a l y z e st h es c h e m eo fu s e rf a i rb a n d w i d t ha l l o c a t i o nw i t hg a m ea n dp r i c i n g t h e o r y , a n ds h o w s i t sr a t i o n a l i t ya n d e q u i l i b r i u m s i m u l a t i o nr e s u l t sa r ep r e s e n t e dt ov a l i d a t et h ep e r f o r m a n c eo ft h ea l g o r i t h mu n d e rd i f f e r e n t s c e n a r i o s k e y w o r d s ：t c p i p q u a l i t yo fs e r v i c e f a i r n e s s 浙江大学博士学位论文2 0 0 4 年 第1 章 绪论 1 。1 引言：关于服务质量 i n t e r n e t 提供的数据报传输是“b e s t e f f o r t ”服务。在这个环境中，所有的_ j 户数据报都 接受相同的转发服务：网络承诺它将尽最大努力地分发用户交付的每一个数据报，但是不提 供任何服务质量上( q o s ，q u a l i t yo f s e r v i c e ) 的保证。所有的用户在发送数据报之前都不需 要征求网络的许可，换句话说，网络对用户没有接纳控制措施。 但是随着i n t e r n e t 商业化进程的加快，应用的多样化，用户希望得到更好的服务或者是 有服务质量定义的服务。 由于一些历史原因，不同的研究组织，如i t u 。t ( i t l it e l e c o m m u n i c a t i o ns t a n d a r d i z a t i o n s e c t o r ) 5 】、i s o ( i n t e m a t i o n a l o r g a n i z a t i o n f o rs t a n d a r d i z a t i o n ) 6 、i e t f ( t h e i n t e m e t e n g i n e e r i n g t a s k f o r c e ) 7 等，对于服务质量给出了不同的定义这些定义的内涵不尽相同。 i t u t 从电信网络运营的角度来理解服务质量，认为服务质量就是用户、服务提供商、 网络提供商之间合同约定的服务功能和性能指标。i s o 从它定义的层次结构出发，认为在网 络的各个层次之间，对应的层次之间都存在服务的概念，因而也都有服务质量的问题。由于 分组网络的特点，i e t f 没有关丁服务质量的统一定义，其概念主要是指i p 层的一些性能和 参数，例如用户的带宽、传输时延、抖动、数据报丢失率等等。这些概念从不同的角度诠释 了服务质量。而对于用户来说，他们所关心的仅仅是能不能满足他们的需求或者说，他们 与服务提供商签订的合同能不能得到严格的执行，简而言之服务的质量如何。 在一个没有接纳控制，采用“b e s te f f o r t ”服务的分组网络中，用户关心的服务质量涉 及带宽、时延、抖动等多方面的性能，但首先是网络带宽。网络带宽指标对于用户来说有两 个方面的内容：网络服务提供商有没有提供足够的网络容量满足所有用户一般的需求；在网 络容量不能满足所有用户的需求时，服务提供商能不能及时扩展网络的容量，以及在短期内 带宽资源是如何分配的。对于i p 网络中的带宽资源分配问题，此时就有了两种不同的观点： o v e r p r o v i s i o n i n g 这种观点的持有者认为，既然现在没有任何集中式控制的i n t e m e t 能够提供令用户满意 的服务，那么有什么理由不相信在未来的几年内不能做到这一点呢? 随着硬件技术的进步， 特别是光传输技术和交换技术的发展，带给市场的将是越来越便宜的传输带宽。不可否认， 第l 章绪论 i n t e m e t 的成功也部分地支持了这种观点。从长远的角度看，要满足用户的需求，确实需要 更多的带宽。 但是，带宽的增加能够解决一切问题吗? 显然不完全是，自从上个世纪i n t e r a c t 投入使 用，一直到现在，有一个问题在持续困扰着i n t e r a c t ，那就是网络拥塞。网络拥塞指的是整 个网络或者局部连接的持续过载状态，也就是对网络资源的需求持续地超过网络的容量。网 络拥塞南接影响网络的使用效率。 r e s e r v a t i o n 另外的一种观点就是带宽资源预留，在上个世纪9 0 年代，i e t f 在这方面作了两个重要 的努力。 1 9 9 3 年t i e t f 提出了一种新的服务模型i n t s e r v ( t h e i n t e g r a t e ds e r v i c e s m o d e l ) 2 。i n t s e r v 服务框架基于数据流的资源预留，使用r s v p ( r e s o u r c er e s e r v a t i o np r o t o c 0 1 ) 完成它所定义 的呼叫接纳控制和预留功能。它要求网络中所有的用户端应用、路由器都支持该协议造成 可扩展性和可管理性较著。所以，i n t s e r v 并没有得到大规模的使用。 1 9 9 7 年，i e t f 又提出了另外的一个i n t e r n e t 服务框架d i f f s e r v ( t h e d i f f e r e n t i a t e ds e r v i c e s a r c h i t e c t u r e ，区分服务) 【3 。区分服务框架的基本思想是在网络的边缘将数据报分类，在网 络的核心对不同服务级别的数据报进行分别转发，从而实现较租粒度数据流级别统计意义上 的服务保证。但是区分服务并没有能够有效地控制拥塞，也没有实现资源在相同服务级别数 据流之间的公平分配。 o v e r p r o v i s i o n i n g 和r e s e r v a t i o n 是两种截然不同的观点，虽然i n t e r a c t 目前的状况偏向 于o v e r p r o v i s i o n i n g ，但未来的发展趋势还需要时间的检验。 不管如何，有一点是肯定的，那就是i n t e r a c t 的“b e s te f f o r t ”服务对于数据通信已经取 得了极大的成功，几乎每个i n t e r a c t 用户每天都在接受网络提供的这种服务( 当你收邮件或 是上w w w 网站的时候) ，没有明显的证据表明这种服务会在可见的将来被废弃或被其它的 服务所取代。 本文的研究正是基于这样的假设。 本文认为，商业化i n t e r a c t 中用户对服务质量的要求，以及网络中新出现的应用如多媒 体数据、实时信息传输等对带宽和延迟的需求，可以通过提供合适的带宽加上适当的控制 来满足。通过增加应用对网络环境的动态适应能力，诸如传输速率的实时调节使各种应用 能够达到用户满意的程度。通过网络和用户两方面的努力，在“b e s te f f o r t ”服务的框架中， 使网络资源得到最有效的利用，用户的需求得到最大的满足。 本文同时认为网络拥塞的一个重要原因是部分用户或数据流对资源的不恰当使用，也即 部分数据流发送的数据大大地超出了它应有的份额，导致网络资源不能够满足用户的需求。 网络必须对数据流施加某种控制，限制用户对网络的不恰当使用，从而保护大多数用户的利 益。网络同时也有义务向用户及时地反馈拥塞信息，使用户能够调整数据发送速率，以避免 2 浙_ i 工夫学博士学位论文2 0 0 4 年 进一步的拥塞。 基下以上认识，本文对t c p i p 网络( i n t e m e t ) 中带宽资源分配的公平性问题作了初步的 研究，并且有了以f 的结果。 1 2 主要工作 用户通过不同的方式接入i n t e r n e t ，向各自的i s p 支付不同的费用，费用的多少往往取 决于1 s p 所提供的接入带宽。在接入的时候，支付较高费用的用户在单位时间内确实能够发 送较高速率的数据流。然而在数据报进入网络以后，在向目的节点的前向转发过程中，用户 数据流得到的却是“b e s te f f o r t ”服务。如果说在正常情况下不存在公平性问题，那么在网 络拥塞时，这个问题就变得突出了，由此本文提出了两种拥塞连接两络带宽的公平分配策略 及其相关的算法实现。 m b l u e 7 3 是一种面向数据流的活动队列管理算法，它的目标是平均公平性。m b l u e 使用数据报丢弃的频率利队列空闲程度来管理网络拥塞探测瓶颈连接早期的拥塞信息，通 过数据报的丢弃和标记避免拥塞。它只维护一个先进先出队列，以较少的数据流状态信息， 在不同流之间公平地分配网络带宽。m b l u e 证实了提高网络服务公平性两个重要原则的有 效性，对公平性问题作了初步的研究。 基于用户公平性概念，本文提出了用户公平的带宽分配策略，并且设计了相关的算法 u f q r 5 3 】。 网络资源分配的用户公平性指的不仅仅是用户的接入带宽应与其所支付的费用相适应， 更进一步的，在用户数据报在网络传输的过程中，带宽资源分配也应该与用户所支付的费用 相适应。两个支付不同费用的用户在拥塞时能够获得的传输带宽应该与其所支付的费用成比 例。 本文找到了一个合适的指标用户期望的服务满意度。用以表征一个用户对网络资源 的使用情况。定义用户期望的服务满意度为用户实际发送的数据流速率与用户接入速率的比 值，或者与用户预约速率的比值，从而形象地反映一个甩户对其所预约的网络带宽资源的使 用状况。用户数据流的期望服务满意度将是拥塞时瓶颈连接进行活动队列管理的重要指标。 同时，设计了一种全新的分布式活动队列管理算法u f q r ，使拥塞时瓶颈连接带宽资源 的分配能够体现出用户公平性，实现对不同用户数据漉的保护和约束。该算法使用路由输出 活动队列长度的指数平均，显式地指示拥塞；使用平均服务水平作为活动队列管理的主要参 照，对输入的用户数据报进行排队管理。 算法采用分阶段数据报标记和丢弃的方法，对于适应性用户数据流。源端的用户在拥塞 时能够较早地接收网络拥塞信息，做出相应的速率调整，从而减少数据报的丢失，避免进一 步的拥塞：对于非适应性数据流，在标记阶段过后。将使用数据报丢弃的方法，直接限制其 数据报的通过，达到控制的目的。 由于使用合适的数据报管理指标和分布式的活动队列管理算法，所以能够在网络的全局 范周内实现带宽资源的用户公平分配。 第l 章绪论 晟后，使用了博弈论的分析方法，对t _ 户公平的带宽分配策略作了进一步的研究。从网 络带宽资源定价的角度。说明了带宽资源分配方法的台理性和均衡性。 1 3 研究方法 除了理论分析，本文主要的研究方法是网络模拟器n s 2 1 4 的模拟试验，通过试验中取 得的相关数据来证实理论分析中的结论。 n s 一2 是一个用于网络研究的离散事件模拟器，是计算机网络理论研究中使用得比较多 的网络模拟软件。它提供了无线或有线网络上的t c p i p 、路由、多播等协议的模拟支持。 试验的硬件平台是浙江大学一浙大网新网格计算研究开发中心的至腾2 0 0 0 集群。该集 群现有3 2 个节点，内部使用易尚y e s - 3 7 1 4 m 千兆交换机集群管理软件为o s c a r 。其中 每个集群节点配备两个至腾2 ，4 gc p u ，1 gr a m ，使用r e d h a t7 3 操作系统。 1 4 论文内容安排 论文接下来的内容安排如下： 在第二章中，首先回顾了数据报交换和电路交换的基本概念，接着介绍了t c p i p 网络 的层次结构，路由器的工作原理，以及数据流在网络中流动的基本过程和控制流在网络中的 基本作用。在这一章中，也介绍了公平性的一般概念。最后总结了“b e s t e f f o r t ”服务的特 点，结合网络目前的实际应用情况，提出了改善网络服务质量，增加网络服务公平性的两个 原则：对用户数据流的保护和约束，以及关于网络使用状况的及时反馈。 在第三章中，介绍了m b l u e ：一个面向数据流的公平队列管理算法。m b l u e 的试验 结果验证了第二章中提出的两个原则的有效性。为进一步的研究奠定了基础。 在第四章中。讨论了用户公平的活动队列管理。介纲了用户公平的活动队列管理模型和 相关的算法策略。使用模拟的方法，在各种环境下验证了该算法的用户公平性和控制的收敛 性，并且简单地讨论了该策略的应用。 在第五章中，先是回顾了i n t e m e t 端到端的设计原则，t c p 的流量控制：接着分析了 a i m d 与t c p 公平性的关系；然后提出了采用分阶段标记和丢弃数据报的u f q r 算法，通 过分析和模拟试验证实了它的性能；针对t c p 在高速网络中启动较慢的问题，介绍了 h s t c p ，同时对u f o r 在高速网络环境下对h s t c p 的影响进行了评估。 在第六章中。首先介绍了n a s h 均衡的概念，然后分析了片段时间内带宽分配均衡的存 在性，提出了适应性数据流的出价战略，最后回顾了相关研究。 最后一章是总结和展望，对全文作了总结，对将来的工作提出了进一步研究的建议。 4 浙江大学博十学位论文2 0 0 4 年 第2 章 t c p i i p 的“b e s te f f o r t ”服务以及公平性 在本章中，首先介绍数据通信网络的基本概念，然后分析t c p i p 网络“b e s te f f o r t ”服 务原则存在的一些问题，最后提出了解决问题的研究方向。 2 1 分组交换与电路交换 通信网络大致可以分为两种类型：电路交换和分组( 数据报) 交换。 已经有1 0 0 多年历史的电话网络就是一种典型的电路交换网络。电路交换的特点是实时 性强，时延小。但同时也带来线路利用率低，不同类型终端用户之间不能通信等缺点。 分组交换网络的主要代表有a t m ( a s y n c h r o n o u st r a n s p o r tm o d e l ) 1 0 】和i p ( i n t e m e t p r o t o c 0 1 ) 网络。它们实质上是在“存储一转发”基础上发展起来的。在这些网络中，信息是由 数据报分组携带的。每个分组都根据其报头所包含的信息被网络存储或交换转发，在一条物 理线路上采用动态复用的技术，同时传送多个数据分组直到到达目的地。在目的地再去 掉分组头，将各数据段按顺序重新装配成完整的报文构造出原始的信息。 分组交换与电路交换相比，具有两个重要的优点 具有对信道统计复用的能力。 分组交换网络以虚电路的形式进行信道的多路复用，极大地提高了线路的利用率，降低 传输费用。特别是在一个具有猝发数据流情况的网络环境中，允许用户共享网络资源可 以明显提高网络的利用率。有研究显示，网络中音频的峰值与平均流量比大概是3 ：1 ， 而数据的峰值流量与平均流量比却高达1 5 ：1 1 1 。i p 网络在数据传输业务中获得的成功， 可以充分说明分组交换网络对于高度猝发的数据传输的适用性。 信息传输可靠性高。 在网络发生故障时，网络中的路由机制会使分组自动地选择一条新的路径避开故障点 不会造成通信中断。这其实也是早期i p 网络设计的一个重要目标。 分组交换网络的主要缺点是统计复用会导致拥塞，以及用户之间不公平的网络带宽资源 分配。在数据报分组的到达速率大于连接的传输容量时就会发生网络拥塞同时引起不公平的 带宽分配。 由于分组交换网络的灵活性和资源利用的有效性，目前的数据通信一般都使用数据报分 组交换技术。日常接触的i n t e r n e t 就是使用i p 数据报交换技术还有前面提到过的a t m ，以 第2 章t c p i p 的“b e s t e f f o r t ”服务以及公平性 及现在骨干网上使用得较多的m p l s ( m u l t i p r o t o c o ll a b e ls w i t c h i n g ) 1 2 。a t m 使用同定长度 的数据报( 信元) 作为传输的基本单位，能够提供最基本的传输服务，也能够提供保证带宽 和延迟的服务。i p 使用的是变长的数据报，支持最基本的“b e s te f f o r t ”服务没有提供 延迟和可靠性的保证。尽管a t m 在技术上较i p 具有很人的优势，但由于各种其它原因，i p 技术却在发展中取得了市场的统治地位。因此，在这篇论文中，将着重讨论使用数据报交换 的i p 网络。 2 2t c p i i p 网络模型 2 2 1 协议软件的概念层次 计算机协议软件通常采用分层的方法，将复杂的通信过程分为若干较小的子任务，使 问题变得更容易处理，然后每个子任务可以分别优化。这种分层的软件模块具有垂直型的栈 结构，如图2 - 1 1 】所示，每一层负责处理问题的一个部分。 图2 - 1 分层协议软件的概念性结构 从概念上讲，从一台机器上的应用程序向另一台机器上的应用程序发送一个报文，该报 文将在发送方的协议软件中逐层下行，通过网络转发，再在接收方的协议软件中逐渐上行e 2 2 2 系统互连( o p e ns y s t e mi n t e r e o n n e e t i o n ，o s l ) 模型 在1 9 8 1 i z ，国际标准化组织( i s o ) 创建了一个委员会小组来开发数据通信标准以促进多 供应商网络的互操作性，其结果就是开放系统互连( o s i ) 模型【6 】。o s i 模型并来确定任何通 信标准或协议；相反，它只是提供了通信任务应该遵循的一些指导性建议。o s i n n 了协议 分层的思想，其模型由7 层组成，如表2 - 1 。 表2 - 10 s i 模型层次 l 7 6543 21 l应用层表示层 会话层传输层网络层 链路层物理层 o s i 给每一层都分配了一组特定的功能。每一层都使用f 层的服务并为其上层提供服 务。例如，网络层使用数据链路, n 的j f t 务井为传输层提供与网络相关的服务a 应用层是o s i 模型的一部分，它并未具体指定用户和通信路径之间的接口是如何工作的，应用程序是这个 接口的具体实现。实际的应用程序通常执行应用层、会话层和表示层的服务，而将传输层、 网络层、数据链接层和物理层服务留给网络操作系统来处理。 6 浙江大学博士学位论文2 0 0 4 年 每一层都与其它计算机中的同一层通信。例如，一个系统中的第3 层与另一个计算机系 统的第3 层通信。当信息从一层传到f 一层时，会在数据前面加一个头，以指出该信息的来 源和目的地。来自某一层的由数据和头所组成的信息块又成为下一层的数据。例如当第4 层将数据传递到第3 层时，它会添加自己的头。当第3 层将该信息传递到第2 层时，第3 层会将 来自第4 层的头和数据作为它的数据，并在该数据前添加第3 层的头，然后才将这个“头+ 数 据”组合传给下一层。 习惯上，每一层信息单元的名称都不同： 应t | = j 层一 消息 传输层一 段 网络层一 数据报 数据链路层一 帧 物理层一 位 2 2 3t c p i p 协议栈 t c p i p 协议栈表示了与o s i 模型类似的网络体系结构，如图2 - 2 所示。 7应用层应用处理协议 6表示层 5会话层 4传输层t c p ，u d p 3网络层 i p 2数据链路层数据锛路层 1物理屡物理屡 图2 2t c p i p 协议栈与0 s i 模型的层次对应关系 但t c p i p 不像o s i 模型那样详细区分协议栈的上面几层。o s i 最上面的3 层大致与t c p i p 的应用处理协议相当。处理协议的一些示例有t e l n e t 、f t p 、s m t p 、n f s 、s n m p 和d n s 。 o s l 模型的传输层负责可靠的数据发送。在t c w i p 协议栈中，这对应于端节点之间的协 议，如t c p 和u d p 。t c p 用来转换来自上层协议的不定长消息以及提供远程系统间必要的确 认和面向连接的数据流控制机制。也就是提供可靠的数据报传输。 u d p 与t c p 相似，但它不面向连接，而且不对数据接收进行确认。u d p 仅接收消息并将 其传递给上层协议。因为u d p 没有类似t c p 的数据流控制机制处理l i d p 数据报的开销比处 理t c p 数据报少，特别是时间开销，所以它为某些特定的应用，如视频传输、数据库访问等 操作提供更有效的服务。 两际协议( i p ) 负责系统间无连接方式的通信。它相当于o s i 模型中网络层部分，负责网 络间的数据报传送。它通过一个i p 地址来完成这种传送，该地址确定了发送消息的系统和路 7 第2 章t c p i p 的“b e s te f f o r t ”服务以及公平性 径。i p 提供与网络层相同的功能并帮助传送系统间的报文段，但是不保证这些报文段能够成 功传送。i p 还可以将这些报文分成多个数据报，然厉在目的地重组这些数据报。另外，每一 数据报都可以沿着不同的网络路径在系统问传送。如果这些数据报到达时乱了次序，i p 会在 目的地将这些数据报按正确的序列重组。t c p i p 协议族的组成如图2 3 所示。 2 。3 数据的流动 分层协议设计的一个重要目标是要达到这样的一个效果：接收主机的第n 层收到的数据 就是源主机第n 层发送的数据。这样，就可以使协议的设计者在一段时间内把注意力集中到 某一层而不必担心较低层执行情况。而源主机上的应用程序与接收主机上的应用程序最终是 通过路由器进行数据报传输的。 分层原则在高层适用于端到端的传输，在低层则适用于简单的机器之间的传输。所以在 i n t e r n e t 中，可以把它想象成一个巨大的、虚拟的网络，并使用l p 数据报来代替帧。分层原 则保证了发送方发送的数据能够顺利到达接收方，并且数据前后是相互一致的。路由器在这 个传输过程中起到了关键的作用。 2 3 1 路由器 正是由于有了路由器，才使网络中无连接的两点互相交互数据报成为了可能，并且使这 种交互成功的可能性达到足够大。两点间的通信成为现实。每个路由器都有两个或两个以上 的接口与不同的网络连接，负责在这些网络之间转发数据报。它从一个网络接口接收数据报， 根据数据报报头中包含的目的地址转发到相关的网络接口。主机把所有目的站点不在主机所 在网络的数据报都发送给路由器，由它按照报文最终的目的站点位置将其转发。数据报传输 过程中经过若干个路由器，最后到达与目的站点处于同一网络的路由器。然后由该路由器交 付给目的主机。为了完成转发，每个路由都维护着一张路由表，路由表将不同的i p 地址映 射到不同的网络。路由表通过特定的路由协议软件维护，这些路由协议软件使用分布式的算 法，通常是基于对最短路径的固定假设，来维护路由表的主机可到达信息。在理想的情况下， 数据报总是沿着最短的路径到达其目的节点。 路由器包含一个或多个输入接口，数据报从这些接口输入；一个或多个输出接口。数据 报从这些接口输出。输入接口与输出接口通过一块使用共享总线、共享内存。或者其它交换 总线技术的高速底板互连。在一个或多个c p u 的帮助下完成路由表的维护与查找。如图2 - 4 所示。底板的主要参数是加速比，它定义了底板从输入接口到输出接口的最大传输速率与输 8 浙江大学博士学位论文2 0 0 4 年 入接7 1 连接或输出接口连接最大传输容量的比值。 当一个数据报通过一个路由器时，数据报可能存储于输入接口、输出接口，或者在两个 接口的存储区经过短暂的停留。根据路由存储数据报的不同特点，路由器可以分为输入排队， 输出排队，输入输出排队路由。 在一个输出排队路由，当数据报抵达输入接1 3 时，立即被转发到相应的输出接口。由于 数据报仅仅在输山接口排队和凋度，这种结构易于分析和理解。所以很多研究分析都使f j 输 出排队路由模型的假设。 然而，输出排队结构对加速比的要求却很高。最坏的情况是所有的输入接口都同时向一 个输出接口转发数据报。因为输入是无缓存的，输出接口必须能够同时接收所有输入接口转 发过来的数据报。这时底板加速比的值就是输入接1 3 的数目。由于当前路由器的输入接1 3 数 目往往较大，使得制造高速的输山排队路由有很多困难。事实上这也是市场上多种路由都使 用了某种类型的输入- 输出排队的原因。通过在输入接口缓存数据报，可以极大地降低底板 的加速比要求，当然这是以增加复杂性为代价的。因为输出接口才最终完成数据报的调度， 所以必须实施控制输入接口- 输出接口数据报流动的复杂的分布式算法。 综上所述输出排队的路由模型易于分析而输入输出排队的路由模型不易分析却具 有较好的可扩展性也因此易于实现。但是随着技术的进步。目前输出排队路由使用的犬部分 算法都可以在输入输出排队路由上实现，而且加速比要求不高。基于这种情况，本文后续 的讨论将集中于输出排队模型，以简化分析和讨论。 2 3 2 数据流的路径 图2 - 4 一个典型的路由器结构 数据流的路径由数据报从源端到目的端流动过程中所经过的路由节点组成。在数据流的 路径中，路由的主要操作是缓冲区活动队列管理，路由查找，数据报分类和调度。缓冲区 管理是指拥塞时路由缓存资源的管理。也就是说，当缓冲区溢出或缓冲区数据报数量超过某 个上限时，路由器就必须实施某种策略的管理。路由查找是根据数据报报头的目的地址查找 前向转发的输山端口地址。数据报分类和调度主要是拥塞时路由输出带宽资源的管理。在路 由器某个输出接口不能响应所有的传输要求时。如果它支持某种服务质量的保证策略，就必 须实行数据报的分类和调度以实现其服务质量的保证。虽然缓冲区管理和数据报调度已经有 了一些研究结果，但是通常还是使用一种基于f i f o ( f i r s t i n f i r s t - o u t ) 的调度策略和“t a i l 9 第2 章t c p i p 的“b e s te f f o r t ”服务以及公平性 d r o p ”的缓冲区管理算法。 目前许多在“b e s te f f o r t ”服务的i p 网络上保证数据流带宽和延迟的技术方案，都要求 路由具有数据报分类的功能。数据报分类可以理解为数据报从输入接 2 1 映射到某个特定数据 流的过程。数据流表示一系列连续的从一个节点流经网络到达另一个节点的数据报。路由表 查找和数据报分类两个操作都可以用来决定数据报前向转发的输出接口。由丁- 耍针对数据流 进行服务的区分，所以除了路由表查找，数据报分类也是路由晟复杂的功能之一。 数据报的前向转发：路由表查找和数据报分类 数据报的前向转发就是将每一个从输入接口进入的数据报根据其数据报头中目的地址 字段转发到相应输出端口。基于数据报头中的目的地址决定输出端口的过程被称为路由查 找。如果需要对数据报进行更加复杂的处理，例如对某些网络用户的数据报提供更好的服务 或者要对某些用户类型的数据报进行特殊处理，路由器还必须使用另外的能够区分用户的分 类。如使用数据报中的源地址来区分不同用户的数据报：使用数据报中的目的端口来区分不 同类型的应用数据流。这个确定数据报所属数据流类的过程就是数据报分类过程。其中路由 查找也可以理解为一种特殊类型的数据报分类，一种使用目的地址进行的数据报分类。 路由表查找：每个路由都维护着一个路由表，路由表是一张映射i p 地址到输出接口的 数据表，路由查找通过路由表完成。路由表的中每一个记录最少都包含两个字段：第一个字 段包含一个地址前缀，第二个字段包含一个输出接口的标识。地址前缀定义了所有共享这个 前缀的i p 地址范围。当一个数据报到达时，路由搜索它的路由表并将数据报的目的地址与 表中记录作最长的匹配，然后将数据报前向转发到所匹配的记录第二个字段定义的输山接 口。路由查找就是确定数据报输出接口的过程。 为了减小路由表的尺寸i p 地址是根据地址前缀分块进行分配的。i p 协议为网络上的每 个设备分配一i p 地址，它由4 个字节组成。不同的值定义不同的地址，这个地址的一部分 表示网络( 有时也可以表示子网) ，而另一部分则表示网络上特定的节点主机。将i p 地址按 一定范围分配，称为将l p 地址分类这取决丁具体的应用和组织的规模。三种晟常见的类 型地址是a 类地址，b 类地址和c 类地址。这三种分类表示了可为本地网络分配的i p 地址 的数目。 1 0 表2 - 2i p 地址类别 类地址 a0 x x x 到 1 2 6 x x x b1 2 8 0 x x 到 1 9 1 。2 5 5 x x c19 2 0 0 x到2 2 3 2 5 5