概述

功能

路由选择：决定数据包走怎样的路从出发点到目的地
- 是指确定分组从源到目的地所采取的端到端路径的网络范围处理过程，路由选择发生的时间尺度长得多 (通常为几秒)
- 寻路算法
  - 怎样最近（快）
- 决定了forwarding表（控制如何转发一个数据包）

转发：数据从路由器的一个口进入，从哪个口出去
- 是指将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地动作，转发发生的时间尺度很短

- 时常拥堵需要排队

*（不都有）建立两点之间的连接
- 在开始传输之前，两个节点之间建立起虚拟连接

服务模型

因特网的网络层提供了单一的服务，称为尽力而为服务

期望

单个包传输
- 保证传输成功
- 保证传输时延
- 安全性。网络层能够在源加密所有数据报并在目的地解密这些分组，从而对所有运输层报文段提供机密性
一组包传输
- 有序分组交付（按序到达）
- 保证最小带宽
- 保证数据包之间的到达间隔（连续传输到达）

ip路由

性能评估（交换容量）

交换容量=N*R
- N=接（端）口数目
- R=每个口的速率

路由器工作原理

入端口

- 物理层->链路层->网络层
任务：
- 接收进入的数据包
- 更新ip包头
- 寻找通往目的地址ip的出端口
输入排队，如果到达速率大于转发速率。先将数据缓存起来
- 这种现象叫作输入排队交换机中的线路前部阻塞HOL
- 即在一个输入队列中排队的分组必须等待通过交换结构发送(即使输出端口是空闲的) ，因为它被位于线路前部的另一个分组所阻塞。
&&快速查表寻址：地址聚合（压缩地址，合并相同方向的地址）
- - 根据范围划分端口，+最长前缀匹配
  - &&考试给定地址划分，设计树

switching fabric交换结构

把数据包从input传输到output（交换速率）
结构
memory模式（最简单）
- 交换速率取决于memory的速度，把input的数据保存到memory在导出传输到output
bus总线模式
- 交换速率取决于总线的带宽
- 不同端口竞争bus的使用
Switching via a Mesh（先进）
- 使用算法决定通断，进行资源调度
  - 每条垂直的总线在交叉点与每条水平的总线交叉，交叉点通过交换结构控制器(其逻辑是交换结构自身的一部分)能够在任何时候开启和闭舍。
- 纵横式网络能够并行转发多个分组。纵横式交换机是非阻塞的( nonbloeking) ，即只要没有其他分组当前被转发到该输出端口，转发到输出端口的分组将不会被到达输出端口的分组阻塞。然而，如果来自两个不同输入端口的两个分组其目的地为相同的输出端口，则一个分组必须在输入端等待

出端口

- Packet classification数据包分类
- Buffer management：决定什么时候开始丢包（到达数据量大于发出）
- Scheduler：决定在什么时候传输哪一个数据包
输出排队
- 在向输出链路发送一个分组的时间内，将有 N 个新分组到达该输出端口 (N 个输入端口的每个都到达 1 个) 。因为输出端口在一个单位时间(该分组的传输时间)内仅能传输一个分组，这 N个到达分组必须排队(等待)经输出链路传输

分组调度（环节输出排队）

最简单：fifo（低端路由器使用）
Packet classification
- 多种分类依据决定优先级
Scheduler
- 设置几个不同的队列
- 几种转发先后的决定策略
- 优先级策略
  - 高一级发送完成了低优先级才能发送
  - 非打断式（非抢占式优先权排队），一个数据传输开始，另一个数据就不能打断（即使是高优先级）
- 轮询FQ：公平轮流发送（给与每个flow相同的优先级）
  - WFQ加权轮询

排队

若N个输入、输出端口的速率都是R~lilne~，如果R~switch~比它快N倍，则只会发生轻微的排队

输入排队

当交换速度没有输入的速度快时会在输入出现分组排队
即使是纵横式交换，当有两项发往同一个输出端口时也会发生排队，并且排在正在等待的分组后面的数据包也全部会被阻塞（HOL线路前部阻塞）

输出排队

即使快N倍，但如果输出端口相同，会在输出端口处出现排队

Virtual Circuit 虚拟电路交换

Virtual circuit虚电路

预留资源，保证服务
提供连续传输的服务
有保障的服务，switcher需要预留保存信息

普通传输

提供的是单个数据报的传输服务
终端进行“智慧操作”（错误检擦、恢复等），线路只负责简单的传输信息
不建立连接，没有固定的线路，不保证按顺序到达

虚电路服务建立

Each packet carries VC identifier（包上有特殊标记）
中途的路由器等设备都要保存这个”专线“的转发状态，单独分配一些资源
两端交互，建立路线，途中每一个设备都要同一才能成功

VC服务内容

从起点到终点的路径
VCnumber标识（在一条线路不同区段可能不同，因为有不同的运营商）
在路径中交换机forwarding table中的存储

IP协议

地址

地址层次

物理网络地址
- 用于在单个物理网络内路由PDU（协议数据单元）
因特网地址
- IP地址或因特网地址，用于在网络之间路由PDU
- 每个主机和路由器都有不同的IP地址（可能有多个）
应用地址
- 分配给目标主机的进程标识符

地址范围

全球地址
- 一个交换机可能有多个全球地址
Network attachment address
- 在特定网络范围内每个设备都有不同的地址（如局域网）
端口地址
- 不是网络层，不同主机、路由器可能不同，在单个设备/系统范围外可以相同（如ssh-22）

地址模式

单拨地址
- 发向单个系统/端口
广播地址
- 向一定范围内所有设备发送
多播地址
- 向指定的多个设备发送
任意拨地址
- 可以指定一个地址，但是可以有多个实体使用该地址。当数据包发送到该地址时，它将被路由到最近的实体。（负载均衡）

IP 功能

路由

主机和路由器维护一个路由表
- 指明数据报应被发送到的下一个路由器
- 静态 - 可能包含替代路由
- 动态--对拥堵和错误的灵活反应
路由策略：
- 距离向量、路径向量、连接状态
数据包可以指定经过/不经过一些路由器

数据报文生命长度处理ttl

防止出了问题的报文一直在网络中浪费资源（无线循环）
给数据报文标记生命时长，一但到了时间，就丢弃数据包而不是向前传输
- Hop count：设置可以转发的最大次数

数据包分解和合并

见后

错误控制

当路由器丢弃数据包时会尝试通知发送源（使用ICMP）

流控

路由器限制数据进入的速率
当buffer已经满了时丢弃掉新进入的数据
- 可能会通过ICMP告知发送者

两项基本功能

Send 是由上层调用，用于请求传输数据单元；
Deliver 是通知上层数据单元已经到达。

包头信息

版本version：
- 4bits（ipv4中一定是）
- 记录数据保的ip协议版本
头部长度IHL（internet header length）：
- 4bits
- 记录头部的大小（由于可选内容的存在，头部的长度并不是固定的）
  - 说明头部由多少个32位字组成（一行32bits，即4字节）
  - 可选内容的最大长度为40字节
