TheMACSublayer TheMediumAccessControl(MAC)sublayeristhebottomhalfoftheDatalinklayer.The upperhalfiscommonlycalledtheLogicalLinkControl(LLC)sublayer. Primaryfunction Arbitrateaccesstoasharedtransmissionmedium.TheMACsublayerisNULLforpointto pointchannels.

Motivationfortheuseofasharedchannel:

SharinggivesbetterperformancethanstaticsuballocationusingpureTDMorFDM Assumeinterarrivalandservicetimedistributionsareexponential:

N =numberofstations=10 C =capacityofthechannelinbitspersecond=10,000bits/sec 1/ =meanbits/frame=1,000bits C=servicerateofthechannelinframes/second=10frames/sec =totalrateatwhichframesarrive=5frames/sec T =meandelay=1/(C)=1/(105)=0.2secs NowsupposewecouldsubdividechannelusingFDMorTDM C/N =newcapacityofeachsubchannel=1frame/sec /N =arrivalrateofeachstation=0.5frames/sec T =1/(C/N/N)=N/(C )=10/(105)=2secs

Sharingischeaperthanreplication(dedicatedpathsbetweenendptpairs) Nevertheless,replicationisbecomingcommoninwirednetworks LANsarenowcommonlystarwiredwithacentralswitch Theswitchsupportsconcurrenttransfersbetweendifferenthostpairs Theswitchcontainssomeoutputbufferingforcommontargets.

Sharinginsteadofreplicationmaybetheonlyviableoption Forwirelessnetsitsnotpossibletoreplicatespace! Forcablenetsreplicationwoulddefeattheprimaryadvantageofcablenoneedto starwiretheworldasinthetelphonesystem.

ModelparametersforsharedmediumMACanalysis Stationmodel: Nindependentstations.Eachgeneratesframesatrate Channelmodel Asinglechannelisusedbyallstations Nohardwarebasedpriorityassignment(asthereisonacomputersystembus) Twoframeswhosetransmissionsoverlapcauseacollisionthatdestroysboth. Timingmodel Continuoustime: Slottedtime: Channelsensemodel Carriersense: Nocarriersense: Collisionmodel: Collisiondetection: NoCD:

framesmaybetransmittedatanytime. framesmaybetransmittedonlyatdistinctclockticks

stationscandetermineifchannelisbusybeforesending notpossibletodetermineifchannelisinuse

stationscanhearacollisionandimmediatelystop stationcontinuestosendentireframe

Approachestocontrollingchannelaccess Contention: Tokenpassing: Reservation: Hybrid: Juststarttransmitting(Collisionsusceptible) Can'ttransmituntilyoureceivetoken(Collisionfree) Makeapriorreservation(Collisionfree) Contentionbasedreservationsystems.

MACprotocolconsiderationsforcontentionbasedapproaches WhencanItransmit? Anytime/anyslot Onlyaftersensinganddetectingidle Onlyaftersensingidleandwaitingarandomtime Decreasing Greediness

Maybedifferencesinbehaviordependinguponwhetherthechannelis initiallyfoundtobebusyoridle. HowdoIdetermineiftherewasacollision? Hearitwhenithappens(Ethernet)(packettime>>RTT) Hearitlater(Aloha)(packettime<<RTT) Don'thearitatall(802.11)andtimeoutformissingACK HowlongdoIwaitafteracollisionbeforeretrying?

Statesofasharedmediumchannel Thechannelalwaysexistsinoneofthreestates(andtwoofthemarebadfor throughput): Idle Collisioninprogress Successfultransmissioninprogress Oftenitisassumedthatallstationshaveaninfinitebacklogoftraffictosend.Inthat casetheefficiencyoftheMACprotocolis

eff=timespenttransmitting/elapsedtime
wheretheelapsedtimeisthesumofthetimespentineachofthethreestates.The efficiencyofaprotocolmayalsobeexpressedasthenumberofsuccessful transmissionsperpackettransmissiontime. Itistypicallythecasethatreducinggreediness decreasesthetimespentcollidingbutitalso increasestheamountofidletime. Sinceidleisjustascostlyascollidingintermsoflossofefficiencywedon'twantto betoonice.

PerformanceanalysisofPureAloha Assumptions Infinitenumberofstations Nocarriersense Noslottedtime Randomwaituntilretransmission Entirecollectionofstationsgeneratenewtrafficatrate Allpacketshavethesamelength Sincetimeisnotslotted,windowofcollisionvulnerability=2packettimes S=Throughputinpackets/packettime= ifsystemisstable G=Totalnumberoftransmissionattempts/packettime(includingcollisions) S<1Ifsystemisstable G>= S P0=Probability(orfraction)ofsuccessfultransmission. S= P0GThenumberofsuccessfultransmissionsperpackettime.

Poissonprobabilityofexactlyktransmissionsintpackettimes.

Pk , t =G t

G t

k!

Windowofcollisionvulnerabilityinpurealohais2packettimes. Becausewehaveassumedaninfinite#ofstations,P[mytransmissionsucceeds|I decidetotransmit]is:

P0= P0,2=2G
Thus

2 G

0!

=e2 G

S= P0 G=G e

2G

