Skip to main content

10. The Neighbor Data Structure (邻居数据结构)

本章详细定义 OSPF 邻居数据结构的组成元素、状态机和维护机制。邻居关系是 OSPF 协议运行的基础。

章节概述 (Chapter Overview)​

邻居数据结构包含：

  • 邻居标识和状态信息
  • 数据库同步相关列表
  • 邻居状态机
  • 定时器和事件处理

10.1 邻居数据结构字段 (Neighbor Data Structure Fields)​

基本标识字段​

字段类型说明
Neighbor IDRouter ID邻居的 Router ID
Neighbor IP AddressIP地址邻居的接口地址
Neighbor Priority0-255DR 选举优先级
Neighbor State枚举邻居当前状态
Inactivity Timer定时器检测邻居失效

DR/BDR 相关字段​

字段说明
Neighbor's Designated Router邻居声明的 DR
Neighbor's Backup Designated Router邻居声明的 BDR

数据库同步字段​

字段说明
Master/Slave数据库交换中的角色
DD Sequence NumberDD 数据包序列号
Last Received Database Description最后收到的 DD 数据包

同步列表​

Link State Request List

  • 需要从邻居请求的 LSA 列表
  • 按 LS Type 排序
  • 用于 Loading 状态

Link State Retransmission List

  • 已发送但未确认的 LSA
  • 需要重传的 LSA
  • 每隔 RxmtInterval 重传

Database Summary List

  • Exchange 状态下使用
  • 包含本地 LSDB 的 LSA 头部
  • 用于生成 DD 数据包

10.2 邻居状态机 (Neighbor State Machine)​

状态定义​

1. Down (失效)​

描述

  • 初始状态
  • 未收到任何 Hello 数据包
  • 或 Inactivity Timer 超时

列表状态

  • 所有列表为空

2. Attempt (尝试)​

描述

  • 仅用于 NBMA 网络
  • 手动配置的邻居
  • 周期性发送 Hello

适用场景

  • NBMA 网络的非 DR 路由器

3. Init (初始化)​

描述

  • 收到邻居的 Hello
  • 但 Hello 中不包含本路由器
  • 单向通信

列表状态

  • 所有列表为空

4. 2-Way (双向通信)​

描述

  • Hello 中包含本路由器 ID
  • 双向通信已建立
  • 关键决策点：是否建立邻接

邻接建立判断

if (接口类型 == 点到点 或 点到多点 或 虚拟链路):
    建立邻接
else if (本路由器是 DR 或 BDR):
    建立邻接
else if (邻居是 DR 或 BDR):
    建立邻接
else:
    保持 2-Way 状态（不建立邻接）

5. ExStart (开始交换)​

描述

  • 协商 Master/Slave 关系
  • 确定初始 DD 序列号
  • 发送空的 DD 数据包

Master/Slave 决定

  • Router ID 大的成为 Master
  • Master 控制序列号递增

列表状态

  • Database Summary List 为空
  • 其他列表也为空

6. Exchange (数据库描述)​

描述

  • 交换数据库描述数据包
  • 描述各自的 LSDB 内容
  • 使用 Database Summary List

Master 行为

  • 首先发送 DD
  • 等待 Slave 响应
  • 收到响应后发送下一个 DD

Slave 行为

  • 等待 Master 的 DD
  • 响应相同序列号的 DD
  • 包含自己的 Database Summary

列表变化

  • Database Summary List 逐渐清空
  • Link State Request List 逐渐填充

7. Loading (加载)​

描述

  • 请求缺失或过期的 LSA
  • 发送 Link State Request
  • 接收 Link State Update

完成条件

  • Link State Request List 为空
  • 所有请求的 LSA 已接收

重传机制

  • 每隔 RxmtInterval 检查
  • 未响应的请求重新发送

8. Full (完全邻接)​

描述

  • 数据库完全同步
  • 正常运行状态
  • 可以用于 SPF 计算

持续活动

  • 发送和接收 Hello
  • LSA 泛洪
  • 维护 Link State Retransmission List

10.3 邻居状态转换 (Neighbor State Transitions)​

状态转换图​

Down
  ↓
Init (收到 Hello)
  ↓
2-Way (Hello 包含本路由器)
  ↓
ExStart (决定建立邻接)
  ↓
Exchange (协商完成)
  ↓
Loading (DD 交换完成)
  ↓
Full (LSR List 为空)

触发事件​

事件说明可能的状态转换
HelloReceived收到 HelloDown → Init, 重置定时器
2-WayReceivedHello 包含本路由器Init → 2-Way
NegotiationDoneMaster/Slave 协商完成ExStart → Exchange
ExchangeDoneDD 交换完成Exchange → Loading 或 Full
LoadingDoneLSA 请求完成Loading → Full
AdjOK?检查是否应建立邻接2-Way ↔ ExStart
SeqNumberMismatchDD 序列号错误任何状态 → ExStart
BadLSReq无效的 LSA 请求任何状态 → ExStart
1-WayHello 不包含本路由器2-Way 以上 → Init
InactivityTimer超时任何状态 → Down

