計(jì)算機(jī)網(wǎng)絡(luò)課件

Chapter4-4routingandIProutingroutingandIProuting2/51Chapter4:NetworkLayer4.1Introduction4.2Virtualcircuitanddatagramnetworks4.3What’sinsidearouter4.4IP:InternetProtocolDatagramformatIPv4addressingICMPIPv64.5RoutingalgorithmsLinkstateDistanceVectorHierarchicalrouting4.6RoutingintheInternetRIPOSPFBGP4.7BroadcastandmulticastroutingroutingandIProuting3/51LogicalStructureofInternetAdhocinterconnectionofnetworksNoparticulartopologyVastlydifferentrouter&linkcapacitiesSendpacketsfromsourcetodestinationbyhoppingthroughnetworksRouterconnectonenetworktoanotherDifferentpathstodestinationmayexisthosthostrouterrouterrouterrouterrouterrouterroutingandIProuting4/51GettingtoaDestinationHowdoyougetdrivingdirections?IntersectionsroutersRoadslinks/networksRoadschangeslowlyroutingandIProuting5/51Whatisrouting?R3ABCR1R2R4DEFR5R5FR3ER3DNextHopDestinationDDroutingandIProuting6/51Whatisrouting?R3ABCR1R2R4DEFR5R5FR3ER3DNextHopDestinationDDDD163241DataOptions(ifany)DestinationAddressSourceAddressHeaderChecksumProtocolTTLFragmentOffsetFlagsFragmentIDTotalPacketLengthT.ServiceHLenVer20bytesroutingandIProuting7/51Whatisrouting?ABCR1R2R3R4DEFR5routingandIProuting8/51BridgeroutingandIProuting9/511230111valueinarrivingpacket’sheaderroutingalgorithmlocalforwardingtableheadervalueoutputlink01000101011110013221Interplaybetweenrouting,forwardingroutingandIProuting10/51uyxwvz2213112535Graph:G=(N,E)N=setofrouters={u,v,w,x,y,z}E=setoflinks={(u,v),(u,x),(v,x),(v,w),(x,w),(x,y),(w,y),(w,z),(y,z)}GraphabstractionRemark:GraphabstractionisusefulinothernetworkcontextsExample:P2P,whereNissetofpeersandEissetofTCPconnectionsroutingandIProuting11/51Graphabstraction:costsuyxwvz2213112535c(x,x’)=costoflink(x,x’)-e.g.,c(w,z)=5costcouldalwaysbe1,orinverselyrelatedtobandwidth,orinverselyrelatedtocongestionCostofpath(x1,x2,x3,…,xp)=c(x1,x2)+c(x2,x3)+…+c(xp-1,xp)Question:What’stheleast-costpathbetweenuandz?Routingalgorithm:algorithmthatfindsleast-costpathroutingandIProuting12/51RoutingAlgorithmclassificationGlobalordecentralizedinformation?Global:allroutershavecompletetopology,linkcostinfo“l(fā)inkstate”algorithmsDecentralized:

routerknowsphysically-connectedneighbors,linkcoststoneighborsiterativeprocessofcomputation,exchangeofinfowithneighbors“distancevector”algorithmsStaticordynamic?Static:

routeschangeslowlyovertimeDynamic:

routeschangemorequicklyperiodicupdateinresponsetolinkcostchangesroutingandIProuting13/51Chapter4:NetworkLayer4.1Introduction4.2Virtualcircuitanddatagramnetworks4.3What’sinsidearouter4.4IP:InternetProtocolDatagramformatIPv4addressingICMPIPv64.5RoutingalgorithmsLinkstateDistanceVectorHierarchicalrouting4.6RoutingintheInternetRIPOSPFBGP4.7BroadcastandmulticastroutingroutingandIProuting14/51ALink-StateRoutingAlgorithmDijkstra’salgorithmnettopology,linkcostsknowntoallnodesplishedvia“l(fā)inkstatebroadcast”allnodeshavesameinfocomputesleastcostpathsfromonenode(‘source”)toallothernodesgivesforwardingtableforthatnodeiterative:afterkiterations,knowleastcostpathtokdest.’sNotation:c(x,y):linkcostfromnodextoy;=∞ifnotdirectneighborsD(v):currentvalueofcostofpathfromsourcetodest.vp(v):predecessornodealongpathfromsourcetovN':setofnodeswhoseleastcostpathdefinitivelyknownroutingandIProuting15/51Dijsktra’sAlgorithm1Initialization:

