3rd Edition Chapter 4第三版4章

1、Network Layer4-1Chapter 4a, Network Layer (IP Addresses)Computer Networking: A Top Down Approach Featuring the Internet, 5th edition. Jim Kurose, Keith RossAddison-Wesley, July 2021. A note on the use of these ppt slides:Were making these slides freely available to all (faculty, students, readers).

2、Theyre in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent 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,

3、 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, 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 mater

4、ial copyright 1996-2021J.F Kurose and K.W. Ross, All Rights ReservedModified by John CopelandGeorgia Techfor use in ECE3600 Network Layer4-2Chapter 4: Network LayerChapter goals: runderstand principles behind network layer services:mnetwork layer service modelsmforwarding versus routingmhow a router

5、 worksmrouting (path selection)mdealing with scalemadvanced topics: IPv6, mobilityrinstantiation, implementation in the InternetNetwork Layer4-3Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv

6、4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-4Network layerrtransport segment from sending to receiving host ron sending side encapsulates segments into datagra

7、msron receiving side, delivers segments to transport layerrnetwork layer protocols in every host, routerrRouter examines IP header fields in all IP datagrams passing through itnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetw

8、orkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalNetwork Layer4-5Two Key Network-Layer Functionsrforwarding: move packets from routers input to appropriate router outputrrouting: determine rout

9、e taken by packets from source to dest. mrouting algorithmsanalogy:rrouting: process of planning trip from source to destrforwarding: process of getting through single interchangeNetwork Layer4-61230111value in arrivingpackets headerrouting algorithmlocal forwarding tableheader value output link0100

10、0101011110013221Interplay between routing and forwardingThe Routing Algorithm is used to calculate the link-IDs in the Forwarding Table.When a datagram arrives, the destination IP address is used to lookup the output link-ID.Network Layer4-7Connection setupr3rd important function in some network arc

11、hitectures:mATM, frame relay, X.25 (but not IP)rbefore datagrams flow, two end hosts and intervening routers establish virtual connectionmrouters get involvedrnetwork vs transport layer connection service:mnetwork: between two hosts (may also involve intervening routers in case of VCs)mtransport: be

12、tween 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 delay“best effort (e.g., IP)Example services for a flow of

13、 datagrams:rin-order datagram deliveryrguaranteed minimum bandwidth to flowrrestrictions on changes in inter-packet spacingNetwork Layer4-9ATM Network layer service models:NetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteed mini

14、mumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno (inferredvia loss)nocongestionnocongestionyesnoGuarantees ?ATM = Asynchronous Transfer ModeNetwork Layer4-10Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr

15、4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-11Network layer connection and connection-less servicerdatagram networ

16、k provides network-layer connectionless servicerVC network provides network-layer connection serviceranalogous to the transport-layer services, but:mservice: host-to-hostmno choice: network provides one or the othermimplementation: in network coreNetwork Layer4-12Virtual circuitsrcall setup, teardow

17、n 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 = predictable service)“source-to

18、-dest path behaves much like telephone circuitperformance-wisenetwork actions along source-to-dest pathNetwork Layer4-13VC implementationa VC consists of:mpath from source to destinationmVC numbers, number may differ for each link along pathmentries in forwarding tables in routers along pathrpacket

19、belonging to VC carries VC number (rather than destination address)rVC number can be changed on each link.1.New VC number comes from forwarding tableNetwork Layer4-14Forwarding table122232123VC numberinterfacenumberIncoming interface Incoming VC # Outgoing interface Outgoing VC #1 12 3 222 63 1 18 3

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

21、iontransportnetworkdata linkphysical1. Initiate call2. incoming call3. Accept call4. Call connected5. Data flow begins6. Receive dataNetwork Layer4-16Datagram networks (Internet)rno call setup at network layerrrouters: no state about end-to-end connectionsrno network-level concept of “connectionrpac

22、kets forwarded using destination host addressrpackets between same source-dest pair may take different paths (network congestion is busty)applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataNetwork Layer4-17Datagram or VC network: why?In

23、ternet (IP, datagram)data exchange among computers“elastic service, no strict timing req. “smart end systems (computers)can adapt, perform control, error recoverysimple inside network, complexity at “edgemany link types different characteristicsuniform service difficultATM (VC)evolved from telephony

24、human conversation: strict timing, reliability requirementsneed for guaranteed service“dumb end systemstelephonescomplexity inside networkNetwork Layer4-18Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram

25、 formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-19Router Architecture OverviewTwo key router functions: rrun routing algorithms/protocol (RIP, OSPF, BGP

26、)rforwarding datagrams from incoming to outgoing linkNetwork Layer 4-20Input 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 forwar

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

28、 systems memoryr speed limited by memory bandwidth (2 bus crossings per datagram)InputPortOutputPortMemorySystem BusNetwork Layer 4-23Switching Via a Busrdatagram from input port memory to output port memory via a shared busrbus contention: switching speed limited by bus bandwidthr1 Gbps bus, Cisco

29、1900: sufficient speed for access and enterprise routers (not regional or backbone)Network Layer 4-24Switching Via An Interconnection Networkrovercome bus bandwidth limitationsrBanyan networks, other interconnection nets initially developed to connect processors in multiprocessorrAdvanced design: fr

30、agmenting datagram into fixed length cells, switch cells through the fabric. rCisco 12000: switches Gbps through the interconnection networkNetwork Layer 4-25Output PortsrBuffering required when datagrams arrive from fabric faster than the transmission raterScheduling discipline chooses among queued

31、 datagrams for transmissionNetwork Layer 4-26Output port queueingrbuffering when arrival rate via switch exceeds output line speedrqueueing (delay) and loss due to output port buffer overflow!Network Layer 4-27Input Port QueuingrFabric slower than input ports combined - queueing may occur at input q

32、ueues rHead-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forwardrqueueing delay and loss due to input buffer overflow!Network Layer 4-28Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a router

33、r4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-29The Internet Network layerforwardingtableHost, router network laye

34、r functions:Routing protocolspath selectionRIP, OSPF, BGPIP protocoladdressing conventionsdatagram formatpacket handling conventionsICMP/IP protocolerror reportingrouter “signaling”Transport layer: TCP, UDPLink layerphysical layerNetworklayerNetwork Layer 4-30Chapter 4: Network Layerr4. 1 Introducti

35、onr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4

36、-31IP datagram format (IPv4)verlength32 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/reassemblytotal datag

