操作系统课件第1章

CopyrightXuJingdong,Allrightreserved,1,ComputerNetworksChapter1Basic,XuJingdongDept.ofComputerScienceandInformationSecurityNankaiUniversityxujd,CopyrightXuJingdong,Allrightreserved,2,Outline,whattheInternetnetworkedge:hosts,accessnet,physicalmedianetworkcore:packet/circuitswitching,Internetstructureperformance:loss,delay,throughputinpacket-switchednetworksprotocolandlayeringexample:FTPovertheInternet,CopyrightXuJingdong,Allrightreserved,3,?,WhatstheInternetinyoureye?,YourComputerConnectedtotheInternet,LocallinktotheInternet,InternetServices,CopyrightXuJingdong,Allrightreserved,4,Internet:theserviceview,World-widecommunicationinfrastructure:supportdistributedapplications,e.g.,Web,Email,FTP,VoIP,games,BT,QQ,WeChatcommunicationservicesprovidedtoapps:reliabledatadeliveryfromsourcetodestination“besteffort”(unreliable)datadeliveryclient-server(C/S)orpeer-to-peer(P2P)model,CopyrightXuJingdong,Allrightreserved,5,Internet:“nutsandbolts”view,Internet:“networkofnetworks”orinternetworkinglooselyhierarchicalpublicInternetversusprivateintranetmillionsofconnectedcomputingdevices:hosts,end-systems,runningnetworkappsPCServersMobilePhones,CopyrightXuJingdong,Allrightreserved,6,Internet:“nutsandbolts”view(cont.),routers:forwardpackets(chunks)ofdatathroughnetworkcommunicationlinksfiber,copper,radio,satelliteprotocols:controlsending,receivingofmessagese.g.,TCP,IP,HTTP,FTP,PPP,CopyrightXuJingdong,Allrightreserved,7,Internetstructure:networkofnetworks,roughlyhierarchicalnational/internationalbackboneproviders(NBPs)e.g.UUnet/WorldCom/MCI,Sprint,ATemailclient/server,peer-peermodel:minimal(orno)useofdedicatedserverse.g.Skype,BitTorrent,13,Accessnetworksandphysicalmedia,Q:Howtoconnectendsystemstoedgerouter?residentialaccessnetsinstitutionalaccessnetworks(school,company)mobileaccessnetworksKeepinmind:bandwidth(bitspersecond)ofaccessnetwork?sharedordedicated?,14,CopyrightXuJingdong,Allrightreserved,15,Residentialaccess:pointtopointaccess,Dialupviamodemupto56Kbpsdirectaccesstorouter(oftenless)Cantsurfandphoneatsametime:cantbe“alwayson”DSL:DigitalSubscriberLinedeployment:telephonecompany(typically)upto1Mbpsupstream(todaytypically256kbps)upto8Mbpsdownstream(todaytypically1Mbps)dedicatedphysicallinetotelephonecentraloffice,CopyrightXuJingdong,Allrightreserved,16,Residentialaccess:cablemodems,HFC:hybridfibercoaxasymmetric:upto30Mbpsdownstream,2MbpsupstreamnetworkofcableandfiberattacheshomestoISProuterhomesshareaccesstorouterdeployment:availableviacableTVcompanies,CopyrightXuJingdong,Allrightreserved,17,Residentialaccess:cablemodems,Diagram:,CopyrightXuJingdong,Allrightreserved,18,Institutionalaccess:localareanetworks,company/universitylocalareanetwork(LAN)connectsendsystemtoedgerouterEthernet:10Mbps,100Mbps,1Gbps,10GbpsEthernetmodernconfiguration:endsystemsconnectintoEthernetswitch,CopyrightXuJingdong,Allrightreserved,19,Wirelessaccessnetworks,sharedwirelessaccessnetworkconnectsendsystemtorouterviabasestationaka“accesspoint”wirelessLANs:IEEE802.11a/b/g:54MbpsIEEE802.11n:600Mbps。wider-areawirelessaccess3G:cellularsystemCDMA2000:3.1/1.8Mbps,TD-SCDMA:2.8/2.2MbpsWCDMA:14.4/5.76Mbps4G:TD-LTE:100/50Mbps5G:?,basestation,mobilehosts,router,Homenetworks,Typicalhomenetworkcomponents:DSLorcablemodemrouter/firewall/NATEthernetwirelessaccesspoint,wirelessaccesspoint,wirelesslaptops,router/firewall,cablemodem,to/fromcableheadend,Ethernet,20,CopyrightXuJingdong,Allrightreserved,21,PhysicalMedia,Bit:propagatesbetweentransmitter/receiverpairsphysicallink:whatliesbetweentransmitter&receiverguidedmedia:signalspropagateinsolidmedia:copper,fiber,coaxunguidedmedia:signalspropagatefreely,e.g.,radio,CopyrightXuJingdong,Allrightreserved,22,PhysicalMedia:TwistedPair,TwistedPair(TP)twoinsulatedcopperwiresCategory3:traditionalphonewires,10MbpsEthernetCategory5:100MbpsEthernet,CopyrightXuJingdong,Allrightreserved,23,PhysicalMedia:coax,Coaxialcabletwoconcentriccopperconductorsbidirectionalbaseband:singlechanneloncablelegacyEthernetbroadband:multiplechannelsoncableHFC,CopyrightXuJingdong,Allrightreserved,24,PhysicalMedia:fiber,Fibercableglassfibercarryinglightpulses,eachpulseabithigh-speedoperation:high-speedpoint-to-pointtransmission(e.g.,10s-100sGps)lowerrorrate:immunetoelectromagneticnoise,CopyrightXuJingdong,Allrightreserved,25,Physicalmedia:radio,signalcarriedinelectromagneticspectrumnophysical“wire”Bidirectionalpropagationenvironmenteffects:reflectionobstructionbyobjectsinterference,RadiolinktypesTerrestrialmicrowavee.g.upto45MbpschannelsWirelessLAN(e.g.WiFi)54Mbps,150Mbpswide-area(e.g.,cellular)3G,1MbpssatelliteKbpsto45Mbpschannel(ormultiplesmaller270millisecondend-enddelay,CopyrightXuJingdong,Allrightreserved,26,Thenetworkcore:,meshofinterconnectedroutersfundamentalquestion:howisdatatransferredthroughnet?circuitswitching:dedicatedcircuitpercall:telephonenetpacket-switching:datasentthroughnetworkindiscrete“chunks”,CopyrightXuJingdong,Allrightreserved,27,NetworkCore:CircuitSwitching,Itsthemethodusedbythetelephonenetworkcallsetuprequired:threephasesEstablishcircuitfromend-to-end(“dialing”),Communicate,Closecircuit(“teardown”).Originally,acircuitwasanend-to-endphysicalwireNowadays,acircuitislikeavirtualprivatewire,CopyrightXuJingdong,Allrightreserved,28,NetworkCore:CircuitSwitching,End-endresourcesreservedfor“call”linkbandwidth,switchcapacitydedicatedresources:nosharingcircuit-like(guaranteed)workresources(e.g.,bandwidth)dividedinto“pieces”piecesallocatedtocallsresourcepieceidleifnotusedbyowningcall(nosharing)dividinglinkbandwidthinto“pieces”frequencydivisiontimedivision,CopyrightXuJingdong,Allrightreserved,29,CircuitSwitching:FDMandTDM,Anexample,Howlongdoesittaketosendafileof640,000bitsfromhostAtohostBoveracircuit-switchednetwork?Alllinksare1.536MbpsEachlinkusesTDMwith24slots/sec500msectoestablishend-to-endcircuitLetsworkitout!,Rate1.536Mbps/24=64,000bpsTotaltime500ms+640000/64000s=10500ms,30,CopyrightXuJingdong,Allrightreserved,31,Source“Caller”,CentralOffice“C.O.”,Destination“Callee”,CentralOffice“C.O.”,TrunkExchange,CircuitSwitching:TelephoneNetwork,CopyrightXuJingdong,Allrightreserved,32,NetworkCore:PacketSwitching,ItsthemethodusedbytheInternetEachend-enddatastreamdividedintopacketsEachpacketisindividuallyroutedpacket-by-packet,usingtherouterslocalroutingtableDifferentpacketsmaytakedifferentpathsSeveralpacketsmayarriveforthesameoutputlinkatthesametime,thereforeapacketswitchhasbuffers,CopyrightXuJingdong,Allrightreserved,33,NetworkCore:PacketSwitching,packetsuserA,Bpacketssharenetworkresourcesstatisticalmultiplexingresourcesusedasneededresourcecontentionaggregateresourcedemandcanexceedamountavailablecongestion:packetsqueue,waitforlinkusestoreandforward:packetsmoveonehopatatimetransmitoverlinkwaitturnatnextlink,CopyrightXuJingdong,Allrightreserved,34,NetworkCore:PacketSwitching,A,B,C,10MbsEthernet,1.5Mbs,45Mbs,statisticalmultiplexing,queueofpacketswaitingforoutputlink,SequenceofA&Bpacketsdoesnothavefixedpattern,bandwidthsharedondemandstatisticalmultiplexing.TDM:eachhostgetssameslotinrevolvingTDMframe.,CopyrightXuJingdong,Allrightreserved,35,Linkrate,R,X(t),Droppedpackets,B,Droppedpackets,QueueLengthX(t),Time,Packetbuffer,Packetsforoneoutput,PacketSwitching&StatisticalMultiplexing,Data,Hdr,Data,Hdr,Data,Hdr,R,R,R,Becausethebufferabsorbstemporarybursts,theegresslinkneednotoperateatrateN.R.Butthebufferhasfinitesize,B,solosseswilloccur.,1,2,N,CopyrightXuJingdong,Allrightreserved,36,StatisticalMultiplexing,B,A,time,time,Rate,Rate,C,C,A,C,B,C,CopyrightXuJingdong,Allrightreserved,37,StatisticalMultiplexingGain,A,B,R,2C,R2C,A+B,time,Rate,Statisticalmultiplexinggain=2C/R,CopyrightXuJingdong,Allrightreserved,38,StatisticalMultiplexingMore,rate,Oneflow,time,CopyrightXuJingdong,Allrightreserved,39,StatisticalMultiplexingMore,rate,Twoflow,time,Averagerate,CopyrightXuJingdong,Allrightreserved,40,StatisticalMultiplexingMore,rate,Manyflow,time,Averageratesof:1,2,10,100,1000flows.,Networktrafficisbursty.i.e.theratechangesfrequently.Peaksfromindependentflowsgenerallyoccuratdifferenttimes.Conclusion:Themoreflowswehave,thesmootherthetraffic.,CopyrightXuJingdong,Allrightreserved,41,Packet-switchednetworks:routing,Goal:movepacketsamongroutersfromsourcetodestinationwellstudyseveralpathselectionalgorithmslater(chap.4)!datagramnetwork:destinationaddressdeterminesnexthoproutesmaychangeduringsessionanalogy:driving,askingdirectionsvirtualcircuitnetwork:eachpacketcarriestag(virtualcircuitID),tagdeterminesnexthopfixedpathdeterminedatcallsetuptime,remainsfixedthrucallroutersmaintainper-callstate,CopyrightXuJingdong,Allrightreserved,42,PacketSwitching:Simpleroutermodel,R1,Link1,Link2,Link3,Link4,Link1,ingress,Link1,egress,Link2,ingress,Link2,egress,Link3,ingress,Link3,egress,Link4,ingress,Link4,egress,ChooseEgress,ChooseEgress,ChooseEgress,ChooseEgress,CopyrightXuJingdong,Allrightreserved,43,SomeDefinitions,Packetlength,P,isthelengthofapacketinbitsLinklength,L,isthelengthofalinkinmetersDatarate,R,istherateatwhichbitscanbesent,inbits/second,orb/s1Propagationdelay,PROP,isthetimeforonebittotravelalongalinkoflength,LPROP=L/c.Transmissiontime,TRANSP,isthetimetotransmitapacketoflengthPTRANSP=P/RLatencyisthetimefromwhenthefirstbitbeginstransmission,untilthelastbithasbeenreceived.Onalink:Latency=PROP+TRANSP,1.Notethatakilobit/second,kb/s,is1000bits/second,not1024bits/second.,CopyrightXuJingdong,Allrightreserved,44,PacketSwitching,HostA,HostB,R1,R2,R3,R1,R2,R4,R3,TRANSP1,TRANSP2,TRANSP3,TRANSP4,PROP1,PROP2,PROP3,PROP4,Source,Destination,“Store-and-Forward”ateachRouter,CopyrightXuJingdong,Allrightreserved,45,PacketSwitching,Breakingmessageintopacketsallowsparalleltransmissionacrossalllinks,reducingendtoendlatencyItalsopreventsalinkorbufferfrombeing“hogged”foralongtimebyonemessage,HostA,HostB,R1,R2,R3,M/R,HostA,HostB,R1,R2,R3,M/R,Q:Whynotsendtheentiremessageinonepacket?,.,CopyrightXuJingdong,Allrightreserved,46,PacketSwitching:QueueingDelay,HostA,HostB,R1,R2,R3,TRANSP1,TRANSP2,TRANSP3,TRANSP4,PROP1,PROP2,PROP3,PROP4,Q2,Becausetheegresslinkisnotnecessarilyfreewhenapacketarrives,itmaybequeuedinabuffer.Ifthenetworkisbusy,packetsmighthavetowaitalongtime.,CopyrightXuJingdong,Allrightreserved,47,QueuesandQueueingDelay,Tounderstandtheperformanceofapacketswitchednetwork,wecanthinkofitasaseriesofqueuesinterconnectedbylinksForgivenlinkratesandlengths,theonlyvariableisthequeueingdelayIfwecanunderstandthequeueingdelay,wecanunderstandhowthenetworkperforms,CopyrightXuJingdong,Allrightreserved,48,Packetswitchingversuscircuitswitching,1Mbitlinkeachuser:100Kbpswhen“active”active10%oftimecircuit-switching:10userspacketswitching:moreusers,Packetswitchingallowsmoreuserstousenetwork!,CopyrightXuJingdong,Allrightreserved,49,Packetswitchingversuscircuitswitching,PacketswitchingGreatforburstydataresourcesharingnocallsetupExcessivecongestion:packetdelayandlossprotocolsneededforreliabledatatransfer,congestioncontrolQ:Howtoprovidecircuit-likebehavior?bandwidthguaranteesneededforaudio/videoappsQoS:stillanunsolvedproblem!,CopyrightXuJingdong,Allrightreserved,50,WhydoesInternetusepacketswitching?,Efficientuseofexpensivelinks:ThelinksareassumedtobeexpensiveandscarcePacketswitchingallowsmany,burstyflowstosharethesamelinkefficiently“Circuitswitchingisrarelyusedfordatanetworks,.becauseofveryinefficientuseofthelinks”DataNetworks,RobertG.Gallager,MITResiliencetofailureoflinks&routers:“Forhighreliability,.theInternetwastobeadatagramsubnet,soifsomelinesandroutersweredestroyed,messagescouldbe.rerouted”ComputerNetworks,Tanenbaum,CopyrightXuJingdong,Allrightreserved,51,Whatsaprotocol?,humanprotocols:whattimeisit?networkprotocols:machinesratherthanhumansallcommunicationactivityinInternetgovernedbyprotocols,Protocols:defineformat,orderofmessagessentandreceivedamongnetworkentities,andactionstakenonmessagetransmission,receipt,Note:twoormorecommunicatingentitiesrunningthesameprotocols,CopyrightXuJingdong,Allrightreserved,52,Whatsaprotocol?,ahumanprotocolandacomputernetworkprotocol,Hi,Hi,TCPconnectionreq.,CopyrightXuJingdong,Allrightreserved,53,Organizationofairtravel,aseriesofsteps,ticket(purchase)baggage(check)gates(load)runwaytakeoffairplanerouting,ticket(complain)baggage(claim)gates(unload)runwaylandingairplanerouting,airplanerouting,Layeringofairlinefunctionality,Layers:eachlayerimplementsaserviceviaitsowninternal-layeractionsrelyingonservicesprovidedbylayerbelow,Introduction1-54,CopyrightXuJingdong,Allrightreserved,55,Distributedimplementationoflayerfunctionality,CopyrightXuJingdong,Allrightreserved,56,Whylayering?,Dealingwithcomplexsystems:explicitstructureallowsidentification,relationshipofcomplexsystemspieceslayeredreferencemodelfordiscussionmodularizationeasesmaintenance,updatingofsystemchangeofimplementationoflayersservicetransparenttorestofsysteme.g.,changeingateproceduredoesntaffectrestofsystemQ:layeringconsideredharmful?,CopyrightXuJingdong,Allrightreserved,57,Layering:OSIreferencemodel,Session,Network,DataLink,Physical,Physical,Physical,Application,Presentation,Transport,Network,DataLink,DataLink,Network,Transport,Session,Presentation,Application,Network,DataLink,Physical,Peer-layercommunication,layer-to-layercommunication,Router,Router,1,2,3,4,5,6,7,1,2,3,4,5,6,7,Host,Host,CopyrightXuJingdong,Allrightreserved,58,FunctionofISOLayers,Layer1:PhysicalHowtransmittingrawbitsovercommunicationchannelCoding,etc.Layer2:DataLinkPoint-to-pointprotocolErrorchecking,Reliability,FlowcontrolControlaccesstothesharedchannel(broadcastnetwork)Layer3:NetworkPacketforwarding:howpacketsareroutedfromsourcetodestinationLayer4:TransportEnd-to-endprotocolReliability,Flowcontrol,Congestioncontrol,CopyrightXuJingdong,Allrightreserved,59,FunctionofISOLayers(Cont.),Layer5:SessionDialogcontrolSynchronizationLayer6:PresentationSyntaxandsemanticsofinformationtransmittedFormattransform,datacompressing,encrypt/decryptLayer7:ApplicationIndividualapplicationprogramProvidingservicetouser,CopyrightXuJingdong,Allrightreserved,60,Layering:TCP/IPmodel,Network,DataLink,Physical,Physical,Physical,Application,Transport,Network,DataLink,DataLink,Network,Transport,Network,DataLink,Physical,Peer-layercommunication,Router,Router,1,2,3,4,5,1,2,3,4,Application,5,Note:linklayer+physicallayerinterfacelayer,CopyrightXuJingdong,Allrightreserved,61,OSImodelvs.TCP/IPmodel,The7-layerOSIModel,The5-layerTCP/IPmodel,Session,Physical,Application,Presentation,Transport,Network,DataLink,1,2,3,4,5,6,7,Physical,DataLink,Network,Transport,1,2,3,4,Application,5,CopyrightXuJingdong,Allrightreserved,62,TCP/IPprotocolstack,Application:supportingnetworkapplicationsftp,smtp,httpTransport:host-hostdatatransfertcp,udpNetwork:routingofdatagramsfromsourcetodestinationip,routingprotocolsDatalink:datatransferbetweenneighboringnetworkelementsppp,ethernetPhysical:bits“onthewire”,CopyrightXuJingdong,Allrightreserved,63,Layering:distributedentities,Eachlayer:distributed“entities”implementlayerfunctionsateachnodeentitiesperformactions,exchangemessageswithpeers,CopyrightXuJingdong,Allrightreserved,64,Layering:logicalcommunication,E.g.:transporttakedatafromappaddaddressing,reliabilitycheckinfotoform“datagram”senddatagramtopeerwaitforpeertoackreceipt,CopyrightXuJingdong,Allrightreserved,65,Layering:physicalcommunication,source,applicationtransportnetworklinkphysical,segment,datagram,destination,applicationtransportnetworklinkphysical,router,Encapsulation,message,frame,Introduction1-66,CopyrightXuJingdong,Allrightreserved,67,Example:FTPovertheInternet,App,OS,R2,R3,R4,R1,R5,Ethernet,“A”,“B”,Ethernet,App,OS,CopyrightXuJingdong,Allrightreserved,68,Inthesendinghost,Application-ProgrammingInterface(API)(1)ApplicationrequestsTCPconnectionwith“B”TransmissionControlProtocol(TCP)(2)CreatesTCP“Connectionsetup”segmentTCPrequestsIPpackettobesentto“B”,TCPData,TCPHeader,TCPSegment,Type=ConnectionSetup,Empty,CopyrightXuJingdong,Allrightreserved,69,Inthesendinghost,InternetProtocol(IP)(3)CreatesIPpacketwithcorrectaddressesIPrequestspackettobesenttorouter,IPData,TCPSegment,Encapsulation,IPHeader,IPPacket,DestinationAddress:IP“B”SourceAddress:IP“A”Protocol=TCP,CopyrightXuJingdong,Allrightreserved,70,Inthesendinghost,Link(“MAC”orEthernet)Protocol(4)CreatesMACframewithFrameCheckSequence(FCS)WaitforAccesstothelineMACrequestsPHYtosendeachbitoftheframe,EthernetData,IPPacket,EthernetFCS,EthernetHeader,EthernetPacket,DestinationAddress:MAC“R1”SourceAddress:MAC“A”Protocol=IP,Encapsulation,CopyrightXuJingdong,Allrightreserved,71,InRouterR1,Link(“MAC”orEthernet)Protocol(5)AcceptMACframe,checkaddressandFrameCheckSequence(FCS)PassdatatoIPProtocol.,EthernetData,IPPacket,EthernetFCS,EthernetHeader,EthernetPacket,DestinationAddress:MAC“R1”SourceAddress:MAC“A”Protocol=IP,Decapsulation,CopyrightXuJingdong,Allrightreserved,72,InRouterR1,InternetProtocol(IP)(6)UseIPdestinationaddresstodecidewheretosendpacketnext(“next-hoprouting”).RequestLinkProtocoltotransmitpacket,IPData,IPHeader,IPPacket,DestinationAddress: