一种轻量化的链路状态路由协议

陈泽婵

（中国电子科技集团公司第七研究所网络交换事业部 广东省广州市 510310）

1 引言

战术通信网络具有机动性高、抗毁能力强、带宽消耗低等特殊应用需求。当前外军战术通信网路由协议主要采用基于链路状态的OSPF路由协议，具有快速、可靠、稳定等优点。但链路状态路由协议对CPU 的计算能力、内存要求高，且需泛洪全网拓扑信息，对链路带宽消耗较大。

为减少路由协议对链路带宽资源的消耗，适应有无线混杂、宽窄带融合的复杂战术环境，本文设计了一种轻量化的链路状态路由协议，下文简称LLSRP（Lightweight Link State Routing Protocol）。

2 总体设计

路由应具备综合选路、路由重分布能力，同时重点进行协议的轻量化设计。

2.1 轻量化设计思路

在进行路由协议的轻量化设计时，通过简化协议交互流程、减少数据包内容等方面降低路由协议运行时的带宽占用。此外，增量更新、聚合发送、同步校验、握手时间自调节等方式将进一步压缩协议带宽开销。

增量更新：当网络拓扑发生变化时，只扩散变化的链路状态通告；

聚合发送：当节点需要发送链路状态更新或确认报文时，延迟一小段时间再集中发送，从而减少路由报文占用信道发送次数；

同步校验：不进行链路状态数据库的老化和定期刷新，通过握手报文中的本地链路状态数据库标识信息（链路状态数据库的校验值）确保链路状态数据库同步；

握手时间自调节：根据无线子网内邻居状态自适应调节握手报文发送周期，初始尝试建立邻居关系时，采用较短的握手时间间隔，当邻居关系建立完成，采用较长的握手时间间隔。

2.2 功能模块

LLSRP 与外部模块之间的关系如图1、内部软件模块结构见图2。

图1：LLSRP 与外部模块关系图

图2：LLSRP 软件模块图

各个节点的LLSRP 模块通过底层物理信道建立并维护邻居关系、获得链路状态与资源等信息；路由管理模块可将其他路由协议的路由表导入LLSRP 模块，支撑LLSRP 的路由重分布功能。

LLSRP 模块由邻居维护、LSDB 同步、路由计算模块组成。

运行LLSRP 的网络内每个节点维护3 张表：邻居表、链路状态数据库、路由表。

（1）邻居列表：列出节点全部邻居信息；

（2）链路状态数据库：列出网络中链路和资源信息，保存了全网的拓扑信息；

（3）路由表：列出到达每个相连节点和网络的最短路径。

邻居维护模块构建并维护邻居表。通过握手协议、链路通断状态进行邻居增删；获取链路带宽等资源信息；进行邻居同步检测，比较本地与邻居的LSDB 标识，不一致时触发LSDB 同步流程。

LSDB 同步模块构建并维护链路状态数据库，采取增量更新、广播泛洪、聚合发送等方式降低协议开销。

路由计算模块构建并维护本地的LLSRP 路由表，包括LLSRP 节点路由表及LLSRP 重分布路由表，其核心算法是最短路径算法SPF。

3 协议描述

3.1 协议工作过程

通过运行LLSRP 协议可以完成混合组网下的整网路由收敛，实现数据业务最短路径转发，其基本步骤如图3。

图3：LLSRP 工作流程图

LLSRP 模块通过周期性握手协议建立并维护邻居表；经由邻居逐跳泛洪链路状态通告，形成全网同步的链路状态数据库（LSDB）；每个节点根据链路状态数据库，采用最短路径算法SPF 计算出全网可达节点的LLSRP 节点路由表；通过重分布路由所在节点位置及LLSRP 节点路由表生成重分布路由表；将节点路由表及重分布路由表合并，即是本地LLSRP 路由表。

3.1.1 邻接关系建立与维护

HELLO 协议用于维护LLSRP 的邻居关系，作用是建立、维护邻居关系和检查LSDB 同步状态。节点周期性发送HELLO 报文。报文中携带了发送节点的邻居列表，接收节点通过HELLO 报文中携带的邻居列表进行信道状态的判断，如果邻居列表中含有本节点信息，则为双向信道，否则为单向信道。节点必须从邻居收到3 次HELLO 报文方可建立双向邻居关系。

在稳定状态下，通过HELLO 报文维护邻居信息。HELLO 报文发送时间间隔缺省值取10s。

邻居关系需要动态维护，如果在规定的保持时间内（3次HELLO 发送间隔）没有收到某一邻居的HELLO 报文或者其他类型报文，则认为此邻居不可达，相应地要删除与该邻居相关的链路状态信息，并向其它邻居发送相关链路状态更新信息。

HELLO 报文发送的周期动态调整，在网络初始化时以较小的HELLO 间隔周期发送从而快速立邻居关系；在网络稳定后，则以较大的Hello 间隔周期发送。在网络稳定后，若节点发现了新邻居，会触发HELLO 报文的立即发送，无论HELLO 间隔是否到期。

当节点获取新邻居后，若发现自身不在邻居的邻居表内，则立即触发HELLO 报文以加快节点间的邻居关系建立。

HELLO 报文中携带有LSDB 标识，可检测本地和邻居节点的链路状态数据库是否同步。

3.1.2 链路状态数据库同步

LLSRP 对同步LSDB 流程进行了简化。

（1）不进行DR/BDR 选举，充分利用无线信道广播的特性，减少报文占用信道的发送次数。邻居之间处于对等关系，通过HELLO 报文中的LSDB 标识确保与所有邻居的LSBD 同步。

