計(jì)算機(jī)網(wǎng)絡(luò)自頂向下方法英文

1、Network Layer4-1Chapter 4Network LayerA note on the use of these ppt slides:Were making these slides freely available to all (faculty, students, readers). Theyre in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously rep

2、resent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, wed like people to use our book!) If you post any slides in substantially unaltered form on a www site

3、, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material.Thanks and enjoy! JFK/KWRAll material copyright 1996-2007J.F Kurose and K.W. Ross, All Rights ReservedComputer Networking: A Top Down Approach 4th edition. Jim Kurose, Keith RossA

4、ddison-Wesley, July 2007. Network Layer4-2Chapter 4: Network LayerChapter goals: understand principles behind network layer services:network layer service modelsforwarding versus routinghow a router worksrouting (path selection)dealing with scaleadvanced topics: IPv6, mobilityinstantiation, implemen

5、tation in the InternetNetwork Layer4-3Chapter 4: Network Layer4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv64.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the Intern

6、etRIPOSPFBGP4.7 Broadcast and multicast routingNetwork Layer4-4Network layertransport segment from sending to receiving host on sending side encapsulates segments into datagramson rcving side, delivers segments to transport layernetwork layer protocols in every host, routerrouter examines header fie

7、lds in all IP datagrams passing through itapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalne

8、tworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalNetwork Layer4-5Two Key Network-Layer Functionsforwarding: move packets from routers input to appropriate router outputrouting: determine route taken by packets from source to dest. routing algorithmsanalog

9、y:routing: process of planning trip from source to destforwarding: process of getting through single interchangeNetwork Layer4-61230111value in arrivingpackets headerrouting algorithmlocal forwarding tableheader valueoutput link01000101011110013221Interplay between routing and forwardingNetwork Laye

10、r4-7Connection setup3rd important function in some network architectures:ATM, frame relay, X.25before datagrams flow, two end hosts and intervening routers establish virtual connectionrouters get involvednetwork vs transport layer connection service:network: between two hosts (may also involve inerv

11、ening routers in case of VCs)transport: between two processesNetwork Layer4-8Network service modelQ: What service model for “channel” transporting datagrams from sender to receiver?Example services for individual datagrams:guaranteed deliveryguaranteed delivery with less than 40 msec delayExample se

12、rvices for a flow of datagrams:in-order datagram deliveryguaranteed minimum bandwidth to flowrestrictions on changes in inter-packet spacingNetwork Layer4-9Network layer service models:NetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrategu

13、aranteed minimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno (inferredvia loss)nocongestionnocongestionyesnoGuarantees ?Network Layer4-10Chapter 4: Network Layer4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet Protoc

14、olDatagram formatIPv4 addressingICMPIPv64.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routingNetwork Layer4-11Network layer connection and connection-less servicedatagram network provides network-layer connectionle

15、ss serviceVC network provides network-layer connection serviceanalogous to the transport-layer services, but:service: host-to-hostno choice: network provides one or the otherimplementation: in network coreNetwork Layer4-12Virtual circuitscall setup, teardown for each call before data can floweach pa

16、cket carries VC identifier (not destination host address)every router on source-dest path maintains “state” for each passing connectionlink, router resources (bandwidth, buffers) may be allocated to VC (dedicated resources = predictable service)“source-to-dest path behaves much like telephone circui

17、t”performance-wisenetwork actions along source-to-dest pathNetwork Layer4-13VC implementationa VC consists of:path from source to destinationVC numbers, one number for each link along pathentries in forwarding tables in routers along pathpacket belonging to VC carries VC number (rather than dest add

18、ress)VC number can be changed on each link.New VC number comes from forwarding tableNetwork Layer4-14Forwarding table122232123VC numberinterfacenumber ing interface ing VC # Outgoing interface Outgoing VC #1 12 3 222 63 1 18 3 7 2 171 97 3 87 Forwarding table innorthwest router:Routers maintain conn

19、ection state information!Network Layer4-15Virtual circuits: signaling protocolsused to setup, maintain teardown VCused in ATM, frame-relay, X.25not used in todays Internetapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Initiate call2. ing call3. Accept call

20、4. Call connected5. Data flow begins6. Receive dataNetwork Layer4-16Datagram networksno call setup at network layerrouters: no state about end-to-end connectionsno network-level concept of “connection”packets forwarded using destination host addresspackets between same source-dest pair may take diff

21、erent pathsapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataNetwork Layer4-17Forwarding table Destination Address Range Link Interface 11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111 11001000 00010111

22、 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 34 billion possible entriesNetwork Layer4-18Longest prefix matching Prefix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 000

23、11000 1 11001000 00010111 00011 2 otherwise 3DA: 11001000 00010111 00011000 10101010 ExamplesDA: 11001000 00010111 00010110 10100001 Which interface?Which interface?Network Layer4-19Datagram or VC network: why?Internet (datagram)data exchange among computers“elastic” service, no strict timing req. “

