计算机系保研南大面试课程

1ComputerNetworksGuQing,XiaNaiNanjingUniversity2023/10/10Chapter4.InternetworkingTheInternetProtocolIPAddressARPandDHCPICMPIPv6InternetRoutingBGPandOSPFIPMulticastingMobileIPMultiprotocolLabelSwitching(MPLS)2TheInternet3PartofnetworklayerandprovidestransferofpacketsacrossmultiplepossiblydissimilarnetworksRoutersdirectpacketsacrossnetworks4InternetworkingR=router

H=hostNet1Net5Net3Net2HNet3RHHHRRRRRNet1Net2Net4Net5

EthernetLANATMSwitchATMSwitchATMSwitchATMSwitchATMNetworkPositionsoftheIPProtocolIP–InternetProtocolMostfamousinternetprotocoldevelopedforARPANETRFC791,InternetSTDnumber5IPlayerentityresidesoneachhostandrouterProvidesconnectionlessservice(i.e.datagrammechanism)5applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysicalnetworkdatalinkphysical6TheInternetNetworklayerHost,routernetworklayerfunctionsforwardingtableRoutingprotocolsPathselectionRIP,OSPF,BGPIPprotocolAddressingconventionsDatagramformatPackethandlingconventionsICMPprotocolErrorreportingRouter“signaling”Transportlayer:TCP,UDPLinklayerphysicallayerNetworklayerIGMPprotocolMulticastingsupportInternetAddressingAddressinglevelAddressingscopeAddressingmode78AddressingLevelPhysicalnetworkaddressUsedtoroutePDUwithinsinglephysicalnetworkInter-networkaddressIPaddressorinternetaddress,usedtoroutePDUacrossnetworksUniqueaddressforeachendsystem(host)andeachintermediatesystem(router)ApplicationaddressProcessidentifierassignedatdestinationhosti.e.TCP/IPport9AddressingScopeGlobaladdressIdentifieshostorrouterwithglobalnon-ambiguitySynonymspermitted,i.e.aroutermayhavemorethanoneglobaladdressNetworkattachmentaddressUniqueaddressforeachdeviceinterfaceonspecificnetworke.g.MACaddressonIEEE802networkorATMhostaddressPortaddressAbovenetworklevelanduniquewithinasystem(routerorhost)e.g.

port80

–webserverlisteningporton

TCP/IPNeednotbeuniqueoutsidethesinglesystem10AddressingModeIndividualorUnicastaddressAddressreferringtoasinglesystemorportBroadcastaddressForallentitieswithinadomainMulticastaddressForspecificsubsetofentitiesAnycastaddressAny(suitable)entitywithinasubset

11LevelofAddressesAddressingLevelsAddressingScopeConnectionIdentifiersIPOperationsRoutingDatagramlifetimeFragmentationandre-assemblyErrorcontrolFlowcontrol1213TheInternetasaNetwork14RoutingHostsandroutersmaintainroutingtablesIndicatenextroutertowhichdatagramshouldbesentStatic–maycontainalternativeroutesDynamic–flexibleresponsetocongestionanderrorsRoutingpolicyDistancevector,Linkstate,PathvectorSourceroutingSourcespecifiesrouteassequentiallistofrouterstobefollowedRouterecording15DatagramLifetimeDatagramsmayloopindefinitelyRoutingbasedonobsoletenetworksinformationTCPneedsupperboundondatagramlifeDatagrammarkedwithlifetimeTimeToLive(TTL)fieldinIPOncelifetimeexpires,datagramisdiscardedinsteadofforwardedTypesoflifetimeHopcount–DecrementTTLonpassingthrougheachrouter16FragmentationandRe-assemblyLengthofapacketexceedsthecomingnetwork’sMTU(maximumtransmissionunit)WhentofragmentHost–determineminofMTUsalongthepathRouter–fragmentifthenextMTUisexceededWhentore-assembleHost–PacketsgettingsmallerasdatatraversesinternetRouter–infeasiblesincefragmentsmaytakedifferentroutes17IPFragmentation(1)IPv4fragmentsatrouterOnedatagramesseveraldatagramsIPheaderbitsusedtoidentify,orderrelatedfragmentsIPre-assemblesatdestinationonlyfragmentation:in:onelargedatagramout:3smallerdatagramsreassembly18IPFragmentationFieldsDataUnitIdentifier(ID)Identifiesendsystemoriginateddatagram,alsoneeds:Sourceanddestinationaddress,Upperlayer(e.g.TCP)DatalengthLengthofuserdatainoctetsincludingheaderOffsetPositionoffragmentofuserdatainoriginaldatagramInmultiplesof64bits(i.e.8octets)MoreflagIndicatesthatthisisnotthelastfragment19FragmentationExampleExample4000octetsdatagram(3980data+20header)MTU=1500octetsID=xoffset=0moreflag=0length=4000ID=xoffset=0moreflag=1length=1500ID=xoffset=185moreflag=1length=1500ID=xoffset=370moreflag=0length=1040Onelargedatagramesseveralsmallerdatagrams1480bytesin