2N'={u}3forallnodesv4ifvadjacenttou5thenD(v)=c(u,v)6elseD(v)=∞

78Loop

9findwnotinN'suchthatD(w)isaminimum10addwtoN'

11updateD(v)forallvadjacenttowandnotinN':12D(v)=min(D(v),D(w)+c(w,v))13/*newcosttoviseitheroldcosttovorknown14shortestpathcosttowpluscostfromwtov*/15untilallnodesinN'

routingandIProuting16/51Dijkstra’salgorithm:exampleStep012345N'uuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)∞2,xD(z),p(z)∞∞4,y4,y4,yuyxwvz2213112535routingandIProuting17/51Dijkstra’salgorithm:example(2)uyxwvzResultingshortest-pathtreefromu:vxywz(u,v)(u,x)(u,x)(u,x)(u,x)destinationlinkResultingforwardingtableinu:routingandIProuting18/51Dijkstra’salgorithm,discussionAlgorithmcomplexity:nnodeseachiteration:needtocheckallnodes,w,notinNn(n+1)/2comparisons:O(n2)moreefficientimplementationspossible:O(nlogn)Oscillationspossible:e.g.,linkcost=amountofcarriedtrafficADCB11+ee0e1100ADCB2+e0001+e1ADCB02+e1+e100ADCB2+e0e01+e1initially…puterouting…pute…puteroutingandIProuting19/51Dijkstra’salgorithm:example(2)uyxwvzResultingshortest-pathtreefromu:vxywz(u,v)(u,x)(u,x)(u,x)(u,x)destinationlinkResultingforwardingtableinu:routingandIProuting20/51Dijkstra’sAlgorithm:ConceptNodeSetsDoneAlreadyhaveleastcostpathtoitHorizon:Reachablein1hopfromnodeinDoneUnseen:CannotreachdirectlyfromnodeinDoneLabeld(v)=pathcostFromstovPathKeeptrackoflastlinkinpathAEFCDB23631123SourceNodeDoneHorizonUnseen0253

CurrentPathCostsroutingandIProuting21/51Dijkstra’sAlgorithm:InitiallyNonodesdoneSourceinhorizonAEFCDB23631123SourceNodeDoneHorizonUnseen0

CurrentPathCostsroutingandIProuting22/51Dijkstra’sAlgorithm:Initiallyd(v)tonodeAshowninredOnlyconsiderlinksfromdonenodesAEFCDB23631123SourceNodeDoneHorizonUnseen0263

CurrentPathCostsroutingandIProuting23/51Dijkstra’sAlgorithmSelectnodevinhorizonwithminimumd(v)AddlinkusedtoaddnodetoshortestpathtreeUpdated(v)informationAEFCDB23631123SourceNodeDoneHorizonUnseen023

CurrentPathCosts65routingandIProuting24/51Dijkstra’sAlgorithmRepeat…AC23631123SourceNodeDoneHorizonUnseen0253

CurrentPathCostsFBDEroutingandIProuting25/51Dijkstra’sAlgorithmUpdated(v)valuesCancauseadditionofnewnodestohorizon2631123SourceNodeDoneHorizonUnseen0243

