计算机网络 第4章 网络层

目 录 网络层概述 虚电路和数据报网络 路由器的工作原理 网际协议:因特网中的转发和编址 选路算法 IP组播介绍 2017年3月11日 2

4.1 网络层概述 网络层的目标 网络层在计算机网络中的地位 实现主机到主机的通信 为运输层提供支持 运输层实现进程到进程的通信 运输层功能的实现依赖于网络层提供的服务 为实现从源主机到目标主机成功的移动数据分组，整个路径上的每一台分组交换机上均需实现网络层 网络层属于通信子网的功能 2017年3月11日 3

4.1 网络层概述 网络层的主要功能 在全局范畴为主机之间的通信进行选路，选路的结果反映为分组交换机上的转发表 分组交换机上的网络层根据转发表以及分组头部信息，将分组向适当链路进行转发 对于面向连接的网络层服务，提供连接建立的功能 ATM、X.25和帧中继 2017年3月11日 4

1 选路算法 首部值 输出链路 0100 3 0101 2 0111 1001 1 到达分组的首部值 2 3 2017年3月11日 5 本地转发表 首部值 输出链路 0100 0101 0111 1001 3 2 1 到达分组的首部值 1 0111 2 3 2017年3月11日 5

4.1 网络层概述 分组交换机的分类 根据链路层首部信息进行转发的——链路层节点交换机 根据网络层首部信息进行转发的——路由器 2017年3月11日 6

4.1 网络层概述 网络层可能提供的服务 确保交付 具有时延上界的确保交付 有序分组交付 确保最小带宽 确保最大时延抖动 …… 2017年3月11日 7

4.1 网络层概述 几种实际使用的网络层服务模型 网络体系结构 服务模型 带宽保证 无丢失保证 排序 定时 拥塞指示 网络体系结构 服务模型 带宽保证 无丢失保证 排序 定时 拥塞指示 因特网 尽力而为 无 无 无 不维持 无 ATM CBR 保证恒定速率 是 有序 维持 无拥塞 ATM ABR 保证最小速率 无 有序 维持 提供指示 2017年3月11日 8

4.2 虚电路和数据报网络 网络层提供的服务 网络层与运输层相应服务的区别 面向连接的服务——虚电路，需事先握手 面向无连接的服务——数据报，无需握手 网络层与运输层相应服务的区别 网络层是向运输层提供主机到主机的服务，而运输层是向应用层提供进程到进程的服务 网络层仅提供上述两种服务中的一种，不同时提供两种，而运输层则同时提供两种 运输层的服务在网络边缘的端系统中实现，而网络层的服务则在整个网络中实现，含路由器 2017年3月11日 9

4.2 虚电路和数据报网络 虚电路 目标 工作机制 使收发双方之间的路径表现得如同电话线路一般 数据开始流动之前，呼叫建立；流动结束后要断开 每一个分组携带虚电路的标识 (而不是目的主机的地址) 路径上的每一个路由器必须为进行中的连接维持连接状态信息 传输层的连接仅涉及到两个端系统（end system） 链路, 路由器资源 (带宽、缓冲区) 可以分配给虚电路 目的：为了达到类似线路交换的性能 2017年3月11日 10

4.2 虚电路和数据报网络 虚电路的组成 从源到目的主机的路径 VC 号, 沿着该路径的每段链路的一个号码 沿着该路径的每台路由器中的转发表 2017年3月11日 11

4.2 虚电路和数据报网络 路由器R1的转发表: 路由器维持连接状态信息! VC 号 12 22 32 R2 1 R1 2 3 接口号 R4 入接口 入 VC # 出接口 出 VC # 1 12 2 22 2 63 1 18 3 7 2 17 1 97 3 87 … … … … 路由器维持连接状态信息! 2017年3月11日 12

4.2 虚电路和数据报网络 信令协议 用于建立、维护以及断开虚电路 用于 ATM, 帧中继, X.25网络 今天的因特网已经不再使用该协议 应用层 传输层 网络层 数据链路层 物理层 5. 数据流开始 6. 接收数据 应用层 传输层 网络层 数据链路层 物理层 4. 呼叫连接 3. 接受呼叫 1. 启动呼叫 2. 入呼叫 2017年3月11日 13

4.2 虚电路和数据报网络 数据报网络 在网络层没有连接建立过程 路由器：在端到端的连接中不维护连接状态信息 传输报文时使用目的主机地址信息 在网络层不存在“联接”的概念 传输报文时使用目的主机地址信息 同一对主机间的报文可能会走不同的路径 应用层 传输层 网络层 数据链路层 物理层 应用层 传输层 网络层 数据链路层 物理层 1. 发送数据 2. 接收数据 2017年3月11日 14

4.2 虚电路和数据报网络 目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 目的地址范围 链路接口 11001000 00010111 00010000 00000000 到 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 到 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 到 2 11001000 00010111 00011111 11111111 其他 3 2017年3月11日 15

4.2 虚电路和数据报网络 虚电路 vs 数据报 虚电路网络：聪明的网络，愚笨的终端 数据报网络：简单的网络，复杂的终端 互联不同类型的网络更加容易 启用新服务的速度更快，更简单 2017年3月11日 16

4.3 路由器的工作原理 路由器的结构 路由选择处理机 3——网络层 2——数据链路层 1——物理层 路由 选择 分组 转发 交换结构 路由选择协议 路由表 3 输入端口 交换结构 输出端口 分组 转发 转发表 分组处理 … 1 2 3——网络层 2——数据链路层 1——物理层 2017年3月11日 17

4.3 路由器的工作原理 输入端口 分散式交换: 按照给出的目的地址,使用输入端口的内存中存储的路由选择表，查找输出端口 网络层处理 排队、 查表、转发 ■■■ 交换 结构 线路端接 数据链路处理 （协议、拆封） 物理层: 位流级的接收 数据链路层: e.g.,以太网 分散式交换: 按照给出的目的地址,使用输入端口的内存中存储的路由选择表，查找输出端口 目标:以“线路速度”完成输入端口的处理 排队：如果数据报到达的速度超过了输入端口将数据报转交给交换结构的速度，则后到的分组会暂时阻塞 2017年3月11日 18

4.3 路由器的工作原理 输入端口排队 如果输入端口的处理速率超过了交换结构的速率，输入端口就可能产生排队 线头阻塞:在输入队列中排队的分组必须等待通过交换结构发送，因为它被位于线头的另一个分组阻塞了。 输入缓冲区溢出可导致排队时延和丢包! 2017年3月11日 19

4.3 路由器的工作原理 交换结构 2017年3月11日 20

4.3 路由器的工作原理 经内存交换 在输入端口和输出端口之间的交换是在CPU（路由处理器）的直接控制下完成的 转发速度受限于内存的带宽 输入端口 输出端口 内存 系统总线 2017年3月11日 21

4.3 路由器的工作原理 经总线交换 输入端口经一根共享总线将分组直接传送到输出端口 总线交换的问题: 交换速度受限于总线的带宽 1 Gbps 总线, Cisco 1900:对于运行在接入网或企业网的路由器，通过总线交换的转发速度是足够的。 输出端口 输入端口 系统总线 2017年3月11日 22

