cubin_ChuanHengFoh_thesis

PerformanceAnalysisandEnhancementofMACProtocolsChuanHengFohB.Sc.,M.Sc.AThesissubmittedintotalfulfillmentoftherequirementsofthedegreeofDoctorofPhilosophyDepartmentofElectricalandElectronicEngineeringNovember2002(Producedonacid-freepaper)iAbstractThechallengeofdesigninganefficientMediumAccessControl(MAC)protocolandanalyzingithasbeenanimportantresearchtopicforover30years.ThisthesisfocusesontheperformanceanalysisandenhancementofMACprotocols,particularlytherandomaccessprotocols.PerformanceofthetwowidelyknownrandomaccessMACprotocols–theIEEE802.3MACprotocolthatemploystheCarrierSenseMultipleAccesswithCollisionDetection(CSMA/CD)protocol,andtheIEEE802.11MACprotocolthatusestheCarrierSenseMultipleAccesswithCollisionAvoidance(CSMA/CA)protocol,arefirststudied.Theyareanalyzedusinganewanalyticalapproachproposedinthisthesis.ThenewapproachisbasedontheideathattheserviceprocessofaMACprotocolcanbemodeledbyaPhase-Type(PH)distribution.Thisway,thearrivalprocessaswellastheserviceprocessoftheactualprotocolcanbedescribedbyacertainmultidimensionalcontinuoustimeMarkovchain.TheadvantagesofthisnoveltechniqueoverthetraditionalapproachforperformanceanalysesofMACprotocolsarethat:(i)itprovidesaunifiedmodelfortheanalysisofMACprotocols;(ii)itsignificantlysimplifiestheanalyticalmodelofaMACprotocolwhichmakesitpossibletoincludeamorecomplexandrealistictrafficmodelwithoutcompromisingtheprotocoldetails;(iii)vastknowledgeisavailableontheanalysisofacontinuoustimeMarkovchain,whichallowsformoreinsighttotheperformanceofaMACprotocol.ExtensivedemonstrationsoftheuseoftheapproachonperformanceanalysesofMACprotocolsareprovided,someofwhichconductedunderrealisticburstytrafficconditions.Asaresultoftheperformanceanalyses,itisfoundthattheIEEE802.3MACprotocolexhibitsrelativelylowandunattractiveperformance,especiallywhenitisoperatedat1Gb/sdatarate.Inresponsetothisfinding,twonewprotocolsareintroducedinthisthesis.Firstly,weintroduceanoveliitechnique,ReservationsbyInterruptions,toprovideanefficientreservationschemeforCSMA/CD.TheresultingprotocolisnamedCSMAwithReservationsbyInterruptions(CSMA/RI).PerformanceofCSMA/RIisevaluatedandcomparedwithCSMA/CD.ThestabilityofCSMA/RIisalsostudied.Inaddition,tworealisticscenarios,namelythesaturationanddisasterscenarios,areusedtodemonstratetheperformanceadvantageofCSMA/RI.Furthermore,performanceanalysesbasedonthenewapproachunderrealistictrafficconditionsareperformedtoshowtheperformancebenefitofCSMA/RI.OuranalyticalresultsshowthatCSMA/RIalwaysoffersbetterperformancethanCSMA/CD,andinsomecases,thedelayperformanceofCSMA/RIapproachesthatofaperfectschedulingG/D/1system.AperformancecomparisonbetweenCSMA/CD,CSMA/RIaswellasthetokenringprotocolisprovided.Finally,someimplementationissuesandlimitationsofCSMA/RIareaddressed.ThesecondMACprotocolintroducedinthisthesisiscalledtheRequestContentionMultipleAccess(RCMA)protocol.RCMAisadistributedgigabitMACprotocol.Itisdesignedtooperateinthepassivestaropticalnetworksuchasthe10BASE-FPversionofEthernetatagigabitdatarate.UnliketheexistingIEEE802.3zGigabitEthernetMACprotocolthatemploysCSMA/CD,RCMAisefficientandstableforawiderangeofusernumbersbasedonourstudyunderthesaturationscenario.Moreover,RCMAcaneasilyaccommodateservicedifferentiationwithintheMAClayerwithnoadditionaloverhead.Intermsofimplementation,itdoesnotappeartobedifficult.TheimplementationofRCMAmayleadtoacostcompetitiveyetefficientsolutionforthefuturegigabitLANs.iiiDeclarationIherebycertifythatthisthesisismyownwork,exceptwhereduereferenceismadeinthetextandthat,tomybestknowledgeandbelief,ithasnotbeensubmittedtothisuniversityortoanyotheruniversityorinstitutionforadegree.SignedChuanHengFoh11thNovember,2002ivAcknowledgmentsIwouldliketothankmythesissupervisor,ProfessorMosheZukerman,fordedicatinghisknowledge,unreservedencouragementandsupportthroughoutthisPhD.ItwashisinspiringcourseinNetworkDesignthatgavemeastartingpointforthisstudy.IwouldalsoliketothankthemembersofmyPhDexaminationcommitteefortheirvaluabletimeandadvice.Finally,andalways,Ithankmylovelywife,YukYeeLeung.Withoutherlove,dedicationanddevotion,noneoftheseiseverpossible.vTableofContentsAbstract......................................................................iDeclaration...............................................................iiiAcknowledgments....................................................ivListofFigures........................................................viiiListofTables..........................................................xvi1Introduction.........................................................11.1Background............................................................11.2Overview................................................................31.3Contributions..........................................................51.4Publications............................................................62RandomAccessProtocols...................................82.1Aloha......................................................................92.1.1ThroughputAnalysis.............................