计算机网络课件：Chapter4

1、Network Layer4-1Chapter 4: Network LayerChapter goals: runderstand principles behind network layer services:mnetwork layer service modelsmforwarding versus routingmhow a router worksmrouting (path selection)mdealing with scalemadvanced topics: IPv6 fundationrinstantiation, implementation in the Inte

2、rnetNetwork Layer4-2Network layerProvides end-to-end transport service rsending side encapsulates segments into datagramsrrcving side delivers segments to transport layerrnetwork layer protocols in every host, routerrrouter examines header fields in all IP datagrams passing through itapplicationtran

3、sportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata

4、 linkphysicalnetworkdata linkphysicalNetwork Layer4-3Two Key Network-Layer Functionsrforwarding: move packets from routers input to appropriate router outputrrouting: determine route taken by packets from source to dest. mrouting algorithmsNetwork Layer4-41230111value in arrivingpackets headerroutin

5、g algorithmlocal forwarding tableheader value output link01000101011110013221Interplay between routing and forwardingNetwork Layer4-5Connection setupr3rd important function in some network architectures:mATM, frame relay, X.25rbefore datagrams flow, two end hosts and intervening routers establish vi

6、rtual connectionmrouters get involvedrnetwork vs transport layer connection service:mnetwork: between two hosts (may also involve intervening routers in case of VCs)mtransport: between two processesNetwork Layer4-6 Network service modelQoS of end to end transportingrguaranteed bandwidth?rpreservatio

7、n of inter-packet timing (no jitter)?rloss-free delivery?rin-order delivery?rcongestion feedback to sender?rNo errorsrDelay ?virtual circuitor datagram?The most important abstraction provided by network layer:service abstractionNetwork-service model defines the characteristics of end-to-end data tra

8、nsport between sender and receiverNetwork Layer4-7Network layer service models:NetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteed minimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno (inferredvia

9、 loss)nocongestionnocongestionyesnoGuarantees ?Network Layer4-8Network layer connection and connection-less servicerdatagram network provides network-layer connectionless servicerVC network provides network-layer connection servicemCall setupmimplementation: in network coreNetwork Layer4-9Virtual ci

10、rcuitsrcall setup, teardown for each call before data can flowreach packet carries VC identifier (not destination host address)revery router on source-dest path maintains “state” for each passing connectionrlink, router resources (bandwidth, buffers) may be allocated to VC (dedicated resources = pre

11、dictable service)“source-to-dest path behaves much like telephone circuit”mperformance-wisemnetwork actions along source-to-dest pathNetwork Layer4-10VC implementationa VC consists of:1.path from source to destination2.VC numbers, one number for each link along path3.entries in forwarding tables in

12、routers along pathrpacket belonging to VC carries VC number (rather than dest address)rVC number can be changed on each link.mNew VC number comes from forwarding tableNetwork Layer4-11Forwarding table122232123VC numberinterfacenumberIncoming interface Incoming VC # Outgoing interface Outgoing VC #1

13、12 3 222 63 1 18 3 7 2 171 97 3 87 Forwarding table innorthwest router:Routers maintain connection state information!Network Layer4-12Virtual circuits: signaling protocolsrused to setup, maintain, teardown VCrused in ATM, frame-relay, X.25rnot used in todays Internetapplicationtransportnetworkdata l

14、inkphysicalapplicationtransportnetworkdata linkphysical1. Initiate call2. incoming call3. Accept call4. Call connected5. Data flow begins6. Receive dataNetwork Layer4-13Datagram networksrno call setup at network layerrrouters: no state about end-to-end connectionsmno network-level concept of “connec

15、tion”rpackets forwarded using destination host addressmpackets between same source-dest pair may take different pathsapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataNetwork Layer4-14Forwarding table Destination Address Range Link Int

16、erface 11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011000 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 34 billion possible entriesNetwork La

17、yer4-15Longest prefix matching Prefix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3DA: 11001000 00010111 00011000 10101010 ExamplesDA: 11001000 00010111 00010110 10100001 Which interface?Which interface?Network Layer4-16Datagram or

18、VC network: why?Internet (datagram)rdata exchange among computersm“elastic” service, no strict timing req. r“smart” end systems (computers)mcan adapt, perform control, error recoverymsimple inside network, complexity at “edge”rmany link types mdifferent characteristicsmuniform service difficultATM (

19、VC)revolved from telephonyrhuman conversation: mstrict timing, reliability requirementsmneed for guaranteed servicer“dumb” end systemsmtelephonesmcomplexity inside networkNetwork Layer4-17Router Architecture OverviewTwo key router functions: rrun routing algorithms/protocol (RIP, OSPF, BGP)rforwardi

20、ng datagrams from incoming to outgoing linkNetwork Layer4-18Input Port FunctionsDecentralized switching: rgiven datagram dest., lookup output port using forwarding table in input port memoryrgoal: complete input port processing at line speedrqueuing: if datagrams arrive faster than forwarding rate i