4.3 路由器的工作原理 经内联网络 克服总线带宽限制，可以并行交换。 Cisco 12000: 通过内联网络交换速度为若干Gb/s 2017年3月11日 23

4.3 路由器的工作原理 输出端口 缓存管理：当交换结构将分组交付给输出端口的速率超过输出链路速率时 调度原则：在数据报队列中选择数据报进行传输 线路 端接 数据链路处理： （协议、封封） 排队（缓存管理） ■■■■■ 交换 结构 2017年3月11日 24

4.3 路由器的工作原理 输出端口排队 当通过交换结构到达的分组速率超过了输出链路的速率时，需要对分组进行缓存 输出端口缓冲区溢出会导致分组的排队和丢失! 2017年3月11日 25

4.4 网际协议:因特网中的转发和编址 主机、路由器的网络层组件 网络层 运输层: TCP, UDP 选路协议 IP 协议 路径选择 RIP, OSPF, BGP IP 协议 编址规则 数据报格式 分组处理规则 网络层 转发表 ICMP 协议 错误报告 路由器 信令 链路层 物理层 2017年3月11日 26

IP数据报的格式 固 定 部 分 可变 部分 4 8 16 19 24 版 本 标志 生 存 时 间 协 议 标 识 服 务 类 型 4 8 16 19 24 版 本 标志 生 存 时 间 协 议 标 识 服 务 类 型 总 长 度 片 偏 移 填 充 首 部 检 验 和 源 地 址 目 的 地 址 可 选 字 段 （长 度 可 变） 比特 首部长度 1 2 3 5 6 7 D T R C 未用 优 先 级 数 据 部 分 首 部 传送 IP 数据报 首 31 2017年3月11日 27

4.4 网际协议:因特网中的转发和编址 IP分片和重组 如何进行分片呢？ 网络链路具有 MTU (最大传输单位)属性——是由链路层最大帧的限制决定的 不同类型的链路有不同的MTU值 大的IP数据报在网络中会被分成小的分片 如何识别那些分片是同一个原始分组分出来的？ 如何确保分片的顺序？ 如何判断是否收到所有的分片？ 如何进行分片呢？ 2017年3月11日 28

4.4 网际协议:因特网中的转发和编址 IP 头 数据区（3980字节, 共4000 字节） ID = 100 片头 数据 1（1480） 数据 2（1480） 片头 数据3 (1020) ID = 100 MF = 1 FO = 0 Len = 1500 ID = 100 MF = 1 FO = 185（1480/8） Len = 1500 ID = 100 MF = 0 FO = 370 Len = 1040 注意：以太网MTU为1500字节。 2017年3月11日 29

4.4 网际协议:因特网中的转发和编址 IP 地址 32位主机或路由器的接口标志符 接口:连接主机,路由器之间的物理链路 一般说来，路由器有多个接口 主机也有可能有多个接口 IP 地址只和接口有关, 而与主机,路由器却没有太多关联 2017年3月11日 30

4.4 网际协议:因特网中的转发和编址 IP地址的表示方法 IP地址的结构 223.1.1.1 32位 11011111 00000001 00000001 00000001 223.1.1.1 223 1 1 1 网络号 Net-id 主机号host-id 32位 2017年3月11日 31

4.4 网际协议:因特网中的转发和编址 IP地址的分类 31 23 15 7 0 0 网 络 号 主 机 号 A 类 31 23 15 7 0 0 网 络 号 主 机 号 A 类 1 0 网 络 号 主 机 号 B 类 1 1 0 网 络 号 主 机 号 C 类 D 类 1 1 1 0 组 播 地 址 1 1 1 1 0 保 留 为 今 后 使 用 E 类 2017年3月11日 32

2.常用的三种类别的 IP 地址 IP 地址的使用范围 网络 最大 第一个 最后一个 每个网络 类别 网络数 可用的 可用的 中最大的 网络 最大 第一个 最后一个 每个网络 类别 网络数 可用的 可用的 中最大的 网络号 网络号 主机数 A 126 (27 – 2) 1 126 16,777,214 B 16,383(214  1) 128.1 191.255 65,534 C 2,097,151 (221  1) 192.0.1 223.255.255 254 说明： (1)IP地址中的网络号为全0的地址是保留地址，表示本网络。 网络号为127（01111111）的地址保留为本地回环测试本主机的进程之间的通信 (2)B类网络地址128.0.0.0不指派 (3)C类网络地址192.0.0.0也是不指派的。 (4)全0的主机号字段表示该IP地址是“本主机”所连接到的网络的网络地址； 全1表示“所有的”，即本网络上的所有主机（广播地址）。 33

IP 地址的一些重要特点 (1) IP 地址是一种分等级的地址结构。分两个等级的好处是： 第一，IP 地址管理机构在分配 IP 地址时只分配网络号，而剩下的主机号则由得到该网络号的单位自行分配。这样就方便了 IP 地址的管理。 第二，路由器仅根据目的主机所连接的网络号来转发分组（而不考虑目的主机号），这样就可以使路由表中的项目数大幅度减少，从而减小了路由表所占的存储空间。 34

IP 地址的一些重要特点 (2) 实际上 IP 地址是标志一个主机（或路由器）和一条链路的接口。 当一个主机同时连接到两个网络上时，该主机就必须同时具有两个相应的 IP 地址，其网络号 net-id 必须是不同的。这种主机称为多归属主机(multihomed host)。 由于一个路由器至少应当连接到两个网络（这样它才能将 IP 数据报从一个网络转发到另一个网络），因此一个路由器至少应当有两个不同的 IP 地址。 35

IP 地址的一些重要特点 (3) 用转发器或网桥连接起来的若干个局域网仍为一个网络，因此这些局域网都具有同样的网络号 net-id。 36

图中的网络号就是 IP 地址中的 net-id 在同一个局域网上的主机或路由器的 IP 地址中的网络号必须是一样的。 图中的网络号就是 IP 地址中的 net-id 222.1.1.1 222.1.1.2 222.1.1.3 LAN1 222.1.1. 222.1.1.4 R1 LAN3 222.1.5.1 222.1.6.1 222.1.3.3 222.1.3. 222.1.2.1 N3 222.1.6. LAN2 222.1.2. N2 222.1.5. 222.1.5.2 222.1.6.2 222.1.3.1 R3 N1 222.1.4. R2 222.1.2.5 222.1.2.2 222.1.3.2 222.1.4.2 222.1.4.1 B 222.1.2.4 222.1.2.3 互联网 2017年3月11日 37

图中的网络号就是 IP 地址中的 net-id 在同一个局域网上的主机或路由器的 IP 地址中的网络号必须是一样的。 图中的网络号就是 IP 地址中的 net-id 222.1.1.1 222.1.1.2 222.1.1.3 LAN1 222.1.1. 222.1.1.4 R1 LAN3 222.1.5.1 222.1.6.1 222.1.3.3 222.1.3. 222.1.2.1 N3 222.1.6. LAN2 222.1.2. N2 222.1.5. 222.1.5.2 222.1.6.2 222.1.3.1 R3 N1 222.1.4. R2 222.1.2.5 222.1.2.2 222.1.3.2 222.1.4.2 222.1.4.1 B 222.1.2.4 222.1.2.3 互联网 2017年3月11日 38

图中的网络号就是 IP 地址中的 net-id 222.1.1.1 222.1.1.2 222.1.1.3 LAN1 222.1.1. 222.1.1.4 R1 LAN3 222.1.5.1 在同一个局域网上的主机或路由器的 IP 地址中的网络号必须是一样的。 图中的网络号就是 IP 地址中的 net-id 222.1.6.1 222.1.3.3 222.1.3. 222.1.2.1 N3 222.1.6. LAN2 222.1.2. N2 222.1.5. 222.1.5.2 222.1.6.2 222.1.3.1 R3 N1 222.1.4. R2 222.1.2.5 222.1.2.2 222.1.3.2 222.1.4.2 222.1.4.1 B 222.1.2.4 222.1.2.3 互联网 2017年3月11日 39

路由器总是具有两个或两个以上的 IP 地址。 路由器的每一个接口都有一个 不同网络号的 IP 地址。 222.1.1.1 222.1.1.2 222.1.1.3 LAN1 222.1.1. 222.1.1.4 R1 LAN3 222.1.5.1 222.1.6.1 222.1.3.3 222.1.3. 222.1.2.1 N3 222.1.6. LAN2 222.1.2. N2 222.1.5. 222.1.5.2 222.1.6.2 222.1.3.1 R3 N1 222.1.4. R2 222.1.2.5 222.1.2.2 222.1.3.2 222.1.4.2 222.1.4.1 B 222.1.2.4 222.1.2.3 互联网 2017年3月11日 40

路由器总是具有两个或两个以上的 IP 地址。 路由器的每一个接口都有一个 不同网络号的 IP 地址。 222.1.1.1 222.1.1.2 222.1.1.3 LAN1 222.1.1. 222.1.1.4 R1 LAN3 222.1.5.1 222.1.6.1 222.1.3.3 222.1.3. 222.1.2.1 N3 222.1.6. LAN2 222.1.2. N2 222.1.5. 222.1.5.2 222.1.6.2 222.1.3.1 R3 N1 222.1.4. R2 222.1.2.5 222.1.2.2 222.1.3.2 222.1.4.2 222.1.4.1 B 222.1.2.4 222.1.2.3 互联网 2017年3月11日 41

路由器总是具有两个或两个以上的 IP 地址。 路由器的每一个接口都有一个 不同网络号的 IP 地址。 222.1.1.1 222.1.1.2 222.1.1.3 LAN1 222.1.1. 222.1.1.4 R1 LAN3 222.1.5.1 222.1.6.1 222.1.3.3 222.1.3. 222.1.2.1 N3 222.1.6. LAN2 222.1.2. N2 222.1.5. 222.1.5.2 222.1.6.2 222.1.3.1 R3 N1 222.1.4. R2 222.1.2.5 222.1.2.2 222.1.3.2 222.1.4.2 222.1.4.1 B 222.1.2.4 222.1.2.3 互联网 2017年3月11日 42

IP 层转发分组的流程 有四个 A 类网络通过三个路由器连接在一起。每一个网络上都可能有成千上万个主机。 可以想像，若按目的主机号来制作路由表，则所得出的路由表就会过于庞大。 但若按主机所在的网络地址来制作路由表，那么每一个路由器中的路由表就只包含 4 个项目。这样就可使路由表大大简化。 43

在路由表中，对每一条路由，最主要的是 （目的网络地址，下一跳地址） 路由器 R2 的路由表 10.0.0.4 20.0.0.7 20.0.0.9 30.0.0.2 30.0.0.1 40.0.0.4 R1 R2 R3 网 1 10.0.0.0 网 2 20.0.0.0 网 3 30.0.0.0 网 4 40.0.0.0 1 路由器 R2 的路由表 目的主机所在的网络 下一跳地址 20.0.0.0 直接交付，接口 0 30.0.0.0 直接交付，接口 1 10.0.0.0 20.0.0.7 40.0.0.0 30.0.0.1 10.0.0.4 20.0.0.7 20.0.0.9 30.0.0.2 30.0.0.1 40.0.0.4 R1 R2 R3 链路 1 链路 2 链路 3 链路 4 44

查找路由表 根据目的网络地址就能确定下一跳路由器，这样做的结果是： IP 数据报最终一定可以找到目的主机所在目的网络上的路由器（可能要通过多次的间接交付）。 只有到达最后一个路由器时，才试图向目的主机进行直接交付。 45

分组转发算法 (1) 从数据报的首部提取目的主机的 IP 地址 D, 得出目的网络地址为 N。 (2) 若目的网络 N 与此路由器直接相连，则把数据报直接交付目的主机 D；否则是间接交付，执行(3)。 (3) 若路由表中有到达网络 N 的路由，则把数据报传送给路由表指明的下一跳路由器；否则，执行(4)。 (4) 若路由表中有一个默认路由，则把数据报传送给路由表中所指明的默认路由器；否则，执行(5)。 (5) 报告转发分组出错。 46

4.4 网际协议:因特网中的转发和编址 子网的划分 如何划分这些地址子块呢？ 问题： 一家跨国公司在海外拥有26家分支机构，包括总部在内，共计27家 机构，该公司所有机构共有54320台计算机需要IP地址，总部向ICANN申请了一个B类地址块，先需要分配给所有的机构，如何分配？ ★ 由总部管理员统一分配，集中管理 （你愿意当这个管理员么？） ★ 总部管理员将IP地址分成27个子块，每个机构一块，各机构管理 员内部自行分配 如何划分这些地址子块呢？ 2017年3月11日 47

4.4 网际协议:因特网中的转发和编址 子网划分的方法 从主机号中借用一部分位数作为子网号 X位 子 网 号 1 0 网 络 号 主 机 号 1 0 网 络 号 主 机 号 B 类 2017年3月11日 48

4.4 网际协议:因特网中的转发和编址 从 1985 年起在 IP 地址中又增加了一个“子网号字段”，使两级的 IP 地址变成为三级的 IP 地址。 从两级 IP 地址到三级 IP 地址 IP 地址空间的利用率有时很低。 两级的 IP 地址不够灵活。 网络如何知道地址的那些部分表示网络号呢？

4.4 网际协议:因特网中的转发和编址 子网掩码 作用：指示网络号和主机号的分界线 设置方法：通过在网络号相应的位置全置1，主机号相应的位置全置0，即可得到子网掩码 172.16.3.0 172.16.4.0 172.16.1.0 172.16.2.0 ★ 对外，网络号是 172.16.0.0 ★ 对内，存在四个子网，子网掩码为255.255.255.0 2017年3月11日 50

IP 地址的各字段和子网掩码 因特网部分 本地部分 两级 IP 地址 网络号 net-id 主机号 host-id 因特网部分 本地部分 subnet-id 子网号 host-id 网络号 主机号 子网掩码 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 划分子网时 的网络地址 net-id subnet-id host-id 为全 0 2017年3月11日 51

(IP 地址) AND (子网掩码) =网络地址 因特网部分 本地部分 两级 IP 地址 网络号 net-id 主机号 host-id 因特网部分 本地部分 三级 IP 地址 net-id host-id subnet-id AND 网络号 子网号 主机号 子网掩码 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 划分子网时 的网络地址 net-id subnet-id host-id 为全 0 2017年3月11日 52