区分服务differentiated services：
- 8bits（ppt上包含拥塞警告）
- Precedence字段占3位，定义了8个级别,表示优先级；
- Reliability字段占1位，表示正常或高可靠性；
- Delay字段占1位，表示正常或低延迟；
- Throughput字段占1位，表示正常或高吞吐量。
全长total length：
- 16bits
- 定义ip包的总长度（包含头和数据）
标识符 identification：
- 16bits
- 用来唯一标识一个包的所有分片（一个包的所有分片具有相同的id）。因为 IP 包不一定都能按时到达，在重组时需要知道分片所属的 IP 包，标识符字段就是一个 IP 包的 ID 。它一般由全局自增计数器生成，每发一个包，计数器就自动加一。
标志flags：
- 3bits
- 包含几个用于控制和识别分片的标志位如（禁止分片、更多分片）
分片偏移 fragment offset：
- 13bits
- 以8字节为单位
- 记录分片在数据包中的位置
TTL：
- 8bits
协议protocol：
- 8bits
- 指示传输层协议类型（TCP还是UDP...）
头部校验和Header checksum
- 16bits
- 针对头部进行校验（数据部分由tcp/udp等负责处理）
- IP协议头校验和是IP协议头部的一个字段，用于检查IP数据包的完整性。它是由所有16位字（把头部切分为长度为16的片段）中的补码和计算得出的。如果校验和不正确，则路由器将丢弃数据包。在计算过程中，每个路由器都会重新验证并重新计算校验和，并将其设置为0。这样做是为了防止在计算过程中发生溢出。如果发生溢出，则会将最高位添加到最低位，这可能会导致校验和错误。因此，在重新计算校验和时，将其设置为0可以避免这种情况的发生。
- 每次都需要重新计算是因为头部会发生变化，比如每转发一次ttl就会减少一
源地址source adddress：
- 32bits
- ip包发送方的地址
目的地址destination addression：
- 32bits
可选片段options
- 最多40字节
- 若不是32整数bits倍，用padding进行补齐

数据内容

长度是8bits的整数倍
最大长度（头加上内容）是65535字节

数据包分片处理

一个数据包的长度不能超过MTU（途径设备能处理的最大长度）
分解：在host和router都可以进行
- 在host处：确定沿路径的MTU的最小值并进行分段。
- 在router处：当数据包长度超过下一个网络的MTU时，路由器会将其分成更小的片段。
合并：只在host进行
- 在host（目的地）：当数据包到达目的地时，需要将分片的数据包重新组装成原始数据包。
- 在router：路由器上重新组装分片是不可行的，因为分片可能会采用不同的路由（路径不同）。
失败控制
- 合并可能发生错误（比如有子数据包发生了丢失）
- 当一组数据包中第一个到达目的地时开始计时，如果到达时间限制后仍没有全部到达，则丢弃数据。
- 同时也在转发次数过多时丢弃包
- 在进行高层处理之前必须先完成还原！高层头不会被复制，只有ip头会被复制（因此复原后才能正常读取）

合并

需要信息：
- 单元标识符，用于标识源端系统发出的数据报（判断是不是原先属于同一个数据包）
- 地址、目的地址、上层协议
- 数据长度
- 偏移量（确定分片在原包中的位置）（8octets（64bits）为一个单位）
- 其他标志mreflag，确定是不是最后一个分片
总结：
- 当一个IP数据包被分成多个片段时，每个片段都有一个偏移量和长度。在重组时，需要为每个数据包准备足够的缓冲区空间，以便将数据包插入到正确的位置。使用长度和偏移量头字段，使用Moreflags来确定是否到达了最后一个片段，直到整个数据字段被重组。从偏移量为0开始，以moreflags为0结束。

ip地址及分配

IP地址是为了方便路由而引入的，每个物理接口都需要一个单独的地址。IP地址使用点分十进制表示法，其中网络号由美国互联网数字地址分配机构（ARIN）、欧洲互联网数字地址分配中心（RIPE）和亚太网络信息中心（APNIC）进行管理，而主机号则由指定组织内部分配。

子网和子网掩码

解决ip地址不充足的问题
IP地址=网络地址+主机地址
- 网络地址=子网掩码&ip地址，网络地址相同说明处于同一个子网
- 主机号=~子网掩码&ip地址
划分子网：从原来的主机号里面借了几位拿去做子网号了
- 二级地址->三级地址

CIDR无分类域间路由选择

三级地址->二级地址
x.x.x.x/n(n表示网络ID的位数)（即自由划分网络号和主机号的位数分配）
一个组织通常具有相同的前缀，减少了路由器转发表的长度
isp层级

NAT

给内部网络和外部网络分配不同的IP集（不同内部网络可以使用相同的ip）
来解决地址不够使用的问题
在出网关时内部地址会被替换为外部地址
三个网段：10、172、192

优点

安全：隐藏内部ip地址（一个外部地址代表了许多不同的内部地址）
使得一个组织有多个不同ip地址（来分配给不同的设备）
便于切换isp（只需要重新配置网关），不需要修改内部设备的配置

控制性

- 两个节点连接到服务器挂机（从而使得另外一个节点可以找到该节点，帮助建立p2p连接）

ICMP

传递控制、错误消息、ping等
- 不同功能的包在第一行后面的格式不同

ping

生成icmp包发送等待回复
可以记录传输信息：如传输时延等，传输路径（traceout经过哪些路由器）
- traceroute原理：
  - 发送TTL依次递增的数据包（到不同路由器时TTL为0，路由器会返回信息，这样可以知道到每个路由器的时间，以及路由器的地址）
  - 可以用于排除网络在哪里发生了中断，排除错误
  - 路由跟踪
- 查找路径MTU：
  - 发送具有一定大小的数据包，并禁止尽心分片，这样通过对包长度进行二分搜索来确定能通过最大的包大小
  - 不能通过时路由器会返回信息

移动ip

解决设备从一个网络到另一个网络时断开连接的问题
防止上层应用发现网络发生了变化
由于系统移动会切换ip，通过转发伪装还在原来的位置

实现

包含一个移动节点和一个与其通讯的设备
- 由于安全性问题现在往返都使用转发，不用三角模型了

发现discovery

移动节点发现它是否在家庭网络中或外出。如果它在家庭网络中，则不需要采取任何措施。如果它在外面，则需要找到家庭网络的Home Agent。
路由器发送ICMP告知是否有这项服务
移动设备向路由请求服务

注册registration

移动节点向Home Agent注册，并告诉Home Agent它的当前位置。Home Agent将此信息存储在移动节点的注册表中。
步骤：
- 节点向外部网络请求服务
- 外部网络向家庭网络发送请求
- 家庭网络进行答复
- 外部网络把结果返回给节点

