计算机网络中的拥塞控制和流量控制.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,学习计划,计算机网络的拥塞控制与流量控制,服务质量,QoS,移动,IP,技术,移动自组网络技术,无线传感器网络,无线,Mesh,网络,网络安全,计算机网络的拥塞控制与流量控制,随着互联网规模和互联网应用的快速增长，网络拥塞和数据冲突问题已经引起了人们的密切关注。拥塞控制技术和流量控制技术成为网络控制中的核心技术。,在拥塞控制中，主要涉及传输层的,TCP,拥塞控制技术以及路由器的队列管理与调度技术。,在流量控制技术方面主要介绍,TCP,流量控制技术以及数据链路层的流量控制技术。,服务质量,QoS,QoS(Quality of Service),，服务质量。它是指网络提供更高优先服务的一种能力。一般而言，服务质量是指网络组件,(,如应用程序、终端计算机或路由器,),所能够提供当信息在网络传递时保障其相关特性的能力。对于不同的应用，所需的服务品质特性亦不相同，目前关于服务品质的实现方式有二种基本型态：资源保留,(Resource reservation),与优先等级化,(Prioritization),。,QoS,路由算法设计,移动,IP,技术,自,20,世纪后期以来，无线移动通讯技术和有线,Internet,技术都取得了飞速的发展，而且两个技术不断的融合，并最终演进为下一代移动,Internet,。下一代移动,Internet,能够很好地支持终端的移动性，并且对对媒体业务提供了完善的服务质量的保证。,IP,技术以其简洁高效等多方面优点，成为整合有线网络和无线网络的统一的框架协议。移动,IP,技术是对,IP,移动支持功能的扩充，促使了,TCP/IP,向无线移动领域的拓展，构成了未来全,IP,有线无线一体化融合的基础。,重点介绍移动,IPv4,协议和,IPv6,协议的基本技术,无线自组网络技术,无线自组网是一个多跳的临时性自治系统，无线,Ad Hoc,技术被提出的一个最大的目的就是实现网络终端在移动过程中随着网络拓扑结构的变化而不至于中断通讯。,无线,Ad Hoc,技术的主要特点,:,不需要固定基础设施支撑，不需要预先配置主机，能够在任何时间、任何地点快速组建起一个移动通讯网络；节点可以任意移动，网络拓扑结构动态变化；没有专用的固定基站或路由操作作为网络的管理中心，网络中的每个节点都兼有主机和路由器的功能；节点间以对等的方式进行通讯，具有较高的协作性；网络的路由协议采用分布式的控制方式，比中心结构的网络具有更强的鲁棒性和抗毁性。,重点介绍网络拓扑结构动态变化时如何更有效的路由、拓扑发现和管理。,无线传感器网络,微电子技术、计算技术和无线通讯等技术的进步，推动了低功耗多功能传感器的快速发展，使其在微小体积内能够集成信息采集、数据处理和无线通信等多种功能。,传感器节点,无线传感器网络,:,就是由部署在检测区域内大量的廉价微型传感器节点组成，通过无线通讯的方式形成的一个多跳的自组织网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。传感器、感知对象和观察者构成了传感器网络的三个要素。,重点研究网络拓扑控制、网络协议以及数据融合和数据管理技术,下一代无线因特网技术：无线,Mesh,网络,无线无线,Mesh,网络是一种新型的无线网络结构，一种高容量、高速率的分布式网络，他与传统的无线网络有很大的差别。在网络拓扑结构上。无线,Mesh,网络与移动,Ad hoc,网络相似，但是网络上大部分节点基本静止不移动，不用电池作为动力，拓扑变化小；在单挑接入上，无线,Mesh,网络可以看做是一中特殊的无线局域网。无线,Mesh,网络节点的主要业务来往于因特网网关的业务。,由于具有较高的可靠性、较大的伸缩性和较低的投资成本，无线,Mesh,网络作为倚重可以解决无线接入,“,最后一公里,”,瓶颈问题的新的方案，被写入到,IEEE 802.16,无线城域网标准之中。,网络安全,重点介绍主动防御策略。,计算机网络中的拥塞控制与流量控制,夏玮,nkxw,网络拥塞控制和流量控制的基础,TCP,拥塞控制与流量控制,路由器中的队列管理,数据链路层流量控制和媒体访问控制,网络拥塞控制和流量控制的基础,网络拥塞控制和流量控制的背景知识,拥塞控制和流量控制措施,拥塞控制和流量控制的有效性评价,端到端拥塞控制是目前,Internet,的一个研究热点,.,在最初的,TCP,协议中只有流控制,(flow control),而没有拥塞控制,接收端利用,TCP,报头将接收能力通知发送端,.,这样的控制机制只考虑了接收端的接收能力,而没有考虑网络的传输能力,导致了网络崩溃,(congestion collapse),的发生,.,1986,年,10,月,由于拥塞崩溃的发生,美国,LBL(,美国劳伦斯,伯克利实验室,),到,UC Berkeley,（加州大学伯克利分校）的数据吞吐量从,32Kbps,跌落到,40bps.,在那之后,拥塞控制领域开展了大量的研究工作,.,拥塞控制算法对保证,Internet,的稳定具有十分重要的作用,.,网络中的拥塞来源于网络资源和网络流量分布的不均衡性,.,拥塞不会随着网络处理能力的提高而消除,.,拥塞控制算法的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥塞控制算法的设计具有很高的难度,.,到目前为止,拥塞问题还没有得到很好的解决,.,网络拥塞（,Congestion,）的含义,网络拥塞：指的是在分组交换网络中传送分组的数目太多时，由于存储转发节点的资源有限而造成网络性能下降的情况。,在网络发生拥塞时，一般会出现数据丢失、时延加大、吞吐量下降，严重的时候甚至会导致,“,拥塞崩溃,”,（,Congestion collapse,）现象。,拥塞崩溃主要包括：,传统的崩溃,未传送数据包导致崩溃,由于数据包分段导致的崩溃,日益增长的控制信息流造成的崩溃。,一般拥塞发生在网络负载增加导致网络效率降低时。,拥塞的一种极端的情况是死锁（,Deadlock,）,致使网络无法工作，退出死锁往往需要网络复位操作。,当网络负载较小时，吞吐量随着负载的增加而增长，呈线性关系，响应时间增长缓慢；,当负载达到网络网络容量时，吞吐量呈现缓慢增长，响应时间急剧增加，这一点称为,knee(,膝点,),；,如果负载继续增加，路由器开始丢包，当负载超过一定量时，吞吐量急剧下降，这一点称为,cliff,（崖点）,可以看出负载在,Knee,附近时网络的使用效率最高,拥塞控制算法包含拥塞避免,(congestion avoidance),和拥塞控制,(congestion control),这两种不同的机制。,拥塞避免,的目的是使网络运行在,Knee,附近，避免拥塞的发生使网络运行在高吞吐量、低延迟的状态下,.,拥塞控制,是,“,恢复,”,机制,它用于把网络从拥塞状态中恢复出来，进入正常的运行状态,;,Internet,的网络模型,拥塞现象的发生和,Internet,的设计机制有密切的联系：,Internet,的最初设计是面向无连接的分组交换网络，所有业务的分组被不加区分地在网络上传输。网络能够出的唯一承诺就是尽自己最大的努力传输进入网络的每一个分组，但是他无法给出一个性能指标。,互联网的网络模型可以用一下几点来抽象,：,分组交换（,packet-switched,）网络,与电路交换（,circuit-switched,）网络相比，分组交换通过共享提高了资源的利用率。但是在共享方式下，如何保证用户的服务质量是一个棘手的问题。在分组交换的过程中可能会出现分组乱序的现象，对乱序分组的处理增加了系统的复杂性。,无连接网络（,connectionless,）,Internet,的节点之间在发送数据之前不需要建立连接,.,无连接模型简化了网络的设计,在网络的中间节点上不需要保存和连接有关的状态信息,.,但是使用无连接模型难以引入,“,接纳控制,”,(admission control),算法,在用户需求大于网络资源时难以保证服务质量,;,在无连接模型中对数据发送源的追踪能力很差,给网络的安全带来了隐患,;,无连接也是网络中乱序报文出现的一个主要原因,.,尽力而为（,best-effort,）的服务模型,.,best-effort,即网络不对数据传输的服务质量提供保证,.,这个选择和早期网络中的应用有关,.,传统的网络应用主要是,FTP,Telnet,SMTP,等,它们对网络性能,(,带宽、延迟、丢失率等,),的变化不敏感,best-effort,模型可以满足需要,.,但,best-effort,模型不能很好地满足新出现的多媒体应用的要求,这些应用对延迟、速率等性能的变化比较敏感,.,这要求网络在原有服务模型的基础上进行扩充,.,Internet,中拥塞发生的原因,拥塞发生的原因是,“,需求,”,大于,“,供给,”,.,网络中有限的资源由多个用户共享使用,.,由于没有,“,接纳控制,”,算法,网络无法根据资源的情况限制用户的数量,;,缺乏中央控制,网络也无法控制用户使用资源的数量,.,目前,Internet,上用户和应用的数量都在迅速增长,如果不使用某种机制协调资源的使用,必然会导致网络拥塞,.,虽然拥塞源于资源短缺,但增加资源并不能避免拥塞的发生,有时甚至会加重拥塞程度。例如,增加网关缓冲会增大报文通过网关的延迟,如果总延迟超过端系统重传时钟的值,就会导致报文重传,反而加重了拥塞,.,拥塞总是发生在网络中资源,“,相对,”,短缺的位置,.,拥塞发生位置的不均衡反映了,Internet,的不均衡性,.,首先是资源分布的不均衡,.,图,(a),中带宽的分布是不均衡的,当以,1Mb/s,的速率从,S,向,D,发送数据时,在网关,R,会发生拥塞,.,其次是流量分布的不均衡,.,图,b,中带宽的分布是均衡的,当,A,和,B,都以,1Mb/s,的速率向,C,发送数据时,在网关,R,也会发生拥塞,.,Internet,中资源和流量分布的不均衡都是广泛存在的,由此导致的拥塞不能使用增加资源的方法解决,.,因为网络拥塞本身是一个动态的问题，不能只靠静态的方式来解决，而需要适当的协议能够在网络出现拥塞时保护网络正常运行,产生拥塞的主要原因：,存储空间不足：当一个输出端口收到几个输入端口的报文时，接收的报文就会在这个端口的缓冲区中排队。如果输出端口没有足够的存储空间，当缓冲区占满时，报文就会被丢失，对于突发的数据流更是如此。适当地增加存储空间在某种程度上会缓解拥塞，当时过于增加存储空间，报文会因为在缓冲区内排队太长而超时，远端会认为他已经被丢弃而选择了重发，从而浪费了网络资源，进一步加重了网络拥塞。,产生拥塞的主要原因,带宽容量不足。高速数据流通过低速链路时也会产生拥塞。根据香农信息理论，任何信道带宽最大值及信道容量,所以节点接收数据的速率不许小于或者等于信道容量，才有可能避免拥塞。否则，接受的报文在节点的缓冲区排队，在缓冲区占满时，报文被丢弃，导致网络拥塞。因此，,网络中的低速链路将成为带宽的瓶颈和拥塞产生的重要原因之一,产生拥塞的主要原因,CPU,处理数据慢。,如果节点在执行缓冲区中排队、选择路由时，,CPU,处理的速度跟不上链路速度时，也会导致拥塞。,不合理的网络拓扑结构和路由选择，也会导致网络拥塞。,流量控制的含义,如果发送端发送的数据过多或者数据发送速率过快，导致接收端来不及处理，则会造成数据在接收端丢失。为了避免这种现象的发生，通常的处理办法就是采用流量控制，即控制发送端发送的数据量以及数据发送速率。使其不超过接收端的承受能力，这个能力主要指接收端的缓存和数据处理速度。,流量控制工作原理,局域网上的主机,H1,通过链路向主机,H2,发送数据，连接,H1,和,H2,的链路带宽为,1.5Mbit/s.,假定现在,H1,向,H2,传送的是实时音频数据。而主机,H2,的数据接收处的处理速率是,1Mbit/s,，此时，,H1,通过链路发送来的数据就会在,H2,端发生拥塞，到达,H2,的实时音频分组就会被丢弃或者延时处理。,为了避免上述现象的发生，可以采取措施限制,H1,的发送速率，使其不超过,1Mbit/s,，或者扩大,H2,的接收缓存，这样就不会超过,H2,的接收能力，从而实现流量控制。,拥塞控制和流量控制,拥塞控制需要确保通讯子网能够承载用户提交的信息量，是针对中间节点资源受限而设置的，是一个全局性的问题，涉及到主机、路由器等很多方面的因素；,流量控制是与点到点的通信量有关的，是针对端系统中的资源受限而设计的，主要是解决快速发送房和慢速接收方的问题，使局部问题，一般都是基于反馈进行控制的。,流量控制和拥塞控制都是限制进入网络的通信量的机制，两者是密切相关的。,网络拥塞控制和流量控制的基础,网络拥塞控制和流量控制的背景知识,拥塞控制和流量控制措施,拥塞控制和流量控制的有效性评价,拥塞控制的措施,单纯增加网络资源并不能从根本上有效的解决网络拥塞，解决这一问题的有效途径是采用拥塞控制。,拥塞控制的目的是在有限的网络资源的情况下，通过通信量的约束与调配减少数据的丢失，提高网络的吞吐量，充分利用已有的网络资源。,因此，拥塞控制通常从两方面入手,通信量的约束：是指控制进入网络的通信量，使其与网络容量相匹配；,通讯量的调配：则是合理处理和转发到达网络数据，实现网络流量的均衡。,从控制理论的角度,从控制理论的角度，拥塞控制又可以分为开环控制和闭环控制。,当流量的特征可以准确的规定、性能的要求可以事先获得的情况下，适合使用开环控制,当流量特征不能准确描述，或者当整个系统不能提供资源预留时，适合使用闭环控制。,Internet,中主要使用闭环控制的方式。,闭环的拥塞控制可以分为三个阶段：,检测网络拥塞的发生；,将拥塞信息报告到拥塞控点；,拥塞控制点根据拥塞信息采取相应的措施以消除拥塞。,闭环的拥塞控制可以动态的适应网络的变化，当使其性能收到反馈延迟的影响比较大，当拥塞发生点和控制点之间的延迟很大时，其性能会严重下降。,根据算法的实现位置,根据算法的实现位置，可以将拥塞控制算法分为两大类：,链路算法（,Link Algorithm,）,:,在网络设备中使用（如路由器、交换机）,链路算法主要集中在队列管理和队列调度方面，其中的主动队列管理技术是目前研究的热点问题,源算法,（,Source,Algorithm,）,:,主要在主机和网络边缘设备中使用,在拥塞控制的源算法方面，大量的工作集中在对,TCP,协议的研究上,近年来非线性规划理论和系统控制理论的思想被引入到拥塞控制的研究中来，一些研究人员尝试使用严格的数学模型来描述由端系统和网关组成的系统，这对于拥塞控制有很大的帮助。,流量控制措施,同样单纯增大接收端的承受能力也不能从根本上有效地解决接收端流量过剩的问题。解决这一问题的有效途径是采用流量控制。,流量控制的目的是在有限的接收端承受能力的情况下，通过流量约束，减少接收端的数据丢失，提高数据发送效率，充分利用接收端的资源。,目前,Internet,中流量控制主要分为：,端到端的流量控制：是基于接收端的最终承受能力控制数据源端的数据流量,链路级流量控制：则主要是基于接收端的承受能力来控制上游节点的数据流量。,流量控制涉及到的技术通常有：,停止,-,等待协议（,STOP-and-Wait,）,：主要用于理想的传输信道，即所传输的的任何数据既不会出现差错也不会丢失。,在进行流量控制时，要求发送方将数据发送到发送缓冲区并且立即发送出去，而接受方的接收缓冲区的大小只要能够装得下一个数据帧即可。发送方发送数据后等待，接收方收到数据后将其放入数据链路层的接收缓冲区并交付给主机，同时发一信息个发送节点表示数据帧已经上交给主机；发送方收到接受站点发过来的双方事先商定好的信息，则从主机取下一个新的数据帧再发送。,该协议可以使接收双方同步的很好，并且有接收方控制发送方的数据流量。,由接收方控制发送方的数据流量，这是计算机网络中流量控制的基本思路。,连续,ARQ,（,Automatic Repeat reQuest,自动重传请求）,连续的自动重传请求协议在发送完一个数据帧后，不是停下来等待确认,帧，而是可以连续在发送若干个数据帧。如果这时候收到接收端发来的确认帧，还可以接着发送数据帧，减少了等待的时间，则整个通信的吞吐量就提高了。,在协议执行的过程中节点每发送完一个帧都要设置一个,超时计时器，,如果在所设置的超时时间内收到来自接受方的确认帧，就立即将,超时计时器,清零；但是若在所设置的超时时间到了仍未收到确认帧，就要重传相应的数据帧，同时仍需重新设置超时计时器（可能仅仅因为这些数据帧前面的一个数据帧出了差错），当出现这种情况时，将使传送的效率降低。,由此可见，若传送信道的传输质量很差因而误码率较大时，连续连续的自动重传请求协议不一定优于停止等待协议。,滑动窗口协议,是指一种采用滑动窗口机制进行流量控制的方法，通过限制已经,发送当还未得到确认的数据帧的数量,，滑动窗口协议可以调整发送方的发送速度。滑动窗口协议在提供流量控制机制的同时，还可以同时实现帧的确认和差错控制。,目前许多使用位填充技术的数据链路层的协议如（,HDLC High-level Data Link Control.,高级数据链路控制）协议等都采用了滑动窗口协议，同时由于滑动窗口协议集帧确认、差错控制以及流量控制为一体的良好性能，使之不仅广泛应用于数据链路层，还被作为传输层实现相应功能的重要工具。,网络拥塞控制和流量控制的基础,网络拥塞控制和流量控制的背景知识,拥塞控制和流量控制措施,拥塞控制和流量控制的有效性评价,拥塞控制和流量控制的有效性评价,从用户的角度出发，可以比较系统的吞吐率、丢失率和网络延迟等指标。,从整个系统的角度，两个非常重要的评价指标：,资源分配的效率,资源分配的公平性,资源分配的效率,网络资源使用的效率是指源端要求的总资源与网络所能提供的资源之间的关系。如果两者刚好相等或者很接近，那么这种方法的效率就是高的，否则就是效率不高的表现。,资源分配的效率可以用,Power,函数来评价，函数定义为：,上式中一般取,=1,，如果在分析中偏重网络吞吐量则,1,，如果在分析中偏重于响应时间则,1.,当负载位于,knee,点时,power,函数取最大值，网络分分配的效率最高。,Power,函数一般应用在网络中单资源、单用户的情况下使用。,资源分配的公平性,公平性是指网络发生拥塞时各连接能够公平地共享网络资源。产生公平性的根本原因在于拥塞发生必然导致数据报的丢失，而数据包的丢失会导致个数据流之间为争抢有限的网络资源发生竞争，竞争力强的数据流将得到更多的网络资源，从而损害可其他流的利益。因此没有拥塞也就没有公平性的问题了。,由于公平性是针对资源分配而言的，因此在评价前首先要确定,“,资源,”,的含义。目前大多数研究文献在评价公平性是都针对网络的吞吐量，这是从用户的角度出发考虑的，并不完全适合网络中的资源状况。,网络中的资源包括链路带宽、网关的缓冲和网关的处理能力等，在考察网络公平性时，应将这些资源的分配情况综合考虑。,复习,传输控制协议,TCP,的基本知识,