默认子网掩码 A 类 地 址 网络地址 net-id host-id 为全 0 默认子网掩码 255.0.0.0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B 类 地 址 网络地址 net-id host-id 为全 0 默认子网掩码 255.255.0.0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 C 类 地 址 网络地址 net-id host-id 为全 0 默认子网掩码 255.255.255.0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 53

【例4-2】已知 IP 地址是 141.14.72.24，子网掩码是 255.255.192.0。试求网络地址。 (a) 点分十进制表示的 IP 地址 141 . 14 . 72 . 24 (b) IP 地址的第 3 字节是二进制 141 . 14 . 0 1 0 0 1 0 0 0 . 24 (c) 子网掩码是 255.255.192.0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (d) IP 地址与子网掩码逐位相与 141 . 14 . 0 1 0 0 0 0 0 0 . 0 (e) 网络地址（点分十进制表示） 141 . 14 . 64 . 0 54

子网掩码是一个重要属性 子网掩码是一个网络或一个子网的重要属性。 路由器在和相邻路由器交换路由信息时，必须把自己所在网络（或子网）的子网掩码告诉相邻路由器。 路由器的路由表中的每一个项目，除了要给出目的网络地址外，还必须同时给出该网络的子网掩码。 若一个路由器连接在两个子网上就拥有两个网络地址和两个子网掩码。 55

4.4 网际协议:因特网中的转发和编址 一个子网规划的问题 条件： 目标 结果 一个C类地址：201.222.5.0 每个子网（ SubNet）20台主机 5个子网 结果 3位子网号、5位主机号 …… 2017年3月11日 56

网络 145.13.0.0 … … … 一个未划分子网的 B 类网络145.13.0.0 我的网络地址 是 145.13.0.0 145.13.3.101 145.13.3.11 … 145.13.7.34 R2 145.13.3.10 145.13.7.35 网络 145.13.0.0 R1 … R3 145.13.7.56 … 所有到网络 145.13.0.0的分组均到达此路由器 145.13.21.23 145.13.21.8 145.13.21.9 57

划分为三个子网后对外仍是一个网络 网络 145.13.0.0 所有到达网络 145.13.0.0 的分组均到达 此路由器 145.13.3.101 145.13.3.11 145.13.7.34 145.13.3.10 … 145.13.7.35 R2 子网 145.13.3.0 子网 145.13.7.0 … 145.13.7.56 R1 R3 子网 145.13.21.0 … 145.13.21.23 网络 145.13.0.0 145.13.21.9 145.13.21.8 58

4.4 网际协议:因特网中的转发和编址 引入子网掩码后的寻址 划分子网纯属一个单位内部的事情。单位对外仍然表现为没有划分子网的网络。 采用子网掩码后，路由器的寻址过程将演变成一个两级寻址过程： ★ 检查分组目的IP地址中的网络号：若网络号不是本网络，则从路由表中找出相应的转发结点地址将其转发出去。 ★ 检查子网号：当网络号是本网络时，路由器将检查子网号，向相应的子网转发此分组。 2017年3月11日 59

划分子网后分组的转发举例 R1 的路由表（未给出默认路由器） 目的网络地址 子网掩码 下一跳 128.30.33.0 128.30.33.13 目的网络地址 子网掩码 下一跳 128.30.33.0 128.30.33.128 128.30.36.0 255.255.255.128 255.255.255.0 接口 0 接口 1 R2 子网1： 网络地址 128.30.33.0 子网掩码 255.255.255.128 H1 128.30.33.1 R1 子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128 128.30.33.130 1 128.30.33.129 H2 128.30.33.138 R2 1 128.30.36.2 子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0 H3 128.30.36.12 2017年3月11日 60

请注意：H1 并不知道 H2 连接在哪一个网络上。 要发送的分组的目的 IP 地址：128.30.33.138 R1 的路由表（未给出默认路由器） 128.30.33.13 子网1： 网络地址 128.30.33.0 子网掩码 255.255.255.128 目的网络地址 子网掩码 下一跳 128.30.33.0 128.30.33.128 128.30.36.0 255.255.255.128 255.255.255.0 接口 0 接口 1 R2 H1 128.30.33.1 R1 子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128 128.30.33.130 1 128.30.33.129 128.30.33.138 R2 H2 因此 H1 首先检查主机 128.30.33.138 是否连接在本网络上。如果 是，则直接交付；否则，就送交路由器 R1，并逐项查找路由表。 请注意：H1 并不知道 H2 连接在哪一个网络上。 H1 仅仅知道 H2 的 IP 地址是 128.30.33.138 1 128.30.36.2 子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0 H3 128.30.36.12 2017年3月11日 61

主机 H1 首先将本子网的子网掩码 255. 255. 255. 128 与分组的 IP 地址 128. 30. 33 主机 H1 首先将本子网的子网掩码 255.255.255.128 与分组的 IP 地址 128.30.33.138 逐比特相“与”(AND 操作) R1 的路由表（未给出默认路由器） 255.255.255.128 AND 128.30.33.138 的计算 128.30.33.13 H1 目的网络地址 子网掩码 下一跳 128.30.33.0 128.30.33.128 128.30.36.0 255.255.255.128 255.255.255.0 接口 0 接口 1 R2 子网1： 网络地址 128.30.33.0 子网掩码 255.255.255.128 255 就是二进制的全 1，因此 255 AND xyz = xyz， 这里只需计算最后的 128 AND 138 即可。 128.30.33.1 R1 子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128 128 →10000000 138 →10001010 128.30.33.130 1 128.30.33.129 H2 逐比特 AND 操作后 10000000 → 128 128.30.33.138 R2 1 128.30.36.2 255.255.255.128 128. 30. 33.138 128. 30. 33.128 逐比特 AND 操作 子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0  H1 的网络地址 H3 128.30.36.12 2017年3月11日 62

因此 H1 必须把分组传送到路由器 R1，然后逐项查找路由表 128.30.33.13 目的网络地址 子网掩码 下一跳 128.30.33.0 128.30.33.128 128.30.36.0 255.255.255.128 255.255.255.0 接口 0 接口 1 R2 子网1： 网络地址 128.30.33.0 子网掩码 255.255.255.128 H1 128.30.33.1 R1 子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128 128.30.33.130 1 128.30.33.129 H2 128.30.33.138 R2 1 128.30.36.2 子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0 H3 128.30.36.12 2017年3月11日 63

路由器 R1 收到分组后就用路由表中第 1 个项目的子网掩码和 128.30.33.138 逐比特 AND 操作 R1 收到的分组的目的 IP 地址：128.30.33.138 R1 的路由表（未给出默认路由器） 128.30.33.13 子网1： 网络地址 128.30.33.0 子网掩码 255.255.255.128 目的网络地址 子网掩码 下一跳 128.30.33.0 128.30.33.128 128.30.36.0 255.255.255.128 255.255.255.0 接口 0 接口 1 R2 H1 128.30.33.1 R1 子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128 不一致 128.30.33.130 1 128.30.33.129 128.30.33.138 R2 H2 255.255.255.128 AND 128.30.33.138 = 128.30.33.128 不匹配! （因为128.30.33.128 与路由表中的 128.30.33.0 不一致） 1 128.30.36.2 子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0 H3 128.30.36.12 2017年3月11日 64

