计算机网路基础第三章习题

2.Thefollowingcharacterencodingisusedinadatalinkprotocol:A:01000111B:11100011FLAG:01111110ESC:11100000Showthebitsequencetransmitted(inbinary)forthefour-characterframeABESCFLAGwheneachofthefollowingframingmethodsisused:(a)Bytecount.(b)Flagbyteswithbytestuffing.(c)Startingandendingflagbyteswithbitstuffing.(a)000001000100011111100011111000001111110(b)0111111001000111111000111110000011100000111000000111111001111110(c)0111111001000111110100011111000000011111010011111107.Inthetextbook,theauthorsshowthatforachannelwitherrorrate10^-6,errordetectingbasedretransmissionismoreefficientthanerrorcorrecting(see27thslide).Pleasegiverangesofthechannelerrorrateinwhicherrorcorrectingismoreefficient,consideringonlyforblocks(1000bits)withatmost1biterror.Supposetheerrorrateisx.N=1/(x*1000);Forerrorcorrecting,itneed10*Nbitofcheckbits.Forerrordetectingitneed2001bit10*N2001,10/(x*1000)2001,x=4.9*10^-68.Hammingcodeisaneffectivewayforerrorcorrecting.Showthatthenumberofcheckbits(i.e.r)intheHammingcodesdescribedinthetextbook(e.g.,Fig.3-6)(almost)achievesthelowboundofEq(3-1).Eq(3-1):(m+r+1)≤2^rInfigure3-6,m+r=11So12≤2^r,r=4.Sothenumberofcheckbitsis4.9.Supposeyouhavethefollowing12-bitmessage:010100111111(a)Numberingbitsfromrighttoleft(ieleast-significantbitontheright),insertcheckbitsaccordingtotoHamming’s1-biterrorcorrectionsystem.Indicatewhichbitsarecheckbitsandwhicharemessagebits.(b)Hamming’sschemeonlycorrects1-biterrors.Sinceit’sadistance3code,itcouldalsobeusedtodetect2-biterrors.Describea3-biterror(3*1-biterrors)intheabovecodewordaffectingonlymessagebits(notcheckbits)thatwouldbeundetected(andofcourseuncorrected).Besuretodescribehowandwhythealgorithmfails.(a)cherkbitswillbeinsertinthe124816.messagebitsare3567910111213141517.(b)todetect3-biterror,thehammingdistanceneedtobe4.tocorrect3-biterror，thehammingdistanceneedtobe7.Sothealgorithmfails.16.Consideranoriginalframe110111011011.Thegeneratorpolynomialx^4+x+1,showtheconvertedframeafterappendingtheCRC.Theremainderisx^2+x+1.22.A3000-km-longT1trunkisusedtotransmit64-byteframes.Howmanybitsshouldthesequencenumbersbeforprotocol5andprotocol6respectively?Thepropagationspeedis6usec/km.T1:1.536Mbps.Sotransmit64-byteframesneed0.3ms.Thepropogationtimeis3000*6=18000usec=18ms.Start-Arrive：18+0.3=18.3msAcknowledgement：18msTime=18+18.3=36.3ms36.3/0.3=121frames[tofillthepipe]So7-bitsequencenumbersareneeded.32.Framesof1000bitsaresentovera1-Mbpschannelusingageostationarysatellitewhosepropagationtimefromtheearthis270msec.Acknowledgementsarealwayspiggybackedontodataframes.Theheadersareveryshort.Three-bitsequencenumbersareused.Whatisthemaximumachievablechannelutilizationfor(a)Stop-and-wait?(b)Protocol5?(c)Protocol6?1000*1mbps=1s.start:t=0msecthefirstframehasbeenfullytransmitted:t=1msec,thefirstframehasfullyarrived:t=271msecthefirstframe'sacknowledgementhasbeenfullysent:t=272msecacknowledgementhasfullyarrived:t=542msecSothecycleis542msec.(a)k=1,efficiency=1/542=0.18%.(b)k=7,efficiency=7/542=1.29%.(c)k=4,efficiency=4/542=0.74%33.Computethefractionoftheusefuldatabandwidthforprotocol6onaheavilyloaded50-kbpssatellitechannelwithdataframesconsistingof40headerand3960databits.Assumethatthesignalpropagationtimefromtheearthtothesatelliteis270msec.ACKframesneveroccur.NAKframesare40bits.Theerrorratefordataframesis1%,andtheerrorrateforNAKframesisnegligible.Thesequencenumbersare3bits.Witha50-kbps8-bitsequencenumbers,thepipeisalwaysfull.Retransmissionsperframe=0.01.Eachgoodframe:40headerbits,1%of4000bits,a40-bitNAKonceevery100frames.Thetotaloverheadis80.4bitsper3960databits,giving80.4/(396080.4)1.99%.