37、ramlength (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?r20 bytes of TCP*r20 bytes of IPr= 40

38、 bytes + app layer overhead*plus options, usually 12-20 bytesNetwork Layer 4-32IP Fragmentation and ReassemblyID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=185fragflag=1length=1500ID=xoffset=370fragflag=0length=1040One large datagram becomesseveral smaller datagramsExa

39、mpler4000 byte datagramrMTU = 1500 bytes1480 bytes in data fieldoffset =1480/8 Steps: 1. Subtract 20 from original length: 4000 -20 = 3980 (bytes of IP data) 2. Subtract 20 from new MTU: 1500- 20 = 1480 (max. bytes of data in each fragment) 3. Divide maximum data bytes by 8: 1480/8 = 185 to get offs

40、et increment 4. Offset of each fragment n (n = 0, 1, 2, .) = n x offset increment: 0, 185, 370. . 5. Length of each fragment (except last) = 20 + max. data bytes = 20 +1480 = 1500 Length of last fragment = 20 + remaining data bytes = 20 + 3980 - 2 x 1480 = 1040Network Layer 4-33IP Fragmentation &

41、; Reassemblyrnetwork links have MTU (max.transfer size) - largest possible link-level frame.rdifferent link types, different MTUs rlarge IP datagram divided (“fragmented) within netrone datagram becomes several datagramsr“reassembled only at final destinationrIP header bits used to identify, order r

42、elated fragmentsfragmentation: in: one large datagramout: 3 smaller datagramsreassemblyAnother fragment flag, DNF (do not fragment) causes a ICMP response (and dropped datagram) instead of fragmentation. The sender then resends future datagrams with smaller size (may fragment itself or reduce MSS fo

43、r TCP). Blue: IP HeaderNetwork Layer 4-34Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routi

44、ng in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-35IP Addressing: introductionrIP address: 32-bit identifier for host, and router interface rinterface: connection between host/router and physical link (sometimes called a port).mrouters typically have multiple interf

45、acesmhost typically has one interfacemIP addresses associated with each interface7 = 11011111 00000001 00000001 00000001223111Network Layer 4-36SubnetsrIP address: msubnet part (high order bits)mhost part (low order bits) rWhats a subnet

46、 ?mdevice interfaces with same subnet part of IP addressmcan physically reach each other without intervening routerm(e.g., on the same Ethernet LAN)network consisting of 3 subnetssubnetNetwork Layer 4-37Subnets have a contiguous block of IP addresses which have the first N bits in common (a /N).223.

47、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 subnet.Subnet mask: /24Higher Order SubnetNetwork Layer 4-38SubnetsHow many?Network Layer 4-39IP addressing: CIDRCI

48、DR: Classless InterDomain Routingmsubnet portion of address of arbitrary lengthmaddress format: , where x is # bits in subnet portion of address11001000 00010111 00010000 00000000subnetparthostpart/23Original scheme: Class A = /8 = 224 (16,600,000) addresses Class B = /16 = 216 (65,000) a

49、ddresses Class C = /24 = 28 (256) addressesNetwork Layer 4-40IP addresses: how to get one?Q: How does host get assigned an IP address?hard-coded by system admin in a fileMS Widowsn: control-panel-network-configuration-tcp/ip-propertiesUNIX: /etc/rc.config file, or use ifconfigDHCP: Dynamic Host Conf

50、iguration Protocol: dynamically get address from as server“plug-and-play (more in next chapter)Network Layer4-41IP addresses: how to get one?Q: How does network get subnet part of IP addr?A: gets allocated portion of its provider ISPs address space (or space assigned to organization*).Autonomous Sys

51、tems (AS) buy connectivity from ISPs. Small companies may lease IP addresses from ISP as well. ISPs block 11001000 00010111 0001Organization 0 11001000 00010111 0001000Organization 1 11001000 00010111 0001001Organization 2 11001000 00010111 0001010 . . . .Organization 7 11001000 00010111 0001111 Net

52、work Layer 4-42Hierarchical addressing: route aggregation“Send me anythingwith addresses beginning /23/23/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning /23Organization 2.Hierarchical

53、addressing allows efficient advertisement of routing information:Network Layer 4-43Hierarchical addressing: more specific routesISPs-R-Us has a more specific route to Organization 1 (who switched ISPs)/23/23/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrgan

54、ization 1ISPs-R-Us“Send me anythingwith addresses /23Organization 2.“Send me anythingwith addresses beginning 1101000 00011001 0001 xxxx xxxxxxxx1101000 00011001 0001 001x xxxxxxxx“ “subnet mask./20 represents a 32-bit binary number that has 20 “ “1 bits at left and 12 “ “0s at the right:

55、11111111 11111111 11110000 00000000This number in dotted decimal format is:A network designator is incomplete without the network mask (either the above form or “ “/20).4-44Network LayerThe (sub)network mask can change:an IP address into the corresponding network address (for comparison in a router

56、forwarding table).Matchi = (IP & maski = Network_addri “=“ means “TRUE if equalsan IP address (or network address) into the network Broadcast Address:Broadcast_addr = IP | mask“& bitwise AND “| bitwise OR “ bitwise inversion (0-1, 1-0)Network LayerNetwork Layer 4-46Analogy to Telephone Numbe

57、rs(before number portability) Block of No.s (CIDR) Block Mask Area Covered 404-000-0000 /3 111-000-0000 Atlanta Area 404-894-0000 /6 111-111-0000 Georgia Tech 404-894-5000 /7 111-111-1000 ECEAtlanta No.s 404-000-0000 to 404-999-9999 107Georgia Tech 404-894-0000 to 404-894-9999 104ECE No.s 404-894-50

58、00 to 404-894-5999 103Network Layer 4-47Forwarding table Destination Address Range Link Interface 11001000 00010111 00010000 00000000 / 21 through 0 11001000 00010111 00010111 11111111 (211 = 2048 addresses) 11001000 00010111 00011000 00000000 / 24 through 1 11001000 00010111

59、 00011000 11111111 (28 = 256 addresses) 11001000 00010111 00011 / 21 through 2 11001000 00010111 00011111 11111111 (211 = 2048 addresses) (non-prefix bits shown in red) otherwise (default route) 3232 = 4 billion possible addressesNetwork Layer 4-48Longest prefix matching Prefix Match Siz

60、e Link Interface 11001000 00010111 0001 0 /21 0 11001000 00010111 0001 1000 /24 1 11001000 00010111 0001 1 /21 2 otherwise 3 DA: 11001000 00010111 0001 1000 1010 1010 ExamplesDA: 11001000 00010111 0001 0110 1010 0001 Which interface?Which interface?DA: 11001000 00010111 0001 1100 1010 1010 Why do we use prefixes of d