卓廣平

?

下一代互聯(lián)網(wǎng)動(dòng)態(tài)路由協(xié)議機(jī)制分析與改進(jìn)策略

卓廣平

（太原師范學(xué)院 計(jì)算機(jī)系，山西 太原 030619）

隨著互聯(lián)網(wǎng)應(yīng)用需求方式、種類及各種性能的不斷涌現(xiàn)，現(xiàn)在的Internet正在向下一代互聯(lián)網(wǎng)發(fā)展和過渡。作為互聯(lián)網(wǎng)體系結(jié)構(gòu)的關(guān)鍵層次——網(wǎng)際層，其核心組成部分之一的動(dòng)態(tài)路由協(xié)議協(xié)議現(xiàn)已成為園區(qū)網(wǎng)、城域網(wǎng)、廣域網(wǎng)等設(shè)計(jì)組建中廣泛使用和首選的進(jìn)行路由選擇和轉(zhuǎn)發(fā)功能的協(xié)議，并且也處于不斷更新和發(fā)展的過程中。本論文闡述了動(dòng)態(tài)路由協(xié)議中基于Dijkstra提出的最短路徑優(yōu)先算法的設(shè)計(jì)思想并對(duì)協(xié)議本身進(jìn)行了較為深入的分析和動(dòng)態(tài)示例。最后，對(duì)在新一代互聯(lián)網(wǎng)中該協(xié)議在算法復(fù)雜度、消息傳遞復(fù)雜度以及IPv6的適應(yīng)性方面進(jìn)行了部分優(yōu)化與改進(jìn)的設(shè)想。

下一代互聯(lián)網(wǎng)；網(wǎng)絡(luò)體系結(jié)構(gòu)；最短路徑優(yōu)先；動(dòng)態(tài)路由協(xié)議

0 引言

在計(jì)算機(jī)網(wǎng)絡(luò)中，作為網(wǎng)絡(luò)的核心部件——路由器主要功能體現(xiàn)在網(wǎng)絡(luò)層（或說網(wǎng)際層、IP層），而在整個(gè)網(wǎng)絡(luò)中，路由器從網(wǎng)絡(luò)的連通性、安全性以及高效性等視角來說，其核心地位是顯而易見的。它來負(fù)責(zé)不同區(qū)域的網(wǎng)絡(luò)連通，跨區(qū)域間的存儲(chǔ)轉(zhuǎn)發(fā)，高效的查詢傳遞，準(zhǔn)確地交付目的主機(jī)等功能。在路由工作中，目前廣泛使用既高效又穩(wěn)定的動(dòng)態(tài)路由協(xié)議是開放最短路徑優(yōu)先協(xié)議——OSPFv2（及支持下一代互聯(lián)網(wǎng)的OSPFv3）。

1 網(wǎng)絡(luò)路由及實(shí)現(xiàn)的主要協(xié)議

在計(jì)算機(jī)網(wǎng)絡(luò)中，作為網(wǎng)絡(luò)的核心部件——路由器主要功能體現(xiàn)在網(wǎng)絡(luò)層（或說網(wǎng)際層、IP層），而在整個(gè)網(wǎng)絡(luò)中，路由器從網(wǎng)絡(luò)的連通性、安全性以及高效性等視角來說，其核心地位是顯而易見的。它來負(fù)責(zé)不同區(qū)域的網(wǎng)絡(luò)連通，跨區(qū)域間的存儲(chǔ)轉(zhuǎn)發(fā)，高效的查詢傳遞，準(zhǔn)確地交付目的主機(jī)等功能。在路由工作中，目前廣泛使用既高效又穩(wěn)定的動(dòng)態(tài)路由協(xié)議是開放最短路徑優(yōu)先協(xié)議——OSPFv2（及支持下一代互聯(lián)網(wǎng)的OSPFv3）。