隧道tunneling

注册之后就建立起了隧道
家庭代理广播无偿ARP请求，将移动节点的IP地址绑定到家庭代理的MAC地址上
家庭代理接收到发送到移动节点的数据包，并通过IP隧道将数据包转发到外部代理
与移动节点连接的设备认为移动设备仍然从家庭络回复信息，也会继续把包发向移动设备
因此再不改变移动设备ip（通过隧道转发）下维护了连接

ipv6

128bits

包头

长度固定，为40字节
Version (4 bits)：值为6
Traffic Class (8 bits)：QoS
- 为了区分不同的数据流而设置的一种标识。
- 用来区分不同的服务类型，如语音、视频、数据等。
- 在IP协议中，Traffic Class被用来标识数据包的优先级，以便路由器可以根据优先级对数据包进行处理。
- Traffic Class的值可以由源、转发器和接收方进行更改，因此上层协议不应该假定数据包中Traffic Class的值没有被更改
Flow Label (20 bits)：流标签
- flow
  - 网络流是指在网络中，从源节点到汇节点的一组流量，它们共享相同的特征，如路由、资源分配、丢弃要求、计费和安全等。
  - 从主机的角度来看，流是由一个应用程序生成的，并具有相同的传输服务要求。可能包括单个或多个TCP连接。一个应用程序可以生成单个流或多个流。
  - 从路由器的角度来看，流共享影响路由器如何处理这些数据包的属性，例如路由、资源分配、丢弃要求、计费和安全等
- label
  - 一个流被发出地址、目的地址、flow label唯一确定
  - flow label在开始传输前就确定下来
  - 路由器只需要检查flow label结合存储的flow label就知道如何转发包
  - 可以给某些数据得传输更高的优先级
Payload length (16 bits)有效载荷长度：包括所有扩展头以及用户数据(不含ip头)
Next Header（8 bits）：标识下一个头部的类型，扩展或上一层
hop limit(8 bits):与ttl类似
Source / Destination Address (128 bits)

扩展头
- Hop-by-Hop Options（逐跳选项）：需要在每个路由器上进行处理的选项。这些选项可以包含一些需要在数据包传输过程中每一跳都进行处理的信息。
- Routing（路由选项）：源路由选项，用于指定报文的传输路径，即源节点指定报文应该经过的中间节点列表。
- Fragment（分片选项）：源分片选项，用于在发送端进行分片，将较大的IPv6报文切分为较小的分片，以便在网络中传输。
- Authentication（认证选项）：提供对IPv6报文的认证机制，确保报文的完整性和身份验证。
- Encapsulating Security Payload（封装安全载荷选项）：提供对IPv6报文的加密和完整性保护。
- Destination Options（目标选项）：在目标节点处理的选项。这些选项可以包含一些目标节点需要处理的信息。

其他改变

路由器不再负责分片（改为由host负责）
- 如果一个IPv6数据包太大，无法通过下一跳，则会发送一个“数据包太大”错误消息。这是一个ICMPv6消息过滤ICMPv6会导致问题。
广播
- ipv6不再有单独的broadcast地址，而是使用包含所有节点的组进行多拨来实现。
- 广播缺点：
  - 实际上只有一少部分需要接收信息，但是唤醒了所有节点
  - 会产生广播风暴
Neighbor Discovery
- 不使用ARP，使用Neighbor Discovery
  - Uses ICMPv6、Multicast
取消首部校验和

ipv6地址

优势

128位
多播地址的可扩展性
任意广播--传递给一组节点中的一个节点
地址自动配置
在IPv6头和传输层头之间分离出可选的头
大部分不被中间路由器检查
更容易扩展选项
取消校验，进一步减少每个路由器的处理时间
更有效、更强大的移动性机制
更加安全：内置的、强大的IP层加密和认证

融合（ipv4->ipv6）

不是所有的路由器都能同时升级
- 两种建议的方法
  - 双栈 - 一些具有双栈（IPv6、IPv4）的路由器可以在不同格式之间进行转换
  - 隧道--在IPv4数据报中以有效载荷形式传输IPv6 在IPv4路由器之间

路由基础

使用路由表决定到达的包的出口
目标:
- 效率：经过最短（少）的路（交换机）
- 鲁棒性：当线路、交换机负载过高时正常工作
- 稳定性：在一定时间内指的路相对固定而不是快速变化
- 把网络拓扑抽象成有向图
- 同一条路不同方向的代价可能不同（如负载不同）

考虑因素

性能评估
- 多种cost计算方法
决策时间与位置
- 时间
  - 普通：在packet到达路由器后查表转发
  - vc虚电路：在发送时（建立vc）决定线路
- 地点：
  - 中央服务器计算决定
  - 在（发送）源决定
  - （最多用）分布式决定：由每个路由器自己决定
信息来源
- 路由器自身的信息
- 相邻路由器的信息
- 网络中所有路由器的信息
信息到达时间
- 动态路由选择算法
  - 周期性更新（始终发生更新）
  - 网络结构发生重大变化时更新（如故障）
  - 更容易受诸如路由选择循环、路由振荡之类问题的影响
- 固定，不自动更新，由管理员手动进行更新（静态路由选择算法）

路由算法

集中式

如链路状态 (Link State , LS) 算法
用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径
当网络发生重大改变时重新计算并下发

分布式算法

路由器以迭代、分布式的方式计算出最低开销路径，没有节点拥有关于所有网络链路开销的完整信息，仅有直接相连的链路的信息
如距离向 ( Distance-Vector, DV) 算法

flooding

收到数据包后发送到除了发送端口以外的全部端口，最终会有一系列的（相同）数据包到达目的地
用于相对简单的网络
- 可以用于控制平面的信息交互
鲁棒性很高，只要发送节点和目的节点是连通的，就能发送成功
至少一个包经过最短路径到达目的地
- 可以用于建立虚电路
问题：
- 创建了一个包的多个副本
- 容易产生环路问题（使用ttl解决）

random

不需要网络信息
从除了发送端口以外的其他端口随机发送
适用于连通性很强的网络（邻居节点很多）
- 选择是不固定的、具有随机性，这是random的根本特征

adaptive(自适应路由)

需要网络信息
致力于拥塞控制
网络发生变化时路由选择也会发生变化
- 综合考虑到目的地距离和排队情况，使用距离加上排队情况得到权值

两个最小路径算法

dijkstra's单源最短路径