24、smart” end systems (computers)can adapt, perform control, error recoverysimple inside network, complexity at “edge”many link types different characteristicsuniform service difficultATM (VC)evolved from telephonyhuman conversation: strict timing, reliability requirementsneed for guaranteed service“du

25、mb” end systemstelephonescomplexity inside networkNetwork Layer4-20Chapter 4: Network Layer4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv64.5 Routing algorithmsLink stateDistance VectorHierarchical rou

26、ting4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routingNetwork Layer4-21Router Architecture OverviewTwo key router functions: run routing algorithms/protocol (RIP, OSPF, BGP)forwarding datagrams from ing to outgoing linkNetwork Layer4-22Input Port FunctionsDecentralized switchin

27、g: given datagram dest., lookup output port using forwarding table in input port memorygoal: complete input port processing at line speedqueuing: if datagrams arrive faster than forwarding rate into switch fabricPhysical layer:bit-level receptionData link layer:e.g., Ethernetsee chapter 5Network Lay

28、er4-23Three types of switching fabricsNetwork Layer4-24Switching Via MemoryFirst generation routers: traditional computers with switching under direct control of CPUpacket copied to systems memory speed limited by memory bandwidth (2 bus crossings per datagram)InputPortOutputPortMemorySystem BusNetw

29、ork Layer4-25Switching Via a Busdatagram from input port memory to output port memory via a shared busbus contention: switching speed limited by bus bandwidth32 Gbps bus, Cisco 5600: sufficient speed for access and enterprise routersNetwork Layer4-26Switching Via An Interconnection Network e bus ban

30、dwidth limitationsBanyan networks, other interconnection nets initially developed to connect processors in multiprocessoradvanced design: fragmenting datagram into fixed length cells, switch cells through the fabric. Cisco 12000: switches 60 Gbps through the interconnection networkNetwork Layer4-27O

31、utput PortsBuffering required when datagrams arrive from fabric faster than the transmission rateScheduling discipline chooses among queued datagrams for transmissionNetwork Layer4-28Output port queueingbuffering when arrival rate via switch exceeds output line speedqueueing (delay) and loss due to

32、output port buffer overflow!Network Layer4-29How much buffering?RFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) times link capacity Ce.g., C = 10 Gps link: 2.5 Gbit bufferRecent mendation: with N flows, buffering equal to RTT C.NNetwork Layer4-30Input Port QueuingFabr

33、ic slower than input ports combined - queueing may occur at input queues Head-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forwardqueueing delay and loss due to input buffer overflow!Network Layer4-31Chapter 4: Network Layer4. 1 Introduction4.2 V

34、irtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv64.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routingNetwork Layer4-32The Internet Network

35、 layerforwardingtableHost, router network layer functions:Routing protocolspath selectionRIP, OSPF, BGPIP protocoladdressing conventionsdatagram formatpacket handling conventionsICMP protocolerror reportingrouter “signaling”Transport layer: TCP, UDPLink layerphysical layerNetworklayerNetwork Layer4-

36、33Chapter 4: Network Layer4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv64.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multic

37、ast routingNetwork Layer4-34IP datagram formatverlength32 bitsdata (variable length,typically a TCP or UDP segment)16-bit identifierheader checksumtime tolive32 bit source IP addressIP protocol versionnumberheader length (bytes)max numberremaining hops(decremented at each router)forfragmentation/rea

38、ssemblytotal datagramlength (bytes)upper layer protocolto deliver payload tohead.lentype ofservice“type” of data flgsfragment offsetupper layer32 bit destination IP addressOptions (if any)E.g. timestamp,record routetaken, specifylist of routers to visit.how much overhead with TCP?20 bytes of TCP20 b

39、ytes of IP= 40 bytes + app layer overheadNetwork Layer4-35IP Fragmentation & Reassemblynetwork links have MTU (max.transfer size) - largest possible link-level frame.different link types, different MTUs large IP datagram divided (“fragmented”) within netone datagram es several datagrams“reassembled”

40、 only at final destinationIP header bits used to identify, order related fragmentsfragmentation: in: one large datagramout: 3 smaller datagramsreassemblyNetwork Layer4-36IP Fragmentation and ReassemblyID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=185fragflag=1length=15

41、00ID=xoffset=370fragflag=0length=1040One large datagram esseveral smaller datagramsExample4000 byte datagramMTU = 1500 bytes1480 bytes in data fieldoffset =1480/8 Network Layer4-37Chapter 4: Network Layer4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Inter

42、net ProtocolDatagram formatIPv4 addressingICMPIPv64.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routingNetwork Layer4-38IP Addressing: introductionIP address: 32-bit identifier for host, router interface interface:

43、 connection between host/router and physical linkrouters typically have multiple interfaceshost typically has one interfaceIP addresses associated with each interface7 = 11011111 00000001 00000001 00000001223111Network Layer4-39SubnetsIP address: subnet part (high order bits)host part (low order bit

44、s) Whats a subnet ?device interfaces with same subnet part of IP addresscan physically reach each other without intervening router7network consisting of 3 subnetssubnetNetwork Layer4-40Subnets/24/24/24RecipeTo determine the subnets, detach each interface from its host or router, creating islands of