OSPF（Open Shortest Path First）路由協(xié)議[1]是開放式最短路徑優(yōu)先協(xié)議，也是一種十分典型的基于鏈路狀態(tài)（Link-state）算法的路由協(xié)議，旨在提升算法的收斂速度，使得可以快速適應(yīng)網(wǎng)絡(luò)變化，能夠在短時(shí)間內(nèi)將網(wǎng)絡(luò)變化后的全網(wǎng)一致的信息——鏈路狀態(tài)數(shù)據(jù)庫(kù)發(fā)送至網(wǎng)絡(luò)中的每一臺(tái)路由設(shè)備，同時(shí)保證網(wǎng)絡(luò)的穩(wěn)定性與快速收斂性。1988年，RFC成立了OSPF的研究小組，最終于1998年4月以標(biāo)準(zhǔn)形式出現(xiàn)了OSPF協(xié)議第二版（OSPFv2），它是基于IPV4的，目的是為了解決RIP協(xié)議的網(wǎng)絡(luò)規(guī)模受限、收斂速度慢等缺陷。它的核心思想之一是每個(gè)路由器在得到更新的鏈路狀態(tài)數(shù)據(jù)庫(kù)之后，就默認(rèn)為自己為根，進(jìn)而構(gòu)造最短的路徑樹——SPANNING TREE，把網(wǎng)絡(luò)中的所有其它網(wǎng)絡(luò)結(jié)點(diǎn)納入其中。OSPF路由器間彼此交換各自的鏈路狀態(tài)信息，并迅速達(dá)到全網(wǎng)一致的狀態(tài)，這也是OSPF廣泛使用的重要原因之一。最終，路由表通過計(jì)算得出是可以用于實(shí)現(xiàn)AS（自治系統(tǒng)）區(qū)域的通信。

2 動(dòng)態(tài)路由計(jì)算過程及分析

在配置OSPF協(xié)議的局域網(wǎng)中，路由的功能并不是說簡(jiǎn)單的把兩個(gè)節(jié)點(diǎn)或者區(qū)域內(nèi)所有節(jié)點(diǎn)連通，是需要從多因素出發(fā)考慮計(jì)算出一條最佳路徑。整個(gè)OSPF路由計(jì)算過程可分為：

1. 路由器接口間發(fā)送hello報(bào)文建立鄰接關(guān)系；

2. DR與BDR的選舉；

3. 路由器通過LSA信息獲得網(wǎng)絡(luò)拓?fù)洌?/p>

4. 路由表的計(jì)算與建立；

2.1 鄰接關(guān)系的建立

2.1.1 鄰接關(guān)系建立過程

建立鄰接關(guān)系，首先要說明的是“鄰接關(guān)系”并不是“鄰居關(guān)系”，這是兩種不一樣的狀態(tài)，只有在先建立了“鄰居關(guān)系”后，才有可能建立“鄰接關(guān)系”。所以先來描述下“鄰居關(guān)系”，鄰居關(guān)系的建立指的是，在初始情況下，路由A、路由B指定接口開啟了OSPF協(xié)議后，都會(huì)開始在這個(gè)接口上去發(fā)組播的OSPF Hello包，目的是為了發(fā)現(xiàn)OSPF鄰居。在Hello包中，active neighbor活躍鄰居字段，雖然是用來存儲(chǔ)路由器在某個(gè)路由接口上發(fā)現(xiàn)的neighbor，但是在初始環(huán)境下，Hello包里是沒有活躍鄰居的。

OSPF路由器B收到鄰居發(fā)來的Hello包，它會(huì)記錄下是誰(shuí)發(fā)來的并將該路由器的狀態(tài)視為init，自己將發(fā)送出去的hello包中的active eighbor中包含該路由器的Router-ID。該路由器收到包后識(shí)別出自己的Router-ID，此時(shí)兩臺(tái)路由器的狀態(tài)變?yōu)閠wo- way。此時(shí)僅為單方向的鄰居關(guān)系已經(jīng)建立，若要建立雙向的鄰居關(guān)系需要重復(fù)上述過程，使得另外一臺(tái)路由器達(dá)到two-way的狀態(tài)。至此OSPF的第一個(gè)穩(wěn)態(tài)就達(dá)到了。雙方成功交換DD（Database Description，數(shù)據(jù)庫(kù)描述）報(bào)文，交換LSA并達(dá)到LSDB的同步之后，才形成真正意義上的鄰接關(guān)系（hello包的期限是40s，超出后視為這條通道無效）。

進(jìn)而進(jìn)入ex-start狀態(tài)，以及Master、Slave的協(xié)商，Router-ID是決定成為Master還是Slave的因素，較大的成為Master，相對(duì)的接口為Slave。這里要注意Master不是DR。M/S協(xié)商過程中使用的是BDB包，這個(gè)包當(dāng)中，有三個(gè)關(guān)鍵位I、M、MS。

當(dāng)OSPF接口收到一個(gè)DBD包，其中I位置0，表明與鄰居的ex-start階段已經(jīng)結(jié)束，從而將鄰居的狀態(tài)置為ex-change，并且存儲(chǔ)LSA 頭部，是由DBD包發(fā)送的，同時(shí)發(fā)送OSPF Database（DB）給鄰居，這樣兩臺(tái)路由都能交互，了解對(duì)方的DB內(nèi)容。在這個(gè)過程中不止交換一次DBD報(bào)文，這些報(bào)文的I位0，且M位是1。除非是OSPF接口發(fā)送的最后一個(gè)DBD包。

當(dāng)路由器收到DBD包，且M偎置為0，說明這是鄰居發(fā)來的最后的DBD包，當(dāng)搜集完其中的內(nèi)容后，如果發(fā)現(xiàn)有興趣的LSA，需要獲得更加詳細(xì)的LSA的信息時(shí)，則對(duì)端置為L(zhǎng)oading狀態(tài)。此時(shí)A發(fā)送LSR報(bào)文，以求交換完整數(shù)據(jù)包LSR LSU，B在收到請(qǐng)求后，通過LSU報(bào)文給予回應(yīng)，發(fā)送出A請(qǐng)求的詳細(xì)的LSA的完整的內(nèi)容與信息，當(dāng)A收到LSU后，將詳細(xì)信息放入自己的LSDB，回應(yīng)B進(jìn)行確認(rèn)通過Lsack。OSPF所有的接口的所有的LSA信息全部接收到最新的狀態(tài)下，所有的鄰居置為FULL狀態(tài)。OSPF鄰接關(guān)系也正式建立。

2.1.2 鄰接關(guān)系建立的8種狀態(tài)

路由器在配置OSPF路由協(xié)議之后，需要建立鄰接狀態(tài)來實(shí)現(xiàn)相互之間跨區(qū)域的通信，在這個(gè)過程中會(huì)有八種狀態(tài)，詳解如表1所示。

2.2 DR和BDR選舉

OSPF協(xié)議定義[2-4]了指定路由器DR（Designated Router）僅在廣播網(wǎng)和NBMA網(wǎng)絡(luò)中，網(wǎng)絡(luò)中同一自治區(qū)域內(nèi)的路由器兩兩實(shí)現(xiàn)通信，這便需要建立n(n-1)/2個(gè)鄰居，是為了解決在不斷更新的路由信息與鏈路信息所造成的傳遞更新的過程中的帶寬浪費(fèi)。所有的路由信息的更新全部發(fā)送給DR，再由DR將路由信息與鏈路狀態(tài)發(fā)送給其他的路由器。

表1 鄰接關(guān)系建立的8種狀態(tài)及說明

Tab.1 8 states and descriptions of the establishment of adjacency relationship

如果制定的DR路由器發(fā)生意外故障，則區(qū)域內(nèi)的所有路由器將會(huì)重新選舉出新的DR。這段時(shí)間較長(zhǎng)，并且還會(huì)影響路由器的正常工作，為了解決或者縮短這個(gè)不正常過程的時(shí)間，提出了BDR（Backup Designated Router，備份指定路由器）的概念。

