基于OSPF協(xié)議的大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)模型

蔣亞平,郭 浩,郭培根

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院,鄭州 450002)

基于OSPF協(xié)議的大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)模型

蔣亞平,郭 浩,郭培根

(鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院,鄭州 450002)

針對(duì)傳統(tǒng)大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)模型的準(zhǔn)確性、完整性、實(shí)時(shí)性的局限性,借鑒OSPF協(xié)議周期性傳播網(wǎng)絡(luò)拓?fù)湫畔⒌臋C(jī)理,提出了基于OSPF協(xié)議的大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)模型LNTDM.該模型首先采用被動(dòng)檢測(cè)方式,通過(guò)獲取OSPF協(xié)議中的鏈路狀態(tài)更新報(bào)文,分析其中Router LSA、Network LSA獲得區(qū)域內(nèi)網(wǎng)絡(luò)拓?fù)?然后通過(guò)邊界路由獲取的Summary Network LSA進(jìn)行分析獲得區(qū)域間網(wǎng)絡(luò)拓?fù)?從而完成大規(guī)模網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的發(fā)現(xiàn).實(shí)驗(yàn)結(jié)果表明,該模型能準(zhǔn)確完整的獲取大規(guī)模網(wǎng)絡(luò)拓?fù)?可以很好的彌補(bǔ)現(xiàn)有大型網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)的不足,實(shí)際應(yīng)用前景廣闊.

網(wǎng)絡(luò)拓?fù)?OSPF協(xié)議;Router LSA;Network LSA;Summary Network LSA

隨著計(jì)算機(jī)技術(shù)的發(fā)展,網(wǎng)絡(luò)在國(guó)家的政治、經(jīng)濟(jì)、軍事等領(lǐng)域的基礎(chǔ)作用越發(fā)突出.網(wǎng)絡(luò)一旦受損,幾乎所有的社會(huì)系統(tǒng)將無(wú)法運(yùn)行,而網(wǎng)絡(luò)拓?fù)洳粌H能使使用者了解整個(gè)網(wǎng)絡(luò)結(jié)構(gòu),對(duì)網(wǎng)絡(luò)中的重要節(jié)點(diǎn)、數(shù)據(jù)流向等信息進(jìn)行分析,而且可以對(duì)網(wǎng)絡(luò)空間進(jìn)行高效管理、合理分配資源以及有效的安全監(jiān)測(cè)和防護(hù)[1].

近年來(lái),大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)在國(guó)內(nèi)外的研究取得了一定的進(jìn)展.Aman Shaikh 等[2]提出利用OSPF 協(xié)議報(bào)文被動(dòng)探測(cè)技術(shù)建立網(wǎng)絡(luò)拓?fù)?但由于側(cè)重分析網(wǎng)絡(luò)實(shí)體的數(shù)目和接口,對(duì)于元素之間的連接關(guān)系缺少深入分析.Spring等[3]在RockFuel項(xiàng)目探測(cè)大規(guī)模網(wǎng)絡(luò)拓?fù)渲惺褂梅植际健⒅鲃?dòng)探測(cè)的技術(shù),能夠快速掃描網(wǎng)絡(luò)空間,但需要發(fā)送大量探測(cè)數(shù)據(jù)包,增加了網(wǎng)絡(luò)負(fù)擔(dān).王慧等[4]提出了TAOS 算法,通過(guò)獲取LSU來(lái)計(jì)算網(wǎng)絡(luò)拓?fù)錇閰^(qū)域內(nèi)和區(qū)域間網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)提供了思路,但在多區(qū)域的大規(guī)模網(wǎng)絡(luò)拓?fù)渲型貌坏酵暾負(fù)?

本文針對(duì)現(xiàn)有大規(guī)模網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)的不足,提出了基于OSPF協(xié)議的拓?fù)浒l(fā)現(xiàn)模型LNTDM(Large-scale network topology discovery model).該模型在不增加網(wǎng)絡(luò)負(fù)擔(dān)的情況下,可以準(zhǔn)確、完整、實(shí)時(shí)地得出網(wǎng)絡(luò)拓?fù)?

1 LNTDM模型原理

圖1 典型網(wǎng)絡(luò)拓?fù)銯ig.1 Typical network topology