过程：
&&例
复杂度O(n^2^)
问题：可能不稳定，发生震荡
- 在网络中，路由算法的目的是为了找到从源节点到目的节点的最佳路径。在某些情况下，当路由算法选择了某个路径后，该路径的负载会随着时间的推移而增加，导致该路径的成本增加。当其他可用路径的成本变得比当前路径更低时，路由算法将会选择其他路径。然而，这可能会导致原先负载较高的路径成本降低，使得该路径再次成为最佳路径。这种情况下，路由算法又会重新选择该路径，如此循环往复，就导致了路由算法的震荡。
- 解决：
  - 让一些流量留在负载较重的链路上，以平衡流量
  - 应用链接利用率来表示链接的状态。
  - 基于先前值和新的利用率进行平衡。
  - 使用跳数归一化指标来计算链接成本。
  - 就是在路由计算中考虑链路的负载情况，并根据链路的利用率进行平衡，同时使用跳数归一化指标来计算链接成本。这些方法可以降低震荡问题的发生，从而提高路由计算的性能和稳定性。
  - 让路由器不同时运行LS算法进行更新

bellman-ford1

每个节点各自维护一个表
枚举路上的最大节点数目
步骤
&&例
- - 收到其他节点上一阶段的表，更新自己这一阶段的表

cost变化对算法的影响

当网络中的链路成本发生变化时，路由协议需要对此做出响应并重新计算最短路径。当一个节点检测到本地链路成本的变化后，它会更新自己的距离向量，重新计算到其他节点的距离，并将更新的信息通知给它的邻居节点。
当链路成本发生变化时，节点之间的距离信息需要经过多轮传递才能收敛，这可能会导致距离信息的不稳定，进而导致网络性能的下降。
例;
- - t0时刻，节点y检测到本地链路成本的变化，它更新自己的距离向量，然后通知它的邻居节点。
  - 在t1时刻，节点z收到节点y的更新信息，更新自己的距离向量，并向它的邻居节点发送更新信息。
  - 在t2时刻，节点y收到节点z的更新信息，更新自己的距离向量，但是因为节点y的最小成本没有发生变化，所以它不需要向节点z发送任何信息。
  - 这样，网络中的所有节点都能够及时地响应链路成本的变化，并重新计算最短路径，从而保证网络的高效性和稳定性。
- 由于“good news travels fast”， bad news travels slow，信息具有一定滞后性，如节点都将数据涌向空闲的线路，导致空闲的线路变成繁忙的，可能会产生count to infinity问题
  - 遇到路由选择环路 routing loop) ，即为到达x，y通过z路由，z又通过y路由。路由选择坏路就像一个黑洞，即目的地为x的分组在t1时刻到达y或z后，将在这两个节点之间不停地来回反复。直到终算出它经由的路径开销大于 50 为止，此时将(最终)确定它到x的最低开销路径是经过它到x的直接连接，y将经由z路由选择到x。关于链路开销增加的坏消息的确传播得很慢!如果链路开销 c(y，x) 变为 10000 且开销 c(z，x) 9999 时将发生什么样的现象呢?由于这种情况，我们所见的问题有时被称为无穷计数( countto-infini ty )问
  - 因此，路由选择协议通常采用一些措施来避免这种情况的发生，例如拓扑分离、路由毒化等。
  - 毒性逆转（是一种路由协议中常用的策略，用于解决距离向量路由协议中出现的"count to infinity"问题。这种策略的核心思想是，在发生链路成本变化时，如果一个节点要通过它的邻居节点(如 z-w-y-x中y会告诉w无穷大，但不会告诉非直接相连的z)来到达某个目的地，那么该节点会将到达该目的地的距离设置为无穷大（来针对这个邻居节点防止被选择），这样可以防止邻居节点将数据包发回给它。具体来说，当某个节点Z需要通过邻居节点Y到达目的地X时，它会向节点Y发送一条信息，告诉它到达目的地X的距离是无限大。这样一来，如果节点Y想要到达目的地X，它就不会再通过节点Z了，因为节点Y知道它通过节点Z到达目的地X的距离是无限大，不会再选择这条路线。毒性逆转策略能够有效地减少路由环路的出现，从而避免距离向量路由协议中出现的"count to infinity"问题。
  - 例：

算法对比

- Link State算法是计算网络中的最短路径的一种分布式算法。每个节点会将其它节点的信息广播出去，通过收集其它节点的信息来计算最短路径。这种算法的优点是计算结果较快，并且能够自适应网络的变化，但是需要较多的网络带宽和计算资源。
- Distance Vector算法是计算网络中的最短路径的一种分布式算法。每个节点会向其它节点广播自己的距离向量，包括它自己到其他节点的距离以及其他节点到目的节点的距离。通过不断地更新距离向量来计算最短路径。该算法的优点是计算结果较快，但是在存在网络环路的情况下可能会出现问题（无限跳），需要采取一些特殊的处理方式。
信息传递：
- Dijkstra：
  - 节点会将信息flood到所有连接的节点，每个节点都维护整个网络拓朴，根据算法建立自己的routing table
  - 不能处理负权图
- Bellman-Ford：
  - 每个节点维护一个距离向量（关于知道的点）
  - 直接相连的点之间传递距离向量来更新路径和花费
  - 分布式的方法建立路由表
| | DK（全局、集中信息） | BF（分布、局部信息） | | ------------------------------------ | ------------------------------------------------------------ | ---------------------------------------------------------- | | 消息复杂度（节点之间发送的消息数量） | n nodes, e links, O(ne) messages（每个点都需要知道所有边的开销） | Depends on convergence time | | 速度 | O(n2) and quick; May have 震荡 | Slow and depends on changes; May contain routing loops | | 鲁棒性（节点故障） | 节点故障可能会导致错误的直接链路成本广播，但错误范围受到限制。 | 错误节点可能会交换错误的路径成本，错误可能会通过网络传播。 |

代价计算

第一阶段是1969年，ARPANET刚刚创建不久。在这个阶段，输出队列长度被用来定义一个链接的成本，并且使用Bellman-Ford算法进行路由。第二阶段是在1979年，此时ARPANET已经发展成为一个更大规模的网络。在这个阶段，测量延迟被用来定义链接的成本。路由使用Dijkstra算法。
- 延迟=重新传输的时间-数据包到达的时间+传输时间+传播时间
排队模型计算：
- 链路的利用率：（给定时间内链路上传输的数据量与链路的总传输能力之比）
  - ρ = 2(Ts − T)/(Ts − 2T)
    - T是当前测量的延迟
    - Ts是平均数据包长度/链路的传输速率
- 平滑化（leveling）
  - Un = α×ρn+(1–α)×Un–1
  - Un：– leveled link utilization at time n
  - α – constant, now set 0.5

路由协议

问题
- 规模问题：有200 million destinations，目的地太多，不能在一个路由表中存储全部的目的地（不可能在一个路由器中存储整个因特网的拓扑结构！），收敛速度太慢！
- 管理自治问题：因特网是将许多子网连接在一起，子网可能想管理自己内部的路由，对外部隐藏一些内部的信息

层级路由管理