==>maxthroughput0.18packets/packettimeatatotalofferedloadof0.5packets perpackettime.

SlottedALOHA Alltransmissionsmuststartataslotboundary.Thereforethewindowofcollision vulnerabilityisnowreducedto1packettimeand

e P0= P0, 1=G =eG 0!

and

S=P0G=GeG
MaximumvalueoccursatG=1 InthiscasewhenG=1 P(0,1)=Prob[0attemptsinaslot]=eG=e1=0.37=%wasted P(1,1)=Prob[1attemptinaslot]=GeG=e1=0.37=%successes 1P(0,1)P(1,1)=0.26=%collided.

ThetextshowshatE[numberofattempts/transmission]=eG Thisresultalsofollowsmoresimplyfromthefactthat G=SE[numberofattempts/transmission] G=GeGE[numberofattempts/transmission] E[numberofattempts/transmission]=eG

CarrierSenseMultipleAccess(CSMA)protocols: AssumethatunlikeAlohastationscanandmustsensecarrierbeforeattemptingto transmit.BoththeoriginalEthernetandsomemodernwirelessprotocolsfallinthis class. VaryingtypesofPersistencehavebeensuggested: 1Persistent appliestoslottedornonslottedtime transmitanytimecarriersensedfree ifcarriersensedbusy transmitassoonascarriersensedfree Advantage: reducestimeintheidlestate Disadvantage: increasescollisions Nonpersistent nonslottedtime transmitanytimecarriersensedfree Ifcarriersensedbusy waitarandomamountoftimeandsenseagain. Advantage: Potentiallyhigherthroughput Disadvantage Worselatency

Ppersistent assumesslottedtime slot=1contentioninterval>=upperboundonsignalpropagation sensechannel ifchannelsensedfree transmitwithprobabilityp delayoneslotwithprobability1pandreturntosense else(channelbusy) delayoneslotandreturntosense PQpersistent Actwithppersistencewhenchanneldetectedidle Actwithqpersistencewhenformerlybusychannelgoesidle Typicallyp>q

Dealingwithcollisions = onewaysignalpropagationtime

Collisionsoccurwhen: twoormorestationsindependentlytransmitwithin unitsofeachother twoormorestationsina1persistentsystembecomereadyduringthe transmissionofanother andpropagationtimeintherealworldisvariable! CSMA/CDsystemscandetectcollisions Minimumtimetodetectisforthestationthatstartssendingfirst Maximumtimetodetectis2 Whenacollisionisdetectedisdetected,asendingstation Stops Jamsfortime2 Backsoffandwaitsarandomamountoftime(possiblep,q,r persistence) Thecostofacollisioninlostchanneltime Purealohaminimumofoneandamaximumoftwopackettimes Slottedalohaexactlyonepackettime CSMA/CDEthernetMinimumof3maximumof4(<<packettime).

10

PerformanceanalysisofCSMA(SimplifiedversionMetcalfandBoggs1976) k=numberofstations p=Prob[anystationtriestotransmitinagivenslot] A=Prob[somestationsucceedsinacquiringtheether] A=kp(1p)k1=Binomialprobabilityofaexactlyonestationattemptingto transmitinagivenslot. Aismaximizedatp=1/k A1/e=0.37(sameasmaxSinslottedAloha)ask P[CIlength=j]=A(1A)j1=P[successafterj1failures] E[CIlengthincontentionintervals]==1/A E[lengthofcontentionintime]=2/A Efficiency=Timespenttransmitting/(Timespenttransmitting+TimeSpent Contending) =P/(P+2/A) whereP=Packettime=thetimerequiredtotransmitasingleframe =L/cLengthofthecable/speedoflight P=F/BF=framesizeinbitsa B=channelspeedinbitspersecond

Eff=1/(1+2/PA)=1/(1+2BL/FAc)

11

Consequences: Increasingthebitratedecreasesefficiency Increasingthelengthofthecabledecreasesefficiency Increasingtheframesizeincreasesefficiency Increasingthespeedoflightincreasesefficiency AsP>2 Eff>1/(1+e)~0.26 whichisworsethanslottedaloha!!

Thegraphshownabovewascomputedusingtheparameters c=300000km/sec L=2km B=10,000,000BPS A=1/e EfficiencyismuchhigherthanpossiblewithAlohawhenthelengthofthecontention slotismuchlessthanthelengthofapackettime.

12

RealWorldLANprotocols ThreemajorapproacheshavebeenemployedinwiredLANs EarlyLANs Contention(CSMACD/Ethernet) Tokenpassing(Tokenring/Tokenbus) LANsofthepast10years Starwiredandswitched(ATM/SwitchedEthernet) Wireless(CSMACA/802.11)

13

OriginalEthernet(IEEE802.3) 1persistentCSMA withCDand binaryexponentialbackoff slottedtime:2=51.2 usecs aftericollisionsastationwaitsbetween0and2i1slots maxwaitis1023 maxretriesis16 Frameformat(stillinusetoday) 7bytes preamble10101010 1byte Startofframe 2or6 Destinationaddress(GlobalvsLocalinbit46) 2or6 Sourceaddress 2 Lengthofdata 01500 payloaddata 046 pad(Minframelength=64bytes=51.2usecat10Mbps) 4 checksum Operationalconstraints(original10Base5) 10 Megabits/second Base Basebandsignaling 5 Hundredmetersegments 2.5KmMaxdistancebetweentransceivers 4Repeaters Maxalonganypath Bridgesmaybeusedto extendfurther reduceloadonsegments Physicalencoding..Manchesterencodedbasebandsignal