OSPF(Open Shortest Path First)是用于自治系統(tǒng)(autonomous system,AS)內(nèi)的鏈路狀態(tài)路由協(xié)議,一個(gè)大型自治系統(tǒng)通常被劃分為多個(gè)區(qū)域(Area),區(qū)域之間相對(duì)獨(dú)立,用區(qū)域號(hào)(Area ID)標(biāo)識(shí)[5].每臺(tái)連接到特定OSPF區(qū)域的路由器在網(wǎng)絡(luò)狀態(tài)穩(wěn)定情況下都應(yīng)該學(xué)習(xí)到完全相同的拓?fù)鋽?shù)據(jù).每臺(tái)路由器在自己的鏈路狀態(tài)數(shù)據(jù)庫(kù)(LSDB)中存儲(chǔ)獨(dú)立LSA(鏈路狀態(tài)通告)數(shù)據(jù).由于承載著LSA的LSU的周期性傳遞,可以通過(guò)被動(dòng)獲取的方式得到該報(bào)文進(jìn)行分析從而得到Area ID 、LinkStateID、 Advertising Router、 RouterID 等拓?fù)湫畔?綜合以上拓?fù)湫畔?gòu)建網(wǎng)絡(luò)拓?fù)?本文提出的LNTDM模型分為兩個(gè)模塊:一是區(qū)域內(nèi)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn).二是區(qū)域間網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn).根據(jù)OSPF中的四種網(wǎng)絡(luò)鏈接類(lèi)型更好的展開(kāi)對(duì)LSA的分析,圖1展示了一個(gè)典型網(wǎng)絡(luò)拓?fù)?路由器相相關(guān)配置在這里不再贅述,查看配置結(jié)果分析網(wǎng)絡(luò)鏈路類(lèi)型.本文將一直使用這個(gè)網(wǎng)絡(luò)拓?fù)渥龇治?

1.1區(qū)域內(nèi)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)

區(qū)域內(nèi)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)是在獲取LSU報(bào)文的基礎(chǔ)上過(guò)濾Router LSA和Network LSA,根據(jù)四種網(wǎng)絡(luò)類(lèi)型進(jìn)行不同的處理.當(dāng)網(wǎng)絡(luò)類(lèi)型是point-to-point、stub或者virtual時(shí)記錄其Advertising router、link ID、link Data三個(gè)字段的拓?fù)溥B接信息,得到完整的網(wǎng)絡(luò)連接信息;當(dāng)網(wǎng)絡(luò)類(lèi)型是transit時(shí),由Router LSA獲取Advertising Router、Link ID字段信息,由Network LSA獲得Link State ID 和Attached Router字段信息.整合所得到的transit類(lèi)型的信息,判斷Link ID和Link State ID字段是否一致,一致則構(gòu)成transit類(lèi)型的三個(gè)字段的拓?fù)溥B接信息.

圖2 Router LSA的詳細(xì)拓?fù)漕?lèi)型Fig.2 Detailed topology type of Router LSA

1.1.1 點(diǎn)對(duì)點(diǎn)和末節(jié)網(wǎng)絡(luò) 從圖1可以看出R1有三個(gè)末節(jié)網(wǎng)絡(luò)(stub),兩個(gè)點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)(piont-to-point).R2和R3的Router LSA中也有相同的信息,路由器有足夠的信息可以判斷通過(guò)那條末節(jié)網(wǎng)絡(luò)來(lái)連接到哪臺(tái)路由器,然后使用接口配置的IP地址來(lái)判斷連接到其他路由器的接口.圖2顯示了基于R1、R2、R3Router LSA中所包含的詳細(xì)信息構(gòu)造出來(lái)的拓?fù)漕?lèi)型.

1.1.2 傳輸網(wǎng) OSPF協(xié)議中SPF(最短路徑優(yōu)先算法)要求使用節(jié)點(diǎn)和節(jié)點(diǎn)之間的鏈路來(lái)構(gòu)建拓?fù)淠Ｐ?具體來(lái)說(shuō),每條鏈路必須是在一對(duì)節(jié)點(diǎn)之間,但當(dāng)存在多路訪(fǎng)問(wèn)數(shù)據(jù)鏈路(如圖1中area1左半部分中的三個(gè)路由器連接在同一個(gè)子網(wǎng)內(nèi))時(shí),OSPF必須對(duì)其進(jìn)行抽象描繪即選舉指定路由器(DR)作為偽節(jié)點(diǎn)使用.如圖3傳輸網(wǎng).