（2）不进行链路状态请求，开始同步链路状态数据库流程时，将本地链路状态数据库所有链路状态通告（LSA）的摘要信息封装为LSA_DD 报文，向邻居节点发送。邻居节点将摘要列表与其LSDB 比较，即可获得本节点缺少的LSA 条目，将这些LSA 详细信息通过LSA_UPDATE 发送给本节点。

在下列情况下，LLSRP 进程新增、删除或更新链路状态数据库：

新增或删除邻居节点；

链路通断状态或性能（如带宽）变化；

收到链路状态更新报文。

3.1.3 路由计算

LLSRP 协议采用最短路径优先算法SPF（即Dijkstra 算法）计算本地路由表。

路由计算时，总的路由代价Cost为各段链路代价Cost之和：

Cost=∑Cost

链路代价计算公式如下：

其中，bw 为链路出口带宽，可由管理员人工配置，也可根据链路出站带宽、链路类型、节点类型自动获得。

为适应多种类型信道并存的网络环境，对特殊信道类型的链路开销应进行针对设计，如空地链路和卫星链路。

空中节点到地面节点的拓扑关系为点到多点，计算链路代价时需根据空中节点连通的地面节点数量（N 个）对总带宽资源（BW）进行平均分配，计算公式如下：

bw= BW/N

卫星链路具有带宽较宽，时延较大的特点，在路由协议中卫星链路代价需同时考虑带宽及时延，计算公式如下：

外部路由代价值(Cost)在LLSRP 网内传播时不变化。当参与本地计算时，总的代价值为外部路由代价值和内部链路代价值之和，计算公式如下：

3.1.4 构建重分布路由表

可通过2 种方式计算重分布路由。

方式一：将重分布路由LSA 当做普通的节点间链路LSA 一样处理，纳入SPF 计算，作为重分布路由所在节点的特殊“下一跳”节点；

方式二：将重分布路由LSA 与普通的节点间链路LSA区分，先用节点间链路LSA 进行SPF 计算，获得全网节点的路由表（NodeRtTable）。再将重分布路由所在节点与NodeRtTable 比较，获得对应下一跳、开销等信息，从而生成重分布路由表（RedisRtTable）。

方式一将大大增加SPF 计算量，当重分布路由条目较多时，对CPU 计算资源和内存占用巨大，故采用方式二。

3.2 协议交互流程

LLSRP 协议的交互流程如图4 所示。

图4：协议交互流程图

协议包括4 种报文：

（1）邻居握手报文HELLO

用于建立和维护节点之间的邻居关系、检测与邻居节点的LSDB 同步状态；

（2）链路状态数据库摘要报文LSA_DD

用于描述本地LSDB 中LSA 条目的摘要信息；

（3）链路状态更新报文LSA_UPDATE

用于向邻居节点传递LSDB 条目的详细内容；

（4）链路状态更新确认LSA_ACK

用于对邻居的LSA_UPDATE 报文进行确认。

协议交互流程如下：

（1）节点之间通过HELLO 报文检测邻居状态，若检测到邻居的新增或删除、本地链路性能变化（如带宽）、本地重分布路由变化，则更新本地LSDB，并进入LSDB 同步流程，向所有邻居节点发送LSA_UPDATE 报文，广播变化的链路状态信息。

（2）节点收到LSA_UPDATE 报文后，更新本地LSDB，并向发送节点回复LSA_ACK 报文进行确认。

（3）节点之间通过HELLO 报文检测邻居节点与本节点的LSDB 标识是否相同。若不同，则进入LSDB 同步流程，向邻居节点发送LSA_DD 报文，描述本地LSDB 所有条目的摘要信息。

（4）节点收到LSA_DD报文后，与本节点的LSDB比对，将邻居节点缺少的链路状态信息通过LSA_UPDATE 发送给该邻居。

（5）当节点的邻居关系未发生变化，且所有邻居节点与本节点的链路状态数据库标识相同时，节点只周期性发送HELLO 报文。

3.3 邻居状态机

LLSRP 的邻居状态机如图5 所示。

图5：邻居状态机

LLSRP 有6 种邻居状态机，分别是：

Down：失效状态，还未交换信息。

Init：初始状态，表示已经收到了邻居的HELLO 报文，但是报文中没有列出本节点的router-ip，即邻居还没有收到本节点发出的Hello 报文。

2-Way：双向通信状态，双方都收到了对方发送的Hello报文，建立了双向邻居关系。

Exchange：信息交换阶段，节点将本地LSDB 所有条目用LSA_DD 描述发给邻居。同时，节点也会收到邻居发来的LSA_DD，如果节点发现本地LSDB 中存在邻居没有的LSA条目，在下一个阶段中将向邻居发送该条目的完整信息。

Loading：信息加载阶段，节点通过发送LSA_UPDATE向邻居发送该邻居没有的LSA 详细信息。邻居则回复LSA_ACK 进行确认。

Syn：同步状态，Loading 结束后，节点与邻居的LSDB达到同步。

3.4 协议内容

LLSRP协议通信采用网络层通信，使用网络层协议号（如195）标识协议，使用特定组播地址（如225.0.0.195）收发报文，TOS 值设为0xE0，以保证路由协议报文优先发送。表1 所列为各类型LLSRP 报文关键内容。

表1：协议内容

4 结果与展望

参照章节3 所述协议流程及报文内容，本文完成了一种LLSRP 的实现，并搭建了如图6 所示的实物验证环境。验证了该实现具备综合选路、链路优选、路由重分布功能，其网络开通时间不大于5 分钟，路由重新收敛时间不大于60s。

图6：实物验证拓扑

该协议具有OSPF 快速、稳定、可靠的优点，同时进行了协议流程与内容的简化，减少了协议的带宽开销、降低了配置复杂度，在带宽资源稀有的特殊环境下具有应用价值。