21、nto switch fabricPhysical layer:bit-level receptionData link layer:e.g., Ethernetsee chapter 5Network Layer4-19Three types of switching fabricsNetwork Layer 4-20Switching Via MemoryFirst generation routers:r traditional computers with switching under direct control of CPUrpacket copied to systems me

22、moryr speed limited by memory bandwidth (2 bus crossings per datagram)InputPortOutputPortMemorySystem BusNetwork Layer4-21Switching Via a Busrdatagram from input port memory to output port memory via a shared busrbus contention: switching speed limited by bus bandwidthr32 Gbps bus, Cisco 5600: suffi

23、cient speed for access and enterprise routersNetwork Layer 4-22Switching Via An Interconnection Networkrovercome bus bandwidth limitationsrBanyan networks, other interconnection nets initially developed to connect processors in multiprocessorradvanced design: fragmenting datagram into fixed length c

24、ells, switch cells through the fabric. rCisco 12000: switches 60 Gbps through the interconnection networkNetwork Layer 4-23Output PortsrBuffering required when datagrams arrive from fabric faster than the transmission raterScheduling discipline chooses among queued datagrams for transmissionNetwork

25、Layer 4-24Output port queueingrbuffering when arrival rate via switch exceeds output line speedrqueueing (delay) and loss due to output port buffer overflow!Network Layer 4-25How much buffering?rRFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) times link capacity Cme.g

26、., C = 10 Gps link: 2.5 Gbit bufferrRecent recommendation: with N flows, buffering equal to RTT C.NNetwork Layer 4-26Input Port QueuingrFabric slower than input ports combined - queueing may occur at input queues rHead-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in

27、queue from moving forwardrqueueing delay and loss due to input buffer overflow!Network Layer 4-27 Router OverviewNetwork Layer 4-28 Router OverviewNetwork Layer 4-29 Router OverviewNetwork Layer 4-30The Internet Network layerforwardingtableHost, router network layer functions:Routing protocolspath s

28、electionRIP, OSPF, BGPIP protocoladdressing conventionsdatagram formatpacket handling conventionsICMP protocolerror reportingrouter “signaling”Transport layer: TCP, UDPLink layerphysical layerNetworklayerNetwork Layer4-31IP datagram formatverlength32 bitsdata (variable length,typically a TCP or UDP

29、segment)16-bit identifierheader checksumtime tolive32 bit source IP addressIP protocol versionnumberheader length (bytes)max numberremaining hops(decremented at each router)forfragmentation/reassemblytotal datagramlength (bytes)upper layer protocolto deliver payload tohead.lentype ofservice“type” of

30、 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?r20 bytes of TCPr20 bytes of IPr= 40 bytes + app layer overheadNetwork Layer 4-32IP Fragmentation & Reassemblyrnetwork lin

31、ks have MTU (max.transfer size) - largest possible link-level frame.mdifferent link types, different MTUs rlarge IP datagram divided (“fragmented”) within netmone datagram becomes several datagramsm“reassembled” only at final destinationmIP header bits used to identify, order related fragmentsfragme

32、ntation: in: one large datagramout: 3 smaller datagramsreassemblyNetwork Layer 4-33IP Fragmentation and ReassemblyID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=1480fragflag=1length=1500ID=xoffset=2960fragflag=0length=1040One large datagram becomesseveral smaller datagr

33、amsExampler4000 byte datagramrMTU = 1500 bytes1480 bytes in data field:01479Offset：14802959 Network Layer 4-34IP Addressing: introductionrIP address: 32-bit identifier for host, router interface rinterface: connection between host/router and physical linkmrouters typically have multiple interfacesmh

34、ost typically has one interfacemIP addresses associated with each interface7 = 11011111 00000001 00000001 00000001223111Network Layer 4-35SubnetsrIP address: mnetwork part (high order bits)mhost part (

35、low order bits) rWhats a subnet ?mdevice interfaces with same net part of IP addressmcan physically reach each other without intervening router7network consisting of 3 subnetssubnetNetwork Layer 4-36Subnets223.

36、1.1.0/24/24/24ReciperTo determine the subnets, detach each interface from its host or router, creating islands of isolated networks. Each isolated network is called a network segment.Subnet mask: /24Network Layer 4-37SubnetsHow many?223.

37、1.2.67Network Layer 4-38 IP Addresses0networkhost10networkhost110networkhost1110multicast addressABCDclass to55 to55 to55 to

38、5532 bitsgiven notion of “network”, lets re-examine IP addresses:“class-full” addressing:Network Layer 4-39 Special AddressesNet-idHost-idSource addDest. addspecifications00This network, this host0Host-idThis network, a hostAll 1All 1Broadcasting in this networkNet-idAll 1Broadcasting in a network12

39、7anyLoopback testNetwork Layer 4-40 Subnet Mask rIntroduced in 1985, adaptive to distributed institute-subnetrsome Left bits of host-id are used for subnet fieldrSubnet partition must use subnet mask:rUsing subnet will reduce available host addressesmB: 65534 host-id, if 6bit used for subnet-idm(26-

40、2)(210-2)=63364Net-idSubnet idHost-id11111111111111.111000.00 default subnet masks:A: B: C: ip address: subnet mask: subnet address= ip address & subnet maskNetwork Layer4-41 An examplerA small company has a class C network license and needs to create 10 usable

