📖 多播路由选择协议

🎯 课程摘要：多播路由选择协议的核心任务是在多播路由器之间为每个多播组建立多播转发树。构建多播转发树有基于源的树（SBT）和组共享树两类方法，前者以源点为根利用反向路径广播（RPB）和剪枝算法构建，后者以核心路由器为根通过加入报文嫁接生成。因特网上 IP 多播尚未大规模应用，但其算法思想已延伸至应用层多播。

📝 详细笔记

1. 多播路由选择协议概述

  • 概念定义：多播路由选择协议的主要任务是在多播路由器之间，为每个多播组建立一个多播转发树。
  • 原理解析：多播转发树连接多播源和所有拥有该多播组成员的路由器，使多播分组能沿树形路径高效送达各成员，避免无谓的重复复制。
  • 构建方法：目前有以下两种方法构建多播转发树
    • 基于源的树（Source-Based Tree, SBT）多播路由选择
    • 组共享树多播路由选择

2. 基于源树的多播路由选择

  • 典型算法：反向路径多播（Reverse Path Multicast, RPM）算法，包含以下两个步骤：
    1. 利用反向路径广播（Reverse Path Broadcast, RPB）算法建立一个广播转发树。
    2. 利用剪枝算法剪除广播转发树中的下游非成员路由器，获得一个多播转发树。

2.1 洪泛法与环路问题

  • 洪泛法：路由器收到广播分组后复制并向所有下游邻居转发，可将分组副本传送到网络中所有节点。
  • ⚠️ 环路问题：若网络中存在环路，使用洪泛法会产生严重问题——广播分组的一个或多个副本将在环路中永久兜圈，无休止的复制和转发会占满网络带宽。

2.2 反向路径广播（RPB）算法

  • 作用：利用 RPB 算法生成的广播转发树不存在环路，可避免广播分组在环路中兜圈。
  • 算法要点：
    • 每台路由器收到广播分组时，先检查该分组是否从源点经最短路径传送过来。
    • 若是，则从除接收接口外的所有其他接口转发；否则丢弃。
    • 若存在多条等长最短路径，只选取一条：取邻居路由器 IP 地址最小的那条。
    • "反向路径"的含义：计算最短路径时把源点当作终点。
  • 示例（假设各路径距离为 1）：
    • 源点向 R1 发送广播分组，R1 向 R2、R3 转发。
    • R2 发现 R1 在自己到源点的最短路径上，向 R3、R4 转发；R3 同理向 R2、R5 转发。
    • R2 发现 R3 不在自己到源点的最短路径上，丢弃 R3 转发的分组（R3 也丢弃 R2 的）。
    • R4 发现 R2 在最短路径上，向 R5、R6、R7 转发。
    • R7 到源点有两条最短路径（经 R4 或经 R5-R3-R1），因 R4 的 IP 较小，只转发 R4 的分组、丢弃 R5 的。
  • ⚠️ 重点：按广播转发树转发，既避免兜圈，每个路由器也不会收到重复分组。

2.3 剪枝与嫁接

  • 剪枝：RPB 只实现了广播，要实现真正多播还需剪除非成员节点。例如 R8 通过 IGMP 发现自己没有多播组成员且无下游路由器（叶子节点），则向上游 R5 发送剪枝报文，将自己从多播转发树上剪除。
  • 嫁接：若被剪枝的路由器又通过 IGMP 发现新的多播组成员，则向上游发送嫁接报文，重新加入多播转发树。
  • ⚠️ 重点：即便某路由器（如 R2）通过 IGMP 发现自己没有多播组成员，也需保留在树上，以确保多播转发树的连通性。

3. 组共享树多播路由选择

  • 算法基础：采用基于核心的分布式生成树算法建立共享树。
  • 原理解析：
    • 在每个多播组中指定一个核心路由器，以它为根建立一棵连接该多播组所有成员路由器的生成树，作为多播转发树。
    • 除核心路由器外的成员路由器，都向核心路由器单播加入报文。
    • 加入报文沿单播路径朝核心路由器转发，直到到达已属于该多播生成树的某节点或核心路由器本身。
    • 加入报文所经路径确定了一条从边缘节点到核心路由器的分支，该分支被嫁接到现有转发树上。
  • 示例：设 R5 为核心路由器
    • R4 向 R5 单播加入报文，链路 R4-R5 成为初始生成树。
    • R3 经 R6 向 R5 单播加入报文，路径 R3-R6-R5 被嫁接。
    • R2 向 R5 直接单播加入报文，链路 R2-R5 被嫁接。
    • R7 向 R5 单播加入报文，路径经 R6，因 R6 已在树上，链路 R7-R6 被嫁接。
    • R1 因无该组成员，不发送加入报文，故不在树上。
  • 源主机发送多播分组：当 R1（源）收到源主机发来的多播分组时，将其封装到目的地址为核心路由器 R5 的单播分组中发给 R5；R5 解封后在多播转发树上洪泛转发。
  • ⚠️ 对比：基于源树为每个源各建一棵树；组共享树则全组共享一棵以核心路由器为根的树。

4. 因特网的多播路由选择协议

  • 现状：目前还没有在整个因特网范围使用的多播路由选择协议，仅有建议使用的协议。
  • 应用局限：尽管 IETF 推动全球多播主干网建设，但 IP 多播至今未大规模应用，主因是改变已成功运行且广泛部署的网络层协议极其困难。
  • 实际应用：IP 多播主要应用于局部园区网络、专用网络或虚拟专用网中。
  • 延伸——应用层多播：P2P 技术推动了应用层多播发展，许多视频流和内容分发公司通过构建自己的应用层多播覆盖网络分发内容，但上述多播路由算法思想在应用层多播中依然适用。

💡 核心总结

  • 多播路由选择协议的核心是构建多播转发树，分为基于源的树（SBT）和组共享树两种。
  • RPM 算法 = RPB 建广播转发树 + 剪枝得多播转发树；RPB 通过"反向最短路径"检查避免环路。
  • 组共享树以核心路由器为根，成员通过单播加入报文逐个嫁接分支。
  • 因特网范围的多播路由协议尚未普及，算法思想已在应用层多播中延续。

❓ 课后思考 / 经典考题

  1. 简述反向路径广播（RPB）算法的工作原理，并说明它如何避免广播分组在环路中兜圈。
  2. RPM 算法包含哪两个步骤？剪枝报文和嫁接报文分别在什么情况下发送？
  3. 比较基于源树的多播路由选择与组共享树多播路由选择的异同。
  4. 为什么即便某路由器没有多播组成员，也需保留在多播转发树上？
  5. 为什么 IP 多播至今未在因特网范围大规模应用？其算法思想在何处得到延续？
最近更新:
Contributors: yangwenguang