6CurrentPathCostsAC3DBEFroutingandIProuting26/51Dijkstra’sAlgorithmFinaltreeshowningreen2631123SourceNode024356AC3DBEFroutingandIProuting27/51Chapter4:NetworkLayer4.1Introduction4.2Virtualcircuitanddatagramnetworks4.3What’sinsidearouter4.4IP:InternetProtocolDatagramformatIPv4addressingICMPIPv64.5RoutingalgorithmsLinkstateDistanceVectorHierarchicalrouting4.6RoutingintheInternetRIPOSPFBGP4.7BroadcastandmulticastroutingroutingandIProuting28/51DistanceVectorAlgorithmBellman-FordEquation(dynamicprogramming)Definedx(y):=costofleast-costpathfromxtoyThendx(y)=min{c(x,v)+dv(y)}whereministakenoverallneighborsvofxvroutingandIProuting29/51Bellman-Fordexampleuyxwvz2213112535Clearly,dv(z)=5,dx(z)=3,dw(z)=3du(z)=min{c(u,v)+dv(z),c(u,x)+dx(z),c(u,w)+dw(z)}=min{2+5,1+3,5+3}=4Nodethatachievesminimumisnexthopinshortestpath?forwardingtableB-Fequationsays:routingandIProuting30/51DistanceVectorAlgorithmDx(y)=estimateofleastcostfromxtoyNodexknowscosttoeachneighborv:c(x,v)NodexmaintainsdistancevectorDx=[Dx(y):y?N]Nodexalsomaintainsitsneighbors’distancevectorsForeachneighborv,xmaintains

Dv=[Dv(y):y?N]routingandIProuting31/51Distancevectoralgorithm(4)Basicidea:

Fromtime-to-time,eachnodesendsitsowndistancevectorestimatetoneighborsAsynchronousWhenanodexreceivesnewDVestimatefromneighbor,itupdatesitsownDVusingB-Fequation:Dx(y)←minv{c(x,v)+Dv(y)}foreachnodey?NUnderminor,naturalconditions,theestimateDx(y)convergetotheactualleastcost

dx(y)routingandIProuting32/51DistanceVectorAlgorithm(5)Iterative,asynchronous:eachlocaliterationcausedby:locallinkcostchangeDVupdatemessagefromneighborDistributed:eachnodenotifiesneighborsonlywhenitsDVchangesneighborsthennotifytheirneighborsifnecessarywaitfor(changeinlocallinkcostormsgfromneighbor)puteestimatesifDVtoanydesthaschanged,notifyneighborsEachnode:routingandIProuting33/51xyzxyz027∞∞∞∞∞∞fromcosttofromfromxyzxyz0fromcosttoxyzxyz∞∞∞∞∞costtoxyzxyz∞∞∞710costto∞201∞∞∞201710timexz127ynodextablenodeytablenodeztableDx(y)=min{c(x,y)+Dy(y),c(x,z)+Dz(y)}

=min{2+0,7+1}=2Dx(z)=min{c(x,y)+

Dy(z),c(x,z)+Dz(z)}=min{2+1,7+0}=332routingandIProuting34/51xyzxyz027∞∞∞∞∞∞fromcosttofromfromxyzxyz023fromcosttoxyzxyz023fromcosttoxyzxyz∞∞∞∞∞costtoxyzxyz027fromcosttoxyzxyz023fromcosttoxyzxyz023fromcosttoxyzxyz027fromcosttoxyzxyz∞∞∞710costto∞201∞∞∞201710201710201310201310201310201310timexz127ynodextablenodeytablenodeztableDx(y)=min{c(x,y)+Dy(y),c(x,z)+Dz(y)}

=min{2+0,7+1}=2Dx(z)=min{c(x,y)+

Dy(z),c(x,z)+Dz(z)}=min{2+1,7+0}=3routingandIProuting35/51DistanceVector:linkcostchangesLinkcostchanges:nodedetectslocallinkcostchangeupdatesroutinginfo,recalculates

distancevectorifDVchanges,notifyneighbors“goodnewstravelsfast”xz1450y1Attimet0,ydetectsthelink-costchange,updatesitsDV,andinformsitsneighbors.Attimet1,zreceivestheupdatefromyandupdatesitstable.ItcomputesanewleastcosttoxandsendsitsneighborsitsDV.Attimet2,yreceivesz’supdateandupdatesitsdistancetable.y’sleastcostsdonotchangeandhenceydoesnotsendanymessagetoz.routingandIProuting36/51DistanceVector:linkcostchangesLinkcostchanges:goodnewstravelsfastbadnewstravelsslow-“counttoinfinity”problem!44iterationsbeforealgorithmstabilizes:seetextPoisonedreverse:

