TheNetworkLayer–Part2ContentsIPForwardingIntroductiontoRoutingStaticRouting,DynamicRoutingTheOptimalityPrinciple,ShortestPathRoutingRoutingAlgorithms:FloodingDistanceVectorRouting,LinkStateRoutingHierarchicalRoutingBroadcastRouting,MulticastRoutingroutingdaemonUDPTCPICMProutecommandnetstatcommandIPoutput:calculatenexthoprouter(ifnecessary)ourpacket(oneofourIPaddressesorbroadcastaddress)?processIPoptionsIPinputqueueroutingtableIPlayerNetworkinterfacessourceroutingforwarddatagram(ifforwardingenabled)ICMPredirectsroutingtableupdatesfromadjacentroutersnoyesProcessingdoneattheIPlayerExtractedfromTCP/IPIllustrated,Volume1,byW.RichardStevensIPForwardingTheIPlayerhasaroutingtableinmemorythatitsearcheseachtimeitreceivesadatagramtosend.Eachentryintheroutingtablecontainsthefollowinginfo.:DestinationIPaddress:hostaddressoranetworkaddressIPaddressofanext-hoprouter,ortheIPaddressofadirectlyconnectednetworkFlags:specifiesthetypeoftheDestinationIPaddress,thetypeofnext-hoprouterSpecificationofwhichnetworkinterfacethedatagramshouldbepassedfortransmissionIPForwardingForahost:IPdatagramissentdirectlytothedestination,ifthedestinationisdirectlyconnectedtothehost(e.g.,apoint-to-pointlink)oronasharednetwork(e.g.,Ethernetortokenring);Otherwise,thehostsendsthedatagramtoadefaultrouter.IPForwardingIPForwardingperformsthefollowingactions:SearchtheroutingtableforanentrythatmatchesthecompletedestinationIPaddress(matchingnetworkIDandhostID).Point-to-pointlinksarefoundhere,forexample.SearchtheroutingtableforanentrythatmatchesjustthedestinationnetworkID.AllthehostsonalocalEthernet,forexample,arehandledwitharoutingtableentryofthistype.Searchtheroutingtableforanentrylabeled"default."Iffound,sendthepackettotheindicatednext-hoprouter.Ifnoneofthestepsworks,thedatagramisundeliverable.gatewayEthernet,subnet140.252.1netbsunbsdimodemmodem.1.183nexthop=(default)SLIP.1.29Ethernet,5Figure3.4Initialpathofdatagramfrombsdito()linkhdrIPhdrdestIP=destEnet=Enetof3nexthop=3(default)nexthop=83(default)IPhdrdestIP=destIP=destEnet=EnetoflinkhdrIPhdrnexthop=(default).1.4InternetU:Therouteisup.

G:Therouteistoagateway(router).Ifthisflagisnotset,thedestinationisdirectlyconnected.

H:Therouteistoahost,thatis,thedestinationisacompletehostaddress.Ifthisflagisnotset,therouteistoanetwork,andthedestinationisanetworkaddress:anetID,oracombinationofanetIDandasubnetID.

D:Theroutewascreatedbyaredirect

M:Theroutewasmodifiedbyaredirectemd0250434U42emd000UG3defaultlo001UHemd000UGH55interfaceUseRefcntFlagsGatewayDestinationRoutingtablessvr4%netstat-rnRouting——IntroductionTheroutingalgorithmisthatpartofthenetworklayersoftwareresponsiblefordecidingwhichoutputlineanincomingpacketshouldbetransmittedon.Routing:makingthedecisionwhichroutestouseForwarding:handleseachpacketasitarrives,lookinguptheoutgoinglinetouseforitintheroutingtablesCertainpropertiesaredesirableinaroutingalgorithm:correctness,simplicity,robustness,stability,fairness,andoptimality.Routing——Introduction(2)Conflictbetweenfairnessandoptimality.Routing——Introduction(3)ClassificationoftheroutingalgorithmsNonadaptivealgorithms:donotbasetheirroutingdecisionsonmeasurementsorestimatesofthecurrenttrafficandtopology,sometimescalledstaticrouting

Adaptivealgorithms:changetheirroutingdecisionstoreflectchangesinthetopology,andusuallythetrafficaswell.sometimescalleddynamic

routingTheOptimalityPrinciple(a)Asubnet.(b)AsinktreeforrouterB.OptimalityPrinciple：IfrouterJisontheoptimalpathfromrouterItorouterK,thentheoptimalpathfromJtoKalsofallsalongthesameroute.ShortestPathRoutingThefirst5stepsusedincomputingtheshortestpathfromAtoD.

Thearrowsindicatetheworkingnode.Dijkstra'salgorithmtocomputetheshortestpaththroughagraph.5-8top

Dijkstra'salgorithmtocomputetheshortestpaththroughagraph.5-8bottomDistanceVectorRoutingAsubnet.InputfromA,I,H,K,andthenewroutingtableforJ.SupposethatJhasmeasuredorestimateditsdelaytoitsneighbors,A,I,H,andKas8,10,12,and6msec,respectivelyDistanceVectorRouting(2)Thecount-to-infinityproblem.LinkStateRoutingEachroutermustdothefollowing:Discoveritsneighborsandlearntheirnetworkaddresses:Whenarouterisbooted,itsfirstsendsaspecialHELLOpacketoneachpoint-to-pointlinetolearnwhoitsneighborsare.Therouterontheotherendisexpectedtosendbackareplytellingwhoitis.MeasurethedelayorcosttoeachofitsneighborsConstructapackettellingallithasjustlearnedSendthispackettoallotherrouters.ComputetheshortestpathtoeveryotherrouterIneffect,thecompletetopologyandalldelaysareexperimentallymeasuredanddistributedtoeveryrouter.ThenDijkstra’salgorithmcanberuntofindtheshortestpathtoeveryotherrouter.LearningabouttheNeighbors(a)NineroutersandaLAN.(b)Agraphmodelof(a).BuildingLinkStatePackets(a)Asubnet.(b)Thelinkstatepacketsforthissubnet.DistributingtheLinkStatePacketsThepacketbufferforrouterBinthepreviousslide(Fig.5-13).HierarchicalRoutingBroadcastRoutingVariousmethodforbroadcastrouting:thesourcesimplysendadistinctpackettoeachdestination;Floodingisanotherobviouscandidate;multidestinationrouting:eachpacketcontainseitheralistofdestinationsorabitmapindicatingthedesireddestinationsspanningtree:makesexplicituseofthesinktreefortherouterinitiatingthebroadcast-oranyotherconvenientspanningtreeforthatmatterIfeachrouterknowswhichofitslinesbelongtothespanningtree,itcancopyanincomingbroadcastpacketontoallthespanningtreelinesexcepttheoneitarrivedonreversepathforwarding:BroadcastRoutingReversepathforwarding.(a)Asubnet.(b)aSinktree.(c)Thetreebuiltbyreversepathforwarding.MulticastRoutingMulticasting：sendingamessagetosuchagroupMulticastRouting:routingalgori