计算机网络英文版课件：Chapter4 Network Layer

Chapter4:NetworkLayerChaptergoals:

understandprinciplesbehindnetworklayerservices:networklayerservicemodelsforwardingversusroutinghowarouterworksrouting(pathselection)dealingwithscaleadvancedtopics:IPv6fundationinstantiation,implementationintheInternet1NetworkLayerNetworklayerProvidesend-to-endtransportservice

sendingsideencapsulatessegmentsintodatagramsrcvingsidedeliverssegmentstotransportlayernetworklayerprotocolsineveryhost,routerrouterexaminesheaderfieldsinallIPdatagramspassingthroughitapplicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysical2NetworkLayerTwoKeyNetwork-LayerFunctionsforwarding:movepacketsfromrouter’sinputtoappropriaterouteroutputrouting:determineroutetakenbypacketsfromsourcetodest.routingalgorithms3NetworkLayer1230111valueinarrivingpacket’sheaderroutingalgorithmlocalforwardingtableheadervalueoutputlink01000101011110013221Interplaybetweenroutingandforwarding4NetworkLayerConnectionsetup3rdimportantfunctioninsomenetworkarchitectures:ATM,framerelay,X.25beforedatagramsflow,twoendhostsandinterveningroutersestablishvirtualconnectionroutersgetinvolvednetworkvstransportlayerconnectionservice:network:betweentwohosts(mayalsoinvolveinterveningroutersincaseofVCs)transport:betweentwoprocesses5NetworkLayer

NetworkservicemodelQoSofendtoendtransportingguaranteedbandwidth?preservationofinter-packettiming(nojitter)?loss-freedelivery?in-orderdelivery?congestionfeedbacktosender?NoerrorsDelay???virtualcircuitordatagram?The

mostimportantabstractionprovidedbynetworklayer:serviceabstractionNetwork-servicemodeldefinesthecharacteristicsofend-to-enddatatransport

betweensenderandreceiver6NetworkLayerNetworklayerservicemodels:NetworkArchitectureInternetATMATMATMATMServiceModelbesteffortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteedminimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno(inferredvialoss)nocongestionnocongestionyesnoGuarantees?7NetworkLayerNetworklayerconnectionandconnection-lessservicedatagramnetworkprovidesnetwork-layerconnectionlessserviceVCnetworkprovidesnetwork-layerconnectionserviceCallsetupimplementation:innetworkcore8NetworkLayerVirtualcircuitscallsetup,teardownforeachcallbeforedatacanfloweachpacketcarriesVCidentifier(notdestinationhostaddress)everyrouteronsource-destpathmaintains“state”foreachpassingconnectionlink,routerresources(bandwidth,buffers)maybeallocatedtoVC(dedicatedresources=predictableservice)“source-to-destpathbehavesmuchliketelephonecircuit”performance-wisenetworkactionsalongsource-to-destpath9NetworkLayerVCimplementationaVCconsistsof:pathfromsourcetodestinationVCnumbers,onenumberforeachlinkalongpathentriesinforwardingtablesinroutersalongpathpacketbelongingtoVCcarriesVCnumber(ratherthandestaddress)VCnumbercanbechangedoneachlink.NewVCnumbercomesfromforwardingtable10NetworkLayerForwardingtable122232123VCnumberinterfacenumberIncominginterfaceIncomingVC#OutgoinginterfaceOutgoingVC#11232226311837217197387…………Forwardingtableinnorthwestrouter:Routersmaintainconnectionstateinformation!11NetworkLayerVirtualcircuits:signalingprotocolsusedtosetup,maintain,teardownVCusedinATM,frame-relay,X.25notusedintoday’sInternetapplicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Initiatecall2.incomingcall3.Acceptcall4.Callconnected5.Dataflowbegins6.Receivedata12NetworkLayerDatagramnetworksnocallsetupatnetworklayerrouters:nostateaboutend-to-endconnectionsnonetwork-levelconceptof“connection”packetsforwardedusingdestinationhostaddresspacketsbetweensamesource-destpairmaytakedifferentpathsapplicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Senddata2.Receivedata13NetworkLayerForwardingtable