datafieldoffset=1480/820DatagramRe-assemblyMustprepareenoughbufferspaceatreassemblypointAsfragmentswiththesameIDarrive,dataareinsertedinproperpositioninthebufferUseLengthandOffsetheaderfieldsUseMoreflagtodetermineifendfragmentarrivedUntilentiredatafieldisreassembledStartingwithanOffsetof0andendingwithafalseMoreflag21DealingwithFailureRe-assemblymayfailifsomefragmentsgetlostRe-assemblytimeoutAssignedwhenfirstfragmentarrivedIftimeoutexpiresbeforeallfragmentsarrive,discardpartialdataUsepacketlifetime(TTLinIP)DecrementwitheachfragmentIfTTLrunsout,killpartialdataIPv6usesourcefragmentation22ErrorControlNotguaranteeddeliveryRoutershouldattempttoinformsourceifpacketdiscardede.g.forchecksumfailure,TTLexpiringDatagramidentificationneededICMPusedtosenderrormessageSourcemayinformhigherlayerprotocol23FlowControlAllowsrouterstolimitrateofingdataLimitedcontrolfunctionsinconnectionlesssystemsNewmechanismscomingsoonRouterdiscardsingpacketswhenbuffersaturatesMaysendsourcequenchpacketstosendinghostUsingICMP24IPv4Header25HeaderFields(1)Version(4bits)Currently4IPv6–seelaterInternetheaderlength(4bits)In32bitwords(4octets)Minimumfixedheader(20octets)+optionsTypeofservice(8bits)Totallength(16bits)Ofdatagram,inoctets26TypeofServicePrecedence3bits,

8levelsdefinedReliability1bit,NormalorhighDelay1bit,NormalorlowThroughput1bit,Normalorhigh27HeaderFields(2)Identification(16bits)SequencenumberUsedwithaddressesanduserprotocoltoidentifydatagramuniquelyFlags(3bits)Moreflag,Don’tfragmentFragmentationoffset(13bits)Timetolive(8bits)Protocol(8bits)Nexthigherlayertoreceivedatafieldatdestination28HeaderFields(3)Headerchecksum(16bits)Complementsumofall16bitwordsinheaderReverifiedandputedateachrouter,setto0duringcalculationSourceaddress(32bits)Destinationaddress(32bits)Options(variable40octets)Padding(variable)Tofilltomultipleof32bitslong29DataFieldCarriesuserdatafromnextlayerupMultipleof8bitslong(i.e.octet)Maxlengthofdatagram(header+data)65,535octetsIPPrimitives2primitivesSend(calledbyupperlayer)RequesttransmissionofdataunitDeliver(notifyupperlayer)NotifyuserofarrivalofdataunitParametersUsedtopassdataandcontrolinfo3031SendandDeliverPrimitivesSend{SourceaddressDestinationaddressProtocolTypeofserviceindicatorsIdentificationDon’tfragmentindicatorTimetoliveDatalengthOptiondataUserdata}Deliver{SourceaddressDestinationaddressProtocolTypeofserviceindicatorsDatalengthOptiondataUserdata}32IPAddressing(1)IPaddress32bitglobalinternetaddressforeachinterfaceNetworkpart(highorderbits)Hostpart(loworderbits)Physicalnetwork(fromIPperspective)Canreacheachotherwithoutinterveningrouter223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.0223.1.2.0223.1.3.0NetworkInterfaces223.1.1.1=11011111000000010000000100000001223111CountthePhysicalNetworksHowmany?33IPAddressAseparateaddressisrequiredforeachphysicalinterfaceofahost/routertoanetworkFacilitatesroutingUseDotted-DecimalNotationnetid

