哈尔滨工业大学-深圳-高级计算机网络-2017-习题集

1ACHANNELHASABITRATEOF4KBPSANDAPROPAGATIONDELAYOF20MSECFORWHATRANGEOFFRAMESIZESDOESSTOPANDWAITGIVEANEFFICIENCYOFATLEAST50ANSWER发送一帧的时间等于信道的传播延迟的2倍，信道的利用率为50，所以，在帧长满足发送时间大于延迟时间的2倍是，效率将会高于50。由于4KBPS4000BPS故40002000012160BIT只有在帧长不小于160BIT时，停止等待协议的效率才会至少是50。解此题可供参考的公式有两个，下面这两种情况下都可以得到答案一个是效率其中P是传输一帧所需要的时间，T是端到端传送时延。所以可以由2250，解出帧N160BIT；二是中第42张中讲到的公式，公式综合考虑了多种因素，信道丢失率，帧头的大小，以及ACK的发送时间。在不考虑数据帧的处理时间TPROC和NNN/ACK发送时间的情况下，我们可以推出帧的最小大小为160BIT。答案详情参看上次文档。作业中得到错误答案有两个（1）N80BIT得出此答案的同学没有弄清楚停等协议，在停等协议公式1分母下面的2T是往返时间，而不是T。（2）160KBIT，单位换算错误。我可以负责任的告诉你没有哪个网络里面帧能够有十几万比特大小的，以太网里最大帧不过1526字节。2IMAGINEASLIDINGWINDOWPROTOCOLUSINGSOMANYBITSFORSEQUENCENUMBERSTHATWRAPAROUNDNEVEROCCURSWHATRELATIONSMUSTHOLDAMONGTHEFOURWINDOWEDGESANDTHEWINDOWSIZE,WHICHISCONSTANTANDTHESAMEFORBOTHTHESENDERANDTHERECEIVERANSWER假设发送者的窗口为（S1，SN）,接受者的窗口为（R1，RN），窗口大小为W，则需满足0SL但一定有RL1时，信道总是过载的，因此在这里信道是过载的。4WHATISTHEBAUDRATEOFTHESTANDARD10MBPSETHERNET答以太网使用曼彻斯特编码，意味着发送每一位都有两个信号周期，标准以太网的数据率为10MB/S，一次波特率是数据率的两倍，为20MBAUD。5A1KMLONG,10MBPSCSMA/CDLANNOT8023HASAPROPAGATIONSPEEDOF200M/SECREPEATERSARENOTALLOWEDINTHISSYSTEMDATAFRAMESARE256BITSLONG,INCLUDING32BITSOFHEADER,CHECKSUM,ANDOTHEROVERHEADTHEFIRSTBITSLOTAFTERASUCCESSFULTRANSMISSIONISRESERVEDFORTHERECEIVERTOCAPTURETHECHANNELINORDERTOSENDA32BITACKNOWLEDGEMENTFRAMEWHATISTHEEFFECTIVEDATARATE,EXCLUDINGOVERHEAD,ASSUMINGTHATTHEREARENOCOLLISIONS答依题意知道一公里的铜电缆中单程的传播时间为1、2000005USEC，往返的时间为2T10USEC，我们知道，一次完整的传输分为六步，发送者侦听铜电缆的时间为10USEC，若线路可用发送数据帧传输时间为256BITS、10MPS256USEC，数据帧最后一位到达时传播的延迟为50USEC，接听者侦听铜电缆的时间为10USEC，若线路可用接听者发送确认帧所用的时间为32USEC，确认帧最后一位到达时的传播延迟为50USEC，总共588SEC,在这期间发送了224BITS的数据，所以数据率为38MPS。6TWOCSMA/CDSTATIONSAREEACHTRYINGTOTRANSMITLONGMULTIFRAMEFILESAFTEREACHFRAMEISSENT,THEYCONTENDFORTHECHANNEL,USINGTHEBINARYEXPONENTIALBACKOFFALGORITHMWHATISTHEPROBABILITYTHATTHECONTENTIONENDSONROUNDK,ANDWHATISTHEMEANNUMBEROFROUNDSPERCONTENTIONPERIOD答把获得通道的尝试从1开始编号。第I次尝试分布在2I1个时隙中。因此，I次尝试碰撞的概率是2I1，开头K1次尝试失败，紧接着第K次尝试成功的概率是PK（12（K1）20212K2（12（K1）2K1K2/2所以每个竞争周期的平均竞争次数是KPKK1,2,38ANIPPACKETTOBETRANSMITTEDBYETHERNETIS60BYTESLONG,INCLUDINGALLITSHEADERSIFLLCISNOTINUSE,ISPADDINGNEEDEDINTHEETHERNETFRAME,ANDIFSO,HOWMANYBYTES答最小的以太帧是64BYTES，包括了以太帧头部的二者地址、类型/长度域、校验和。因为头部域占用18BYTES报文是60BYTES，总的帧长度是78BYTES,已经超过了64BYTE的最小限制。因此，不需要填补。1DESCRIBEDISTANCEVECTORDVALGORITHMDISCUSSTHEFEATUREOFTHEDVROUTINGALGORITHMSOLUTION1THEBASICIDEAOFDVALGORITHMEACHNODEXBEGINSWITHDXY,ANESTIMATEOFTHECOSTOFTHELEASTCOSTPATHFROMITSELFTONODEY,FORALLNODESINNLETDXDXYYINNBENODEXSDISTANCEVECTOR,WHICHISTHEVECTOROFCOSTESTIMATESFROMXTOALLOTHERNODES,Y,INNWITHTHEDVALGORITHM,EACHNODEXMAINTAINSTHEFOLLOWINGROUTINGINFORMATIONFOREACHNEIGHBORV,THECOSTCX,VFROMXTODIRECTLYATTACHEDNEIGHBORVNODEXSDISTANCEVECTOR,THATIS,DXDXYYINN,CONTAININGXSESTIMATEOFITSCOSTTOALLDESTINATIONS,Y,INNTHEDISTANCEVECTORSOFEACHOFITSNEIGHBORS,THATIS,DVDVYYINNFOREACHNEIGHBORVOFXINTHEDISTRIBUTED,ASYNCHRONOUSALGORITHM,FROMTIMETOTIME,EACHNODESENDSACOPYOFITSDISTANCEVECTORTOEACHOFITSNEIGHBORSWHENANODEXRECEIVESANEWDISTANCEVECTORFROMANYOFITSNEIGHBORSV,ITSAVESVSDISTANCEVECTOR,ANDTHENUSESTHEBELLMANFORDEQUATIONTOUPDATEITSOWNDISTANCEVECTORASFOLLOWSDXY_MINVCX,VDVYFOREACHNODEYINNIFNODEXSDISTANCEVECTORHASCHANGEDASARESULTOFTHISUPDATESTEP,NODEXWILLTHENSENDITSUPDATEDDISTANCEVECTORTOEACHOFITSNEIGHBORS,WHICHCANINTURNUPDATETHEIROWNDISTANCEVECTORSMIRACULOUSLYENOUGH,ASLONGASALLTHENODESCONTINUETOEXCHANGETHEIRDISTANCEVECTORSINANASYNCHRONOUSFASHION,EACHCOSTESTIMATEDXYCONVERGESTODXY,THEACTUALCOSTOFTHELEASTCOSTPATHFROMNODEXTONODEY2THEFEATUREOFTHEDVROUTINGALGORITHMTHEDISTANCEVECTORDVALGORITHMISITERATIVE,ASYNCHRONOUS,ANDDISTRIBUTEDITISDISTRIBUTEDINTHATEACHNODERECEIVESSOMEINFORMATIONFROMONEORMOREOFITSDIRECTLYATTACHEDNEIGHBORS,PERFORMSACALCULATION,ANDTHENDISTRIBUTESTHERESULTSOFITSCALCULATIONBACKTOITSNEIGHBORSITISITERATIVEINTHATTHISPROCESSCONTINUESONUNTILNOMOREINFORMATIONISEXCHANGEDBETWEENNEIGHBORSINTERESTINGLY,THEALGORITHMISALSOSELFTERMINATINGTHEREISNOSIGNALTHATTHECOMPUTATIONSHOULDSTOPITJUSTSTOPSTHEALGORITHMISASYNCHRONOUSINTHATITDOESNOTREQUIREALLOFTHENODESTOOPERATEINLOCKSTEPWITHEACHOTHER2CONSIDERACONFIGURATIONINWHICHPACKETSARESENTFROMCOMPUTERSONALANTOSYSTEMSONOTHERNETWORKSALLOFTHESEPACKETSMUSTPASSTHROUGHAROUTERTHATCONNECTSTHELANTOAWIDEAREANETWORKANDHENCETOTHEOUTSIDEWORLDLETUSLOOKATTHETRAFFICFROMTHELANTHROUGHTHEROUTERPACKETSARRIVEWITHAMEANARRIVALRATEOF5PERSECONDTHEAVERAGEPACKETLENGTHIS144BYTES,ANDITISASSUMEDTHATPACKETLENGTHISEXPONENTIALLYDISTRIBUTEDLINESPEEDFROMTHEROUTERTOTHEWIDEAREANETWORKIS9600BPSTHEFOLLOWINGQUESTIONSAREASKEDAWHATISTHEUTILIZATIONOFTHELINKOFTHEROUTERBWHATISTHEMEANRESIDENCETIMEINTHEROUTERCHOWMANYPACKETSAREINTHEROUTER,INCLUDINGTHOSEWAITINGFORTRANSMISSIONANDTHEONECURRENTLYBEINGTRANSMITTEDIFANY,ONTHEAVERAGESOLUTIONAMEANARRIVALRATETHROUGHPUTX5PACKETS/SECAVERAGESERVICETIMES144BYTES/PACKET8BITS/BYTE/9600BPS012SEC/PACKETUTILIZATIONTIMETHEROUTERISBUSYUXS5PACKETS/SEC012SEC/PACKET06BTHEMEANRESIDENCETIMEISTS/1U012SEC/PACKET/10603SEC/PACKETCNUMBEROFPACKETSINTHEROUTERISENU/1U15PACKETS2CONSIDERTHEARRIVALTRAFFICCHARACTERIZEDBYATOKENBUCKETWITHPARAMETERSAVERAGERATE1MBPS,MMAXIMUMOUTPUTRATE2MBPS,ANDCTOKENCAPACITY200KBWHATISTHEMINIMUMRATERTHATNEEDSTOBEALLOCATEDBYAROUTERINORDERTOGUARANTEEADELAYNOLARGERTHAN50MSSOLUTIONWEBUILDTHEEQUATIONACCORDINGTOTHERULETHEBITSFLOWEDINTHEROUTERAREEQUALTOTHEBITSFLOWEDOUTTHEROUTERLETSBEBURSTLENGTH,THEMAXIMUMACCUMULATIVEAMOUNTOFARRIVALTRAFFICTOTHEROUTERISCSMSWEGETSC/MWHENTHEROUTERDEALTHEARRIVALTRAFFICATTHEMINIMUMRATERWITHADELAYNOLARGERTHAN50MS,LETD50MSANDTHEEQUATIONISMSRSDSO,/20/21041605/52MSCMBPSKBPSMBMPSDSS3DESCRIBETHEBORDERGATEWAYPROTOCOLBGPANDDISCUSSHOWAPACKETWOULDBETRANSMITTEDAMONGDIFFERENTAUTONOMOUSSYSTEMASSOLUTIONBORDERGATEWAYPROTOCOLVERSION4BGP4WEJUSTLEARNEDHOWISPSUSERIPANDOSPFTODETERMINEOPTIMALPATHSFORSOURCEDESTINATIONPAIRSTHATAREINTERNALTOTHESAMEASLETSNOWEXAMINEHOWPATHSAREDETERMINEDFORSOURCEDESTINATIONPAIRSTHATSPANMULTIPLEASSBGPPROVIDESEACHASAMEANSTO1OBTAINSUBNETREACHABILITYINFORMATIONFROMNEIGHBORINGASS2PROPAGATETHEREACHABILITYINFORMATIONTOALLROUTERSINTERNALTOTHEAS3DETERMINE“GOOD”ROUTESTOSUBNETSBASEDONTHEREACHABILITYINFORMATIONANDONASPOLICY4SUPPOSETHATFRAMESARE1250BYTESLONGINCLUDING25BYTESOFHEADALSOASSUMETHATACKFRAMEARE25BYTESLONGCALCULATETHEEFFICIENCYOFSTOPANDWAITARQINASYSTEMTHATTRANSMITSATR1MBPSANDWITHREACTIONTIMEOF1MSFORCHANNELSWITHABITERROROF106,105,104SOLUTIONFROMTHEABOVEFIGUREANDCONDITION,WEKNOWTHETOTALTIMETOTRANSMIT1FRAMEIST02TPROPTPROCTFTAHERE,2TPROPTPROCISTHEREACTIONTIMEOF1MS,TFISTHETIMETOTRANSMITTHEFAMESNF1250BYTESWITHTHEHEADNH25BYTESANDTAISTHETIMETOTRANSMITTHEACKFRAMENA25BYTESANDTHEUSEFULSIZEOFTHEFRAMEISNFNHMOREOVER,THEPROBABILITYOFTRANSMITTINGAFRAMEWITHOUTERRORSIS1PESOTHETRANSMISSIONEFFICIENCYISASFOLLOWS0/11122/12508/10EFFHFHEEEPROCPROFAFHFHEEPROCPROFAPROCRPFAFHEREACTIONFARNTNPPPRRTTTTTNTRNBYSITBYPRSM125/718EEPEITSWHENPE106,8750,WHENPE105,8750,WHENPE104,87495DESCRIBETHETCPCONGESTIONCONTROLSCHEMEDERIVETHEDELAYMODELINGFORTCPTRAFFICINFIXEDCONGESTIONWINDOWWHENWS/R10ACTIVELESSTHAN0004QHOWDIDWEGETVALUE000044CARAVANANALOGYCARS“PROPAGATE”AT100KM/HRTOLLBOOTHTAKES12SECTOSERVICEACARTRANSMISSIONTIMECARBITCARAVANPACKETQHOWLONGUNTILCARAVANISLINEDUPBEFORE2NDTOLLBOOTHTIMETO“PUSH”ENTIRECARAVANTHROUGHTOLLBOOTHONTOHIGHWAY1210120SECTIMEFORLASTCARTOPROPAGATEFROM1STTO2NDTOLLBOTH100KM/100KM/HR1HRA62MINUTESCARSNOW“PROPAGATE”AT1000KM/HRTOLLBOOTHNOWTAKES1MINTOSERVICEACARQWILLCARSARRIVETO2NDBOOTHBEFOREALLCARSSERVICEDAT1STBOOTHYESAFTER7MIN,1STCARAT2NDBOOTHAND3CARSSTILLAT1STBOOTH1STBITOFPACKETCANARRIVEAT2NDROUTERBEFOREPACKETISFULLYTRANSMITTEDAT1STROUTERSEEETHERNETAPPLETATAWLWEBSITE56COULDTHECONGESTIONPROBLEMBESOLVEDWITHALARGEBUFFERSPACETOOLITTLEMEMORYTOOMUCHTRAFFICWILLLEADTOBUFFEROVERFLOWANDPACKETLOSSTOOMUCHMEMORYTHEQUEUESANDTHEDELAYSCANGETSOLONGTHATBYTHETIMETHEPACKETSCOMEOUTOFTHESWITCH,MOSTOFTHEMHAVEALREADYTIMEDOUTANDHAVEBEENRETRANSMITTEDBYHIGHERLAYERSPACKETSORTHEIRRETRANSMISSIONSHAVETOBEDROPPEDAFTERTHEYHAVECONSUMEDPRECIOUSNETWORKRESOURCESTOOMUCHMEMORYINTHEINTERMEDIATENODESISASHARMFULASTOOLITTLEMEMORY7COULDTHECONGESTIONPROBLEMBESOLVEDWITHHIGHSPEEDLINKSINTRODUCINGHIGHSPEEDLINKSWITHOUTPROPERCONGESTIONCONTROLCANLEADTOREDUCEDPERFORMANCETHESAMESPEEDATHETIMETOTRANSFERAPARTICULARFILEWASFIVEMINUTESBTHELINKBETWEENTHEFIRSTTWONODESWASREPLACEBYAFAST1MBITSLINK,THETRANSFERTIMEINCREASEDTO20MINUTESWITHTHEHIGHSPEEDLINK,THEARRIVALRATETOTHEFIRSTROUTERBECAMEMUCHHIGHERTHANTHEDEPARTURERATE,LEADINGTOLONGQUEUES,BUFFEROVERFLOWS,ANDPACKETLOSSESTHATCAUSEDTHETRANSFERTIMETOINCREASETHEPROTOCOLSHAVETOBEDESIGNEDSPECIFICALLYTOENSURETHATTHISINCREASINGRANGEOFLINKSPEEDSDOESNOTDEGRADETHEPERFORMANCE8COULDTHECONGESTIONPROBLEMBESOLVEDWITHHIGHSPEEDPROCESSORSSIMILARTOTHATFORLINKSINTRODUCTIONOFAHIGHSPEEDPROCESSORINANEXISTINGNETWORKMAYINCREASETHEMISMATCHOFSPEEDSANDTHECHANCESOFCONGESTIONINTRODUCINGHIGHSPEEDLINKSWITHOUTPROPERSCHEMESCONGESTIONOCCURSEVENIFALLLINKSANDPROCESSORSAREOFTHESAMESPEEDANEXAMPLEOFTHEBALANCEDCONFIGURATIONASSUMEALLPROCESSORSANDLINKSHAVEATHROUGHPUTCAPACITYOF1GBITSASIMULTANEOUSTRANSFEROFDATAFROMNODESAANDBTONODECCANLEADTOATOTALINPUTRATEOF2GBITSPERSECONDATTHEROUTERRWHILETHEOUTPUTRATEISONLY1GBITSPERSECOND,THEREBY,CAUSINGCONGESTION6SOLUTIONSCONGESTIONINNETWORKSISADYNAMICPROBLEMITCANNOTBESOLVEDWITHSTATICSOLUTIONSALONEWENEEDPROTOCOLDESIGNSTHATPROTECTNETWORKSINTHEEVENTOFCONGESTIONTHEEXPLOSIONOFHIGHSPEEDNETWORKSHASLEDTOMOREUNBALANCEDNETWORKSTHATARECAUSINGCONGESTIONINPARTICULAR,PACKETLOSSDUETOBUFFERSHORTAGEISASYMPTOMNOTACAUSEOFCONGESTIONSOLUTIONPROPERPROTOCOLSANDMECHANISMSDESIGN,EGADMISSIONCONTROL,SCHEDULING,ETAL7“ENDTOEND”AND“POINTTOPOINT”AENDTOENDCOMMUNICATIONSIDATACOMMUNICATIONSONAPATHBETWEENTHESO