IP路由技术与协议

IP路由技术与协议

IP 网络技术 第 6 部分 —— IP 路由协议与技术 参考内容： （ 1 ） 《 用 TCP/IP 进行网际互连 》 第一卷：原理、协议与体系结构（第五版） 第 13 、 14 、 15 、 16 章 （ 2 ） 《TCP/IP 协议族 》 （第 4 版） 第 11 、 12 章 1 内容提纲 1 、引言 2 、域内和域间路由选择 3 、距离向量路由选择与 RIP 4 、链路状态路由选择与 OSPF 5 、路径向量路由选择与 BGP 6 、多播和多播路由选择协议 2 1 、引言 互联网由许多 路由器 连接起来的网络组成 数据从源站到目的站，可能经过多个路由器 一个 路由器 连接多个网络，当路由器收到分组，应该将分组转发到哪个网络？ 按照路由表（选路表）转发！ 路由表 是怎样形成的？ 何时如何发现路由？ 如何建立和管理路由表？ lxm 3 1 、引言 根据何时和如何发现路由，路由可分为： 先应式路由 表驱动路由（事先建立路由表，查表转发） 适合静态网络的路由 反应式路由 按需路由（需要时发现并建立路由，按实时路由转发） 适合动态移动网络路由（如移动多跳 Ad-hoc 网络） 根据路由表的建立方式，路由可分为： 静态路由 —— 路由表管理者人工配置和维护 建表不需要额外网络开销 不能及时自动反映网络变化 可能出现路由与网络不一致的情况 动态路由 —— 路由表由路由协议动态创建和维护 路由发现过程需要占用网络资源，额外开销 表的形成需要一定时间 能自动适应网络变化，更灵活 lxm 4 1 、引言 路由协议的目的 —— 使路由器能够找到到达目的地的最佳路径 路由协议的共同特点 路由器协同工作 彼此共享对互连网络的信息 计算路径，建立路由表 根据拓扑或某些策略 规定信息交互的周期，定期更新路由表 网络拓扑变化时，触发更新路由 lxm 5 交互信息（报文）不同，体现了不同路由协议特点 不同的路由协议，计算方法不同 : 可能局部路由，可能全局路由，可能依赖邻居 关键词 ——Metric （度量） Metric ：用来衡量 通过某一网络 所需的代价 代价 是什么？ 代价的度量取决于 Routing Protocol Hop count （跳数） , bandwidth （带宽） , delay （延迟） , MTU, load （负载） , reliability （可靠性） , … Routing protocol 使用 Metric 来选择一条 best path （最优路） for routing Metric 之和最小的路径 64K 64K 10M 10M 10M Hop count: A  B  Net Bandwidth: A  C  D  Net A D C B Net lxm 6 关键词 ——Convergence （收敛） Convergence 网络中的所有路由器都认为一致的 topology Convergence time （收敛时间） 网络发现到网络形成或网络变化到恢复的时间 反应了网络形成或恢复的快慢 从不一致到一致所经历的时间 体现路由算法的效率 影响收敛的因素 使用的路由协议 变化点到路由器的距离 网络中路由器的数量 通信链路的带宽和负载 路由器的负载 。。。。。。 lxm 7 2 、域内路由与域间路由 Internet 十分庞大，需要划分多个自治系统 AS Autonomous system （自治系统， AS ） 一个管理机构管辖的一组网路和路由器 每个 AS 可选择一个或多个路由协议处理本 AS 内的路由选择 AS 内部的路由选择称为 域内路由选择 AS 的编号 每个 AS 都赋予一个编号 Range: 1~65535 Private AS number: 64512~65535 lxm 8 2 、域内路由与域间路由 Internet 十分庞大，需要划分多个自治系统 AS Autonomous system （自治系统， AS ） 一个管理机构管辖的一组网路和路由器 每个 AS 可选择一个或多个路由协议处理本 AS 内的路由选择 AS 内部的路由选择称为 域内路由选择 AS 的编号 每个 AS 都赋予一个编号 Range: 1~65535 Private AS number: 64512~65535 lxm 9 2 、域内路由与域间路由 Internet 由若干 AS 互相连接构成 每个 AS 内可能有多个网络存在 核心主干网也可以构成一个 AS 核心主干网提供到所有可能的目的地的可靠的、统一的、权威的路由 lxm 10 ASx ASy AS1 核心主干网 AS3 AS2 IGP 与 EGP IGP: Interior Gateway Protocol （内部网关协议） 适用于 AS 内部路由，寻找 AS 内的最佳路径 Example ： RIP 、 OSPF 、 IS-IS EGP: Exterior Gateway Protocol （外部网关协议） 适用于 AS 之间路由，寻找到 AS 的最佳路径 Example ： BGP-4 Note The static routing or an IGP could also be used between autonomous systems in some case AS1 AS2 R R EGP IGP IGP lxm 11 IGP ：动态路由协议 RIP ：适用于密集型网络 采用广播方式与邻居网关交互路由信息 V-D 路由算法 RIPv1 ： RFC1058(STD 34, 1988) ， 基本协议 RIPv2 ： RFC1723(1994) ， 增加 CIDR 支持 OSPF ：适用于稀疏型网络 采用扩散方式与所有网关交互路由信息 Open SPF ，具有开放性的链路状态路由算法 OSPF V2 ： RFC2178 ， . J. Moy. April 1998. lxm 12 3 、距离向量路由选择与 RIP 协议 3.1 距离向量路由选择 3.1.1 距离向量路由选择算法 3.1.2 环路问题分析 3.1.3 解决环路的措施 3.2 RIP 协议 lxm 13 距离 向量 法（ V-D ： Vector Distance ） 根据协议的设计者命名，也称为 Bellman-Ford 路由算法 V-D 算法通常以跳数作为 Metric （ cost ） 当然也可以是其他度量参数：如时延、带宽等 基本 思想 每个节点都保持一张到其他节点的路由表 （ 目的 网络 ，距离，下一 节点 ）（如以跳数为 cost ，则距离就是跳数） 邻居 之间交换路由信息（ 目的 网络 ， 距离） 根据收到相邻节点的信息，判断并决定是否更新路由 算法涉及的内容 初始的路由表如何建立？ 邻居交换哪些信息 ? 如何根据邻居信息计算并更新自己的路由表？ V-D 路由算法 算法的几个步骤 初始化 建立初始路由表 —— 直连路由表 扩散 向邻居扩散自己的路由表信息 计算 根据收到相邻节点的信息，计算最短路径，更新路由表 再扩散、再计算 这样就逐渐形成了到全网路由 使每个节点都计算出了到其他节点的路径信息 值得注意的是：何时向邻居扩散路由信息？ 定期 拓扑发生变化时 V-D 算法案例 1 ）初始路由表建立 （目的网络，距离，下一跳）（初始都是直连网路 2 ）路由表向邻居扩散 2 1 3 4 5 特别说明： 为方便讲解，本教案采用跳数作为 metric 到直连网络的最短距离为 1 跳，因此“距离”记为 1 注意： 度量值也可以是其他参数 1 2 3 4 5 6 目的 网络 距离 下 一跳 1 1 --- 2 1 -- 目的 网络 距离 下 一跳 1 1 -- 3 1 -- 目的 网络 距离 下 一跳 2 1 -- 4 1 -- 5 1 -- 目的 网络 距离 下 一跳 3 1 -- 4 1 -- 6 1 -- 目的 网络 距离 下 一跳 5 1 -- 6 1 -- V-D 算法案例 3 ）节点计算并更新本节点的路由表 相邻 节点定期交换信息 （目的网络，距离） ——— （目的网络，跳数） 更新路由表的原则 （以跳数为例） 将收到的路由表信息与 本 节点 原 路由表比较 （ 1 ）若原表项 无该项 ，则代价 +1 ，添加该项 （ 2 ）若原表项中 有该项 若具有不同 的下一跳，但 代价 +1 小于 原表项，更新 ； 否则 ，保留原表项 若具有相同的下一跳，无论代价是否 = 原代价，都必须更新！ Why ？ 距离矢量算法 节点 1 路由表更新 初始值 目的 网络 距离 下 一跳 1 1 --- 2 1 -- 收到节点 2 信息 目的 网络 距离 1 1 3 1 更新 1 目的 网络 距离 下 一跳 1 1 --- 2 1 -- 3 2 2 2 1 3 5 1 2 3 4 5 6 4 目的 网络 距离 2 1 4 1 5 1 收到节点 3 信息 目的 网络 距离 下 一跳 1 1 --- 2 1 -- 3 2 2 4 2 3 5 2 3 更新 2 目的 网络 距离 下 一跳 1 1 --- 2 1 -- 3 2 2 4 2 3 5 2 3 多次更新的 稳定的表项 6 3 2 也可能是 3 ，取决于节点 1 先收到 2 还是 3 的再次路由信息发布 同理，其他节点也能得到稳定的路由表 Count to Infinity ，计数到无穷大 2-node loop Net 1 Net 2 Net 3 Net1 …… … … Routing table Net1 A …… … … Routing table A B You can reach net1 through me with length 2 B can reach net1 ! Great ! Hop count changed ! - 1 16 2 3 Hop count changed ! 4 - B ∞ ∞ B: ( net1, 2 ) A: ( net1, 3 ) B: ( net1, 4 ) lxm 19 定义 16 代表无穷大 A C B D 平时： A 收到 C 告知： D 有两跳 A 收到 B 告知： D 有一跳 选 B C 收到 A 告知： D 有两跳 C 收到 B 告知： D 有一跳 选 B 当 B 到 D 的链路断掉后，一种可能的情形： B 告诉 A 、 C ： D 不可达 A 重新选路，正好收到 C 告知 D 有两跳（ C 还没收到 B 的更新信息） A 选择到 D 经过 C ，距离为三跳 A 告知 B ： D 有三跳 B 选择到 D 经过 A ，距离为四跳 C 收到 B 先前的 D 不可达更新，重新选路 B 告知 C ： D 有四跳 C 选择到 D 经过 B ，距离为五跳 出现路由环路， 并计数到无穷大 几种解决措施 Defining infinity （定义无穷大） U se a finite metric value to represent “infinity“ （ 典型值 16 ） Th e value must be large enough that no real metric would ever get that large Triggered update （触发更新） Split horizons （水平分割） Poison reverse （毒性逆转） A variation of split horizons None of them are 100% effective ! lxm 21 触发更新 目的：促进快速收敛 如网络无变化 每隔 30 秒定期发送路由更新消息 如网络有变化 立即触发发送路由更新消息 lxm 22 Split Horizons （水平分割） Net 1 Net 2 Net 3 A B Net2 1 Net3 2 Net3 1 Net1 2 Net2 1 节点没有必要将从某节点 收到的信息再传回给该节点 lxm 23 Net1 1 ---- Net2 1 ---- Net3 2 B A 路由表 Net2 -- Net3 -- B 发给 A Net1 1 A 传给 B Poison Reverse （毒性反转） Net 1 Net 2 Net 3 A B Net2 1 Net3 2 Net1 16 Net2 16 Net3 16 Net1 1 Net2 16 Net3 1 Net1 16 Net2 1 Net3 16 Net1 2 节点将从某节点收到的信息再传回给该节点时，告诉对方不能从我这里过（设置成 16 ） lxm 24 Hold-down Timer, 抑制定时器 当路由器收到一个路由不可达更新消息时，启动抑制定时器 ( 60s 、 120s) 路由器收到某条路由不可达的消息后，在一段时间内（典型 60 秒），忽略关于该网络的任何路由信息 确保有较大范围内的站点都收到该坏消息，避免过时的路由通告，但抑制期间环路依然存在 V-D 算法小节 特点： 只与邻节点交换路由信息 各节点独立计算最优路径（但依赖邻居的计算结果） 能适应网络拓扑的变化 稳定后，形成最短路径 算法简单 缺点： 网络变化扩散到全网速度慢 扩散时间：所有节点都发现变化的速度 路由收敛慢 经过多轮邻居信息交换才能趋于一致 存在路由环－－在网络变化未扩散完全时。 适用于 小网 lxm 26 3.2 RIP 协议 3.2.1 RIP 概述 3.2.2 RIP 操作 3.2.3 RIP 定时器 3.2.4 RIP 消息格式 3.2.5 相关讨论 lxm 27 3.2.1 RIP 概述 标准 RIPv1 ： RFC1058(STD 34, 1988) ， 基本协议 RIPv2 ： RFC2453 ， 增加 CIDR 支持 采用 V-D 算法 采用跳数作为度量 采用 UDP 封装 平面路由协议，仅适合小网 lxm 28 3.2.1 RIP 协议 Routing Information Protocol ， RIP v1 ： RFC 1058 ， v2 ： RFC 2453 ，路由信息协议 IP LANs MANs WANs ICMP IGMP ARP RARP Network Layer Network Access Layer TCP UDP Transport Layer RIP Application Layer 520 软件实现层次 RIP = RIPv1 lxm 29 yn@uestc.edu.cn 30 Example of a domain using RIP Metric: hop count （跳数） Infinity = 16, means unreachable The maximum hop count = 15 3.2.2 RIP 操作 Discovery Topology change Calculating RIP updating algorithm Initialize RT Send RT Update RT Update? Send RT per 30s No Yes Find the change Update RT Send RT on schedule Like discovery Split horizons & poison reverse Triggered update lxm 31 yn@uestc.edu.cn 32 RFC1058 ： 发送时 unchanged 接收时 Metric + 1 某些实现： 发送时 Metric + 1 接收时 unchanged lxm 32 网络发现 A B C N1 N2 N3 N4 1 2 1 2 1 2 N3 - 1 0 N4 - 2 0 N1 - 1 0 N2 - 2 0 N2 - 1 0 N3 - 2 0 路由表： 目的网络 下一跳 发送接口 Metric   N3 N1 N2 B1 2 1 A2 1 1 B2 1 1 C1 2 1 N4 A: (N1, 1) (N2, 1) B: (N2, 1) (N3, 1) C: (N3, 1) (N4, 1) B: (N2, 1) (N3, 1)   N4 B1 2 2 N1 B2 1 2 A: (N1,1) (N2,1) (N3,2) B: (N2,1) (N3,1) (N1,2) (N4,2) C: (N3,1) (N4,1) (N2,2) B: (N2,1) (N3,1) (N1,2) (N4,2)   A:(N1,1)(N2,1)(N3,2)(N4,3) B: (N2,1) (N3,1) (N1,2) (N4,2) C:(N3,1)(N4,1)(N2,2)(N1,2) B: (N2,1) (N3,1) (N1,2) (N4,2) lxm 33 拓扑变化 A B C N1 N2 N3 N4 1 2 1 2 1 2 N3 - 1 0 N4 - 2 0 N1 - 1 0 N2 - 2 N2 - 1 N3 - 2 0   N3 N1 N2 B1 2 1 A2 1 1 B2 1 1 C1 2 1 N4  N4 B1 2 2 N1 B2 1 2 B: (N2,16) (N3,1) (N1,16) (N4,2) A: (N1,1) (N2,16) (N3,16) (N4,16) 0 0 ∞ ∞ ∞ C: (N3,1) (N4,1) (N2,16) (N1,16) ∞ ∞ ∞ ∞ lxm 34 3.2.3 RIP 的定时器 Timers 无用信息收集 60 或 120 s (for each route) 截至期 180 s (for each route) 定期 30 s (for each router) 控制更新报文定期通告， 通常为 25-35s 的随机数 避免同时更新引起过载 触发更新例外 管理路由的有效性 正常情况下，每 30s 复位一次，如故障，在 180s 未收到更新报文，则过期，跳数设置为 16 当某条路由信息成为无效时（ 16 ），路由器并不立即清除该表项，而是继续通告，待 120s 后才清除该表项 lxm 35 3.2.4 RIP 消息格式（ V1) RIP 只定义了有一种报文格式 交换（ IP address ， Metric ）对 IP address 可为 A 、 B 、 C 类网络地址或主机地址 Command Version=1 IP address All 0s All 0s All 0s Metric ( hop count ) All 0s Family = 2 Repeated lxm 36 3.2.4 RIP 消息格式（ V1) Command 1=Request 请求部分或全部选路信息 2=Response 发送方给出自己选路表的 (V ， D) 9= 更新请求 10= 更新响应 11= 更新确认 Address Family Identifier 2 ＝ IPaddress V1 版未定义掩码，只能用于有类地址方式 lxm 37 RIPv2 的扩展 RIPv2 格式 路由标记：路由起点、自治域号等额外信息 RIP2 实现对 CIDR 的扩展 0 8 16 24 31 Command Version=2 Must be 0 Address Family Identifier 目的网的路由标记 目的网地址（ IP Addr ） 目的网掩码（ Mask ） 到目的网的下一网关（ Next Hop ） 到目的网的距离（ Metric ） 重复 25 次 lxm 38 3.2.5 RIP 的讨论 距离＝ 16 指网络的跨度，而不是路由器的数目 RIP 适合于不大的网络 简单的路由，无法处理时延、容量要求 相对固定的路由，较长时间不变 无法对网络性能变化（负载、时延等）做出反应（调整路由） 仍有大量的应用 lxm 39 4 、链路状态路由选择与 OSPF 4.1 链路状态路由选择 4.1.1 算法基本思想 4.1.2 链路状态算法的操作 4.2 OSPF 协议 lxm 40 4.1.1 L-S 路由选择算法基本思想 参与该算法的所有路由器都需要掌握全部拓扑结构 拓扑结构： 点：路由器 边：路由器相连的网络 算法基本思想 周期地检查邻接路由器的状态（可达性） 向所有路由器通告自己的链路状态（全网扩散） 每个路由器根据自己掌握的拓扑结构，独立计算到所有目网络的路由 典型算法： Dijkstra 最短路径算法 lxm 41 4.1.1 L-S 路由选择算法基本思想 涉及到的主要问题 （ 1 ）各路由器如何知道全部拓扑？ （ 2 ）路由器如何扩散自己的链路状态 （ 3 ）路由器如何计算到各网的最短路径 lxm 42 4.1.2 链路状态算法的操作 发现邻居 探寻邻居，得到邻居的唯一地址 测量链路开销 测量到各邻居节点的延迟（链路质量） 交换路链路状态信息 形成链路状态分组，向所有节点扩散 充实路由信息库 根据收到各节点的链路状态信息，进而得出全网拓扑 计算到各网络的最佳路径 根据自己掌握的路由信息，独立计算本节点到其他节点的最佳路由 特别注意： 交流的路由信息：链路状态信息 交流的对象：向所有的节点 交流的方法：扩散法 路由的计算：只根据自己掌握的路由信息，独立计算最佳路由（不依赖别人的计算） lxm 43 链路状态算法 —— 发现邻居 初始时，每个节点都向每个出口（直接链路）发送 “ Hello ” 分组，告知自己的 IP 地址 收到分组的节点则回应一个分组告知自己的 IP 地址 特别强调：每个节点的地址必须唯一 A B Hello ， I am A Hello ， I am B lxm 44 链路状态算法 —— 测量链路开销 测量链路开销（以链路时延为例） 向邻居发送 “ Echo ” 分组（对方必须应答） 对方发送应答 计算来回延时除以 2 ，得到时延（可计算几次得平均值） 计算链路开销时值得讨论的问题 是否考虑负荷？ 两种观念 考虑负荷，从进入发送队列排队开始算 忽略负荷，从发送开始算 正反方向延时是否一样？ 可能不一样 为分析简便，通常忽略差异，用平均值 A B T “Echo” “Echo”Response lxm 45 链路状态算法 —— 测量并计算链路开销 通过测试计算出到邻居的开销 假设各节点测得的开销如下所示 A 节点 B 节点 4 C 3 B 开销 邻居 6 C 5 D 3 A 开销 邻居 2 D 6 B 1 E 4 A 开销 邻居 3 E 2 C 2 F 5 B 开销 邻居 3 D 2 F 1 C 开销 邻居 2 E 2 D 开销 邻居 C 节点 D 节点 F 节点 E 节点 lxm 46 链路状态算法 —— 交换链路状态信息 创建链路状态分组并向全网发布 根据测得的到所有邻居的的延时，形成链路状态分组 链路状态分组的内容 发布者：发布信息的节点名称 序号：序号的大小表示信息的新旧 年龄：一个分组在网络中的存活时间 B A C D E F 1 2 2 5 6 2 4 3 3 4 C 3 B 时间 序号 A 发布者 6 C 3 A 时间 序号 B 发布者 5 D 6 B 4 A 时间 序号 C 发布者 2 D 1 E 2 C 5 B 时间 序号 D 发布者 3 E 2 F 3 D 1 C 时间 序号 E 发布者 2 F 2 E 2 D 时间 序号 F 发布者 lxm 47 链路状态算法 发布链路状态分组 发布对象：所有节点 发布时间：定期，连路状态发生改变时 发布方法：扩散法（洪泛） 采用扩散法一定可以到达全网各节点 节点可能收到多个相同的分组 可根据序号判别，相同的序号则丢弃重复的 节点也可能收到同一个发布者不同序号的分组 根据发布时间判别，丢弃老的，处理新的 为避免分组可能在网中循环 通过年龄字段避免（年龄按时间递减，到 0 时将被丢弃） lxm 48 链路状态算法 —— 绘制全局拓扑 根据逐步收到的链路分组，充实路由信息库，逐步 “ 绘出 ” 拓扑图 以节点 A 为例，各节点发布链路分组后， A 逐步得到了分组 4 C 3 B 时间 序号 A 发布者 6 C 3 A 时间 序号 B 发布者 5 D 6 B 4 A 时间 序号 C 发布者 2 D 1 E 2 C 5 B 时间 序号 D 发布者 3 E 2 F 3 D 1 C 时间 序号 E 发布者 2 F 2 E 2 D 时间 序号 F 发布者 B A C D E F 1 2 2 5 6 2 4 3 3 lxm 49 链路状态算法 —— 计算最佳路径 计算到各节点的最佳路由 计算方法： 把本节点作为源节点，计算到其他节点的路由 采用著名的 Dijkstra 算法（最短路径算法） 计算的依据 只根据自己掌握的路由信息库（拓扑） 独立计算最佳路由（不依赖别人的计算） lxm 50 链路状态算法 Dijkstra 算法的基本思想 以计算路由的节点 V0 为源节点（出发点） 1 ）设置源节点到其他所有节点的初始开销 相邻的节点设置为测得的开销值（ Ci ， Vi ） Ci ：源节点到相邻节点 Vi 的代价（ cost ） 不相邻的节点设置为（ ∞， - ） 2 ）将具有最小 Ci 的节点 Vi 及链路加入到 V0 的路由中 3 ）根据加入的 Vi 节点计算与之相邻节点到 V0 的最小代价 并将到 V0 代价最小的节点及链路加入到路由中（已加入的节点和链路除外） 4 ）依此，不断重复 3 ），直到包含所有节点和最佳链路为止 lxm 51 链路状态算法 Dijkstra 算法案例 假设 A 收到 B 的链路分组， 以 A 为源节点， 计算 A 到其他节点的路由 B A C D 5 6 4 3 A B C D 3 4 ∞ A B 4 8 A B C 8 A B C D 8 节点的逐步加入 链路的逐步加入 A 到其他节点代价的逐步优化 A-B A-C B-D 6 C 3 A 时间 序号 B 发布者 5 D B A C D 5 4 3 A 的路由 转发表 目的节点 下一节点 开销 B B 3 C C 4 D B 8 A 节点 4 C 3 B 开销 邻居 lxm 52 链路状态算法 Dijkstra 算法案例 假设 A 收到 B 、 C 的链路分组， 以 A 为源节点， 计算 A 到其他节点的路由 6 C 3 A 时间 序号 B 发布者 5 D 6 B 4 A 时间 序号 C 发布者 2 D 1 E B A C D E 1 5 6 2 4 3 A B C D E 3 4 ∞ ∞ A B 4 8 ∞ A B C 6 5 A B C E 6 A B C E D 节点的逐步加入 链路的逐步加入 A 到其他节点代价的逐步优化 A-B A-C C-E C-D B A C D E 1 2 4 3 A 的路由转发表 目的节点 下一节点 开销 B B 3 C C 4 D C 6 E C 5 lxm 53 A 的路由转发表 链路状态算法 Dijkstra 算法案例 A 点收到所有节点分组后 以 A 为源节点， 计算 A 到其他节点的路由 B A C D E F 1 2 2 5 6 2 4 3 3 A B C D E F 3 4 ∞ ∞ ∞ A B 4 8 ∞ ∞ A B C 6 5 ∞ A B C E 6 7 A B C E D 7 A B C E D F 节点的逐步加入 链路的逐步加入 A 到其他节点代价的逐步优化 A-B A-C C-E C-D E-F lxm 54 链路状态算法 Dijkstra 算法案例 计算的结果， A 点到其他节点形成了一棵以 A 为根的树 根据最优判决原理，这是一棵最佳路由树 也称为信源树或汇集树 B A C D E F 1 2 2 5 6 2 4 3 A B C E D F 3 3 4 2 1 2 lxm 55 链路状态算法 Dijkstra 算法案例 根据计算结果， A 节点的路由转发表如下： A B C E D F 3 4 2 1 2 目的节点 下一节点 开销 B B 3 C C 4 D C 6 E C 5 F C 7 A 节点的路由转发表 B A C D E 1 2 2 5 6 2 4 3 3 F lxm 56 链路状态算法小结 特点 与全网节点交换路由信息－－路由信息的扩散 各节点独立计算最优路径－－一致性、准确性有较好的保证 不是建立在别人的计算结果上（如距离矢量算法以来邻居的计算结构） 能适应网络拓扑的变化，稳定后能形成最短路径 收敛速度快－－可在大网中使用 拓扑改变立即独立计算 算法复杂，存储空间需求大 需要记录全网所有的链路状态 lxm 57 4.2 OSPF 4.2.1 OSPF 概述 4.2.2 OSPF 的分区 4.2.3 OSPF 路由器类型 4.2.4 OSPF 链路类型 4.2.5 OSPF 分组格式 4.2.6 OSPF 的 LSU 分组 4.2.7 OSPF 的 LSA 类型 4.2.8 OSPF 的操作 lxm 58 4.2.1 OSPF 概述 OSPF: O pen S hortest P ath F irst 一种适合与 AS 内的路由协议 采用 L-S 算法计算最短路径 OSPF 直接使用 IP 实体提供的服务 IP 协议 ID 89 是一种分层的路由协议，适合于大网 lxm 59 4.2.1 OSPF 概述 lxm 60 IP LANs MANs WANs ICMP IGMP ARP RARP Network Layer Network Access Layer TCP UDP Transport Layer OSPF Application Layer 89 软件实现层次 RIP 520 OSPF 算法核心思想 掌握网络拓扑结构 掌握网络拓扑 = 掌握所有路由器与邻居的连接关系 通过路由器之间彼此共享链路状态 拓扑有变化时更新并共享 路由计算 根据网络拓扑结构，计算到任意站点的最短路径 (SPF) Dijkstra 经典算法 从最短路径确定下一跳地址 (FIB 内容 ) 关键点 只要掌握了网络拓结构，路由器就能计算所有路由 R1,1 R2,2 R3,3 R0,2 R1,2 R5,25 R2,25 R3,35 R4,45 R6,56 R8,58 邻居关系： R0 R2 R5 R0,1 R2,12 R4,14 R8,18 R1 lxm 61 4.2.2 OSPF 的分区 分区域理由：大规模的网络会给 OSPF 路由器带来沉重的负担 链路状态的改变，可能会使路由器经常执行 SPF （最短路径优先）算法 路由表膨胀 每个路由器需要保持的完整网络拓扑（链路数据库） OSPF 将网络划分成若干较小的区域 区域内的路由器执行 SPF 算法 区域间：交换汇总后的路由信息，而不是详细的路由信息 lxm 62 4.2.2 OSPF 的分区 lxm 63 多区域 每个区域是独立的 OSPF 路由协议范围 网络拓扑数据库只包含区域内部分 OSPF 协议在区域边界处终止 某些路由器会属于多个区域 称为：区域边界路由器 区域边界路由器构成另一个路由域（主干域） 形成分层路由结构 一级路由：区域间路由 —— 主干路由 二级路由：区域内路由 OSPF 域 OSPF 域 OSPF 域 OSPF 域 OSPF 域 OSPF 域 AS R R R R R R R R R R R R R R R R R R R R R R R R R 2 级路由 区域内路由 1 级路由 区域间路由） 3 级路由 R R R 区域内路由器 R 区域间路由器 R AS 边界路由器 分级路由结构 OSPF 多区域模型 2 级路由 区域内路由 2 级路由 区域内路由 3 级路由 lxm 63 4.2.2 OSPF 的分区 Area ：包含在 AS 中的一些网络、主机和路由器的集合 类型：标准区域、主干区域（ Backbone area ）、残桩区域（ Stub area ） Autonomous System Area 1 Area 2 Area 0 (backbone) To other ASs lxm 64 OSPF 区域类型 区域的类型：决定 了该区域内路由器所能接收的路由信息的类型 标准区域：区域内路由器能够接收 链路状态更新 和 路由归纳（区间路由） 主干区域：具有标准区域的一切属性，特殊之处在于：它需要负责 互连 其它所有 区域 残桩区域：这种区域 不接收 那些 自治系统以外 的路由信息 如果需要发送分组到自治系统之外的网络，区域内路由器将使用 默认路由 lxm 65 Area 2 Area 3 Area 0 Area 1 Area 0 主干区域 负责分发非主干区域间的路由信息 AS 中的其他所有区域必须与主干区邻接 并不要求一定是物理连接 可以是 Virtual link （可以人工配置） Area 0 Area 0 Area 2 Area 1 Area 3 lxm 66 67 4.2.3 OSPF 路由器类型 Autonomous System Area 1 Area 2 Area 0 (backbone) To other AS ABR ， BR IR ASBR ， BR IR ， BR Internal router （内部路由器） , IR Backbone router （主干路由器） , BR Area Border Router （区域边界路由器） , ABR AS Border Router （ AS 边界路由器） , ASBR lxm 67 68 4.2.3 OSPF 路由器类型 Autonomous System Area 1 Area 2 Area 0 (backbone) To other AS ABR:ABR 接口连接不同区域 ABR 为其连接的每个区域维护单独的链路状态数据库 并从中归纳路由，将汇总路由发布到主干区域，而主干区域中的 ABR 再将其扩散到其它区域 IR ： IR 所有接口都在同一区域，同区的 IR 有相同的链路状态库 ASBR ：向 AS 通告 AS 以外的路由 IR ， BR lxm 68 4.2.4 OSPF 的链路类型 Types of links Stub Transient Point-to-point Virtual Connect two routers directly Each router has many neighbors A special case of the transient network Created when link is broken lxm 69 4.2.4 OSPF 的链路类型 Point-to-point network ，点到点网络（链路） Stub network ，残桩网络（链路） Transit network ，转接网络（穿越网络，链路） Broadcast Frame Relay X.25 RFC2328 lxm 70 yn@uestc.edu.cn 71 3 3 3 2 2 5 2 2 5 Stub network Point-to-point network Point-to-point network Transit network Stub network Stub network lxm 71 穿越网络中的指定路由器 DR 和备份路由器 BDR Ethernet A B C D E Transient network A B C D E Unrealistic representation A B C D E Realistic representation Designated Router A designated router is used to show the connectivity of each router and one single network, so each router has only one neighbor now A transient link is a network with several routers attached to it lxm 72 4.2.5 OSPF 分组 Format Multicasting: 224.0.0.5, 224.0.0.6 224.0.0.5 所有 OSPF 路由器组播地址 224.0.0.6 穿越网络中的 DR/BDR 组播地址 Encapsulation: IP ( protocol 89 ) Version Type Router ID Area ID Packet Length Authentication Authentication Authentication Type Checksum Header OSPF Packet Data 路由器在 AS 内的唯一标识，发送该分组的源路由器。 32 位，采用路由器最大接口或最小接口的 IP 地址 lxm 73 TYPE 字段：分组类型 1: Hello packet ：问候分组（类型 1 ） A 64-byte packet （周期性发送 以保持链路 “alive” ） 2: DBD ( Database Description ) ，数据库描述分组（类型 2 ） 路由器间交换网络拓扑数据库 3: LSR ( Link-State Request ) ，链路状态请求分组（类型 3 ） 用于路由器向相邻路由器请求查询特定链路的当前信息 4: LSU ( Link-State Update ) ，链路状态更新分组（类型 4 ） 对 LSR 的响应，通告链路状态 5: LSAck ( Link-State Acknowledgement ) ，链路状态确认分组（类型 5 ） 对链路状态通告（ LSA ）的确认 4.2.5 LSU 分组格式 OSPF common header 24 bytes, Type = 4 Repeated LSAs (any combination of different kinds) # LSAs ( 1 byte ) 链路状态通告：五种不同类型的任意组合 链路状态通告数 lxm 75 LSA 格式 Header LSA data LS sequence number Advertising Router ID Link state ID LS checksum length LS age Options LS type 创建 LSA 的路由器 ID 链路状态类型： 5 种 lxm 76 Link State ID & Link ID Link state ID —— in LSA header Link ID —— in Router-LSA ( type 1 LSA ) LS type Link State ID 1: router-LSA The originating router's Router ID 2: network-LSA The IP interface address of the network's DR 3: summary-LSA The destination network's IP address 4: summary-LSA The Router ID of the described ASBR 5: AS-external-LSA The destination network's IP address Link type Link State ID 1: Point-to-point link Neighbor Router ID 2: link to transit network Interface address of DR （指定路由器） 3: link to stub network IP network address 4: virtual link Neighbor Router ID lxm 77 4.2.6 OSPF 的 LSA 类型 Intra-area （区域内） Type 1: Router–LSA Type 2: Network–LSA Inter-area （区域间） Type 3: Summary–LSA Type 4: Summary–LSA External （ AS 外） Type 5: AS–external–LSA lxm 78 Intra-area LSAs Type 1: Router–LSA 由所有路由器创建 描述连接真路由器的一条链路 仅在一个区域内洪泛 Type 2: Network–LSA 由指定路由器 DR 创建 包含连接到该网路的所有路由器 仅在一个区域内洪泛 lxm 79 Inter-area LSAs Type 3: Summary–LSA( 汇总链路到网络 ) ：由 ABR 产生，在其 所属的每个区域 里中发布 到达其它区域 的路由信息 lxm 80 R1/R2 ：两个路由表（区域 1/ 区域 2 ，区域 0 ） 向区域 1/ 区域 2 发布如何到达区域 0 的信息 ABS 产生的 LSA （汇总链路到网络） 举例 当子网 1 恢复连通以后，在子网 4 中收到的链路状态通告 lxm 81 Inter-area LSAs Type 4: Summary–LSA ( 汇总链路到 ASBR) ：由 ABR 产生，在本 AS 内的 所有区域中 发布到达 ASBR 的路径信息 lxm 82 ABS 产生的 LSA （汇总链路到 ASBR ） 举例 lxm 83 External LSAs Type 5: AS–external–LSA ：由 ASBR 产生，在 本 AS 内的某些区域 中发布到达 AS 以外网络 的路径信息 Originated by ASBR Describes a route to a destination in another AS Flooded throughout the AS except the stub area lxm 84 OSPF LSA Example 哪些路由器会发送 Router–LSA ？ Solution All routers advertise router link LSAs. R1 has two links, Net1 and Net2. R2 has one link, Net2 in this AS. R3 has two links, Net2 and Net3 lxm 85 OSPF LSA Example 哪些路由器发送的 LSA 中含有网络信息？ Solution All three network must advertise network links: R1 通告 Net1 Because it is the only router and therefore the designated router. Net2 可能由 R1, R2, R3 中任意一个通告 depending on which one is chosen as the designated router. R3 通告 Net3 is done because it is the only router and therefore the designated router. lxm 86 LSA 的发送方式 LSA 采用组播发送，所有 OSPF 路由器的组播地址都是： 224.0.0.5 在转接（穿越）网络中， DR 和 BDR 还具有自己的组播地址： 224.0.0. 6 转接网络中，由于一般路由器只与 DR/BDR 存在邻居关系，所以其 LSA 将发送到 224.0.0. 6 lxm 87 OSPF Databases Adjacency database （邻接数据库） All the neighbors to which a router has established bidirectional communication Unique for each router Link-state database （链路状态数据库） The relationship between each router and its neighbors All routers within an area have identical link-state databases Forwarding database ( routing table ) 转发表 The routes generated when an SPF algorithm is run on the link-state database The routing table on each router is unique lxm 88 4.2.7 OSPF 操作 1. Establish router adjacencies （建立邻接关系） Done with the exchange of Hellos 2. Elect the DR / BDR ( if necessary ) 如需要选择 DR/BDR Done on multiaccess network only 3. Discover routes （发现路由） Done in the ExStart and Exchange states 4. Select appropriate routes 选择合适路由 Done through the calculation of SPF algorithm 5. Maintain routing information 维护路由信息 Done through the regular exchange of Hellos lxm 89 Step 3. Discover routes Hello Packet A B Exstart Exchange Loading Full Hello Packet DBD Packet DBD Packet LSAck Packet LSAck Packet LSR Packet LSU Packet LSAck Packet lxm 90 5 、路径向量路由选择与 BGP 5.1 路径向量路由选择 5.1.1 问题的提出 5.1.2 基本思路 5.2 BGP lxm 91 5.1 问题的提出 RIP 与 OSPF 适合 AS 内的路由协议 当运行区域变大时， RIP 和 OSPF 变得不可用 RIP 变得不稳定，很难收敛 OSPF 计算路由表需要大量资源 引出 AS 间路由选择 —— 路径向量路由选择 Path vector routing 一种策略路由选择： 基于路径属性选择到达目的地的最佳路径 lxm 92 5.2 基本思路 每个 AS 中指定一些发言节点 —— 代表整个 AS 发言节点创建到达其他网络的路由表，并将其通知给相邻 AS 中发言节点 路由信息：（网络，路径） 路径： AS 列表组成 lxm 93 yn@uestc.edu.cn 94 Initial Routing Tables AS 3 AS 1 AS 2 AS 4 yn@uestc.edu.cn 95 Stabilized Routing Tables A1 B1 C1 D1 AS1 B2 B3 B4 A4 A2 A3 A5 C2 C3 D2 D3 D4 AS2 AS3 AS4 3 3 路径向量路由选择路由表 路由表： { 目的地， Next-hop ， Path } An ordered list of ASs that a packet should travel through to reach the destination Example Loop prevention 如果自己的 AS 在到达终点路径上，直接丢弃该报文。 Network Next Router Path N01 R01 AS1 4 , AS23, AS67 N02 R05 AS22, AS67, AS05, AS89 N03 R06 AS67, AS89, AS09, AS34 N04 R12 AS62, AS02, AS09 lxm 96 4.2 BGP-4 Border Gateway Protocol ， BGP v4 ： RFC 1771 ， RFC 1772 ，边界网关协议 IP LANs MANs WANs ICMP IGMP ARP RARP Network Layer Network Access Layer TCP UDP Transport Layer BGP-4 Application Layer 179 软件实现层次 lxm 97 从 BGP 的观点来看互联网 AS10 AS20 AS30 AS50 AS40 到 AS60 的路由是： AS20 、 AS10 、 AS30 AS60 lxm 98 AS 的类型 Stub AS （ Single-homed AS ，残庄 AS ） Only one connection to another AS Example: AS 1, AS 3 Multihomed AS （多归属 AS) More than one connection to other ASs Only a source or sink for data traffic not allow transit traffic to pass through it Example: the campus network of UESTC Transit AS （转接 或穿越 AS) A multihomed AS that allows transient traffic Example: ChinaNET, CERNET, … AS 1 AS 2 R R R AS 3 R lxm 99 外部网关协议实例 两个 AS ： CerNet 和 ChinaNet 沈阳 北京 上海 武汉 成都 广州 CerNet ChinaNet 担心：存在过度侵占其它 AS 资源的可能性 AS 间的路由需求问题 -- 不合理路由 -- 外部进入的访问保护 -- 穿越 AS 能力 (ISP) -- 穿越 AS 时选择避开非友好 AS -- 存在多条链路的协议交互 lxm 100 BGP,Border Gateway Protocol 一种 BGP 协议 BGP Speaker BGP Speaker 两个 AS 的多对网关连接和路由选择 AS1 核心网 AS2 核心网 用少量网关代言 (speaker) 所有网关 BGP 核心功能 向对方通告本方可达性信息及对应网关 Net-A Net-B G a G b G c G d BGP 基本操作 Gc 向对方通告： < 经 Gc 可达 Net-B> < 经 Ga 可达 Net-A> 效果： 到 Net-A 只能通过 Ga 到 Net-B 只能通过 Gc lxm 101 BGP 的工作模型 BGP 对等实体间通信方式 采用 TCP 保持长期连接，交互可达信息 两端 BGP 路由器不必有直接的链路连接 向内部路由器通告外部路由 BGP BGP TCP 连接 链路 链路 向 AS 内其它路由通告外部路由 lxm 102 BGP 协议交互 BGP 定义 5 个交互报文 OPEN 建立于对方 AS speaker 的 BGP 通信连接、进行认证等 UPDATE 通告路由项：增加、删除操作 ( 核心报文 ) NOTIFICATION 通告报文出错情况 KEEPALIVE 维持和测试通信连接 REFRESH 请求对方重传路由通告 TCP 的好处 可靠的通信，因此不需要应答、重传等复杂交互过程 为了保证可靠，仍设计了 refresh 报文，在需要的时候让对方重传 lxm 103 BGP 核心报文解析 通告对方增加和 / 或删除的路由项目 UPDATE( 删除 ( 路由列表 ) ，新增 < 路由属性、路由列表 >) 到该路由所经过的 AS 列表 该路由下一跳网关 Speaker 功能 让对方选择使用或弃用的参考 网关通过策略控制向对方有选择地通告路由项 -- 选择权在通告方 -- 由 AS 管理者制定策略 lxm 104 BGP 的功能 通告可达性 BGP BGP AS1 AS2 新增可达区域 N3 原可达区域 N1 R1 R2 原可达区域 N2 AS2 BGP 通告 UPDATE( 删除 N1 ，新增 N3(via R1)) 可访问： AS2 的 N1 和 N2 网络部分 可访问： AS2 的 N2 和 N3 网络部分， N1 部分已不可访问 通知 R2 拒绝来访 N1 通知 R1 开放 N3 的来访 lxm 105 BGP 协议交互过程 设计交互过程的因素 TCP 提供了可靠通信，因此，信息传递是可靠的 通告给对方的可达性信息不会经常改变 一旦信息传递发生错误 ( 小概率 ) ，有恢复措施 某条链路若出现故障时的预案 交互过程设计 信息传递及握手过程该如何实现？ 可达性信息传递是全部还是部分，周期还是非周期？ 链路状态如何探测？ 出错或重新连接时，如何得到可达性信息？ 链路故障时，采取什么预案，如何交互？ lxm 106 BGP 应用 —Cernet 对外路由 教育网和电信网两个自治系统 两个网络有多处互连 成都 武汉 西安 北京 上海 哈尔滨 广州 成都 武汉 西安 北京 上海 哈尔滨 广州 Cernet Chinanet Uestc 校园网 从 uestc 到新浪网经过的是哪条路？ 从 uestc 到清华校园网经过哪条路？ lxm 107 BGP 应用 — 负载均衡 为了增加某条链路容量，设置两条或更多的并行链路，把网间通信流量均衡分配到这些链路上 如何用 BGP 进行流量均衡？ 方法 1 、。。。 方法 2 、。。。 lxm 108 BGP 小结 自治系统间的路由协议 传递路由可达性信息 可达性路由信息与我们常说的路由信息有什么不同？ 自治系统对外开放窗口 BGP 如何处理到达的 IP 报文？ BGP 交互特性 TCP 可靠连接下的交互 交互过程的特点、实现的功能 自治系统内应用 网络之间互联与访问控制 例如：我校学院间的互访、与学校其它部门的互访 负载均衡 网络间多条链路的负载平衡 lxm 109 5 、多播和多播路由选择协议 引言 多播特点 IP 多播地址 IP 多播在物理网上是如何实现的？ 路由器如何掌握子网上是否需要多播？ 多播的路由问题 lxm 110 引言 单播 (unicast) 、广播 (broadcast) 、多播 (multicast) 单播：目的地址 = 单播地址 跨子网 本地广播：目的地址 = 全 1 地址 子网广播：目的地址 = 子网 + 全 1 主机 某个子网内 子网广播地址作单播地址看待 多播 目的地址 = 多播地址 跨子网 引言 IP 协议接收和处理多播报文的条件 IP 协议加入指定的多播组 IP 实体 报文 To:224.1.2.3 ( 丢弃报文 ) 未加入 224.1.2.3 多播组时 IP 实体 报文 To:224.1.2.3 ( 处理报文 ) 加入了 224.1.2.3 多播组时 每一个多播地址代表一个多播组 IP 实体可同时加入多个多播组 lxm 112 多播的用途 子网内路由器多播 RIP 路由器之间用多播传播路由信息 IPTV 一路电视网上只有一个视频流 极大减轻网络负担 多播在 Internet 应用广泛 VOD Net-Meeting 远程教学 … TV1 TV2 lxm 113 多播特点和多播类型 多播组 多播组由多播地址来定义 站点加入多播组来接收多播报文 加入多播组：设置接口允许接收该多播地址的报文 退出多播组：设置接口禁止接收该多播地址的报文 多播域 多播的传播范围，最大范围是 AS 内所有子网 站点 可随时加入或退出一个或多个多播组 多播路由器 专门的多播路由器 或在常规路由器中增加多播路由功能 lxm 114 IP 多播地址 地址范围 224.0.0.0~ 239.255.255.255 ，共 2 28 个多播地址 每个多播地址定义一个多播组 多播地址属性 子网多播地址：多播域有效范围在一个子网内 全局多播地址 每个多播地址的用途在所有多播域是一致的 如同电话的 110,119 等 本地多播地址 多播用途只在该多播域内有效，其它多播域可重用 lxm 115 IETF 规定的一些 IP 多播地址 224.0.0.1 ：本子网上的所有站点 224.0.0.2 ：本子网上的所有路由器 224.0.0.5 ：多播域内所有 OSPF 路由器 224.0.0.9 ：多播域内所有 RIP 路由器 224.0.0.11 ：移动代理 224.0.1.7 ：语音新闻广播 224.0.1.27-224.0.1.255 ：未定义，本地多播 224.2.0.0-224.2.255.255 ：多媒体会议 224.0.5.128-224.0.5.255 ：未定义，本地多播 224.0.6.128-224.0.6.255 ：未定义，本地多播 lxm 116 IP 多播技术 IP 多播如何在 IP 子网内实现？ 路由器如何掌握和管理子网内的多播组？ 路由器如何为多播选择路由 ( 多播路由 ) ？ lxm 117 IP 多播在子网内实现 IP 多播实现策略 利用物理网的多播机制 或利用物理网的广播机制 关键是让组播成员收到应该收到的组播报文 非多播成员收到多网报文会自动滤除 局域网都支持多播和广播 广域网通常 不 支持多播和广播 则采用单播方式实现多播 在支持多播的物理网上实现多播 如：以太网具备多播功能 关键问题是 IP 多播地址到 物理网地址映射 lxm 118 以太网上实现多播 以太网的多播机制 多播地址 =1xxxxxxxx…xxxxxxxx (x 不全为 1) MAC MAC MAC MAC MAC 多播组列表 MAC 协议中需配置多播组列表 MAC 接收以太网帧种类： 目的地址 = 自身 目的地址 = 广播地址 目的地址 in ( 多播组列表 ) 配置接口 MAC 最多设 16 个多播地址 当地址多于 16 个时， MAC 进入全收状态 lxm 119 IP 多播映射到 MAC 多播 IP 多播到以太网多播 IETF 规定的映射规则 将 IP 多播地址的低 23bit 放置到 MAC 地址 01.00.5E.00.00.00 的低 23bit 上 B0 1110 xxxx B1 xxxxxxxx B2 xxxxxxxx B3 xxxxxxxx 01 00 5E 00 00 00 IP 地址 MAC 地址 IP MAC 发送：以太网多播地址 = ARP (IP 多播地址 ) 接收：根据多播组地址列表进行过滤 IP 多播组列表 lxm 120 接收多播报文 以太网接收多播报文 MAC 对接收帧的过滤，只接收规定目的地址的帧 IP 接收多播报文 加入多播组  设置 MAC 实体的多播表 加入多个多播组 = 多次设置 MAC 实体的多播表 ( 设置计数加 1) IP 实体退出多播 撤销加入多播组 = 撤销 MAC 多播表对应地址 ( 设置计数减 1) MAC 的设置计数为 0 ，则删除对应多播 MAC 地址 MAC SAP=0800H IP 允许接收： 1 、目的 MAC 是自己 2 、目的 MAC 是广播 3 、目的 MAC 是预设的多播 MAC 之一 多播表 未加入多播组的站点不会收到多播报文 lxm 121 IP 多播管理协议 (IGMP) 路由器掌握子网的多播组信息，能更高效地实现多子网区域的多播中继 见示意图 IGMP 协议功能 站点向路由器报告加入或退出某个多播的情况 路由器查询子网的多播组情况 IP IP IP 若路由器知道 B 网没有多播组 1 的成员，则可以不向 B 网转发多播组 1 的报文 B A 多播组 1 MAC IP IGMP 内部接口 lxm 122 IGMP 协议 路由器掌握子网的多播组情况，是实现多子网区域组播的关键 ( 将多播报文从其它子网中继进来 ) 站点加入或退出多播组时，需向物理网的路由器报告 站点需确信路由器掌握自己加入多播组信息 IP A lxm 123 IGMP 协议设计 路由器查询、站点报告的协议 使用多播机制 (224.0.0.1) 实现 IGMP 协议通信 路由器查询（ 查询范围，路由器接口所在的子网） 周期性查询，重新登记多播组记录 发出查询时，路由器将“清空”组播记录 成员报告 每个组有一个成员发出报告即可 IP IP IP IP IP IP IP IP 组 1 组 1 组 2 定期查询 (125s) 报告 224.0.0.1 lxm 124 IGMP 协议说明 使用多播机制 (224.0.0.1) 实现 IGMP 通信 不参与多播的站点不受干扰 加入多播组的站点，一定同时要加入 224.0.0.1 组 路由器实际上只关心子网上有哪些多播组 哪些多播报文需要向该子网转发，与成员多少无关 查询时清空记录，以清空不存在的多播组 站点报告 组内有一个成员报告即可 路由器中有了多播组记录，站点才能成为多播组成员 在向路由器报告前，站点不算成员，故称为“延迟的成员” lxm 125 多播组成员状态转换 路由器周期性查询，站点的多播成员也随着周期性发生改变 路由器开始查询时，站点暂时退出“正式”成员，直到发出报告为止 站点刚加入某多播组时，不清楚路由器是否有该组的记录，所以站点不能算正式成员 非成员 延迟的 成员 成员 加入 / 定时 退出 / 取消定时 超时 / 发出报告 其它站点报告 / 取消定时 计数为 0/ 退出群组 查询 / 定时 lxm 126 IGMP 报文格式 IGMPv3 比以前版本有较大改变，但基本思路没变 查询报文 通用查询功能：要求任何群组都发出报告 特定查询功能：要求报文中指定的群组发出报告 报告报文 站点在报告中列出自己加入的一个或多个群组 IGMP 目前的不足 IGMP 没有为站点提供多播地址查询功能 除了永久分配的群组地址，站点不知道该子网上正在使用或可以使用哪些群组地址，也不知道这些群组地址的用途，也无法查询 没有站点主动退出时的报告机制 ( 造成路由器定时清空处理 ) lxm 127 多播转发和多播路由 多子网区域的多播，路由器转发多播报文 多播转发的特征： 动态：成员在动态变化 无方向性：应该向各处转发 A B C 动态路由选择： 1 、当网络 C 没有该多播组成员时，路由器不应该向网络 C 转发多播报文 2 、网络 C 的其它站点也可向该组发送多播报文，路由器应该转发此报文 2 、当网络 C 有站点加入该多播组时，路由器应当向网络 C 转发多播报文 某多播组成员 多播路由环路： 多播的路由极易形成环路 lxm 128 用洪泛方式实现多播 思想：确保多播报文送达多播域各处 从一个接口收到多播，向其余接口转发 洪泛控制 转发次数控制（ IP 报文中的 TTL 值） 序号控制转发 (IP 报文中的 ID 值 ) 记住并停止转发已转发过的多播报文 ( 源 IP ， ID) 第 k 次转发 1 2 2 3 3 3 3 k 3 3 3 极易形成“广播风暴” lxm 129 用洪泛方式实现多播 洪泛的性能 多播报文在网络中的信道出现次数 A A 处发出多播报文 计算 TTL 控制法和序号控制法的洪泛性能 lxm 130 经典的多播路由 反向路径转发 (RPF) 与单播路由结合，实现多播转发 A G1 G2 目的 Next 接口 Net1 A Net1 G1 1 2 3 3 当 G2 从接口 3 收到源为 A 的多播报文时，向其余接口转发 当 G2 从其它接口收到源为 A 的多播报文时，拒绝转发 G2 关于 Net1 的路由表项 与路由方向相反时转发多播，否则拒绝 lxm 131 经典的多播路由 截尾反向路径转发 (TRPF) 对 RPF 的多播性能改进 A Net1 Net2 R1 R2 R3 R4 R5 R6 1 、当 Net2 中 没有 站点加入 A 的多播组时， R3 应该 不再 向 R4 转发多播报文 2 、当 Net2 中 又有 站点加入 A 的多播组时， R3 应该 恢复 向 R4 转发多播报文 lxm 132 反向路径多播 (RPM) RPM 本质同 TRPF 增加路由器之间的多播组信息传递，动态修剪树枝 广播并剪除 ( 截尾技术 ) 如果某路由器下没有该多播组成员，则将此信息 ( 剪除请求 ) 通知路径的上一路由器，从而在多播传输上剪除该树枝 实现该截尾技术的条件是，第一个多播尽可能传递到所有子网，让路由器知道多播源站的方向，便于回溯多播信息 嫁接请求 若某路由器获知又有站点加入该多播组，则向上一路由器发出嫁接请求，把剪除的树枝再接上 第一次多播用“广播”到所有子网，路由器才考虑多播树的方向 然后路由器开始考虑发送“剪除请求” 剪除 剪除 嫁接 lxm 133 多播树 树可能是实现多播转发的“最好”的方法 树的形状 根、枝、叶 RPF 、 TRPF 、 RPM 的树 是一个以多播源站为“根”的树 值得思考的是 一个网络上有多个多播源，就有了多颗树 路由器就需要为多棵树考虑不同方向的转发 记录每个 （多播群组，源站） 问题的复杂性在于： 网络有多个群组 每个群组有多个源 ( 多播群组 1, 源站 11) ( 多播群组 1, 源站 12) ( 多播群组 1, 源站 13) ( 多播群组 2, 源站 21) ( 多播群组 2, 源站 22) ( 多播群组 2, 源站 23) ( 多播群组 3, 源站 31) ( 多播群组 3, 源站 32) ( 多播群组 3, 源站 33) 多播组 1 多播源 1 转发接口 1 转发接口 2 转发接口 3 多播源 2 转发接口 1 转发接口 2 多播组 2 lxm 134 核心基干树 (CBT) 考虑图论“树根”的性质 树的任意“点”都可以看作树根 由此，网络上只需要一颗多播树即可 ( 共享树 ) 即使没有“最短路径”的优势 可以在网络拓扑的众多树中选择一颗“最佳”的树 每个路由器只需考虑自己的哪些接口是“树枝” CBT 的形成：静态 + 动态 静态： 把网络划分成多个“区段”，指定区段内“核心路由器” 动态： 其它路由器通过“发现机制”找到“核心路由器”，形成区段内的树 树枝 树枝 树枝 lxm 135 多播 从任意节点进行多播，多播到所有节点 lxm 136 多播树 从任意节点进行多播 只需要树上的几个节点实现多播报文转发和多播发送 lxm 137 PIM—DM 、 SM PIM ： Protocol Independent Multicast 实际指：本身与单播路由协议有关，但仅 用单播路由表来建立多播树 PIM-DM 密集模式，站点密集的子网组成的多子网区域 多播技术： RPM 多播报文向所有路由器扩散，直到收到某路由器“剪除请求”后，后续报文才不向该路由器扩散 PIM-SM 稀疏模式，网络上有很多点对点信道 多播技术： CBT 指定一个“多播汇聚点”的路由器 ( 只有一个区段的 CBT 技术 ) lxm 138 可靠多播？ 一般情况下，广播和多播都不采用可靠传输技术 可靠传输技术 ( 按序 ) 需要应答和重传机制 如果要实现可靠多播，主要问题在于： 所有多播成员都向多播源发送 ACK 信息、或请求重传 多播源站无法承受非常多、来自多个子网的 ACK 如果非要实现可靠多播，该怎么办？ 确认聚集器：分散处理 ACK 应答 多子网区域 1 多子网区域 2 多子网区域 3 确认聚集器 缓存多播报文，处理 ACK 及重传 减少 ACK 措施 不使用 ACK ，仅使用 NAK lxm 139 多播小结 IP 的 D 类地址为多播地址 IP 多播要求物理子网至少支持广播通信 点对点的子网除外 子网内的多播群组是动态变化的 多播分为：本地多播和多子网区域多播 IGMP ：供路由器掌握子网的多播群组情况 路由器增加多播报文转发功能 依靠“树”形拓扑形成多播路由 RPF 、 TRPF 、 RPM 、 CBT 、 … 靠分散处理 ACK 来实现可靠多播 lxm 140