unique&administeredbyAmericanRegistryforInternetNumbers(ARIN)ReseauxIPEuropeens(RIPE)AsiaPacificNetworkInformationCentre(APNIC)hostid

assignedwithindesignatedorganization3435IPv4AddressFormats36IPAddresses–ClassAStartwithbinary0ReservednetidAll0reserved01111111(127)reservedforloopbackRange1.x.x.xto126.x.x.xUpto16millionhostsAllallocated37IPAddresses–ClassBStartwith10Range128.0.x.xto191.255.x.xSecondOctetalsoincludedinnetworkaddress214=16,384classBnetworksUpto65,000hostsAllallocated38IPAddresses–ClassCStartwith110Range192.0.0.xto223.255.255.xSecondandthirdoctetalsopartofnetworkaddress221=2,097,152networksUpto254hostsNearlyallallocated39Inter-NetworkswithAddresses40SubnetsandSubnetMasksHandleproblemofnetworkaddressinadequacyHostportionofaddresspartitionedintosubnetnumberandhostnumberSubnetmaskindicateswhichbitsaresubnetnumberandwhicharehostnumberEachLANassignedasubnetnumber,moreflexibilityLocalroutersroutewithinsubnettednetworkSubnetslookstorestofinternetlikeasinglenetworkInsulateoverallInternetfromgrowthofnetworknumbersandroutingcomplexity41SubnetsExample42SubnetstotheRest43RoutingUsingSubnets(1)44RoutingUsingSubnets(2)CIDR

NotationClasslessInterDomainRouting(CIDR)AnIPaddressisrepresentedas“A.B.C.D/n”,whereniscalledtheIP(network)prefix45IPAddressSubnetNetworkIDCIDR10.217.112.0/20255.255.240.01111111111111111111100000000000010.217.123.70000101011011001011110110000011100001010110110010111000000000000MoreGeneralCaseAnISPcanbelookedasasetofsubnetsSupportmanyorganizations(Intranets)Hierarchicaladdressing46RouteAggregationAllowsefficientadvertisementofroutinginformation47NetworkAddressTranslationNATEnablesdifferentsetsofIPaddressesforinternalandexternaltrafficTheIPaddresstranslationsoccurwheretheIntranetinterfaceswiththebroaderInternetPurposesActsasafirewallbyhidinginternalIPaddressesEnablesanenterprise(organization)tousemoreinternalIPaddressesIsolatethe(organization/ISP)changes48IllustrationofNAT49InternetInside10.1.1.110.1.1.2HostB172.20.7.3ACBInside

