基于無向圖的網(wǎng)絡(luò)拓撲生成算法

1、基于無向圖的網(wǎng)絡(luò)拓撲生成算法科技論文基于無向圖的網(wǎng)絡(luò)拓撲生成算法汪德文陳健摘要:網(wǎng)絡(luò)拓撲圖在網(wǎng)絡(luò)管理中起著非常重要的作用,但是目前還沒有任何公共協(xié)議用于網(wǎng)絡(luò)拓撲發(fā)現(xiàn),因此,用于拓撲發(fā)現(xiàn)的拓撲信息一般都來源于多種協(xié)議本文建立了基于無向圖的網(wǎng)絡(luò)拓撲描述模型,用來描述形式各異的拓撲信息,并提出了基于該模型的拓撲生成算法,該算法與網(wǎng)絡(luò)協(xié)議無關(guān),適用性強.關(guān)鍵詞:網(wǎng)絡(luò)拓撲拓撲發(fā)現(xiàn)拓撲描述模型協(xié)議無關(guān)的拓撲生成算法無向圖1引言拓撲管理是網(wǎng)絡(luò)管理的重要組成部分,是配置管理的核心和故障管理的基礎(chǔ).拓撲發(fā)現(xiàn)是指利用網(wǎng)管協(xié)議或工具搜集分布在網(wǎng)絡(luò)各處的原始拓撲數(shù)據(jù),通過拓撲生成算法綜合出完整的拓撲信息.網(wǎng)絡(luò)拓撲發(fā)現(xiàn)

2、包括兩方面的內(nèi)容:拓撲信息收集和拓撲圖的生成.由于目前還沒有任何公共協(xié)議可用于拓撲發(fā)現(xiàn),加上網(wǎng)絡(luò)和網(wǎng)管協(xié)議種類眾多,因此,現(xiàn)有的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法中的拓撲信息來源于多種協(xié)議.怎樣用統(tǒng)一的模型來描述這些拓撲信息,從而用統(tǒng)一的算法來描述現(xiàn)有的拓撲發(fā)現(xiàn)方法值得研究.本文在充分總結(jié)分析網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法特點的基礎(chǔ)上,歸納其共性,抽象出了網(wǎng)絡(luò)拓撲描述模型和協(xié)議無關(guān)的網(wǎng)絡(luò)拓撲圖生成算法.2基本思想本算法的基本思想是由局部拓撲生成整個目標網(wǎng)絡(luò)的拓撲結(jié)構(gòu).網(wǎng)絡(luò)拓撲信息是從網(wǎng)絡(luò)線路上的多種協(xié)議中收集來的,從某一種協(xié)議中提取出來的拓撲信息只是目標網(wǎng)絡(luò)中某一片的局部拓撲,如兩個或多個路由器的連接.這些局部拓撲是用來還原

3、整個目標網(wǎng)絡(luò)拓撲結(jié)構(gòu)的原材料,我們要像拼圖一樣把這些原材料拼接起來.不同的協(xié)議中包含的拓撲信息在表示形式上有很大差異,因此,在拼接之前,要把零散的,形式各異的局部拓撲信息歸一化為統(tǒng)一的表示形式.這就需要為網(wǎng)絡(luò)拓撲結(jié)構(gòu)的描述建立一個模型,在該模型的基礎(chǔ)上實現(xiàn)網(wǎng)絡(luò)拓撲圖的拼接,拼接的過程就是網(wǎng)絡(luò)拓撲圖的生成過程.從上面的敘述中可以看出,算法的核心是網(wǎng)絡(luò)拓撲描述模型和網(wǎng)絡(luò)拓撲圖生成算法.3網(wǎng)絡(luò)拓撲結(jié)構(gòu)描述模型3.1模型選擇要求建立網(wǎng)絡(luò)拓撲描述模型的目的是用來表示從各種協(xié)議中獲取的各種拓撲信息,將異構(gòu)的拓撲信息歸一化.既然是要用局部拓撲拼接整個目標網(wǎng)絡(luò)的拓撲結(jié)構(gòu),那么局部拓撲和整個網(wǎng)絡(luò)拓撲就應(yīng)該用一個

