NS2 学习笔记 8 队列管理机制.doc

NS2 学习笔记 8 队列管理机制 NS2学习笔记(8)--队列管理机制2010年06月20日星期日15：421、目标：学习DropTail和RED队列管理机制，以了解被动式和主动式队列管理机制的优缺点。 2、基础知识： 2.1两种传统的包的调度策略 在介绍Drop Tail之前，我们先介绍两种传统的包的调度策略-决定包的传送顺序。(1)FIFO(First In First Out，先进先出)是一种经典的包调度策略，它的最大优点在于实施起来简单。FIFO又叫先到先服务(FCFS)，即第一个到达路由器的数据包首先被传输。FIFO的问题在于在排队的时候没有考虑包的重要程度，对FIFO排队的一个简单改进是优先级排队。基本思想是给每个数据包分配一个优先级标志。这个优先级标志可以放在IP数据包内。路由器则执行多个FIFO排队。一个队列对应一个优先级。路由器在排队的时候总是给优先级高的队列先排队。在同一优先级队列中，数据包仍按FIFO排队。 (2)公平排队算法(Fair Queue，FQ)是FIFO的一种改进。FIFO排队的主要问题是无法区分不同的数据流。由于整个TCP的拥塞控制是在源端执行，而FIFO排队不提供约束所有数据源遵守拥塞控制的机制，这就有可能让行为不良的数据流强占大量带宽。在Internet环境中，某个应用不使用TCP协议是完全可能的。结果，它可以绕开端到端的拥塞控制机制，向路由器任意发送自己的数据包，从而引起其它应用的包被丢弃。FQ算法则解决了这个问题。在FQ算法中，路由器对每个输出线路有一个排队队列。路由器按轮询方式处理包。当一条线路闲时，路由器就来回扫描所有队列，依次将每队每一个包发出。当某个流的数据包到达过快时，其队列就会很快占满，属于这个流的新到的数据包就会被丢弃。采用这种方式，每个数据流就不可能牺牲其它数据流而多占资源。另外，FQ算法并没有告知源端路由器状态的机制，也就是说，FQ仍然要依赖于端到端的拥塞控制机制。它只是将数据流分隔，使不遵守拥塞控制机制的数据流不至于影响其它流。所以它在没有牺牲统计复用的情况下提供了公平性，与端到端的拥塞控制机制也可以较好地协同。 传统的队列长度管理机制是去尾(Drop Tail)。它有点类似于FIFO(先入先出)的存储方式。Drop Tail最大的优点是原理简单。当路由器队列长度达到最大值时，通过丢包来指示拥塞，先到达路由器的分组首先被传输。由于路由器缓存有限，如果包到达时缓存已满，那么路由器就丢弃该分组。一旦发生丢包，发送端立即被告知网络拥塞，从而调整发送速率。这种做法不考虑被丢弃包的重要程度。 Drop Tail仍是目前Internet使用最为广泛的分组排队、丢弃的方式。这种方式将拥塞控制的责任都推给网络边缘。所以TCP假定网络中的路由器对拥塞控制不起任何作用，而独自承担检测和响应拥塞的全部责任。 基于Drop Tail的一种改进算法是优先级排队。它的基本思路是将每个分组分配一个优先级标志。路由器则执行多个队列排队。一个队列对应一个优先级。路由器总是优先传输非空的最高优先级队列。在同一优先级队列中，分组仍按Drop Tail方式管理。 优先级排队的主要问题是最高优先级队列能抢占其它所有的队列。只要高优先级队列非空，低优先级队列就得不到服务。所以，不能允许用户不受控地指定高优先级。同时，Drop Tail无法识别面向连接的TCP流，所以对它们的公平性较差，对上层TCP快速恢复的效率也很低。 除了这些，它在具体实施过程中也存在着很多其它的弊端。如；若缓冲器很长，则每个分组所经历的延迟就会增大：而若缓冲器很短的话，又不能够适应突发性数据流；另外，全局同步的发生又将直接导致吞吐率的减小，等等。所有这些都可能引起网络崩溃。 2.2常见的队列调度算法 (1)先到先服务(First Come First Served)：FIFO队列实现的FCFS是Internet使用最多的一种方式，它的最大优点在于实施简单。FIFO本质上是一种去尾(Drop-tail)的算法，不需要选择丢弃的分组，只是在系统中没有空闲缓冲资源时丢弃到达的分组。虽然这种算法已经在Internet上成功工作了许多年，但它有三个严重的缺陷：①持续的满队列状态；②业务流对缓存的死锁；③业务流的全局同步。而队列管理最重要的目标之一就是降低稳定状态下队列的长度，因为端到端时延主要就是由于在队列中排队等待造成的。另外，DropTail容易造成TCP全局同步(TCP Global Synchronization)问题，由于Internet上的数据流都具有突发本质(Burstiness)，到达路由器的封包也往往是突发的。如果队列是满的或者几乎是满的，就会导致在短时间内连续大量的丢包。而TCP数据流具有自适应特性(Adaptive)，来