计算机网络-4

1、网络层1第4章 网络层Network Layer计算机网络：自顶向下方法 (原书第四版)陈鸣译，机械工业出版社，2010年Computer Networking: A Top Down Approach , 4rd edition. Jim Kurose, Keith RossAddison-Wesley, July 2008. 网络层2第4章 网络层本章目的: r理解网络层服务依赖的原理:m选路 (路径选择)m处理扩展性m路由器工作原理m先进主题: IPv6, NATr因特网中的实例和实现网络层3第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP:

2、 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路算法m链路状态m距离矢量m等级选路r4.6 互联网中选路mRIPmOSPFmBGPr4.7 广播和多播选路网络层44.1网络层r从发送主机到接收主机传输段r在发送端将段封装进数据报r在接收端，向运输层交付段r网络层协议在每台主机、路由器中r当IP数据报通过路由器时，路由器检查所有数据报首部字段r路由器不运行应用层和运输层协议networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalne

3、tworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路层物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical网络层5关键的网络层功能r转发: 将分组从路由器的输入移动到适当的路由器输出r选路: 决定分组从源到目的地所采用的路由m选路算法P200类比:r选路: 规划从源到目的地路径的过程r转发: 通过单个立交桥的过程网络层61230111到达分组首部的值选路算法本地转发

4、表首部值输出链路01000101011110013221选路和转发相互影响转发：查询本地转发表选路：接收选路协议报文，以建立转发表网络层7连接建立r在数据报流动之前，两台主机和其间的路由器创建虚拟连接m需要路由器参与r网络层和运输层的连接服务:m网络层: 在两台主机之间m运输层: 在两个进程之间网络层84.1.2 网络服务模型问题：对从发送方到接收方“隧道”化传输数据报，其服务模型 是什么?对单个数据报的例子服务:r确保交付r以少于40 msec时延的时延上界确保交付对数据报流的例子服务:r按序数据报交付r对流确保最小带宽r对分组间间隔变化的限制r安全性网络层9网络层服务模型:网络体系结构服务

5、模型带宽保证无丢失保证排序定时拥塞指示因特网尽力而为无 无任何可能的顺序不维持无ATMCBR保证恒定速率 是有序维持拥塞不出现ATMABR保证最小速率 无有序不维持提供拥塞指示网络层10第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层114.2 网络层连接和无连接服务r网络层和运输层的连接服务:m网络层: 在两台主机之间m运输层: 在两个进程

6、之间r数据报网络提供网络层无连接服务r虚电路网络提供网络层连接服务r与运输层服务的类比:m服务: 主机到主机m无选择: 网络提供一个或其他m实现: 在网络内部网络层124.2.1虚电路r在数据流动之前，建立呼叫；然后拆除r每个分组携带VC标识符r在源到目的地路径上的每台路由器为每条经过的连接维护状态r链路、路由器资源(带宽、缓存)可能分配给VC“源到目的地路径与电话电路行为非常相似”m性能明确m沿着源到目的地路径的网络动作网络层13VC实现一条VC由下列组成:1.从源到目的地的路径2.VC号是标识沿路径每条链路的号码3.沿路径路由器中转发表中的项r属于VC的分组携带一个VC号r每条链路的VC号

7、必须改变m新的VC号来自转发表网络层14转发表122232132VC号接口号 入接口 入VC # 出接口 出VC #1 12 2 222 63 1 18 3 7 2 171 97 3 87 1路由器中的转发表 :路由器维护连接状态信息!虚电路的三个阶段r虚电路建立：发送方运输层与网络层联系，指定接收方地址，等待网络建立虚电路。网络层决定该虚电路经过的所有链路与路由器，并为每条链路确定一个VC号，同时在没太路由器的转发表中增加VC号与接口号的对应r数据传送：沿虚电路传送分组r虚电路拆分:发送方或接收方通知网络层要终止虚电路，则将通知另一段终止，并更新路径上每台路由器中的转发表网络层16虚电路:

