一種輕量化的鏈路狀態(tài)路由協(xié)議

陳澤嬋

（中國(guó)電子科技集團(tuán)公司第七研究所網(wǎng)絡(luò)交換事業(yè)部 廣東省廣州市 510310）

1 引言

戰(zhàn)術(shù)通信網(wǎng)絡(luò)具有機(jī)動(dòng)性高、抗毀能力強(qiáng)、帶寬消耗低等特殊應(yīng)用需求。當(dāng)前外軍戰(zhàn)術(shù)通信網(wǎng)路由協(xié)議主要采用基于鏈路狀態(tài)的OSPF路由協(xié)議，具有快速、可靠、穩(wěn)定等優(yōu)點(diǎn)。但鏈路狀態(tài)路由協(xié)議對(duì)CPU 的計(jì)算能力、內(nèi)存要求高，且需泛洪全網(wǎng)拓?fù)湫畔ⅲ瑢?duì)鏈路帶寬消耗較大。

為減少路由協(xié)議對(duì)鏈路帶寬資源的消耗，適應(yīng)有無(wú)線混雜、寬窄帶融合的復(fù)雜戰(zhàn)術(shù)環(huán)境，本文設(shè)計(jì)了一種輕量化的鏈路狀態(tài)路由協(xié)議，下文簡(jiǎn)稱LLSRP（Lightweight Link State Routing Protocol）。

2 總體設(shè)計(jì)

路由應(yīng)具備綜合選路、路由重分布能力，同時(shí)重點(diǎn)進(jìn)行協(xié)議的輕量化設(shè)計(jì)。

2.1 輕量化設(shè)計(jì)思路

在進(jìn)行路由協(xié)議的輕量化設(shè)計(jì)時(shí)，通過(guò)簡(jiǎn)化協(xié)議交互流程、減少數(shù)據(jù)包內(nèi)容等方面降低路由協(xié)議運(yùn)行時(shí)的帶寬占用。此外，增量更新、聚合發(fā)送、同步校驗(yàn)、握手時(shí)間自調(diào)節(jié)等方式將進(jìn)一步壓縮協(xié)議帶寬開(kāi)銷。

增量更新：當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，只擴(kuò)散變化的鏈路狀態(tài)通告；

聚合發(fā)送：當(dāng)節(jié)點(diǎn)需要發(fā)送鏈路狀態(tài)更新或確認(rèn)報(bào)文時(shí)，延遲一小段時(shí)間再集中發(fā)送，從而減少路由報(bào)文占用信道發(fā)送次數(shù)；

同步校驗(yàn)：不進(jìn)行鏈路狀態(tài)數(shù)據(jù)庫(kù)的老化和定期刷新，通過(guò)握手報(bào)文中的本地鏈路狀態(tài)數(shù)據(jù)庫(kù)標(biāo)識(shí)信息（鏈路狀態(tài)數(shù)據(jù)庫(kù)的校驗(yàn)值）確保鏈路狀態(tài)數(shù)據(jù)庫(kù)同步；

握手時(shí)間自調(diào)節(jié)：根據(jù)無(wú)線子網(wǎng)內(nèi)鄰居狀態(tài)自適應(yīng)調(diào)節(jié)握手報(bào)文發(fā)送周期，初始嘗試建立鄰居關(guān)系時(shí)，采用較短的握手時(shí)間間隔，當(dāng)鄰居關(guān)系建立完成，采用較長(zhǎng)的握手時(shí)間間隔。

2.2 功能模塊

LLSRP 與外部模塊之間的關(guān)系如圖1、內(nèi)部軟件模塊結(jié)構(gòu)見(jiàn)圖2。

圖1：LLSRP 與外部模塊關(guān)系圖

圖2：LLSRP 軟件模塊圖

各個(gè)節(jié)點(diǎn)的LLSRP 模塊通過(guò)底層物理信道建立并維護(hù)鄰居關(guān)系、獲得鏈路狀態(tài)與資源等信息；路由管理模塊可將其他路由協(xié)議的路由表導(dǎo)入LLSRP 模塊，支撐LLSRP 的路由重分布功能。