把路由器按照区域（自治域AS）进行划分
- AS：一个路由、网络的集合，它们在互联网上被视为一个单一的单位，由单个组织/isp进行管理
- 在同一个AS中的路由运行相同的路由策略策略
- 每个自治系统在互联网中都有一个唯一的自治系统号码，16/32位
- 在任何两个节点之间至少有一个路由
网关路由：
- 负责路由到AS外目的地的路由器
- 它们运行与其他网关路由器的自治系统间路由协议，并与AS内的路由器运行自治系统内路由协议
- 是一个自治系统与外界通信的关键设备
- 一级之间互联，与center互联
- 二级之间互联，与一级互联
- 大型互联网公司与多个运营商相连，如图中中央部分的AS

内部/外部路由协议

- “Perform inter-AS routing amongst themselves”意味着不同的自治系统之间的路由器之间需要执行路由选择协议，以便它们可以找到最佳的路径将数据包从一个自治系统传递到另一个自治系统。
- 而“Perform intra-AS routing with other routers in their AS”则意味着自治系统内的路由器需要执行路由选择协议，以便它们可以找到在自治系统内传递数据包的最佳路径。这个过程称为自治系统内部路由选择。
IGP (Interior Gateway Protocol): for Intra-AS routing
- IGP用于在AS（自治系统）内部进行路由选择，它在路由器之间传递路由信息，可以专注于性能，而不需要考虑其他AS的路由算法和表格（可能不同）。
- RIP是一种距离向量协议，用于测量距离并选择最短路径。
- OSPF是一种链路状态协议，它使用链路状态数据库中存储的拓扑信息来计算最短路径。
- IGRP是思科公司专有的自治系统内部路由协议。
EGP (Exterior Gateway Protocol): for Inter-AS routing
- EGP用于在AS之间进行路由选择，因为路由器需要了解其AS之外的网络情况，它支持关于可达性的摘要信息。在这种情况下，策略可能会优先于性能。（要兼容）
- BGP是一种边界网关协议，用于在不同自治系统之间传输路由信息。
EGP要求的特性：
- 不同的AS可能会使用不同的指标和有不同的限制；
  - 最关心的是通过了哪些AS（isp）
- 并不是所有子网都需要被所有路由器知道；
- 距离向量协议无法提供有关经过的AS的信息；
- 链路状态协议将链路状态信息泛洪到所有路由器中不可控
- 所以：链路状态协议（Link-state protocol）和距离向量协议（Distance-vector protocol）。它们被用于AS内的路由，但是对于连接不同AS之间的路由，它们并不适用。
EGP协议：
- 让每个网关路由器向邻居广播到达目的地的完整路径。每个信息块列出了在路径上经过的所有自治系统。这样，网关路由器可以执行策略路由，避免经过特定的自治系统，尽可能减少经过的自治系统数量。此外，该协议还可以考虑其他因素，如链路速度、网络容量、易拥塞程度、总体运营质量和安全性等。

路由协议

正在使用：

RIP

使用dv
即通过跳数（最大15跳）来衡量网络中不同节点之间的距离
- 后来使用队列长度代替hop来衡量距离
每隔30秒，路由器会向相邻的节点发送一条RIP更新消息，其中包含了距离向量信息。
如果在180秒内未能接收到更新消息，则说明与相邻节点的连接已经断开。
每个更新广告中最多可以列出25个目标网络。这些广告会通过UDP数据包进行发送。
策略上与bf算法类似
例:

OSPF

替代了RIP
使用Link-State routing algorithm替代dv
- 在该算法中，每个路由器都会维护与相邻路由器之间的链路状态列表，并定期向整个自治系统广播状态信息（即广告），以便其他路由器更新其路由表。
- 这个广播过程称为泛洪（所有其他路由器），每10秒进行一次。LS算法使用一个成本度量值来评估每条链路的开销，这个度量值通常是链路带宽、延迟等因素的综合。
- 广告消息直接通过IP协议传输，而不是UDP协议。
- 每个节点都存储了一个有向图，用于描述该节点的相邻节点和它们之间的连接方式。
- 节点分为路由器节点和网络节点（过渡节点和Stub节点）。边分为路由器之间的边和路由器与网络之间的边。为了计算出到每个目的地的最短路径，使用了Dijkstra算法，确定spf（以自身为根节点到所有子网的最短路径树）。
- 每条链路的具体开销是由管理员设定的
- 目的地：Networks（N）, hosts and BGP(H) routers(R)
操作过程：
- &&网络中的每个路由器都计算出到所有目的地的最短路径树（SPF tree），并使用这些路径来转发数据包(使用dj单源最短路径算法)
  - SPF树可以通过使用路由协议中的链路状态信息来计算。在OSPF中，每个路由器通过发送链路状态广告（LSA）来描述与其相邻的所有链接。这些LSA被所有OSPF路由器接收并用于计算SPF树。在RIP中，每个路由器发送其已知的路由表，其他路由器将它们的路由表合并到自己的路由表中，然后使用这些信息来计算SPF树。
  - 一旦SPF树被计算出来，每个路由器都可以使用该树来选择到目标的最佳路径，这是通过选择SPF树中的最短路径来完成的。当一个路由器决定了它的最佳路径，它会将该路径作为下一跳来发送数据包。
优势：
- 安全性：OSPF使用身份验证来防止恶意入侵。
- 允许多条相同代价的路径：OSPF支持在相同代价的多条路径之间进行负载平衡。
- 支持不同类型的服务类型（TOS）：对于每个链路，可以为不同的服务类型设置多个代价指标。例如，可以将卫星链路的代价设置为“低”，以获得最佳的尝试，而将其设置为“高”，以获得实时传输。
- 集成的单播和多播支持：OSPF集成了单播和多播的支持。
- 大型域中的分层OSPF：在大型域中，可以使用分层OSPF来减少网络复杂性。层次化的配置多个区域。
区域划分Hierarchical OSPF-提高可扩展性：
- 每个区域由一个32位的区域ID进行标识，该区域内的路由器只知道该区域内的完整拓扑信息，从而限制了链路状态信息向其他区域的洪泛。
- 区域边界路由器可以对其他区域的信息进行汇总，从而实现跨区域的路由信息传播。
- 每个区域都必须与骨干区域（仅有一个）（0.0.0.0）相连（用于连通其他下层区域），以便在区域之间传播路由信息。通过分级的方式，有效地减少了 OSPF 网络中链路状态信息的洪泛，从而提高了网络的可扩展性。
- 路由器分类：
  - Internal router 是指只有连接到同一区域内的网络的路由器，它们只知道区域内的拓扑信息。
  - Area border router 是指连接不同 OSPF 区域的路由器，它们会汇总所连接区域内的路由信息，将其广播到其他区域的 Area border router 中。
    - 是位于两个或多个区域边界上的路由器，它连接不同的区域并负责交换LSA信息。
  - Backbone router 是指连接 OSPF 各个区域的骨干路由器，它们会将所连接区域内的路由信息汇总，然后再将其广播到各个 Area border router 中。
    - 是负责运行在骨干区域的路由器。BBR处理在骨干区域内的所有路由信息，负责与其他骨干区域路由器之间的路由交换。
  - AS boundary router 是指 BGP 中的路由器，主要是负责将 OSPF 内部的路由信息发送到其他 AS（虽然ospf进行了分区，但这还是在同一个AS中！）中。
