编辑“︁网络路由算法”︁

= 网络路由算法 =

网络路由算法是计算机网络中用于确定数据包从源节点到目标节点传输路径的核心技术。它广泛应用于互联网、电信网络、数据中心以及各类分布式系统中，直接影响网络性能、可靠性和资源利用率。本条目将系统介绍路由算法的分类、经典实现、代码示例及实际应用场景。

== 基本概念 ==
'''路由算法'''通过计算最优或可行路径解决以下问题：
* '''路径选择'''：根据网络拓扑和度量标准（如跳数、延迟、带宽）选择传输路径
* '''动态适应'''：应对网络拓扑变化（如链路故障）重新计算路径
* '''负载均衡'''：避免部分链路过载，提高整体吞吐量

主要分类如下：
{| class="wikitable"
|+ 路由算法分类
! 类型 !! 特点 !! 典型算法
|-
| '''静态路由''' || 人工配置固定路径 || 手动路由表
|-
| '''动态路由''' || 自动适应网络变化 || [[#距离矢量路由|距离矢量]]、[[#链路状态路由|链路状态]]
|-
| '''集中式''' || 中央控制器计算路径 || SDN控制器
|-
| '''分布式''' || 节点协作计算路径 || OSPF, BGP
|}

== 经典算法实现 ==
=== 距离矢量路由 ===
基于Bellman-Ford算法，每个节点维护到其他节点的距离向量，定期与邻居交换信息。

算法步骤：
# 初始化：节点到自身距离为0，到其他节点为∞
# 定期向邻居发送自己的距离向量
# 收到邻居向量后更新本地路由表

<mermaid>
graph TD
    A((A)) --1--> B((B))
    A --4--> C((C))
    B --1--> C
    B --2--> D((D))
    C --1--> D
</mermaid>

'''示例路由表更新过程'''（节点A的视角）：
{| class="wikitable"
|+ 迭代过程
! 目标 !! 初始 !! 收到B的向量后 !! 收到C的向量后
|-
| B || ∞ → 1 || - || -
|-
| C || ∞ → 4 || min(4, 1+1)=2 || -
|-
| D || ∞ || min(∞,1+2)=3 || min(3,2+1)=3
|}

=== 链路状态路由 ===
采用Dijkstra算法，每个节点维护完整的网络拓扑图，独立计算最短路径。

'''Python实现示例'''：
<syntaxhighlight lang="python">
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    heap = [(0, start)]
    
    while heap:
        current_dist, current_node = heapq.heappop(heap)
        if current_dist > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    
    return distances

# 示例网络拓扑
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 1, 'D': 2},
    'C': {'A': 4, 'B': 1, 'D': 1},
    'D': {'B': 2, 'C': 1}
}

print(dijkstra(graph, 'A'))  # 输出: {'A': 0, 'B': 1, 'C': 2, 'D': 3}
</syntaxhighlight>

== 实际应用案例 ==
=== 互联网路由 (BGP) ===
边界网关协议(BGP)是互联网骨干路由的核心协议，其特点包括：
* '''路径向量算法'''：记录完整AS路径而不仅是距离
* '''策略路由'''：允许管理员基于商业关系设置策略
* '''增量更新'''：仅传播变化的路由信息

'''典型路由决策过程'''：
<mermaid>
sequenceDiagram
    participant AS1
    participant AS2
    participant AS3
    AS1->>AS2: 通告路由 192.0.2.0/24
    AS2->>AS3: 通告路由 192.0.2.0/24 (路径: AS1,AS2)
    AS3->>AS2: 选择最优路径
</mermaid>

=== 数据中心路由 (ECMP) ===
等价多路径路由(ECMP)通过哈希分流实现负载均衡：
* '''流量分发'''：将流均匀分配到多条等代价路径
* '''哈希算法'''：通常基于五元组(源/目标IP+端口，协议)
* '''故障恢复'''：自动检测失效路径并重路由

数学表示为：
<math>
P_i = \frac{1}{N} \quad \text{其中} \ N \ \text{为等价路径数}
</math>

== 进阶主题 ==
* '''QoS路由'''：考虑带宽、延迟等服务质量参数
* '''移动自组网路由'''：AODV, DSR等适用于动态拓扑的算法
* '''SDN路由'''：集中式控制器实现全局优化

== 参见 ==
* [[最短路径问题]]
* [[分布式系统]]
* [[网络协议栈]]

本条目通过理论分析、代码实现和实际案例展示了网络路由算法的核心原理与应用实践，读者可根据需要进一步研究特定协议或算法的实现细节。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:实际应用案例]]