路由器 R1 再用路由表中第 2 个项目的子网掩码和 128.30.33.138 逐比特 AND 操作 R1 收到的分组的目的 IP 地址：128.30.33.138 R1 的路由表（未给出默认路由器） 128.30.33.13 子网1： 网络地址 128.30.33.0 子网掩码 255.255.255.128 目的网络地址 子网掩码 下一跳 128.30.33.0 128.30.33.128 128.30.36.0 255.255.255.128 255.255.255.0 接口 0 接口 1 R2 H1 一致! 128.30.33.1 R1 子网2：网络地址 128.30.33.128 子网掩码 255.255.255.128 128.30.33.130 1 128.30.33.129 128.30.33.138 R2 H2 255.255.255.128 AND 128.30.33.138 = 128.30.33.128 匹配! 这表明子网 2 就是收到的分组所要寻找的目的网络 1 128.30.36.2 子网3：网络地址 128.30.36.0 子网掩码 255.255.255.0 H3 128.30.36.12 2017年3月11日 65

4.4 网际协议:因特网中的转发和编址 构造超网 IP地址的扩展——构造超网 问题： 怎么办？ 从网络号中借用一部分位数作为主机号 ★ 如果申请B类地址块，则费用过高，而且大量的地址被浪费 ★ 如果申请C类地址块，则需要四个不同的C类地址块，需要构 造四个不同的网段 怎么办？ 构造超网 从网络号中借用一部分位数作为主机号 2017年3月11日 66

4.4 网际协议:因特网中的转发和编址 子网划分示例 某公司现获得了一批IP地址，是： 218.103.24.112~218.103.24.127 请问： (1) 该批IP地址的网络号是多少？ (2) 该批IP地址的子网掩码是多少？ (3) 如果针对该批IP地址进行进一步的子网划分，还可以划 分为多少个子网？请用“网络号/掩码位数”来表示这 些子网。 2017年3月11日 67

4.4 网际协议:因特网中的转发和编址 CIDR(Classless InterDomain Routing) 背景 CIDR编址格式 地址空间的利用率低, 地址空间面临耗尽 e.g., 一个B类网址可以容纳65K台主机, 但可能被一个只有2K 台主机的单位占据 CIDR编址格式 IP地址 ::= {<网络前缀>, <主机号>} 斜线记法：192.168.0.1/24 简写记法：10.0.0.0/10 10/10 2017年3月11日 68

ISP 大学 X 因特网 三系 四系 二系 一系 206.0.64.0/18 206.0.68.0/22 206.0.68.0/23 206.0.70.0/24 206.0.71.0/25 206.0.71.128/25 206.0.68.0/25 206.0.68.128/25 206.0.69.0/25 206.0.69.128/25 206.0.70.0/26 206.0.70.64/26 206.0.70.128/26 206.0.70.192/26 206.0.71.0/26 206.0.71.64/26 206.0.71.128/26 206.0.71.192/26 三系 四系 二系 一系 单位 地址块 二进制表示 地址数 ISP 206.0.64.0/18 11001110.00000000.01* 16384 大学 206.0.68.0/22 11001110.00000000.010001* 1024 一系 206.0.68.0/23 11001110.00000000.0100010* 512 二系 206.0.70.0/24 11001110.00000000.01000110.* 256 三系 206.0.71.0/25 11001110.00000000.01000111.0* 128 四系 206.0.71.128/25 11001110.00000000.01000111.1* 128 2017年3月11日 69

ISP 大学 X 206.0.64.0/18 因特网 206.0.68.0/22 206.0.68.0/23 206.0.70.0/24 206.0.71.0/25 206.0.71.128/25 206.0.68.0/25 206.0.68.128/25 206.0.69.0/25 206.0.69.128/25 206.0.70.0/26 206.0.70.64/26 206.0.70.128/26 206.0.70.192/26 206.0.71.0/26 206.0.71.64/26 206.0.71.128/26 206.0.71.192/26 三系 四系 二系 一系 这个 ISP 共有 64 个 C 类网络。如果不采用 CIDR 技术，则在与该 ISP 的路由器交换路由信息的每一个路由器的路由表中，就需要有 64 个项目。但采用地址聚合后，只需用路由聚合后的 1 个项目 206.0.64.0/18 就能找到该 ISP。 2017年3月11日 70

4.4 网际协议:因特网中的转发和编址 最长前缀匹配 使用 CIDR 时，路由表中的每个项目由“网络前缀”和“下一跳地址”组成。在查找路由表时可能会得到不止一个匹配结果。 应当从匹配结果中选择具有最长网络前缀的路由：最长前缀匹配(longest-prefix matching)。 网络前缀越长，其地址块就越小，因而路由就越具体。 最长前缀匹配又称为最长匹配或最佳匹配。 2017年3月11日 71

收到分组的目的地址 D = 206.0.71.142 路由表中项目：206.0.68.0/22 （ISP） 206.0.71.128/25 （四系） 查找路由表中的第 1 个项目 第 1 个项目 206.0.68.0/22 的掩码 M 有 22 个连续的 1。 M = 11111111 11111111 11111100 00000000 因此只需把 D 的第 3 个字节转换成二进制。 M = 11111111 11111111 11111100 00000000 AND D = 206. 0. 01000111.10001110 206. 0. 01000100. 0 与 206.0.68.0/22 匹配！ 2017年3月11日 72

收到分组的目的地址 D = 206.0.71.142 路由表中项目：206.0.68.0/22 （ISP） 206.0.71.128/25 （四系） 再查找路由表中的第 2 个项目 第 2 个项目 206.0.71.128/25 的掩码 M 有 25 个连续的 1。 M = 11111111 11111111 11111111 10000000 因此只需把 D 的第 4 个字节转换成二进制。 M = 11111111 11111111 11111111 10000000 AND D = 206. 0. 71. 10001110 206. 0. 71. 10000000 与 206.0.71.128/25 匹配 2017年3月11日 73

4.4 网际协议:因特网中的转发和编址 D AND (11111111 11111111 11111100 00000000) = 206.0.68.0/22 匹配 D AND (11111111 11111111 11111111 10000000) = 206.0.71.128/25 匹配 选择两个匹配的地址中更具体的一个，即选择最长前缀的地址。 2017年3月11日 74

4.4 网际协议:因特网中的转发和编址 右表为一个使用CIDR的路由表，请说明下列地址的下一跳各是什么？ (a) C4.5E.13.87 (b) C4.5E.22.09 (c) C3.41.80.02 (d) 5E.43.91.12 (e) C4.6D.31.2E (f) C4.6B.31.2E 网络/掩码长度 下一跳点 C4.50.0.0/12 A C4.5E.10.0/20 B C4.60.0.0/12 C C4.68.0.0/14 D 80.0.0.0/1 E 40.0.0.0/2 F 0.0.0.0/2 G B A E F C D 2017年3月11日 75

4.4 网际协议:因特网中的转发和编址 获取网络地址 Q: 一个网络如何获得一块地址？ A:从ISP的地址空间中获得。 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... ….. …. …. Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 2017年3月11日 76

