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

1、東南大學博士學位論文CICQ交換機調(diào)度算法及基于時限的優(yōu)先級保證姓名：李勇申請學位級別：博士專業(yè)：計算機應用技術(shù)指導教師：羅軍舟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