4、同構(gòu)的模型來表示,整個網(wǎng)絡(luò)拓撲表現(xiàn)為局部拓撲的和.無向圖具備電信技術(shù)研究2007年第4期這樣的特點,因此,用無向圖來描述網(wǎng)絡(luò)拓撲是合適的.首先,網(wǎng)絡(luò)拓撲圖描述的是網(wǎng)絡(luò)元素以及網(wǎng)絡(luò)元素之間的關(guān)系,圖是某類具體事物和這些事物之間的聯(lián)系的抽象,因此,圖可以描述網(wǎng)絡(luò)元素之間的各種關(guān)系.其次,圖是一個抽象的模型,與協(xié)議無關(guān),可以描述從各種協(xié)議中提取的網(wǎng)絡(luò)拓撲信息.最后,各種零散的局部拓撲信息都可以用圖來描述,將局部拓撲圖拼接為整個目標網(wǎng)絡(luò)拓撲圖的過程實際上就是圖的并,聯(lián)運算.因此,圖的運算可以實現(xiàn)網(wǎng)絡(luò)拓撲圖的拼接.3.2相關(guān)定義先給出圖及相關(guān)概念的定義u.定義1:一個圖g定義為一個有序?qū)?v,e),記為

5、g(v,e),其中(1)v是一個非空集合,稱為頂點集,其元素稱為頂點或點,ivi表示頂點數(shù).(2)e是由v中的點組成的無序點構(gòu)成的集合,成為邊集,其元素稱為邊,且同一點對在e中可能出現(xiàn)多次.圖g的頂點集也記為v(g),邊集記為e(g).頂點集和邊集都有限的圖稱為有限圖,即沒有重邊也沒有環(huán)的圖稱為簡單圖.圖g的頂點數(shù)和邊數(shù)分別用符號n(g)和m(g)表示.定義2:設(shè)g,是g的子圖,gl和g,的并運算是g的一個子圖,其頂點集為v(g1)uv(g,),其邊集為e(g)ue(g,).圖i是圖的并運算示意圖.g1g2glug2圖1圖的并運算示意圖定義3:在不相交的g1和g2的并圖qug2中,把的每個頂點

6、和的每個頂點連接起來所得到的圖稱為gl和g2的聯(lián)圖,記為vg2.圖2是圖的聯(lián)運算示意圖.2ag1bag2glvg圖2圖的聯(lián)運算示意圖b科技論文3.3網(wǎng)絡(luò)拓撲描述模型網(wǎng)絡(luò)拓撲描述模型是拓撲生成算法的基礎(chǔ),只有建立了合適的描述模型,才能使拓撲生成算法獨立于網(wǎng)絡(luò)協(xié)議,只和描述模型有關(guān).網(wǎng)絡(luò)拓撲描述模型的作用是:(1)將從各種協(xié)議中獲取的拓撲信息表示為統(tǒng)一的形式,即拓撲信息的歸一化.(2)作為拓撲信息與拓撲生成算法之間的中介.歸一化后的拓撲信息作為拓撲生成算法的輸入,而不是各種表示形式各異的原始拓撲信息,這樣拓撲生成算法就可以獨立于網(wǎng)絡(luò)協(xié)議了,從不同的協(xié)議中提取的拓撲信息經(jīng)過描述模型歸一化后都可以使用

7、同一個拓撲生成算法生成拓撲圖.根據(jù)上述圖的相關(guān)概念,網(wǎng)絡(luò)拓撲圖可以抽象為簡單無向圖,圖的頂點表示網(wǎng)絡(luò)元素,邊表示網(wǎng)絡(luò)元素之間的連接關(guān)系.根據(jù)這個模型,網(wǎng)絡(luò)拓撲圖的還原過程可以概括為兩個步驟:第一步,把從各種協(xié)議中提取的拓撲信息表示為一個個的子圖gi,g:,g;第二步,求子圖的并圖g.g:glug2uug并圖g就是整個目標網(wǎng)絡(luò)的拓撲圖.3.4通信子網(wǎng)邊界拓撲描述問題及解決方法網(wǎng)絡(luò)拓撲發(fā)現(xiàn)中,一般是利用路由信息來發(fā)現(xiàn)路由器子網(wǎng),利用主動探測獲取存活主機地址j.路由信息只是描述用戶子網(wǎng)路由而不是主機路由,因此,通信子網(wǎng)的邊界拓撲用無向圖描述為路由器拓撲子圖g,g刪中的頂點代表用戶子網(wǎng),而不是主機;主