BDR實(shí)際上是DR的替代品，在選舉DR的同時(shí)BDR也同時(shí)被選舉出來。由于DR與BDR在被選舉出來后，都會(huì)與所有的路由器建立鄰接狀態(tài)并且實(shí)時(shí)交換更新信息。當(dāng)DR故障后，BDR瞬間變成DR，繼續(xù)實(shí)施轉(zhuǎn)發(fā)的任務(wù)，不會(huì)影響工作的正常進(jìn)行，在這個(gè)過程中，也會(huì)選舉出另外的BDR，以備不時(shí)之需。

DR和BDR之外的路由器稱為DR Other之間將不再建立鄰接關(guān)系，也不會(huì)再次交換任何路由信息。

當(dāng)網(wǎng)絡(luò)中接入新的路由器，并且激活了新的接口，也不會(huì)重新選舉DR與BDR，前提是已存在DR與BDR。它會(huì)自動(dòng)接受原有的DR與BDR。如果沒有，則會(huì)重新選舉。

選舉過程是以優(yōu)先級(jí)大小來確認(rèn)的，在優(yōu)先級(jí)相同的情況下，Router-ID成為新的標(biāo)準(zhǔn)，數(shù)值越高的將會(huì)成為DR，如果僅是無BDR則僅僅需要選舉BDR，過程同上，且新進(jìn)的路由器接口也具有資格。

2.3 傳遞LSA

LSA（Link State Advertisement）鏈路狀態(tài)廣播數(shù)據(jù)，OSPF協(xié)議通過LSA將所有的信息更新傳遞到網(wǎng)絡(luò)中的路由器中。這是與RIP距離矢量路由協(xié)議的根本不同。距離矢量路由協(xié)議傳送的是路由表，OSPF會(huì)建立動(dòng)態(tài)的狀態(tài)數(shù)據(jù)庫(kù)來尋出接口的狀態(tài)，生成最短路經(jīng)樹，進(jìn)而構(gòu)造路由表。

2.3.1 LSA分析

LSA都包含序列號(hào)，校驗(yàn)以及老化時(shí)間。路由器發(fā)送的LSA的序號(hào)越大則視為越新，在每次發(fā)送的LSA序列號(hào)都會(huì)加1，標(biāo)志著是最新的信息。

LSDB是存放LSA的動(dòng)態(tài)數(shù)據(jù)庫(kù)，5 min對(duì)LSA 進(jìn)行一次校驗(yàn)，以確保LSA未損壞。一條LSA都是具有老化時(shí)間，如果在LSDB中，LSA一直未重新發(fā)送，也就是老化時(shí)間從未設(shè)置為0，在累計(jì)到1 h之后，便自動(dòng)從LSDB中清除，這個(gè)時(shí)間的累計(jì)是由每個(gè)路由器中的InfTranDelay來實(shí)現(xiàn)操作。在配置有OSPF的網(wǎng)絡(luò)中，只有始發(fā)路由可以設(shè)置時(shí)間，來使得LSA手動(dòng)的失效，清除出LSDB，方法是設(shè)置時(shí)間，將時(shí)間設(shè)置的無限大。

LSA的會(huì)接受到路由器的確認(rèn)，確認(rèn)方式有顯示與陰式兩種。然后才會(huì)用LSAck進(jìn)行回應(yīng)，LSAck僅包含LSA頭部，這是顯示確認(rèn)。陰式確認(rèn)相對(duì)復(fù)雜，需要始發(fā)路由器收到包含LSA信息的數(shù)據(jù)包來確認(rèn)。

2.3.2 LSA種類

OSPF的LSA類型種類繁多，我們不得不對(duì)它進(jìn)行研究。OSPF的LSA類型一共有11種分別是：

LSA1 路由器LSA（Router LSA）

LSA2 網(wǎng)絡(luò)LSA（Network LSA）

LSA3 網(wǎng)絡(luò)匯總LSA（Network summary LSA）

LSA4 ASBR匯總LSA（ASBR summary LSA）

LSA5 自治系統(tǒng)外部LSA（Autonomous system external LSA）

LSA6 組成員LSA （Group membership LSA）

LSA7 NSSA外部LSA （NSSA External LSA）

LSA8 BGP的外部屬性LSA（External attributes LSA for BGP）

LSA9 不透明LSA（本地鏈路范圍）（opaque LSA）

