资源描述
Network Layer4-1Chapter 4Network LayerComputer Networking:A Top Down Approach 4th edition.Jim Kurose,Keith RossAddison-Wesley,July 2007.Network Layer4-2Chapter 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,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 formatmIPv4 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 datagramsron rcving side,delivers segments to transport layerrnetwork layer protocols in every host,routerrrouter examines header fields in all IP datagrams passing through itapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalNetwork Layer4-6Two Key Network-Layer Functionsrforwarding:move packets from routers input to appropriate router outputrrouting:determine route 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-71230111value in arrivingpackets headerrouting algorithmlocal forwarding tableheader value output link01000101011110013221Interplay between routing and forwardingNetwork Layer4-8Connection setupr3rd important function in some network architectures:mATM,frame relay,X.25rbefore 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:between two processesNetwork Layer4-9Chapter 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 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-10Network layer connection and connection-less servicerdatagram network 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-11Virtual circuitsrcall 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=predictable service)“source-to-dest path behaves much like telephone circuit”mperformance-wisemnetwork actions along source-to-dest pathNetwork Layer4-12VC implementationa VC consists of:1.path from source to destination2.VC numbers,one number for each link along path3.entries in forwarding tables in 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-13Forwarding table122232123VC numberinterfacenumberIncoming interface Incoming 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 connection state information!Network Layer4-14Virtual circuits:signaling protocolsrused to setup,maintain teardown VCrused in ATM,frame-relay,X.25rnot used in todays Internetapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1.Initiate call2.incoming call3.Accept call4.Call connected5.Data flow begins6.Receive dataNetwork Layer4-15Datagram networksrno call setup at network layerrrouters:no state about end-to-end connectionsmno network-level concept of“connection”rpackets forwarded using destination host addressmpackets between same source-dest pair may take different pathsapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1.Send data2.Receive dataNetwork Layer4-16Forwarding table Destination Address Range Link Interface 11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 34 billion possible entriesNetwork Layer4-17Longest 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-18Datagram or 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(VC)revolved from telephonyrhuman conversation:mstrict timing,reliability requirementsmneed for guaranteed servicer“dumb”end systemsmtelephonesmcomplexity inside networkNetwork Layer4-19Chapter 4:Network Layerr4.1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a router and how to router4.4 IP:Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-20Router Architecture OverviewTwo key router functions:rrun routing algorithms/protocol(RIP,OSPF,BGP)rforwarding datagrams from incoming to outgoing linkNetwork Layer4-21Input 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 into switch fabricPhysical layer:bit-level receptionData link layer:e.g.,Ethernetsee chapter 5Network Layer 4-22Three types of switching fabricsNetwork Layer 4-23Switching Via MemoryFirst generation routers:r traditional computers with switching under direct control of CPUrpacket copied to systems memoryr speed limited by memory bandwidth(2 bus crossings per datagram)InputPortOutputPortMemorySystem BusNetwork Layer 4-24Switching 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:sufficient speed for access and enterprise routersNetwork Layer 4-25Switching Via An Interconnection Networkrovercome bus bandwidth limitationsrSwitch Fabric:2n buses,n:input;n:outputradvanced design:fragmenting datagram into fixed length cells,switch cells through the fabric.rCisco 12000:switches 60 Gbps through the interconnection networkNetwork Layer 4-26Output PortsrBuffering required when datagrams arrive from fabric faster than the transmission raterScheduling discipline chooses among queued datagrams for transmissionNetwork Layer 4-27Output port queueingrbuffering when arrival rate via switch exceeds output line speedrqueueing(delay)and loss due to output port buffer overflow!Network Layer 4-28Input 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 queue from moving forwardrqueueing delay and loss due to input buffer overflow!routingprotocltable3input3switchinginputoutputforwardingRouting tableoutput11133122223network2data link1physicalphyData linknetwork swtching inputphyData link outputswitchingfrom A to B Network网络网络routerABRouting tableDest next hop Routing tableDest next hopRouting tableDest next hopStore and forwardrDirect deliver:source and destination are in the same network.rIndirect deliver:source and destination are in the different network.Network 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 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-36The Internet Network layerforwardingtableHost,router network layer functions:Routing protocolspath selectionRIP,OSPF,BGPIP protocoladdressing conventionsdatagram formatpacket handling conventionsICMP protocolerror reportingrouter“signaling”Transport layer:TCP,UDPLink layerphysical layerNetworklayerNetwork Layer 4-37Chapter 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 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-38IP 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/reassemblytotal 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?r20 bytes of TCPr20 bytes of IPr=40 bytes+app layer overheadIP header RFC791midentification:m flag:MF：More Fragments；(the 1st bit)DF：Dont Fragment；(the 2nd bit)mFragment offset8 Bit as a unit Network Layer 4-42IP Fragmentation&Reassemblyrnetwork links 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 fragmentsfragmentation:in:one large datagramout:3 smaller datagramsreassemblyprotocol MTU（Byte)Token Ring（16M）17914Token Ring（4M)4464FDDI 4352ethernet 1500X.25 576Network Layer 4-44IP Fragmentation and ReassemblyID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=185fragflag=1length=1500ID=xoffset=370fragflag=0length=1040One large datagram becomesseveral smaller datagramsExampler4000 byte datagramrMTU=1500 bytes1480 bytes in data fieldoffset=1480/8 Network Layer 4-45Chapter 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 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-46IP Addressing:introductionrIP address:32-bit identifier for host,router interface rinterface:connection between host/router and physical linkmrouters typically have multiple interfacesmhost typically has one interfacemIP addresses associated with each interface223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.1=11011111 00000001 00000001 00000001223111“dotted decimal notation”100011111000000010001001100100001st Byte=1282nd Byte=1433rd Byte=1374th Byte=144128.143.137.144128.143.137.144Special Ipm1，broadcast ip：The subnet broadcast 202.112.41.224 202.112.41.255 hosts in the same subnet receive it.Limited broadcast 255.255.255.255,all hosts receive it.m2，multicast ip：D，224.0.0.0 239.255.255.255IGMP(01-00-5e-00-00-00 01-00-5e-ff-ff-ff)m3，“0”：Host+network Host=0,network address;Network=0,host address;m4，loopback127.0.0.0 127.255.255.255；127.0.0.1rPrivate IP 10.0.0.0 -10.255.255.255172.16.0.0-172.31.255.255192.168.0.0-192.168.255.255 NAT:NAT:Network Address TranslationUsed in lanNetwork Layer 4-53rWhats a subnet?mdevice interfaces with same subnet part of IP addressmcan physically reach each other without intervening router223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27network consisting of 3 subnetssubnetNetwork Layer 4-54Subnets223.1.1.0/24223.1.2.0/24223.1.3.0/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:/24Network Layer 4-55SubnetsHow many?223.1.1.1223.1.1.3223.1.1.4223.1.2.2223.1.2.1223.1.2.6223.1.3.2223.1.3.1223.1.3.27223.1.1.2223.1.7.0223.1.7.1223.1.8.0223.1.8.1223.1.9.1223.1.9.2255.255.252.0The bits of network+subnet are 1.Subnet mask:A:255.0.0.0(/8);B:255.255.0.0(/16);C:255.255.255.0(/24)network numbernetwork numberhost numberhost numbersubnet numbersubnet numbernetwork numbernetwork numberhost numberhost numbersubnet part(high order bits)host part(low order bits)Subnet:Why?dlutCollege2libraryCollege1 Network Layer 4-59ISPs block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 .Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 Network Layer 4-60Hierarchical addressing:route aggregation“Send me anythingwith addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16”200.23.20.0/23Organization 2.Hierarchical addressing allows efficient advertisement of routing information:Network Layer4-61Hierarchical addressing:more specific routesISPs-R-Us has a more specific route to Organization 1“Send me anythingwith addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16or 200.23.18.0/23”200.23.20.0/23Organization 2.Subnet mask is 255.255.255.224Host Ip:202.112.41.241/27Cumpute:1,network address and Host address?2,how many subnets are created at most?Compute themr224 1111.11100000r202.112.41.241:24111110001=17 0.0.0.17;r202.112.41.224r255.255.255.2241111.11100000rEight subnets:202.112.41.0；202.112.41.32；202.112.41.64；202.112.41.96；202.112.41.128；202.112.41.160；202.112.41.192；202.112.41.224；Network Layer 4-64IP addresses:how to get one?Q:How does a host get IP address?rhard-coded by system admin in a filemWindows:control-panel-network-configuration-tcp/ip-propertiesmUNIX:/etc/rc.configrDHCP:Dynamic Host Configuration Protocol:dynamically get address from as serverm“plug-and-play”Network Layer 4-65DHCP: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“on”)Support for mobile users who want to join network(more shortly)DHCP overview:mhost broadcasts“DHCP discover”msgmDHCP server responds with“DHCP offer”msgmhost requests IP address:“DHCP request”msgmDHCP server sends address:“DHCP ack”msg Network Layer 4-66DHCP client-server scenario223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27ABE DHCP server arriving DHCP client needsaddress in thisnetworkNetwork Layer 4-67DHCP client-server scenarioDHCP server:223.1.2.5arriving clienttimeDHCP discoversrc:0.0.0.0,68 dest.:255.255.255.255,67yiaddr:0.0.0.0transaction ID:654DHCP offersrc:223.1.2.5,67 dest:255.255.255.255,68yiaddrr:223.1.2.4transaction ID:654Lifetime:3600 secsDHCP requestsrc:0.0.0.0,68 dest:255.255.255.255,67yiaddrr:223.1.2.4transaction ID:655Lifetime:3600 secsDHCP ACKsrc:223.1.2.5,67 dest:255.255.255.255,68yiaddrr:223.1.2.4transaction ID:655Lifetime:3600 secsNetwork Layer 4-68Q:How does an ISP get block of addresses?A:ICANN:Internet Corporation for Assigned Names and Numbersmallocates addressesmmanages DNSmassigns domain names,resolves disputesrIn order to solve the shortage of IP address1，CIDR无分类编址2,NAT3，IPv6Network Layer 4-70IP addressing:CIDRCIDR:Classless InterDomain Routingmsubnet portion of address of arbitrary lengthmaddress format:a.b.c.d/x,where x is#bits in subnet portion of address11001000 00010111 00010000 00000000subnetparthostpart200.23.16.0/23Network Layer4-71NAT:Network Address Translation10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7local network(e.g.,home 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:138.76.29.7,different source port numbersNetwork Layer 4-72NAT:Network Address TranslationrMotivation:local network uses just one IP address as 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 explicitly addressable,visible by outside world(a security plus).Network Layer 4-73NAT: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 using(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,port#)stored in NAT tableNetwork Layer 4-74NAT:Network Address Translation10.0.0.110.0.0.210.0.0.3S:10.0.0.1,3345D:128.119.40.186,80110.0.0.4138.76.29.71:host 10.0.0.1 sends datagram to 128.119.40.186,80NAT translation tableWAN side addr LAN side addr138.76.29.7,5001 10.0.0.1,3345 S:128.119.40.186,80 D:10.0.0.1,33454S:138.76.29.7,5001D:128.119.40.186,8022:NAT routerchanges datagramsource addr from10.0.0.1,3345 to138.76.29.7,5001,updates tableS:128.119.40.186,80 D:138.76.29.7,500133:Reply arrives dest.address:138.76.29.7,50014:NAT routerchanges datagramdest addr from138.76.29.7,5001 to 10.0.0.1,3345 Network Layer 4-75NAT:Network Address Translationr16-bit port-number field:m60,000 simultaneous connections with a single LAN-side address!rNAT is controversial:mrouters should only process up to layer 3mviolates end-to-end argumentNAT possibility must be taken into account by app designers,eg,P2P applicationsmaddress shortage should instead be solved by IPv6rNAT traversal穿透 is a cover all term used to describe the various methods employed to set up and maintain a TCP/IP network or UDP connections that cross NAT gateways.These techniques are needed in most peer to peer and VoIP applications Network Layer 4-77NAT traversal problemrclient wants to connect to server with address 10.0.0.1mserver address 10.0.0.1 local to LAN(client cant use it as destination addr)monly one externally visible NATted address:138.76.29.7rsolution 1:statically configure NAT to forward incoming connection requests at given port to serverme.g.,(123.76.29.7,port 2500)always forwarded to 10.0.0.1 port 2500010.0.0.110.0
展开阅读全文