41、subnets, each subnet capable of accommodating at least 12hosts. Which of the following is the appropriate subnet mask?r r r 92 r 24 r 40Network Layer 4-42IP addressing: CIDRCIDR: Classless InterDomain Routingmnetwork portion of address of arbitrar

42、y lengthmaddress format: a.b.c.d/x, where x is # bits in subnet portion of address11001000 00010111 00010000 00000000subnetparthostpart/23Network Layer 4-43IP addresses: how to get one?Q: How does a host get IP address?rhard-coded by system admin in a filemWindows: control-panel-network-c

43、onfiguration-tcp/ip-propertiesmUNIX: /etc/rc.configrDHCP: Dynamic Host Configuration Protocol: dynamically get address from as serverm“plug-and-play” Network Layer 4-44DHCP: Dynamic Host Configuration ProtocolGoal: allow host to dynamically obtain its IP address from network server when it joins net

44、workCan renew its lease on address in useAllows reuse of addresses (only hold address while connected an “on”)Support for mobile users who want to join network (more shortly)DHCP overview:mhost broadcasts “DHCP discover” msgmDHCP server responds with “DHCP offer” msg mhost requests IP address: “DHCP

45、 request” msgmDHCP server sends address: “DHCP ack” msg Network Layer 4-45DHCP client-server scenario7ABE DHCP server arriving DHCP client needsaddress in thisnetworkNetwork Layer 4-46DHCP client-server scenari

46、oDHCP server: arriving clienttimeDHCP discoversrc : , 68 dest.: 55,67yiaddr: transaction ID: 654DHCP offersrc: , 67 dest: 55, 68yiaddrr: transaction ID: 654Lifetime: 3600 secsDHCP requestsrc: , 68 dest: 55, 67yiad

47、drr: transaction ID: 655Lifetime: 3600 secsDHCP ACKsrc: , 67 dest: 55, 68yiaddrr: transaction ID: 655Lifetime: 3600 secsHalf of time:Re-requestNetwork Layer 4-47DHCP: more than IP addressDHCP can return more than just allocated IP address on subnet:maddress of

48、 first-hop router for clientmname and IP address of DNS severmnetwork mask (indicating network versus host portion of address)Network Layer 4-48DHCP: examplerconnecting laptop needs its IP address, addr of first-hop router, addr of DNS server: use DHCProuter(runs DHCP)DHCPUDPIPEthPhyDHCPDHCPDHCPDHCP

49、DHCPDHCPUDPIPEthPhyDHCPDHCPDHCPDHCPDHCPrDHCP request encapsulated in UDP, encapsulated in IP, encapsulated in 802.3 EthernetrEthernet frame broadcast (dest: FFFFFFFFFFFF) on LAN, received at router running DHCP serverrEthernet demuxed to IP demuxed, UDP demuxed to DHCP Network Layer 4-49rDC

50、P server formulates DHCP ACK containing clients IP address, IP address of first-hop router for client, name & IP address of DNS serverrouter(runs DHCP)DHCPUDPIPEthPhyDHCPDHCPDHCPDHCPDHCPUDPIPEthPhyDHCPDHCPDHCPDHCPDHCPrencapsulation of DHCP server, frame forwarded to client, demuxing up to DHCP a

51、t clientrclient now knows its IP address, name and IP address of DSN server, IP address of its first-hop routerDHCP: exampleNetwork Layer 4-50IP 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 11001000 00

52、010111 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 200.

53、23.30.0/23 Network Layer4-51Hierarchical addressing: 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”

54、/23Organization 2.Hierarchical addressing allows efficient advertisement of routing information:Network Layer 4-52Hierarchical addressing: more specific routesISPs-R-Us has a more specific route to Organization 1“Send me anythingwith addresses beginning /20”/23200.23

55、.18.0/23/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning /16or /23”/23Organization 2.Network Layer 4-53IP addressing: the last word.Q: How does an ISP get block of addresses?A: ICANN: In

56、ternet Corporation for Assigned Names and Numbersmallocates addressesmmanages DNSmassigns domain names, resolves disputesNetwork Layer 4-54NAT: Network Address Translationlocal network(e.g., home network)10.0.0/24rest ofInternetDatagrams with source or dest

57、ination 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 Layer 4-55NAT: Network Address TranslationrMotivation: local network uses just one IP address as

58、 far as outside world is concerned:mrange of addresses not needed from ISP: just one IP address for all devicesmcan change addresses of devices in local network without notifying outside worldmcan change ISP without changing addresses of devices in local networkmdevices inside local net not explicit

59、ly addressable, visible by outside world (a security plus).Network Layer 4-56NAT: Network Address TranslationImplementation: NAT router must:moutgoing datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #). . . remote clients/servers will respond us

60、ing (NAT IP address, new port #) as destination addr.mremember (in NAT translation table) every (source IP address, port #) to (NAT IP address, new port #) translation pairmincoming datagrams: replace (NAT IP address, new port #) in dest fields of every incoming datagram with corresponding (source IP address,