LSA10 不透明LSA（本地區(qū)域范圍）（opaque LSA）

LSA11 不透明LSA（AS范圍）（opaque LSA）

在這11種LSA中，我們主要研究LSA1、LSA2、LSA3、LSA4、LSA5、LSA7。

表2 LSA的11種類型

Tab.2 11 types of LSA

2.4 OSPF路由表的計(jì)算

2.4.1 Dijkstra的最短路徑優(yōu)先算法的計(jì)算流程與基本算法

圖1 最短路徑優(yōu)先算法流程

基本的核心算法如下：

1 Initialization

2 N={A}

3 for all nodes v

4 if v adjacent to A

5 then D(v)= c(A,v)

6 else D(v)= infinity

7

8 Loop

9 find w not in N such that D(w) is a minmum

10 add w to n

11 update D(v) for all v adjacent to w and not in n;

12 D(v)= min(D(v),D(w)+c(w,v))

13 /*new cost to v is either old cost to v or known

14 shortest path cost to w plus cost from w to v*

15 until all nodes in N

在Dijkstra計(jì)算中，每個(gè)路由器維護(hù)了兩個(gè)列表：

a. PATH list,是一個(gè)節(jié)點(diǎn)列表，叫做路徑類列表，存放路徑中的每個(gè)節(jié)點(diǎn)。

b. 可能在也可能不在到達(dá)目的地的最短路徑上的下一跳類表，這個(gè)表稱為TENTative或TENT列表。

2.4.2 Dijkstra最短路徑優(yōu)先算法的實(shí)例：

計(jì)算圖中路由器A的路由表項(xiàng)。

圖2 路由拓?fù)鋱D例

（1）把自己加入PATH列表中，距離為0，下一跳是自己。路由器A的數(shù)據(jù)庫(kù)如下表：

PATHTENT {A,0,0}{empty}

（2）將鄰居B、C和D加入TENT列表中，下一跳為自己。

PATHTENT {A,0,0}{B,6,B} {C,3,C} {D,2,D}

（3）D的代價(jià)小于C的3和B的6，將{D,2, D}移到PATH列表中。

PATHTENT {A,0,0}{B,6,B} {D,2,D}{C,3,C}

（4）檢查D的鄰居。路由D到C的鏈路代價(jià)是5，A-D-C的代價(jià)為2+5=7，大于A-C-C的代價(jià)3，所以將{C,3,C}加入到PATH列表中：

PATHTENT {A,0,0}{B,6,B} {D,2,D} {C,3,C}

（5）檢查C的鄰居。路由C到B的鏈路代價(jià)是2，A-C-B的代價(jià)為3+2=5，小于A-B-B的代價(jià)6，所以在TENT列表中刪除{B,6,B}，添加{B,5,C}：

PATHTENT {A,0,0}{B,6,B} {D,2,D}{B,5,C} {C,3,C}

（6）將{B,5,C}加入PATH列表，這時(shí)A的所有列表已經(jīng)在PATH列表中了，TENT列表為NULL，停止計(jì)算：

PATHTENT {A,0,0} {D,2,D} {C,3,C} {B,5,C}

（7）這時(shí)候A的PATH列表就成了它的路由表項(xiàng)：

結(jié)點(diǎn)代價(jià)下一跳 A0Self B5C C3Connected D2Connected

2.4.3 路由表數(shù)據(jù)結(jié)構(gòu)

路由表數(shù)據(jù)結(jié)構(gòu)包含的內(nèi)容：目的地址、目的類型、目的網(wǎng)絡(luò)掩碼、接口標(biāo)識(shí)、域標(biāo)識(shí)、路徑類型、路由度量、鏈路狀態(tài)標(biāo)識(shí)、下一跳等。由于路由表是路由器轉(zhuǎn)發(fā)包任務(wù)的唯一依據(jù)，其重要性無需更多的描述。再轉(zhuǎn)發(fā)包信息的時(shí)候，通過路由表，將目的信息同表進(jìn)行對(duì)比，找到最佳匹配的路由條目，從而決定路由策略。

2.4.4 路由表的計(jì)算過程

有關(guān)路由表的計(jì)算是OSPF最為核心的部分[5]。是生成動(dòng)態(tài)的內(nèi)核路由表的基礎(chǔ)，路由表的計(jì)算要完成目的地址、目的類型、目的網(wǎng)絡(luò)掩碼、接口標(biāo)識(shí)、域標(biāo)識(shí)、路徑類型、路由度量、鏈路狀態(tài)標(biāo)識(shí)、下一跳等的填寫，網(wǎng)絡(luò)中的鏈路狀態(tài)通告類型有：路由器鏈路狀態(tài)通告、網(wǎng)絡(luò)鏈路狀態(tài)通告、摘要鏈路狀態(tài)通告、AS外部鏈路狀態(tài)通告。這些通告無疑是填寫內(nèi)容的唯一依據(jù)。

整個(gè)計(jì)算過程為:

（1）域內(nèi)路由的計(jì)算

域內(nèi)路由計(jì)算有兩個(gè)階段組成，A、Dijkstra算法生成最短路徑優(yōu)先樹，但此時(shí)的節(jié)點(diǎn)僅僅是域內(nèi)的各個(gè)節(jié)點(diǎn)且僅僅考慮路由器和傳輸網(wǎng)絡(luò)。B、最短路徑優(yōu)先樹中添加端網(wǎng)絡(luò)；最短路徑優(yōu)先樹的建立就是應(yīng)用了Dijkstra算法。但在該階段，計(jì)算路由器只考慮其鏈路狀態(tài)數(shù)據(jù)庫(kù)（LinkStateDataBase簡(jiǎn)稱LSDB）中的路由器鏈路狀態(tài)通告和網(wǎng)絡(luò)鏈路狀態(tài)通告。路由器鏈路狀態(tài)通告詳細(xì)描述了區(qū)域內(nèi)每個(gè)路由器與相應(yīng)區(qū)域的連接情況，網(wǎng)絡(luò)鏈路狀態(tài)通告詳細(xì)描述了網(wǎng)絡(luò)連接中的路由器的狀況，整個(gè)的網(wǎng)絡(luò)拓?fù)涞挠成浣M可以完整的表現(xiàn)出來了。

通過Dijkstra算法生成最短路徑優(yōu)先樹已經(jīng)描述了路由器到達(dá)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的最短路徑。所以，下一跳的計(jì)算成為生成域內(nèi)路由表時(shí)的關(guān)鍵任務(wù)。下一跳是指路由器在“存儲(chǔ)—轉(zhuǎn)發(fā)”數(shù)據(jù)包時(shí)，為達(dá)到目的地址的接口應(yīng)該轉(zhuǎn)發(fā)的IP地址。具體計(jì)算如下：

計(jì)算時(shí)要涉及根、父節(jié)點(diǎn)、目的三個(gè)參數(shù)。

如果目的和根之間最少存在有一個(gè)路由器,則下一跳只需直接從父節(jié)點(diǎn)獲取。

否則，目的和跟之間不存在路由器的節(jié)點(diǎn)，分為兩種情況的計(jì)算。

A、父節(jié)點(diǎn)就是根，即對(duì)點(diǎn)到多點(diǎn)網(wǎng)絡(luò)，需查看數(shù)據(jù)域（目的節(jié)點(diǎn)路由器鏈路狀態(tài)通告組成的），點(diǎn)對(duì)點(diǎn)則不需要下一跳地址。

B、父節(jié)點(diǎn)就變成了網(wǎng)絡(luò)，也需查看鏈路數(shù)據(jù)域，用來輸出的接口是從IP地址來獲取，該IP地址是指的是下一跳的IP地址。

（2）域間路由計(jì)算

域間路由分成兩種情況下的路由，分別是到達(dá)其它域網(wǎng)絡(luò)的路由和自治系統(tǒng)邊界路由器(ASBR)的路由。摘要鏈路狀態(tài)通告描述出這兩種情況在OSPF中。如果路由器連接到多個(gè)區(qū)域，則我們只考慮主干域中的摘要鏈路狀態(tài)通告，對(duì)于每條鏈路狀態(tài)通告有下面的原則：

①鏈路狀態(tài)通告的度量值或存活時(shí)間均為最大值，鏈路狀態(tài)通告是由本路由器發(fā)出，則不考慮。

②由邊界路由器ASBR產(chǎn)生的鏈路狀態(tài)通告，且通告描述的是一個(gè)網(wǎng)絡(luò)，則會(huì)將該通告的增加到目的的網(wǎng)絡(luò)的路由，度量值是路由器到路由器的度量值與目的網(wǎng)絡(luò)的度量值之和。

③查看路由表中優(yōu)先級(jí)最高的路由條目，若該鏈路狀態(tài)通告描述的是ASBR為目的，且優(yōu)先級(jí)最高的路由條目均低于域間路由條目，則增加相應(yīng)的路由。

④路由表中是否增加或者替換相應(yīng)路由條目，由路由表中到達(dá)目的地址的路由的優(yōu)先級(jí)決定。

（3）通過傳輸域的摘要鏈路狀態(tài)通告去選擇最優(yōu)的的路由

這一步只在某個(gè)區(qū)域的邊界路由器上執(zhí)行，該邊界路由器連接了多個(gè)不同的域。目的是：

①檢查是否存在更加優(yōu)化的路由存在，代替之前形成的路由條目；

②為更新后的主干區(qū)域內(nèi)的路由與ASBR之間的虛擬鏈路尋找真正的下一跳地址。

如圖3所示。

圖3 虛擬鏈路圖示

圖3中，網(wǎng)絡(luò)N1是主干區(qū)域，為了保障主干區(qū)域的通信，在R2與ASBR R0之間配置了一條虛擬鏈路。從圖5中可看出，路由器R1到達(dá)N1的度量5要遠(yuǎn)比R0的度量40小。因此，R1成為了傳輸區(qū)域1的DR，所有的路由器會(huì)通過它來轉(zhuǎn)發(fā)所有去向網(wǎng)絡(luò)N1的包。但通過路由表計(jì)算過程中第（1）步的計(jì)算，R2已經(jīng)得到了通過R0將包轉(zhuǎn)發(fā)給N1的路徑，顯然與實(shí)際情況不符。因此，通過第（3）步計(jì)算，R2將選擇R1作為轉(zhuǎn)發(fā)包的途徑。

（4）AS外部路由的計(jì)算

通信目的是AS區(qū)域[6-7]之外的路由或者其他設(shè)備的路由器稱為AS外部路由，通過AS外部鏈路狀態(tài)通告計(jì)算得到它。AS外部路由的計(jì)算相對(duì)來說較為簡(jiǎn)單。對(duì)每一條鏈路狀態(tài)通告，只需經(jīng)過下面的一些判斷：

①通告路由器、度量值、存活時(shí)間三者中有一個(gè)不符合條件，不予處理。

②不存在到通告路由器的路由，則不予處理。

③轉(zhuǎn)發(fā)路由器IP地址0.0.0.0，是一條缺省路由，數(shù)據(jù)包則應(yīng)轉(zhuǎn)交給通ASBR，按照缺省路由增加相應(yīng)路由。

④若轉(zhuǎn)發(fā)路由器不為0，但其不可達(dá)，則不予處理。

此時(shí)，按照上述的過程進(jìn)行完畢之后，OSPF的LSDB（鏈路狀態(tài)數(shù)據(jù)庫(kù)）便會(huì)根據(jù)內(nèi)容生成路由表，但是這是OSPF自身的路由表，區(qū)別于通信時(shí)路由器的內(nèi)核路由表。

3 結(jié)語(yǔ)

OSPF作為一種重要的內(nèi)部網(wǎng)關(guān)協(xié)議,得到了普遍應(yīng)用,極大地增強(qiáng)了網(wǎng)絡(luò)的靈活性與穩(wěn)定性。同時(shí)也反映出動(dòng)態(tài)路由協(xié)議功能的強(qiáng)悍及實(shí)現(xiàn)的復(fù)雜。在下一代互聯(lián)網(wǎng)中的動(dòng)態(tài)路由協(xié)議如OSPFv3[8-9]，基本功能雖與OSPEv2相同，但更好地支持了IPv6協(xié)議（如128位二進(jìn)制數(shù)的IP地址以及更好的認(rèn)證及加密的安全保證），在實(shí)現(xiàn)中利用到更多的鏈路狀態(tài)通告來保障具體的通信成功和安全保證。此外，比這認(rèn)為在計(jì)算復(fù)雜度和消息傳遞的復(fù)雜度方上還有更好的優(yōu)化改進(jìn)策略。同時(shí)，我們也看到，如何更高效地解決層次化路由、網(wǎng)絡(luò)拓?fù)涞木酆稀⒁约版溌窢顟B(tài)更廣泛和靈活的描述仍將是網(wǎng)絡(luò)研究的重要方向。

[1] 張春青, 張宏科. OSPF動(dòng)態(tài)路由協(xié)議中的路由計(jì)算北方交通大學(xué)學(xué)報(bào), 2003, (3): 100-103.

[2] 康威. OSPF路由協(xié)議安全性分析與研究北京郵電大學(xué), 2010.

[3] 張芳. OSPF路由協(xié)議的研究與實(shí)現(xiàn)學(xué)位論文, 北京郵電大學(xué), 2004.

[4] 倪勇, 史懷洲, 朱培棟. 基于OSPF鏈路狀態(tài)數(shù)據(jù)庫(kù)構(gòu)建網(wǎng)絡(luò)拓?fù)鋄J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2009(3): 1-4.

[5] 周集良. 基于OSPF路由協(xié)議的動(dòng)態(tài)配置技術(shù)[D]. 國(guó)防科學(xué)技術(shù)大學(xué), 2003.

[6] 郭偉, 柯漢波. 多區(qū)域OSPF校園網(wǎng)路由設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2003(8): 48-50.

[7] 張春青, 張宏科. OSPF動(dòng)態(tài)路由協(xié)議中的路由計(jì)算[J]. 北方交通大學(xué)學(xué)報(bào), 2003(3): 100-103.

[8] 林琴?gòu)?qiáng). OSPF剖析及其鏈路狀態(tài)數(shù)據(jù)庫(kù)的實(shí)現(xiàn)[D]. 四川大學(xué), 2003.

[9] 嚴(yán)斌宇, 盧葦, 黃銳. OSPF路由選擇協(xié)議的研究[J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版), 2002(3): 460-464.

Dynamic Routing Protocol Mechanism Analysis and Improved Strategy for Next Generation Internet

ZHUO Guang-ping

(Taiyuan Normal University, Department of computer science, ShanXi Tai yuan 030619)

With the growing demand for Internet applications, types and performance, Internet is developing and transferring to the next generation of Internet. As the key layer of the Internet Architecture - the Internet layer, the dynamic routing protocol, one of the core components of the Internet, has now become a widely used and preferred protocol for routing and forwarding functions in the design and establishment of park, man, and wide area network, and is also in the process of continuous updating and development. This paper describes the design idea of the shortest path priority algorithm based on Dijkstra in dynamic routing protocol and carries out a more in-depth analysis and dynamic example of the protocol itself. Finally, some optimization and improvement are made for the complexity of the algorithm, the complexity of message transfer and the adaptability of IPv6 in the new generation of Internet.

Next generation Internet; Network architecture; Shortest path first; Dynamic routing protocol

TP393.02

J

10.3969/j.issn.1003-6970.2018.07.043

卓廣平(1972-)，男，計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)工學(xué)博士副教授，主要研究方向：網(wǎng)絡(luò)體系結(jié)構(gòu)、協(xié)議機(jī)制與優(yōu)化、人工智能。

本文著錄格式：卓廣平. 下一代互聯(lián)網(wǎng)動(dòng)態(tài)路由協(xié)議機(jī)制分析與改進(jìn)策略[J]. 軟件，2018，39（7）：202-207