计算机网络课件：Chapter4 Network Layer

1、Network Layer4-1Chapter 4Network LayerComputer Networking: A Top Down Approach Featuring the Internet, 3rd edition. Jim Kurose, Keith RossAddison-Wesley, July 2004. A note on the use of these ppt slides:Were making these slides freely available to all (faculty, students, readers). Theyre in PowerPoi

2、nt 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:q If you use these slides (e.g., in a class) in substantially unaltered form, that you mention

3、 their source (after all, wed like people to use our book!)q 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 19

4、96-2006J.F Kurose and K.W. Ross, All Rights ReservedNetwork 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

5、, 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 Vector

6、mHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-4Network layerrtransport segment from sending host to receiving host ron sending side encapsulates segments into datagrams (packet)ron rcving side, delivers segments to transport layerrne

7、twork layer protocols in every host, routerrRouter examines header fields in all IP datagrams passing through itnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphys

8、icalapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata 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 algorithmsanalo

9、gy: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 link01000101011110013221Interplay between routing and forwardingNetwork

10、Layer4-7Connection setuprConnection setup（except for forwarding and routing） is the 3rd important function of network layer in some network architectures:mATM, frame relay, X.25rbefore datagrams flow, two end hosts and intervening routers establish virtual connectionmrouters get involvedrnetwork vs

11、transport layer connection service:mnetwork: between two hosts (may also involve intervening routers in case of VCs)mtransport: between two processesNetwork Layer4-8Network service modelQ: What service model for “channel” transporting datagrams from sender to receiver?Example services for individual

12、 datagrams:rguaranteed deliveryrguaranteed delivery with less than 40 msec delayBut Internet only provides “best-effort service” in which seams almost “nothing”.Example services for a flow of datagrams:rin-order datagram deliveryrguaranteed minimum bandwidth to flowrrestrictions on changes in inter-

13、packet spacingNetwork Layer4-9Network layer service models:NetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABR(Available)UBRBandwidthnoneConstantBit Rateguaranteedrateguaranteed minimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno (inferredvia loss

14、)nocongestionnocongestionyesnoGuarantees ?Network Layer4-10Chapter 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

15、 routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-11Network layer connection and connection-less servicerdatagram network provides network-layer connectionless servicerVC network provides network-layer connection serviceranalogous to the transport-la

