計算機網(wǎng)絡(luò)英文課件：Chapter4 Network Layer

1、 Introduction1-1Chapter 4Network LayerNetwork 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 scalerinstantiation, implementation in th

2、e InternetNetwork Layer4-3Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPr4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmR

3、IPmOSPFmBGPNetwork Layer4-4Network layerrtransport segment from sending to receiving host ron sending side encapsulates segments into datagramsron receiving side, delivers segments to transport layerrnetwork layer protocols in every host, routerrrouter examines header fields in all IP datagrams pass

4、ing through itapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetwor

5、kdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalNetwork Layer4-5Two Key Network-Layer Functionsrforwarding: move packets from routers input to appropriate router outputrrouting: determine route taken by packets from source to dest. mrouting algorithmsanalogy:vrouting: process of pl

6、anning trip from source to destvforwarding: process of getting through single interchangeNetwork Layer4-61230111value in arrivingpackets headerrouting algorithmlocal forwarding tableheader value output link01000101011110013221Interplay between routing and forwardingrouting algorithm determinesend-en

7、d-path through networkforwarding table determineslocal forwarding at this routerNetwork Layer4-7Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPr4.5 Routing algorithmsmLink st

8、atemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPNetwork Layer4-8Network layer connection and connection-less servicerdatagram network provides network-layer connectionless servicervirtual-circuit network provides network-layer connection serviceranalogous to the TCP/