8、信令协议r用于建立、维护和拆除VCr用于ATM、帧中继、X.25中r没有用于今天的因特网中应用运输网络数据链路物理应用运输网络数据链路物理1. 发起呼叫2. 入呼叫3. 接受呼叫4. 呼叫已连接5. 数据流开始6. 接收数据网络层174.2.2数据报网络r在网络层无呼叫建立r路由器：没有端到端连接的状态m无网络级“连接”的概念r分组使用目的主机地址转发m在相同源和目的对可能采用不同的路径应用运输网络数据链路物理应用运输网络数据链路物理1. 发送数据2. 接收数据网络层18转发表 目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 110010

9、00 00010111 00010111 11111111 11001000 00010111 00011000 00000000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 00010111 00011111 11111111 其他 340亿可能的项网络层19最长前缀匹配 前缀匹配 链路接口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 othe

10、rwise 3目的地址: 11001000 00010111 00011000 10101010 例子目的地址: 11001000 00010111 00010110 10100001 哪个接口?哪个接口?网络层20数据报或虚电路网络: why?因特网r在计算机间交换数据m“弹性”服务，无严格的定时要求r“智能” 端系统 (计算机)m能够适应，执行控制，差错控制m网络内部简单，“边缘”复杂r许多链路类型 m不同的特点m难以提供统一服务ATMr从电话技术演化来r人类交谈：m严格定时，可靠性要求m对确保服务的需求r“哑” 端系统m电话m网络内部复杂网络层21第4章 网络层r4. 1 概述r4.2

11、虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层224.3 路由器体系结构概述路由器的两个关键功能: r运行选路算法/协议(RIP, OSPF, BGP)r从入链路到出链路转发 数据报网络层234.3.1输入端口功能分散式交换分散式交换: P210（转发表的影子拷贝存放在每个输入端口中）r给定数据报目的地址, 在输入端口内存中使用转发表查找输出端口r目的: 以“线速”P210完成输

12、入端口处理，使用二分查找r排队：如果数据报到达速率比交换结构 的转发速率快物理层:比特级接收数据链路层:如以太网参见第5章网络层244.3.2三种类型的交换结构内存总线纵横制网络层25经内存交换第一代路由器:r 具有交换功能的传统计算机，在CPU的直接控制下r分组拷贝到系统的内存r速率受内存带宽限制(每数据报跨越两次总线)输入端口输出端口内存系统总线网络层26经总线交换r数据报从输入端口到输出端口内存经一个共享的总线，一次只能有一个分组通过总线传输r总线竞争: 交换速率受总线带宽限制r可达到1Gbps总线网络层27经互联网络的交换r克服了总线带宽限制r使用了2n条总线，形成nn的交叉网络总线r

13、先进的设计：数据报分段为固定长度的信元，通过交换结构转发信元r Cisco 12000: 通过互联网络交换，可达60Gbps网络层28三种交换结构比较内存总线纵横制网络层29r输出端口处理取出存放在输出端口内存中的分组并将其传送到输出链路上。r当交换结构将分组交付给输出端口的速率超过输出链路速率时，就需要排队与缓存管理。4.3.3输出端口网络层30r当数据报来自交换结构比传输速率更快时，需要缓存，当缓存用尽后，开始丢包。见下页图r调度安排 P214在排队数据报之间选择报文进行传输m先来先服务m加权公平排队r 主动队列管理（AQM）P214m随机早期检测：为输出队列长度维护一个加权平均长度m设定

14、最小阈值和最大阈值m平均长度最大阈值； 在两者之间；交换结构排队：缓存管理数据链路处理(协议、拆封)线路端接4.3.3输出端口网络层31输出端口排队r当到达速率经交换结构超过输出链路速率时缓存r因为输出缓存溢出，出现排队(时延)和丢包!交换结构交换结构在时间t输出端口竞争一个分组时间以后网络层32输入端口排队r交换结构比组合的输入端口慢- 排队可能出现在输入队列r线路前部(HOL)阻塞: 排队的数据报在队列的前面阻碍队列中的其他数据报转发r由于输入缓存溢出，出现排队时延和丢包!在时间t输出端口竞争，仅一个红色分组能被传输 绿色分组经历了HOL阻塞交换结构网络层33第4章 网络层r4. 1 概述