圖3 傳輸網(wǎng)Fig.3 The transmission network

1.1.3 虛鏈路 OSPF虛鏈路允許兩臺(tái)連接到同一非骨干區(qū)域的ABR通過(guò)該非骨干區(qū)域建立鄰居關(guān)系,即便這兩臺(tái)ABR被許多其他路由器和子網(wǎng)分隔開(kāi).虛電路表現(xiàn)為兩臺(tái)路由器之間的虛擬的點(diǎn)到點(diǎn)鏈接.如圖1,R2和R3.

1.2區(qū)域間網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)

區(qū)域間網(wǎng)絡(luò)拓?fù)涫沁^(guò)濾含有Summary Network LSA的LSU報(bào)文獲得Area ID,分析Summary Network LSA,獲得Advertising router及所對(duì)應(yīng)的Link ID字段,從獲得的這些字段中可得到一個(gè)自治系統(tǒng)的所有區(qū)域ID號(hào),這些區(qū)域中的邊界路由器的ID號(hào),以及這些區(qū)域的所有子網(wǎng),進(jìn)一步分析可以得到ABR都和那些區(qū)域相連等拓?fù)湫畔?區(qū)域間的路由信息依靠ABR創(chuàng)建的類(lèi)型三LSA轉(zhuǎn)遞,而區(qū)域間的網(wǎng)絡(luò)拓?fù)淇梢酝ㄟ^(guò)獲取ABR產(chǎn)生的Summary Network LSA分析得來(lái).OSPF的重要特征之一是它的靈活性,該協(xié)議可以使用ABR將任何區(qū)域構(gòu)成的互聯(lián)的網(wǎng)絡(luò)連接在一起.ABR能夠處理一組區(qū)域構(gòu)成的全網(wǎng)狀拓?fù)?每個(gè)區(qū)域都與其他所有區(qū)域相連)、部分網(wǎng)狀拓?fù)?、一個(gè)區(qū)域連接到下一個(gè)區(qū)域的鏈狀拓?fù)浠蛘咂渌魏尉W(wǎng)絡(luò)配置,它也能處理隨著時(shí)間推移可能出現(xiàn)的拓?fù)渥兓?

ABR的在它不了解區(qū)域內(nèi)部拓?fù)涞那闆r下,只是接受從區(qū)域傳遞給它的信息并將這些信息與其他區(qū)域共享.在圖1中捕獲ABR產(chǎn)生的LSU,讀取Area ID和Summary Network LSA中的Advertising router字段,從而得到區(qū)域間的網(wǎng)絡(luò)拓?fù)淙鐖D4所示.

圖4 區(qū)域間網(wǎng)絡(luò)拓?fù)銯ig.4 Inter-area network topology

2 算法實(shí)現(xiàn)

本文提出的LNTDM模型基本思想是:提取包含拓?fù)湫畔⒌腖SU,在拓?fù)浣Y(jié)構(gòu)不發(fā)生變化的情況下得到所有LSA[6-7],針對(duì)三類(lèi)不同的LSA進(jìn)行不同操作,得出完整拓?fù)淞斜鞟S后算法結(jié)結(jié)束.LNTDM算法分兩步:①數(shù)據(jù)處理,建立域內(nèi)拓?fù)溥B接關(guān)系集合CONNET.②建立域間拓?fù)溥B接關(guān)系集合ABR,合并CONNET和ABR得到集合AS.

1)數(shù)據(jù)處理,定義報(bào)文LSUi,i=1,2,…,n.按接收順序排列.

設(shè)V為某一區(qū)域的結(jié)點(diǎn)集合,V={v|v=〈RouterIDi,AreaIDi,AR〉，RouterIDi,取自L(fǎng)SUi頭部,AR∈LSA頭部}.

設(shè)C、N為區(qū)域內(nèi)連接的集合,C={c|c=〈RouterIDi,AreaIDi,AR〉，〈Type,LinkIDi,LinkData〉〉，RouterIDi,AreaIDi取自L(fǎng)SUi頭部,AR∈RouterLSA},將三元組〈Type,LinkID,LinkData〉簡(jiǎn)記為l,當(dāng)存在多個(gè)相同的RouterLSA時(shí)按照接收順序替換舊信息.

