Skip to main content

2. The Link-state Database: Organization and Calculations (链路状态数据库：组织与计算)

本章描述 OSPF 链路状态数据库的组织结构以及如何使用该数据库计算路由表。

章节概述 (Chapter Overview)​

本章涵盖以下主要主题：

  • 路由器和网络的表示方法
  • 最短路径树的构建
  • 外部路由信息的使用
  • 等价多路径的实现

2.1 Representation of Routers and Networks (路由器和网络的表示)​

核心概念 (Core Concepts)​

图论表示 (Graph Representation)

  • 自治系统被建模为有向图 (AS modeled as directed graph)
  • 顶点 (Vertices)：路由器和网络
  • 边 (Edges)：路由器接口
  • 代价 (Cost)：每条边的权重

路由器表示 (Router Representation)

  • 路由器 ID：32 位唯一标识符
  • 接口列表：连接到网络的接口
  • 邻居关系：与相邻路由器的连接
  • 链路状态：每个接口的状态信息

网络类型 (Network Types)

网络类型英文特征示例
点到点网络Point-to-Point连接两个路由器T1 线路, PPP
广播网络Broadcast多路访问，支持广播Ethernet, Token Ring
NBMA 网络Non-Broadcast Multi-Access多路访问，不支持广播Frame Relay, X.25
点到多点网络Point-to-MultiPoint作为点到点链路集合处理部分网状 Frame Relay

2.1.1 Representation of Non-broadcast Networks (非广播网络的表示)​

NBMA 网络特性 (NBMA Network Characteristics)

  • 不支持链路层广播或组播
  • 需要手动配置邻居
  • 需要选举指定路由器 (DR) 和备份指定路由器 (BDR)
  • 必须具有完全网状连接或使用点到多点模式

配置要求 (Configuration Requirements)

  • 邻居列表配置
  • DR 优先级设置
  • Hello 间隔和 Dead 间隔
  • 轮询间隔 (Poll Interval)

本节通过具体示例展示链路状态数据库的结构和内容。

示例网络拓扑 (Example Network Topology)

  • 多个路由器互连
  • 不同类型的网络
  • 区域划分
  • 虚拟链路

LSA 类型 (LSA Types)

LSA 类型名称描述泛洪范围
Type 1Router-LSA路由器链路状态区域内
Type 2Network-LSA网络链路状态区域内
Type 3Summary-LSA (网络)区域间网络路由单个区域
Type 4Summary-LSA (ASBR)ASBR 路由单个区域
Type 5AS-external-LSA外部路由整个 AS

2.2 The Shortest-path Tree (最短路径树)​

Dijkstra 算法 (Dijkstra's Algorithm)​

算法步骤 (Algorithm Steps)

  1. 初始化：将自身设为根节点
  2. 候选列表：维护待处理顶点列表
  3. 选择最小代价顶点
  4. 更新邻居代价
  5. 重复直到所有顶点处理完毕

代价计算 (Cost Calculation)

  • 接口代价：基于带宽或手动配置
  • 路径代价：沿路径所有接口代价之和
  • 默认代价公式：Cost = 参考带宽 / 接口带宽

树的构建 (Tree Construction)

  • 根节点：执行计算的路由器
  • 内部节点：AS 内的路由器和网络
  • 叶节点：外部路由（AS-external-LSA）

关键术语 (Key Terms)​

术语英文定义
SPF 树SPF Tree以路由器为根的最短路径树
候选列表Candidate List待添加到树的顶点
父节点Parent树中的前驱节点
距离Distance从根到节点的代价
下一跳Next Hop到达目的地的第一个路由器

2.3 Use of External Routing Information (外部路由信息的使用)​

外部路由类型 (External Route Types)​

Type 1 外部路由 (Type 1 External)

  • 代价 = 内部代价 + 外部代价
  • 可比较的度量
  • 适用于相同 AS 内的 IGP

Type 2 外部路由 (Type 2 External)

  • 代价 = 外部代价（内部代价仅用于打破平局）
  • 不可比较的度量
  • 适用于不同 AS 的 EGP
  • OSPF 默认类型

ASBR (Autonomous System Boundary Router)​

ASBR 角色 (ASBR Role)

  • 引入外部路由到 OSPF
  • 产生 AS-external-LSA
  • 可以是任何 OSPF 路由器
  • 通过 Type 4 Summary-LSA 通告

路由重分发 (Route Redistribution)

  • 从其他协议导入路由
  • 设置外部路由类型
  • 配置路由标记 (Route Tag)
  • 设置转发地址 (Forwarding Address)

2.4 Equal-cost Multipath (等价多路径)​

ECMP 概念 (ECMP Concept)​

基本原理 (Basic Principles)

  • 到达同一目的地的多条等价路径
  • 路径代价完全相同
  • 流量在多条路径间分配
  • 提高带宽利用率和冗余性

实现方式 (Implementation Methods)

方法描述优点缺点
逐包轮询Per-packet round-robin简单可能导致乱序
逐流分配Per-flow distribution保持顺序需要流识别
基于哈希Hash-based高效、确定性可能不均衡

配置参数 (Configuration Parameters)

  • 最大路径数：系统支持的最大 ECMP 路径数
  • 负载均衡算法：选择流量分配方法
  • 代价阈值：允许的代价差异范围

路由表条目 (Routing Table Entries)​

多路径表示 (Multipath Representation)

  • 单个目的地前缀
  • 多个下一跳接口
  • 相同的路由代价
  • 相同的路由类型

技术要点总结 (Technical Summary)​

关键数据结构 (Key Data Structures)​

  1. 链路状态数据库 (LSDB)：存储所有 LSA
  2. SPF 树：最短路径树结构
  3. 路由表：最终的转发表
  4. 邻居表：相邻路由器信息

重要算法 (Important Algorithms)​

  1. Dijkstra SPF：计算最短路径
  2. LSA 泛洪：分发链路状态信息
  3. 路由计算：从 SPF 树生成路由表
  4. ECMP 选择：多路径负载均衡

性能考虑 (Performance Considerations)​

  • SPF 计算复杂度：O(N log N)
  • 数据库大小：影响内存使用
  • 收敛时间：拓扑变化到路由更新
  • 扩展性：大型网络的区域划分

参考资料 (References)

  • 完整原文：RFC 2328 Section 2
  • Dijkstra 算法：E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs"

注意 (Note)：本文档基于 RFC 2328 官方规范。完整的技术细节、算法伪代码和规范性语言请参考原文档。

Last updated on