LocalIPAddress10.1.1.210.1.1.1SimpleNATtableInsideGlobalIPAddress192.168.2.3192.168.2.2BADSA10.1.1.1DA10.1.1.1SA192.168.2.2DA192.168.2.2NATRouterOverloadingGlobalAddress5010.1.1.2:172310.1.1.1:1024NATtable192.168.2.2:1723192.168.2.2:1024176.21.17.9:23172.20.7.3:23TCPTCP10.1.1.3:1723192.168.2.2:1492176.21.17.9:23TCPInternetInside10.1.1.1HostB172.20.7.313SA10.1.1.1DA10.1.1.1SA192.168.2.2DA192.168.2.210.1.1.210.1.1.3452HostC176.21.17.9DA192.168.2.24InsideGlobalIPAddress:PortOutsideGlobalIPAddress:PortProtocolInsideLocalIPAddress:Port10.1.1.1NetworkAddressTranslation5110.0.0.110.0.0.210.0.0.3S:10.0.0.1,3345D:128.119.40.186,80110.0.0.4138.76.29.7NATtranslationtableWANsideaddrLANsideaddr138.76.29.7,500110.0.0.1,3345…………S:128.119.40.186,80D:10.0.0.1,33454S:138.76.29.7,5001D:128.119.40.186,802S:128.119.40.186,80D:138.76.29.7,500132TypesofNATStaticNATAprivateIPaddressismappedtoonereservedpublicIPaddressUsuallyforserverhostsinIntranetDynamicNATTheNATrouterkeepsapoolofregisteredIPaddresses,andassigntoprivateIPaddressesondemandUsuallyforclientPCsinIntranet52NATisControversialAddresseschangesfromtimetotimeE.g.mustbetakenintoaccountbyP2PapplicationsRelayinginSkypeNATedsupernodesestablishesconnectiontorelayExternalclientconnectstorelayRelaybridgespacketsbetween2connections5310.0.0.1NATrouter138.76.29.7Client1.connectiontorelayinitiatedbyNATedhost2.connectiontorelayinitiatedbyclient3.relayingestablished54IPForwardingTryHandlingoutAddressesWalkthrough:senddatagramfromAtoBviaR55ARPandDHCPARP(AddressResolutionProtocol)ConvertanIPaddressintoaphysical(MAC)addressusingbroadcasts,typicalforLANusersDHCP(DynamicHostConfigurationProtocol)AssigndynamicIPaddressestohostsonanetwork,typicalfordial-upandLANusers56AddressResolutionProtocolUseraccessDNSgivesitsIPaddress202.119.32.12ItsMACaddressisneededtodeliverthedataOnLAN,ARPisusedgetahost/router’sMACgivenitsIPaddress57ARPProcedureSenderLooksintolocalcachefirst,ifnoneConstructsARPrequest,insert<senderIP,senderMAC,destinationIP>BroadcastsusingMACframeCachesdestination’s<MAC,IP>pairwithtimestampReceiverChecksthedestinationIP,ifOKConstructsARPreply,insert<destinationIP,destinationMAC>SendstosenderMACusingMACframeCachessender’s<MAC,IP>pairwithtimestamp58IllustrationofARP59ComputerA:IP:129.25.10.72MAC:49:72:16:08:64:14ComputerB:IP:129.25.10.97MAC:49:72:16:08:80:70ComputerC:IP:129.25.10.81MAC:49:17:92:96:96:96Server/RouterRIP:129.25.10.11MAC:49:78:21:21:23:90MACaddressof129.25.10.11?

Requestedby:49:72:16:08:64:14(129.25.10.72)ARP-RequesttoMACFF:FF:FF:FF:FF:FF1Reply:129.25.10.11(49:78:21:21:23:90)

Requestedby:129.25.10.72ARP-ReplytoMAC49:72:16:08:64:142DHCPDynamicHostConfigurationProtocolAnextensionofBootstrap

protocol(BOOTP),builtontopofUDP(Port67/68)ForpassingconfigurationinformationtohostsonaTCP/IPnetwork60LocalNetworkDHCPClientsDHCPServerIPAddressDatabaseTypicalProcedureofDHCPTheclientbroadcastsaDHCP-DISCOVERmessageonitssubnetEachservermayrespondwithaDHCP-OFFERmessageTheclientchoosesoneserver,broadcastsaDHCP-REQUESTmessageincludingserverIPTheselectedservercommitsthebinding,respondswithaDHCP-ACKmessage61DHCP-DiscoverDHCP-OfferDHCP-RequestDHCP-AckDHCP-Release……TypicalProcedureofDHCPTheclientsetitsconfigurationparameterswithintheDHCP-ACKTheclientrelinquishthebindingbyaDHCP-RELEASEmessageThebindingwillbeexpirediftheclientdoesnotrenew(rebind)thebindingbefore62DHCP-DiscoverDHCP-OfferDHCP-RequestDHCP-AckDHCP-Release……DHCPMessages63DHCPserver:223.1.2.5arrivingclienttimeDHCPdiscoversrc:0.0.0.0,68dest.:255.255.255.255,67yiaddr:0.0.0.0transactionID:654DHCPoffersrc:223.1.2.5,67dest:255.255.255.255,68yiaddrr:223.1.2.4transactionID:654Lifetime:3600secsDHCPrequestsrc:0.0.0.0,68dest::255.255.255.255,67yiaddrr:223.1.2.4transactionID:655Lifetime:3600secsDHCPACKsrc:223.1.2.5,67dest:255.255.255.255,68yiaddrr:223.1.2.4transactionID:655Lifetime:3600secs64ICMPInternetControlMessageProtocol(RFC792)TransferoferrorandcontrolmsgsamongroutersandhostsEchorequestandreplytofacilitatediagnosticFeedbackaboutproblems,e.g.timetoliveexpired,unreachablehostEncapsulatedinIPdatagramProtocoltype=1Notreliable65ICMPMessageFormats66SomeICMPMessageTypesType