14

Multiplestandardshaveevolved.. 10Base5(Original500Mruns/thickwire/vampiretaps) 10Base2(200Mruns/thinwire/BNCconnectors) 10BaseT(100~150Mruns/Cat3and5UTP/RJ45Connectors) 100BaseT(100MCat3and5UTP) GigabitoverCat5UTP Gigabitoverfiber. 10Gigabitoverfiber(andCat6?) FiberlinkscanbeconsiderablylongerthanUTPbuttheboththemediumandthe NICsareconsiderablymoreexpensive. Packetsizeissues Packettimefor1500bytesona1Gbpslinks~12microseconds ThiscreatesexcessiveCPUloadonhostsduetointerruptprocessing. Solutionsinclude: Largeframesizes Interruptcoalescing

15

Connectionmechanisms Sharedbus(10Base2/5) Sharedmediumhub(10BaseT/100BaseT) Receivesononeportatatimeandtransmitsinputtoalloutputs Switchedhub(raisestheeffectivethroughputofthenet) Canreceiveonmultipleportsatatimeandtransmitsonlytodest. Switchcanconductmultipletransfersatonetime. Unicastpacketsaresentbyswitchonlytodestinationhost. Storeandforwardswitch CanBufferwholepacketslikearouterbeforeretransmitting Collisionproblemiseffectivelyremoved. Cutthroughswitch (reducesthelatencyofthestoreandforwardswitch) Forwardspacketsassoonasaddressisrecognized. Thusmodern"Ethernets"sharelittlemorethanframeformatwiththeirCSMACD precursors

16

Tokenpassingprotocols: Generalprinciples Asingletokenispassedfromstationtostationinafixedroundrobinpattern Astationmaynottransmituntilitholdsthetoken Thelengthoftimeastationmaytransmitislimited Whenthetimelimitisreachedorthestationhasnomoredatatosend,thetokenis passed. Operationalissues Initializationhowdoesthefirsttokencometobecreated Addinganewsystemtoanoperationalring Removingasystemfromanoperationalring Gracefully Aftercrash Lossoftoken(holderpoweredoffornetworkerror) Duplicatetoken(tworingssplicedtogether) Existingstandards TokenBus: IEEE802.4 TokenRing: IEEE802.5 FDDIRing: SimilartoIEEE802.5 Majordifferencesrelatetocontroloftheringoperation Bus: Fullydistributedcontrol Ring: Centralizedcontrol Tradeoffis(theoretically)oneofrobustnessvs.simplicity

17

