CICQ交換機(jī)調(diào)度算法及基于時(shí)限的優(yōu)先級(jí)保證.pdf

1、東南大學(xué)博士學(xué)位論文CICQ交換機(jī)調(diào)度算法及基于時(shí)限的優(yōu)先級(jí)保證姓名：李勇申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)指導(dǎo)教師：羅軍舟20070301ABSTRACTABSTRACTWithnOinternalspeeduprequiredandparallel，distributeschedulingatinputandoutputtheClCQ(CombinedInputCrosspointQueuedorbufferedswitch)f

2、abricprovidesuniqueadvantageofdesigninghighperformanceswitchesTheopenproblemsinthisfieldale：lowlevelschedulingalgorithmsusuallyputemphasisonitspracticabilitywhichaimatachievinglittlebufferlowcomplexityandhighthroughputHi

3、gIIlevelschedulingalgorithmusuanyisconsideredtosolvesomeproblemswhichmustsatisfymorerestrictionssuchasdeadlineguaranteedetcMultideadlineschedulingproblemhasbeenprovedtObeNPcompleteifthreeormoledistinctdeadlines(classes)a

4、mpresentinthesetPriorityschedulingproblemwithdeadlineguaranteedhasalsobeenahotanddifficultproblemstudiedinthefieldofRealTimeschedulingHowevertheproposedlowlevelschedulingalgorithmsc柚onlyachieveofIeOrseveralrequirementsMe

5、anwhile，hilghlevelschedulingalgorithmsstillcannotbreaktheperformancelimitofEDFalgorithmsinthereeent30yearsThisdissertationaddressestheaboveopenproblemsInthelowlevelschedulingfieldperformanceanalysisresultsaleproposedunde

6、runiformtrafficandnouuniformtrafficThethreecriterionincludinglittlebufferlowcomplexityandhighthroughputmustbeobeyedinthedesignofschedulingalgorithmMoreoverRRarbiterisbelievedtobethebestchoiceintheoutputschedulingBasedont

7、heperformanceanalysisresults，aschedulingalgorithmisproposedwhichisliRlebuffer0(】)complexityand100％throughputinthelowlevelschedulingThenewalgorithmCallachieve100％throughputundereitheruniformOrnonuniformtraffic，maintaining

8、thesimplicityandeffectivenessofRoundRobinalgorithmandmeanwhileovercomingtheinstabilityoftheRoundRobinalgorithmundernonuniformtrafficInthehighlevelschedulingfieldanovelalgorithmnamedFlowbasedIterativePacketScheduling(FIPS

9、)isproposedTheFIPSalgorithmemployedentirelydifferentschedulingstrategywhencomparingtotheclassicEDFalgorithmThemultideadlinepriorityschedulingNPCproblemisconvertedtosolvethenetflowproblemwithupperandlowerboundthroughconst

10、ructtheflowbasedmodelbetweenthedifferentdeadlinespacketsetsFIPSalgorithmpromotesthelowerprioritypacketstotheidlepositionsinhighprioritypacketssetunderglobalconsiderationsnotrandomlyThecomparisonexperimentswithotherclassi

11、calgorithmssuchasEDFetc，indicatethatFIPShasalowerpacketdroprateandhigherschedulingSuccessratioThenewalgorithminlowlevelschedulingfieldsisindependentwiththetrafficmodelsItCanefficientlyovercometheservicelosscausedbynonuni

12、formtrafficBasedonthehardwaleindustrialbackgroundthatthelimitedbufferCallbeintegratedintocrosspoints，thenewalgorithmisabsolutelyapracticalalgorithmWhiletheCICQswitchemployedthenewalgorithm，theestimatedcostofferportwhichs