《网路概论》PPT课件

-1-,網路概論Class4DataLinkControlPartII,授課老師楊人順2001/10/16-17,-2-,PresentationOutlines,ErrorDetectionTechniquesCyclicredundancycheckErrorControlErrorControlTechniqueErrorControlMechanismDataLinkProtocolsMultiplexingWhatismultiplexing?FrequencyDivisionMultiplexingTimeDivisionMultiplexingCodeDivisionMultipleAccessDigitalSubscriberLine,-3-,Cyclicredundancycheck,CRCisthemostcommonandpowerfulerror-detectingcodes.AlgorithmSendercalculatesaFrameCheckSequence(FCS)fromapattern.Sendersendsaframewith(Message+FCS).Receiverthendividestheincomingframebythesamepatternand,ifthereisnoremainder,assumetherewasnoterror.Modulo2Arithmetic:anexclusion-ORoperationtoreplacethe“Add”and“Subtract”DefinitionT=(k+n)-bitframetobetransmitted,withnkM=k-bitmessage,thefistkbitsofTF=n-bitFCS,thelastnbitsofTP=patternofn+1bits;thisisthepredetermineddivisor.,-4-,CRCPrinciple,TargetsinreceiversiteNoerrordetected:T/PnoremainderErrorsdetected:T/Pwithasleastonebiterror.Atrue:|P|=|F|+1FCSgeneration,-5-,CRCPrinciple(cont),ErrorDetectionExample:pp.204AnotherviewofCRC:expressallvalueaspolynomialsinadummyvariableXE.g.,M=110011,M(X)=X5+X4+X+1,P=11001,P(X)=X4+X3+1,-6-,CapacityofCRC,AnerrorE(X)willonlybeundetectableifitisdivisiblebyP(X).Thefollowingerrortypesaredetectable:Allsingle-biterrorsAlldouble-biterrors,aslongasP(X)hasasleastthree1sAnyoddnumberoferrors,aslongasP(X)containsafactor(X+1)Anybursterrorforwhichthelengthoftheburstislessthanthelengthofthedivisorpolynomial;thatis,lessthanorequaltothelengthoftheFCSMostlargerbursterrorsUndetectableerrorprobability(risthelengthofFCS)Abursterroroflengthr+1,undetectableerrorprobabilityis1/2r1Alongerburst,undetectableerrorprobabilityis1/2r,-7-,CurrentCRCVersions,CRC-12,P(X)=X12+X11+X3+X2+X+1Usedforthestreamof6bitscharacters,FCSis12bitsCRC-16,P(X)=X16+X15+X2+1Usedforthestreamof8bitscharacters,FCSis16bitsPopularformostapplicationsUnitedStatesCRC-CCITT,P(X)=X16+X12+X5+1Usedforthestreamof8bitscharacters,FCSis16bitsPopularformostapplicationsEuropeCRC-32,P(X)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1Somepoint-to-pointsynchronoustransmissionstandards.,-8-,ErrorControl,Errortypes:lostframe,damagedframeErrorcontroltechniquesErrordetection:typicallyCRCisusedPositiveacknowledgment(ACK)Negativeacknowledgment(NAK)ErrorcontrolmechanismsStop-and-waitARQ(AutomaticRepeatRequest)Go-back-NARQSelective-rejectARQPiggybackedacknowledgment,-9-,Stop-and-WaitARQ,BelongtoIdleRQ(Fredpp.170)Basedonstop-and-waitflowcontrolExample:pp.210figure7.8Note1:framesequence0,1Note2:framelosstimeoutLinkUtilization,-10-,Go-Back-NARQ,BelongtocontinuesARQBasedonslidingwindowflowcontrolAlgorithm:pp.209-pp.211ExampleinnextslideIfsequencenumberfield=nbits,thenwindowsize=2n1(why?)LinkUtilization,-11-,AnExampleofGo-back-NARQ,-12-,Selective-RejectARQ,BelongtocontinuesARQBasedonslidingwindowflowcontrolAlgorithm:onlyre-transmittingtheframewithNegativeacknowledgement(SREJ)TimeoutlossExampleinnextslideIfsequencenumberfield=nbits,thenwindowsize=2n-1(why?)LinkUtilization,-13-,AnExampleofSelective-RejectARQ,-14-,DataLinkProtocols,High-LevelDataLinkControl(HDLC)HDLCisthebasisformanyotherimportantdatalinkcontrolprotocolsISO3009,ISO4335LinkAccessProcedure,Balanced(LAPB)LAPBwasissuedbyITU-TX.25packet-switchingnetworkinterfacestandard,itprovidesp-t-plinkcontrolbetweenausersystemandapacket-switchingnetworknodeLinkAccessProcedure,D-Channel(LAPD)LAPDwasissuedbyITU-TaspartofitssetofrecommendationsonISDNLAPDprovidesdatalinkcontroloverDchannel,-15-,DataLinkProtocols(cont),LogicalLinkControl(LLC)LLCispartofIEEE802familyofstandardsLLCcontrolthelinkoperationoveraLANLinkcontrolfunctionsinthecaseofLLCaredividedbetweentwolayers:LLCandMAC(MediaAccessControl)layersUseCRC-32FrameRelay(willbeexplainedinClass13)AsynchronousTransferMode(ATM)(willbeexplainedinClass13),-16-,Multiplexing,WhatisMultiplexing?MultiplexingTypesFrequencyDivisionMultiplexing(FDM)TimeDivisionMultiplexing(TDM)SynchronousTDMAsynchronous(Statistical)TDMCodeDivisionMultiplexing(CDM),-17-,FDMv.s.TDM,-18-,FDMSystem,SeparatedFrequencyBandUn-shareableChannelNarrowBandChannelSimultaneouslyTransmissionCable-TV,-19-,SynchronousTDM,SharedFrequencyBandUn-shareableTime-slotFixedTime-slotallocationDigitalCarrierSystem,ISDNandTelephoneNetwork,-20-,AnExampleofSynchronousTDM,-21-,DigitalCarrierSystems,-22-,DS-1TransmissionFormat,-23-,ISDNPrimaryAccessFrameFormats,-24-,SynchronousTDMv.s.StatisticalTDM,-25-,s1(t),s2(t),s(t)=s1(t)+s2(t),d1(t)+c1(t)s2(t),c2(t)s1(t)+d2(t),LPF,LPF,SimplifiedSchemeofCDMA(uplink),-26-,DigitalSubscriberLine,AsynchronousDigitalSubscriberLine(ADSL)Provideshigh-speeddigitaldataratetransmissionoverordinarytelephonewireUsesFDMtoexploitthe1-MHzcapacityoftwistedpairEachcarrier(frequency)isuseQAM(ASK+PSK)analogsignalingtechniqueHighDataRateDigitalSubscriberLine(HDSL)Tocopetheproblemsofhighbandwidth(1.5MHz)andshortdistance(1km)inT1lineHDSLuses2B1Qcodingschemetoprovideadatarateofupto2Mbpsovertwotwistedpairlineswithinabandwidthabout196kHzandenablesdistancerange3.7km.,-27-,DigitalSubscriberLine(cont),SignalLineDigitalSubscriberLine(SDSL)Usesonlyonetwistedpairline.Echocancellationisusedtoachievefull-duplextransmissionoverasignalpairVeryHighDataRateDigitalSubscriberLi