TokenBus: StationsareattachedtoasharedmediumbusasinEthernetanduseaCSMAlisten beforetransmitprotocol. Exercise:CouldthisprotocolbeusedinaWirelessenvironment. Majorissues Membershipmanagement Networkinitialization Addingnewstation Orderlywithdrawalofastation Faultmanagement Losttoken Duplicatetoken Lostsuccessor Prioritymanagement 4Priorityclasses0,2,4,6 TokenpassingisinMACadddressorderfromhighaddresstolow Frameformat 1+bytes 1byte 1byte 2or6 2or6 n 4 1 preamble10101010 Startdelimiter Framecontrol(Packettype)(TypeforTOKENiswronginhandout.. shouldbe8 Destinationaddress(GlobalvsLocalinbit46) Sourceaddress Data checksum Enddelimiter

18

Eachstationmaintainsazilliontimersandmustalwaysknow Itsownaddress(thisstation)(TS) Thenextstation(NS) Thepreviousstation(PS) Initialization CLAIM_TOKEN Stationscontinuallylistenforvalidtransmission,andifoneisnotheard,they timeoutandissueCLAIM_TOKEN. Ifacollisionoccurs Contentionisresolvedusingaquartiarycountdown ACLAIM_TOKENframecontainsupto4extraslotswhosepresence usagedependson"current"twoaddressbits Astationlistensaftercompletingitsframe. If(continuingtransmissionheard) GIVEUP else Repeatusingnexttwoaddressbits Ifnocollisionthetransmittingstationnowownsthetoken

19

Addinganewstation SOLICIT_SUCCESSOR_1(NS)(havinga1slotresponsewindow) MayormaynotbeissuedeachTokenrotation InvitesstationsbetweenTSandNStoattempttojoinbus StationwishingtojoinrespondswithSET_SUCCESSOR Ifcollisionthetokenholder TransmitsRESOLVE_CONTENTIONwhichhasa4slotresponse window Collidersreplyinslot#associatedwith1sttwoaddressbits. Ifcollisionrepeated Continueusingnextaddressbitsuntilresolved. LowestnumberedstationintheringusesaSOLICIT_SUCCESSOR_2 SOLICIT_SUCCESSOR_2(NS)(hastworesponsewindows) StationswithaddresslowerthanTScanreplyinwindow1 StationswithaddresshigherthanTScanreplyinwindow2

20

Orderlyexit SendSET_SUCCESSOR(PS)toPS Lostsuccessor IssueWHOFOLLOWS(NS)specifyingcurrentsuccessor IfresponsereceivedupdateNSpasstoken IfnoresponseissueSOLICITSUCCESSOR2 Anystationcanrespond Ifonedoesatwostationringiscreated LostToken TimeoutandCLAIMTOKEN Rebuildring Duplicatetoken Generallycausedbypartitionedbusbeingrejoined. Generallydetectedbyacollisionoccurrence Actionistodroptoken Mayresultinlosttoken

21

Prioritycontrol(simplified): CertainproportionoftotalTokenHoldingTimecanbereservedforeachtypeof trafficPriority6,4,2,and0. Problem:Ifnotbusyyoumighthaswellbeabletosenddataofotherclasses: THT=tokenholdingtime:themaximumtimethatastationcanholdthe tokentotransmitclass6data. TRT4=tokenrotationtimeforclass4:maximumtimethatatokencantaketo circulateandstillallowclass4transmissions. Class4time=TRT4(Timeoflastrotation+timeofclass6 transmission) N*THT>TRT4=>Class4trafficmaybestarved. Example: N=10stations THT=20msec Ifallstationshavealwayshaveclass6trafficitwilltake200msecfora completerotation.IfTRT4=220thentherewillbeatotalof20msecper rotationforclass4traffic.

22

TokenRing Basicsofoperation Nocontentionatall Eachstationhasastoreandforwardbuffer Txcanbedrivenfrom thestoreandforwardbuffer(idle) onboardpacketbuffers(transmitting) Rxcanbedirectedto thestoreandforwardbuffer(idle) onboardpacketbuffers(receive) the"bitbucket"(drain) Astationcan'ttransmituntilitinvertstokenbitbecomingthetokenholder Theholdercaninjectapacket Theholdermustdraineachpacketthatitsends. TheholderrecreatesthetokenafterTHT(def10ms)expiresornomoredata Theringmustbelongenoughtoholdthetoken 802.5

4or16Mbits(booksays1or4)nowavailablein100Mbitflavors Typicallyhookedupviawirecenters(Hubs) Multiplewirecentersmaybecabledtogether

Packetformat Tokenbitis4thbitinACbyte Addressingasin802.3and802.4 FS(framestatus)byteatendcarries AAddressrecognized CFramecopiedbits

23

Ringmaintenance Activemonitorelection StationtransmitsCLAIM_TOKENstreamandlistens: Seesownaddress Success Seeshigheraddressdesistssendingandgoesintorepeatermode Seesloweraddresscontinuessending Highestaddressstationeventuallywins: Ringmaintenanceissues Lossofactivemonitor Orphanframes Lossoftoken Tokenprioritystuckhigh Activemonitorfunctions PeriodicallyissueACTIVE_MONITOR_PRESENT Regeneratetoken SetM=1oneachvalidframeorhighprioritytoken M=1onframeortoken Eatframeortoken Regeneratetoken Evidenceofactivemonitor Gotostandbystatus Insertdelaybitsasrequired

24

Prioritycontrol 8prioritylevels TwofieldsineachACbyte Priorityfield Reservationfield Astationwithhighprioritytrafficcanmakeareservation Stationholdingthetokenonseeingreservationmust Rememberstate Setprioritytoreservation Immediatelyreleasetoken Stationissuingahighprioritytokenisresponsibleforreducingthepriority

25

Comparisonofthethreetechnologies Factor Minlatency Maxlatency Maxthroughput Cost/Complexity 802.3 Low High Medium Low 802.4 Medium Medium High High 802.5 Medium Medium High Medium SwitchedE Low Medium High Low

Othercollisionfreeprotocols: Polling Onestationisidentifiedaprimary.Allothersassumesecondarystatus. Primarypollssecondariesinroundrobinfasion.Secondariesmaynot transmituntilpolled. Bitmap Contentionslotsinwhichstationsmakereservations Followedbyframeslots=innumbertobitsinthebitmap

Disadvantages Bitmapslots2 ratherthan1bittimeinsize Lownumberedstationsgetworselatencyatlowloads. Highnumberedstationsgetworselatencyatmoderateloads. Youmustchangebitmapsizetoaddstations Bitmaplatencyatlowloadsespeciallyifslotsare2

26

BRAP=BRAM+MSAP Stationbegintransmissionimmediatelyaftersettingbitmapbit. Bitmaprestartsfollowingtransmissionwiththestationaftertheonethatjust transmitted. Disadvantagesremaining: Bitmapslots2ratherthat1bittimeinsize Youmustchangebitmapsizetoaddstations Bitmaplatencyatlowloadsespeciallyifslotsare2 Binarycountdown Bitmap=numberofbitsinastationaddress Ifastationhasa1bitatcurrentslotitwritesitintotheslot.... Untilitseesa1bitwritteninaslotwhereithasazero. Inthatcaseitgivesup. Result:Highestnumberedreadystationwins. Obviouslythisisunfair... Solution Usevirtualstationnumbers. AfterasuccessfulXmitbecomevirtualstation0. Allstationsbetweentransmitterand0getincremented. ===>Highestprioritystationistheonethathasn'ttransmittedinthe longesttime.

27

OtherMACprotocols FDDI Opticaltokenring 100Mbits/second Senderregeneratestokenatendoftransmission==>multiplepacketspossible onRing Formerlyusedtolink802.xLANSinalargeenterprise/ NowreplacedbyGigE Satellitenetworks FDM,STDMokforphonecircuits Adaptivereservationschemesbetterforburstydatatraffic. Objectiveofsuchschemes: Heavy<Load>Light TDMAloha Anumberofadaptiveprotocolshavebeenproposed,butintherealworldFDM, STDM,ALOHAandCDMAhavebeenused.

28

WirelessNetworks TheElectromagneticSpectrum Canbeviewedassinusoidal"waves"passingthroughspace Includesradio,infrared,visiblelight,ultravioletlight,Xray,Gammaray Frequency,f=numberofcompletecyclesofthesinewave/secondmeasuredinHz Wavelengthl=lengthaofcompletecycleofthesinewaveinmeters Fundamentalrelationshipisfl=c. IflismeasuredinmetersandfinMhzfl=300. Achannelisacontinuousrangeoffrequencies[f1,f2]orequivalentlywavelengths [l2,l1] Thebandwidthofachannelisf2f1. ThemaximumnumberofbitsperHzisdeterminedbytheSNRtypicallyintherange of1to16forwiredandwirelesschannels(c.f.Dialmodems)

29

(WavelengthimagefromUniversebyFreedmanandKaufmann.)

30

Example:The1.3micronband(infraredlight)(Channelsusedinwirelessradio communicationshavesignificantlylowerbandwidth!

l2=1.21microns l1=1.38microns
Thefrequencyatthecenteroftheband(1.3micronwavelength)isapproximately:

f=c/l~=(3*10^8)/(1.3*10^6)=2*10^14Hz
Thebandwidthisthedifferencebetweentheminandmaxfrequencies:

df

=f2f1 =c/l2c/l1 =c(l2l1)/l1l2 =cdl/l2l1 ~=cdl/l2^2=3*10^8*0.17*10^6/1.7*10^(12) ~30Thz

31

Spreadspectrumtechniques BasicobjectiveDistributesignalenergyacrossarelativelywiderangeoffrequencies. Motivations securecommunications, increasedresistancetonaturalinterferenceandtojamming, andtopreventdetectionofcommunications Implementations

Frequencyhopping(primarilyusedinmilitaryapplications) OFDM(paralleltransmissiononmultiplesubchannels) directsequencespreadspectrum(probablythemostdifficulttounderstand)

Directsequence

Eachbitistransmittedusingasequenceof"subbits"calledchips. Thespecificsequence(e.g.+++)thatisdefinedtomean"1"bit Thissequencedoesn'tchangeduringoperation. Thecomplementofthesequence(++++)thenrepresentsa"0"bit. Differenttransmittersusedifferentchippingsequences Thechippingsequencesaredesignedtospreadthesignalpower.

32

CDMACodeDivisionMultipleAccess Adirectsequencespreadspectrumtechniqueinwhichitis(theoretically)possiblefor allstationstosendsimultaneouslyandnondestructively. BittimesaredividedintoNChips(typically64or128) Eachstationhasauniquechipsequenceof64or128(+1/1)'s Tosenda1bitthestationsendsitschipsequence Tosenda0bitthestationsendsthecomplementofitschipsequence Chipsequencesaremutuallyorthogonalwithrespecttothestandarddot product. (C1dotC2)=0 (C1dot~C2)=0 (C1dotC1)=N (C1dot~C1)=N Receivermayreceivesuperimposedsignals C1+~C2+C3+~C4 Receiverdotsthesumwiththedesiredsender'sChipsequence (C1+~C2+C3+~C4)dotC3=C3dotC3 Example: A:111+1+11+1+1 B:11+11+1+1+11 C:1+11+1+1+111 D:1+11111+11

IfsomechipsarereceivedinerrorthenthedotproductmaybesomewhereN andN.IfthevalueisalmostN,thenitslikelya1bitwassent.Ifitsnearly N,thenlikelya0bitwasmeant.Ifthedotproduct~0thenwhoknows??

33

PNsequences InpracticeitiscommontousePN(pseudorandom)noisesequencesinsteadofdedicated chippingsequences.

Thesequencesconsistofamixof1and+1's Tosenda1bitthesequenceitselfissent Tosenda0bittheinverseofthesequenceissent ThereceiverperformsthedotproductofthereceivedsequencewiththeknownPN sequence

Alargepostitiveresult>1 Alargenegativeresult>0

34

WirelessLANsIEEE802.11 Original802.11physicallayerusedthreebasicphysicallayertechnologies: Infrared Microwave(2.4Ghz)Industrial,Scientific,Medical(ISM)Band Frequencyhoppingspreadspectrum Directsequencespreadspectrum Datarateslimitedto12Mbps Neweradditionsinclude 802.11a(OrthogonalFDM)(OFDMusing52subchannelsof1Mhz bandwidthprovidingupto54Mbpson5GhzUNNI(unlicensed NationalInformationInfrastructure)band 802.11b(HRDSSS(HighrateDSSS))upto11Mbps 802.11g(OFDM)upto54Mbpson2.4GhzISMband. 802.16>WiMAXSC/OFDM/OFDMAusing192/256subchannels

35

MACLayerIssues ThewirelessenvironmentisfarmorehostilethanthewiredoneandthisaffectsMAC protocoldesign.Herearesome"classic"problems: Thehiddenstationproblem ABC SupposeCistransmittingtoBbutAisoutofrangeofC IfstationAwishestosendtoB,itwillsenseidlebutwillcauseacollision. Theexposedstationproblem DABC SupposeAistransmittingtoDandBwantstotransmittoC. Bmayfalselyconcludethatasuccessfultransmissionisimpossiblewheninfactit wouldsucceed.

36

Operationalmodesof802.11networks Adhocmode An802.11networkingframeworkinwhichdevicesorstationscommunicatedirectlywith eachother,withouttheuseofanaccess point(AP).Adhocmodeisalsoreferredtoaspeer topeermodeoranIndependentBasicServiceSet(IBSS).Adhocmodeisusefulfor establishinganetworkwherewirelessinfrastructuredoesnotexistorwhereservicesarenot required. Infrastructuremode: AmodeinwhichdevicescommunicatewitheachotherviaanAccess Point(AP)whichis typicallyconnectedtoawirednetwork.WhenoneAPisconnectedtowirednetworkanda setofwirelessstationsitisreferredtoasaBasicServiceSet(BSS). TheESS AnExtendedServiceSet(ESS)isasinglelogicalnetworksegment(alsoknownasasubnet), ItisidentifiedbyitsServiceSetIdentifier(SSID).Iftheavailablephysicalareasofthe wirelessAPsinanESSoverlap,thenawirelessclientcanroam,ormovefromonelocation (withawirelessAP)toanother(withadifferentwirelessAP)whilemaintainingNetwork layerconnectivity.Forexample,cuairnetandtigernetareSSIDsandthecampuswireless networksareESS's. Withininfrastructuremodeoneoftwotypesofcoordinationfunctionisused: DCFDistributedCoordinationFunction:TheMACprocedureisdistributedamong allthewirelessstations. PCFPointCoordinationFunction:AbasestationalsocalledanAccessPoint(AP) controlsallaccesstothechannelusingthepollingtechnique. DCFismandatorybutPCFisanoptionaladdon.AllrealworldwirelessLAN's useDCF.

37

DCF 802.11usesaMACprotocolcalledCSMA/CA(CollisionAvoidance) TwomodesofCSMACA PhysicalChannelSensing Sensechannel Ifidleemitentireframe Ifbusydeferuntilcontentionslot(backoff)counterreaches0 Ifcollisionusebinaryexponentialbackoff. VirtualChannelSensing CABD SupposeAwishestosendtoB AsendsashortRTStoBcontainingthelengthofthemessage BsendsCTSbacktoA ChearsRTSandnotesthenetworkbusyinitsNAV(networkallocationvector) DhearsCTSandnotesthenetworkbusyinitsNAV Asendsthepacket BsendsanACK Dealingwithnoisychannels Framesmaybefragmentedwitheachfragmentcarryingitsownchecksum FragmentsarenumberedandackedindividuallyusinganS&Wprotocol. TheNAVmechanismprotectsonlythefirstfragment PCF NostationmaysenduntilpolledbytheAP Anentry/exitprotocolisalsorunbytheAP

38

Interoperation of DCF and PCF |Frame | |SIFS |<ACK> | PIFS |<Poll> | DIFS|<Data> | EIFS| | |Badframerecovery|

SIFSShortinterframespacing TheSIFSisa10usecdelaywhosepurposeistogivethelasttransmittertime toswitchhisradiofromTxtoRxmode. OnlyonestationiseligibletosendwhentheSIFSexpires Theeligiblestationwillsend CTS ACK ResponsetoPoll Nextfragmentofaburst PIFSPCFInterFrameSpacing IfanAPoperatinginPCFmodewishestosendapollitmustwaitSIFS+PIFS andifthechannelisstillidleitmaydoso. ThereceiverofthepollmayrespondattheendoftheSIFS DIFSDCFInterframeSpacing Thestandardcontentionslotis20usec. TheendoftheDIFSis2contentionslottimesbeyondtheendoftheSIFSfor atotalof50usec.(orSIFS+PIFSinaPCFsystem). EIFSExtendedInterFrameSpacing Usedbyareceiverofabadorunknownframetoreport

39

The802.11contentionalgorithm Adualpersistenceapproachisemployed

LimitsonthesizeofthecontentionwindowCWaredefinedbyCWmin=31slots andCWmax=1023slots.ThecurrentsizeofthecontentionwindowiscalledCW. CWisresettoCwminafterasuccessfultransmissionandisdoubledaftereach collision. Whenastationbecomesreadytosend,itsensesthecarrierforDIFSamountoftime andifnothingisheardittransmits. Ifithearsatransmissioninprogress,itwaitsuntiltheTxendsandcomputesa randomnumberofslotswcountbetween0andCW(WhereCWisinitiallyCWmin). ItlistensthroughtheSIFSandtheDIFSandifithearsatransmissioncommenceit defersuntiltheendofthattransmission.Whilenotransmissionisheard,it decrementswcountforeach20usecslottimethatpasses. Whenwcountreaches0,thestationwilltransmit. Ifanotherstationstartstransmittingbeforewcountreaches0,thedecrementingof wcountissuspendeduntiltheframe,thefollowingsifsandpifshavepassedatwhich timeitresumeswhereitleftoff..Inthiswaythelastcomefirstservedbehavioris avoided. AcollisionisinferredfromamissingCTSorACK.CWisdoubledwhenacollision occursuntilitreachesCWmax.CWisresettoCWminwhenatransmission succeeds.

40

802.11e ToprovidesomemannerofDiffServ(butstillnottheQoScapabilityofWiMAX)EDCFwas invented. In802.11efourtrafficclassesareidentified: TC0VOIP TC1Video TC2BestEffort TC3Background ThesetrafficclasseshavedifferentiatedvaluesofCWminandCWmax. TheprotocolalsoemploysanvariableArbitrationIFS(AIFS)whichgeneralizestheDIFS andthismakesitpossibletogiveonetrafficclassABSOLUTEpriorityoveranotherina heavilyloadednetwork.InthetablebelowitcanbeseenthattheAIFSforTC0andTC1is thesameastheDIFSbutTC2andTC3havesuccessivelyhighervalues. Valuesoftheseparametersaretypicallyconfigurableandmappingparametersetsto workloadsanddesiredoutcomesisa"workofart". TrafficType Background(TC3) BestEffort(TC2) Video(TC1) Voice(TC0) CWMin 31 31 15 7 CWMax 1023 1022 31 15 AIFS 7 3 2 2

41

802.11FrameStructure Bytes 2 Framecontrol 2 Durationtimetheframe+ackwilloccupychannel 6 Address1Sourcehost 6 Address2Desthost 6 Address3SourceAP 2 Seq# (12bitsframeidand4bitsfragmentid) 6 Address4DestinationAP 02312Data 4 Checksum Framecontrolword Bits 2 2 4 1 1 1 1 1 1 1

ProtocolVersion Framebasetype(Control,management,ordata) Subtype(RTS,CTS,etc.) ToDS(Frameisgoingtoanintercelldistributionsystem) FromDS(Frameiscomingfromanintercelldistributionsystem) MF(Morefragmentsfollowthisone) Retry(Retransmissionofpreviouslysentframe) Pwr(Powermanagementbitusedtoputstationtosleeporwakeitup) WEP(FramebodyhasbeenencryptedusingWiredEquivalentPrivacyalg) O(Processframesstrictlyintheorderinwhichtheyarereceived)

42

802.11Services Intercellservices Associationabilityofamobilestationtoconnecttoabasestation.Parameters includeSSID,datarate,PCFcapabilities,powermanagementneeds. Disassociationbreakingtheconnection.Canbetriggeredwheneitherthemobile stationorthebasestationgoesdown. Reassociationchangingofbasestation.Occurswhenamobilestationchangescells whileup. Distributionaroutingserviceprovidedbythewireddistributionsystem(DS) Integrationperformingrequiredpacketreformattingatabasestation.(e.g. reassemblyoffragmentspriortoforwardingonanethernet). Intracellservices AuthenticationAmechanismbywhichstationsmustauthenticatebeforebeing acceptedbythebasestation.Notintheoriginalstandardandpotentiallya nuisancetointernetcafeusers.Itsabsencehasledto"warchalking" DeauthenticationOccurswhenastationdisassociatesorreassociates. PrivacyTheflawedWEPalgorithm Datadeliverybesteffortservicelikeethernet.

43

Securityissues The802.11physicallayerislikeanearlyEthernetabusinwhichallstationshearall transmissions ItislesssecurethanearlyEthernetinthatanyunauthorizedpersoncan(almost) unobtrusivelymonitornettraffic. Seenewarchitect.htmlintheclassdirectoryforanexampleoftheproblem. Apotentialsolutionistoencrypteachpacket. WEP(usingavariantoftheRC4encryptionalgorithm)waschosenasthestandard. UnfortunatelyWEPturnedouttobeadefectiveimplementation. Seewepweaknesses.pdfandcrackingwep.pdfintheclassdirectory. Seetheairsnorthackkitontheweb. Currentsolution: BesuretouseSSLtools(ssh,scp,etc)whichuseanonbrokenimplmentation ofRC4 802.11i>802.112007definesanewencryptionsstandard(WPA)WiFiprototected accessthatisbasedontheAdvancedEncryptionStandard(AES)insteadof RC4.Itisavailableincurrentproductsandhasyettobebroken. Theproblemofdisseminatingandmaintainingcontrolofthesecuritykeystoalarge populationofusersremainschallenging. Otherwaysofenhancingsecurityinclude: Don'tbroadcasttheSSID. LimitassociationstostationshavingMACaddressesinanaccesslist.

44

Otherwirelesstechnologies 802.16(laterWiMAX)Designedtoprovidebroadbandwirelessservicetofixedstations (i.e.aMAN) Laterversionssupportmobility. MAClayerprotocolisavariantoftheDOCSISprotocol.

BluetoothDesignedtoconnectcellphonestocomputermodems(aPicoNetorPersonal AreaNetwork) Linksarelimitedto10m. Uses79channelsof1Mhzeachinthe2.4GhzISMband.

45

Data over Cable TV systems DefinedbytheDataofCableServiceInterfaceSpecification(DOCSIS). Thephysicallayermediumisasharedaccesscable. MACfunctionsarecontrolledbyaheadenddevicecalledaCableModemTerminating System(CMTS). UserattachmentpointsaredualporteddevicescalledCableModems(CMs)thatrun DOCSISonthecableside Ethernetontheuserside TrafficflowisalwaysCM<>CMTSneverCM<>CM TypicalaggregatebandwidthsharedbyallusersinDOCSIS1.1systems 30MbpsdownstreamfromtheCMTS 5MbpsupstreamtowardtheCMTS ATDMbandwidthsharingisenforcedbytheCMTSwithtypicalmaximumvaluesof 3Mbpsdownstream>now6Mbpsormore 256Kbpsupstream>now768Kbpsormore. DownstreambandwidthsharingissimplebecausetheCMTSistheonlyTx'er TheCMTSuses(possiblyprioritizedandordeficit)roundrobinservicetodeliver packetstoCMs

46

Upstreamchannelaccess Upstreambandwidthallocationisnotsosimple,becauseallCM'smustsharethesamecable. TheupstreamchannelisATDMmultiplexedinfixedtimeunitscalledminislots. Theminislotisapoweroftwomulitplenumberofbasicticks. Thebasictickis6.25usec. Typicalvalues: Upstreambitrate Basicticksperminislot Minislotlength Bytes/minislot

5.12*106bps 4 25usec 16

SinceastandardTCP/IPpacketrequiresatleast20byteseachofIPandTCPheadera minislotisnotintendedtocarryanentirepacket.Itshouldbeinsteadviewedas somewhatanalogoustoanATMcell.

47

Allocationofminislots UsageofindividualminislotsisdictatedbyaspecialcontrolpacketcalledtheMAPwhichis sentonthedownstreamchanneleveryfewmillisecondsanddescribesthenearfuture allocationofslotsintheupstreamchannel.ThesetofminislotsdescribedinasingleMAP iscalledaframe. Frametimeistypicallyintherange210msec. Upstreamusesofminislotsinclude: GrantstoCMsforupstreamdatatransmission ContentionSlotsfornewCMstorequesttocomeonline Unsolicitedgrantsforservicesuchascabletelephones(UGS) Grantsfordedicatedslotsinwhichupstreambandwidthcanberequestedina contentionfreeway(RTPS=realtimepollingservice). ContentionSlotsinwhichCMsmayrequestupstreambandwidth

48

Whenacablemodemhasbesteffortupstreamtrafficsendit: Generatesarandomnumberbackoffbaseduponitscurrentbackoffwindowsize StartingwiththenextMAPitwaitsbackoffcontentionslots(whichmaybemultiple maptimes)andthenmakesitsrequestinthenextcontentionslot. Ifsuccessful,therequestwillbeacknowledged(butnotnecessarilygranted)inthe nextMAP. Acollisionisinferredbytheabsenceofanacknowledgment.TheCMmustdouble itsbackoffwindowandstartover. Refinements Theminandmaxsizesofthebackoffwindowarespecifiedperiodicallybythe CMTSinspecialcontrolmessagesandsomaybedynamic. ACMcanrequestupstreamgrantsforamaxiumofonepacketatatime,butapiggy backingfacilityallowsthestationtorequestadditionalgrantsattheendofthecurrent packetwithouthavingtousethecontentionmechanism. MultipleIPframescanbeconcatenatedinasingleMAClayertrafficburst.

49

QoSinDOCSISandWiMAX UpstreamServicecategoriesinclude: UGSaserviceflowreceivesunsolicitedgrantsatafixedrate. RTPSaserviceflowreceivesdedicatedslotsinwhichtorequestupstream serviceatafixedrate(butdoesn'thavetouseit).ARTPSflowcannotmake contentionrequests. NRTPSaserviceflowreceivesperiodicopportunitiestorequestupstream servicebutcanalsousethecontentionmechanism. BEonlythecontentionmechanismisused.

50

AssigningQoSattributes ClassifierruleUsedtoassociatepacketswithparticularserviceflowsbasedupon sourceordestinationMACaddress,IPaddress,Portaddress. ServiceflowHasaservicecategory(UGS,RTPS,etc)andaserviceparameters suchasminimumguaranteedthroughput,maximumpermittedthroughput,maximum allowedjitter. Typicallyserviceflowsandclassifierrulesmustbemanuallysetupbyasystem administrator.Sensibledefaultsforgenericcategories(VoIP,besteffort,etc)can facilitatetheproblemtoacertaindegree. DynamicServiceActivation(DSA) UGSandRTPSservicesconsumeupstreambandwidthwhenevertheyareactive. Atelephoneserviceshouldconsumebandwidthonlywhenacallisinprogress. Therefore,provisioningmustbeatwostepprocess.Thesystemadministratormust provisionaserviceflowbutDSAprotocolsbetweentheCMandCMTSactivateand deactivatetheserviceautomatically. Inthiswaybandwidthisnotconsumedbyinactivebutprovisionedflows.

51