15、r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层344.4The Internet 网络层转发表主机，路由器网络层功能:选路协议路径选择RIP, OSPF, BGPIP 协议编址规则数据报格式分组处理规则ICMP 协议差错报告路由器“信令”运输层: TCP, UDP链路层物理层网络层网络层35IP:无连接交付系统r互联网服务被定义成分组交付系统。m服务是不可靠的，因为分组

16、可能丢失、重复、延迟或不按序交付等，但服务不检测这些情况，也不提醒发送方和接收方。m服务是尽力而为的，互联网并不随意地丢弃分组；只有当资源用完或底层网络出现故障时才可能出现不可靠性。m服务是无连接的，因为每个分组都是独立对待的。分组序列可能经过不同的传输路径或者有的丢失有的到达。网络层364.4.1 IP 数据报格式ver数据长度32 bits数据(变长,通常是一个TCP或UDP段)16-bit标识符首部检查和生命周期32 bit源IP地址IP协议版本号首部长度 (字节)剩余跳的最大数(在每台路由器减1)对分段/重装总数据报长度(字节)较高层协议交付的负载首部长度服务类型数据的“类型”标志段偏

17、移上层协议32 bit目的IP地址选项 (如果有的话)例如，时间戳，记录所经路径，定义访问的路由器列表TCP的开销多大?r20 字节 TCPr20 字节 IPr= 40字节+ 应用层开销网络层374.4.1 IP分片和重新组装r网络链路有MTU (最大传输长度) 最大可能的链路级帧m不同的链路类型MTU不同r在网络中，大IP 数据报被分割(“分段”)m一个数据报 变为几个数据报m“重新装配”仅在最后目的地mIP首部比特用于标识、排序相关段分段: 输入: 一个大的数据报输出: 3个小的数据报reassembly网络层38IP分片和重新组装ID=x偏移=0段标识=0长度=4000ID=x偏移=0段

18、标识=1长度=1500ID=x偏移=185段标识=1长度=1500ID=x偏移=370段标识=0长度=1040一个大数据报 变为几个较小的数据报例子r4000字节数据报rMTU = 1500字节在数据字段1480 字节偏移 =1480/8 网络层39第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层404.4.2 IP编址:概述rIP地址: 对

19、主机、路由器接口的32-bit 标识符 r接口: 在主机/路由器和物理链路之间的连接m路由器通常具有多个接口m主机可能具有多个接口mIP编址与每个接口相联系223.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网络层41子网r什么是子网 ?m具有IP地址相同的子网部分的设备接口m能够物理上互相到达而没有中间路由器rIP地址:m子网部分(高阶比特)m主机部分(低阶比

20、特) 223.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.27网络由3个子网组成LAN网络层42子网223.1.1.0/24223.1.2.0/24223.1.3.0/24判断方法r为了决定子网，从其主机或路由器分离每个接口，生成孤立网络的岛。每个孤立的网络被称为一个子网子网掩码: /24网络层43子网多少个子网?a.b.c.d/x组织外部的路由器仅考虑x前面的前缀，32-x就可以作为组织内将数据包转发到相应的主机的依据223.1.1.1223.1.1.3223.1.1

21、.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.2Interconnected system consistingof six networks网络层44保留的IP地址00.000000 . 000011.11 1111 . 1111本机本网中的主机局域网中的广播对指定网络的广播回路00.00主 机 号1111 . 1111网络号127任 意 值以下这些IP地址具有特殊的含义:一般来说，主机号部分为全“1

22、”的IP地址保留用作广播地址； 主机号部分为全“0 ”的IP地址保留用作网络地址。0000 . 0000网络号网络地址网络层45Private address (Rfc 1918)rclass A: 10.0.0.0-10.255.255.255 m10/8 prefixm number of subnets：1 rclass B 172.16.0.0-172.31.255.255 m172.16/12 prefixmnumber of subnets ：16rclass C 192.168.0.0-192.168.255.255 m192.168.0/24 prefixmnumber of