广告分类：
- Router Link Advertisement（路由器链路广告）：由所有OSPF路由器生成，包含了在该区域内所有路由器的链路状态信息，仅在该区域内部进行广播。
- Network Link Advertisement（网络链路广告）：由指定路由器（DR）生成，列出了连接到该网络的所有路由器的ID，仅在该区域内部进行广播。
- Summary Link Advertisement（汇总链路广告）：由区域边界路由器（ABR）生成，概括了来自其他区域的路由信息，用于跨区域的路由，仅在本区域内和相邻的区域进行广播。
- AS External Link Advertisement（AS外部链路广告）：由AS边界路由器（ASBR）生成，描述了到达OSPF网络之外目的地的路由，被洪泛到所有的区域。

BGP

AS希望自由的自主选择路由（传输过程）、自主性、隐私性(保密自身的信息，如拓扑结构)
&&AS之间的关系
- customer\provider(给钱)，peer（互助型，不互相给钱）
- 差距三倍以内认为几乎相等，才能构建peer
- peer的目的：省钱
- 前提：peer双方都能从中受益
- 物理上通，商业上不一定通，这是商业策略的结果
一个由多个自治系统（AS）组成的网络，每个AS都有一个唯一的标识符，并使用BGP协议进行自治域间路由。在网络拓扑图中，IP前缀被分配给目标，而AS被表示为节点，而链接则表示物理链接和业务关系。由于AS的内部是隐藏的，因此网络拓扑图中只显示自治域间的路由信息。
基本idea：
- An AS advertises (“exports”) its best routes to one or more IP prefixe
  - 这个广播是有选择的，选择广播哪些，不广播哪些
- Each AS selects the “best” route it hears advertised for a prefix
  - 其他节点对路径的选择也是自主选择

BGP与DV

它不需要将整个网络的拓扑信息集中在一起，而是在每个目的地处计算出最佳路径。这种方法可以使网络更快地收敛，并且不需要大量的计算和存储资源。
区别：
- 不一定选择最短路径：
  - 会根据策略选择最好的路径，而不是最短的路径
- BGP是一种路径矢量（Path-Vector）路由协议，而DV是一种距离向量（Distance-Vector）路由协议
  - 路径矢量路由协议的关键思想是广告整个路径，这样每个路由器都可以了解整个网络的拓扑结构，并可以通过该信息做出更好的路由决策。距离向量路由协议的关键思想是发送到达目的地的距离度量值，这样每个路由器可以通过这些度量值选择最短路径来转发数据包。
  - 除了距离外还想知道更多的信息
  - 优点：
    - 可以避免回路
    - 基于整个路径的灵活有利的策略
- 有选择的路径广告
  - 出于各种原因，as可能选择不向某个目的地广告某条路由，因此即使图形物理上已连接，可达性也不能得到保证。
- BGP可以将一组具有相同前缀的路由汇总为一个路由
  - 减少了需要交换的路由数量，提高了路由交换的效率和可扩展性。

BGP协议细节

BGP协议是由AS中的边界路径来使用的
- 规定了：与其他BGP“speaker”交换的消息，消息类型（例如路由广告，更新），消息语法，以及如何处理这些消息。
BGP分类：
- eBGP：
  - eBGP是指处于不同自治系统（AS）之间的边界路由器之间的BGP会话，其目的是学习到外部目的地的路由信息，以便最优地转发数据包到不同的AS中。
- iBGP：
  - iBGP是指处于同一个自治系统中的边界路由器和其他路由器之间的BGP会话，其目的是在AS内部分发外部学习到的路由信息，以便实现内部路由的可达性。
  - 在一个自治域内部，如果有多个边界路由器与不同的外部AS相连，这些路由器之间必须使用iBGP协议来分发学习到的外部路由信息，以确保自治域内部的所有路由器都具有完整的路由信息。iBGP协议确保自治域内部所有路由器之间的路由信息同步，并且避免出现路由环路等问题。
- IGP：
  - IGP是指“Interior Gateway Protocol”，即自治域内部的路由协议，如OSPF和RIP等，其目的是为自治域内部的所有路由器提供内部可达性，使数据包能够在自治域内部进行正确的路由选择和传输。
- 总结：
  - 首先，自治域内的边界路由器会使用eBGP协议来学习到外部AS中的路由信息，以便知道如何将数据包发送到外部目的地。然后，边界路由器之间使用iBGP协议来分发和同步学习到的外部路由信息，以确保自治域内的所有路由器都具有完整的路由信息。
  - 最后，自治域内的所有路由器都使用IGP协议（如OSPF或RIP）来确定到达目的地的最短路径，即通过自治域内部的网络设备来确定到达目的地的下一跳路由器，并将数据包发送到该下一跳路由器。这个过程会一步步地进行，直到数据包到达自治域的边界路由器，然后通过eBGP协议将数据包发送到目的地的外部AS中。

BGP的实现

路由属性:
- 路由是通过属性来描述的。这些属性用于路由的选择和导出决策，即帮助路由器选择应该发送到其邻居的路由，以及如何向外传播路由。
- BGP中的路由属性可以分为本地属性和全局属性。本地属性是仅在本地AS中使用的属性，不包括在路由公告中。全局属性则会随着eBGP路由公告一起传播。
- 具体属性：
  - ASPATH：
    - 是全局属性，在BGP路由公告中被携带，并以反向顺序列出所有经过的AS。
    - 可以防止环路：如果一台路由器在路径列表中看到包含自己的AS，将拒绝该通告
    - 使得目标BGP路由器可以了解到路由是如何到达它们的，从而进行合理的路由选择和策略制定。
  - LOCAL PREF：
    - LOCAL_PREF属性是本地属性，仅在iBGP消息中传递，不会被传播到其他AS中。是要发送信息的as内部的属性，用于指定想要的路由路径（即经过哪些AS）。
    - 在BGP路由选择中，LOCAL_PREF属性通常是第一优先级。当有多条AS路径到达同一目的地时，BGP路由器将优先选择LOCAL_PREF值最高的路径。
  - MED：
    - 用于在存在多个出口的情况下选择到达目的地的最优路径。
      - 是转发的AS所宣布的，即以何路径从一个AS到另一个AS（当存在多条线路时）
    - 指定了前缀到达该出口的距离，这有助于选择到达目的地的最短路径。
    - MED属性的值由AS宣布前缀的路由器设置，它是一个非强制性属性。当一个AS有多个出口时，MED属性可以告诉其他AS它希望通过哪个出口传递数据，也可以用于将流量分布到多个链接上。
  - IGP cost：
    - 每个路由器根据内部域协议中的路径成本选择最近的出口点。IGP cost属性携带在BGP更新中，用于影响BGP的路径选择。当存在多个出口点以到达目标时，路由器选择距离目标最近的出口点，即IGP成本最小的出口点。
    - 它是通过在自治系统内使用内部网关协议（IGP）来计算的，因此在整个自治系统内是可见的。每个路由器都使用IGP成本选择最近的出口点来路由数据包。因此，IGP成本对于自治系统内的所有路由器都是相同的。
