IPv4 数据报格式:
┌──────┬──────┬──────────┬───────────────┬──────────────┐
│Ver(4)│IHL(4)│DSCP(6)+ECN(2)│  总长度(16)  │
├──────┴──────┴──────────┼───────────────┤──────────────┤
│     标识(16)           │Flags(3)+偏移(13)             │
├────────────────────────┼───────────────┤──────────────┤
│   TTL(8)  │ 协议(8)    │  首部校验和(16)              │
├───────────┴────────────┼───────────────┤──────────────┤
│     源 IP 地址 (32)    │                              │
├────────────────────────┤                              │
│     目的 IP 地址 (32)  │                              │
├────────────────────────┴──────────────────────────────┤
│              选项（可选）                               │
└───────────────────────────────────────────────────────┘

关键字段:
- TTL: 防止分组无限循环，每经过一个路由器减 1，为 0 时丢弃
- 协议: 标识上层协议（6=TCP, 17=UDP, 1=ICMP）
- 首部校验和: 只校验首部，不校验数据（效率考虑）

算法:
1. 每个节点向所有其他节点广播链路状态
2. 每个节点构建完整的网络拓扑图
3. 运行 Dijkstra 算法计算最短路径树

复杂度: O(n²) 或 O(n log n)（使用优先队列）

优势: 收敛快，无路由环路
劣势: 需要全局拓扑信息，扩展性差
代表: OSPF

算法:
每个节点维护到所有目的的距离向量
周期性向邻居发送自己的距离向量
收到邻居的距离向量后更新:
  d_x(y) = min_v {c(x,v) + d_v(y)}

复杂度: O(n × m)（n 节点, m 链路）

优势: 分布式，只需邻居信息
劣势: 收敛慢，计数到无穷问题
代表: RIP, BGP (路径向量变体)

计数到无穷问题:
A → B → C → D
如果 D 断开:
B 先更新: d(B,D) = ∞
A 还没更新: d(A,D) = 2 (通过 B)
B 收到 A 的更新: d(B,D) = min(∞, 1 + 2) = 3 (通过 A)
→ 环路! 需要毒性反转或水平分割来解决

BGP (Border Gateway Protocol):
- 互联网的路由协议
- 在自治系统 (AS) 之间交换路由信息
- 基于路径向量，携带完整的 AS 路径

BGP 属性:
- AS_PATH: 路由经过的 AS 序列（用于环路检测和策略）
- NEXT_HOP: 到达目的的下一跳 IP
- LOCAL_PREF: 本地优先级
- MED: 多出口鉴别器

BGP 路由选择:
1. 最高 LOCAL_PREF
2. 最短 AS_PATH
3. 最低 MED
4. eBGP 优于 iBGP
5. 最短 IGP 路径到 NEXT_HOP
6. 路由器 ID 最小

BGP 策略:
- 不一定要最短路径
- 可以基于商业关系选择路由
- 客户 > 对等 > 提供商

SDN (Software-Defined Networking):
核心思想: 控制平面与数据平面分离

┌──────────────────────────────┐
│     应用层 (路由、防火墙)      │
├──────────────────────────────┤
│     控制层 (OpenFlow 控制器)   │
├──────────────────────────────┤
│     数据层 (交换机/路由器)     │
└──────────────────────────────┘

优势:
- 集中式控制: 全局视图，优化路由
- 可编程: 通过软件定义网络行为
- 创新加速: 新协议只需更新控制器

OpenFlow:
- 流表: 匹配字段 + 动作 + 优先级
- 匹配: 目的 IP、源 IP、端口、协议...
- 动作: 转发、丢弃、修改、发送到控制器

import heapq

def dijkstra(graph, source):
    """
    graph: {node: {neighbor: cost}}
    返回: (dist, prev)
    """
    dist = {node: float('inf') for node in graph}
    prev = {node: None for node in graph}
    dist[source] = 0
    pq = [(0, source)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u].items():
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))
    
    return dist, prev

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

dist, prev = dijkstra(graph, 'A')
print("从 A 到各节点的最短距离:", dist)
# 输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}