23、subnets ：255 网络层46IP编址: CIDR无类型域间选路(Classless InterDomain Routing,CIDR)m任意长的地址的子网部分m地址格式: a.b.c.d/x, 其中x是地址子网部分的比特长度11001000 00010111 00010000 00000000子网部分主机部分200.23.16.0/23网络层47IP编址问题：ISP怎样得到地址块?回答:因特网名字与号码分配团体( Internet Corporation for Assigned Names and Numbers,ICANN )m分配地址m管理DNSm分配域名，调解争议网络层48IS

24、P的块 1001000 00010111 00010000 00000000 200.23.16.0/20 组织 0 11001000 00010111 0001 0000 00000000 200.23.16.0/23 组织 1 11001000 00010111 0001 0010 00000000 200.23.18.0/23 组织 2 11001000 00010111 0001 0100 00000000 200.23.20.0/23 . . . .组织 7 11001000 00010111 0001 1110 00000000 200.23.30.0/23 IP编址:如何得到一个

25、地址?问题：网络怎样得到IP地址的子网部分?回答: 从它的ISP的地址空间得到分配的部分聚合网络层49r使用CIDR技术把4个C类网络192.24.12.0/24、192.24.13.0/24、192.24.14.0/24 和192.24.15.0/24 汇聚成一个超网，得到的地址是 。（1）A192.24.8.0/22 B192.24.12.0/22C192.24.8.0/21 D192.24.12.0/21 r设有下面 4 条路由： 172.18.129.0/24 、 172.18.130.0/24 、 172.18.132.0/24 和172.18.133.0/24 ，如果进行路由汇聚，

26、能覆盖这 4 条路由的地址是 。（2）A172.18.128.0/21 B172.18.128.0/22 C172.18.130.0/22 D172.18.132.0/23网络层50r某公司网络的地址是133.10.128.0/17，被划分成16个子网，下面的选项中不属于这16个子网的地址是 （3） 。 （3）A133.10.136.0/21B133.10.162.0/21 C133.10.208.0/21 D133.10.224.0/21 r以下地址中不属于网络100.10.96.0/20的主机地址是 （4） 。（4）A100.10.111.17B100.10.104.16 C100.10.

27、101.15 D100.10.112.18 r下给出的地址中，属于子网192.168.15.19/28 的主机地址（5） 。（5）A192.168.15.17 B192.168.15.14 C192.168.15.16 D192.168.15.31网络层51一个局域网中某台主机的IP 地址为176.68.160.12，使用22 位作为网络地址，那么该局域网的子网掩码为 （6） ，最多可以连接的主机数为 （7） 。（6）A255.255.255.0 B255.255.248.0 C255.255.252.0 D255.255.0.0（7）A254 B512 C1022 D1024一个网络的地址为

28、172.16.7.128/26，则该网络的广播地址是 （8） 。（8）A172.16.7.255B172.16.7.129C172.16.7.191 D172.16.7.252网络层52IP编址: 如何得到一个地址?问题：主机怎样得到IP地址?r由系统管理员在文件中的硬编码mWindows: 控制面板-网络-配置-TCP/IP-性质mUNIX: /etc/rc.configr动态主机配置协议(Dynamic Host Configuration Protocol DHCP): 动态地从服务器得到地址m“即插即用” 网络层53DHCP: Dynamic Host Configuration Pr

29、otocolGoal: allow host to dynamically obtain its IP address from network server when it joins network可以更新使用地址的租期允许地址的再利用支持需要加入网络的移动用户（或更短）除了为主机分配IP地址外，DHCP还允许一台主机获取其他信息，如子网掩码、第一跳路由器地址（默认网关）、本地DNS服务器地址P225DHCP步骤DHCP overview:P225mhost broadcasts “DHCP discover” msg：client在端口67发送该报文，由于不知道目的地址，因此使用广播地址

30、255.255.255.255，源地址使用0.0.0.0mDHCP server responds with “DHCP offer” msg：DHCP服务器作出相应，指明自己的ip，为client分配的ip，并用255.255.255.255广播出去mhost requests IP address: “DHCP request” msg：client选择一个DHCP服务器，广播mDHCP server sends address: “DHCP ack” msg：最后广播确认ACK网络层55DHCP client-server scenario223.1.1.1223.1.1.2223.1.

31、1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27ABEDHCP server arriving DHCP client needsaddress in thisnetwork223.1.2.5网络层56DHCP 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: 6

32、54DHCP 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.4transact

33、ion ID: 655Lifetime: 3600 secs网络层57网络规划案例r某个公司的区域网络分配了172.16.12.0/22的地址空间，公司的网络规划如下：r在路由器D连接3个VLAN，m其中 2个VLAN有不超过200台的主机，m另外一个VLAN包括3个子网，每个子网主机数量不超过30台，r路由器A，B，C通过FR和D相连，保证每条PVC仅分配2个IP地址。r所有路由器均采用RIPv2无类别路由协议，路由更新中可以传送子网掩码信息，支持VLSM。网络层58网络层59r由于需要3个VLAN，其中两个VLAN有不超过200台的主机，m根据公式，主机需要8位地址（28=25620027

34、=128），r子网需要2位（22=43），因此得到4个连续的/24位子网，分别是172.16.12.0 /24，172.16.13.0/24，172.16.14.0/24，172.16.15.0/24。r其中172.16.12.0/24和 172.16.13.0/24分配给其中两个VLAN，每个子网最多可以支持254台主机。网络层60r剩下一个VLAN每个子网主机数不超过30台，需要5个主机位，对应需要/27位的掩码(32-5=27)，最多可以满足8个/27位子网的需求（238）r由于172.16.12.0/24，和172.16.13.0/24子网已分配，不能继续作子网划分，现在可以采用的子网

35、是172.16.14.0/24和172.16.15.0/24作进一步的子网划分。r假定这里使用172.16.14.0/24，3个LAN 分配的子网是172.16.14.0/27，172.16.14.32/27，172.16.14.64/27，同时还保留了5个子网作为备用或保留作进一步的子网划分。 网络层61r由于WAN连接仅需要两个IP地址，所以最佳的掩码应该是/30位（2(32-30)-2=2），同样，我们挑选一个未分配的/27位子网做进一步的划分，为了方便起见，我们选用最后一个/27位子网172.16.14.224/27作为WAN连接的地址空间。经过划分得到172.16.14.224/30

36、，172.16.14.228/30，172.16.14.232/30等子网，同时还保留了5个/30的子网备用。 网络层62172.16.12.0/24172.16.13.0/24172.16.14.0/27172.16.14.32/27172.16.14.64/27172.16.14.224/30172.16.14.228/30172.16.14.232/30剩余可分配/24 的子网172.16.15.0/24剩余可分配/27 的子网172.16.14.96/27172.16.14.128/27172.16.14.160/27172.16.14.192/27172.16.14.224/27剩余

37、可分配/30 的子网172.16.14.236/30172.16.14.240/30172.16.14.244/30172.16.14.248/30172.16.14.252/30172.16.12.0/22网络层63第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层64NAT: 网络地址转换10.0.0.110.0.0.210.0.0.310