信息传递：
- Open消息用于在两个BGP对等体之间建立BGP会话，并且在该会话上使用TCP协议进行数据传输。
- Notification消息用于报告不寻常的状况，如错误或异常情况，以便另一端的BGP对等体可以采取相应的措施。
- Update消息用于向邻居通知新的路由信息或者已经失效的路由信息，以便邻居可以更新其路由表。
  - BGP协议中的路由更新消息包括一个IP前缀和一组路由属性。路由属性描述了路由的各种属性和特征，例如路由的度量值、来源、下一跳等。\
  - 分类：
    - Announcement指的是新路由或对现有路由的更改，这些更新将被发送到BGP邻居中。
    - Withdrawal消息指的是移除已经不存在的路由，也会被发送给邻居，以便邻居可以更新其路由表并删除已经不可达的路由。
- Keep-alive消息用于向邻居发送一个空的BGP消息，以便让邻居知道连接仍然有效。这有助于避免连接因长时间不活动而被认为是失效的情况。
*路径决策过程
- AS Path：BGP路由器会检查AS Path属性并选择具有最短AS Path的路径，因为这通常意味着这是最直接的路径。
- LOCAL_PREF：如果AS Path相同，则BGP路由器将比较LOCAL_PREF属性，并选择具有最高LOCAL_PREF值的路径。
- MED：如果两个路径来自同一个AS，并且AS Path和LOCAL_PREF相同，则BGP路由器将比较MED属性，并选择具有最低MED值的路径。
- IGP cost：如果上述三个属性都相同，则BGP路由器将使用IGP cost属性来决定路由路径。它将选择到最近egress点的路径。

ip多播

分类：
多播可以发一份（一个操作）到达不同目的地，效率高：
应用：
- 电视广播
- 电话会议
- 数据库应用，如一个数据库同时为多个模型的训练提供信息
- 分布式计算
定义：
- multicast group：接收组的集合
- source：发送者
- receiver：接收者
服务模型
- 当一个主机加入一个组播组时，它会通知本地路由器，告诉路由器它要接收该组的数据包。路由器会记录哪些主机已经加入了哪些组播组，并在收到组播数据包时，将数据包转发给那些已经加入了该组的主机。
多播地址
- ipv4使用D类ip表示，一个地址表示一组（多个）目的ip地址
- ipv6: 8 bit prefix, 4 bit flags, 4 bit scope, 112 bit group identifier
地址转换（IP multicast address and multicast MAC address)
- 组播mac地址的高24bit为0x01005e，mac 地址的低23bit为组播ip地址的低23bit。
- 通过将组播IP地址的低23位与固定的MAC地址前缀进行组合，就可以得到对应的组播MAC地址。

IGMP组播

建立

本地主机可以通知多播路由器告知要加入某个组
多播路由器相互交互，构建多播树
过程：
- 主机发送信息加入、退订一个多播组；离开不一定立刻完成（如轮询时发现要退出）
- 路由器周期性的询问主机都是否还要在某个组里（不回答就是退出）
两个特殊地址：
- 224.0.0.1: all multicast groups on subnet
- 224.0.0.2: all routers on subnet
每个子网中只需要选出一个路由器来作为querier（询问者）
- Querier periodically sends a Membership Query message to 224.0.0.1 with TTL = 1
- 回复时，每个节点给与每个组一个随机的发送时延（0-10s），计时结束后发送，如果一个节点发现别的节点发送了，则不再重复发送，这样可以减少开销
询问分类：
- “General query”是对所有组播组的查询
- “Group-specific query”是对特定组播组的查询
- “Group-and-source specific query”是对特定组播组和源的查询

版本

IGMP v1：
- 每次都广播询问所有组的订阅情况
- 主机只发送要加入的组，通过不回复来表示离开某个组
IGMP v2：
- 可以询问单个组的使用情况
- 允许主动发送消息主动离开组
问题：（1&2）
- 发送源的位置是未知的，每一个主机都可发送信息到任何一个组
- 多播树的建立存在问题
- 多播的垃圾邮件问题
- 寻找全球唯一的组播地址很困难
IGMP v3
- 允许接收主机设定一个源列表（只接受来自列表中的源的信息），其他的会在路由器丢弃
- 允许主机阻止来自来源的发送不需要的流量数据包。

表头

询问

