RED实验报告.docx

实验名称: RED 算法分析一、 RED 算法提出背景当网络上开始出现拥塞的时候, 路由器的缓存就充满了, 于是路由器就开始丢弃分组, 对于 TCP 通信量, 这就是进入慢启动阶段的一个信号, 这样就可以减轻网络的负载和缓解拥塞。但在这种情况下有两个困难,第一,丢失的分组必须重传, 这就又增加了网络的负载, 并对 TCP 的流增加了明显的时延。更严重的发生全局同步现象, 当出现通信量突发时, 队列就排满了, 然后就丢失很多的分组, 可能出现的结果就是有许多的 TCP 连接受到影响, 接着就进入了慢启动。这样会引起网络通信量的急剧下降, 所以在一段时间内, 网络处在不必要的低利用率的状况。因为许多 TCP 连接在大约同一时刻进入慢启动,它们也将在大约同一时刻脱离慢启动, 而这将引起另一个大的突发和另一次拥塞的循环。有一种解决方法就是在路由器中使用更大的缓存以减少丢弃分组的概率, 但一方面, 当这些大的缓存都充满时, 所有的连接上的时延将急剧增大, 另一方面,如果通信量基本上是自相似的, 那么就不能构造足够大的缓存, 大的突发一个接一个地达到, 如果拥塞继续下去, 而对缓存的需求一直在增长。一个更好的解决方法应当是能够预计拥塞的开始, 并告诉一个 TCP 连接应当在某个时刻慢下来, 然后就测量这一个连接慢下来的效果, 在此之后才使另一个连接慢下来, 用这种方式, 在拥塞开始时,放慢速率是逐渐进行的, 因而通信量负荷也是逐渐减轻的, 这样对 TCP 的连接影响也最小, 不会出现全局同步。二、 RED 算法设计目标 AQM 的主要技术目标是在减小排队时延的同时保证较高的吞吐量, 具体分析 AQM 解决的问题主要包括以下几个方面: (1) 早期探测路由器可能发生的拥塞, 并通过随机丢弃或标记分组来通知源端采取措施避免可能发生的拥塞。(2) 公平地处理包括突发性、持久性和间歇性的各种 TCP 业务流。(3) 避免多个 TCP 连接由于队列溢出而造成的同步进入“慢启动”状态。(4) 维持较小的队列长度, 在高吞吐量和低时延之间做出合理平衡。虽然 Brade 等人在 IETF 提出 AQM 的研究议题是在 1998 年, 但与其密切相关的 RED(RandomEarlyDeteetion) 算法的研究却是由来已久了, 早在 1993 年,Floyd 和 Jacobeon 就提出了 RED 算法, 当时的主要目的是克服“早期随机丢弃”(EarlyRandomDrop,ERD) 网关偏袒突发业务而造成的不公平问题。因为在提出 AQM 的研究时,既D 是唯一一个能实现它技术目标的算法, 所以将其推荐为 AQM 的唯一候选算法, 随后, 围绕着 AQM 和 RED 的研究逐渐丰富起来。与 AQM 相区别,RED 的设计目标如下: (l) 拥塞避免,RED 的设计是为了避免拥塞, 而不是对拥塞做出反应, 这样,既D 必须检测拥塞的开始, 以便使网络维持在一个低时延和高吞吐量的工作区域。(2) 避免全局同步, 当得知拥塞开始时, 路由器必须决定应当通知哪个连接或哪些连接要进行退避, 在当前的实现中, 通知时是隐式的, 同时还有丢弃的分组。由于及早检测出拥塞, 并且只通知必要的那些连接, 因此不会出现全局同步。(3) 避免对突发通信量的偏见, 拥塞开始往往是由于到达了来自一个或几