3rd edition chapter 4第三版4章

Network Layer,4-1,Chapter 4a, Network Layer (IP Addresses),Computer Networking: A Top Down Approach Featuring the Internet, 5th edition. Jim Kurose, Keith RossAddison-Wesley, July 2009.,A 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 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, 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 material copyright 1996-2009J.F Kurose and K.W. Ross, All Rights Reserved,Modified by John CopelandGeorgia Techfor use in ECE3600,Network Layer,4-2,Chapter 4: Network Layer,Chapter goals: understand principles behind network layer services:network layer service modelsforwarding versus routinghow a router worksrouting (path selection)dealing with scaleadvanced topics: IPv6, mobilityinstantiation, implementation in the Internet,Network Layer,4-3,Chapter 4: Network Layer,4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv6,4.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routing,Network Layer,4-4,Network layer,transport segment from sending to receiving host on sending side encapsulates segments into datagramson receiving side, delivers segments to transport layernetwork layer protocols in every host, routerRouter examines IP header fields in all IP datagrams passing through it,Network Layer,4-5,Two Key Network-Layer Functions,forwarding: move packets from routers input to appropriate router outputrouting: determine route taken by packets from source to dest. routing algorithms,analogy:routing: process of planning trip from source to destforwarding: process of getting through single interchange,Network Layer,4-6,Interplay between routing and forwarding,The 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 Layer,4-7,Connection setup,3rd important function in some network architectures:ATM, frame relay, X.25 (but not IP)before 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 intervening routers in case of VCs)transport: between two processes,Network Layer,4-8,Network service model,Q: 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 datagrams:in-order datagram deliveryguaranteed minimum bandwidth to flowrestrictions on changes in inter-packet spacing,Network Layer,4-9,ATM Network layer service models:,NetworkArchitectureInternetATMATMATMATM,ServiceModelbest effortCBRVBRABRUBR,Bandwidthnoneconstantrateguaranteedrateguaranteed minimumnone,Lossnoyesyesnono,Ordernoyesyesyesyes,Timingnoyesyesnono,Congestionfeedbackno (inferredvia loss)nocongestionnocongestionyesno,Guarantees ?,ATM = Asynchronous Transfer Mode,Network Layer,4-10,Chapter 4: Network Layer,4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv6,4.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routing,Network Layer,4-11,Network layer connection and connection-less service,datagram network provides network-layer connectionless 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 core,Network Layer,4-12,Virtual circuits,call setup, teardown for each call before data can floweach packet 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 circuit”performance-wisenetwork actions along source-to-dest path,Network Layer,4-13,VC implementation,a VC consists of:path from source to destinationVC numbers, number may differ for each link along pathentries in forwarding tables in routers along pathpacket belonging to VC carries VC number (rather than destination address)VC number can be changed on each link.New VC number comes from forwarding table,Network Layer,4-14,Forwarding table,Forwarding table innorthwest router:,Routers maintain connection state information!,Network Layer,4-15,Virtual circuits: signaling protocols,used to setup, maintain teardown VCused in ATM, frame-relay, X.25not used in todays Internet,1. Initiate call,2. incoming call,3. Accept call,4. Call connected,5. Data flow begins,6. Receive data,Network Layer,4-16,Datagram networks (Internet),no 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 different paths (network congestion is busty),1. Send data,2. Receive data,Network Layer,4-17,Datagram or VC network: why?,Internet (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 “edge”many link types different characteristicsuniform service difficult,ATM (VC)evolved from telephonyhuman conversation: strict timing, reliability requirementsneed for guaranteed service“dumb” end systemstelephonescomplexity inside network,Network Layer,4-18,Chapter 4: Network Layer,4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv6,4.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routing,Network Layer,4-19,Router Architecture Overview,Two key router functions: run routing algorithms/protocol (RIP, OSPF, BGP)forwarding datagrams from incoming to outgoing link,Network Layer,4-20,Input Port Functions,Decentralized switching: 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 fabric,Physical layer:bit-level reception,Data link layer:e.g., Ethernetsee chapter 5,Network Layer,4-21,Three types of switching fabrics,Network Layer,4-22,Switching Via Memory,First 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),Network Layer,4-23,Switching Via a Bus,datagram from input port memory to output port memory via a shared busbus contention: switching speed limited by bus bandwidth1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone),Network Layer,4-24,Switching Via An Interconnection Network,overcome bus bandwidth 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 Gbps through the interconnection network,Network Layer,4-25,Output Ports,Buffering required when datagrams arrive from fabric faster than the transmission rateScheduling discipline chooses among queued datagrams for transmission,Network Layer,4-26,Output port queueing,buffering when arrival rate via switch exceeds output line speedqueueing (delay) and loss due to output port buffer overflow!,Network Layer,4-27,Input Port Queuing,Fabric 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 Layer,4-28,Chapter 4: Network Layer,4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv6,4.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routing,Network Layer,4-29,The Internet Network layer,Host, router network layer functions:,Transport layer: TCP, UDP,Link layer,physical layer,Networklayer,Network Layer,4-30,Chapter 4: Network Layer,4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv6,4.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routing,Network Layer,4-31,IP datagram format (IPv4),how much overhead with TCP?20 bytes of TCP*20 bytes of IP= 40 bytes + app layer overhead,*plus options, usually 12-20 bytes,Network Layer,4-32,IP Fragmentation and Reassembly,Example4000 byte datagramMTU = 1500 bytes,1480 bytes in data field,offset =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 offset 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 = 1040,Network Layer,4-33,IP Fragmentation & Reassembly,network links have MTU (max.transfer size) - largest possible link-level frame.different link types, different MTUs large IP datagram divided (“fragmented”) within netone datagram becomes several datagrams“reassembled” only at final destinationIP header bits used to identify, order related fragments,fragmentation: in: one large datagramout: 3 smaller datagrams,reassembly,Another 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 for TCP).,Blue: IP Header,Network Layer,4-34,Chapter 4: Network Layer,4. 1 Introduction4.2 Virtual circuit and datagram networks4.3 Whats inside a router4.4 IP: Internet ProtocolDatagram formatIPv4 addressingICMPIPv6,4.5 Routing algorithmsLink stateDistance VectorHierarchical routing4.6 Routing in the InternetRIPOSPFBGP4.7 Broadcast and multicast routing,Network Layer,4-35,IP Addressing: introduction,IP address: 32-bit identifier for host, and router interface interface: connection between host/router and physical link (sometimes called a port).routers typically have multiple interfaceshost typically has one interfaceIP addresses associated with each interface,,,,, = 11011111 00000001 00000001 00000001,223,1,1,1,Could advertise a single route to Inet, /22,Network Layer,4-36,Subnets,IP address: subnet part (high order bits)host part (low order bits) Whats a subnet ?device interfaces with same subnet part of IP addresscan physically reach each other without intervening router(e.g., on the same Ethernet LAN),,,,,,,,,,7,network consisting of 3 subnets,subnet,Network Layer,4-37,Subnets have a contiguous block of IP addresses which have the first N bits in common (a /N).,RecipeTo 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: /24,/22,Higher Order Subnet,Network Layer,4-38,Subnets,How many?,,,,,,,,,7,,,,,,,,Network Layer,4-39,IP addressing: CIDR,CIDR: Classless InterDomain Routingsubnet portion of address of arbitrary lengthaddress format: a.b.c.d/x, where x is # bits in subnet portion of address,Original scheme: Class A = /8 = 224 (16,600,000) addresses Class B = /16 = 216 (65,000) addresses Class C = /24 = 28 (256) addresses,Network Layer,4-40,IP 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 Configuration Protocol: dynamically get address from as server“plug-and-play” (more in next chapter),Network Layer,4-41,IP 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 Systems (AS) buy connectivity from ISPs. Small companies may lease IP addresses from ISP as well.,ISPs block 11001000 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,* see / - Internet Assigned Numbers Authority,Network Layer,4-42,Hierarchical addressing: route aggregation,“Send me anythingwith addresses beginning /20”,Fly-By-Night-ISP,Organization 0,Organization 7,Internet,Organization 1,ISPs-R-Us,“Send me anythingwith addresses beginning /16”,Organization 2,Hierarchical addressing allows efficient advertisement of routing information:,Network Layer,4-43,Hierarchical addressing: more specific routes,ISPs-R-Us has a more specific route to Organization 1 (who switched ISPs),Fly-By-Night-ISP,Organization 0,Organization 7,Internet,Organization 1,ISPs-R-Us,“Send me anythingwith addresses beginning /16or /23,Organization 2,“Send me anythingwith addresses beginning /20”,1101000 00011001 0001 xxxx xxxxxxxx,1101000 00011001 0001 001x xxxxxxxx,Textbook refers to /20 in the network designator /20 as the “subnet mask”./20 represents a 32-bit binary number that has 20 “1” bits at left and 12 “0”s at the right: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-44,Network Layer,The (sub)network mask can change:an IP address into the corresponding network address (for comparison in a router forwarding table).Matchi = (IP & maski = Network_addri “=“ means “TRUE if equals”an 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 Layer,Network Layer,4-46,Analogy to Telephone Numbers(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-5000 to 404-894-5999 103,Network Layer,4-47,Forwarding 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 00011000 11111111 (28 = 256 addresses) 11001000 00010111 00011000 00000000 / 21 through 2 11001000 00010111 00011111 11111111 (211 = 2048 addresses) (non-prefix bits shown in red) otherwise (default route) 3,