多播算法全面解析：从应用层到网络层

### 多播算法全面解析：从应用层到网络层 #### 1. 应用层多播算法分类 多播算法的设计充满了算法挑战。最通用的场景允许每个进程在每一步向任意且动态变化的进程组进行多播，但这种通用性会带来更多开销。因此，实际系统中实现的算法往往在某种程度上更加“集中化”。多播协议可分为以下五类： ##### 1.1 基于通信历史的算法 这类算法利用部分通信历史来保证排序要求。 - **RST 和 KS 算法**：仅提供因果排序，不需要跟踪单独的组，适用于开放组多播。 - **Lamport 算法**：为消息分配标量时间戳，进程只有在知道没有时间戳更低的其他消息可以被多播时才能传递消息。 - **NewTop 协议**：将 Lamport 算法扩展到重叠组，保证总排序和因果排序，使用封闭组配置。 ##### 1.2 基于特权的算法 操作方式如 Figure 6.18(a) 所示，一个令牌在发送者进程之间循环，令牌携带下一个要多播消息的序列号，只有持有令牌的进程才能多播。发送后序列号更新，目的进程按序列号递增顺序传递消息。假设为封闭组，可提供总排序和因果排序，但不允许并发发送事件，扩展性不佳，在大型系统中用途有限，例如 On - Demand 和 Totem 算法。 ##### 1.3 移动排序器算法 操作如 Figure 6.18(b) 所示，最初由 Chang 和 Maxemchuck 提出，Pinwheel 和 RMP 算法是其变体。具体步骤如下： 1. 发送者将消息发送给所有排序器。 2. 排序器之间循环令牌，令牌携带序列号和已分配序列号的消息列表。 3. 排序器收到令牌后，为所有收到但未排序的消息分配序列号，将新排序的消息发送到目的地，插入令牌列表，然后将令牌传递给下一个排序器。 4. 目的进程按序列号递增顺序传递消息，保证总排序。 ##### 1.4 固定排序器算法 操作如 Figure 6.18(c) 所示，是移动排序器算法的简化版本，有一个单一排序器（除非发生故障），本质上是集中化的。传播树方法属于此类，其他算法包括 ISIS 排序器、Amoeba、Phoenix 和 Newtop 的非对称算法。以 Newtop 的非对称算法为例，所有进程维护逻辑时钟，每个组有独立排序器，单播和多播都有时间戳，属于多个组的进程在发送下一个消息前需处理完之前消息对应的所有消息，假设 FIFO 通道可保证总排序。 ##### 1.5 目的协议算法 操作如 Figure 6.18(d) 所示，目的地接收带有有限排序信息的消息，然后相互交换信息来定义顺序。分为两个子类： - 第一子类使用时间戳，如 Lamport 的三相算法。 - 第二子类使用进程间的协议或“共识”协议。 #### 2. 容错组通信的语义 在现实世界中，系统组件可能会在多播操作期间发生故障，多播协议的行为必须遵循明确定义的规范，以确保故障恢复后的明确操作。规范分为常规规范和统一规范两种： |规范类型|有效性|一致性|完整性| | ---- | ---- | ---- | ---- | |常规可靠多播|如果一个正确的进程多播消息 M，那么所有正确的进程最终将传递 M|如果一个正确的进程传递消息 M，那么所有正确的进程最终将传递 M|每个正确的进程最多传递消息 M 一次，并且只有当 M 之前由发送者多播时才传递| |统一可靠多播|如果一个正确的进程多播消息 M，那么所有正确的进程最终将传递 M|如果一个正确或错误的进程传递消息 M，那么所有正确的进程最终将传递 M|每个正确或错误的进程最多传递消息 M 一次，并且只有当 M 之前由发送者多播时才传递| 同时，还定义了 FIFO 顺序、因果顺序和总顺序在多播中的常规和统一规范，统一规范要求即使是错误的进程也不能违反排序属性。 此外，多播消息传递的过度延迟也被视为一种故障。对于有实时约束的应用，消息传递应在多播后的有限时间内完成，可基于全局时间或本