Code

description00echoreply(ping)30dest.networkunreachable31desthostunreachable32destprotocolunreachable33destportunreachable36destnetworkunknown37desthostunknown40sourcequench(congestioncontrol)80echorequest(ping)90routeadvertisement100routerdiscovery110TTLexpired120Parameterunintelligible130timestamp140timestampreply150addressmaskrequest160addressmaskreply67UsingICMP–PingTestdestinationreachabilitySourcesendsechorequesttoaremotehostorrouterIfremotesystemreceivestheICMPpacket,itsendsbackanechoreplytosourceThepingutilitymayfurtherdoCalculateround-triptimeCountthenumberofhopstodestination(useTTL)68UsingICMP–TracerouteMeasuresthenumberofhopsrequiredtoreachadestinationSourcesends1stIP(UDP)packetwiththeTTLvaluesetto1ThefirstrouterdecrementstheTTLto0,discardsthepacket,sendsaTTLexpiredbackSourcecalculatesRTT,andrepeat3timesSourcesends2ndIPpacketwiththeTTLsetto2ThesecondrouterwillsendbackaTTLexpiredSourcecalculatesRTT,andrepeat3timesSourcerepeatsthiswithincreasingTTLuntildestinationisreached(orhostunreachable)Maysufferfromdynamicrouting(how?)69UsingICMP–PathMTUDeterminestheminimumMTUalongthepathtodestinationSourcesendsalargeIPpacketwithdon’tfragmentbitsetIfpackettoolarge,relevantrouterwillsendbackaparameterunintelligibleSourcedecrementsthepacketlengthaccordinglyandtriesagainUntilthepacketreachesdestinationwithoutICMPerrormessageAlsosufferfromdynamicrouting70IPv6Initialmotivation:addressspaceexhaustionRapidgrowthofnetworksandtheInternet32-bitaddressspace(esp.netaddress)soontobecompletelyallocatedAdditionalmotivationNewheaderformathelpsspeedprocessingandforwardingHeaderchangestofacilitateQOSNofragmentationatrouterNewaddressmode:routeto“best”ofseveralreplicatedservers71IPv6RFCs1752–mendationsfortheIPNextGenerationProtocol2460–Overallspecification2373–addressingstructureOthers()1981–PathMTUDiscoveryforIPv62401–SecurityArchitecturefortheInternetProtocol2402–IPAuthenticationHeader2406–IPEncapsulatingSecurityProtocol(ESP)2463–ICMPforIPv6…IPv6HeaderVersion(4bits):6TrafficClass(8bits)Classesorprioritiesofpacket,identifyQoS7273IPv6HeaderFieldsFlowLabel(20bits)Identifydatagramsinthesame“flow”Payloadlength(16bits)IncludesallextensionheadersplususerdataNextHeader(8bits)IdentifiestypeofthenextheaderExtensionornextlayerupSource/DestinationAddress(128bits)74IPv6Enhancements(1)Expandedaddressspace:128bitImprovedoptionmechanismSeparateoptionalheadersbetweenIPv6headerandtransportlayerheaderMostarenotexaminedbyintermediateroutersEasiertoextendoptionsChecksumremovedtofurtherreduceprocessingtimeateachrouter75IPv6Enhancements(2)IncreasedaddressingflexibilityAnycast–deliveredtooneofasetofnodesScalabilityofmulticastaddressesAddressauto-configurationSupportforresourceallocationUsestrafficclassGroupingpacketstoparticulartrafficflowAllowsQoShandlingotherthanbest-effort,e.g.real-timevideo76IPv6FlowAsequenceofpacketssentfromaparticularsourcetoaparticulardestinationFromhostspointofviewGeneratedfromoneapplicationandhavethesametransferservicerequirementsMaycompriseasingleormultipleTCPconnectionsOneapplicationmaygenerateasingleflowormultipleflowsFromrouterspointofviewShareattributesthataffecthowthesepacketsarehandledbytheroutere.g.routing,resourceallocation,discardrequirements,accounting,andsecurity77FlowLabelAflowisuniquelyidentifiedbythecombinationofSourceanddestinationaddressAnon-zero20-bitFlowLabelFlowrequirementsaredefinedpriortoflowcommencementThenauniqueFlowLabel