8、動探測只是獲取的存活主機的ii)地址,用無向圖描述為主機拓撲子圖gh,gh中只有頂點,代表主機.g與gh吲的交集為空,因此gugh是非連通的,如圖3所示,b是路由器,a,c,d是用戶子網(wǎng),e,f,g是主機.這就是通信子網(wǎng)邊界拓撲描述問題.產(chǎn)生通信子網(wǎng)邊界拓撲描述問題的原因是缺少主機與通信子網(wǎng)連接的描述信息.怎樣描述主機與通信子網(wǎng)的連接關(guān)系呢?實際上,用戶子網(wǎng)的網(wǎng)絡(luò)號與主機地址信息本身已經(jīng)包含了兩者之間的關(guān)系:用戶子網(wǎng)包含主機,主機只是用戶子網(wǎng)內(nèi)部元素,如圖4a所示,通信子網(wǎng)里用戶子網(wǎng)節(jié)點已經(jīng)代表了該子網(wǎng)內(nèi)所有的主機.因此,如果把用戶子網(wǎng)與主機的關(guān)系描述為子網(wǎng)包含主機,拓撲圖中就只有路由器和用戶

9、子網(wǎng),無法把主機單獨表示出來了.c一-:1iof-!:l_一go一一jj!gro缸圖3通信子網(wǎng)邊界拓撲描述問題示意圖3電信技術(shù)研究2007年第4期如果把用戶子網(wǎng)與主機的關(guān)系描述為主機通過用戶子網(wǎng)連接到路由器,就可以把用戶子網(wǎng)看作連接主機和路由器的網(wǎng)絡(luò)元素了,這樣就能在拓撲圖中清楚的反映出路由器,子網(wǎng)和主機,如圖4b.九用,刪包含t帆b,用廣予髑與主jlj足財?shù)葘嶓w圖4用戶子網(wǎng)與主機關(guān)系示意圖在這樣的描述方法下,無向圖中的頂點有三種類型:路由器,-ti和主機,通信子網(wǎng)邊界拓撲描述問題的解決方法如下:首先分別用g吼n和g分別表示路由器子網(wǎng)拓撲和主機,其中g(shù)n.中只有頂點沒有邊.對于每個g中的頂點,

10、在所有g(shù).盯中尋找類型為子網(wǎng)的頂點nefn0,如果ip在子網(wǎng)netno.范圍內(nèi),求neln0構(gòu)成的子圖和gh吲的聯(lián)圖,用g,替換gh0.即gh.st=gh.sivgnetn.其中g(shù)nei=(n01),)這樣處理后,與g川.的并圖就是連通的了.4網(wǎng)絡(luò)拓撲圖生成模型通過建立網(wǎng)絡(luò)拓撲圖描述模型,網(wǎng)絡(luò)拓撲發(fā)現(xiàn)問題就歸結(jié)為兩個圖論相關(guān)的簡單問題:將拓撲信息表示為無向圖;圖的并運算.本節(jié)結(jié)合例子來描述網(wǎng)絡(luò)拓撲圖生成模型.例子中,拓撲發(fā)現(xiàn)設(shè)備可以獲取目標網(wǎng)絡(luò)中路由器間傳輸?shù)膐spf路由協(xié)議報文,利用icmp探測網(wǎng)絡(luò)內(nèi)活動的主機ip地址.從ospf報文中可以提取網(wǎng)絡(luò)中某個路由器和與其直連的路由器之問的關(guān)系.a

11、dvertisingrouter是通告該報文的路由器的fd,下方的2個類型為ptp的鏈路描述說明該路由器與其他兩個路由器直連,這個兩個路由器的id就是報文中的ls_id字段,在該報文中的值分別為192.168.11.129和192.168.11.130.圖5是一個ospf報文的解析結(jié)果.在本算法中有三種網(wǎng)絡(luò)元素:路由器,主機,子網(wǎng).其中,路由器的標識是路由器id號,主機的標識是地址,子網(wǎng)標識是子網(wǎng)號.在算法中圖g的頂點對應(yīng)的網(wǎng)絡(luò)元素標識作為下標,也就是說標識為m的網(wǎng)絡(luò)元素在圖g中對應(yīng)的頂點為,例如,地4科技論文址為192.168.11.135的主機對應(yīng)的頂點為l92l68.35,網(wǎng)絡(luò)號為192