4.4 网际协议:因特网中的转发和编址 Q: ISP 如何获得整块地址? A: ICANN: Internet Corporation for Assigned Names and Numbers（因特网名字与号码分配团体） 分配IP地址 管理 DNS 分配域名, 解决域名纠纷 2017年3月11日 77

4.4 网际协议:因特网中的转发和编址 Q: 主机如何获得IP地址? (主机部分) 手工配置：系统管理员手工为一台主机配置IP地址 Windows: 控制面板->网络->配置->tcp/ip->属性 UNIX: /etc/rc.config DHCP: Dynamic Host Configuration Protocol （动态主机配置协议:从服务器上动态获取IP地址 “即插即用协议” 2017年3月11日 78

4.4 网际协议:因特网中的转发和编址 NAT(Network Address Translation) 因特网的 本地网络 其他部分 (例如., 家庭网络) 10.0.0/24 10.0.0.1 10.0.0.4 10.0.0.2 138.76.29.7 本网络中的数据报有着类似 10.0.0/24的源或目的IP地址 所有离开本地网络的报文都拥有同一个源IP地址: 138.76.29.7,以及不同的源端口号 10.0.0.3 2017年3月11日 79

4.4 网际协议:因特网中的转发和编址 动机: 本地网络只要使用一个IP地址就可以和外部网络相连 : 不需要从 ISP处获得大批IP地址: 所有设备可以使用同一个 IP地址 可以在不通知外部网络的情况下改变内网主机的IP地址 即使改变了ISP也无须改变内网主机的IP地址 内网主机对外网主机而言是不可见的、不可寻址的。 (这也算是一项安全措施). 2017年3月11日 80

4.4 网际协议:因特网中的转发和编址 实现 发送数据报: 将每个外出报文的源IP地址,端口号替换 为NAT IP地址以及新的端口号 接收数据报:根据NAT转换表将每个进入报文的NAT IP地址,端口号替换为相应的源IP地址以及端口号 2017年3月11日 81

4.4 网际协议:因特网中的转发和编址 NAT 转换表 WAN 端 LAN 端 1: 主机 10.0.0.1 发送数据报到主机 128.119.40, 80 2: NAT路由器将 数据报的源地址 10.0.0.1, 3345 转换成138.76.29.7, 5001,同时更新 NAT转换表 138.76.29.7, 5001 10.0.0.1, 3345 …… …… S: 10.0.0.1, 3345 D: 128.119.40.186, 80 10.0.0.1 1 S: 138.76.29.7, 5001 D: 128.119.40.186, 80 2 10.0.0.4 10.0.0.2 138.76.29.7 S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4 S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3 10.0.0.3 4: NAT路由器将 数据报的目的地址138.76.29.7, 5001 转换成 10.0.0.1, 3345 3: 响应报文到达 目的地址: 138.76.29.7, 5001 2017年3月11日 82

4.4 网际协议:因特网中的转发和编址 两类地址 三种地址转换方式 本地地址 全球地址 静态NAT：一个本地地址对应一个全球地址 10/8 172.16/12 192.168/16 全球地址 三种地址转换方式 静态NAT：一个本地地址对应一个全球地址 动态NAT：一个全球地址对应多个本地地址 端口NAT：一个本地地址的端口对应到一个全球地址的端口 2017年3月11日 83

4.4 网际协议:因特网中的转发和编址 ICMP：因特网控制报文协议 用于主机、路由器、网关之间交换网络层信息 错误报告: 如主机、网络、端口、协议不可达等。 回声请求/回答 (用于ping应用程序) 从体系结构而言，位于IP层之上 : ICMP 报文封装在IP分组中 ICMP 消息: 包括一个类型字段和一个编码字段 ICMP 报文的种类有两种，即 ICMP 差错报告报文和 ICMP 询问报文 2017年3月11日 84

ICMP 报文的格式 8 16 31 前 4 个字节 都是一样的 类型 代码 检验和 （这 4 个字节取决于 ICMP 报文的类型） 8 16 31 前 4 个字节 都是一样的 类型 代码 检验和 （这 4 个字节取决于 ICMP 报文的类型） ICMP 的数据部分（长度取决于类型） ICMP 报文 首 部 数 据 部 分 IP 数据报 2017年3月11日 85

4.4 网际协议:因特网中的转发和编址 类型 代码 描述 0 0 回声回答（对Ping的回答） 3 1 目的主机不可达 类型 代码 描述 0 0 回声回答（对Ping的回答） 3 1 目的主机不可达 3 2 目的协议不可达 3 3 目的端口不可达 3 6 目的网络未知 3 7 目的主机未知 4 0 源抑制 (拥塞控制，未用) 8 0 回声请求 (ping) 9 0 路由器通告 10 0 路由器发现 11 0 TTL 过期 12 0 IP 首部错误 2017年3月11日 86

4.4 网际协议:因特网中的转发和编址 IPv4面临的问题 地址空间消耗很快 虽然NAT减少了IP地址的需求量，或者扩大了IP地址的数量 首部长度不定（20-40字节），中间结点（路由器）需要消耗相当资源用于分组处理 缺少QoS 安全性不够高 …… 2017年3月11日 87

4.4 网际协议:因特网中的转发和编址 IPv6数据报格式 无检查和，中间结点无需计算 中间结点不再负责分片和重组，由端结点负责 首部长度固定，加速中间结点转发速度 版本 流量类型 流标签 有效载荷长度 下一个首部 跳限制 源地址（128比特） 目的地址（128比特） 数据 2017年3月11日 88

4.4 网际协议:因特网中的转发和编址 IPv4到IPv6的迁移 设立标志日，统一迁移 双栈技术 隧道技术 可能会出现信息的丢失 隧道技术 2017年3月11日 89

4.4 网际协议:因特网中的转发和编址 双协议栈 IPv6/IPv4 双协议栈 IPv6/IPv4 IPv6 IPv4 网络 IPv6 A B C D E F 双协议栈 IPv6/IPv4 双协议栈 IPv6/IPv4 IPv4 网络 IPv6 IPv6 隧道 A B E F IPv4 网络 流标号：X 源地址：A 目的地址：F …… 数据 源地址：B 目的地址：E 源地址：B 目的地址：E 流标号：X 源地址：A 目的地址：F …… 数据 … IPv6 数据报 IPv6 数据报 IPv6 数据报 IPv6 数据报 2017年3月11日 90 IPv4 数据报 IPv4 数据报

4.5 选路算法 几个概念 选路算法的目的 默认路由器：一台主机“直接”连接到的路由器 源路由器：源主机的默认路由器 目的路由器：目标主机的默认路由器 选路算法的目的 给定一组路由器以及连接路由器的链路，从中找到一条从源路由器到目标路由器“好的”路径 “好的”通常指具有最低费用的路径 2017年3月11日 91

4.5 选路算法 G = (N,E) N = 路由器集 = { u, v, w, x, y, z } ■ 抽象模型——图 G = (N,E) N = 路由器集 = { u, v, w, x, y, z } E = 链路集 ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } u y x w v z 2 1 3 5 c(x,x’) = 节点X和X’ 间边的费用 讲课备注： 如何找出一条最优的路径呢？ 我们可以把网络形式化为一张图，应用图论和算法的知识解决问题 当然在网络中我们仅考虑无向图，即假定双向的费用一致 路径费用 (x1, x2, x3,…, xp) = c(x1,x2)+c(x2,x3)+…+c(xp-1,xp) 2017年3月11日 92

