资源描述：
《一种改进的DRR调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第卷第期电子与信息学报〕之年月以提高其可实现性并改善它的输出突发特性局限性及其改进葬法实现上的局限性算法将有数据包等待发送的队列序号放入一个链表中。每次访问链表头上的队列时,先将队列的令牌数加上一个预先分配的值每次轮询允许发送的字节数,然后服务该队列。每次服务前判断队头上的数据包长度是否大于队列令牌数如果队列头上的数据包长度小于该队列剩余的令牌数,服务后队列令牌数减去发送的数据包长度,否则将其从链表中取出并插入链表尾部,然后访问链表中的下一个队列。当队列空时将其移出链表。从算法描述可知,实现需要在发送数据包之前知道数据包长度以决定是否可以发送,但是这个
2、要求会增加实现的开销。同时,持续对满足条件的链表头上的队列服务,直到队列用尽它的令牌。目前采用的交换结构一般可以分为两种一种是共享存储器结构另一种是结构在共享存储器交换中,所有的输入和输出口都要访问存储器模块。在一个时隙中,最多有个数据块从输入口写入存储器并且最多有个数据块被读出存储器。在一个的共享一一,一一改收到回国家自然科学基金资助项目©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net期伍翔等一种改进的调度算法存储
3、器型交换机中,存储器会有次写入和次读出如果每个端口速率为,那么共享存储器的速率为。尾公图两种调度算法一一图减小输出突发性的调度算法,乞,艺,,葱的令表示第个队列叭表示每次循环分配给队列的令牌数表示队列令牌数,表示最大数据包长度,表示队列个数。初始化乞乞艺乞、入队模块数据包到达乞所属的队列‘由空变为非空将乞加入调度链表尾部、、蚕©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net706电子与信息学报25卷P加入Q。出队模块
4、：While(TRUE)do{While(ActiveNow非空)d0{将ActiveNow链头出队，假设为Qi；发送Q队头数据包；DCi=DCi—Qi队头数据包长度；If(DCi>LMa)and(Qi非空)d0将i重新加入ActiveNow尾部；Elseif(Qi为空)thenDCi=Max；Else将序号i插入ActiveNext尾部；DCi=DCi+；Endif；)ActiveN0w<：>ActiveNext(交换服务链))改进后算法判断是否允许发送一个数据包不需要知道数据包的长度．调度之后发送数据包的同时可以得到数据包的长度，然后从令牌数中扣除
5、。我们假设iMax，那么在离开ActiveNow的队列再次进入ActiveNow时令牌值一定会大于LM，即至少可以发送一个数据包，调度器每次都能访问到可以发送的队列。从而使算法的时间复杂度为0(1)。3性能分析3．1算法公平性我们使用的公平性参数基于Golestani分析SCFQ时采用的服务公平指数(SFI：ServiceFairnessIndex)[引。假设r为链路带宽，(7-，t)为在(7-，t]队列i发送的业务量。如果P表示分配给队列i的带宽，我们称(7-，t)／pi为在(7-，t]内队列i得到’服务．如果任何两个队列i，J在时间(tl，t2]内
6、持续有数据包等待发送，并且We(t,，t2)／Pi—wj(t,，t~)／pjISS为一个常数。那么S为服务的公平性。令F表示算法的最大帧长F=∑1i，其中V为队列个数。那么分配给一个队列的带宽为POir／F(2)考虑时间段(t0，t]，其中t0为第1个轮询周期的开始，t为to后第n个轮询周期的结束时刻．如果k=1，2，⋯，n队列i持续非空，那么(t一1，tk)=Dc一+—DC其中DC为连接i在第k个周期结束时的令牌数．wi(to，t)=后+DC一DC,期伍翔等一种改进的调度算法,,、二当,初始化时队列在链表中时最大为由空闲进入该链表的队列,为叭‘最小为
7、,否则它必须离开链表。当队列在链表中时,令牌数为队列离开时的令牌数加上垂‘,由于离开链表的队列剩余令牌数大于而且小于,所以在链表中的队列的令牌数满,,、。中‘、蚕,当队列空‘、中,三三中‘足闲时所以套再。,三‘,,由式可以得到哄无中算法为提高效率时间复杂性一般为即,,户户三中必,一功,。,其中九鸟价‘二如果‘只有一个数据包需要在本轮询周期发送则图退化为图的形式。否则,它们不可能同时分别取得最大值和最小值所以孔垂‘由以上分析可知,算法改进后公平性能够得到改善。尹‘门‘杏必厂一下一刁呜‘“⋯卜一一—改进的图算法公平性©1994-2008ChinaAcade
8、micJournalElectronicPublishingHouse.Allrightsre
