信息网络与协议15-ch07.pptVIP

先到先服务先到先服务（FCFS：First-Come-FirstServed）发送机会到来时，最先到达的分组具有最高的调度优先级缺点：无法实现流区分，所有流的分组都同样对待优先级调度优先级队列（PQ：PriorityQueueing）到达输出队列的流被分成若干个具有不同优先级的队列当发送机会到来时，选择最高优先级并且非空的队列中的分组来发送，对于属于同一个优先级队列的分组，采用FCFS调度机制缺点：低优先级队列调度会出现“饥饿”现象，因为只有高优先级队列中无分组发送时，低优先级的分组才有发送机会高优先级队列：分组1，3，4

低优先级队列：分组2，5优先级调度当有比当前正在发送分组优先级更高的分组到达时，如何处理？继续发送低优先级分组，直到发送完成后再处理高优先级分组低优先级分组被停止服务，重新放回队列中或者被丢弃，开始发送高优先级分组非抢占式调度抢占式调度RoundRobinRoundRobin调度到达输出队列的流被分成不同的队列当有发送机会到来时，采用轮询的方式选择队列，并且从队列中选择分组发送缺点：流的分组大小不同，每个流发送的数据量不同，难以保证公平性队列1：分组1，2，4

队列2：分组3，5公平调度公平（Fairness）不是指用户分配相同份额的资源，而是指每个用户对资源具有相同的访问权利问题：如果系统没有足够的资源满足所有用户的需求，并且某些用户可能比其他用户需要更少的资源。在保证公平的情况下如何分配资源？Max-Min公平共享：首先要满足那些需求小于它们可以得到部分的用户，然后将多余的资源在那些需求更大的用户之间平均分配可以证明，在RoundRobin调度算法中，如果每个队列中的分组大小都相等，则满足Max-Min公平共享Max-Min公平共享原理资源按照递增的顺序分配没有用户获得大于其所需的资源无法满足需求的用户获得相同的资源分配过程假设系统总资源R用户集合1，2，…，n对应的资源需求r1，r2，…，rn，r1r2…rn步骤 首先将R/n的资源分配给用户1，也就是具有最小资源需求的那个用户，R/n可能大于r1，也就是比用户1需求的要多，此时将r1分配给用户1，并且继续这个过程，在剩余用户中分配剩下来的资源，直到出现第一个分配到的资源不比其需要的多为止，该用户的需求没有得到满足Max-Min公平共享分配例子---步骤1Max-Min公平共享分配例子---步骤2Max-Min公平共享分配例子---步骤3Max-Min公平共享分配例子---步骤4加权Max-Min公平共享赋予某些用户比其它用户具有获取更大份额资源的权利对每一个用户i都赋予相应的权重wi，以反应其获取资源的相对权利加权Max-Min公平共享分配定义对用户需求通过权重归一化，然后按递增顺序来分配资源。没有用户获得大于其所需的资源无法满足需求的用户获得与其权重成比例的资源份额加权Max-Min公平共享例子链路容量C=1Mbps=1,000,000bps权重为：w1=0.5,w2=2,w3=1.75,w4=0.75权重归一化后得到2/20,8/20,7/20,3/20。第1轮分配结束后，3多出的145,200在1，2，4中进行分配，1得到145200*2/(2+8+3)=22338bps,2得到145200*8/(2+8+3)=89354bps,4得到145200*3/(2+8+3)=33508bps，需要注意的是，在分配时只用考虑剩下用户的权值权重为：w1=0.5,w2=2,w3=1.75,w4=0.75链路容量C=1Mbps=1,000,000bps权重为：w1=0.5,w2=2,w3=1.75,w4=0.75加权Max-Min公平共享例子公平调度算法GPS理想情况下实现Max-Min公平共享的调度算法FQ在实际环境下模拟GPS算法GPS和FQ的目标是实现或者接近MAX-MIN公平共享，在实现时采用类似于RoundRobin的调度规则GPS调度GPS：GeneralizedProcessorSharing为属于不同流的分组分别维护不同的队列以bit-by-bitroundrobin的方式工作路由器从队列1选择1个比特发送，然后从队列2选择1个比特发送，如此循环Aij:第i个流的第j个分组的到达时间流1的分组长度为2比特流2和流3的分组长度为3比特对于每个队列，有以下两个假设：1）队列内的调度是先到先服务2）队列内采用非抢占调度对于一个k比特的分组，需要k轮调度才能完成，但是实际所需的时间随着活跃流的数量而变化GPS总结GPS算法实