基于EDF的高速交换局域网调度研究.pdf

《基于EDF的高速交换局域网调度研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类号卫：三塑一学校代码!逝垒2密级——学号2鲤墨!鲤2嫂垒!．基于EDF的高速交换局域网调度研究TheScheduIingResearchofHighSpeedLocaINetworksBasedonEDF湖南师范大学学位评定委员会办公室二零一一年五月摘要㈣Y帆1m9黜1吣m1帆6叭3m0帆随着网络的迅速发展，网络的服务质-量_(qualityofservice，QoS)保证成为当前研究的热点问题。而分组调度算法是实现QoS的重要内容。。本文首先分析了现有的典型分组调度算法：基于优先级的调度算法、基于比例共享

2、的调度算法和基于时间的调度算法。详细研究和分析了一种动态优先级调度算法：EDF(EarliestDeadlineFirst，最早截止期优先)调度算法，由于网络环境下直接采用EDF方案会存在诸如任务超截止期等问题，本文研究探讨了一种改进的分组调度算法：EDFBO(EarliestDeadlineFirstBasedonOvertime)算法，即基于超时处理的EDF算法。此改进算法通过仔细分析算法的每个调度步骤，采取充分利用空闲时间片和设置临时优先级的方法，较好地解决了本文所研究的实时高速局域网任务超截止期的问题。

3、为了在系统运行前计算出调度方案，实现真正的高速调度，本文设计了一个离线设计器。依据时间片机制和实时任务调度的特点，在系统中提供了周期性任务模型、连接模型和交换机EDFBO调度算法，以满足系统的计算需求。此设计器适用于一级或多级交换机网络的离线调度方案计算。论文中用一个三级交换机网络的例子验证了系统的可行性和实用性。考虑到运行时总存在时基误差或线路延迟等各种不稳定因素，本论文就如何进行动态调整也做了深入研究，做了大量实验和复杂度分析，主要介绍了两种方案：最大延迟值优先调度方案和先延先服务方案。最大延迟值优先方案以

4、添加硬件方式实现，先延先服务方案时间复杂度为常数O(1)，可以直接用软件方法实现。这些方法与EDFBO相结合后，都能够一定程度地满足周期性业务环境下的运行时高速调度要求。最后对EDFBO算法和动态调整算法均在OPNET网络仿真环境下进行了仿真实验，实验结果表明改进后的算法在时延和吞吐率方面ABSTRACTWiththedevelopmentoftheInternet，theguaranteeingofQualityofService(QoS)hasbecomeanimportantresearchrespect

5、．AndpacketschedulingalgorithmsareimportanttechniquesofrealizingQoS．Firstly，thispaperanalyzestherecentpacketschedulingalgorithms：priority—drivenschedulingalgorithm，share—drivenschedulingalgorithmandtime—drivenschedulingalgorithm．Adynamicpriorityschedulingalgo

6、rithm-一EDF(EarliestDeadlineFirst)schedulingalgorithm---isanalyzedindetail．InordertoresolvetheissuesuchasovertimeinEDFschedulingalgorithminthelocalnetworks，animprovedpacketschedulingalgorithm：EDF_B0(EarliestDeadlineFirstBasedonOvertime)isdiscussed．Theimproved

7、algorithmanalyzeseachschedulingstepscarefully，makingfulluseofthefreetimesliceandsettingatemporarypriority，whichsolvestheproblem-一real—timetasksmay．beovertimeinHighspeedlocalnetworks一一better．Secondly，inordertocalculatetheschedulingsolutionbeforesystemrunning-

8、-implementinghighspeedscheduling一—wedesignanofflinecalculator．Accordingtothefeaturesoftimesliceandreal—timetasksscheduling，weprovideaperiodictaskmodel，aconnectionmodelandEDF-B0schedulingalgorith