isassignedtotheflowRouterdecidehowtorouteandprocessthepacketbySimplylookinguptheFlowLabelinatableandwithoutexaminingtherestoftheheader78IPv6Addresses128bitslong,assignedtointerfaceSingleinterfacemayhavemultipleunicastaddresses3typesofaddressdefinedUnicast,Multicast,AnycastFEDC:BA98:7654:3210:FEDC:BA98:7654:32101080:0:0:0:8:800:200C:417A79ExampleIPv6AddressesDifferentIPv6addressesAunicastaddress1080:0:0:0:8:800:200C:417A,simplifiedas1080::8:800:200C:417AAmulticastaddressFF01:0:0:0:0:0:0:101,simplifiedasFF01::101Theloopbackaddress0:0:0:0:0:0:0:1,simplifiedas::1Unspecifiedaddresses0:0:0:0:0:0:0:0,simplifiedas::IPv4address

IPv6addressx:x:x:x:x:x:d.d.d.d,2possibleways0:0:0:0:0:0:13.1.68.3,simplifiedas::13.1.68.30:0:0:0:0:FFFF:129.144.52.38,simplifiedas::FFFF:129.144.52.3880IPv6

HeaderStructureExtensionHeadersAppearedinorderHop-by-HopOptions:RequireprocessingateachrouterRouting:SourceroutingFragment:sourcefragmentationAuthenticationEncapsulatingsecuritypayloadDestinationoptions:handleatdestination8182IPv6ExtensionHeaders83RoutingHeaderListofoneormoreintermediatenodestobevisitedNextHeader(8bits)Headerextensionlength(8bits)In64bits(8octets)unit,excludingfirst8octetsRoutingtype(8bits)Onlytype0definednowSegmentsleft(8bits)Numberofnodesstilltobevisited84OperationofType0RoutingHeaderAsthepackettravelsfromStoI1:SourceAddress=S HdrExtLen=6

DestinationAddress=I1 SegmentsLeft=3 Address[1]=I2 Address[2]=I3 Address[3]=DAsthepackettravelsfromI1toI2:SourceAddress=S HdrExtLen=6

DestinationAddress=I2 SegmentsLeft=2 Address[1]=I1 Address[2]=I3 Address[3]=DAsthepackettravelsfromI2toI3:SourceAddress=S HdrExtLen=6

DestinationAddress=I3 SegmentsLeft=1 Address[1]=I1 Address[2]=I2 Address[3]=DAsthepackettravelsfromI3toD:SourceAddress=S HdrExtLen=6

