CICQ交换机调度算法及基于时限的优先级保证

《CICQ交换机调度算法及基于时限的优先级保证》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东南大学博士学位论文CICQ交换机调度算法及基于时限的优先级保证姓名：李勇申请学位级别：博士专业：计算机应用技术指导教师：罗军舟20070301ABSTRACTWithnOinternalspeed-uprequiredandparallel，distributeschedulingatinputandoutput,theClCQ(CombinedInputCrosspointQueuedorbufferedswitch)fabricprovidesuniqueadvantageofdesigni

2、nghighperformanceswitches．Theopenproblemsinthisfieldale：lowlevelschedulingalgorithmsusuallyputemphasisonitspracticability,whichaimatachievinglittlebuffer,lowcomplexityandhighthroughput．HigIIlevelschedulingalgorithmusuanyisconsideredtosolvesomeproblems

3、whichmustsatisfymorerestrictions,suchasdeadlineguaranteedetc．Multi-deadlineschedulingproblemhasbeenprovedtObeNP-completeifthreeormoledistinctdeadlines(classes)ampresentintheset．Priorityschedulingproblemwithdeadlineguaranteedhasalsobeenahotanddifficult

4、problemstudiedinthefieldofReal-Timescheduling．However,theproposedlowlevelschedulingalgorithmsc柚onlyachieveofIeOrseveralrequirements．Meanwhile，hilghlevelschedulingalgorithmsstillcannotbreaktheperformancelimitofEDFalgorithmsintheree,ent30years．Thisdisse

5、rtationaddressestheaboveopenproblems．Inthelowlevelschedulingfield,performanceanalysisresultsaleproposedunderuniformtrafficandnou-uniformtraffic．Thethreecriterionincludinglittlebuffer,lowcomplexityandhighthroughputmustbeobeyedinthedesignofschedulingalg

6、orithm．Moreover,RRarbiterisbelievedtobethebestchoiceintheoutputscheduling．Basedontheperformanceanalysisresults，aschedulingalgorithmisproposedwhichisliRlebuffer,0(】)complexityand100％throughputinthelowlevelscheduling．ThenewalgorithmCallachieve100％throug

7、hputundereitheruniformOrnon-uniformtraffic，maintainingthesimplicityandeffectivenessofRoundRobinalgorithmandmeanwhileovercomingtheinstabilityoftheRoundRobinalgorithmundernon-uniformtraffic．Inthehighlevelschedulingfield'anovelalgorithmnamedFlow-basedIte

8、rativePacketScheduling(FIPS)isproposed．TheFIPSalgorithmemployedentirelydifferentschedulingstrategywhencomparingtotheclassicEDFalgorithm．Themulti-deadlinepriorityschedulingNP-Cproblemisconvertedtosolvethenet-flowproblemwithupperandlowerboundthr