LLSRP 模塊由鄰居維護(hù)、LSDB 同步、路由計(jì)算模塊組成。

運(yùn)行LLSRP 的網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)維護(hù)3 張表：鄰居表、鏈路狀態(tài)數(shù)據(jù)庫(kù)、路由表。

（1）鄰居列表：列出節(jié)點(diǎn)全部鄰居信息；

（2）鏈路狀態(tài)數(shù)據(jù)庫(kù)：列出網(wǎng)絡(luò)中鏈路和資源信息，保存了全網(wǎng)的拓?fù)湫畔ⅲ?/p>

（3）路由表：列出到達(dá)每個(gè)相連節(jié)點(diǎn)和網(wǎng)絡(luò)的最短路徑。

鄰居維護(hù)模塊構(gòu)建并維護(hù)鄰居表。通過(guò)握手協(xié)議、鏈路通斷狀態(tài)進(jìn)行鄰居增刪；獲取鏈路帶寬等資源信息；進(jìn)行鄰居同步檢測(cè)，比較本地與鄰居的LSDB 標(biāo)識(shí)，不一致時(shí)觸發(fā)LSDB 同步流程。

LSDB 同步模塊構(gòu)建并維護(hù)鏈路狀態(tài)數(shù)據(jù)庫(kù)，采取增量更新、廣播泛洪、聚合發(fā)送等方式降低協(xié)議開(kāi)銷。

路由計(jì)算模塊構(gòu)建并維護(hù)本地的LLSRP 路由表，包括LLSRP 節(jié)點(diǎn)路由表及LLSRP 重分布路由表，其核心算法是最短路徑算法SPF。

3 協(xié)議描述

3.1 協(xié)議工作過(guò)程

通過(guò)運(yùn)行LLSRP 協(xié)議可以完成混合組網(wǎng)下的整網(wǎng)路由收斂，實(shí)現(xiàn)數(shù)據(jù)業(yè)務(wù)最短路徑轉(zhuǎn)發(fā)，其基本步驟如圖3。

圖3：LLSRP 工作流程圖

LLSRP 模塊通過(guò)周期性握手協(xié)議建立并維護(hù)鄰居表；經(jīng)由鄰居逐跳泛洪鏈路狀態(tài)通告，形成全網(wǎng)同步的鏈路狀態(tài)數(shù)據(jù)庫(kù)（LSDB）；每個(gè)節(jié)點(diǎn)根據(jù)鏈路狀態(tài)數(shù)據(jù)庫(kù)，采用最短路徑算法SPF 計(jì)算出全網(wǎng)可達(dá)節(jié)點(diǎn)的LLSRP 節(jié)點(diǎn)路由表；通過(guò)重分布路由所在節(jié)點(diǎn)位置及LLSRP 節(jié)點(diǎn)路由表生成重分布路由表；將節(jié)點(diǎn)路由表及重分布路由表合并，即是本地LLSRP 路由表。

3.1.1 鄰接關(guān)系建立與維護(hù)

HELLO 協(xié)議用于維護(hù)LLSRP 的鄰居關(guān)系，作用是建立、維護(hù)鄰居關(guān)系和檢查L(zhǎng)SDB 同步狀態(tài)。節(jié)點(diǎn)周期性發(fā)送HELLO 報(bào)文。報(bào)文中攜帶了發(fā)送節(jié)點(diǎn)的鄰居列表，接收節(jié)點(diǎn)通過(guò)HELLO 報(bào)文中攜帶的鄰居列表進(jìn)行信道狀態(tài)的判斷，如果鄰居列表中含有本節(jié)點(diǎn)信息，則為雙向信道，否則為單向信道。節(jié)點(diǎn)必須從鄰居收到3 次HELLO 報(bào)文方可建立雙向鄰居關(guān)系。

在穩(wěn)定狀態(tài)下，通過(guò)HELLO 報(bào)文維護(hù)鄰居信息。HELLO 報(bào)文發(fā)送時(shí)間間隔缺省值取10s。

