上傳人：伐***

認(rèn)證信息

認(rèn)證類型：機(jī)構(gòu)認(rèn)證

認(rèn)證主體：寧夏凱米世紀(jì)網(wǎng)絡(luò)科技有限公司

IP屬地：寧夏

統(tǒng)一社會(huì)信用代碼/組織機(jī)構(gòu)代碼

91640100MA774ECW4K

IP屬地：寧夏 上傳時(shí)間：2021-09-28 格式：DOC 頁(yè)數(shù)：11 大?。?9.50KB 積分：12 舉報(bào) 版權(quán)申訴

1、基于無(wú)向圖的網(wǎng)絡(luò)拓?fù)渖伤惴萍颊撐幕跓o(wú)向圖的網(wǎng)絡(luò)拓?fù)渖伤惴ㄍ舻挛年惤≌?網(wǎng)絡(luò)拓?fù)鋱D在網(wǎng)絡(luò)管理中起著非常重要的作用,但是目前還沒有任何公共協(xié)議用于網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn),因此,用于拓?fù)浒l(fā)現(xiàn)的拓?fù)湫畔⒁话愣紒?lái)源于多種協(xié)議本文建立了基于無(wú)向圖的網(wǎng)絡(luò)拓?fù)涿枋瞿Ｐ?用來(lái)描述形式各異的拓?fù)湫畔?并提出了基于該模型的拓?fù)渖伤惴?該算法與網(wǎng)絡(luò)協(xié)議無(wú)關(guān),適用性強(qiáng).關(guān)鍵詞:網(wǎng)絡(luò)拓?fù)渫負(fù)浒l(fā)現(xiàn)拓?fù)涿枋瞿Ｐ蛥f(xié)議無(wú)關(guān)的拓?fù)渖伤惴o(wú)向圖1引言拓?fù)涔芾硎蔷W(wǎng)絡(luò)管理的重要組成部分,是配置管理的核心和故障管理的基礎(chǔ).拓?fù)浒l(fā)現(xiàn)是指利用網(wǎng)管協(xié)議或工具搜集分布在網(wǎng)絡(luò)各處的原始拓?fù)鋽?shù)據(jù),通過(guò)拓?fù)渖伤惴ňC合出完整的拓?fù)湫畔?網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)

2、包括兩方面的內(nèi)容:拓?fù)湫畔⑹占屯負(fù)鋱D的生成.由于目前還沒有任何公共協(xié)議可用于拓?fù)浒l(fā)現(xiàn),加上網(wǎng)絡(luò)和網(wǎng)管協(xié)議種類眾多,因此,現(xiàn)有的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法中的拓?fù)湫畔?lái)源于多種協(xié)議.怎樣用統(tǒng)一的模型來(lái)描述這些拓?fù)湫畔?從而用統(tǒng)一的算法來(lái)描述現(xiàn)有的拓?fù)浒l(fā)現(xiàn)方法值得研究.本文在充分總結(jié)分析網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法特點(diǎn)的基礎(chǔ)上,歸納其共性,抽象出了網(wǎng)絡(luò)拓?fù)涿枋瞿Ｐ秃蛥f(xié)議無(wú)關(guān)的網(wǎng)絡(luò)拓?fù)鋱D生成算法.2基本思想本算法的基本思想是由局部拓?fù)渖烧麄€(gè)目標(biāo)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).網(wǎng)絡(luò)拓?fù)湫畔⑹菑木W(wǎng)絡(luò)線路上的多種協(xié)議中收集來(lái)的,從某一種協(xié)議中提取出來(lái)的拓?fù)湫畔⒅皇悄繕?biāo)網(wǎng)絡(luò)中某一片的局部拓?fù)?如兩個(gè)或多個(gè)路由器的連接.這些局部拓?fù)涫怯脕?lái)還原

3、整個(gè)目標(biāo)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的原材料,我們要像拼圖一樣把這些原材料拼接起來(lái).不同的協(xié)議中包含的拓?fù)湫畔⒃诒硎拘问缴嫌泻艽蟛町?因此,在拼接之前,要把零散的,形式各異的局部拓?fù)湫畔w一化為統(tǒng)一的表示形式.這就需要為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的描述建立一個(gè)模型,在該模型的基礎(chǔ)上實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)鋱D的拼接,拼接的過(guò)程就是網(wǎng)絡(luò)拓?fù)鋱D的生成過(guò)程.從上面的敘述中可以看出,算法的核心是網(wǎng)絡(luò)拓?fù)涿枋瞿Ｐ秃途W(wǎng)絡(luò)拓?fù)鋱D生成算法.3網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)描述模型3.1模型選擇要求建立網(wǎng)絡(luò)拓?fù)涿枋瞿Ｐ偷哪康氖怯脕?lái)表示從各種協(xié)議中獲取的各種拓?fù)湫畔?將異構(gòu)的拓?fù)湫畔w一化.既然是要用局部拓?fù)淦唇诱麄€(gè)目標(biāo)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),那么局部拓?fù)浜驼麄€(gè)網(wǎng)絡(luò)拓?fù)渚蛻?yīng)該用一個(gè)

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

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