N={n|n=〈RouterIDi,AreaIDi,AR,LinkStateID,AttachedRouter〉，RouterIDiAredIDi,取自L(fǎng)SUi頭部,AR∈NetworkLSA},當(dāng)存在多個(gè)相同的NetworkLSA時(shí)按照接收順序替換舊信息.

連接集合C，V,檢查?C.Type≠trasit滿(mǎn)足C.AR=V.AR,C.LinkID=N.LinkStateID,將兩個(gè)集合連接得到集合CONNET,CONNET={connet|conner=〈RouterIDi,AreaIDi,AR，l〉}.

連接集合C，V，N,檢查?C.Type≠trasit滿(mǎn)足C.AR=V.AR,C.LinkID=N.LinkStateID,將集合連接加入CONNET中.

圖5 拓?fù)浒l(fā)現(xiàn)算法流程圖Fig.5 The flow chart for topology discovery algorithm

2)建立區(qū)域間拓?fù)溥B接關(guān)系集合,合并集合得到AS.

設(shè)B為邊界結(jié)點(diǎn)的集合,B={b|b=〈RouterIDi,AreaIDi…n,AR〉，RouterIDiAredIDi…n,取自L(fǎng)SUi頭部，RouterIDi∈{ABR,ABSR},AR∈SummaryNetworkLSA}.

設(shè)E為區(qū)域間建立的連接的集合,E={e|e=〈RouterIDi,AreaIDi……AreaIDn,AR,LinkIDi〉}.

連接集合B,E檢查是否存在?B.RouterIDi∈V.RouterID,滿(mǎn)足B.AR=E.AR,由B.AR和E.AR將集合B和E連接,得到集合ABR.

ABR={abr|abr=〈RouterIDi,AreaIDi…AreaIDn,AR,LinkIDi〉}.

將CONNET按照同一AreaID歸類(lèi),得到n個(gè)區(qū)域集合CONNET1…CONNETn,檢查同一AreaID中是否存在?CONNRT.Type=stub,?ABR.RouterIDi∈CONNET.RouterID,滿(mǎn)足ABR.LinkID=CONNET.LinkID,將兩個(gè)集合合并為AS.

AS={AS|RouterIDi,conneti…connetn,AR}.

經(jīng)過(guò)以上處理后得到整個(gè)網(wǎng)絡(luò)拓?fù)溥B接關(guān)系集合.使用上述算法先對(duì)區(qū)域內(nèi)網(wǎng)絡(luò)拓?fù)溥M(jìn)行繪制,再用得到的區(qū)域內(nèi)所有網(wǎng)絡(luò)子網(wǎng)對(duì)其進(jìn)行比對(duì)分析,之后使用ABR對(duì)所有區(qū)域進(jìn)行連接從而得到整個(gè)網(wǎng)絡(luò)拓?fù)?算法流程圖如圖5所示.

3 實(shí)驗(yàn)結(jié)果及分析

圖6 兩個(gè)學(xué)院網(wǎng)絡(luò)拓?fù)銯ig.6 The network topologies of two college

本實(shí)驗(yàn)遍布校園計(jì)共設(shè)置了20個(gè)不同的檢測(cè)點(diǎn),用于捕獲網(wǎng)絡(luò)上流經(jīng)的OSPF協(xié)議報(bào)文.經(jīng)過(guò)兩周的搜集,剔除其余OSPF報(bào)文只保留LSU,然后使用LNTDM模型對(duì)校園網(wǎng)進(jìn)行拓?fù)浒l(fā)現(xiàn),最終確定校園中包含了1個(gè)路由器,16個(gè)三層設(shè)備和145個(gè)子網(wǎng).然后對(duì)計(jì)通學(xué)院和經(jīng)管學(xué)院的網(wǎng)絡(luò)拓?fù)溥M(jìn)行繪制.圖6顯示了兩個(gè)學(xué)院的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).其中areaID為0.0.0.20,包含了1個(gè)路由器和6個(gè)三層設(shè)備和33個(gè)子網(wǎng).

