物联网基础：路由算法与性能指标解析

# 物联网基础：路由算法与性能指标解析 ## 1. 最短路径路由——迪杰斯特拉算法 在网络中，路由器可看作节点，连接节点的边代表通信链路，边上的权重则表示诸如距离、延迟、成本和带宽等指标。我们的目标是确定从源节点到目标节点的最短路径或最小指标路径。 迪杰斯特拉算法用于计算无向图中的最短路径。该算法由荷兰人于1959年开发，在无向图中，从节点A到节点B和从节点B到节点A的最短路径是相同的。初始时，由于路径未知，各节点被赋予无穷大的权重。若找到比之前更好的路径，路径将被更新。路径上的权重可以是临时的或永久的，一旦基于最小指标标准确定为永久权重，则不再改变。 ### 1.1 迪杰斯特拉算法示例 以图1.13的拓扑结构为例，我们从源节点A开始，逐步找到下一个最近的节点。在每次迭代中，通过上一次迭代的新节点找到最小成本路径，目标是确定从源节点A到拓扑中所有其他节点的最短路径。 | 步骤 | 节点B | 节点C | 节点D | 节点E | | --- | --- | --- | --- | --- | | 初始 | 2 via A | 5 via A | ∞ | ∞ | | 经过节点B | 2 via A | 5 via A | 6 via B | 9 via B | | 经过节点C | 2 via A | 5 via A | 6 via B | 9 via B | | 经过节点D | 2 via A | 5 via A | 6 via B | 8 via D | 具体计算过程如下： - 初始时，从节点A到节点A的成本为0，到节点B和节点C的成本分别为2和5，节点D和节点E不可达，初始权重设为无穷大。 - 第一步，选择通过节点A到达节点B的成本2，因为这是最小成本。然后通过节点B寻找最短路径，到节点C没有路径，沿用第一步的记录；到节点D的成本为第一步到节点B的成本2加上从节点B到节点D的成本4，即6；到节点E的成本为2 + 7 = 9。 - 第二步，选择通过节点A到达节点C的成本5。通过节点C到节点D的成本为5 + 3 = 8，到节点E的成本为5 + 5 = 10，均大于上一步的记录，所以不更新。 - 第三步，选择通过节点B到达节点D的成本6。通过节点D到节点E的成本为6 + 2 = 8，这是目前到节点E的最小成本。 最终，从节点A到节点E的最短路径为A—B—D—E，从节点A到节点D的最短路径为A—B—D。 ### 1.2 注意事项 在表格的每一行，我们使一个节点的权重变为永久。对于所有节点都要进行此操作。若某一行出现平局，可随机选择一个节点。 ## 2. 内部网关路由协议 ### 2.1 路由信息协议（RIP） RIP是最古老的内部网关路由协议，基于距离向量路由。它由施乐网络系统开发，使用跳数作为指标，从源路由器到目标子网的最大跳数限制为15。 在距离向量路由中，每个路由器与相邻路由器交换距离向量，即该路由器到子网的当前最短路径。路由器每30秒交换一次路由信息，若180秒内未收到相邻路由器的信息，则认为该邻居已关闭或故障，随后通过向相邻路由器发送广告来更新路由表。路由器也可发送RIP请求消息以了解邻居到目标的成本。 RIP路由表包含三列：目标子网、到目标子网的跳数以及最短路径上的下一个路由器。例如，当路由器A收到路由器B的广告后，发现通过路由器D到目标子网Z的路径更短，便会更新其路由表。 然而，RIP适用于小型系统，且存在计数到无穷大问题和收敛问题，这促使我们使用基于链路状态路由的开放最短路径优先（OSPF）协议。 ### 2.2 开放最短路径优先（OSPF） OSPF由IETF在RFC 2328中标准化，用于自治系统内部的路由。它使用链路状态路由来泛洪链路状态数据包，并结合迪杰斯特拉最短路径算法。“开放”意味着路由协议规范在文献中公开。 管理员会为两个路由器之间的连接计算多个指标，如距离、延迟、数据速率等，与链路容量成反比的指标可抑制特定路由的流量。OSPF提供了确定最小成本路径路由的机制。 #### 2.2.1 OSPF的特点 - 路由器定期（每30分钟）或在链路状态变化时向自治系统内的所有路由器广播链路状态信息，与仅向直接邻居广播的距离向量路由不同。 - 支持多路径负载均衡。 - 路由器之间的信息交换是安全的，新手研究人员无法注入虚假路由信息。 - 支持自治系统的分层结构，便于更好地管理。 #### 2.2.2 OSPF术语 - **区域（Area）**：是一个广义的子网，包含网络、路由器和主机。区域内的路由器向该区域的其他路由器广播链路状态数据包，每个区域使用最短路径算法运行其链路状态路由。区域不重叠，但有些路由器可能不属于任何区域，区域内的网络必须是连通的。 - **区域边界路由器（Area Border Router）**：负责将数据包发送到其他区域。 - **骨干路由器（Backbone Router）**：位于主区域零内，骨干区域连接自治系统的所有正常区域，流量通过骨干区域从一个区域传输到另一个区域。 - **OSPF链路**： - **传输网络（Transit Network）**：承载既不源于也不终止于连接系统的数据。 - **存根网络（Stub Network）**：连接到单个路由器，数据要么源于该路由器，要么终止于该路由器。 为了交换信息，会选举一个指定路由器，其他路由器与之连接，以提高效率。在紧急情况下，会使用备份指定路由器和虚拟链路。每个路由器通过Hello消息向其所在区域的所有其他路由器泛洪链路状态信息（邻居和成本），并使用序列号跟踪最新信息。每个路由器为其所在区域创建拓扑结构，然后使用迪杰斯特拉算法找到骨干路由器与其他路由器之间的最短路径。 ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(源节点):::process -->|链路1| B(中间节点1):::process A -->|链路2| C(中间节点2):::process B -->|链路3| D(目标节点):::process C -->|链路4| D ``` ## 3. 外部网关路由协议 ### 3.1 边界网关协议（BGP） BGP用于多个自治系统之间的路由，它通过建立TCP连接进行可靠通信。BGP是一种距离向量协议，但与RIP不同，它只考虑到目标的成本，其路由表除了包含到目标的成本外，还包含所使用的精确路径。BGP在RFC 4271中被标准化。 在BGP中，选择路由基于指标（成本）和本地偏好。本地偏好涉及策略因素，有些自治系统可能不会通过某些自治系统传输数据，即使这些路径是最短的。自治系统可以对来自其他自治系统的传输流量收费或拒绝。如果两条路由的本地偏好程度相似，BGP会选择最短路径；如果本地偏好程度和成本都相同，则选择下一跳路由器最近的路由。 ### 3.2 BGP的工作步骤 BGP的工作分为三个步骤：邻居协议、邻居可达性和网络可达性。 1. **邻居协议**：自治系统之间建立邻居关系，通过eBGP（外部BGP）在不同自治系统的BGP路由器之间交换信息，iBGP（内部BGP）在自治系统内部的BGP路由器之间交换信息。 2. **邻居可达性**：确定邻居是否可达，以确保信息能够正常交换。 3. **网络可达性**：更新路由/转发表，使每个自治系统了解其他自治系统的可达性信息。 例如，AS 1通过eBGP向AS 2发送可达性信息，反之亦然；AS 2的网关再将AS 1的可达性信息发送给AS 3，AS 3更新其路由表。 ### 3.3 BGP的特点 - **唯一标识**：每个自治系统由ICANN分配的全局唯一的自治系统编号（ASN）标识，类似于IP地址。 - **AS路径**：包含路由所经过的自治系统列表，例如，当广告从AS 1通过AS 2到达AS 3时，AS路径为{AS 1, AS 2}。 - **避免环路**：BGP不会出现计数到无穷大的问题，可防止路由环路和不稳定。路由器不会选择包含自身的路由，因为AS路径明确显示了要经过的自治系统。 | 特点 | 描述 | | --- | --- | | 唯一标识 | 自治系统由全局唯一的ASN标识 | | AS路径 | 记录路由经过的自治系统列表 | | 避免环路 | 防止路由环路和不稳定，不选择包含自身的路由 | ## 4. 性能指标 ### 4.1 延迟类型 网络中的总延迟（或延迟）定义为所有数据包从源到目标传输所需的时间，由以下几个部分组成： - **处理时间**：检查数据包头部、确定下一站和检查位级错误所需的时间。 - **排队时间**：传输前的等待时间，取决于队列中已有的数据包数量。如果队列为空，则排队时间为零。 - **传输时间**：将数据包的所有位传输到通信链路上所需的时间，计算公式为：传输时间（秒）= 消息大小（位）/ 带宽（位/秒）。 - **传播时间**：位在源和目标之间传播所需的时间，计算公式为：传播时间 = 距离 / 传播速度。空气中电磁信号的传播速度为3 × 10⁸ m/s，电缆中的传播速度为光速的三分之二。 ### 4.2 重要性能指标 - **吞吐量**：定义为接收器接收的位数与经过时间的比率。网络的整体吞吐量由瓶颈链路的传输速率决定，即源和目标之间所有链路传输速率的最小值。 - **带宽 - 延迟乘积**：表示可以容纳在链路中的位数，可类比为管道，带宽是管道的横截面积，延迟是管道的长度，带宽 - 延迟乘积是管道的体积。计算公式为：带宽 - 延迟乘积 = 带宽（bps）× 延迟（秒）。 - **数据包丢失**：由于缓冲区（队列）的容量有限，如果数据包到达时队列已满，路由器会丢弃该数据包，称为数据包丢失。丢失率与流量强度成正比。 ### 4.3 示例计算 #### 4.3.1 延迟计算 对于一个10 kb的消息，通过100 Mbps的带宽传输，源和目标之间的距离为2000 km，电缆中的传播速度为2 × 10⁸ m/s。 - 传输时间 = 10×1024 / 100×10⁶ = 0.0001024 s = 0.1024 ms - 传播时间 = 2000×1000 / 2×10⁸ = 0.01 s = 10 ms #### 4.3.2 吞吐量计算 平均每分钟可以发送10,000帧，每帧由6000位组成，对于一个5 Mbps带宽的网络： 吞吐量 = 10,000×6000 / 60 = 1 × 10⁶ bps = 1 Mbps，小于理论上的5 Mbps带宽。 #### 4.3.3 网络吞吐量计算 在具有多个链路的网络中，网络的吞吐量由瓶颈链路的传输速率决定。例如，在一个网络中，源 - 路由器链路的速率为R1，路由器 - 目标链路的速率为R2，中央链路的传输速率为R₃，则网络的吞吐量为： - 吞吐量1 = min{R1, R2} - 吞吐量2 = min{R1, R₃, R2} ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(源):::process -->|R1| B(路由器):::process B -->|R3| C(路由器):::process C -->|R2| D(目标):::process ``` 综上所述，网络路由算法和性能指标是网络通信中的重要组成部分。不同的路由协议适用于不同的网络场景，而性能指标则用于评估网络的运行效率和质量。了解这些知识有助于我们更好地设计、管理和优化网络。