6、和的每個(gè)頂點(diǎn)連接起來(lái)所得到的圖稱為gl和g2的聯(lián)圖,記為vg2.圖2是圖的聯(lián)運(yùn)算示意圖.2ag1bag2glvg圖2圖的聯(lián)運(yùn)算示意圖b科技論文3.3網(wǎng)絡(luò)拓?fù)涿枋瞿Ｐ途W(wǎng)絡(luò)拓?fù)涿枋瞿Ｐ褪峭負(fù)渖伤惴ǖ幕A(chǔ),只有建立了合適的描述模型,才能使拓?fù)渖伤惴í?dú)立于網(wǎng)絡(luò)協(xié)議,只和描述模型有關(guān).網(wǎng)絡(luò)拓?fù)涿枋瞿Ｐ偷淖饔檬?(1)將從各種協(xié)議中獲取的拓?fù)湫畔⒈硎緸榻y(tǒng)一的形式,即拓?fù)湫畔⒌臍w一化.(2)作為拓?fù)湫畔⑴c拓?fù)渖伤惴ㄖg的中介.歸一化后的拓?fù)湫畔⒆鳛橥負(fù)渖伤惴ǖ妮斎?而不是各種表示形式各異的原始拓?fù)湫畔?這樣拓?fù)渖伤惴ň涂梢元?dú)立于網(wǎng)絡(luò)協(xié)議了,從不同的協(xié)議中提取的拓?fù)湫畔⒔?jīng)過(guò)描述模型歸一化后都可以使用

7、同一個(gè)拓?fù)渖伤惴ㄉ赏負(fù)鋱D.根據(jù)上述圖的相關(guān)概念,網(wǎng)絡(luò)拓?fù)鋱D可以抽象為簡(jiǎn)單無(wú)向圖,圖的頂點(diǎn)表示網(wǎng)絡(luò)元素,邊表示網(wǎng)絡(luò)元素之間的連接關(guān)系.根據(jù)這個(gè)模型,網(wǎng)絡(luò)拓?fù)鋱D的還原過(guò)程可以概括為兩個(gè)步驟:第一步,把從各種協(xié)議中提取的拓?fù)湫畔⒈硎緸橐粋€(gè)個(gè)的子圖gi,g:,g;第二步,求子圖的并圖g.g:glug2uug并圖g就是整個(gè)目標(biāo)網(wǎng)絡(luò)的拓?fù)鋱D.3.4通信子網(wǎng)邊界拓?fù)涿枋鰡?wèn)題及解決方法網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)中,一般是利用路由信息來(lái)發(fā)現(xiàn)路由器子網(wǎng),利用主動(dòng)探測(cè)獲取存活主機(jī)地址j.路由信息只是描述用戶子網(wǎng)路由而不是主機(jī)路由,因此,通信子網(wǎng)的邊界拓?fù)溆脽o(wú)向圖描述為路由器拓?fù)渥訄Dg,g刪中的頂點(diǎn)代表用戶子網(wǎng),而不是主機(jī);主

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

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

10、在所有g(shù).盯中尋找類型為子網(wǎng)的頂點(diǎn)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ò)拓?fù)鋱D生成模型通過(guò)建立網(wǎng)絡(luò)拓?fù)鋱D描述模型,網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)問(wèn)題就歸結(jié)為兩個(gè)圖論相關(guān)的簡(jiǎn)單問(wèn)題:將拓?fù)湫畔⒈硎緸闊o(wú)向圖;圖的并運(yùn)算.本節(jié)結(jié)合例子來(lái)描述網(wǎng)絡(luò)拓?fù)鋱D生成模型.例子中,拓?fù)浒l(fā)現(xiàn)設(shè)備可以獲取目標(biāo)網(wǎng)絡(luò)中路由器間傳輸?shù)膐spf路由協(xié)議報(bào)文,利用icmp探測(cè)網(wǎng)絡(luò)內(nèi)活動(dòng)的主機(jī)ip地址.從ospf報(bào)文中可以提取網(wǎng)絡(luò)中某個(gè)路由器和與其直連的路由器之問(wèn)的關(guān)系.a

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

12、.18.0.0的子網(wǎng)對(duì)應(yīng)的頂點(diǎn)為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報(bào)文解析結(jié)果設(shè)整個(gè)網(wǎng)絡(luò)的拓?fù)鋑,通信子網(wǎng)拓?fù)鋑c;通信子網(wǎng)局部拓?fù)鋱D;主機(jī)子圖;與g的聯(lián)圖.拓?fù)渖伤惴枋鋈缦?第一步,根據(jù)路由協(xié)議生

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

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

16、的拓?fù)鋱D生成算法是與協(xié)議無(wú)關(guān)的,不管拓?fù)湫畔哪男﹨f(xié)議中提取,都可以用第3節(jié)中的拓?fù)涿枋瞿Ｐ瓦M(jìn)行歸一化,然后利用該算法生成目標(biāo)網(wǎng)絡(luò)的拓?fù)鋱D.5總結(jié)由于還沒有公共的拓?fù)浒l(fā)現(xiàn)協(xié)議,因此,現(xiàn)有的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法中,用于拓?fù)浒l(fā)現(xiàn)的拓?fù)湫畔?lái)自多種協(xié)議,不同的協(xié)議對(duì)應(yīng)的拓?fù)浒l(fā)現(xiàn)算法不同.本文建立的基于無(wú)向圖的拓?fù)涿枋瞿Ｐ涂梢詫?lái)自不同協(xié)議的拓?fù)湫畔w一化為統(tǒng)一的表示形式,在此基礎(chǔ)上提出的拓?fù)渖伤惴í?dú)立于協(xié)議,實(shí)現(xiàn)了各種網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法的統(tǒng)一描述.參考文獻(xiàn)1張先迪,李正島圖論及其應(yīng)用.北京:高等教育出版社.20042yuribreitbart,minosgarofalakis,benjai,clifrmartin,rajeevrastogiandavisilberschatz.topologydiscoveryinheterogeneousipnetworks:thenetlnventorysystem.ieee/acmtransactionsonnetworking,vol.12,no.3,june200431j.moy,ospfversion2,r