蔣亞平,郭 浩,郭培根

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

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

蔣亞平,郭 浩,郭培根

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

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

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

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

近年來,大規(guī)模網(wǎng)絡(luò)拓撲發(fā)現(xiàn)技術(shù)在國內(nèi)外的研究取得了一定的進展.Aman Shaikh 等[2]提出利用OSPF 協(xié)議報文被動探測技術(shù)建立網(wǎng)絡(luò)拓撲,但由于側(cè)重分析網(wǎng)絡(luò)實體的數(shù)目和接口,對于元素之間的連接關(guān)系缺少深入分析.Spring等[3]在RockFuel項目探測大規(guī)模網(wǎng)絡(luò)拓撲中使用分布式、主動探測的技術(shù),能夠快速掃描網(wǎng)絡(luò)空間,但需要發(fā)送大量探測數(shù)據(jù)包,增加了網(wǎng)絡(luò)負擔(dān).王慧等[4]提出了TAOS 算法,通過獲取LSU來計算網(wǎng)絡(luò)拓撲為區(qū)域內(nèi)和區(qū)域間網(wǎng)絡(luò)拓撲發(fā)現(xiàn)提供了思路,但在多區(qū)域的大規(guī)模網(wǎng)絡(luò)拓撲中往往得不到完整拓撲.

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

1 LNTDM模型原理

圖1 典型網(wǎng)絡(luò)拓撲Fig.1 Typical network topology

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

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

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

圖2 Router LSA的詳細拓撲類型Fig.2 Detailed topology type of Router LSA

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

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

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

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

1.2區(qū)域間網(wǎng)絡(luò)拓撲發(fā)現(xiàn)

區(qū)域間網(wǎng)絡(luò)拓撲是過濾含有Summary Network LSA的LSU報文獲得Area ID,分析Summary Network LSA,獲得Advertising router及所對應(yīng)的Link ID字段,從獲得的這些字段中可得到一個自治系統(tǒng)的所有區(qū)域ID號,這些區(qū)域中的邊界路由器的ID號,以及這些區(qū)域的所有子網(wǎng),進一步分析可以得到ABR都和那些區(qū)域相連等拓撲信息.區(qū)域間的路由信息依靠ABR創(chuàng)建的類型三LSA轉(zhuǎn)遞,而區(qū)域間的網(wǎng)絡(luò)拓撲可以通過獲取ABR產(chǎn)生的Summary Network LSA分析得來.OSPF的重要特征之一是它的靈活性,該協(xié)議可以使用ABR將任何區(qū)域構(gòu)成的互聯(lián)的網(wǎng)絡(luò)連接在一起.ABR能夠處理一組區(qū)域構(gòu)成的全網(wǎng)狀拓撲(每個區(qū)域都與其他所有區(qū)域相連)、部分網(wǎng)狀拓撲、一個區(qū)域連接到下一個區(qū)域的鏈狀拓撲或者其他任何網(wǎng)絡(luò)配置,它也能處理隨著時間推移可能出現(xiàn)的拓撲變化.

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

圖4 區(qū)域間網(wǎng)絡(luò)拓撲Fig.4 Inter-area network topology

2 算法實現(xiàn)

本文提出的LNTDM模型基本思想是:提取包含拓撲信息的LSU,在拓撲結(jié)構(gòu)不發(fā)生變化的情況下得到所有LSA[6-7],針對三類不同的LSA進行不同操作,得出完整拓撲列表AS后算法結(jié)結(jié)束.LNTDM算法分兩步:①數(shù)據(jù)處理,建立域內(nèi)拓撲連接關(guān)系集合CONNET.②建立域間拓撲連接關(guān)系集合ABR,合并CONNET和ABR得到集合AS.

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

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

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

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

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

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

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

2)建立區(qū)域間拓撲連接關(guān)系集合,合并集合得到AS.

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

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

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

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

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

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

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

3 實驗結(jié)果及分析

圖6 兩個學(xué)院網(wǎng)絡(luò)拓撲Fig.6 The network topologies of two college

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

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

4 結(jié)語

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

[1] 趙帆,羅向陽,劉粉林.網(wǎng)絡(luò)空間測繪技術(shù)研究[J].網(wǎng)絡(luò)與信息安全學(xué)報,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é)議報文的網(wǎng)絡(luò)拓撲分析算法[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ā)現(xiàn)算法[J].計算機工程與設(shè)計,2011(5):1550-1553,1567.

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

責(zé)任編輯：時凌

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)基金項目(0624220084);河南省科技廳基礎(chǔ)與前沿技術(shù)項目(122300410255).

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

1008-8423(2017)04-0434-04

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

TP393

A