DestinationAddressRange

LinkInterface

11001000000101110001000000000000through0

11001000000101110001011111111111

11001000000101110001100000000000through111001000000101110001100011111111

11001000000101110001100000000000through2

11001000000101110001111111111111otherwise34billionpossibleentries14NetworkLayerLongestprefixmatching

PrefixMatch

LinkInterface110010000001011100010011001000000101110001100011100100000010111000112otherwise3DA:11001000000101110001100010101010ExamplesDA:11001000000101110001011010100001Whichinterface?Whichinterface?15NetworkLayerDatagramorVCnetwork:why?Internet(datagram)dataexchangeamongcomputers“elastic”service,nostricttimingreq.“smart”endsystems(computers)canadapt,performcontrol,errorrecoverysimpleinsidenetwork,complexityat“edge”manylinktypesdifferentcharacteristicsuniformservicedifficultATM(VC)evolvedfromtelephonyhumanconversation:stricttiming,reliabilityrequirementsneedforguaranteedservice“dumb”endsystemstelephonescomplexityinsidenetwork16NetworkLayerRouterArchitectureOverviewTwokeyrouterfunctions:

runroutingalgorithms/protocol(RIP,OSPF,BGP)forwardingdatagramsfromincomingtooutgoinglink17NetworkLayerInputPortFunctionsDecentralizedswitching:

givendatagramdest.,lookupoutputportusingforwardingtableininputportmemorygoal:completeinputportprocessingat‘linespeed’queuing:ifdatagramsarrivefasterthanforwardingrateintoswitchfabricPhysicallayer:bit-levelreceptionDatalinklayer:e.g.,Ethernetseechapter518NetworkLayerThreetypesofswitchingfabrics19NetworkLayerSwitchingViaMemoryFirstgenerationrouters:traditionalcomputerswithswitchingunderdirectcontrolofCPUpacketcopiedtosystem’smemoryspeedlimitedbymemorybandwidth(2buscrossingsperdatagram)InputPortOutputPortMemorySystemBus20NetworkLayerSwitchingViaaBusdatagramfrominputportmemorytooutputportmemoryviaasharedbusbuscontention:switchingspeedlimitedbybusbandwidth32Gbpsbus,Cisco5600:sufficientspeedforaccessandenterpriserouters21NetworkLayerSwitchingViaAnInterconnectionNetworkovercomebusbandwidthlimitationsBanyannetworks,otherinterconnectionnetsinitiallydevelopedtoconnectprocessorsinmultiprocessoradvanceddesign:fragmentingdatagramintofixedlengthcells,switchcellsthroughthefabric.Cisco12000:switches60Gbpsthroughtheinterconnectionnetwork22NetworkLayerOutputPortsBufferingrequiredwhendatagramsarrivefromfabricfasterthanthetransmissionrateSchedulingdisciplinechoosesamongqueueddatagramsfortransmission23NetworkLayerOutputportqueueingbufferingwhenarrivalrateviaswitchexceedsoutputlinespeedqueueing(delay)andlossduetooutputportbufferoverflow!24NetworkLayerHowmuchbuffering?RFC3439ruleofthumb:averagebufferingequalto“typical”RTT(say250msec)timeslinkcapacityCe.g.,C=10Gpslink:2.5GbitbufferRecentrecommendation:withNflows,bufferingequaltoRTTC.N25NetworkLayerInputPortQueuingFabricslowerthaninputportscombined->queueingmayoccuratinputqueuesHead-of-the-Line(HOL)blocking:queueddatagramatfrontofqueuepreventsothersinqueuefrommovingforwardqueueingdelayandlossduetoinputbufferoverflow!26NetworkLayer

RouterOverview27NetworkLayer

RouterOverview28NetworkLayer

