计算机网络(自顶向下方法)配套课件Chapter4.

1、Network Layer4-1Chapter 4Network LayerA 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 rep

2、resent a lot of work on our part. In return for use, we only ask the following:q 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!)q If you post any slides in substantially unaltered form on a www si

3、te, 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-2007J.F Kurose and K.W. Ross, All Rights ReservedComputer Networking: A Top Down Approach 4th edition. Jim Kurose, Keith Ros

4、sAddison-Wesley, July 2007. Network Layer4-2Chapter 4: Network LayerChapter goals: runderstand principles behind network layer services:mIP addressing (寻址)mforwarding versus routing (转发 vs 路由)mrouting (path selection)madvanced topics: IPv6, mobilityrinstantiation, implementation in the InternetNetwo

5、rk 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 InternetmRIPmOSPFmBG

6、Pr4.7 Broadcast and multicast routingNetwork Layer4-4Vocabulary and TermrVirtual Circuit (VC) /Datagram m虚电路虚电路/数据报数据报rRouter/Switch/Hub/Repeaterm路由器路由器/交换机交换机/集线器集线器/中继器中继器rInput/Output Portm输入输入/输出输出 端口端口rSwitch Fabric 、Crossbarm交换结构、交叉开关交换结构、交叉开关rForwarding/Routingm转发转发/路由路由rFIB (Forwarding Infor

7、mation Base)/Route Tablem转发表转发表/路由表路由表Network Layer4-5Chapter 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 rout

8、ingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-6App. LayerApp. LayerHost 1 L2 L1L4L3Host 2L2 L1 L4 L3 MediaL1 ProtocolL2 ProtocolL3 ProtocolL4 Protocol InterfaceProtocol：comm rulesSegment332132Header132323DataApp. Protocol44444444AssembleDataNetwork La

9、yer4-7Network 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 passing through itapplica

10、tiontransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnet

11、workdata linkphysicalnetworkdata linkphysicalNetwork Layer4-8Journey of a PacketL1L2 L1 L2 L1L3 132323321325432154321HubSwitchRouterHostHostNetwork Layer4-9Two Key Network-Layer Functionsrforwarding: move packets from routers input to appropriate router outputrrouting: determine route taken by packe

12、ts from source to destination mrouting algorithmsanalogy:rrouting: process of planning trip from source to destinationrforwarding: process of getting through single interchangeNetwork Layer4-10Router FunctionsrSelect Best RouterForwarding （Interface ij）rControl（Congest, Security）DestNext-Hop-Dest Po

13、rt/NHNext-hop Cal. PacketNetwork Layer4-11Router StartuprPower-On Self Test (POST)rBoot ROM rLoading OSmIOS in FlashrLoading Configure InformationmConfig file in NVRAMrRun applicationsNetwork Layer4-121230111value in arrivingpackets headerrouting algorithmlocal forwarding tableheader value output li

14、nk01000101011110013221Interplay between routing and forwardingNetwork Layer4-13Connection 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

15、. transport layer connection service:mnetwork: between two hosts (may also involve inervening routers in case of Virtual Circuits)mtransport: between two processesNetwork Layer4-14Network service modelQ: What network service model for “channel” transporting datagrams from sender to receiver?Example

16、services for individual datagrams:rguaranteed deliveryrguaranteed delivery with less than 40 msec delayExample services for a flow of datagrams:rin-order datagram deliveryrguaranteed minimum bandwidth to flowrrestrictions on changes in inter-packet spacingNetwork Layer4-15Network layer service model

17、s:NetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteed minimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno (inferredvia loss)nocongestionnocongestionyesnoGuarantees ?Network Layer4-16Chapter 4: Ne

18、twork 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 mult

19、icast routingNetwork Layer4-17Network 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

20、 or the othermimplementation: in network coreNetwork Layer4-18Virtual circuitsrcall setup, teardown for each call before data can flowreach packet carries VC identifier (not destination host address)revery router on source-destination path maintains “state” for each passing connectionrlink, router r

21、esources (bandwidth, buffers) may be allocated to VC (dedicated resources = predictable service)“source-to-destination path behaves much like telephone circuit”mperformance-wisemnetwork actions along source-to-dest pathNetwork Layer4-19Circuit Switchingrdedicated resources: no sharingrguaranteed per

22、formanceRecallNetwork Layer 4-20VC 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 destination address)rVC number can be changed