9、UDP connecton-oriented / connectionless transport-layer services, but:mservice: host-to-hostmno choice: network provides one or the othermimplementation: in network coreNetwork Layer4-9Virtual circuitsrcall setup, teardown for each call before data can flowreach packet carries VC identifier (not des

10、tination 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 actio

11、ns 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 routers along pathrpacket belonging to VC carries VC number (rather than dest address)rVC number can be c

12、hanged on each link.mNew VC number comes from forwarding tableNetwork Layer4-11Forwarding 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

13、information!Network Layer4-12Virtual 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. Ca

14、ll 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 “connection”rpackets forwarded using destination host addressmpackets between same source-dest pair may take diff

15、erent pathsapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataNetwork Layer4-14123Datagram forwarding tableIP destination address in arriving packets headerrouting algorithmlocal forwarding tabledest addressoutput linkaddress-range 1add

16、ress-range 2address-range 3address-range 432214 billion IP addresses, so rather than list individual destination addresslist range of addresses(aggregate table entries)Network Layer4-15Datagram Forwarding table Destination Address Range Link Interface 11001000 00010111 00010000 00000000 through 0 11

17、001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 3Q: but what happens if ranges dont divide up so nicely? Network Layer4-16Longest prefix mat

18、chingDestination Address Range 11001000 00010111 00010* * 11001000 00010111 00011000 *11001000 00010111 00011* *otherwise DA: 11001000 00010111 00011000 10101010 examples:DA: 11001000 00010111 00010110 10100001 which interface?which interface?when looking for forwarding table entry for given destina

19、tion address, use longest address prefix that matches destination address.longest prefix matchingLink interface0123Network Layer4-17Internet (datagram)rdata exchange among computersm“elastic” service, no strict timing req. rmany link types mdifferent characteristicsmuniform service difficultr“smart”

20、 end systems (computers)mcan adapt, perform control, error recoverymsimple inside network, complexity at “ “edge” ”ATM (VC)revolved from telephonyrhuman conversation: mstrict timing, reliability requirementsmneed for guaranteed servicer“dumb” end systemsmtelephonesmcomplexity inside networkDatagram

21、or VC network: why?Network Layer4-18Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPr4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the

22、InternetmRIPmOSPFmBGPNetwork Layer4-19two key router functions: vrun routing algorithms/protocol (RIP, OSPF, BGP)vforwarding datagrams from incoming to outgoing linkhigh-seed switchingfabricrouting processorrouter input portsrouter output portsforwarding data plane (hardware)routing, managementcontr

23、ol plane (software)forwarding tables computed,pushed to input portsRouter Architecture OverviewNetwork Layer 4-20lineterminationlink layer protocol(receive)lookup,forwardingqueueingdecentralized switching: rgiven datagram dest., lookup output port using forwarding table in input port memory (“match

24、plus action”)rgoal: 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 5switchfabricInput Port FunctionsNetwork Layer4-21Switching fabricsvtransfer packet

25、from input buffer to appropriate output buffervswitching rate: rate at which packets can be transfer from inputs to outputsoften measured as multiple of input/output line rateN inputs: switching rate N times line rate desirablevthree types of switching fabricsmemorymemorybuscrossbarNetwork Layer 4-2

26、2Output portsvbuffering required when datagrams arrive from fabric faster than the transmission ratevscheduling discipline chooses among queued datagrams for transmissionlineterminationlink layer protocol(send)switchfabricdatagrambufferqueueingNetwork Layer 4-23Output port queueingrbuffering when ar

27、rival rate via switch exceeds output line speedrqueueing (delay) and loss due to output port buffer overflow!at t, packets morefrom input to outputone packet time laterswitchfabricswitchfabricNetwork Layer 4-24Input port queuingrfabric slower than input ports combined - queueing may occur at input q

28、ueues mqueueing delay and loss due to input buffer overflow!rHead-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forwardoutput port contention:only one red datagram can be transferred.lower red packet is blockedswitchfabricone packet time later: gr

29、een packet experiences HOL blockingswitchfabricNetwork Layer 4-25Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPr4.5 Routing algorithmsmLink statemDistance VectormHierarchica

30、l routingr4.6 Routing in the InternetmRIPmOSPFmBGPNetwork Layer 4-26The Internet Network layerforwardingtableHost, router network layer functions:Routing protocolspath selectionRIP, OSPF, BGPIP protocoladdressing conventionsdatagram formatpacket handling conventionsICMP protocolerror reportingrouter

31、 “signaling”Transport layer: TCP, UDPLink layerphysical layerNetworklayerNetwork Layer 4-27Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPr4.5 Routing algorithmsmLink statemD

32、istance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPNetwork Layer 4-28IP 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 nu

33、mberremaining 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

34、of routers to visit.how much overhead with TCP?r20 bytes of TCPr20 bytes of IPr= 40 bytes + app layer overheadNetwork Layer 4-29IP Fragmentation & Reassemblyrnetwork links have MTU (max.transfer size) - largest possible link-level frame.mdifferent link types, different MTUs rlarge IP datagram di

35、vided (“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 datagramsreassemblyNetwork Layer 4-30IP Fragmentation and ReassemblyID=xoffset=0f

36、ragflag=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 Layer4-31Chapter 4: Network Layerr4.

37、 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPr4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPNetwork Layer 4-32IP Addressing: introduct

38、ionrIP 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

39、.2.17 = 11011111 00000001 00000001 00000001223111Network Layer 4-33SubnetsrIP address: msubnet part (high order bits)mhost part (low order bits) rWhats a subnet ?mdevice interfaces with same subnet part of IP addressmcan physically reach each other without interve

40、ning router7network consisting of 3 subnetssubnetNetwork Layer 4-34Subnets/24/24/24ReciperTo determine the subnets, detach each interface from its host or router, creating islands of

41、isolated networks. rEach isolated network is called a subnet.Subnet mask: /24Network Layer 4-35SubnetsHow many?7Network Layer 4-36IP addressing: CIDRCIDR: C

42、lassless 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 00000000subnetparthostpart/23CIDR address：206.13.01.48/25being same to 206.13.01.48 28Network Layer 4

43、-37IP addresses: how to get one?Q: How does host get IP address?rhard-coded by system admin in a filemWintel: 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-3

44、8DHCP: 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 sh

45、ortly)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-39DHCP client-server scenario223.1

46、.3.27ABE DHCP server arriving DHCP client needsaddress in thisnetworkNetwork Layer 4-40DHCP client-server scenarioDHCP server: arriving clienttimeDHCP discoversrc : , 68 dest.: 55,67yiaddr: transaction ID: 654DHCP offersrc: , 67 dest: 25

47、55, 68yiaddrr: transaction ID: 654Lifetime: 3600 secsDHCP requestsrc: , 68 dest: 55, 67yiaddrr: transaction ID: 655Lifetime: 3600 secsDHCP ACKsrc: , 67 dest: 55, 68yiaddrr: transaction ID: 655Lifetime: 3600 secsNetwork L

48、ayer4-41DHCP: more than IP addressesDHCP can return more than just allocated IP address on subnet:address of first-hop router for clientname and IP address of DNS severnetwork mask (indicating network versus host portion of address)Network Layer 4-42IP addresses: how to get one?Q: How does network g

49、et subnet part of IP addr?A: gets allocated portion of its provider ISPs address spaceISPs block 11001000 00010111 00010000 00000000 /20 Organization 0 11001000 00010111 00010000 00000000 /23 Organization 1 11001000 00010111 00010010 00000000 /23 Organization 2 11001

50、000 00010111 00010100 00000000 /23 . . . .Organization 7 11001000 00010111 00011110 00000000 /23 Network Layer 4-43Hierarchical addressing: route aggregation“Send me anythingwith addresses beginning /20”/23/23/23Fly-By-Night-ISPOrgani

51、zation 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning /16”/23Organization 2.Hierarchical addressing allows efficient advertisement of routing information:Network Layer 4-44Hierarchical addressing: more specific routesISPs-R-Us has a more

52、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

53、ation 2.How to convert 8-bit binary code into decimal digit? 11001010=27+26+23+21=128+64+8+2=2021. 華工分配到一個華工分配到一個C類地址類地址，每個子網(wǎng)需要，每個子網(wǎng)需要20臺主機，臺主機，請進行子網(wǎng)規(guī)劃，并寫出子網(wǎng)掩碼。請進行子網(wǎng)規(guī)劃，并寫出子網(wǎng)掩碼。Solution: 20 neighbor/link declared deadmroutes via neighbor invalidatedmnew advertisements sent to neighborsmne

54、ighbors in turn send out new advertisements (if tables changed)Network Layer 4-101RIP table processingvRIP routing tables managed by application-level process called route-d (daemon)vadvertisements sent in UDP packets, periodically repeatedphysicallinknetwork forwarding (IP) tabletransport (UDP)rout

55、edphysicallinknetwork (IP)transprt (UDP)routedforwardingtableNetwork Layer 4-102Chapter 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 statemDistanc

56、e VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPNetwork Layer 4-103OSPF (Open Shortest Path First)r“open”: publicly availableruses link state algorithm mLS packet disseminationmtopology map at each nodemroute computation using Dijkstras algorithmrOSPF advertisement carries one

57、entry per neighbor radvertisements flooded to entire ASmcarried in OSPF messages directly over IP (rather than TCP or UDPNetwork Layer 4-104OSPF “advanced” features (not in RIP)rsecurity: all OSPF messages authenticated (to prevent malicious intrusion) rmultiple same-cost paths allowed (only one pat

58、h in RIP)rintegrated uni- and multicast support: mMulticast OSPF (MOSPF) uses same topology data base as OSPFrhierarchical OSPF in large domains.Network Layer 4-105Hierarchical OSPFboundary routerbackbone routerarea 1area 2area 3backboneareaborderroutersinternalroutersNetwork Layer 4-106Hierarchical

59、 OSPF rtwo-level hierarchy: local area, backbone.mLink-state advertisements only in area meach nodes has detailed area topology; only know direction (shortest path) to nets in other areas.rarea border routers: “summarize” distances to nets in own area, advertise to other Area Border routers.rbackbon

60、e routers: run OSPF routing limited to backbone.rboundary routers: connect to other ASs.Network Layer 4-107Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithms