计算机网络自顶向下方法第四章讲义

1、计 算 机 网 络20142014年年9 9月月国防科技学院国防科技学院第第4 4章章 网络层网络层2第第4 4章章 网络层网络层计算机网络第第4 4章章 网络层网络层3本章目的: 理解网络层服务依赖的原理:u选路 (路径选择)u处理扩展性u路由器工作原理u先进主题: IPv6, NAT因特网中的实例和实现 第4章 网络层第第4 4章章 网络层网络层44. 1 概述概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第第4 4章章 网络层网络层5 从发送主机到接收主机传输段 网络层协议在每台主机、路由器中 当IP数

2、据报通过路由器时，路由器检查所有数据报首部字段networkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysical网络层数据链路物理层applicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical 网络层第第4 4章章

3、 网络层网络层6转发（ forwarding ）: 将分组从路由器的输入移动到适当的路由器输出选路（ routing ）: 决定分组从源到目的地所采用的路由u选路算法类比:r选路: 规划从源到目的地路径的过程r转发: 通过单个立交桥的过程 转发与选路(网络层功能)第第4 4章章 网络层网络层71230111到达分组首部的值选路算法本地转发表首部值输出链路01000101011110013221 选路和转发相互影响第第4 4章章 网络层网络层8它是在某些网络体系结构中第三个重要的功能:uATM, 帧中继, X.25在数据报流动之前，两台主机和其间的路由器创建虚拟连接u需要路由器参与网络层和运输层

4、的连接服务:u网络层: 在两台主机之间u运输层: 在两个进程之间 连接建立(网络层功能)第第4 4章章 网络层网络层9问题：对从发送方到接收方“隧道”化传输数据报，其服务模型 是什么?对单个数据报的例子服务: 确保交付 以少于40毫秒时延确保交付对数据报流的例子服务: 按序数据报交付 对流确保最小带宽 对分组间间隔变化的限制（确保最大时延抖动） 网络服务模型第第4 4章章 网络层网络层104. 1 概述4.2 虚电路和数据报网络虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第第4 4章章 网络层网络层11 虚电路与数据报

5、网络层为接在网络上的主机所提供的服务可以有两大类u无连接的网络服务（数据报服务）u面向连接的网络服务（虚电路服务）第第4 4章章 网络层网络层12 数据传输前，需建立连接，一个连接被称为一条虚电路VC 虚电路由VC号来标识和区分 虚电路连接的状态需要维持（路径上的交换节点都参与） 虚电路连接涉及资源预留问题“源到目的地路径与电话电路行为非常相似”u性能明确u沿着源到目的地路径的网络动作 虚电路第第4 4章章 网络层网络层13H1H5H2H4H3ACDBH6E分组交换网H1 要和 H5 通信虚电路H1 向 H5 发送的所有分组都沿此虚电路传送。 虚电路建立连接第第4 4章章 网络层网络层14H1

6、H5H2H4H3ACDBH6E分组交换网同理，H2 与 H6通信也要建立虚电路 虚电路建立连接第第4 4章章 网络层网络C号接口号 入接口 入VC # 出接口 出VC #1 12 2 222 63 1 18 3 7 2 171 97 3 87 西北路由器中的转发表 :路由器维护连接状态信息! VC号与转发表 VC号局部的，而非全网的，以简化虚电路的连接建立。第第4 4章章 网络层网络层16 虚电路建立（信令协议控制） 数据传输 虚电路拆除（信令协议控制）应用运输网络数据链路物理应用运输网络数据链路物理1. 发起呼叫2. 入呼叫3. 接受呼叫4. 呼叫已连接5. 数据流

7、开始6. 接收数据 虚电路的三个阶段第第4 4章章 网络层网络层17 在网络层无呼叫建立 路由器：没有端到端连接的状态u无网络级“连接”的概念 分组使用目的主机地址转发u在相同源和目的对可能采用不同的路径应用运输网络数据链路物理应用运输网络数据链路物理1. 发送数据2. 接收数据 数据报网络第第4 4章章 网络层网络层18 数据报网络H1H5H2H4H3ACDBH6E分组交换网H1 向 H5 发送分组H2 向 H6 发送分组路径可能变化第第4 4章章 网络层网络层19 目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 11001000 00

8、010111 00010111 11111111 11001000 00010111 00011000 00000000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 00010111 00011111 11111111 其他 340亿可能的项 转发表第第4 4章章 网络层网络层20 前缀匹配 链路接口 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2

9、otherwise 3目的地址: 11001000 00010111 00011000 10101010 例子目的地址: 11001000 00010111 00010110 10100001 哪个接口?哪个接口? 最长前缀匹配第第4 4章章 网络层网络层21 数据报和虚电路比较对比的方面 虚电路服务 数据报服务 思路 可靠通信应当 可靠通信应当 由网络来保证 由用户主机来保证连接的建立 必须有 不要分组的转发 属于同一条虚电路 每个分组独立选择 的分组均按照同一 路由进行转发 路由进行转发当节点出 所有通过出故障的 故障结点可能丢失 故障时 结点的虚电路 分组，一些路由 均不能工作 可能会发

10、生变化分组的顺序 总是按发送顺序 到达目的站时不一定 到达目的站 按发送顺序第第4 4章章 网络层网络层224. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成路由器的构成4.4 IP: 网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第第4 4章章 网络层网络层23思科(Cisco)公司创始人列昂纳德波萨克 和桑德拉勒纳 第一台路由器及其开发者第第4 4章章 网络层网络层24 路由器图示（华为）第第4 4章章 网络层网络层25路由器的主要功能u运行路由算法以得到转发表u根据转发表对IP分组进行转发u提供多种网络类型接口，完成不同网络的互联 路由器功能概要第第4 4章

11、章 网络层网络层26 路由器体系结构 路由器一般由以下部分组成u输入/输出端口u交换结构u选路处理器第第4 4章章 网络层网络层27 数据链路层剥去帧首部和尾部后，将分组送到网络层的队列中排队等待处理。这会产生一定的时延。 输入端口处理物理层处理数据链路层处理网络层处理 分组排队 交换结构 输入端口的处理从线路接收分组查表和转发第第4 4章章 网络层网络层28 当交换结构传送过来的分组先进行缓存。数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。 输出端口处理物理层处理数据链路层处理网络层处理 分组排队 输出端口的处理向线路发送分组缓存管理交换结构第第4 4章章 网络

12、层网络层29内存总线纵横制 交换结构（典型三种）第第4 4章章 网络层网络层30第一代路由器: 具有交换功能的传统计算机，在CPU的直接控制下分组拷贝到系统的内存速率受内存带宽限制(每数据报跨越两次总线)输入端口输入端口输出端口输出端口内存内存系统总线系统总线 经内存交换第第4 4章章 网络层网络层31 数据报从输入端口到输出端口内存经一个共享的总线（总线芯片），总线速度快于内存读取速度 总线竞争: 任何时刻，总线仅能连通1个输入和1个输出，数据转发速率受总线带宽限制 1 Gbps总线, Cisco 1900: 用于接入和企业(非区域或主干)路由器的充足速率 经总线交换第第4 4章章 网络层网

13、络层32 克服了总线带宽限制 Crossbar一般同时满足多个输入和输出连通 一般是路由交换机 Cisco 12000: 通过互联网络交换提供60Gbpscrossbarswitching fabric 经互联网络的交换第第4 4章章 网络层网络层334. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议网际协议4.5 选路算法4.6 互联网中选路4.7 广播和多播选路第第4 4章章 网络层网络层34 网络层与IP协议各种应用层协议 网络接口层(TELNET, FTP, SMTP 等)物理硬件运输层TCP, UDP应用层ICMPIPRARPARP与各种网络接口网络

14、层IGMP互联网的IP服务被定义成分组交付系统。第第4 4章章 网络层网络层35固定部分可变部分04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部传送IP 数据报首部 IP数据报格式第第4 4章章 网络层网络层36可变部分首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数

15、据 部 分首 部传送IP 数据报固定部分第第4 4章章 网络层网络层37首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分数 据 部 分首 部传送IP 数据报固定部分可变部分第第4 4章章 网络层网络层38首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）首部长度数 据 部 分固定部分可变部分版本占 4 bit，指I

16、P协议的版本目前的 IP 协议版本号为 4 (即 IPv4)第第4 4章章 网络层网络层39首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分首部长度占 4 bit，可表示的最大数值是 15 个单位(一个单位为 4 字节)因此 IP 的首部长度的最大值是60字节。第第4 4章章 网络层网络层40首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目

17、的 地 址可 选 字 段 （长 度 可 变）比特首部长度01234567DTRC未用优 先 级数 据 部 分比特固定部分可变部分服务类型占 8 bit，用来获得更好的服务这个字段以前一直没有被人们使用 第第4 4章章 网络层网络层41首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分总长度占 16 bit，指首部和数据之和的长度，单位为字节，因此数据报的最大长度为 65535 字节。总长度必须不超过最大传送单元 MTU。 第第

18、4 4章章 网络层网络层42首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分标识、标志、片偏移：用于IP分片功能。 第第4 4章章 网络层网络层43首部版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）首部长度数 据 部 分固定部分可变部分协议(8 bit)字段指出此数据报携带的数据使用何种协议以便目的主机的 IP 层将数据

19、部分上交给哪个处理过程TCP：6 UDP：1704816192431比特第第4 4章章 网络层网络层44首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）比特首部长度数 据 部 分固定部分可变部分首部检验和(16 bit)字段只检验数据报的首部不包括数据部分。 第第4 4章章 网络层网络层45首部04816192431版 本标志生 存 时 间协 议标 识服 务 类 型总 长 度片 偏 移填 充首 部 检 验 和源 地 址目 的 地 址可 选 字 段 （长 度 可 变）

20、比特首部长度数 据 部 分固定部分可变部分源地址和目的地址都各占 4 字节第第4 4章章 网络层网络层46 网络链路有MTU (最大传输长度) 最大可能的链路级帧u不同的链路类型及MTU 在网络中，大IP 数据报被分割(“分段”)u一个数据报 变为几个数据报u“重新装配”仅在最后目的地uIP首部比特用于标识、排序相关段reassembly IP分片和重新组装第第4 4章章 网络层网络层47ID=x偏移=0段标识=0长度=4000ID=x偏移=0段标识=1长度=1500ID=x偏移=185段标识=1长度=1500ID=x偏移=370段标识=0长度=1040一个大数据报 变为几个较小的数据报例子4

21、000字节数据报MTU = 1500字节在数据字段1480 字节偏移 =1480/8 IP分片和重新组装第第4 4章章 网络层网络层48 IP地址: 对主机、路由器接口的32-bit 标识符 接口: 在主机/路由器和物理链路之间的连接u路由器通常具有多个接口u主机可能具有多个接口uIP编址与每个接口相联系7 = 11011111 00000001 00000001 00000001223111 IP

22、编址:概述点分十进制记法第第4 4章章 网络层网络层49 两级IP地址: u子网部分，网络号，网络前缀(高阶比特)u主机部分，主机号(低阶比特) 什么是子网 ?uIP地址具有相同的子网部分的设备接口（具有共同的IP地址前缀）u无需通过路由器就能够物理上互相到达7网络由3个子网组成LAN 子网第第4 4章章 网络层网络层50/24/24/24判断方法 为了决定子网，

23、从其主机或路由器分离每个接口，生成孤立网络的岛。每个孤立的网络被称为一个子网子网掩码: /24子网的表示方法： 1、子网掩码：子网掩码：用从最高位开用从最高位开始的连续始的连续1表示表示IP地址中的子网地址中的子网号部分号部分 2、前缀前缀/长度：长度：/24，表示前表示前24位为子网号部分位为子网号部分 子网第第4 4章章 网络层网络层51多少个子网?7223.

24、1.8.0 子网第第4 4章章 网络层网络层52 分类IP编址net-id24 bithost-id24 bitnet-id16 bitnet-id8 bit0A 类地址host-id16 bitB 类地址C 类地址01 1host-id8 bitD 类地址 1 1 1 0多 播 地 址E 类地址保 留 为 今 后 使 用1 1 1 1 001第第4 4章章 网络层网络层53 分类IP编址 网络数uA类：27-2；B类：214 ；C类：221u网络号不能为全0；127.X.X.X为循环测试保留地址 主机数uA类：224-2；B类：216-2

25、 ；C类：28-2u主机号全0代表网络本身；主机号全1代表本子网的广播地址 地址范围（包括网络地址本身，广播地址，私有地址等）uA类： 55uB类： 55uC类： 55uD类： 55uE类： 55第第4 4章章 网络层网络层54 私有地址 私有地址：在互联网中不使用，仅在局域网中使用的IP地址u10.X.X.X (A类)u55 (B类)u

26、192.168.X.X (C类)第第4 4章章 网络层网络层55无类型域间选路(Classless InterDomain Routing, CIDR)u子网为连续地址的地址块u由网络前缀（如/25）确定网络部分的比特长度u（地址块，主机地址）格式: a.b.c.d/x11001000 00010111 00010000 00000000子网部分主机部分/23 CIDR(无类域间路由)-不分类编址第第4 4章章 网络层网络层56 地址块描述的例子 某地址块为/23，则其u子网掩码为： 或 /23u网络地址为：200.23.1

27、6.0 (主机比特全0)u可用主机地址为：54u广播地址为：55 (主机比特全1) 某地址块为/25，则其u子网掩码为：28 或 /25u网络地址为：u可用主机地址为：26u广播地址为：27第第4 4章章 网络层网络层57问题：主机怎样得到IP地址? 由系统管理员配置静态地址 动态主机配置协议(Dynamic Host Configuration Protocol DHCP): 动态地从服务器得

28、到地址（“即插即用” ）uDHCP服务器发现： 55uDHCP服务器提供： a.b.c.d55uDHCP请求uDHCP ACK IP编址: 如何得到一个地址?第第4 4章章 网络层网络层58问题：网络怎样得到IP地址的子网部分?回答: 从它的ISP的地址空间得到分配的部分ISPs block 11001000 00010111 00010000 00000000 /20 Organization 0 11001000 00010111 00010000 00000000 /23 Org

29、anization 1 11001000 00010111 00010010 00000000 /23 Organization 2 11001000 00010111 00010100 00000000 /23 . . . .Organization 7 11001000 00010111 00011110 00000000 /23 IP编址:如何得到一个地址?第第4 4章章 网络层网络层59“向我发送地址始于/20的任何分组”/23/23

30、/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于/16的任何分组”/23组织 2.等级编址允许有效的通告选路信息: 等级编址: 路由聚合第第4 4章章 网络层网络层60ISPs-R-Us具有更为特定的路由到组织 1“向我发送地址始于/20的任何分组”/23/23/23Fly-By-Night-ISP组织 0组织 7因特网组织 1ISPs-R-Us“向我发送地址始于/16或200.23.18.

31、0/23的任何分组”/23组织 2. 等级编址: 更为特定的路由第第4 4章章 网络层网络层61某单位申请了一段某单位申请了一段IP地址：地址：/23。单。单位内由位内由4个部门个部门(A,B,C,D)组成，每个部门的主机组成，每个部门的主机数量分别是：数量分别是：200(A), 100(B), 50(C), 40(D)。试将。试将单位的总地址块单位的总地址块/23划分为划分为4个子网分个子网分配各配各4个部门。个部门。u1. 写出每个子网（地址块）写出每个子网（地址块）u2. 每个子网的网络前缀？子网掩码？每个子网的网络前缀？

32、子网掩码？u3. 每个子网的广播地址？主机可用地址范围？每个子网的广播地址？主机可用地址范围？ 练习(注：注：/23的二进制表示的二进制表示 11001000 00010111 00010000 00000000 ）第第4 4章章 网络层网络层62 网络地址转换NAT问题：IPv4的IP地址共有多少个？够用吗？解决办法：下一代的IPv6，增加IP地址位数（彻底解决）NAT技术（地址代理技术），提供内部私有地址与共有地址的转换，支持内网与公网的通信第第4 4章章 网络层网络层63本地网络(

33、如归属网络)10.0.0/24因特网其他部分具有该网源或目的的数据报都有10.0.0/24的地址(照常)所有数据报本地离开本地网络具有相同的单一源NAT IP地址: ,不同的源端口号 网络地址转换NAT第第4 4章章 网络层网络层64S: , 3345D: 86, 801: 主机 发送数据报到128.119.40, 80NAT 转换表WAN 侧地址 LAN 侧地址, 5001 , 3345 S

34、: 86, 80 D: , 33454S: , 5001D: 86, 8022: NAT路由器改变数据报源地址从, 3345 到, 5001,更新表S: 86, 80 D: , 500133: 回答到达的目的地址: , 50014: NAT 路由器改变数据报目的地址从, 5001到, 3345 外网IP地址与端口号转换内网IP地址与端口号 网络地址转换NAT第第4 4

35、章章 网络层网络层6516-bit 端口号字段: u用一个LAN侧地址支持60,000 并行连接!NAT 引起争议:u路由器的处理上升为第三层u违反了端到端原则u应用设计者必须要考虑 NAT可能性，如 P2P应用程序u地址短缺应当由IPv6来解决 网络地址转换NAT第第4 4章章 网络层网络层66 由主机和路由器用于网络级信息的通信u差错报告：不可达主机，网络，端口, 协议u回声请求/回答 (由 ping使用) 与IP的关系:类型 编码 描述0 0 回声回答 (ping)3 0 目的网络不可达3 1 目的主机不可达3 2 目的协议不可达3 3 目的端口不可达3 6 目的网络未知3 7 目的主机

36、未知4 0 源抑制(拥塞控制未使用）8 0 回声请求 (ping)9 0 路由通告10 0 路由器发现11 0 TTL过期12 0 坏的IP首部 互联网控制报文协议ICMPIP网络是尽力而为（不可靠）的，ICMP通过差错报文和询问报文来辅助IP网络的功能IP首部首部IP数据区数据区ICMP首部首部ICMP数据数据第第4 4章章 网络层网络层67 源向目的地发送一系列UDP段u第一个 TTL =1u第二个 TTL=2, 等u不可能的端口号 当第n个数据报 到达第n和路由器:u路由器丢弃数据报u并向源发送一个ICMP报文 (类型 11, 编码0)u报文包括路由器的名字和IP地址 当ICMP报文到达

37、，源计算 RTT Traceroute执行上述过程3次停止规则 UDP段最终到达目的地主机 目的地返回ICMP “端口不可达”分组 (类型3, 编码3) 当源得到该ICMP, 停止 Traceroute和ICMP第第4 4章章 网络层网络层68初始动机: 32bit地址空间耗尽IPv6的特点:u大地址空间，地址128bitu更简洁的报文头u更好的QoS支持u更好的安全性 3.410385.981024千克 5.691010个/克 下一代IP协议：IPv6第第4 4章章 网络层网络层69 IPv6首部基本首部 扩展首部 1 扩展首部 N 数 据 部 分选项IPv6 数据报有效载荷041631版

38、本位目 的 地 址源 地 址下 一 个 首 部流 标 号12业务类型（128 位）（128 位）有 效 载 荷 长 度跳 数 限 制24有效载荷（扩展首部 / 数据）IPv6 的基本首部（40 B）IPv6 的有效载荷（至 64 KB）第第4 4章章 网络层网络层70041631版 本位目 的 地 址源 地 址下 一 个 首 部流 标 号12业务类型（128 位）（128 位）有 效 载 荷 长 度跳 数 限 制24IPv6的基本首部40 B 业务类型，流标号：提供QoS区分与支持第第4 4章章 网络层网络层71并非所有的路由器能被同时更新u无“标志日 ”uIPv4和IPv6路由器混合将如何运

39、行? 隧道: 在IPv路由器之间IPv6数据报作为IPv4数据报的负载 从IPv4到IPv6的迁移第第4 4章章 网络层网络层72ABEFIPv6IPv6IPv6IPv6隧道逻辑视图:物理视图:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4流: X源: A目的: F数据流: X源: A目的: F数据流: X源: A目的: F数据源:B目的: E流: X源: A目的: F数据源:B目的: EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6 在IPv4中B-to-C:IPv6 在IPv4中 隧道第第4 4章章 网络层网络层734. 1 概述4.2 虚电路和数据报网络

40、4.3 路由器的构成4.4 IP: 网际协议4.5 选路算法选路算法4.6 互联网中选路4.7 广播和多播选路第第4 4章章 网络层网络层74选路算法的图论抽象: 图中的节点是路由器 图中的边是物理链路u链路代价: 时延，费用或拥塞等级目的：决定从源到目的地通过网络的“好的路径”(路由器序列)选路 协议AEDCBF2213112535r“好的”路径:m通常意味着最小费用的路径m其他定义也是可能的 选路第第4 4章章 网络层网络层75全局的或分散的信息?分散的: 路由器知道物理相连的邻居，到邻居的链路费用计算的迭代过程，与邻居交换信息“距离矢量” 算法全局的:所有路由器具有完全的拓扑、链路费用信

41、息“链路状态”算法s静态的或动态的?静态: 路由随时间缓慢变化动态: 路由更快地变化u 周期的更新u 适应链路费用变化 选路算法分类第第4 4章章 网络层网络层76Dijkstra算法 所有节点知道网络拓扑、链路费用u经“链路状态广播”完成u所有节点具有相同信息 从一个节点(源)到所有其他节点计算最低费用路径u给出对这些节点的转发表 迭代: k次迭代后，得知到k个目的地的最低费用路径概念: c(x,y): 从节点x到y的链路费用; = 如果不是直接邻居 D(v):从源到目的地v路径费用的当前值 p(v): 从源到v沿路径的前任节点 N: 已知在最小费用路径中的节点集合Dijkstra 迪杰斯特

42、拉 链路状态算法第第4 4章章 网络层网络层771 初始化初始化: 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)最小 10 将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中中 Dijsktra算法第第4 4章章 网络层网络层78步骤012345Nuuxux

43、yuxyvuxyvwuxyvwzD(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 Dijkstra算法: 例子第第4 4章章 网络层网络层79算法复杂性: n个节点 每次迭代: 需要检查所有节点w, 不在N中 n(n+1)/2 对比: O(n2) 更有效的实现是可能的: O(nlogn)可能振荡: 如链路费用 = 承载流量的量wzyx11+ee0e1100wzyx2+e0001+e 1wzyx02+e1+e10 0wzyx2+e0e01+e 1最初

44、重计算选路 重计算重计算e11e11e11 Dijkstra算法, 讨论第第4 4章章 网络层网络层80Bellman-Ford方程 (动态规划)定义dx(y) := 从x到y最低费用路径的费用则dx(y) = min c(x,v) + dv(y) 其中min对x的所有邻居 距离矢量算法第第4 4章章 网络层网络层81yxwvz2213112535Clearly, 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

45、= 4取最小的节点是在最短路中的下一跳 转发表B-F equation says: Bellman-Ford 例子第第4 4章章 网络层网络层82基本思想: 每个节点周期性的发送它自己的距离矢量估计到其邻居 当节点x接收到来自邻居的新DV估计，它使用B-F方程更新其自己的DV :Dx(y) minvc(x,v) + Dv(y) for each node y N在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用 dx(y) 距离矢量算法第第4 4章章 网络层网络层83迭代、异步: 每次本地迭代由下列引起: 本地链路费用改变 DV从邻居更新报文分布式: 每个节点仅当其DV改变时通知邻居

46、u 如果必要，邻居则通知它们的邻居等待 (来自邻居本地费用报文的变化)重新计算 估计值如果到任何目的地的DV已经变化, 通知 邻居 每个节点: 距离矢量算法第第4 4章章 网络层网络层84链路费用变化:好消息传播得快坏消息传播得慢“计数到无穷”问题!在算法稳定前，迭代44 次: 参见课文xz1450y60 距离矢量: 链路费用变化第第4 4章章 网络层网络层85报文复杂性 LS: 对n个节点，E条链路, 发送O(nE) 报文 DV: 仅在邻居之间交换u收敛时间变化收敛速度 LS: O(n2) 算法要求 O(nE)报文u可能具有振荡 DV: 收敛时间变化u可能有选路环路u计数到无穷问题健壮性:

47、如果路由器异常，将发生什么现象?LS: u节点可能通告不正确的链路费用u每个节点仅计算它自己的表DV:uDV节点通告不正确的路径费用u每个节点表能由其他人使用u差错通过网络传播 LS和DV算法的比较第第4 4章章 网络层网络层86规模: 具有2亿个目的地: 在选路表中不能存储所有的目的地! 选路表交换将堵塞链路! 管理自治 互联网 = 网络的网络 每个网络管理员可能要控制他自己网络中的选路我们的选路研究至此是理想的r所有路由器是等同的r网络“扁平” 实践中并不真实 等级选路第第4 4章章 网络层网络层87出于管理和扩展的目的，因特网可以被分割成许多不同的自治系统(autonomous syst

48、em，AS)，换句话说，因特网是由很多自治系统汇集而成的从选路的角度来说，自治系统是指使用统一内部路由协议的一组网络u自治系统内的选路协议(intra-AS)u自治系统间的选路协议(inter-AS)自治系统具有唯一的AS号（全球已分配几千个AS号，活跃的接近一千个） 自治系统第第4 4章章 网络层网络层883b1d3a1c2aAS3AS1AS21a2c2b1bAS内部选路 算法AS之间选路 算法转发表3c 转发表由AS内部和AS之间的选路算法所配置uAS内部设置内部目的地表项uAS之间和AS内部对外部目的地设置表项 互联的AS第第4 4章章 网络层网络层893b1d3a1c2aAS3AS1A

49、S21a2c2b1b3c 假定在AS1中的路由器接收目的地是AS1外部的数据报u路由器应当将分组朝着网关路由器转发，但哪个呢？AS1需要:1. 知道通过AS2可到达哪些目的地，通过AS3到达哪些2. 传播这些可达信息到AS1中所有路由器AS间选路的工作! AS间的任务第第4 4章章 网络层网络层904. 1 概述4.2 虚电路和数据报网络4.3 路由器的构成4.4 IP: 网际协议4.5 选路算法4.6 互联网中选路互联网中选路4.7 广播和多播选路第第4 4章章 网络层网络层91用于自治系统内部的路由协议称为“内部网关协议”，简称 IGP(Interior Gateway Protocol)

50、uRIPuOSPFuEIGRP用于自治系统间接口上的路由协议称为“外部网关协议”，简称EGP(Exterior Gateway Protocol)uBGP-4 选路协议第第4 4章章 网络层网络层92路由信息协议 RIP 是内部网关协议 IGP中最先得到广泛使用的协议。RIP 是一种分布式的基于距离向量的路由选择协议。 路由信息协议RIP第第4 4章章 网络层网络层93 从一路由器到直接连接的网络的距离定义为 1。 从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。 RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。 RIP认为一

51、个好的路由就是它通过的路由器的数目少，即“距离短”。 RIP允许一条路径最多只能包含 15 个路由器， “距离”的最大值为16 时即相当于不可达。 “距离”的定义 第第4 4章章 网络层网络层94仅和相邻路由器交换信息。 交换的信息是当前本路由器所知道的全部信息，即自己的路由表。 按固定的时间间隔交换路由信息，例如，每隔 30 秒。 RIP协议的三个要点 第第4 4章章 网络层网络层95 路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。 以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。 经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一

52、个网络的最短距离和下一跳路由器的地址。 路由表的建立 第第4 4章章 网络层网络层96收到相邻路由器（其地址为 X）的一个 RIP 报文：(1) 先修改此 RIP 报文中的所有项目：将“下一跳”字段中的地址都改为 X，并将所有的“距离”字段的值加 1。(2) 对修改后的 RIP 报文中的每一个项目，重复以下步骤：若项目中的目的网络不在路由表中，则将该项目加到路由表中。 否则 若下一跳字段给出的路由器地址是同样的，则将收到的项目替换原路由表中的项目。 否则 若收到项目中的距离小于路由表中的距离，则进行更新，否则，什么也不做。(3) 若 3 分钟还没有收到相邻路由器的更新路由表，则将此相邻路由器记

53、为不可达的路由器，即将距离置为16（距离为16表示不可达）。(4) 返回。 距离向量算法 第第4 4章章 网络层网络层971 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 一开始，各路由表只有到相邻路由器的信息网 3网 2网 4网 6网 5网 1“4”表示“从本路由器到网 4”“1”表示“距离是 1”“ ”表示“直接交付”第第4 4章章 网络层网络层981 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网

54、 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后A 说：“我到网 1 的距离是 1。”因此 B 现在也可以到网 1，距离是 2，经过 A。”第第4 4章章 网络层网络层991 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后A 说：“我到网 2 的距离是 1。”因此 B 现在也可以到网 2，距

55、离是 2，经过 A。”第第4 4章章 网络层网络层1001 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后A 说：“我到网 3 的距离是 1。”但 B 没有必要绕道经过路由器 A再到达网 3，因此这一项目不变。第第4 4章章 网络层网络层1011 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1

56、 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2 C更新后C 说：“我到网 4 的距离是 1。”但 B 没有必要绕道经过路由器 C再到达网 4，因此这一项目不变。第第4 4章章 网络层网络层1021 1 2 1 3 1 FEDCBA5 1 6 1 2 1 5 1 3 1 4 1 4 1 6 1 1 1 5 1 路由器 B 收到相邻路由器 A 和 C 的路由表网 3网 2网 4网 6网 5网 11 1 2 1 3 1 4 1 6 1 1 2 A2 2 A3 1 4 1 6 2

57、C更新后C 说：“我到网 6 的距离是 1。”因此 B 现在也可以到网 6，距离是 2，经过 C。”第第4 4章章 网络层网络层103最终所有的路由器的路由表都更新了FEDCBA1 1 2 1 3 1 4 2 B5 2 E6 3 B1 1 2 2 A3 2 A4 3 A5 1 6 2 F1 2 E2 2 D3 3 C4 2 C5 1 6 1 1 3 B2 3 B3 2 B4 1 5 2 F6 1 网 2网 6网 5网 1网 3网 41 2 A2 1 3 2 A4 3 A5 1 6 2 F1 2 A2 2 A3 1 4 1 5 3 C6 2 C第第4 4章章 网络层网络层104假设网络中的路由器

58、D中的转发表如左图 练习现在，路由器D收到来自B的RIP通告右图。试给出路由器D更新后的转发表。 第第4 4章章 网络层网络层105 4 字节RIP 报文路由信息（20 字节/路由）可重复出现最多 25 个IP 数据报路由标记网络地址地址族标识符距离 (1-16) IP 首部UDP 首部首部路由部分必为 0版本命令 4 字节子网掩码下一跳路由器地址UDP 用户数据报 RIP2协议的报文格式 RIP 协议使用运输层的协议使用运输层的用户数据报用户数据报 UDP进行传进行传送（使用送（使用 UDP 的端口的端口 520）第第4 4章章 网络层网络层106 RIP 协议最大的优点就是实现简单，开销较

59、小。 RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。 路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。 RIP 存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器。 RIP协议的优缺点 第第4 4章章 网络层网络层107R2R1网 1网 3网 2正常情况1 1 1 2 R1R1 说：“我到网 1 的距离是 1，是直接交付。”“1”表示“从本路由器到网 1”“1”表示“距离是 1”“ ”表示“直接交付”第第4 4章章 网络层网络层108R2R1网 1网 3网 2正常情况1 1 1 2 R1R2 说：

60、“我到网 1 的距离是 2，是经过 R1。”“1”表示“从本路由器到网 1”“2”表示“距离是 2”“R1”表示经过 R1第第4 4章章 网络层网络层109R2R1网 1网 3网 2R2R1网 1网 3网 2网 1出了故障正常情况1 1 1 16 1 2 R11 2 R1R1 说：“我到网 1 的距离是 16 （表示无法到达）， 是直接交付。”但 R2 在收到 R1 的更新报文之前，还发送原来的报文，因为这时 R2 并不知道 R1 出了故障。第第4 4章章 网络层网络层110R2R1网 1网 3网 2R2R1网 1网 3网 2网 1出了故障正常情况1 1 1 16 1 2 R11 2 R1R1 收到