DestinationAddress=D SegmentsLeft=0 Address[1]=I1 Address[2]=I2 Address[3]=I385TransitionFromIPv4ToIPv6NotallrouterscanbeupgradedsimultaneouslyHowwillthenetworkoperatewithmixedIPv4andIPv6routersTwoproposedapproachesDualStack–somerouterswithdualstack(IPv6,IPv4)cantranslatebetweenformatsTunneling–IPv6carriedaspayloadinIPv4datagramamongIPv4routers86DualStackApproachABEFIPv6IPv6/v4IPv4/v6IPv6CDIPv4IPv4Flow:XSrc:ADest:FdataFlow:??Src:ADest:FdataSrc:A’Dest:F’dataA-to-B:IPv6Src:A’Dest:F’dataB-to-E:IPv4B-to-E:IPv4B-to-C:IPv6AddresstranslationbetweenIPv4andIPv6isneededSomeIPv6featuresislost87TunnelingABEFIPv6IPv6IPv6IPv6tunnelLogicalview:Physicalview:ABEFIPv6IPv6-v4IPv6-v4IPv6CDIPv4IPv4Flow:XSrc:ADest:FdataFlow:XSrc:ADest:FdataFlow:XSrc:ADest:FdataSrc:BDest:EFlow:XSrc:ADest:FdataSrc:BDest:EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6insideIPv4D-to-E:IPv6insideIPv4LooksOKbutlesseffective88InternetRoutingOurroutingstudythusfar–idealizationAllroutersidentical,network“flat”NottrueinpracticeScale:with200milliondestinationsCannotstorealldestinationsinroutingtablesRoutingtableexchangewouldswamplinksAdministrativeautonomyInternet=networkofnetworksEachnetworkadminmaywanttocontrolroutinginitsownnetworks89HierarchicalRoutingAggregateroutersintoregions,i.e.autonomoussystems(AS)RoutersinsameASrunsameroutingprotocolIntra-ASroutingprotocolRoutersindifferentAScanrundifferentintra-ASroutingprotocolGatewayroutersRoutersinASresponsibleforroutingtodestinationsoutsideASRuninter-ASroutingprotocolwithothergatewayroutersRunintra-ASroutingprotocolwithroutersinAS90AutonomousSystems(AS)SetofroutersandnetworksmanagedbysingleISPorlargeorganizationAconnectedinternetsuniquelyassigneda16-bitor32-bitASNumberThereisatleastoneroutebetweenanypairofnodesUsecommonroutingprotocol91Intra-ASandInter-ASroutingGateways:Performinter-ASroutingamongstthemselvesPerformintra-ASroutingwithotherroutersintheirASinter-AS,intra-ASroutingingatewayA.cnetworklayerlinklayerphysicallayerabbaaCABdA.aA.cC.bB.acbc92RoutingProtocolsRoutingInformationAbouttopologyanddelaysintheInternetRoutingAlgorithmUsedtomakeroutingdecisionsbasedoninformation93IGPandEGPIGP(InteriorGatewayProtocol):forIntra-ASroutingPassesroutinginformationbetweenrouterswithinASCanfocusonperformanceRoutingalgorithmsandtablesmaydifferbetweendifferentASEGP(ExteriorGatewayProtocol):forInter-ASroutingRoutersneedsomeinfoaboutnetworksoutsidetheirASSupportssummaryinformationonreachabilityPolicymaydominateoverperformance94ApplicationofIGPandEGPabbaaCABdA.aA.cC.bB.acbc95CommonProtocolsIGP–Intra-ASprotocolsRIP:RoutingInformationProtocol,usedistancevectorOSPF:OpenShortestPathFirst,uselinkstateIGRP:InteriorGatewayRoutingProtocol(Ciscoproprietary)EGP–Inter-ASprotocolsBGP:BorderGatewayProtocol96Distance-VectorFirstgenerationroutingalgorithmforARPANETEachnode(routerorhost)exchangeinformationwithneighboringnodesNeighborsarebothdirectlyconnectedtosamenetworkNodemaintainsvectorofLinkcostsforeachdirectlyattachednetworkEstimateddistanceandnext-hopvectorsforeachdestinationDVupdatemessagesexchangedbetweenneighborstobuild/updateroutingtablesChangestakelongtimetopropagate97Link-StateSecondgenerationroutingalgorithmforARPANETWhenrouterinitialized,itdetermineslinkcostoneachinterfaceAdvertisessetoflinkcoststoallotherroutersintopologyNotjustneighboringroutersFromthenon,monitorlinkcostsIf

significantchange,routeradvertisesnewsetoflinkcosts98Link-StateEachroutercanconstructtopologyofentireconfigurationCancalculateshortestpathtoeachdest