16、yer services, but:mservice: host-to-hostmno choice: network provides one or the other, not both of them.mimplementation: beside in end system also in network coreNetwork Layer4-12Virtual circuitsrcall setup, teardown for each call before/after data can flowreach packet carries VC identifier (not des

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

18、ns along source-to-dest pathNetwork Layer4-13VC 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

19、be changed on each link.mNew VC number comes from forwarding tablem一条虚电路上的逐段链路不使用同一VC号,能够”减少分组首部中VC字段的长度”,且”大大简化了虚电路的建立,免得路由器交换和处理相当大量的报文”Network Layer4-14Forwarding table122232123VC numberinterfacenumberIncoming interface Incoming VC # Outgoing interface Outgoing VC #1 12 3 222 63 1 18 3 7 2 171 97

20、 3 87 Forwarding table innorthwest router:Routers maintain connection state information!创建一新连接时,新连接项加入表中;释放一旧连接时,从表中删除该项.Network Layer4-15Virtual circuits: signaling protocols(交换用于建立与释放连接的信令报文的协议)rused to setup, maintain teardown VCrused in ATM, frame-relay, X.25rnot used in todays Internetapplicati

21、ontransportnetworkdata linkphysicalapplicationtransportnetworkdata 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 connection

22、smno network-level concept of “connection”rpackets forwarded using destination host addressmpackets between same source-dest pair may take different pathsm路由器中有将目的地址映射到链路接口的转发表applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataNetwork L

23、ayer4-17Forwarding 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 000111

24、11 11111111 otherwise 332 bits addr. means near 4 billion possible entries(表项) need to establish难以实施.采用前缀匹配来简化实现.Network Layer4-18Longest prefix matching Prefix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3转发表中只需这四个表项既可转发表中只需这四个表项既可

25、.DA: 11001000 00010111 00011000 10101010 ExamplesDA: 11001000 00010111 00010110 10100001 Which interface?Which interface?Network Layer4-19Datagram or VC network: why?Internet (datagram)rdata exchange among computersm“elastic” service, no strict timing req. r“smart” end systems (computers)mcan adapt,

26、 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 systemsmtelepho

27、nesmcomplexity inside networkNetwork Layer 4-20Chapter 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

28、 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-21Router Architecture OverviewTwo key router functions: rrun routing algorithms/protocol (RIP, OSPF, BGP)rforwarding datagrams from incoming to outgoing linkNetwork Layer 4-22Input Port FunctionsDecentralized (分散

29、式分散式) switching: rgiven datagram dest., lookup output port using forwarding table in input port memoryrgoal: complete input port processing at line speed(执行一次查找的时间应小于从输入端口接收一个分组所需的时间)rqueuing: if datagrams arrive faster than forwarding rate (into switch fabric) 线路端接 Physical layer:bit-levelreception

30、Data link layer:e.g., Ethernetsee chapter 5Network Layer 4-23Three types of switching fabricsNetwork Layer 4-24Switching Via MemoryFirst generation routers:r traditional computers with switching under direct control of CPUrpacket copied to systems memory(借助于选路处理器)r speed limited by memory bandwidth

31、(2 bus crossings per datagram同一分组用了两倍时间完成写/读)InputPortOutputPortMemorySystem BusNetwork Layer 4-25Switching Via a Bus (无需选路处理器干预)rdatagram from input port memory to output port memory via a shared bus (一次只能有一个分组通过总线传送)rbus contention: switching speed limited by bus bandwidthr1 Gbps bus, Cisco 1900:

32、sufficient speed for access and enterprise routers (接入网和企业网,not regional or backbone)Network Layer 4-26Switching Via An Interconnection Network (纵横制)rovercome bus bandwidth limitationsrBanyan networks, other interconnection nets initially developed to connect processors in multiprocessor architectur

33、erAdvanced design: fragmenting datagram into fixed length cells且加上标签,然后switch cells through the fabric. 从而大大简化和加快了分组的交换.rCisco 12000: switches 60 Gbps through the interconnection network(借助于选路处理器)Network Layer 4-27Output PortsrBuffering required when datagrams arrive from fabric faster than the tran

34、smission raterScheduling discipline chooses among queued datagrams for transmissionNetwork Layer 4-28Output port queueingrbuffering when arrival rate via switch exceeds output line speedrqueueing (delay) and loss due to output port buffer overflow! (丢失发生取决于流量、负载交换结构的相对速率和线路速率等因素，其概率值一般是与平均队列长度、最小阈值和

35、最大阈值有关的函数值)(NCRTTBNetwork Layer 4-29Input Port QueuingrFabric speed is 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 forward (线路前部阻塞)rqueueing delay and loss due to input

36、buffer overflow!Network Layer 4-30Chapter 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 t

37、he InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer4-31The Internet Network layerforwardingtableHost, router network layer functions(三个重要组件完成):Routing protocolspath selectionRIP, OSPF, BGPIP protocoladdressing conventions(规则)datagram formatpacket handling conventionsICMP protoc

38、olerror reportingrouter “signaling”Transport layer: TCP, UDPLink layerphysical layerNetworklayerNetwork Layer 4-32Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Rou

39、ting algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-33IP datagram formatverlength32 bitsdata (variable length,typically a TCP or UDP segment;也可是ICMP报文段)16-bit identifierheader checksumtime tolive3

40、2 bit source IP addressIP protocol versionNumber（4位）header length（4位） (首部bytes:至少20B)max numberremaining hops(decremented at each router:减为零时丢弃)for fragmenta-tion/Reassembly（标识;16位;标志:3位,有1位表示分片是否为最后一个分片-置0;片偏移:13位,以8字节块为单位）total datagramlength (bytes): 1500Bupper layer protocolto deliver payload to

41、(6:TCP;17:UDP)head.lentype ofservice8个优先级：3位；D（延迟）、T（吞吐量）、R（可靠性）、C （费用）各1位；1位未用。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 lay

42、er overheadNetwork Layer 4-34IP Fragmentation & Reassembly(路由器的分片与目的主机的组装)rnetwork links have MTU (max.transfer size) - largest possible link-level frame.mdifferent link types, different MTUs (以太网frame1500B,而广域网链路的frame576B)rlarge IP datagram divided (“fragmented”,) within net (因IP数据报被封装在链路层的fra

43、me中,故受其MTU 所约束)mone datagram becomes several datagramsm“reassembled” only at final destinationmIP header bits used to identify, order related fragmentsfragmentation: in: one large datagramout: 3 smaller datagramsReassembly组装Network Layer 4-35IP Fragmentation and ReassemblyID=xoffset=0fragflag=0lengt

44、h=4000ID=xoffset=0fragflag=1length=1500ID=xoffset=185fragflag=1length=1500ID=xoffset=370fragflag=0length=1040One large datagram becomesseveral smaller datagramsExampler4000 byte datagram (含有20B的头,数据为3980B)rMTU = 1500 bytes第一片:1480 bytes in data field(0到1479B)第二片: offset =1480/8 (data field:1480到2959

45、B)第三片:数据为1020B(3980-1480-1480, 2960到3979B)Network Layer 4-36Chapter 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 VectormHierarchica

46、l routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routingNetwork Layer 4-37IP Addressing: introductionrIP address: 32-bit identifier for host, router interface rinterface: connection between host/router and physical linkmrouters typically have multiple interfacesmhost ty

47、pically has one interfacemIP addresses associated with each interface (技术上IP地址与接口相关联,而非主机或路由器)7 = 11011111 00000001 00000001 00000001223111Network Layer 4-38SubnetsrIP address: msubnet part (high order

48、 bits)mhost part (low order bits) rWhats a subnet ?mdevice interfaces with same subnet part of IP addressmcan physically reach each other without intervening router7network consisting of 3 subnetssubnetNetwork

49、Layer 4-39Subnets/24/24/24 To 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-4

50、0SubnetsHow many? 6个:/24,/24,/24,和/24,/24,/247Network Layer4-41IP addressing: CIDR （无类别域间选路） CIDR: Cla

51、ssless InterDomain Routing 这是英特网的地址分配策略，将32位的IP地址划分为两部分。msubnet portion of address of arbitrary lengthmaddress format: a.b.c.d/x, where x is # bits in subnet portion of address采用CIDR之前，有A、B、C(网络地址分别为8 、16和24位)、D和E类网络的“分类编址”方案，易造成IP地址的浪费或地址空间的低利用率。11001000 00010111 00010000 00000000subnetparthostpart

52、/23Network Layer 4-42IP addresses: how to get one? Q: How does host get IP address? 是先获得主机所在组织的块地址,然后由该组织为其内的主机或路由器接口分配独立的IP地址。rhard-coded （手动配置）by system admin in a filemWintel: control-panel-network-configuration-tcp/ip-propertiesmUNIX: /etc/rc.configrDHCP(Dynamic Host Configuration Pro

53、tocol): dynamically get address from the DHCP serverm“plug-and-play协议” （能将主机自动连接进一个网络）mC/S结构协议, four steps: DHCP server发现（主机广播发送DHCP发现报文的IP数据报，找到要与自己交互的DHCP server ）； DHCP server提供（用一个携带了推荐的IP地址及租用期、网络掩码等信息的DHCP提供报文以响应）； DHCP请求（用携带了配置参数的请求报文对选中的服务器进行响应、回显配置参数）；DHCPACK（被选中的服务器用DHCPACK 报文进行相应，证实所要求的参数

54、）Network Layer 4-43IP addresses: how to get one?Q: How does network get 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 11

55、001000 00010111 00010010 00000000 /23 Organization 2 11001000 00010111 00010100 00000000 /23 . . . .Organization 7 11001000 00010111 00011110 00000000 /23 Network Layer 4-44IP addressing: the last word.Q: How does an ISP get block of addresses?A: ICANN: Internet Corp

56、oration for Assigned Names and Numbersmallocates addresses（给地区性英特网注册机构）mmanages DNSmassigns domain names, resolves disputes（分配域名,解决域名纷争）Network Layer 4-45NAT: Network Address Translation（英特网的一个重要组件）local network(e.g., home network)10.0.0/24rest ofInternetDa

57、tagrams 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: ,different source port numbersNetwork Layer 4-46NAT: Network Address Translation Implementation: NAT router

58、 (NAT使能路由器) must:moutgoing datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #) 所有离开NAT使能路由器通向Internet的报文都具有同一个源的IP地址(NAT IP address) 和new port #。. . . remote clients/servers will respond using (NAT IP address, new port #) as destination addr.mrem

59、ember (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 table 所有来自Internet流向NAT使

60、能路由器的报文都具有同一个目的IP地址(NAT IP address) 和new port #，且进入后将其置换成已存储在NAT translation table中与之配对的(source IP address, port #) 。Network Layer 4-47NAT: Network Address TranslationS: , 3345D: 86, 801: host sends datagram to 86, 80NAT tr