10.4 邻居事件处理 (Neighbor Event Processing)​

HelloReceived 事件​

处理步骤

  1. 重置 Inactivity Timer
  2. 检查 Hello 中的邻居列表
  3. 更新邻居的 DR 和 BDR 字段
  4. 如果 Hello 包含本路由器 → 触发 2-WayReceived

2-WayReceived 事件​

处理步骤

  1. 如果当前状态 < 2-Way：
    • 转到 2-Way 状态
    • 调用 AdjOK? 检查是否建立邻接
  2. 如果当前状态 >= 2-Way：
    • 调用 AdjOK? 检查邻接是否仍然需要

NegotiationDone 事件​

处理步骤

  1. 初始化 DD Sequence Number
  2. 初始化 Database Summary List
  3. 转到 Exchange 状态
  4. 如果是 Master，发送第一个 DD

ExchangeDone 事件​

处理步骤

  1. 如果 Link State Request List 为空：
    • 转到 Full 状态
  2. 否则：
    • 转到 Loading 状态
    • 发送 Link State Request

LoadingDone 事件​

处理步骤

  1. 转到 Full 状态
  2. 如果是新的邻接：
    • 生成新的 Router-LSA
    • 可能需要生成 Network-LSA（如果是 DR）

10.5 邻居列表管理 (Neighbor List Management)​

用途

  • 跟踪需要从邻居请求的 LSA
  • 用于 Loading 状态

操作

  • 添加：Exchange 状态发现邻居有更新的 LSA
  • 删除：收到对应的 LSA
  • 重传：RxmtInterval 后未收到响应

用途

  • 跟踪已发送但未确认的 LSA
  • 保证 LSA 可靠传输

操作

  • 添加：泛洪 LSA 或响应 LSR 时
  • 删除：收到 LSAck 或隐式确认
  • 重传：每隔 RxmtInterval

Database Summary List​

用途

  • Exchange 状态下使用
  • 包含本地 LSDB 的摘要

操作

  • 初始化：ExStart → Exchange 转换时
  • 使用：生成 DD 数据包
  • 清空：Exchange 完成

10.6 邻居维护机制 (Neighbor Maintenance)​

Inactivity Timer​

功能

  • 检测邻居失效
  • 每收到 Hello 重置

超时处理

Inactivity Timer 超时:
  1. 邻居状态 → Down
  2. 清空所有列表
  3. 如果是 DR/BDR 或 Full 邻接:
     - 生成新的 Router-LSA
     - 可能生成新的 Network-LSA
  4. 触发 SPF 计算

Master/Slave 重传控制​

Master 重传

每隔 RxmtInterval:
  if (上次发送的 DD 未收到响应):
    重传 DD 数据包

Slave 重传

每隔 RxmtInterval:
  if (上次发送的 DD 未收到新的 Master DD):
    重传上次的 DD 数据包

10.7 性能和扩展性考虑 (Performance Considerations)​

列表大小优化​

Database Summary List

  • 大小 = 本地 LSDB 中的 LSA 数量
  • 可能很大
  • Exchange 状态临时使用

Link State Request List

  • 通常较小
  • Loading 状态快速清空

Link State Retransmission List

  • 动态变化
  • 稳定网络中应为空或很小
  • 大量 LSA 表示网络问题

内存管理​

优化策略

  • 使用指针引用 LSA 而非复制
  • 及时清理已完成的列表
  • 复用数据结构

技术要点总结 (Technical Summary)​

关键概念​

  1. 状态机驱动邻居管理

    • 8 个明确定义的状态
    • 事件驱动的转换
    • 清晰的进入和退出条件

  2. 三个关键列表

    • Database Summary List：描述本地 LSDB
    • Link State Request List：请求缺失的 LSA
    • Link State Retransmission List：保证可靠传输

  3. 可靠的数据库同步

    • Master/Slave 机制
    • 序列号控制
    • 重传保证

实现要点​

邻居发现

  • 监听 Hello 数据包
  • 创建邻居数据结构
  • 初始化定时器

邻接建立

  • 检查是否需要邻接
  • 执行状态转换
  • 同步数据库

邻居维护

  • Hello 保活
  • Inactivity Timer 监控
  • 列表维护和清理

故障处理

  • 超时检测
  • 状态回退
  • 触发路由重新计算

参考资料 (References)

注意 (Note)：邻居数据结构和状态机是 OSPF 最复杂的部分之一。正确实现邻居管理对于协议的稳定运行至关重要。

Last updated on