鄰居關(guān)系需要?jiǎng)討B(tài)維護(hù)，如果在規(guī)定的保持時(shí)間內(nèi)（3次HELLO 發(fā)送間隔）沒(méi)有收到某一鄰居的HELLO 報(bào)文或者其他類型報(bào)文，則認(rèn)為此鄰居不可達(dá)，相應(yīng)地要?jiǎng)h除與該鄰居相關(guān)的鏈路狀態(tài)信息，并向其它鄰居發(fā)送相關(guān)鏈路狀態(tài)更新信息。

HELLO 報(bào)文發(fā)送的周期動(dòng)態(tài)調(diào)整，在網(wǎng)絡(luò)初始化時(shí)以較小的HELLO 間隔周期發(fā)送從而快速立鄰居關(guān)系；在網(wǎng)絡(luò)穩(wěn)定后，則以較大的Hello 間隔周期發(fā)送。在網(wǎng)絡(luò)穩(wěn)定后，若節(jié)點(diǎn)發(fā)現(xiàn)了新鄰居，會(huì)觸發(fā)HELLO 報(bào)文的立即發(fā)送，無(wú)論HELLO 間隔是否到期。

當(dāng)節(jié)點(diǎn)獲取新鄰居后，若發(fā)現(xiàn)自身不在鄰居的鄰居表內(nèi)，則立即觸發(fā)HELLO 報(bào)文以加快節(jié)點(diǎn)間的鄰居關(guān)系建立。

HELLO 報(bào)文中攜帶有LSDB 標(biāo)識(shí)，可檢測(cè)本地和鄰居節(jié)點(diǎn)的鏈路狀態(tài)數(shù)據(jù)庫(kù)是否同步。

3.1.2 鏈路狀態(tài)數(shù)據(jù)庫(kù)同步

LLSRP 對(duì)同步LSDB 流程進(jìn)行了簡(jiǎn)化。

（1）不進(jìn)行DR/BDR 選舉，充分利用無(wú)線信道廣播的特性，減少報(bào)文占用信道的發(fā)送次數(shù)。鄰居之間處于對(duì)等關(guān)系，通過(guò)HELLO 報(bào)文中的LSDB 標(biāo)識(shí)確保與所有鄰居的LSBD 同步。

（2）不進(jìn)行鏈路狀態(tài)請(qǐng)求，開(kāi)始同步鏈路狀態(tài)數(shù)據(jù)庫(kù)流程時(shí)，將本地鏈路狀態(tài)數(shù)據(jù)庫(kù)所有鏈路狀態(tài)通告（LSA）的摘要信息封裝為L(zhǎng)SA_DD 報(bào)文，向鄰居節(jié)點(diǎn)發(fā)送。鄰居節(jié)點(diǎn)將摘要列表與其LSDB 比較，即可獲得本節(jié)點(diǎn)缺少的LSA 條目，將這些LSA 詳細(xì)信息通過(guò)LSA_UPDATE 發(fā)送給本節(jié)點(diǎn)。

在下列情況下，LLSRP 進(jìn)程新增、刪除或更新鏈路狀態(tài)數(shù)據(jù)庫(kù)：

新增或刪除鄰居節(jié)點(diǎn)；

鏈路通斷狀態(tài)或性能（如帶寬）變化；

收到鏈路狀態(tài)更新報(bào)文。

3.1.3 路由計(jì)算

LLSRP 協(xié)議采用最短路徑優(yōu)先算法SPF（即Dijkstra 算法）計(jì)算本地路由表。

路由計(jì)算時(shí)，總的路由代價(jià)Cost為各段鏈路代價(jià)Cost之和：

Cost=∑Cost

鏈路代價(jià)計(jì)算公式如下：

其中，bw 為鏈路出口帶寬，可由管理員人工配置，也可根據(jù)鏈路出站帶寬、鏈路類型、節(jié)點(diǎn)類型自動(dòng)獲得。

為適應(yīng)多種類型信道并存的網(wǎng)絡(luò)環(huán)境，對(duì)特殊信道類型的鏈路開(kāi)銷應(yīng)進(jìn)行針對(duì)設(shè)計(jì)，如空地鏈路和衛(wèi)星鏈路。