45、isolated networks. Each isolated network is called a subnet.Subnet mask: /24Network Layer4-41SubnetsHow many?7Network Layer4-42IP addressing: CIDRCIDR: Classless InterDomain Routingsubnet portion of address of arbitrary lengthaddress format: a.b.c.d/x, where x is # bits in subnet portion of address1

46、1001000 00010111 00010000 00000000subnetparthostpart/23Network Layer4-43IP addresses: how to get one?Q: How does host get IP address?hard-coded by system admin in a fileWintel: control-panel-network-configuration-tcp/ip-propertiesUNIX: /etc/rc.configDHCP: Dynamic Host Configuration Protocol: dynamic

47、ally get address from as server“plug-and-play” Network Layer4-44DHCP: Dynamic Host Configuration ProtocolGoal: allow host to dynamically obtain its IP address from network server when it joins networkCan renew its lease on address in useAllows reuse of addresses (only hold address while connected an

48、 “on”Support for mobile users who want to join network (more shortly)DHCP overview:host broadcasts “DHCP discover” msgDHCP server responds with “DHCP offer” msghost requests IP address: “DHCP request” msgDHCP server sends address: “DHCP ack” msg Network Layer4-45DHCP client-server scenario7ABE DHCP

49、server arriving DHCP client needsaddress in thisnetworkNetwork Layer4-46DHCP client-server scenarioDHCP server: arriving clienttimeDHCP discoversrc : , 68 dest.: 55,67yiaddr: transaction ID: 654DHCP offersrc: , 67 dest: 55, 68yiaddrr: transaction ID: 654Lifetime: 3600 secsDHCP requestsrc: , 68 dest:

50、 55, 67yiaddrr: transaction ID: 655Lifetime: 3600 secsDHCP ACKsrc: , 67 dest: 55, 68yiaddrr: transaction ID: 655Lifetime: 3600 secsNetwork Layer4-47IP addresses: how to get one?Q: How does network get subnet part of IP addr?A: gets allocated portion of its provider ISPs address spaceISPs block 11001

51、000 00010111 00010000 00000000 /20 Organization 0 11001000 00010111 00010000 00000000 /23 Organization 1 11001000 00010111 00010010 00000000 /23 Organization 2 11001000 00010111 00010100 00000000 /23 . . . .Organization 7 11001000 00010111 00011110 00000000 /23 Network Layer4-48Hierarchical addressi

52、ng: route aggregation“Send me anythingwith addresses beginning /20”/23/23/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning /16”/23Organization 2.Hierarchical addressing allows efficient advertisement of routing information:Network

53、 Layer4-49Hierarchical addressing: more specific routesISPs-R-Us has a more specific route to Organization 1“Send me anythingwith addresses beginning /20”/23/23/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning /16or /23”/23Organiz

54、ation 2.Network Layer4-50IP addressing: the last word.Q: How does an ISP get block of addresses?A: ICANN: Internet Corporation for Assigned Names and Numbersallocates addressesmanages DNSassigns domain names, resolves disputesNetwork Layer4-51NAT: Network Address Translationlocal network(e.g., home

55、network)10.0.0/24rest ofInternetDatagrams with source or destination in this networkhave 10.0.0/24 address for source, destination (as usual)All datagrams leaving localnetwork have same single source NAT IP address: ,different source port numbersNetwork Layer4-52NAT: Network Address TranslationMotiv

56、ation: local network uses just one IP address as far as outside world is concerned:range of addresses not needed from ISP: just one IP address for all devicescan change addresses of devices in local network without notifying outside worldcan change ISP without changing addresses of devices in local

57、networkdevices inside local net not explicitly addressable, visible by outside world (a security plus).Network Layer4-53NAT: Network Address TranslationImplementation: NAT router must:outgoing datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #).

58、. . remote clients/servers will respond using (NAT IP address, new port #) as destination addr.remember (in NAT translation table) every (source IP address, port #) to (NAT IP address, new port #) translation pair ing datagrams: replace (NAT IP address, new port #) in dest fields of every ing datagr

59、am with corresponding (source IP address, port #) stored in NAT tableNetwork Layer4-54NAT: Network Address TranslationS: , 3345D: 86, 8011: host sends datagram to 86, 80NAT translation tableWAN side addr LAN side addr, 5001 , 3345 S: 86, 80 D: , 33454S: , 5001D: 86, 8022: NAT routerchanges datagrams

60、ource addr from, 3345 to, 5001,updates tableS: 86, 80 D: , 500133: Reply arrives dest. address: , 50014: NAT routerchanges datagramdest addr from, 5001 to , 3345 Network Layer4-55NAT: Network Address Translation16-bit port-number field: 60,000 simultaneous connections with a single LAN-side address!