搜索
Problem61.Theroutingfunctionattemptstofindtheleast-costroutethroughthenetwork,withcostbasedonnumberofhops,expecteddelay,orothermetrics2.Adaptiveroutingalgorithmstypicallyrelyontheexchangeofinformationabouttrafficconditionsamongnodes.3.Routingdecisionsaremadeonthebasisofsomeperformancecriterion.Twokeycharacteristicsofthedecisionarethetimeandplacethatthedecisionismade.4.Decisiontimeisdeterminedbywhethertheroutingdecisionismadeonapacketorvirtualcircuitbasis.Whentheinternaloperationofthenetworkisdatagram,aroutingdecisionismadeindividuallyforeachpacket.Forinternalvirtualcircuitoperation,aroutingdecisionismadeatthetimethevirtualcircuitisestablished.5.Thetermdecisionplacereferstowhichnodeornodesinthenetworkareresponsiblefortheroutingdecision.Fordistributedrouting,inwhicheachnodehastheresponsibilityofselectinganoutputlinkforroutingpacketsastheyarrive.Forcentralizedrouting,thedecisionismadebysomedesignatednode,suchasanetworkcontrolcenter.6.Theroutingalgorithmisthatpartofthenetworklayersoftwareresponsiblefordecidingwhichoutputlineanincomingpacketshouldbetransmittedon.7.Arouterhastwoprocessesinsideit.Oneofthemhandleseachpacketasitarrives,lookinguptheoutgoinglinetouseforitintheroutingtables.Thisprocessisforwarding.Theotherprocessisresponsibleforfillinginandupdatingtheroutingtables.Thatiswheretheroutingalgorithmcomesintoplay.8.Nonadaptivealgorithmsdonotbasetheirroutingdecisionsonmeasurementsorestimatesofthecurrenttrafficandtopology.Instead,thechoiceoftheroutetouseiscomputedinadvance,off-line,anddownloadedtotherouterswhenthenetworkisbooted.Thisprocedureissometimescalledstaticrouting.9.Adaptivealgorithms,changetheirroutingdecisionstoreflectchangesinthetopology,andusuallythetrafficaswell.10.Floodingisthetechniquerequiresnonetworkinformationwhatsoeverandworksasfollows.Apacketissentbyasourcenodetoeveryoneofitsneighbors.Ateachnode,anincomingpacketisretransmittedonalloutgoinglinksexceptforthelinkonwhichitarrived.11.Dijkstra'salgorithmisagraphsearchalgorithmthatsolvesthesingle-sourceshortestpathproblemforagraphwithnon-negativeedgepathcosts,producingashortestpathtree.Theshortestpathalgorithmiswidelyusedinnetworkroutingprotocols,mostnotablyIS-ISandOSPF(OpenShortestPathFirst).12.TheBellman-Fordalgorithmcanbestatedasfollows:Findtheshortestpathsfromagivensourcenodesubjecttotheconstraintthatthepathscontainatmostonelink,thenfindtheshortestpathswithaconstraintofpathsofatmosttwolinks,andsoon.13.Theroutersinaninternetareresponsibleforreceivingandforwardingpacketsthroughtheinterconnectedsetofnetworks.Eachroutermakesroutingdecisionbasedonknowledgeofthetopologyandtraffic/delayconditionsoftheinternet.14.RoutinginformationisInformationaboutthetopologyanddelaysoftheinternet.RoutingalgorithmisThealgorithmusedtomakearoutingdecisionforaparticulardatagram,basedoncurrentroutinginformation.15.AnASisasetofroutersandnetworksmanagedbyasingleorganization.AnASconsistsofagroupofroutersexchanginginformationviaacommonroutingprotocol.16.Interiorrouterprotocol(IRP)isusedtopassroutinginformationbetweenrouterswithinanAS.Exteriorrouterprotocol(ERP)isusedtopassroutinginformationbetweenroutersindifferentAss.17.Withinanautonomoussystem,IGPsoftwareusesaroutingmetrictochooseanoptimalpatheachdestination.EGPsoftwarefindsapatheachdestination,butcannotfindanoptimalpathbecauseitcannotcompareroutingmetricsfrommultipleautonomoussystems.18.Internetroutingprotocolsemployoneofthreeapproachestogatheringandusingroutinginformation:distance-vectorrouting,link-staterouting,andpath-vectorrouting.19.Distance-vectorroutingrequiresthateachnode(routerorhostthatimplementstheroutingprotocol)exchangeinformationwithitsneighboringnodes.Twonodesaresaidtobeneighborsiftheyarebothdirectlyconnectedtothesamenetwork.ThefirstgenerationroutingalgorithmforARPANETusesthisapproach.20.Path-vectorrouting,istodispensewithroutingmetricsandsimplyprovideinformationaboutwhichnetworkscanbereachedbyagivenrouterandtheASsthatmustbecrossedtogetthere.21.Link-stateroutingisdesignedtoovercomethedrawbacksofdistance-vectorrouting.Whenarouterisinitialized,itdeterminesthelinkcostoneachofitsnetworkinterfaces.Therouterthenadvertisesthissetoflinkcoststoallotherroutersintheinternettopology,notjustneighboringrouters.Becausetherouterhasarepresentationoftheentirenetwork,itdoesnotuseadistributedversionofaroutingalgorithm,asisdoneindistance-vectorrouting.Rather,theroutercanuseanyroutingalgorithmtodeterminetheshortestpaths.Inpractice,Dijkstra’salgorithmisused.TheOpenShortestPathFirst(OSPF)isanexampleofaroutingprotocolthatuseslink-staterouting.22.TheBorderGatewayProtocol(BGP)wasdevelopedforuseinconjunctionwithinternetsthatemploytheTCP/IPsuite,althoughtheconceptsareapplicabletoanyinternet.BGPhasbecomethepreferredexteriorrouterprotocolfortheInternet.