12、.18.0.0的子網(wǎng)對應(yīng)的頂點為l92l8oo.l1nk一5tateadvert1sementtype:router-lsa(1.).link一一stat星一id三-皇135一一一一一一一一一一一一一一,ladvertisi.router一:.皇一168一,35(192.一168一.ii一.一1曼ilssequencenumber:ox800066dclscheck5um:6ca6length:96田f1aqs:ox02(e)number0flnk5:6田圍田田固圈e:stubid:192.168.11.135data:255.255.呈55.一呈主ie:ptpid:192.168.11.12

13、9data:192.168.11.2一墮i1505064641type:51:ubid:192.168.11.0dal:a:255.255.255一至2一met盟vpe:ptpid:192.168.11.130data:192.168.11.38m.etr.j.type:stubid:192.168.11.36data:255.255.255.252metrc:type:stubid:_.18.0.0data:255.255.240.0metrc:圖5ospf報文解析結(jié)果設(shè)整個網(wǎng)絡(luò)的拓撲g,通信子網(wǎng)拓撲gc;通信子網(wǎng)局部拓撲圖;主機子圖;與g的聯(lián)圖.拓撲生成算法描述如下:第一步,根據(jù)路由協(xié)議生

14、成通信子網(wǎng)局部拓撲圖.在ospf協(xié)議中,每個鏈路狀態(tài)描述對應(yīng)的是個局部拓撲,=(e)其中,=口r,l,2,ecsl=mad,rohium,u如rohler|dtllsld2,n如roh_erldu|出lj,n是鏈路狀態(tài)描述的個數(shù).第二步,生成通信子網(wǎng)g.第一步中得到的所有通信子網(wǎng)局部拓撲(的并圖就是通信子網(wǎng)g,m是局部拓撲的個數(shù).第三步,利用icmp報文探測目標網(wǎng)絡(luò)地址段內(nèi)的所有地址,發(fā)現(xiàn)活動網(wǎng)絡(luò)主機,并為每個主機生成一個主機子圖(每個子圖由一個頂點組成)=(,ehi)其中,=),eh=.第四步,將主機與子網(wǎng)連接起來,生成主機一子網(wǎng)局部拓撲子圖.即對于每個主機子圖,其中=),=,從中找出頂點子

15、網(wǎng)號,滿足ip屬-t-u的地址范圍,求出主機與其所在子網(wǎng)構(gòu)成的局部拓撲g5u吖u=u=電信技術(shù)研究2007年第4期ghsl=ghlvg=(,巨,).其中,=子網(wǎng)號,=.第五步,生成整個目標網(wǎng)絡(luò)的拓撲圖gg=u(u).i=1g描述了整個目標網(wǎng)絡(luò)中包含的網(wǎng)絡(luò)元素,以及網(wǎng)絡(luò)元素之間的連接關(guān)系.整個算法的思想就是從局部到整體.先發(fā)現(xiàn)網(wǎng)絡(luò)元素,生成局部拓撲,找出局部拓撲之間的聯(lián)系,最后生成整個目標網(wǎng)絡(luò)的拓撲圖.由于使用圖的概念作為網(wǎng)絡(luò)拓撲圖的描述模型,可以用相應(yīng)的圖運算來完成網(wǎng)絡(luò)拓撲圖的生成過程,使得網(wǎng)絡(luò)拓撲圖的發(fā)現(xiàn),生成過程層次分明.雖然本例中的拓撲信息是從ospf和icmp協(xié)議中提取的,但是文中提出

16、的拓撲圖生成算法是與協(xié)議無關(guān)的,不管拓撲信息從哪些協(xié)議中提取,都可以用第3節(jié)中的拓撲描述模型進行歸一化,然后利用該算法生成目標網(wǎng)絡(luò)的拓撲圖.5總結(jié)由于還沒有公共的拓撲發(fā)現(xiàn)協(xié)議,因此,現(xiàn)有的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法中,用于拓撲發(fā)現(xiàn)的拓撲信息來自多種協(xié)議,不同的協(xié)議對應(yīng)的拓撲發(fā)現(xiàn)算法不同.本文建立的基于無向圖的拓撲描述模型可以將來自不同協(xié)議的拓撲信息歸一化為統(tǒng)一的表示形式,在此基礎(chǔ)上提出的拓撲生成算法獨立于協(xié)議,實現(xiàn)了各種網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法的統(tǒng)一描述.參考文獻1張先迪,李正島圖論及其應(yīng)用.北京:高等教育出版社.20042yuribreitbart,minosgarofalakis,benjai,clifrmartin,rajeevrastogiandavisilberschatz.topologydiscoveryinheterogeneousipnetworks:thenetlnventorysystem.ieee/acmtransactionsonnetworking,vol.12,no.3,june200431j.moy,ospfversion2,r