空中節(jié)點(diǎn)到地面節(jié)點(diǎn)的拓?fù)潢P(guān)系為點(diǎn)到多點(diǎn)，計(jì)算鏈路代價(jià)時(shí)需根據(jù)空中節(jié)點(diǎn)連通的地面節(jié)點(diǎn)數(shù)量（N 個(gè)）對(duì)總帶寬資源（BW）進(jìn)行平均分配，計(jì)算公式如下：

bw= BW/N

衛(wèi)星鏈路具有帶寬較寬，時(shí)延較大的特點(diǎn)，在路由協(xié)議中衛(wèi)星鏈路代價(jià)需同時(shí)考慮帶寬及時(shí)延，計(jì)算公式如下：

外部路由代價(jià)值(Cost)在LLSRP 網(wǎng)內(nèi)傳播時(shí)不變化。當(dāng)參與本地計(jì)算時(shí)，總的代價(jià)值為外部路由代價(jià)值和內(nèi)部鏈路代價(jià)值之和，計(jì)算公式如下：

3.1.4 構(gòu)建重分布路由表

可通過(guò)2 種方式計(jì)算重分布路由。

方式一：將重分布路由LSA 當(dāng)做普通的節(jié)點(diǎn)間鏈路LSA 一樣處理，納入SPF 計(jì)算，作為重分布路由所在節(jié)點(diǎn)的特殊“下一跳”節(jié)點(diǎn)；

方式二：將重分布路由LSA 與普通的節(jié)點(diǎn)間鏈路LSA區(qū)分，先用節(jié)點(diǎn)間鏈路LSA 進(jìn)行SPF 計(jì)算，獲得全網(wǎng)節(jié)點(diǎn)的路由表（NodeRtTable）。再將重分布路由所在節(jié)點(diǎn)與NodeRtTable 比較，獲得對(duì)應(yīng)下一跳、開(kāi)銷等信息，從而生成重分布路由表（RedisRtTable）。

方式一將大大增加SPF 計(jì)算量，當(dāng)重分布路由條目較多時(shí)，對(duì)CPU 計(jì)算資源和內(nèi)存占用巨大，故采用方式二。

3.2 協(xié)議交互流程

LLSRP 協(xié)議的交互流程如圖4 所示。

圖4：協(xié)議交互流程圖

協(xié)議包括4 種報(bào)文：

（1）鄰居握手報(bào)文HELLO

用于建立和維護(hù)節(jié)點(diǎn)之間的鄰居關(guān)系、檢測(cè)與鄰居節(jié)點(diǎn)的LSDB 同步狀態(tài)；

（2）鏈路狀態(tài)數(shù)據(jù)庫(kù)摘要報(bào)文LSA_DD

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

（3）鏈路狀態(tài)更新報(bào)文LSA_UPDATE

用于向鄰居節(jié)點(diǎn)傳遞LSDB 條目的詳細(xì)內(nèi)容；

（4）鏈路狀態(tài)更新確認(rèn)LSA_ACK

用于對(duì)鄰居的LSA_UPDATE 報(bào)文進(jìn)行確認(rèn)。

協(xié)議交互流程如下：

（1）節(jié)點(diǎn)之間通過(guò)HELLO 報(bào)文檢測(cè)鄰居狀態(tài)，若檢測(cè)到鄰居的新增或刪除、本地鏈路性能變化（如帶寬）、本地重分布路由變化，則更新本地LSDB，并進(jìn)入LSDB 同步流程，向所有鄰居節(jié)點(diǎn)發(fā)送LSA_UPDATE 報(bào)文，廣播變化的鏈路狀態(tài)信息。

（2）節(jié)點(diǎn)收到LSA_UPDATE 報(bào)文后，更新本地LSDB，并向發(fā)送節(jié)點(diǎn)回復(fù)LSA_ACK 報(bào)文進(jìn)行確認(rèn)。

（3）節(jié)點(diǎn)之間通過(guò)HELLO 報(bào)文檢測(cè)鄰居節(jié)點(diǎn)與本節(jié)點(diǎn)的LSDB 標(biāo)識(shí)是否相同。若不同，則進(jìn)入LSDB 同步流程，向鄰居節(jié)點(diǎn)發(fā)送LSA_DD 報(bào)文，描述本地LSDB 所有條目的摘要信息。

