《主动队列对web性能影响的研究论文.doc》由会员分享，可在线阅读，更多相关《主动队列对web性能影响的研究论文.doc（28页珍藏版）》请在金锄头文库上搜索。
1、主动队列对WEB性能影响的研究摘要我们首先呈现一个关于主动队列管理技术（AQM）和显式堵塞通知在网络中经历大量用户浏览网页后响应时间的分布情况的经验研究。三种著名的方案可以考虑：比例积分(PI)控制器,随机指数标记(REM)控制器和自适应随机早期检测(ARED)。研究了在有显式堵塞通知和无显式堵塞通知下这些AQM方案的影响。我们的主要衡量性能指标是端到端的HTTP请求-响应交换响应时间。对于这种方法,我们的主要结果是：如果不支持显式堵塞通知,ARED操作在字节模式是表现最好的AQM方案,提供比尾部丢包FIFO排队在提供的负载超过链路容量的90%时有更好的响应时间性能。然而,ARED操作在包模式
2、(有或没有显式堵塞通知)是表现最差的方案。甚至比尾部丢包FIFO排队还要差。显式堵塞通知支持有利于PI和REM。在显式堵塞通知下,PI和REM是所有方案中表现最佳的方案,显式堵塞通知为在字节模式下的ARED操作提供重要的响应时间改进。对于REM, 显式堵塞通知带来的好处是戏剧性的。没有显式堵塞通知,REM比尾部丢包的FIFO排队在所有负载下的响应时间性能都还要差。AQM对于响应时间是否有重大的改善很大程度上依赖于流经历的往返时延的分布情况，当流的RTT增加时引起AQM和显式堵塞通知对于响应时间性能的影响降低。我们得出结论,AQM可以提高网页类应用程序和网络性能的工作负载。特别是,在AQM和显式
3、堵塞通知下,提供的链接可以在接近饱和水平没有明显退化上操作达到用户预期的性能。关键字：网络拥塞控制；AQM算法；标记/丢失概率；PI控制器第一章 引言计算机科学的迅速发展是20 世纪科学发展史上最伟大的事件之一，标志着人类社会进入了信息时代。随着现代高科技技术的发展，计算机技术和通信技术的结合形成了计算机通信系统。计算机网络就是把分布在不同地点的具有独立功能的多台计算机系统通过通信线路和设备互相连接在一起，按照网络协议进行信息通信，实现资源共享的计算机通信系统。20 世纪80 年代出现的Internet 是现在全球最大的计算机网络。Internet 在过去的几十年经历了爆炸式发展。1980年A
4、RPA 网（Internet 的前身）只包含200 台计算机，从1986 年接入6000 台计算机开始，5 年后数量就达到了60 万，一直到上一世纪末，全球Internet 用户达到2 亿之多。现在Internet 网络的容量与规模仍以惊人的速度继续不断的向前发展，人类日常的生活与工作也越来越觉得离不开Internet。Internet 的出现使得传统的信息获取、传送、存储和处理方式发生了根本的变化，人们的生活与工作方式也随之发生了很大的变化。Internet 网络的强大功能使得计算机网络在社会各个领域已有广泛的应用，对全世界科学、经济和社会产生了重大影响。Internet 网络使终端与计算机
5、之间、计算机与计算机之间能快速地相互传输数据、程序和信息，并可对这些数据信息进行分散、分级、集中管理和处理，从而使用户解除了地理位置的束缚，提高了数据处理的速度。如自动订票系统、银行财经系统、政府的计划统计系统、气象数据收集系统等。Internet 网络可以让用户充分利用计算机系统共享网络上的软件资源和硬件资源。如大容量磁盘存储器、异常昂贵的外部设备、数据库、应用软件等，使得网络中分散的资源互通有无，分工协作，资源使用率大为提高，处理能力大为增强，处理的平均费用大为下降。Internet 网络上设备分散，数据安全可靠。当网络上某处计算机发生故障时，可由别处的计算机代为处理，也可把数据备份到其他
6、计算机上，有网络作为公用后备，投资少，效益高。当某处计算机负担过重时，可将新的作业传送到网络中另一个较空闲的计算机上去处理，从而减少了用户等待时间，均衡了网络负载。多媒体网络的应用，使声、文、图像多种信息的收集、传送、存储和处理融为一体，给计算机网络用户提供了很大的方便。如用户可以在网络上收听广播、收看电视、查询信息等。随着网络应用范围不断扩大，用户数量的爆炸式增长，Internet 遇到了网络拥塞的问题。所谓拥塞（Congestion）是指在某一时刻，当网络中某一资源的到达量超过了该资源在相关网络节点的承载量时，称该节点在该时刻发生了拥塞。拥塞导致的直接后果是分组丢失率提高，端到端延时加大，
7、网络性能降低，严重时会产生拥塞崩溃，几乎没有数据包可以送达目的地。拥塞崩溃的出现可以追溯到Internet 的早期发展中。1984 年Nagle 报告了由于TCP 连接中不必要的重传所诱发的拥塞崩溃，19861987 年间这种现象在美国曾经多次发生，严重时一度使美国LBL 到UC Berkeley 之间的数据吞吐量从32Kb/s 跌落到了40b/s。拥塞崩溃在20 世纪80年代中期最先提出的时候，主要是由于TCP 连接重传那些正在传送或己经被接收方接收了的数据包所引起。我们将这种由于不必要的重传数据包而引起的拥塞崩溃称为典型拥塞崩溃。典型拥塞崩溃的问题己经通过定时器和TCP 的改进应用而基本得
8、到解决。当今的Internet 中的拥塞控制机制代表着一种最大利用的人工反馈系统，随着Internet 在规模、应用种类、应用领域的不断扩大，拥塞控制在多网络融合方面起着日益重要的作用。人们一致认为这种成为社会基本资源的网络如何得到有效控制已经变得日益紧迫了。鉴于网络的规模和复杂性，传统的拥塞控制开始是基于直接推断、实验证明的方法，直到本世纪初，国外研究人员开始尝试使用分析模拟和反馈控制理论。最近几年，人们把分析模型用于Internet 的拥塞控制6。拥塞控制策略包括拥塞避免（Congestion avoidance）和拥塞控制（Congestion control）两种不同的机制。拥塞避免是
9、“预防机制”，它的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延迟的状态。拥塞控制是“恢复机制”，作为拥塞避免失败的补救措施。拥塞控制的研究目的不是完全避免拥塞，而是研究怎样的拥塞程度更为合适。这是因为：TCP/IP 网络采用分组交换技术来提高网络链路的利用率，经常造成数据包在路由器的缓存中排队待发；如果队列缓存经常为空，虽然传输延迟小，但此时网络利用率低；反之，队列缓存总被占用，传输延迟加大了，但网络利用率较高。拥塞控制的目标是实现网络综合指标的最优化。根据拥塞控制算法实现的位置可以分为两大类：在传输层实现的源端拥塞控制，已被广泛应用的是TCP 拥塞控制；在网络层实现的通信子网拥塞控
10、制，也称为IP 拥塞控制。当网络中传输的数据分组接近网络的处理能力时，网络中间节点（如交换机、路由器等）设备缓存（buffer）中等待服务的数据分组队列（queue）会逐渐增大，在网络中的分组由于往返时间的增大有可能导致发送端定时器超时，而发生数据重传现象。如果队列长度超出中间节点的缓存中队列的容量，分组就会由于队列溢出而被丢弃。网络中发生分组丢失或者重传现象，就标志着发生了网络拥塞。如果不采用及时的、适宜的方法去控制网络拥塞，保证网络稳定运行，将导致网络瘫痪。因此在网络中为了避免出现网络拥塞，最大限度提高网络的利用率，最大可能地保证网络的稳定运行，保证网络信息的可靠传输，采用有效的拥塞控制机
11、制是非常重要的。拥塞会造成网络吞吐量的急剧下降和响应时间的增加。图1.1 中是网络有拥塞控制算法和无拥塞控制算法时有效吞吐量对于网络负载的变化曲线。由图可知，如果不采用拥塞控制机制，当网络负载较大时会导致有效吞吐量的急剧下降，而有效的拥塞控制机制能使网络在这种情况下仍然维持较高的有效吞吐量。在Internet 中，拥塞控制算法根据其实现的位置可以分为源算法（source algorithm）和链路算法（link algorithm），也可以分别称之为端节点算法和中间节点算法，两者协作完成网络的拥塞控制。其中链路算法的研究主要集中在主动队列管理（Active Queue Management，A
12、QM）。AQM 的思想是：网络中间节点在队列溢出之前通过丢弃或标记部分分组，以通知端系统网络的拥塞状况，端系统及时对可能发生或者已经发生的拥塞进行响应，避免即将发生的拥塞或者缓解已经发生的拥塞。AQM 算法使网络中间节点主动的参与到拥塞控制之中，期望在保证较高吞吐量的基础上，中间节点上的AQM 机制有效地控制队列长度，从而实现控制端到端的时延和时延抖动，保证网络的服务质量（Quality of Service，QoS）。AQM 是近年来拥塞控制领域的一个研究热点，AQM 机制可以减少数据分组的突发性丢弃，减小端到端延迟，并可以避免少数连接流占用大多数队列资源现象的发生。AQM 是当前拥塞控制研
13、究的一个热点。但是已提出的AQM 算法大多数是基于经验，启发式的算法，没有用系统理论的观点进行分析和设计。近几年系统控制理论被引入到拥塞控制的研究中，已经有一些基于控制理论的AQM 算法被提出，但大多此类算法都是基于传统控制理论（包括经典控制理论和现代控制理论）设计的。由于网络的复杂性和时变特性，这些算法的实用性和有效性还存在一些问题，需要更进一步的研究。 第二章 经典AQM算法在使用AQM算法的网络中间节点中，路由器根据自身拥塞状况对分组进行转发、丢弃/标记。图2.1是在路由器使用AQM控制机制的框图。AQM机制根据缓冲区队列长度或者其它测度检测拥塞，计算丢弃/标记数据分组的概率。中间节点通
14、过对分组的丢弃或标记，及时通知端系统网络的拥塞状况，发送端可以及时的调整自己的数据发送速率，尽量避免拥塞的产生。图2.1 在路由器中使用主动队列管理当前AQM 算法的研究根据其研究方法和思想主要可以分为以下几种：（1）基于经验的启发式算法，如RED；（2）基于优化理论的算法，如REM；（3）基于控制理论进行已有的算法稳定性分析、参数整定或者设计新的AQM 算法，如PI； 2.1 RED算法随机早期检测（Random Early Detection，RED）由Floyd 等提出的RED是目前已提出的最主要的AQM 的算法。它在队列溢出之前以一定概率丢失或标记分组，及时通知端系统网络的拥塞情况，以
15、便发送端对发送速率做出调整，减小网络发生拥塞的可能性。RED 算法由两部分组成，每当有新的分组到达队列时：（1）由瞬时队列长度计算出平均队列长度；（2）根据平均队列长度计算丢弃概率，并以此概率丢弃刚到达队列的分组。平均队列长度avg和丢弃概率p的计算方法，分别见式（2.1）和（2.2）： （2.1） （2.2）其中： 为计算avg的权值，q为瞬时队列长度。式中: 为最小阈值， 为最大阈值，为最大概率。图2.2所示为RED中丢弃概率与平均队列长度之间的函数关系。RED 使用平均队列长度而不是瞬时队列长度进行网络拥塞程度的度量，其计算平均队列长度的过程本质上是一个截止频率为,（其中 为采样间隔，在
16、RED 中即为分组到达的间隔时间）的低通滤波器，目的是为了平滑由于数据突发产生的瞬间的队列变化。从控制理论的角度分析，计算丢弃概率p 的部分是一个比例控制器。RED算法与Drop-Tail相比，可以有效的控制平均队列长度，从而控制了端到端的延时，同时减少了分组的突发性丢弃，避免了TCP全局同步问题。此外由于RED算法的随机丢弃机制，占用带宽越高的流的分组越容易被丢弃，所以算法可以在无需维护每个流状态的前提下提供一定程度的公平性，避免死锁问题。实验结果证明RED的性能优于Drop-Tail。尽管RED已被广泛应用于网络队列管理中来提高网络系统的性能，但是RED算法仍然存在以下问题：1）算法性能对网络参数和状态敏感；2）不能总是保证所有的流公平地分享带宽；3）算法鲁棒性不佳，导致路由器队列长度大幅震荡甚至溢出；4）使用RED算
