操作系统课件第4章

CopyrightXuJingdong,Allrightreserved,1,ComputerNetworksChapter4NetworkLayer,XuJingdongDept.ofComputerScienceandInformationSecurityNankaiUniversityxujd,CopyrightXuJingdong,Allrightreserved,2,Thegoalofthischapter,understandprinciplesbehindnetworklayerservicesroutingorpathselectionpacketforwardinghowarouterworksinstantiationandimplementationintheInternet(IP),CopyrightXuJingdong,Allrightreserved,3,Outline,NetworklayerservicesandfunctionInternetProtocol(IP)IPservicecharacteristicsIPaddressesIPdatagramformatIPdatagramforwardingRoutingalgorithmsInternetroutingprotocolsintra-domaininter-domain,CopyrightXuJingdong,Allrightreserved,4,Networklayerandtransportlayer,Networklayer,transportsegmentfromsendingtoreceivinghostonsendingsideencapsulatessegmentsintodatagramsonreceivingside,deliverssegmentstotransportlayernetworklayerprotocolsineveryhost,routerrouterexaminesheaderfieldsinalldatagramspassingthroughit,5,TwoKeyNetwork-LayerFunctions,forwarding:movepacketsfromroutersinputtoappropriaterouteroutputrouting:determineroutetakenbypacketsfromsourcetodest.routingalgorithms,6,Interplaybetweenroutingandforwarding,routertableforwardingtable,7,CopyrightXuJingdong,Allrightreserved,8,Networklayerservice,ConnectionlessServicenoadvancesetupisneededpacketsareinjectedintothenetworkindividuallyandroutedindependentlyofeachotherthepacketsarefrequentlycalleddatagramsthenetworkiscalledadatagramnetworke.g.IPnetwork,CopyrightXuJingdong,Allrightreserved,9,Networklayerservice(cont.),Connection-OrientedServiceapathfromthesourceroutertothedestinationroutermustbeestablishedbeforeanydatapacketscanbesentthisconnectioniscalledaVC(virtualcircuit)link,routerresources(bandwidth,buffers)maybeallocatedtoVC(togetcircuit-likeperformance)thenetworkiscalledavirtual-circuitnetworke.g.ATM,framerelay,X.25,CopyrightXuJingdong,Allrightreserved,10,Networklayerservice:more,guaranteedbandwidth?preservationofinter-packettiming?loss-freedelivery?in-orderdelivery?congestionfeedbacktosender?,Datagramnetworks,nocallsetupatnetworklayerrouters:nostateaboutend-to-endconnectionsnonetwork-levelconceptof“connection”packetsforwardedusingdestinationhostaddresspacketsbetweensamesource-destpairmaytakedifferentpaths,1.Senddata,2.Receivedata,11,Datagramnetworks:example,H2,R1,H4,H3,H5,H1,ForwardingtableinR1,1,2,3,4,ForwardingtableinR1(later),12,Virtualcircuitnetworks:signalingprotocols,usedtosetup,maintainandteardownVCusedinATM,frame-relay,X.25notusedintodaysInternet,1.Initiatecall,2.incomingcall,3.Acceptcall,4.Callconnected,5.Dataflowbegins,6.Receivedata,13,VCimplementation,VCconsistsof:path(linksandrouters)fromsourcetodestinationhostsVCnumbers,onenumberforeachlinkalongpathentriesinforwardingtablesinroutersalongpathpacketbelongingtoaVCcarriesaVCnumberinitsheader(notdestinationhostaddress)VCnumbercanbechangedoneachlink.NewVCnumbercomesfromforwardingtable,14,Virtualcircuitnetworks:example,H2,R1,H4,H3,H5,H1,ForwardingtableinR1,1,2,3,4,Routersmaintainconnectionstateinformation!,10,VCnumber,18,interfacenumber,15,DatagramorVCnetwork:why?,Internet(datagram)dataexchangeamongcomputers“elastic”service,nostricttimingreq.“smart”endsystems(computer)canadapt,performcontrol,errorrecoverysimpleinsidenetwork,complexityat“edge”manylinktypesdifferentcharacteristicsuniformservicedifficult,ATM(VC)evolvedfromtelephonyhumanconversation:stricttiming,reliabilityrequirementsneedforguaranteedservice“dumb”endsystemstelephonescomplexityinsidenetwork,16,CopyrightXuJingdong,Allrightreserved,17,ServiceofInternetNetworklayer,connectionless(datagram-based)Best-effortdelivery(unreliableservice)packetsarelostpacketsaredeliveredoutoforderduplicatecopiesofapacketaredeliveredpacketscanbedelayedforalongtime,CopyrightXuJingdong,Allrightreserved,18,Internetnetworklayer:example,CopyrightXuJingdong,Allrightreserved,19,FunctionofInternetNetworklayer,Transportlayer:TCP,UDP,Linklayer,physicallayer,Networklayer,CopyrightXuJingdong,Allrightreserved,20,IPv4Addressing:introduction,IPaddress:32-bitidentifierforhost,routerinterfaceinterface:connectionbetweenhost,routerandphysicallinkrouterstypicallyhavemultipleinterfaceshostmayhavemultipleinterfacesIPaddressesassociatedwithinterface,nothost,router,,,,,=11011111000000010000000100000001,223,1,1,1,CopyrightXuJingdong,Allrightreserved,21,IPAddressing(cont.),IPaddress:net-id:networkpart(highorderbits)host-id:hostpart(loworderbits)Whatsanetwork?(fromIPaddressperspective)deviceinterfaceswithsamenet-idofIPaddresscanphysicallyreacheachotherwithoutinterveningrouter,,,,,,,,,,7,networkconsistingof3IPnetworks(forIPaddressesstartingwith223,first24bitsarenet-id),LAN,CopyrightXuJingdong,Allrightreserved,22,IPAddressing(cont.),Howtofindthenetworks?Detacheachinterfacefromrouter,hostcreate“islands”ofisolatednetworks,,,,,,,,,7,,,,,,,,Interconnectedsystemconsistingofsixnetworks,CopyrightXuJingdong,Allrightreserved,23,IPAddressing:class,host,A,B,C,D,class,to55,to55,to55,to55,32bits,network,0,E,to55,Class“A”address:1(18ClassA)Class“B”address:55(128ClassB),CopyrightXuJingdong,Allrightreserved,24,IPAddressing(cont.),ClassfulAddressandNetworkSizes:,BitsInPrefix,AddressClass,MaximumNumberofNetworks,BitsInSuffix,MaximumNumberOfHostsPerNetwork,ABC,71421,128163842097152,24168,1677721665536256,Prefix:net-idSuffix:host-id,CopyrightXuJingdong,Allrightreserved,25,IPAddressing(cont.),SpecialAddresses:,NetworkaddressnotusedinpacketsLoopbackneverleaveslocalcomputer,Prefix,Suffix,TypeofAddress,Purpose,all-0snetworknetworkall-1s127,all-0sall-0sall-1sall-1sany,thiscomputernetworkdirectedbroadcastlimitedbroadcastloopback,usedduringbootstrapidentifiesanetworkbroadcastonspecifiednetbroadcastonlocalnettesting,CopyrightXuJingdong,Allrightreserved,26,IPaddresses:howtogetone?,Q:HowdoeshostgetIPaddress?hard-codedbysystemadministratorinafileWindows:control-panel-network-configuration-tcp/ip-propertiesUNIX:/etc/rc.configDHCP:DynamicHostConfigurationProtocol:(RFC2131)dynamicallygetaddress:“plug-and-play”hostbroadcasts“DHCPdiscover”msgDHCPserverrespondswith“DHCPoffer”msghostrequestsIPaddress:“DHCPrequest”msgDHCPserversendsaddress:“DHCPack”msgotherprotocol,CopyrightXuJingdong,Allrightreserved,27,IPdatagramformat,ver,length,32bits,data(variablelength,typicallyaTCPorUDPsegment),16-bitidentifier,Internetchecksum,timetolive,32bitsourceIPaddress,IPprotocolversionnumber,headerlength(4bytes),maxnumberremaininghops(decrementedateachrouter),forfragmentation/reassembly,totaldatagramlength(bytes),upperlayerprotocoltodeliverpayloadto,head.len,typeofservice,“type”ofdata,flgs,fragmentoffset,upperlayer,32bitdestinationIPaddress,Options(ifany),E.g.timestamp,recordroutetaken,specifylistofrouterstovisit.,CopyrightXuJingdong,Allrightreserved,28,IPdatagramformat(cont.),Typeofservicethree-bitprecedencefield:from0(normal)to7(networkcontrolpacket)threeflagbits:Delay,Throughput,ReliabilityFlgsDFstandsforDontFragmentMFstandsforMoreFragments,allfragmentsexceptthelastonehavethisbitset,CopyrightXuJingdong,Allrightreserved,29,Gettingadatagramfromsourcetodest,routingtableinA,IPdatagram:,dataremainsunchanged,asittravelssourcetodestinationaddrfieldsofinteresthere,CopyrightXuJingdong,Allrightreserved,30,Gettingadatagramfromsourcetodest.,StartingatA,dest.B:lookupnet.addressofBfindBisonsamenet.asAlinklayerwillsenddatagramdirectlytoBinsidelink-layerframeBandAaredirectlyconnected,miscfields,,,data,CopyrightXuJingdong,Allrightreserved,31,Gettingadatagramfromsourcetodest.,StartingatA,dest.E:lookupnetworkaddressofEEondifferentnetworkA,Enotdirectlyattachedroutingtable:nexthoproutertoEislinklayersendsdatagramtorouterinsidelink-layerframedatagramarrivesatcontinued.,miscfields,,,data,CopyrightXuJingdong,Allrightreserved,32,Gettingadatagramfromsourcetodest.,Arrivingat,destinedforlookupnetworkaddressofEEonsamenetworkasroutersinterfacerouter,Edirectlyattachedlinklayersendsdatagramtoinsidelink-layerframeviainterfacedatagramarrivesat!,miscfields,,,data,CopyrightXuJingdong,Allrightreserved,33,IPFragmentationnotbyintermediaterouters.Toavoidfragmentation,hostscommonlyusepathMTUdiscoverytofindthesmallestMTUalongthepath.PathMTUdiscoveryinvolvessendingvarioussizedatagramsuntiltheydonotrequirefragmentationalongthepath.MostlinksuseMTU=1500bytestoday,CopyrightXuJingdong,Allrightreserved,36,HowaRouterForwardsIPDatagrams,EverydatagramcontainsadestinationIPaddressTherouterdeterminesnet-idofdestinationIPaddressIsthedatagramforahostonadirectlyattachednetwork?Ifno,consultforwardingtabletofindnext-hopLookupthisnet-idinforwardingtableIfknown,forwardtocorrectportIfunknown,droppacketDecrementTTL,updateheaderChecksumForwardpackettooutgoinginterface,CopyrightXuJingdong,Allrightreserved,37,HowaRouterForwardsDatagrams,,,,,,,D,Port,4,3,3,4,3,4,,,,,,,Next-hop,R1,R2,R3,R4,2,3,4,,,e.g.4Port2,Forwarding/routingtable,1,,,2,,CopyrightXuJingdong,Allrightreserved,38,Insidearouter,Link1,ingress,Link1,egress,Link2,ingress,Link2,egress,Link3,ingress,Link3,egress,Link4,ingress,Link4,egress,ChooseEgress,ChooseEgress,ChooseEgress,ForwardingDecision,ForwardingTable,CopyrightXuJingdong,Allrightreserved,39,IPAddressing:problem,Addressclassesweretoo“rigid”.Formostorganizations,ClassCweretoosmallandClassBtoobig.Ledtoveryinefficientuseofaddressspace,andashortageofaddressesOrganizationswithinternalroutersneededtohaveaseparate(ClassC)net-idforeachlinkAndtheneveryotherrouterintheInternethadtoknowabouteverynet-idineveryorganization,whichledtolargeaddresstablesSmallorganizationswantedClassBincasetheygrewtomorethan255hosts.Buttherewereonlyabout16,000ClassBnet-id,CopyrightXuJingdong,Allrightreserved,40,CERNETMap,29June1999,IP,CopyrightXuJingdong,Allrightreserved,41,IPAddressing:twosolutions,Subnettingisusedwithinanorganizationtosubdividetheorganizationsnet-idClasslessInterdomainRouting(CIDR)wasintroducedin1993toprovidemoreefficientandflexibleuseofIPaddressspaceacrossthewholeInternetCIDRisalsoknownas“supernetting”becausesubnettingandCIDRarebasicallythesameidea,CopyrightXuJingdong,Allrightreserved,42,Subnetting,Addanotherleveltoaddress/routinghierarchy:subnetSubnetmasksdefinevariablepartitionofhostpartSubnetsvisibleonlywithinsite,CopyrightXuJingdong,Allrightreserved,43,Subnetting,CLASS“B”e.g.University,10,Net-ID,Host-ID,2,14,16,10,Net-ID,Host-ID,2,14,16,0000,SubnetID(20),SubnetHostID(12),10,Net-ID,Host-ID,2,14,16,1111,SubnetID(20),SubnetHostID(12),10,Net-ID,Host-ID,2,14,16,000000,SubnetID(22),SubnetHostID(10),10,Net-ID,Host-ID,2,14,16,1111011011,SubnetID(26),SubnetHostID(6),e.g.college,e.g.Dept.,CopyrightXuJingdong,Allrightreserved,44,Subnetting,Subnetsareusuallyrepresentedviaanaddressplusasubnetmaskor“subnetmask”SubnetmaskFFFFFF00:thefirst24bitsarethesubnetID,andthelast8bitsarethehostIDCanalsoberepresentedbya“prefix+length”,e.g./24,CopyrightXuJingdong,Allrightreserved,45,Exampleofsubnetting,ClassBIPaddress:,CopyrightXuJingdong,Allrightreserved,46,SizeoftheRoutingTableatthecoreoftheInternet,Source:,CopyrightXuJingdong,Allrightreserved,47,PrefixLengthDistribution,Source:GeoffHuston,Oct2001,CopyrightXuJingdong,Allrightreserved,48,ClasslessInterdomainRouting(CIDR),CIDR:ClasslessInterDomainRoutingnetworkportionofaddress:arbitrarylengthaddressformat:a.b.c.d/x,wherexis#bitsinnetworkportionofaddress,CopyrightXuJingdong,Allrightreserved,49,CIDR(Cont.),Prefixaggregation:Ifaserviceproviderservestwoorganizationswithprefixes,itcan(sometimes)aggregatethemtoformalargerprefix.Otherrouterscanrefertothislargerprefix,andsoreducethesizeoftheiraddresstableE.g.ISPserves/24and/24,itcantellotherrouterstosenditallpacketsbelongingtotheprefix/23,CopyrightXuJingdong,Allrightreserved,50,CIDR:anexample,ISPsblock11001000000101110001000000000000/20Organization011001000000101110001000000000000/23Organization111001000000101110001001000000000/23Organization211001000000101110001010000000000/23.Organization711001000000101110001111000000000/23,CopyrightXuJingdong,Allrightreserved,51,Hierarchicaladdressing:routeaggregation,“Sendmeanythingwithaddressesbeginning/20”,ISPA,Organization0,Organization7,Internet,Organization1,ISPB,“Sendmeanythingwithaddressesbeginning/16”,Organization2,Hierarchicaladdressingallowsefficientadvertisementofroutinginformation:,CopyrightXuJingdong,Allrightreserved,52,Hierarchicaladdressing:specificroutes,ISPBhasamorespecificroutetoOrganization1,“Sendmeanythingwithaddressesbeginning/20”,ISPA,Organization0,Organization7,Internet,Organization1,ISPB,“Sendmeanythingwithaddressesbeginning/16or/23”,Organization2,CopyrightXuJingdong,Allrightreserved,53,Longestmatchingprefix,“Sendmeanythingwithaddressesbeginning/20”,ISPA,Internet,ISPB,“Sendmeanythingwithaddressesbeginning/16or/23”,/16,/23,/20,Prefix,Port,1,2,2,,Next-hop,e.g.0=ISPB,Forwarding/routingtable,1,2,,,,,NankaiIP:-55(32classC)-55(32classC)-55(32classC),CopyrightXuJingdong,Allrightreserved,54,PrivateIPAddresses,PublicIPaddressesaregloballyunique,andareallocatedbytheRegionalInternetRegistries(RIRs)orISPsPrivateIPaddressesarenon-routeableglobally,andareavailablefreelyNetworkAddressTranslators(NATs)to551ClassAnetworkto5516ClassBnetworksto55256ClassCnetworks,NAT:NetworkAddressTranslation,,,,,,localnetwork(e.g.,homenetwork)/24,restofInternet,Datagramswithsourceordestinationinthisnetworkhave/24addressforsource,destination(asusual),AlldatagramsleavinglocalnetworkhavesamesinglesourceNATIPaddress:,differentsourceportnumbers,55,NAT:NetworkAddressTranslation,Motivation:localnetworkusesjustoneIPaddressasfarasoutsideworldisconcerned:rangeofaddressesnotneededfromISP:justoneIPaddressforalldevicescanchangeaddressesofdevicesinlocalnetworkwithoutnotifyingoutsideworldcanchangeISPwithoutchangingaddressesofdevicesinlocalnetworkdevicesinsidelocalnetnotexplicitlyaddressable,visiblebyoutsideworld(asecurityplus).,56,NAT:NetworkAddressTranslation,Implementation:NATroutermust:outgoingdatagrams:replace(sourceIPaddress,port#)ofeveryoutgoingdatagramto(NATIPaddress,newport#).remoteclients/serverswillrespondusing(NATIPaddress,newport#)asdestinationaddr.remember(inNATtranslationtable)every(sourceIPaddress,port#)to(NATIPaddress,newport#)translationpairincomingdatagrams:replace(NATIPaddress,newport#)indestfieldsofeveryincomingdatagramwithcorresponding(sourceIPaddress,port#)storedinNATtable,57,NAT:NetworkAddressTranslation,,,,,,NATtranslationtableWANsideaddrLANsideaddr,,500,3345,3:Replyarrivesdest.address:,5001,4:NATrouterchangesdatagramdestaddrfrom,5001to,3345,58,NAT:NetworkAddressTranslation,16-bitport-numberfield:60,000simultaneousconnectionswithasingleLAN-sideaddress!NATiscontroversial:routersshouldonlyprocessuptolayer3violatesend-to-endargumentNATpossibilitymustbetakenintoaccountbyappdesigners,eg,P2PapplicationsaddressshortageshouldinsteadbesolvedbyIPv6,59,NATtraversalproblem,clientwantstoconnecttoserverwithaddressserveraddresslocaltoLAN(clientcantuseitasdestinationaddr)onlyoneexternallyvisibleNATaddress:,,,NATrouter,,Client,?,60,NATtraversalproblem,solution1:staticallyconfigureNATtoforwardincomingconnectionrequestsatgivenporttoservere.g.,(,port2500)alwaysforwardedtoport25000,,,NATrouter,,Client,61,NATtranslationtableWANsideaddrLANsideaddr,,2500,25000,NATtraversalproblem,solution2:UniversalPlugandPlay(UPnP)InternetGatewayDevice(IGD)Protocol.AllowsNAThostto:learnpublicIPaddress()add/removeportmappings(withleasetimes)i.e.,automatestaticNATportmapconfiguration,,,NATrouter,,Client,IGD,62,NATtranslationtableWANsideaddrLANsideaddr,,80,80,NATtraversalproblem,solution3:relaying(usedinSkype)NATclientestablishesconnectiontorelayExternalclientconnectstorelayrelaybridgespacketsbetweentoconnections,,Client,1.connectiontorelayinitiatedbyNAThost,2.connectiontorelayinitiatedbyclient,3.relayingestablished,63,CopyrightXuJingdong,Allrightreserved,64,ICMP:InternetControlMessageProtocol,Usedbyhosts,routerstocommunicatenetwork-levelinformationICMPerrormessagesDestinationUnreachable（RFC-792，RFC-1122）RedirectSourceQuenchTimeExceededParameterProblemICMPquerymessagesEchoInformationTimestampAddressMask（RFC-950）,CopyrightXuJingdong,Allrightreserved,65,ICMP:InternetControlMessageProtocol,TypeCtocolunreachable33dest.portunreachable34fragmentneededandDFset35sourceroutefailed50redire