將圖6與網(wǎng)絡(luò)中心提供的實(shí)際拓?fù)鋱D相比,除了子網(wǎng)的數(shù)目少了倆個(gè)以外,其余鏈路信息基本準(zhǔn)確.會(huì)出現(xiàn)上述的結(jié)果主要是因?yàn)樵O(shè)置的檢測(cè)點(diǎn)沒(méi)有覆蓋所有子網(wǎng),得到這樣的結(jié)論之后又在之前沒(méi)有設(shè)立檢測(cè)點(diǎn)的區(qū)域進(jìn)行檢測(cè),得到了之前沒(méi)有的兩個(gè)子網(wǎng)的拓?fù)湫畔?實(shí)驗(yàn)表明文中提出的算法能夠有效的處理OSPF報(bào)文,針對(duì)多個(gè)區(qū)域的大型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)遇到的困難找到了合理的解決方案.

4 結(jié)語(yǔ)

文中提出的一種基于OSPF協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法改進(jìn),該算法通過(guò)對(duì)區(qū)域內(nèi)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)和區(qū)域間網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn),得到了整個(gè)自治系統(tǒng)的連接信息,從而進(jìn)行拓?fù)浒l(fā)現(xiàn)解決了跨區(qū)域網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的困難.但由于OSPF報(bào)文的獲取需要跨越多個(gè)區(qū)域,導(dǎo)致報(bào)文獲取不全的現(xiàn)象.結(jié)合采集器在不同區(qū)域建立隧道從而獲取完整的OSPF Update報(bào)文將是下一步的研究方向.

[1] 趙帆,羅向陽(yáng),劉粉林.網(wǎng)絡(luò)空間測(cè)繪技術(shù)研究[J].網(wǎng)絡(luò)與信息安全學(xué)報(bào),2016(9):1-11.

[2] SHAIKH A,GREENBERG A.OSPF Monitoring: Architecture,Design and Deployment Experience[C]∥Proc of the 1st Symposium on Networked System Design and Implementation,San Francisco,CA:[s.n.],2004: 57-70.

[3] SPRING N,MAHAJAN R,WETHERALL D.Measuring ISP topologies with rocketfuel[J].ACM Sigcomm Computer Communication Review,2002,32(4): 133-145.

[4] 王慧,羅軍勇,寇曉蕤.基于OSPF協(xié)議報(bào)文的網(wǎng)絡(luò)拓?fù)浞治鏊惴╗J].計(jì)算機(jī)工程,2008(6):103-105.

[5] CHARLES M KOZIEROK.The TCP/IP Guide,A Comperhensive,Illustrated Internet Protocols Reference,published by No Starch Press.

[6] 潘楠,王勇,陶曉玲.基于OSPF協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2011(5):1550-1553,1567.

[7] 趙天福,周丹平.基于OSPF協(xié)議的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)的實(shí)現(xiàn)[J].江南大學(xué)學(xué)報(bào)(自然科學(xué)版),2008(2):151-156.

責(zé)任編輯：時(shí)凌

LargeScaleNetworkTopologyDiscoveryModelBasedonOSPFProtocol

JIANG Yaping,GUO Hao,GUO Peigen

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China )

For the traditional large-scale network topology discovery model,its real-time,accuracy and characterization are relatively limited.By referring to the mechanism of periodic propagation of network topology information by OSPF protocol,a Large Scale Network Topology Discovery Model Based on OSPF Protocol (LNTDM) is proposed.The model adopts the passive detection.Firstly,the link state update packets in the OSPF protocol are obtained and the router LSA and Network LSA are analyzed to obtain regional network topology.And then the Summary Network LSA obtained through the boundary routing is analyzed to obtain inter-regional network topology,thus completing the large-scale network topology discovery.The experimental results show that the model can accurately obtain the large-scale network topology and it can make up for the shortcomings of the existing large-scale network topology discovery technology.The practical application prospect of the model is broad.

network topology;OSPF protocol;router LSA;network LSA;summary network LSA

2017-05-24.

河南省科技廳科技攻關(guān)基金項(xiàng)目(0624220084);河南省科技廳基礎(chǔ)與前沿技術(shù)項(xiàng)目(122300410255).

蔣亞平(1972-),男,博士,副教授,主要從事網(wǎng)絡(luò)安全、計(jì)算機(jī)網(wǎng)絡(luò)的研究.

1008-8423(2017)04-0434-04

10.13501/j.cnki.42-1569/n.2017.12.018

TP393

A