38、.0.0.4138.76.29.7本地网络(如归属网络)10.0.0/24因特网其他部分具有该网源或目的的数据报都有10.0.0/24的地址(照常)所有数据报本地离开本地网络具有相同的单一源NAT IP地址: 138.76.29.7,不同的源端口号网络层65NAT: 网络地址转换r动机: 外部关注本地网络只使用的一个IP地址 :m对ISP无需分配地址范围：对所有设备只用一个IP地址m能够改变本地网络中的设备地址，而不必通知外部m本地网络中的设备不显式地可寻址、由外部所见(增强安全性)网络层66NAT: 网络地址转换实现: NAT 路由器必须:m出数据报: 每个外出的数据报用(NAT IP地址,

39、 新port #) 代替(源IP地址, port #). . . 远程的客户机/路由器的响应，将用(NAT IP地址, new port #)作为目的地址 m记住(在NAT转换表中)每个 (源IP地址, port #)到(NAT IP地址, 新port #) 转换对m入数据报: 对每个入数据报的地址字段用存储在NAT表中的(源IP地址, port #)替代对应的 (NAT IP地址, 新port #) 网络层67NAT: 网络地址转换10.0.0.110.0.0.210.0.0.3S: 10.0.0.1, 3345D: 128.119.40.186, 80110.0.0.4138.76.29.

40、71: 主机10.0.0.1 发送数据报到128.119.40, 80NAT 转换表WAN 侧地址 LAN 侧地址138.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路由器改变数据报源地址从10.0.0.1, 3345 到138.76.29.7, 5001,更新表S: 128.119.40.186, 80 D: 138.76.29.7, 500133: 回答到达的目的地址: 138.76.29.7, 500

41、14: NAT 路由器改变数据报目的地址从138.76.29.7, 5001到10.0.0.1, 3345 网络层68NAT: 网络地址转换r16-bit 端口号字段: m用一个LAN侧地址支持60,000 并行连接!rNAT 引起争议:m端口号是进程的编址m路由器的处理最多达第三层分组m违反了端到端原则 修改了IP， 修改了端口号（T层属性）m地址短缺应当由IPv6来解决网络层69第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢

42、量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层70ICMP: 互联网控制报文协议r由主机和路由器用于网络级信息的通信m差错报告：不可达主机，网络，端口, 协议m回声请求/回答 (由 ping使用)r网络层 “上面的” IP:mIP 数据报中携带ICMP 报文rICMP报文: 类型、编码以及引起差错的IP 数据报 的前面 8 字节类型 编码 描述0 0 回声回答 (ping)3 0 目的网络不可达3 1 目的主机不可达3 2 目的协议不可达3 3 目的端口不可达目的端口不可达3 6 目的网络未知3 7 目的主机未知4 0 源抑制(拥塞控制未使用）8 0

43、 回声请求 (ping)9 0 路由通告10 0 路由器发现11 0 TTL过期12 0 坏的IP首部网络层71Traceroute和ICMPr源向目的地发送一系列UDP段m第一个 TTL =1m第二个 TTL=2, 等m不可能的端口号r当第n个数据报 到达第n个路由器:m路由器丢弃数据报m并向源发送一个ICMP报文 (类型 11, 编码0)m报文包括路由器的名字和IP地址r当ICMP报文到达，源计算 RTTrTraceroute执行上述过程3次停止规则rUDP段最终到达目的地主机r目的地返回ICMP “主机不可达”分组 (类型3, 编码3)r当源得到该ICMP, 停止网络层72第4章 网络层

44、r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层73IPv6r初始动机: 32-bit地址空间很快将会被完全分配完r附加的动机:m首部格式帮助加速处理/转发m首部变化以促进QoS IPv6 数据报格式: m固定长度 40 字节首部m不允许分段网络层74IPv6首部(续)优先级 : 标识特殊流的分组优先权流标签: 标识在相同“流”中的i数据报(流的概念没有很

45、好定义)下一个首部: 标识数据的上层协议网络层75与IPv4相比的其他变化r分片/重装：IPv6不允许在中间路由器上进行分片/重装r检查和: 完全去除以减小每跳的处理时间r选项: 允许，但在首部之外，可由“下一个首部”字段指示rICMPv6: 新版本的 ICMPm附加的报文类型，如 “分组太大”网络层76第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路算法m链路状态m距离矢量m等级选路r4.6 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层77直接

46、和间接交付r直接交付直接交付m是指在一个物理网络上，数据报从一台机器上直接传送到另一台机器上，这是所有互联网通信的基础。只有当两台机器同时连到同一底层物理传输系统时(例如一个以太网)，才能进行直接交付r间接交付间接交付m当目的地不在一个直接连接的网络上时，发送方必须把数据报发给一个路由器才能交付它r互联网中数据报交付的最后一步是直接交付，直接交付是间接交付的一个特例Q10.0.0.520.0.0.5R20.0.0.630.0.0.6S40.0.0.7网络10.0.0.0网络20.0.0.0网络30.0.0.0网络40.0.0.0网络层78选路选路算法的图论抽象:r图中的节点是路由器r图中的边是

47、物理链路m链路代价: 时延，费用或拥塞等级目的：决定从源到目的地通过网络的“好的路径”(路由器序列)选路 协议AEDCBF2213112535r“好的”路径:m通常意味着最小费用的路径m其他定义也是可能的网络层79选路算法分类全局的或分散的信息?r分散的: 路由器知道物理相连的邻居，到邻居的链路费用计算的迭代过程，与邻居交换信息“距离矢量” 算法r全局的:所有路由器具有完全的拓扑、链路费用信息“链路状态”算法s静态的或动态的?r静态: 路由随时间缓慢变化r动态: 路由更快地变化m周期的更新m适应链路费用变化网络层80A Link-State 选路算法Dijkstra算法r所有节点知道网络拓扑、

48、链路费用m经“链路状态广播”完成m所有节点具有相同信息r从一个节点(源)到所有其他节点计算最低费用路径m给出对这些节点的转发表r迭代: k次迭代后，得知到k个目的地的最低费用路径概念:rc(x,y): 从节点x到y的链路费用; = 如果不是直接邻居rD(v):从源到目的地v路径费用的当前值rp(v): 从源到v沿路径的前任节点rN: 已知在最小费用路径中的节点集合网络层81Dijsktra算法1 初始化初始化: 2 N = u 3 对所有节点v 4 if v 临近 u 5 then D(v) = c(u,v) 6 else D(v) = 7 8 Loop 9 找出w不在N中使得D(w)最小 1

49、0 将w加入N 11 对于所有v临近w并不在N中，更新D(v): 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* 到v的新费用或是到v的老费用或到w加上从w到v的已知最短路费用*/ 15 until 所有节点在所有节点在 N中中 Nwv网络层82Dijkstra 算法: 例子步骤012345NuuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)2,xD(z),p(z) 4,y4,y4,yyxwvz2213112535网络层83Dijkstra算法,

50、 讨论算法复杂性: n个节点r每次迭代: 需要检查所有节点w, 不在N中rn(n+1)/2 对比: O(n2)r更有效的实现是可能的: O(nlogn)网络层84第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层85距离矢量算法(1)Bellman-Ford方程 (动态规划)定义dx(y) := 从x到y最低费用路径的费用则dx(y) = mi

51、n c(x,v) + dv(y) 其中min对x的所有邻居XVVVVY网络层86Bellman-Ford 例子 (2)yxwvz2213112535Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3du(z) = min c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) = min 2 + 5, 1 + 3, 5 + 3 = 4取最小的节点是在最短路中的下一跳 转发表B-F equation says:网络层87距离矢量算法(3)基本思想: r每个节点周期性的发送它自己的距离矢量的估计到其邻居r当节点x接收到来自邻居的新