（4）節(jié)點(diǎn)收到LSA_DD報(bào)文后，與本節(jié)點(diǎn)的LSDB比對(duì)，將鄰居節(jié)點(diǎn)缺少的鏈路狀態(tài)信息通過(guò)LSA_UPDATE 發(fā)送給該鄰居。

（5）當(dāng)節(jié)點(diǎn)的鄰居關(guān)系未發(fā)生變化，且所有鄰居節(jié)點(diǎn)與本節(jié)點(diǎn)的鏈路狀態(tài)數(shù)據(jù)庫(kù)標(biāo)識(shí)相同時(shí)，節(jié)點(diǎn)只周期性發(fā)送HELLO 報(bào)文。

3.3 鄰居狀態(tài)機(jī)

LLSRP 的鄰居狀態(tài)機(jī)如圖5 所示。

圖5：鄰居狀態(tài)機(jī)

LLSRP 有6 種鄰居狀態(tài)機(jī)，分別是：

Down：失效狀態(tài)，還未交換信息。

Init：初始狀態(tài)，表示已經(jīng)收到了鄰居的HELLO 報(bào)文，但是報(bào)文中沒(méi)有列出本節(jié)點(diǎn)的router-ip，即鄰居還沒(méi)有收到本節(jié)點(diǎn)發(fā)出的Hello 報(bào)文。

2-Way：雙向通信狀態(tài)，雙方都收到了對(duì)方發(fā)送的Hello報(bào)文，建立了雙向鄰居關(guān)系。

Exchange：信息交換階段，節(jié)點(diǎn)將本地LSDB 所有條目用LSA_DD 描述發(fā)給鄰居。同時(shí)，節(jié)點(diǎn)也會(huì)收到鄰居發(fā)來(lái)的LSA_DD，如果節(jié)點(diǎn)發(fā)現(xiàn)本地LSDB 中存在鄰居沒(méi)有的LSA條目，在下一個(gè)階段中將向鄰居發(fā)送該條目的完整信息。

Loading：信息加載階段，節(jié)點(diǎn)通過(guò)發(fā)送LSA_UPDATE向鄰居發(fā)送該鄰居沒(méi)有的LSA 詳細(xì)信息。鄰居則回復(fù)LSA_ACK 進(jìn)行確認(rèn)。

Syn：同步狀態(tài)，Loading 結(jié)束后，節(jié)點(diǎn)與鄰居的LSDB達(dá)到同步。

3.4 協(xié)議內(nèi)容

LLSRP協(xié)議通信采用網(wǎng)絡(luò)層通信，使用網(wǎng)絡(luò)層協(xié)議號(hào)（如195）標(biāo)識(shí)協(xié)議，使用特定組播地址（如225.0.0.195）收發(fā)報(bào)文，TOS 值設(shè)為0xE0，以保證路由協(xié)議報(bào)文優(yōu)先發(fā)送。表1 所列為各類型LLSRP 報(bào)文關(guān)鍵內(nèi)容。

表1：協(xié)議內(nèi)容

4 結(jié)果與展望

參照章節(jié)3 所述協(xié)議流程及報(bào)文內(nèi)容，本文完成了一種LLSRP 的實(shí)現(xiàn)，并搭建了如圖6 所示的實(shí)物驗(yàn)證環(huán)境。驗(yàn)證了該實(shí)現(xiàn)具備綜合選路、鏈路優(yōu)選、路由重分布功能，其網(wǎng)絡(luò)開(kāi)通時(shí)間不大于5 分鐘，路由重新收斂時(shí)間不大于60s。

圖6：實(shí)物驗(yàn)證拓?fù)?/p>

該協(xié)議具有OSPF 快速、穩(wěn)定、可靠的優(yōu)點(diǎn)，同時(shí)進(jìn)行了協(xié)議流程與內(nèi)容的簡(jiǎn)化，減少了協(xié)議的帶寬開(kāi)銷、降低了配置復(fù)雜度，在帶寬資源稀有的特殊環(huán)境下具有應(yīng)用價(jià)值。