IfZroutesthroughYtogettoX:ZtellsYits(Z’s)distancetoXisinfinite(soYwon’troutetoXviaZ)willthiscompletelysolvecounttoinfinityproblem?xz1450y60routingandIProuting37/51ComparisonofLSandDValgorithmsMessagecomplexityLS:withnnodes,Elinks,O(nE)msgssentDV:exchangebetweenneighborsonlyconvergencetimevariesSpeedofConvergenceLS:O(n2)algorithmrequiresO(nE)msgsmayhaveoscillationsDV:convergencetimevariesmayberoutingloopscount-to-infinityproblemRobustness:whathappensifroutermalfunctions?LS:

nodecanadvertiseincorrectlinkcosteachnodecomputesonlyitsowntableDV:DVnodecanadvertiseincorrectpathcosteachnode’stableusedbyotherserrorpropagatethrunetworkroutingandIProuting38/51Chapter4:NetworkLayer4.1Introduction4.2Virtualcircuitanddatagramnetworks4.3What’sinsidearouter4.4IP:InternetProtocolDatagramformatIPv4addressingICMPIPv64.5RoutingalgorithmsLinkstateDistanceVectorHierarchicalrouting4.6RoutingintheInternetRIPOSPFBGP4.7BroadcastandmulticastroutingroutingandIProuting39/51HierarchicalRoutingscale:with200milliondestinations:can’tstorealldest’sinroutingtables!routingtableexchangewouldswamplinks!

administrativeautonomyinternet=networkofnetworkseachnetworkadminmaywanttocontrolroutinginitsownnetworkOurroutingstudythusfar-idealizationallroutersidenticalnetwork“flat”…nottrueinpracticeroutingandIProuting40/51HierarchicalRoutingaggregateroutersintoregions,

“autonomoussystems”(AS)routersinsameASrunsameroutingprotocol“intra-AS”routingprotocolroutersindifferentAScanrundifferentintra-ASroutingprotocolGatewayrouterDirectlinktorouterinanotherASroutingandIProuting41/513b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRoutingalgorithmInter-ASRoutingalgorithmForwardingtable3cInterconnectedASesforwardingtableconfiguredbybothintra-andinter-ASroutingalgorithmintra-ASsetsentriesforinternaldestsinter-AS&intra-AssetsentriesforexternaldestsroutingandIProuting42/513b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AStaskssupposerouterinAS1receivesdatagramdestinedoutsideofAS1:routershouldforwardpackettogatewayrouter,butwhichone?AS1must:learnwhichdestsarereachablethroughAS2,whichthroughAS3propagatethisreachabilityinfotoallroutersinAS1Jobofinter-ASrouting!routingandIProuting43/51Example:Settingforwardingtableinrouter1dsupposeAS1learns(viainter-ASprotocol)thatsubnetxreachableviaAS3(gateway1c)butnotviaAS2.inter-ASprotocolpropagatesreachabilityinfotoallinternalrouters.router1ddeterminesfromintra-ASroutinginfothatitsinterfaceIisontheleastcostpathto1c.installsforwardingtableentry(x,I)3b1d3a1c2aAS3AS1AS21a2c2b1b3cx…routingandIProuting44/51Example:ChoosingamongmultipleASesnowsupposeAS1learnsfrominter-ASprotocolthatsubnetxisreachablefromAS3andfromAS2.toconfigureforwardingtable,router1dmustdeterminetowardswhichgatewayitshouldforwardpacketsfordestx.thisisalsojobofinter-ASroutingprotocol!3b1d3a1c2aAS3AS1AS21a2c2b1b3cx……routingandIProuting45/51Learnfrominter-ASprotocolthatsubnetxisreachableviamultiplegatewaysUseroutinginfofromintra-ASprotocoltodeterminecostsofleast-costpathstoeachofthegatewaysHotpotatorouting:ChoosethegatewaythathasthesmallestleastcostDeterminefromforwardingtabletheinterfaceIthatleadstoleast-costgateway.Enter(x,I)inforwardingtableExample:ChoosingamongmultipleASesnowsupposeAS1learnsfrominter-ASprotocolthatsubnetxisreachablefromAS3andfromAS2.toconfigureforwardingtable,router1dmustdete