52、DV估计，它使用B-F方程更新其自己的DV :Dx(y) minvc(x,v) + Dv(y) for each node y Nr在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y) 网络层88距离矢量算法(4)迭代、异步: 每次本地迭代由下列引起: r本地链路费用改变rDV从邻居更新报文分布式:r每个节点仅当其DV改变时通知邻居m如果必要，邻居则通知它们的邻居等待 (来自邻居本地费用报文的变化)重新计算 估计值如果到任何目的地的DV已经变化, 通知 邻居 每个节点:网络层89x y zxyz0 2 7fromcost tofromfromx y zxyz0fromcos

53、t tox y zxyz cost tox y zxyz7 10cost to2 0 1 2 0 17 1 0timexz127ynode x tablenode y tablenode z tableDx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min2+0 , 7+1 = 2Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 332 网络层90 x y zxyz0 2 7fromcost tofromfromx y zxyz0 2 3fromcost tox y zxyz0 2 3f

54、romcost tox y zxyz cost tox y zxyz0 2 7fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 3fromcost tox y zxyz0 2 7fromcost tox y zxyz7 10cost to2 0 1 2 0 17 1 02 0 17 1 02 0 13 1 02 0 13 1 02 0 13 1 02 0 13 1 0timexz127ynode x tablenode y tablenode z tableDx(y) = minc(x,y) + Dy(y), c(x,z) + Dz(y) = min