23、 on each link.mNew VC number comes from forwarding tableNetwork Layer4-21Forwarding 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 inform

24、ation!Network Layer 4-22Virtual 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 co

25、nnected5. Data flow begins6. Receive dataNetwork Layer 4-23Datagram 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 differen

26、t pathsapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataNetwork Layer 4-24SummaryExchange TechnologyMessage SwitchingStore & ForwardingCircuit ExchangeVirtual CircuitDatagramPacket SwitchingNetwork Layer 4-25Forwarding table Desti

27、nation 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 billi

28、on possible entries ?Network Layer 4-26Longest 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 interfa

29、ce?Network Layer 4-27Datagram 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 characteristi

30、csmuniform service difficultATM (VC)revolved from telephonyrhuman conversation: mstrict timing, reliability requirementsmneed for guaranteed servicer“dumb” end systemsmtelephonesmcomplexity inside networkNetwork Layer 4-28Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram ne

31、tworksr4.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-29CISCO RoutersCisco1600Cisco2500Cis

32、co2600Cisco3600Cisco4000As5200/5300As5800Cisco7200Cisco7500Cisco12000Network Layer 4-30Routers: Low/Middle PerformanceNetwork Layer4-31Router: High-Performance Lucent NX64000CISCO 12000Network Layer 4-32Router InsiderCisco 2600Front endBack endNetwork Layer 4-33COM Port Network Layer 4-34Router Orga

33、nizationNetwork Layer 4-35Network Layer 4-36Router Architecture OverviewTwo key router functions: rrun routing algorithms/protocol (RIP, OSPF, BGP)rforwarding datagrams from incoming to outgoing linkNetwork Layer 4-37Input Port FunctionsDecentralized switching: rgiven datagram destination, lookup ou

34、tput 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-38Three types of switching

35、fabricsNetwork Layer 4-39Switching Via MemoryFirst generation routers:r traditional computers with switching under direct control of CPUr packet copied to systems memoryr speed limited by memory bandwidth (2 bus crossings per datagram)InputPortOutputPortMemorySystem BusNetwork Layer 4-40Switching Vi

36、a 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 Layer4-41Switching Via An Interconnection Networkrovercome bus bandwidth limitati

37、onsrBanyan networks, other interconnection nets initially developed to connect processors in multiprocessorradvanced design: fragmenting datagram into fixed length cells, switch cells through the fabric. rCisco 12000: switches 60 Gbps through the interconnection networkNetwork Layer 4-42Output Ports

38、rBuffering required when datagrams arrive from fabric faster than the transmission raterScheduling discipline chooses among queued datagrams for transmissionNetwork Layer 4-43Output port queueingrbuffering when arrival rate via switch exceeds output line speedrqueueing (delay) and loss due to output

39、 port buffer overflow!Network Layer 4-44How much buffering?rRFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) times link capacity Cme.g., C = 10 Gbps link: 2.5 Gb bufferrRecent recommendation: with N flows, buffering equal to RTT C.NNetwork Layer 4-45Input Port Queuingr

40、Fabric 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!Network Layer 4-46Fourth Generation RoutersSwitch CoreLin

41、ecardsOptical links100sof metres160Gb/s - 20Tb/s routers in developmentNetwork Layer 4-47HomeworkrReviews：2，3，7，10 Network Layer 4-48Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressin

42、gmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-49Network Layer 4-50Network Layer4-51Network Layer 4-52Ethernet HeaderPacket IP HeaderTCP HeaderHTTP Headere.g., HTTP BodyNet

43、work Layer 4-53The Internet Network LayerforwardingtableHost, router network layer functions:Routing protocolspath selectionRIP, OSPF, BGPIP protocoladdressing conventionsdatagram formatpacket handling conventionsICMP protocolerror reportingrouter “signaling”Transport layer: TCP, UDPLink layerphysic

44、al layerNetworklayerNetwork Layer 4-54IP 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)forfragmen

45、tation/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

46、 of TCPr20 bytes of IPr= 40 bytes + app layer overheadNetwork Layer 4-55IP Format （Chinese Version）Network Layer 4-56TTLrTime to livemmax number remaining hopsmdecremented at each routermTTL=0: discard (only in LAN when initial TTL=1)mToo small to reach the destinationmcan be used to count hops to d