RouterOverview29NetworkLayerTheInternetNetworklayerforwardingtableHost,routernetworklayerfunctions:RoutingprotocolspathselectionRIP,OSPF,BGPIPprotocoladdressingconventionsdatagramformatpackethandlingconventionsICMPprotocolerrorreportingrouter“signaling”Transportlayer:TCP,UDPLinklayerphysicallayerNetworklayer30NetworkLayerIPdatagramformatverlength32bitsdata(variablelength,typicallyaTCPorUDPsegment)16-bitidentifierheaderchecksumtimetolive32bitsourceIPaddressIPprotocolversionnumberheaderlength(bytes)maxnumberremaininghops(decrementedateachrouter)forfragmentation/reassemblytotaldatagramlength(bytes)upperlayerprotocoltodeliverpayloadtohead.lentypeofservice“type”ofdataflgsfragmentoffsetupperlayer32bitdestinationIPaddressOptions(ifany)E.g.timestamp,recordroutetaken,specifylistofrouterstovisit.howmuchoverheadwithTCP?20bytesofTCP20bytesofIP=40bytes+applayeroverhead31NetworkLayerIPFragmentation&ReassemblynetworklinkshaveMTU(max.transfersize)-largestpossiblelink-levelframe.differentlinktypes,differentMTUslargeIPdatagramdivided(“fragmented”)withinnetonedatagrambecomesseveraldatagrams“reassembled”onlyatfinaldestinationIPheaderbitsusedtoidentify,orderrelatedfragmentsfragmentation:in:onelargedatagramout:3smallerdatagramsreassembly32NetworkLayerIPFragmentationandReassemblyID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=1480fragflag=1length=1500ID=xoffset=2960fragflag=0length=1040OnelargedatagrambecomesseveralsmallerdatagramsExample4000bytedatagramMTU=1500bytes1480bytesin

datafield:0~1479Offset：1480~2959

33NetworkLayerIPAddressing:introductionIPaddress:32-bitidentifierforhost,routerinterface

interface:connectionbetweenhost/routerandphysicallinkrouter’stypicallyhavemultipleinterfaceshosttypicallyhasoneinterfaceIPaddressesassociatedwitheachinterface7=1101111100000001000000010000000122311134NetworkLayerSubnetsIPaddress:

networkpart(highorderbits)hostpart(loworderbits)What’sasubnet?deviceinterfaceswithsamenetpartofIPaddresscanphysicallyreacheachotherwithoutinterveningrouter7networkconsistingof3subnetssubnet35NetworkLayerSubnets/24/24/24RecipeTodeterminethesubnets,detacheachinterfacefromitshostorrouter,creatingislandsofisolatednetworks.Eachisolatednetworkiscalledanetworksegment.Subnetmask:/2436NetworkLayerSubnetsHowmany?737NetworkLayer

IPAddresses0networkhost10networkhost110networkhost1110multicastaddressABCDclass

to55

to55

to55

to5532bitsgivennotionof“network”,let’sre-examineIPaddresses:“class-full”addressing:38NetworkLayer

SpecialAddressesNet-idHost-idSourceaddDest.addspecifications00Thisnetwork,thishost0Host-idThisnetwork,ahostAll1All1BroadcastinginthisnetworkNet-idAll1Broadcastinginanetwork127anyLoopbacktest39NetworkLayer

SubnetMask

Introducedin1985,adaptivetodistributedinstitute--subnetsomeLeftbitsofhost-idareusedforsubnetfieldSubnetpartitionmustusesubnetmask:UsingsubnetwillreduceavailablehostaddressesB:65534host-id,if6bitusedforsubnet-id(26-2)(210-2)=63364Net-idSubnetidHost-id111111…11111111..111000..00

defaultsubnetmasks:A:B:C:

ipaddress:subnetmask:

subnetaddress=ipaddress&subnetmask40NetworkLayer

AnexampleAsmallcompanyhasaclassCnetworklicenseandneedstocreate10usablesubnets,eachsubnetcapableofaccommodatingatleast12hosts.Whichofthefollowingistheappropriatesubnetmask?

92244041NetworkLayerIPaddressing:CIDRCIDR:

ClasslessInterDomainRoutingnetworkportionofaddressofarbitrarylengthaddressformat:a.b.c.d/x,wherexis#bitsinsubnetportionofaddress1100100000010111

0001000000000000subnetparthostpart/2342NetworkLayerIPaddresses:howtogetone?Q:HowdoesahostgetIPaddress?hard-codedbysystemadmininafileWindows:control-panel->network->configuration->tcp/ip->propertiesUNIX:/etc/rc.configDHCP:

DynamicHostConfigurationProtocol:dynamicallygetaddressfromasserver“plug-and-play”43NetworkLayerDHCP:DynamicHostConfigurationProtocolGoal:allowhosttodynamicallyobtainitsIPaddressfromnetworkserverwhenitjoinsnetworkCanrenewitsleaseonaddressinuseAllowsreuseofaddresses(onlyholdaddresswhileconnectedan“on”)Supportformobileuserswhowanttojoinnetwork(moreshortly)DHCPoverview:hostbroadcasts“DHCPdiscover”msgDHCPserverrespondswith“DHCPoffer”msg

hostrequestsIPaddress:“DHCPrequest”msgDHCPserversendsaddress:“DHCPack”msg44NetworkLayerDHCPclient-serverscenario7ABE

DHCP

server

arrivingDHCPclientneedsaddressinthisnetwork45NetworkLayerDHCPclient-serverscenarioDHCPserver:arrivingclienttimeDHCPdiscoversrc:,68dest.:55,67yiaddr:transactionID:654DHCPoffersrc:,67dest:55,68yiaddrr:transactionID:654Lifetime:3600secsDHCPrequestsrc:,68dest::55,67yiaddrr:transactionID:655Lifetime:3600secsDHCPACKsrc:,67dest:55,68yiaddrr:transactionID:655Lifetime:3600secsHalfoftime:Re-request46NetworkLayerDHCP:morethanIPaddressDHCPcanreturnmorethanjustallocatedIPaddressonsubnet:addressoffirst-hoprouterforclientnameandIPaddressofDNSsevernetworkmask(indicatingnetworkversushostportionofaddress)47NetworkLayerDHCP:exampleconnectinglaptopneedsitsIPaddress,addroffirst-hoprouter,addrofDNSserver:useDHCProuter(runsDHCP)DHCPUDPIPEthPhyDHCPDHCPDHCPDHCPDHCPDHCPUDPIPEthPhyDHCPDHCPDHCPDHCPDHCPDHCPrequestencapsulatedinUDP,encapsulatedinIP,encapsulatedin802.3EthernetEthernetframebroadcast(dest:FFFFFFFFFFFF)onLAN,receivedatrouterrunningDHCPserverEthernetdemux’edtoIPdemux’ed,UDPdemux’edtoDHCP48NetworkLayerDCPserverformulatesDHCPACKcontainingclient’sIPaddress,IPaddressoffirst-hoprouterforclient,name&IPaddressofDNSserverrouter(runsDHCP)DHCPUDPIPEthPhyDHCPDHCPDHCPDHCPDHCPUDPIPEthPhyDHCPDHCPDHCPDHCPDHCPencapsulationofDHCPserver,frameforwardedtoclient,demux’inguptoDHCPatclientclientnowknowsitsIPaddress,nameandIPaddressofDSNserver,IPaddressofitsfirst-hoprouterDHCP:example49NetworkLayerIPaddresses:howtogetone?Q:HowdoesnetworkgetsubnetpartofIPaddr?A:getsallocatedportionofitsproviderISP’saddressspaceISP'sblock11001000000101110001000000000000/20Organization011001000000101110001000000000000/23Organization111001000000101110001001000000000/23Organization211001000000101110001010000000000/23...…..….….Organization711001000000101110001111000000000/23

50NetworkLayerHierarchicaladdressing:routeaggregation“Sendmeanythingwithaddressesbeginning/20”/23/23/23Fly-By-Night-ISPOrganization0Organization7InternetOrganization1ISPs-R-Us“Sendmeanythingwithaddressesbeginning/16”/23Organization2......Hierarchicaladdressingallowsefficientadvertisementofroutinginformation:51NetworkLayerHierarchicaladdressing:morespecificroutesISPs-R-UshasamorespecificroutetoOrganization1“Sendmeanythingwithaddressesbeginning/20”/23/23/23Fly-By-Night-ISPOrganization0Organization7InternetOrganization1ISPs-R-Us“Sendmeanythingwithaddressesbeginning/16or/23”/23Organization2......52NetworkLayerIPaddressing:thelastword...Q:HowdoesanISPgetblockofaddresses?A:ICANN:InternetCorporationforAssigned

NamesandNumbersallocatesaddressesmanagesDNSassignsdomainnames,resolvesdisputes53NetworkLayerNAT:NetworkAddressTranslationlocalnetwork(e.g.,homenetwork)10.0.0/24restofInternetDatagramswithsourceordestinationinthisnetworkhave10.0.0/24addressforsource,destination(asusual)AlldatagramsleavinglocalnetworkhavesamesinglesourceNATIPaddress:,differentsourceportnumbers54NetworkLayerNAT:NetworkAddressTranslationMotivation:localnetworkusesjustoneIPaddressasfarasoutsideworldisconcerned:rangeofaddressesnotneededfromISP:justoneIPaddressforalldevicescanchangeaddressesofdevicesinlocalnetworkwithoutnotifyingoutsideworldcanchangeISPwithoutchangingaddressesofdevicesinlocalnetworkdevicesinsidelocalnetnotexplicitlyaddressable,visiblebyoutsideworld(asecurityplus).55NetworkLayerNAT:NetworkAddressTranslationImplementation:NATroutermust:

outgoingdatagrams:

replace(sourceIPaddress,port#)ofeveryoutgoingdatagramto(NATIPaddress,newport#)...remoteclients/serverswillrespondusing(NATIPaddress,newport#)asdestinationaddr.

remember(inNATtranslationtable)every(sourceIPaddress,port#)to(NATIPaddress,newport#)translationpair

incomingdatagrams:

replace(NATIPaddress,newport#)indestfieldsofeveryincomingdatagramwithcorresponding(sourceIPaddress,port#)storedinNATtable56NetworkLayerNAT:NetworkAddressTranslationS:,3345D:86,8011:hostsendsdatagramto86,80NATtranslationtableWANsideaddrLANsideaddr,5001,3345…………S:86,80D:,33454S:,5001D:86,8022:NATrouterchangesdatagramsourceaddrfrom,3345to,5001,updatestableS:86,80D:,500133:Replyarrivesdest.address:,50014:NATrouterchangesdatagramdestaddrfrom,5001to,3345

57NetworkLayerNAT:NetworkAddressTranslation16-bitport-numberfield:60,000simultaneousconnectionswithasingleLAN-sideaddress!NATiscontroversial:routersshouldonlyprocessuptolayer3violatesend-to-endargumentNATpossibilitymustbetakenintoaccountbyappdesigners,eg,P2PapplicationsaddressshortageshouldinsteadbesolvedbyIPv658NetworkLayerNATtraversalproblemclientwantstoconnecttoserverwithaddressserveraddresslocaltoLAN(clientcan’tuseitasdestinationaddr)onlyoneexternallyvisibleNATtedaddress:solution1:staticallyconfigureNATtoforwardincomingconnectionrequestsatgivenporttoservere.g.,(,port2500)alwaysforwardedtoport25000NATrouterClient?59NetworkLayerNATtraversalproblemsolution2:UniversalPlugandPlay(UPnP)InternetGatewayDevice(IGD)Protocol.AllowsNATtedhostto:learnpublicIPaddress()add/removeportmappings(withleasetimes)i.e.,automatestaticNATportmapconfigurationNATrouterIGD60NetworkLayerNATtraversalproblemsolution3:relaying(usedinSkype)NATedclientestablishesconnectiontorelayExternalclientconnectstorelayrelaybridgespacketsbetweentoconnectionsClientNATrouter1.connectiontorelayinitiatedbyNATtedhost2.connectiontorelayinitiatedbyclient3.relayingestablished61NetworkLayerICMP:InternetControlMessageProtocolusedbyhosts&routerstocommunicatenetwork-levelinformationerrorreporting:unreachablehost,network,port,protocolechorequest/reply(usedbyping)network-layer“above”IP:ICMPmsgscarriedinIPdatagramsICMPmessage:type,codeplusfirst8bytesofIPdatagramcausingerrorType

Code

description00echoreply(ping)30workunreachable31desthostunreachable32destprotocolunreachable33destportunreachable36destnetworkunknown37desthostunknown40sourcequench(congestioncontrol-notused)80echorequest(ping)90routeadvertisement100routerdiscovery110TTLexpired120badIPheader62NetworkLayerTracerouteandICMPSourcesendsseriesofUDPsegmentstodestFirsthasTTL=1SecondhasTTL=2,etc.UnlikelyportnumberWhennthdatagramarrivestonthrouter:RouterdiscardsdatagramAndsendstosourceanICMPmessage(type11,code0)Messageincludesnameofrouter&IPaddressWhenICMPmessagearrives,sourcecalculatesRTTTraceroutedoesthis3timesStoppingcriterionUDPsegmenteventuallyarrivesatdestinationhostDestinationreturnsICMP“hostunreachable”packet(type3,code3)WhensourcegetsthisICMP,stops.63NetworkLayerIPv6Initialmotivation:

32-bitaddressspacesoontobecompletelyallocated.Additionalmotivation:headerformathelpsspeedprocessing/forwardingheaderchangestofacilitateQoSIPv6datagramformat:

fixed-length40byteheadernofragmentationallowed64NetworkLayerIPv6Header(Cont)Priority:identifypriorityamongdatagramsinflowFlowLabel:identifydatagramsinsame“flow.”(conceptof“flow”notwelldefined).Nextheader:identifyupperlayerprotocolfordata65NetworkLayerOtherChangesfromIPv4Checksum:

removedentirelytoreduceprocessingtimeateachhopOptions:allowed,butoutsideofheader,indicatedby“NextHeader”fieldICMPv6:newversionofICMPadditionalmessagetypes,e.g.“PacketTooBig”multicastgroupmanagementfunctions66NetworkLayerTransitionFromIPv4ToIPv6Notallrouterscanbeupgradedsimultaneousno“flagdays”HowwillthenetworkoperatewithmixedIPv4andIPv6routers?Tunneling:IPv6carriedaspayloadinIPv4datagramamongIPv4routers67NetworkLayerTunnelingABEFIPv6IPv6IPv6IPv6tunnelLogicalview:Physicalview:ABEFIPv6IPv6IPv6IPv6IPv4IPv468NetworkLayerTunnelingABEFIPv6IPv6IPv6IPv6tunnelLogicalview:Physicalview:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4Flow:XSrc:ADest:FdataFlow:XSrc:ADest:FdataFlow:XSrc:ADest:FdataSrc:BDest:EFlow:XSrc:ADest:FdataSrc:BDest:EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6insideIPv4B-to-C:IPv6insideIPv469NetworkLayer1230111valueinarrivingpacket’sheaderroutingalgorithmlocalforwardingtableheadervalueoutputlink01000101011110013221Interplaybetweenrouting,forwarding70NetworkLayeruyxwvz2213112535Graph: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,whereNissetofpeersandEissetofTCPconnections71NetworkLayerGraphabstraction:costsuyxwvz2213112535

c(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-costpath72NetworkLayerRoutingAlgorithmclassificationGlobalordecentralizedinformation?Global:allroutershavecompletetopology,linkcostinfo“linkstate”algorithmsDecentralized:

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

routeschangeslowlyovertimeDynamic:

routeschangemorequicklyperiodicupdateinresponsetolinkcostchanges73NetworkLayerALink-StateRoutingAlgorithmDijkstra’salgorithmnettopology,linkcostsknowntoallnodesaccomplishedvia“linkstatebroadcast”allnodeshavesameinfocomputesleastcostpathsfromonenode(‘source”)toallothernodesgivesforwardingtableforthatnodeiterative:afterkiterations,knowleastcostpathtokdest.’sNotation:c(x,y):linkcostfromnodextoy;=∞ifnotdirectneighborsD(v):currentvalueofcostofpathfromsourcetodest.vp(v):predecessornodealongpathfromsourcetovN':setofnodeswhoseleastcostpathdefinitivelyknown74NetworkLayerDijsktra’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'

75NetworkLayerDijkstra’salgorithm:exampleStep012345N'uuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,u