55、2+0 , 7+1 = 2Dx(z) = minc(x,y) + Dy(z), c(x,z) + Dz(z) = min2+1 , 7+0 = 3网络层91距离矢量: 链路费用变化链路费用变化:r好消息传播得快r坏消息传播得慢“计数到无穷”问题!毒性逆转: r如果Z路由通过Y得到 X :mZ告诉Y它(Zs)到X的距离是无穷 (因此Y将不能经Z路由到X)r这将完全解决计数到无穷问题? xz1450y60网络层92LS和DV算法的比较报文复杂性rLS: 对n个节点，E条链路, 发送O(nE) 报文 rDV: 仅在邻居之间交换m收敛时间变化收敛速度rLS: O(n2) 算法要求 O(nE)报文m可能

56、具有振荡rDV: 收敛时间变化m可能有选路环路m计数到无穷问题健壮性: 如果路由器异常，将发生什么现象?LS: m节点可能通告不正确的链路费用m每个节点仅计算它自己的表DV:mDV节点通告不正确的路径费用m每个节点表能由其他人使用 差错通过网络传播网络层93第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选路算法m链路状态m距离矢量m等级选路r4.7 互联网中选路mRIPmOSPFmBGPr4.8 广播和多播选路网络层94层次选路规模: 具有2亿个目的地:

57、r在选路表中不能存储所有的目的地!r选路表交换将堵塞链路! 管理自治r互联网 = 网络的网络r每个网络管理员可能要控制他自己网络中的选路我们的选路研究至此是理想的r所有路由器是等同的r网络“扁平” 实践中并不真实网络层95层次选路r将某区域的路由器聚合成为 “自治系统” (AS)r在相同AS中的路由器运行相同的选路协议m“intra-AS” 选路协议m在不同的AS中的路由器能够运行不同的inter-AS 选路协议网关路由器r直接链路到在另一个AS中的路由器网络层963b1d3a1c2aAS3AS1AS21a2c2b1bAS内部选路 算法AS之间选路 算法转发表3c互联的ASr转发表由AS内部和

58、AS之间的选路算法所配置mAS内部设置内部目的地表项mAS之间和AS内部对外部目的地设置表项网络层973b1d3a1c2aAS3AS1AS21a2c2b1b3cAS间的任务r假定在AS1中的路由器接收目的地是AS1外部的数据报m路由器应当将分组朝着网关路由器转发，但哪个呢？AS1需要:1.知道通过AS2可到达哪些目的地，通过AS3到达哪些2.传播这些可达信息到AS1中所有路由器AS间选路的工作!网络层98例子: 设置路由器1d的转发表r假定AS1从AS间协议得知子网 x 从AS3(网关1c)可达，而不是从AS2到达rAS间协议传播可达性信息到所有内部路由器r路由器1d从AS内部信息决定，它的接

59、口I正处于到1c的最低费用路径上r在转发表中放入表项(x,I).3b1d3a1c2aAS3AS1AS21a2c2b1b3cx网络层99从AS间协议得知，子网x经多个网关可达使用来自AS内部协议选路信息，以决定到每个网关的最低费用路径热土豆选路:选择具有最小费用的网关从转发表决定接口I 通向最低费用网关。表项Enter (x,I) 在转发表中例子: 在多个AS之间选择r现在假定AS 1从AS间协议得知，子网x 从AS3和从AS2可达r为了配置转发表, 路由器1d必须决定对目的地x ，它应当将分组转发向哪个网关r这也是AS间选路协议的工作!r热土豆选路: 发送分组朝着两个路由器中最近的那个3b1d

60、3a1c2aAS3AS1AS21a2c2b1b3cx网络层100R1H1H2内部网关协议IGP（例如，RIP）自治系统 A自治系统 B自治系统 CIGPIGPIGPIGPIGPIGPIGPIGPIGPIGPIGPIGPEGPEGPEGP内部网关协议IGP（例如，OSPF）外部网关协议EGP（例如，BGP-4）IGPR3R2自治系统和内部网关协议、外部网关协议自治系统和内部网关协议、外部网关协议 网络层101第4章 网络层r4. 1 概述r4.2 虚电路和数据报网络r4.3 路由器的构成r4.4 IP: 网际协议m数据报格式mIPv4编址mNATmICMPmIPv6r4.5 选路概念r4.6 选