4.5 选路算法 路由算法的目标 如何找到一个路径序列（x1, x2, x3,…, xp） 使路径费用最小？ 2017年3月11日 93

4.5 选路算法 选路算法分类 根据信息是全局性还是分散式的进行分类 全局选路算法 分散式选路算法 所有路由器都知道整个网络拓扑图以及链路的费用信息 链路状态算法 分散式选路算法 每个路由器仅有与其相连链路的费用信息 通过迭代计算过程与相邻节点交换信息 距离向量算法 2017年3月11日 94

4.5 选路算法 根据信息是静态还是动态的进行分类 静态选路算法 动态选路算法 随着时间的流逝，路由的变化非常缓 路由信息可以更快地发生变化 周期性的更新 可以响应拓扑或链路费用的变化 2017年3月11日 95

4.5 选路算法 根据是否对负载敏感进行分类 负载敏感算法 负载迟钝算法 链路费用会动态地变化以反映出链路的当前状况 链路费用不明显地反映链路的当前状况 2017年3月11日 96

4.5 选路算法 链路状态选路算法 所有节点都知道网络拓扑和链路费用 计算从某节点到网络中所有其他节点的最低费用 所有节点具有该网络的同一个完整的视图 通过链路状态广播获得信息 计算从某节点到网络中所有其他节点的最低费用 迭代计算，获得该节点到所有其他节点的最低费用路径 为该节点提供转发表 2017年3月11日 97

4.5 选路算法 链路状态选路算法——符号定义 若x和y不直接相连，则c(x,y)=∞ c(x,y): 从节点x到节点y的链路费用 D(v): 从源节点到目的v的最低费用路径的费用 p(v): 从源节点到v沿着当前最低费用路径的前一节点 N‘: 节点子集。 若源节点到x的最低费用路径已知，则x在该集合中。 2017年3月11日 98 98

4.5 选路算法 链路状态选路算法 z x u y w v 步骤 1 2 3 4 5 N' u ux uxy uxyv uxyvw 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz D(v),p(v) 2,u D(w),p(w) 5,u 4,x 3,y D(x),p(x) 1,u D(y),p(y) ∞ 2,x D(z),p(z) ∞ 4,y 2017年3月11日 99

4.5 选路算法 1 Initialization: 2 N' = {u} 3 for all nodes v 4 if v adjacent to u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in N' such that D(w) is a minimum 10 add w to N' 11 update D(v) for all v adjacent to w and not in N' : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N' 2017年3月11日 100

4.5 选路算法 链路状态选路算法的复杂性 对于第一次迭代: 需要搜索所有的n个节点以确定出节点w,w不在N’中且具有最低费用 在所有迭代中需要搜索的节点总数为n(n+1)/2 ，所以链路状态算法在最差情况下复杂性为 O(n2) 2017年3月11日 101

4.5 选路算法 链路状态选路算法可能出现的问题 A D B C … 重新计算路由 …重新计算 初始选路 1 1+e 2+e e 2+e 初始选路 … 重新计算路由 …重新计算 2017年3月11日 102

4.5 选路算法 解决的方案 强制链路费用不依赖于所承载的流量 确保所有的路由器不同时运行LS算法 无法解决高拥塞的问题，不可接受 因特网上的路由器能够自同步 随机化路由器发送链路通告的时间 2017年3月11日 103

4.5 选路算法 距离向量选路算法 特点：迭代、分布、自我终止、异步 思想 dx(y)=minv{c(x,v)+dv(y)} 路由器不定期向其邻居路由器传送距离向量的拷贝 接收到邻居距离向量的路由器，用方程式更新自己的距离向量 如果因为邻居的距离向量导致自己的发生改变，则将其更新的距离向量发送它的每一个邻居 每一个路由器重复上述动作，直至收敛 从x到y的最低费用 dx(y)是：对于x所有邻居v的 c(x,v)+dv(y)值最小的那一个 2017年3月11日 104

4.5 选路算法 向量更新 z x u y w v u v: 2，v u x v: 3，x u w: 5，w u x w: 4，x v 1 3 5 向量更新 u v: 2，v u x v: 3，x u w: 5，w u x w: 4，x v 2,v w 5,w x 1,x y ∞ z ∞ u u的距离向量： 4,x v 2,v w 3,w u 1,u y 1,y z ∞ x的距离向量： x 2017年3月11日 105

4.5 选路算法 链路状态改变时的特点 好消息传的快 在 t0 时刻, y 检测到链路费用变化, 更新自己的距离向量, 同时将这个变化通知给它的邻居 在 t1时刻, z 收到来自 y 的更新报文并更新了自己的距离向量表，计算出到x的新的最低费用，并向邻居发送它的新距离向量 在 t2时刻，y 收到自z的更新并更新其距离向量表，Y的最低费用未变，因此y不发送任何报文给z x z 1 4 50 y 2017年3月11日 106

4.5 选路算法 链路状态改变时的特点 坏消息传播的慢 y重新计算其链路向量： 60 x z 1 50 y 4 Dy(x) = 4 Dy(z) = 1 Dz(y) = 1 Dz(x) = 5 y重新计算其链路向量： Dy(z) = 1 Dy(x) = min{c(y,x), c(y,z)+Dz(x)} = min{60, 1+5} = 6 y的链路向量到达z，使得Dz(x)=7，再传回y，使得Dy(x)=8 , …… 2017年3月11日 107

4.5 选路算法 解决方案——毒性逆转 如果z通过y选路到达目的地x : 当涉及到三个或者以上的节点的问题时，毒性逆转方案无法解决！ z将通告y，它到x的距离是无穷大 (所以 y不会通过z到达x) 当涉及到三个或者以上的节点的问题时，毒性逆转方案无法解决！

4.5 选路算法 链路状态路由选择算法 vs 距离向量路由选择算法 收敛速度 报文的复杂性 LS: n 个节点, E 条链路,需要发送 O(nE)个报文 DV: 只在直连的邻居之间交换报文 收敛速度 算法收敛时间依赖于许多因素，因而是可变的 LS: 是一个要求O(nE)个报文的O(n2) 算法 可能有震荡 DV: 收敛时间不确定 可能会遇到选路环路 记数到无穷问题 2017年3月11日 109 109

4.5 选路算法 健壮性 LS: DV 节点能够向其连接的链路广播不正确费用 每个节点只计算自己的转发表 一个节点可向任意或所有目的节点通告其不正确的最低费用路径 每个节点的计算都会传递给它的邻居 错误会通过网络进行传播 2017年3月11日 110 110

4.5 选路算法 层次路由 问题背景 因特网规模过大 管理自治 路由器无法存储每台主机的选路信息 路由表更新的报文广播将导致无剩余带宽供发送数据使用 管理自治 因特网 = 网络的网络 每个网络管理员可能希望能够按照自己的愿望运行和管理其网络 2017年3月11日 111 111

4.5 选路算法 解决方法 将路由器聚合到一个区域, “自治系统” (AS) 在AS内的路由器运行AS内选路协议 自治系统内部选路协议 内部网关协议 IGP (Interior Gateway Protocol) 目前这类路由选择协议使用得最多，如 RIP 和 OSPF 协议。 在相同AS内的路由器可运行AS内选路协议 在不同AS内的路由器可以运行不同的自治系统内部选路协议 不同AS间的选路，利用AS间选路协议 负责连接不同AS的路由器称为“网关路由器” 2017年3月11日 112 112

4.5 选路算法 转发表是由AS内部选路算法和AS间选路算法共同决定的 目标地址在AS内的由AS内选路协议产生 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d AS内部 选路算法 AS间选 路算法 转发表 2017年3月11日 113 113

4.5 选路算法 因特网中的自治系统内部选路协议1——OSPF协议 “开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。 “最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法SPF OSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。 是分布式的链路状态协议。 2017年3月11日 114 114

4.5 选路算法 三个要点 向本自治系统中所有路由器发送信息，使用的方法是洪泛法 发送的信息就是与本路由器相邻的所有路由器的链路状态 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息 2017年3月11日 115

链路状态数据库 由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库 这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的 OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。OSPF 的更新过程收敛得快是其重要优点 2017年3月11日 116

4.5 选路算法 因特网中的链路状态选路——OSPF协议 不强制如何设置链路权值的策略，但提供对给定链路权值集合确定最低费用路径的机制 即使链路状态未发生变化，每30分钟广播一次链路状态 链路状态以OSPF通告的形式封装在OSPF报文中，由IP分组承载（协议号：89） OSPF路由器之间的交换都是经过鉴别的（简单的、MD5的），以确认OSPF通告的真实性，防止伪造和篡改 OSPF通告都是有序列号的，以防止重放攻击 OSPF中支持多条具有相同费用的路径 OSPF支持多播选路和层次路由 2017年3月11日 117 117

4.5 选路算法 因特网上的自治系统内部选路协议2——RIP协议 距离向量算法 相邻两点间链路上的费用定义为1，即只考虑源到目标经过多少个路由器，或多少“跳” 一条路径的最大费用限制为15 选路更新消息每30s在邻居之间以RIP响应报文（RIP通告）的形式进行交换 路由器经过180s没有收到来自某个邻居的RIP通告，则认为该邻居已离线，修改选路表，向其它邻居广播 RIP是一个运行在UDP上的应用层协议（端口520） 2017年3月11日 118 118

4.5 选路算法 自治系统间路由器的任务 AS1需要: 需要知道通过AS2可以到达哪些目的地，通过AS3可以到达哪些目的地 问题：该路由器应该将该数据报转 发到某一个网关路由器，但 是是哪一个呢？ AS1需要: 需要知道通过AS2可以到达哪些目的地，通过AS3可以到达哪些目的地 将这些可达性信息向AS1中的所有路由器传播 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c 2017年3月11日 119 119

4.5 选路算法 场景1：从源到目标仅有一条路可选 假设AS1从AS间选路协议知道子网 x 经AS3 (网关1c) 可达，但是通过AS2不可达。 AS1向它的所有路由器广播该可达信息。 路由器1d 知道，它的接口 I 在到路由器1c的最低费用路径上。 从而路由器1d将表项 (x,I)放入其转发表。 3b 1d 3a 1c 2a AS3 AS1 AS2 1a 2c 2b 1b 3c 2017年3月11日 120 120

使用AS内部协议的选路信息 决定每个网关的最低费用路径的费用 4.5 选路算法 场景2:从源到目标有多条路可选 现在假设AS1知道子网 x 可以通过 AS3 和 AS2到达. 为了配置转发表, 路由器 1d 必须决定通过哪个网关路由器转发报文（1b或1c）。 这也是自治系统间选路协议必须解决的问题! 热土豆选路: 将报文发送到最近的路由器。 从AS间协议知道经多个网关 可达子网x 使用AS内部协议的选路信息 决定每个网关的最低费用路径的费用 热土豆选路: 选择具有最小的最低费用的网关 从转发表决定通向最低费用网关的接口I，即转发表中的 (x,I) 表项。 2017年3月11日 121 121

4.5 选路算法 因特网上的AS间路由——BGP4 因特网的规模太大，使得自治系统之间路由选择非常困难。 对于自治系统之间的路由选择，要寻找最佳路由是很不现实的。 自治系统之间的路由选择必须考虑有关策略 BGP 为每个AS提供一种手段，以处理 从相邻AS获取子网可达性信息 向该AS内部的所有路由器传播这些可达性信息 基于该可达性信息和AS策略，决定到达子网的“好”路由 边界网关协议 BGP 只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由 2017年3月11日 122 122

4.5 选路算法 BGP 发言人 每一个自治系统的管理员要选择至少一个路由器作为该自治系统的“BGP 发言人” 。 一般说来，两个 BGP 发言人都是通过一个共享网络连接在一起的，而 BGP 发言人往往就是 BGP 边界路由器，但也可以不是 BGP 边界路由器。 2017年3月11日 123

4.5 选路算法 BGP 交换路由信息 一个 BGP 发言人与其他自治系统中的 BGP 发言人要交换路由信息，就要先建立 TCP 连接，然后在此连接上交换 BGP 报文以建立 BGP 会话(session)，利用 BGP 会话交换路由信息。 使用 TCP 连接能提供可靠的服务，也简化了路由选择协议。 使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此成为对方的邻站或对等站。 2017年3月11日 124

BGP 发言人和自治系统 AS 的关系 BGP BGP 发言人 AS1 发言人 AS2 BGP 发言人 BGP 发言人 AS3 2017年3月11日 125

BGP 发言人交换路径向量 自治系统 AS2 的 BGP 发言人通知主干网的 BGP 发言人：“要到达网络 N1, N2, N3 和 N4 可经过 AS2。” 本地 ISP（AS4） N1， N2 本地 ISP（AS5） N3， N4 地区 ISP （AS2） 主干网 （AS1） 本地 ISP（AS6） N5 地区 ISP （AS3） 本地 ISP（AS7） N6， N7 2017年3月11日 126

BGP 发言人交换路径向量 主干网还可发出通知：“要到达网络 N5, N6 和 N7 可沿路径（AS1, AS3）。” 本地 ISP（AS4） N1， N2 地区 ISP （AS2） 本地 ISP（AS5） N3， N4 主干网 （AS1） 本地 ISP（AS6） N5 本地 ISP（AS7） N6， N7 地区 ISP （AS3） 2017年3月11日 127

4.5 选路算法 路由协议小结 RIP OSPF BGP 协议类型 IGP EGP 信息表达格式 距离－向量协议 链路－状态协议 路径向量 交换信息范围 相邻路由器 自治系统或区域内路由器 BGP发言人 交换信息内容 路由表 链路状态 交换信息时间 30S 当链路状态发生变化 有变化 原则 最短路径 最小代价 可达性 收敛过程 较快 快 传输协议 UDP IP TCP 适用网络类型 小型网络 大型网络 自治系统之间 衡量标准 距离 可有多种度量标准 无 2017年3月11日 128 128

课后思考题 复习题 1、3、9、15、17、22、24 习 题 1、4、7、14、15、18、19、21、 23、25、 讨论题 5、6 习 题 1、4、7、14、15、18、19、21、 23、25、 讨论题 5、6 2017年3月11日 129 129

作业题 习题 1、15、16、22、26 2017年3月11日 130