47、estinationverlength16-bit identifierHeader checksumtime tolive32 bit source IP addresshead.lentype ofserviceflgsfragment offsetupper layer32 bit destination IP addressOptions (if any)Network Layer 4-57Internet Protocol Numbers ：2008-02-27/assignments/protocol-numbersr0-133：SAMEr134 RSVP

48、-E2E-IGNORE RFC3175r135 Mobility Header RFC3775r136 UDPLite RFC3828r137 MPLS-in-IP RFC4023r138 manet MANET Protocols RFC-ietf-manet-iana-07.txtr139 HIP Host Identity Protocol RFC-ietf-hip-base-10.txt r140-252 Unassigned IANAr253 Use for experimentation and testing RFC3692 r254 Use for experimentatio

49、n and testing RFC3692 r255 Reserved IANANetwork Layer 4-58IP Fragmentation & Re-assemblernetwork 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 datagram

50、sm“re-assembled” only at final destinationmIP header bits used to identify, order related fragmentsfragmentation: in: one large datagramout: 3 smaller datagramsreassemblyNetwork Layer 4-59IP Fragmentation & Re-assembleID=xoffset=0fragflag=0length=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=1

51、85fragflag=1length=1500ID=xoffset=370fragflag=0length=1040One large datagram becomesseveral smaller datagramsExample: Ethernetr4000 byte datagramrMTU = 1500 bytes1480 bytes in data fieldoffset =1480/8 Flag = 1 there is more fragmentFlag = 0 this is the last fragmentOffset: byte number of the 1st byt

52、e of the fragment (specified in units of 8-byte chunks)Network Layer 4-60Chapter 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 Vecto

53、rmHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-61Address AllocationrIANA：Internet Assigned Numbers Authority(互联网号码分配机构互联网号码分配机构)mDomain name, IP address, protocol parameters, root server management rICCAN：Internet Corporation for Ass

54、igned Names and Numbersmallocates addressesmmanages DNSmassigns domain names, resolves disputesrASO (Address Supporting Organization)mAdvisory on policy and structureNetwork Layer 4-62IP addressing: the last word.Q: How does an ISP get block of addresses?A: ICANN: Internet Corporation for Assigned N

55、ames and Numbersmallocates addressesmmanages DNSmassigns domain names, resolves disputesNetwork Layer 4-63IP AddressingrIP Address： Classful Addressing (有类寻址有类寻址)mA，B，C，D，E -5 ClassesrNetwork Mask (网络掩码网络掩码) rClassless Addressing (无类寻址无类寻址)mSubnet (子网子网) & Supernet (超网超网)rNAT (Network Address Tr

56、anslation)Network Layer 4-64IP Address Classes Class A: Class B: Class C: Class D: Multicast Class E: Research purposeNetworkHostHostHostNetwork NetworkHostHostNetwork Network NetworkHost8 bits8 bits8 bits8 bitsNetwork Layer 4-65Classful AddressingNetwork Layer 4-66IP in ChinaNetwork Layer 4-67IP in

57、 China (2005)rTelcom：34.70%rNetcom：21.40%rCERNET：15.08%rCNNIC：14.47%rUnicom：3.07%rMobile：2.84%r其他：8.43%Network Layer 4-68China IPv4 Allocation List (2007.1)Network Layer 4-69IP Address: 点分十进制表示法10000000000010110000001100011111 主机的 IP 地址是 32 位二进制代码10000000 00001011 00000011 00011111 每隔 8 位插入一个空格以提高可读

58、性 readable!1 128 11 3 31 将每 8位的二进制数转换为十进制数表示Network Layer 4-70Number of Networks and Hosts ClassNetworkNumber of NetworksHosts for each networkA - 27 2(125)224 -2(16 777 216)B -214 -2(16384)216 （ 64K ）-2(65 534)C - 221 2(2million)28

59、-2(254)Network Layer4-71How to get Network ID：by Network MaskClassBits for Network IDBits for host IDNetwork MaskA824B1616C248IP Address “AND” mask= Network ID Network Layer 4-72Example: Address0000 1000 0000 0001 0000 0100 0000 0101Mask1111 1111 0000

60、 0000 0000 0000 0000 0000Result0000 1000 0000 0000 0000 0000 0000 0000Address1000 0010 0000 0100 0110 0100 0000 0101Mask1111 1111 1111 1111 0000 0000 0000 0000Result1000 0010 0000 0100 0000 0000 0000 0000Example1: First 8 bits are network IDExample2: First 16 bits are network