- Type (8 bits): 数据包类型，0x11 表示查询数据包。
- Max Response Time (8 bits): 接收方在发送响应前的最长（随机）等待时间，以 1/10 秒为单位。
- Checksum (16 bits): 数据包的校验和，采用和 IPv4 相同的算法。
- Group Address (32 bits): 查询的多播组地址，若为通用查询，则为 0。
- S Flag (1 bit): 是否抑制接收方常规的定时器更新操作，1 表示抑制。
- QRV (querier's robustness variable) (3 bits): 发送查询的路由器鲁棒性变量，用于确定重传次数以确保报告不会被漏掉。
- QQIC (querier's query interval code) (8 bits): 查询间隔代码，指定发送多个查询的时间间隔。路由器可以采用最近收到的 QI 值。
- Number of Sources (16 bits): 源地址的数量。
- Source addresses: 源地址，每个地址使用 32 位无符号整数表示。如果有多个源，则会有多个地址字段。

- Type (8 bits): 报告消息类型，0x22表示这是一个IGMP报告消息。
- Checksum (16 bits): 检验和，用于检验IGMP报告消息在传输过程中是否出现错误。
- Number of Group Records: 组记录的数量，即这个报告消息涉及到的组的数量。
- Group Records: 每个组记录对应一个组
  - Record Type (8 bits): 记录类型，有三种：0x01表示该组仅仅是一个模式匹配，0x02表示该组是属于特定主机的，0x03表示该组是共享的。
  - Aux Data Len (8 bits): 辅助数据长度，表示附加到此记录中的数据的长度（单位：字节）。
  - Number of Sources (16 bits): 源的数量，即加入此组的主机数量。
  - Multicast Address (32 bits): 多播地址，标识一个特定的组。
  - Source Addresses: 源地址列表，表示加入此组的所有主机的IP地址列表。如果Number of Sources为0，则该字段为空。
ipv6中的多播
- igmp被整合到了icmpv6
  - 包含icmpv4和idmp的全部功能
- 包括组成员查询和组成员报告消息，这些功能与IGMPv3一样被使用。

多播路由

多播树

多播树：构成最小费用树连接所有节点（发送者、接收者）
路由器要知道多播组的存在；知道哪些端口连接着目标组（中的节点）；
分类：
- 共享树：（共享一个生成树）
- 每个（发送至）源构建不同的树：

构建

确定多播数据包应该发送到哪个接口
每类树都有两种构建方法
Shortest Path Trees
- 使用dijkstra算法，找到从源到全部接收者的最短路径树
- used with OSPF
&&Reverse Path Forwarding
- Used with RIP
- 建立在路由器知道到每一个发送者（节点）的最短路径的前提上
- 基本思想是：当一个路由器收到一个多播数据包时，它将检查其路由表中是否存在最佳路径来到达数据包的源地址。如果该路径存在，则认为数据包是从最短路径到达该路由器的，并将数据包转发到其出站接口（泛洪到所有其他接口）。否则，该路由器将丢弃该数据包。
- 通过构建反向树来确定多播数据包的最佳路径。这个反向树的构建是基于每个路由器维护的路由表信息，路由表中记录了反向路径最短的前一跳路由器和相应的出接口信息。如果网络中存在链路不对称的情况，反向树的构建可能会出现问题。在这种情况下，如果选择了错误的前一跳路由器，可能会导致反向树的路径不是最优的，从而影响数据包的传输效率和可靠性。
- 可能会包含不含加入多播组的节点（即数据不需要发送到该多播组）路由器可以向上游发送“prune”消息，告诉它的上游路由器它已经没有任何下游组成员需要接收这些数据报，可以停止向它转发了。这样可以避免不必要的数据传输和浪费网络资源。
Steiner Tree
- 最小化成本的树形连接所有具有连接组成员的路由器的算法。虽然问题是NP完全的，但有很好的启发式方法来解决。然而，在实践中，该算法不被广泛采用，主要因为计算复杂度很高，并且需要对整个网络进行信息收集。此外，该算法是整体式的，需要每当路由器需要加入/离开时重新运行。
Center-based Trees
- 将网络中的一个路由器标识为中心节点，并由此构建树形结构。
- 其他路由器可以通过向中心节点发送单播加入消息来加入该树形结构，加入消息将由中间路由器进行处理，并向中心节点转发。当加入消息到达中心节点时，加入路径成为新的树枝，该路径成为加入节点和中心节点之间的分支。
- - R6为中心节点，其他路由器向R6发送信息，发送的路径构成生成树

多播路由协议

DVMRP

一种基于RIP的多播路由协议，使用dv
Reverse Path Forwarding方法构建源基树source-based tree。
该协议是软状态的，DVMRP路由器会定期（1分钟）"忘记"剪枝的分支，多播数据会再次通过未剪枝的分支传输。下游路由器可以重新剪枝，否则将继续接收数据。
- 修剪是指从路由器的多播转发树中删除特定分支的操作。当某个分支上没有接收者或者接收者已经明确要求不接收该组的数据时，路由器会将该分支标记为修剪状态。这样，多播数据将不会被发送到这些被修剪的分支上，从而减少了网络流量和资源消耗。
- 然而，为了确保及时传递多播数据，DVMRP路由器会周期性地（每分钟）"忘记"分支被修剪的信息。这意味着即使某个分支之前被标记为修剪状态，DVMRP路由器也会在一定时间后重新考虑是否发送多播数据到该分支，以确保数据能够及时到达接收者。
然而，DVMRP协议的缺点是在规模化网络中不适用，因为所有路由器都需要全局了解所有多播组和其源的信息。

MOSPF

MOSPF是指“多播扩展开放式最短路径优先协议”（Multicast Extensions to OSPF），基于ospf
MOSPF是一种基于链路状态的路由协议，可以为每个多播数据报计算一棵相同的最短路径树，从而保证每个目的组成员都能够接收到多播数据报，且数据报从源到目的组成员的传输路径是唯一的。不过，MOSPF并没有得到广泛的应用。

PIM

依赖于任何特定的底层单播路由算法，可以与任何单播路由协议一起使用。
PIM 协议有两种模式，一种是稀疏模式，适用于组成员分散的情况，采用中心点的方法建立组播树。另一种是密集模式，适用于组成员比较密集的情况，采用源点树（source-based tree）和反向路径转发（reverse path forwarding）的方式建立组播树，与 DVMRP 协议类似。
- 在稀疏模式下，PIM 协议使用中心点方法建立组播树，这个中心点可以是任意一个路由器，其他路由器通过向中心点发送加入消息来加入组播。组成员比较分散，带宽有限。
- 在密集模式下，PIM 协议使用源点树和反向路径转发建立组播树，与 DVMRP 协议类似。组成员比较密集，带宽相对较充足。

应用层多播

多播它并没有被广泛采用。仅仅谨慎使用，例如仅在局域网或校园网内使用，很少在广域网上使用。它的失败原因有很多，包括路由协议的可扩展性、难以管理、难以实现TCP等效性、难以让应用程序在没有广泛部署的情况下使用IP组播、难以让路由器供应商支持功能，并且难以让ISP配置路由器以启用功能。这些问题导致IP组播在实际应用中存在困难和挑战。因此，我们需要探索其他方法来实现高效的多点传递，而无需IP层的支持。
应用层组播通过在应用层复制和缓存数据包而不是在路由器上复制数据包来避免IP组播的部署问题。应用层组播无须对路由器作任何修改,因此在 Internet 上非常容易部署
应用层多播只是最终要将信息发送到多个目的节点，而不关心途径路径
- 也不一定是从一个源发送到所有目的节点，可能经过多个端进行传递。
- 组播是通过分段单播连接实现的。很明显，终端主机而不是路由器负责复制和转发组播数据包，这样ALM的生成树在最终主机之间形成了一个仅由终端主机和单播连接组成的叠加拓扑。
对比：
- | | 应用层多播 | ip多播 | | -------- | ------------------------------------------------------------ | ------------------------------------------------------------ | | 原理 | 应用层多播是在网络层IP单播的基础上实现的。应用层多播是基于点对多点通信的思想，即将源节点发送的数据复制到多个目标节点上，从而实现多点传输。不依赖于网络层的多播支持。 | IP多播是在IP协议层实现的，依赖于底层网络（设备）的多播支持 | | 使用场景 | 点对点应用，例如P2P文件共享和在线游戏。 | IP多播通常用于广播媒体流和网络电话等多媒体应用 | | | | |
优缺点：
- 优点：
  - 不需要底层网络支持IP多播功能，因此可以在任何网络环境中使用。
  - 可以更容易地控制多播组成员，以便更好地保护网络安全。
  - 可以更灵活地处理不同的应用需求，如实时视频和音频流等。
- 缺点：
  - 由于没有底层支持，因此需要更多的计算和网络带宽资源。（效率低、延迟高）
  - 需要专门的服务器来协调多播组成员，这可能会导致单点故障和瓶颈问题。
  - 应用层多播不如IP多播标准化和普及，因此不如IP多播适用于大规模网络部署。