基于AFT滿足下行約束的物理拓?fù)浒l(fā)現(xiàn)方法
2016-11-17 05:43:25刁興春丁晨路蔣國(guó)權(quán)
電子學(xué)報(bào) 2016年8期
張 賓,刁興春,劉 藝,俞 赟,袁 震,丁晨路,蔣國(guó)權(quán)
(總參第63研究所,江蘇南京 210007)
?
基于AFT滿足下行約束的物理拓?fù)浒l(fā)現(xiàn)方法
張 賓,刁興春,劉 藝,俞 赟,袁 震,丁晨路,蔣國(guó)權(quán)
(總參第63研究所,江蘇南京 210007)
物理拓?fù)浒l(fā)現(xiàn)對(duì)于網(wǎng)絡(luò)管理和應(yīng)用具有重要意義,基于地址轉(zhuǎn)發(fā)表的物理拓?fù)浒l(fā)現(xiàn)是目前學(xué)術(shù)界研究的熱點(diǎn)問題.但由于實(shí)際網(wǎng)絡(luò)的地址轉(zhuǎn)發(fā)表通常不完整,導(dǎo)致了物理拓?fù)浒l(fā)現(xiàn)的難度,本文基于降低在實(shí)際拓?fù)浒l(fā)現(xiàn)時(shí)對(duì)AFT完整性的要求,定義了地址轉(zhuǎn)發(fā)表的三類約束,并提出了地址轉(zhuǎn)發(fā)表滿足下行約束的樹型剪裁算法,用于發(fā)現(xiàn)子網(wǎng)的物理拓?fù)浣Y(jié)構(gòu).算法極大地降低了拓?fù)浒l(fā)現(xiàn)對(duì)地址轉(zhuǎn)發(fā)表完整性的要求,是對(duì)僅通過下行端口地址轉(zhuǎn)發(fā)表進(jìn)行拓?fù)浒l(fā)現(xiàn)的最松約束.模擬仿真實(shí)驗(yàn)驗(yàn)證了算法的正確性和高效性,算法在實(shí)際網(wǎng)管系統(tǒng)中的部署進(jìn)一步驗(yàn)證了算法在真實(shí)網(wǎng)絡(luò)環(huán)境中的實(shí)用性.
物理拓?fù)浒l(fā)現(xiàn);地址轉(zhuǎn)發(fā)表;網(wǎng)絡(luò)管理;
電子學(xué)報(bào)URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.014
1 引言
網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)分為邏輯(網(wǎng)絡(luò)層、三層)與物理(鏈路層、二層)拓?fù)浒l(fā)現(xiàn)兩種,邏輯拓?fù)浒l(fā)現(xiàn)是指發(fā)現(xiàn)路由器間及路由器和各個(gè)子網(wǎng)間的連接關(guān)系,而忽略子網(wǎng)內(nèi)交換機(jī)與主機(jī)等設(shè)備的物理連接關(guān)系,物理拓?fù)浒l(fā)現(xiàn)是指發(fā)現(xiàn)管理域內(nèi)交換機(jī)與主機(jī)及路由器等設(shè)備間的實(shí)際連接關(guān)系.
網(wǎng)絡(luò)層的拓?fù)浒l(fā)現(xiàn)按發(fā)現(xiàn)的不同級(jí)別可以分為[1]:IP接口級(jí)、路由器級(jí)、PoP級(jí)、AS級(jí),發(fā)現(xiàn)方法主要有:Ping方法、Traceroute方法、DNS方法、SNMP和ARP方法、路由協(xié)議方法、Tomography方法等.網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)技術(shù)研究的相對(duì)成熟,有很多項(xiàng)目和產(chǎn)品應(yīng)用這些技術(shù)進(jìn)行拓?fù)浒l(fā)現(xiàn),比如惠普的Open View、IBM的Tivoli等,然而這些產(chǎn)品都依賴于私有協(xié)議,難以發(fā)現(xiàn)大型局域網(wǎng)中含有不同廠商交換設(shè)備的二層拓?fù)浣Y(jié)構(gòu).許多網(wǎng)絡(luò)管理任務(wù),比如性能分析、網(wǎng)絡(luò)規(guī)劃和模擬、異常檢測(cè)等都依賴于二層的拓?fù)浒l(fā)現(xiàn),因此,準(zhǔn)確實(shí)時(shí)的二層拓?fù)浒l(fā)現(xiàn)對(duì)于網(wǎng)絡(luò)管理和應(yīng)用具有重要的意義.
網(wǎng)絡(luò)設(shè)備的地址轉(zhuǎn)發(fā)表(Address Forwarding Table,AFT)記錄了設(shè)備端口在一段時(shí)間內(nèi)的實(shí)際通信的設(shè)備地址,基于地址轉(zhuǎn)發(fā)表的物理拓?fù)浒l(fā)現(xiàn)是目前學(xué)術(shù)界研究的熱點(diǎn)問題,也是物理拓?fù)浒l(fā)現(xiàn)的最重要方法.但通常實(shí)際網(wǎng)絡(luò)的AFT不完整,導(dǎo)致了物理拓?fù)浒l(fā)現(xiàn)的困難,本文基于降低在實(shí)際拓?fù)浒l(fā)現(xiàn)時(shí)對(duì)AFT完整性的要求,定義了AFT的三類約束,并提出了AFT滿足下行約束的樹型剪裁算法,用于發(fā)現(xiàn)子網(wǎng)的AFT滿足下行約束的物理拓?fù)浣Y(jié)構(gòu),算法僅依賴于下行AFT,且不要求下行AFT完整,本文提出的算法極大地降低了對(duì)AFT完整性的要求,是對(duì)僅通過下行端口AFT進(jìn)行拓?fù)浒l(fā)現(xiàn)的最松約束.
2 相關(guān)工作
二層的拓?fù)渲噪y以發(fā)現(xiàn)的主要原因是:(1)大部分的拓?fù)浒l(fā)現(xiàn)工具主要用于發(fā)現(xiàn)網(wǎng)絡(luò)層拓?fù)?要求管理員手工維護(hù)二層連接信息,而且MIB中并不直接提供網(wǎng)絡(luò)節(jié)點(diǎn)間的直接鏈接信息;(2)二層設(shè)備的地址轉(zhuǎn)發(fā)表包含了可達(dá)的地址信息,但信息通常不完整.
為了克服這些困難,IETF于2000年推出物理拓?fù)銶IB[2],試圖解決網(wǎng)絡(luò)層以下拓?fù)浣Y(jié)構(gòu)的發(fā)現(xiàn)問題,但是由于沒有確定如何獲取這些MIB對(duì)象的機(jī)制而難以應(yīng)用,為了彌補(bǔ)這種狀況,IEEE提出鏈路層發(fā)現(xiàn)協(xié)議(LLDP)作為802.1AB-205標(biāo)準(zhǔn)的一部分,LLDP是一個(gè)廠商無關(guān)的二層協(xié)議,它允許網(wǎng)絡(luò)設(shè)備在本地子網(wǎng)中通告自己的設(shè)備標(biāo)識(shí)和性能.但是目前已部署的很多設(shè)備上并不支持這個(gè)協(xié)議.還有一種鄰居發(fā)現(xiàn)協(xié)議CDP,而CDP是思科私有的協(xié)議,只能發(fā)現(xiàn)思科的二層設(shè)備.
除了可以應(yīng)用鄰居發(fā)現(xiàn)協(xié)議來直接發(fā)現(xiàn)二層設(shè)備的連接關(guān)系外,目前二層拓?fù)浒l(fā)現(xiàn)算法主要有基于生成樹協(xié)議、基于地址轉(zhuǎn)發(fā)表、基于端口流量特征及基于探測(cè)包的方法.
文獻(xiàn)[3～5]將網(wǎng)絡(luò)流量特征引入拓?fù)浒l(fā)現(xiàn)算法中,把網(wǎng)絡(luò)設(shè)備接口的流量變化看作隨機(jī)過程進(jìn)行研究,嘗試通過流量特征相近程度來推斷網(wǎng)絡(luò)的物理拓?fù)?但這些方法依賴于統(tǒng)計(jì)相關(guān),只能大致推斷出可能的鏈接,并不能確定設(shè)備間一定存在相應(yīng)的連接,而且在不同子網(wǎng)間的設(shè)備互聯(lián)時(shí)這種方法的正確性還有待驗(yàn)證.
文獻(xiàn)[6]中提出一種基于生成樹協(xié)議的方法,其基本思想是利用生成樹的信息構(gòu)建網(wǎng)橋設(shè)備之間的連接關(guān)系,該方法的優(yōu)點(diǎn)在于時(shí)間和空間消耗較小,可以發(fā)現(xiàn)局域網(wǎng)中的備用鏈路,缺點(diǎn)是許多交換機(jī)不支持生成樹協(xié)議,使其適用范圍受到一定的限制,并且該方法不能發(fā)現(xiàn)交換機(jī)和主機(jī)之間的連接關(guān)系.
文獻(xiàn)[7]中提出一種基于探測(cè)包的方法,其基本思想是,在每個(gè)主機(jī)上設(shè)置一個(gè)代理進(jìn)程,產(chǎn)生一些探測(cè)包,并把網(wǎng)卡設(shè)置在混雜模式下(在該工作模式下,網(wǎng)卡可以接收到網(wǎng)段內(nèi)的所有數(shù)據(jù)包),然后,根據(jù)每個(gè)主機(jī)所接收的數(shù)據(jù)包來判斷設(shè)備之間的連接關(guān)系,該種方法可以判斷出交換機(jī)之間、交換機(jī)和主機(jī)之間的連接關(guān)系,缺點(diǎn)是在每個(gè)主機(jī)設(shè)備上都要設(shè)置一個(gè)代理進(jìn)程,這對(duì)一個(gè)較大型的網(wǎng)絡(luò)來說是不太可能的事情.
總體來說,上述方法都具有較大的局限性,目前的二層拓?fù)浒l(fā)現(xiàn)的研究重點(diǎn)主要基于地址轉(zhuǎn)發(fā)表,每臺(tái)交換機(jī)都維護(hù)一張地址轉(zhuǎn)發(fā)表,地址轉(zhuǎn)發(fā)表的記錄格式可以簡(jiǎn)單地表示為
貝爾實(shí)驗(yàn)室的Breitbart等人提出了基于完整地址轉(zhuǎn)發(fā)表的物理拓?fù)浒l(fā)現(xiàn)方法[8,9],可以發(fā)現(xiàn)跨子網(wǎng)交換域的拓?fù)浣Y(jié)構(gòu),其算法的核心是直接連接定理:分屬兩個(gè)交換機(jī)的一對(duì)端口是相連的,當(dāng)且僅當(dāng)這兩個(gè)端口的地址轉(zhuǎn)發(fā)條目集合的交集為空,且其并集中包含了該子網(wǎng)中所有交換機(jī)的地址條目.Bejerano等人[10]進(jìn)一步提出一種基于不同完整地址轉(zhuǎn)發(fā)表的多子網(wǎng)拓?fù)浒l(fā)現(xiàn)算法,該方法首先根據(jù)地址轉(zhuǎn)發(fā)表和子網(wǎng)信息構(gòu)造出不同結(jié)點(diǎn)之間的粗略路徑,然后進(jìn)一步為每一條路徑構(gòu)造出一組路徑約束,利用路徑約束信息,不斷細(xì)化粗略路徑,最終確定一條唯一的路徑.
基于完整地址轉(zhuǎn)發(fā)表的方法存在一個(gè)難以克服的缺點(diǎn),即需要保證地址轉(zhuǎn)發(fā)表的完整性.為了做到這一點(diǎn),Breitbart[8,9]提出增加額外流量和連續(xù)采集兩種方法來提高地址轉(zhuǎn)發(fā)表的完整性.鄭海等人[11]通過在管理站上Ping所有交換機(jī)的方法來保證下行端口的地址轉(zhuǎn)發(fā)表的完整性.在實(shí)際網(wǎng)絡(luò)中,由于地址轉(zhuǎn)發(fā)表老化機(jī)制的存在、地址轉(zhuǎn)發(fā)表長(zhǎng)度的限制以及SNMP協(xié)議采用無連接的UDP進(jìn)行通信,不能提供可靠的數(shù)據(jù)傳輸,因此,交換機(jī)地址轉(zhuǎn)發(fā)表的完整性很難保證,從而影響這些算法的準(zhǔn)確性.
鄭海等人[11]提出了一種方法,該方法僅要求只要下行端口的地址轉(zhuǎn)發(fā)表是完整的,就可以構(gòu)造出交換機(jī)之間的連接關(guān)系.陳福等[12]提出了一種新型的數(shù)據(jù)結(jié)構(gòu)“樹型圖”,也僅要求下行端口的地址轉(zhuǎn)發(fā)表完整即可構(gòu)造出連接關(guān)系.Lowekamp等人[13]提出了一種更為寬松的基于非完整地址轉(zhuǎn)發(fā)表的拓?fù)浒l(fā)現(xiàn)算法,算法要求一對(duì)交換機(jī)節(jié)點(diǎn)的AFT間至少共享三個(gè)轉(zhuǎn)發(fā)條目,該算法把網(wǎng)絡(luò)拓?fù)渲械倪B接分為兩種類型:直接連接和間接連接,該算法基于這樣一個(gè)定理(間接連接定理):如果兩個(gè)交換機(jī)僅有一對(duì)端口的通過集相交為空,則這對(duì)端口必然相連(間接連接).但這三種方法一個(gè)較大的缺點(diǎn)是只能適用于一個(gè)子網(wǎng)的拓?fù)浒l(fā)現(xiàn),在交換域跨越多個(gè)子網(wǎng)時(shí)很容易出錯(cuò).
孫延濤等[14]試圖提出一個(gè)完備的規(guī)則,如果僅依賴地址轉(zhuǎn)發(fā)表,兩個(gè)交換機(jī)之間的端口連接是可以唯一確定的,則利用此規(guī)則,就可以唯一確定這兩個(gè)端口的連接關(guān)系.在此規(guī)則的基礎(chǔ)上,文中提出了一種有效的算法推導(dǎo)出交換式以太網(wǎng)的物理拓?fù)潢P(guān)系,但文中并沒有對(duì)所提規(guī)則的完備性作證明.Bejerano[15,16]提出了一個(gè)很簡(jiǎn)單的方法來發(fā)現(xiàn)多子網(wǎng)局域網(wǎng)的拓?fù)浣Y(jié)構(gòu),文中定義了一種Skeleton-Tree的數(shù)據(jù)結(jié)構(gòu),算法主要思想是用Skeleton-Tree自頂向下構(gòu)建每個(gè)子網(wǎng)的拓?fù)浣Y(jié)構(gòu),然后子網(wǎng)間合并出整個(gè)交換域的拓?fù)浣Y(jié)構(gòu),這個(gè)算法能發(fā)現(xiàn)大部分的網(wǎng)絡(luò)拓?fù)淝闆r,但這個(gè)算法要求下行端口AFT完整且上行端口AFT中含有根節(jié)點(diǎn)的地址.
Gobjuka和Breitbart在他們的工作[17～22]中證明了AFT不完整時(shí)二層拓?fù)浒l(fā)現(xiàn)的NP難問題,并且給定AFT表是否能定義一個(gè)唯一的拓?fù)湟彩荖P難問題;在給定AFT完整時(shí),他們提出一種算法能發(fā)現(xiàn)所有可能的拓?fù)鋱D并定義了拓?fù)湮ㄒ坏臈l件;在給定AFT不完整時(shí),他們提出了一組規(guī)則來擴(kuò)展AFT并提出了三種算法滿足不同情況需要,第一個(gè)是當(dāng)所有節(jié)點(diǎn)的AFT中都含有同一個(gè)節(jié)點(diǎn)地址的情況,第二個(gè)是每個(gè)節(jié)點(diǎn)的AFT在半完全的情況,第三個(gè)是針對(duì)任意AFT情況但并不保證能發(fā)現(xiàn)正確的拓?fù)浣Y(jié)構(gòu).
在對(duì)相關(guān)工作的闡述中我們可以看到,由于實(shí)際網(wǎng)絡(luò)的AFT通常不完整導(dǎo)致了拓?fù)浒l(fā)現(xiàn)的困難,目前僅依賴下行端口AFT的拓?fù)浒l(fā)現(xiàn)方法是鄭海等人[11]提出的,但他們的方法要求下行端口的AFT完整,這在實(shí)際網(wǎng)絡(luò)中是很難滿足的,基于這樣的動(dòng)機(jī),本文提出了一個(gè)基于下行端口AFT的樹型剪裁算法,本文提出的算法是對(duì)僅通過下行端口AFT進(jìn)行拓?fù)浒l(fā)現(xiàn)的AFT完整性要求的最松約束.
3 下行約束算法
3.1 算法基礎(chǔ)
由于交換域內(nèi)的交換機(jī)必須遵循生成樹協(xié)議,其它鏈路只作為備用鏈路而不參與實(shí)際的數(shù)據(jù)傳輸,因此,可以將交換域建模為一棵無向樹G=(D,E),D是交換域內(nèi)所有結(jié)點(diǎn)(網(wǎng)絡(luò)設(shè)備)的集合,E是設(shè)備端口之間的直接連接集合,若S表示所有交換機(jī)的集合,H表示所有主機(jī)、路由器及一些啞設(shè)備(HUB、中繼器等)的集合(二層拓?fù)浒l(fā)現(xiàn)可以將路由器作為主機(jī)處理),則D=S+H,每臺(tái)交換機(jī)都維護(hù)一張地址轉(zhuǎn)發(fā)表(AFT),若以Si表示交換域中第i臺(tái)交換機(jī),Sij表示Si的第j個(gè)接口,Aij表示端口Sij的地址轉(zhuǎn)發(fā)表,如果Aij包含了Sij所能接收到的所有數(shù)據(jù)幀的MAC地址,則稱Sij的地址轉(zhuǎn)發(fā)表是完整的.在根交換機(jī)確定的情況下,我們稱樹型結(jié)構(gòu)中交換機(jī)上連鏈路的端口為上行端口,顯然上行端口是唯一的,交換機(jī)其它的端口稱為下行端口.
如果一個(gè)交換域只包含一個(gè)子網(wǎng),那么Aij就對(duì)應(yīng)于網(wǎng)絡(luò)中節(jié)點(diǎn)Si通過端口Sij在交換域生成樹的路徑中可能到達(dá)的節(jié)點(diǎn)集合,當(dāng)AFT完整時(shí),Aij含有了路徑中所有節(jié)點(diǎn)的集合[8,9].但這對(duì)于交換域含有多個(gè)子網(wǎng)的情況并不成立,因此,一個(gè)多子網(wǎng)的交換域內(nèi)即使所有端口的AFT完整也并一定能確定唯一的拓?fù)浣Y(jié)構(gòu)[8,9].如果我們假定網(wǎng)絡(luò)中不含有度數(shù)為2的啞設(shè)備,這時(shí),單子網(wǎng)交換域網(wǎng)絡(luò)的AFT完整必定可以唯一確定這個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),因此,單子網(wǎng)交換域的生成樹G有以下性質(zhì).
性質(zhì)1 如果單子網(wǎng)交換域網(wǎng)絡(luò)的AFT完整,這樣的AFT必定可以唯一確定網(wǎng)絡(luò)生成樹G的拓?fù)浣Y(jié)構(gòu).
證明 由于生成樹G中任意一個(gè)節(jié)點(diǎn)Si的Aij完整,此時(shí),Aij含有了端口Sij在交換域生成樹的路徑中所有可達(dá)節(jié)點(diǎn)的集合,這時(shí),對(duì)于網(wǎng)絡(luò)中的另外一個(gè)任意節(jié)點(diǎn)的端口Smn的地址轉(zhuǎn)發(fā)表Amn與Aij只可能存在兩種情況:(1)Amn≠Aij,兩者不等時(shí),則這兩個(gè)端口的連接也必定不同,否則必然Amn=Aij;(2)Amn=Aij,即這兩個(gè)端口的AFT完全相同,這時(shí)可以判定是存在一個(gè)啞設(shè)備連接這兩個(gè)端口.因此,無論對(duì)于哪種情況,都可以唯一確定網(wǎng)絡(luò)生成樹的拓?fù)浣Y(jié)構(gòu).
性質(zhì)2 網(wǎng)絡(luò)生成樹G中節(jié)點(diǎn)的上行端口是唯一的.
這是樹的基本性質(zhì).
除了性質(zhì)2,樹的其它性質(zhì)也可以用于網(wǎng)絡(luò)生成樹G中,根據(jù)性質(zhì)1,完整的AFT可以確定唯一正確的網(wǎng)絡(luò)生成樹的拓?fù)浣Y(jié)構(gòu),因此,對(duì)于單子網(wǎng)交換域,我們可以定義如下三類約束:
定義1 最小約束AFT 如果通過子網(wǎng)的網(wǎng)絡(luò)節(jié)點(diǎn)的AFT可以構(gòu)造出唯一正確的子網(wǎng)拓?fù)浣Y(jié)構(gòu),則稱這樣的AFT滿足最小約束,即滿足最小約束的AFT可以唯一確定子網(wǎng)的拓?fù)浣Y(jié)構(gòu).
定義2 下行約束AFT 在根交換機(jī)確定的情況下,每個(gè)交換機(jī)的上行端口至少包含一個(gè)祖宗交換機(jī)地址(即不能為空),這時(shí),如果僅通過交換機(jī)的下行端口的AFT就可以確定子網(wǎng)的唯一拓?fù)?則稱AFT滿足下行約束.
定義3 上行約束AFT 在根交換機(jī)確定的情況下,每個(gè)交換機(jī)的下行端口至少包含一個(gè)子孫節(jié)點(diǎn)的地址(即不能為空),這時(shí),如果僅通過交換機(jī)的上行端口的AFT就可以確定子網(wǎng)的唯一拓?fù)?則稱AFT滿足上行約束.
顯然,子網(wǎng)的完整的AFT是滿足最小約束的,滿足最小約束的AFT卻并不一定是完整的,但滿足最小約束的AFT和完整的AFT都可以唯一定義一個(gè)子網(wǎng)的拓?fù)浣Y(jié)構(gòu),因此,總可以找到一些規(guī)則,使得滿足最小約束的AFT經(jīng)規(guī)則推導(dǎo)后成為完整的AFT;同理,對(duì)于上行端口確定時(shí),下行約束AFT也可以通過一些規(guī)則得到下行完整的AFT;對(duì)于下行端口確定時(shí),上行約束AFT也可以通過一些規(guī)則得到上行完整的AFT.從對(duì)這三個(gè)約束的定義可以知道,滿足最小約束AFT是能通過AFT得到子網(wǎng)唯一正確拓?fù)浣Y(jié)構(gòu)的AFT不完整的最松約束,滿足下行約束AFT是僅通過下行AFT得到子網(wǎng)唯一正確拓?fù)浣Y(jié)構(gòu)的下行端口AFT不完整的最松約束,滿足上行約束AFT是僅通過上行AFT得到子網(wǎng)唯一正確拓?fù)浣Y(jié)構(gòu)的上行端口AFT不完整的最松約束.
雖然滿足最小約束AFT是AFT不完整的最松約束,但顯然研究通過滿足最小約束AFT得到子網(wǎng)唯一正確拓?fù)浣Y(jié)構(gòu)的拓?fù)浒l(fā)現(xiàn)算法是最困難的,研究滿足下行約束AFT和上行約束AFT算法相對(duì)要簡(jiǎn)單些,本文著眼于研究滿足下行約束AFT的拓?fù)浒l(fā)現(xiàn)算法,上行約束和最小約束算法的研究會(huì)在我們的后續(xù)工作中逐步展開,同時(shí)這里也為其他學(xué)者提供了一個(gè)開放的研究課題.
對(duì)于滿足下行約束的AFT,具有這樣特征,樹中每個(gè)節(jié)點(diǎn)的下行端口的AFT中或者含有其孩子節(jié)點(diǎn)的地址或含有孩子節(jié)點(diǎn)至少兩個(gè)下行鏈路可達(dá)的節(jié)點(diǎn)的地址,如圖1表示一條從樹根到葉子的任意一條鏈路,Si和Sk表示鏈路中任意兩個(gè)相鄰節(jié)點(diǎn),其中Si是Sk的父親節(jié)點(diǎn),以Bkt表示Sk下行端口t的可達(dá)地址,則Si的端口j的AFT或者含有Sk的地址,即Sk∈Aij,或者?a∈Akl且?b∈Akt,且{a,b}?Aij,因此,我們有定理1.
定理1 滿足下行約束的AFT要求每個(gè)節(jié)點(diǎn)的下行端口的AFT中或者含有其孩子節(jié)點(diǎn)的地址或者含有孩子節(jié)點(diǎn)至少兩個(gè)下行端口所連接的下行鏈路中節(jié)點(diǎn)的地址.
證明:圖1中的父子節(jié)點(diǎn)Si和Sk不失一般性,若Sk?Aij,且Aij只含有Sk一個(gè)下行端口(如端口l)的下行鏈路中節(jié)點(diǎn)的地址,則圖1中節(jié)點(diǎn)Si和Sk的位置顯然可以進(jìn)行互換,互換后的拓?fù)浣Y(jié)構(gòu)并不影響任何節(jié)點(diǎn)的AFT,因此,不滿足下行約束的AFT會(huì)導(dǎo)致鏈路中任意兩個(gè)父子節(jié)點(diǎn)Si和Sk的順序無法確定.
定理得證.
從定理1可以知道,如果節(jié)點(diǎn)中的孩子節(jié)點(diǎn)只有一個(gè)下行端口,則節(jié)點(diǎn)必含有孩子節(jié)點(diǎn)的地址.對(duì)于滿足下行約束的子網(wǎng)的AFT,顯然無向樹G=(D,E)變成了下行有向樹,每個(gè)父親節(jié)點(diǎn)或者有指向其孩子節(jié)點(diǎn)的鏈接(也同時(shí)有可能有指向任意子孫的),或者有指向其孩子節(jié)點(diǎn)至少兩個(gè)下行端口可達(dá)的子孫節(jié)點(diǎn),這樣我們就可以提出一個(gè)十分簡(jiǎn)單有效的樹型剪裁算法,以O(shè)(n2)的算法復(fù)雜度來得到正確的拓?fù)浣Y(jié)構(gòu),n為節(jié)點(diǎn)數(shù).樹型剪裁算法基于這樣一個(gè)簡(jiǎn)單的思想,如果一棵樹所有的分叉及其連接的葉子被砍掉,而砍掉的分叉變成一個(gè)新葉子,這樣樹就可以一層層被砍光.在介紹算法前,我們先給出四個(gè)定義.
定義4 葉交換機(jī) 交換機(jī)的所有下行端口都連接的是非交換機(jī)設(shè)備,稱這樣的交換機(jī)為葉交換機(jī).
定義5 中間交換機(jī) 定義所有的非葉交換機(jī)為中間交換機(jī).
定義6 葉端口 定義交換機(jī)連接葉交換機(jī)的端口為葉端口.
定義7 葉子 定義所有終端設(shè)備(如主機(jī)和路由器)為葉子節(jié)點(diǎn).
葉交換機(jī)的下行端口可以連接主機(jī)、路由器、HUB等設(shè)備,顯然中間交換機(jī)至少有兩個(gè)端口連接其它交換機(jī),由此,可以證明以下三個(gè)定理.
定理2 葉交換機(jī)只有一個(gè)端口的AFT含有其它交換機(jī)的地址.
證明:根據(jù)葉交換機(jī)的定義,葉交換機(jī)的下行端口不可能連接其它交換機(jī),而樹型結(jié)構(gòu)中的上行端口只有一個(gè),根據(jù)下行約束的定義,每個(gè)交換機(jī)的上行端口至少包含一個(gè)祖宗交換機(jī)地址(即不能為空),因此,葉交換機(jī)只有一個(gè)端口(上行端口)的AFT含有其它交換機(jī)的地址.
定理得證.
定理3 中間交換機(jī)要么至少有兩個(gè)端口的AFT含有其它交換機(jī)的地址,要么一個(gè)端口的AFT含有其它交換機(jī)的地址并且至少存在一個(gè)端口含有的葉子節(jié)點(diǎn)地址分布在其它交換機(jī)的不同端口上.
證明:根據(jù)中間交換機(jī)的定義,它的上行端口的AFT必然含有一個(gè)祖宗交換機(jī)的地址,另外,它必然有一個(gè)下行端口存在孩子交換機(jī),根據(jù)定理1,此下行端口要么含有其孩子交換機(jī)的地址,要么含有孩子節(jié)點(diǎn)至少兩個(gè)下行端口所連接的下行鏈路中節(jié)點(diǎn)的地址.當(dāng)此下行端口含有孩子交換機(jī)的地址或者含有孩子節(jié)點(diǎn)至少兩個(gè)下行端口所連接的下行鏈路中節(jié)點(diǎn)的地址存在一個(gè)子孫交換機(jī)地址時(shí),這時(shí),這個(gè)中間交換機(jī)至少有兩個(gè)端口的AFT含有其它交換機(jī)的地址;當(dāng)此下行端口含有孩子節(jié)點(diǎn)至少兩個(gè)下行端口所連接的下行鏈路中節(jié)點(diǎn)的地址都為葉子節(jié)點(diǎn)地址時(shí),這時(shí),由于葉子節(jié)點(diǎn)地址來自兩個(gè)以上不同的下行鏈路,此下行端口含有的葉子節(jié)點(diǎn)地址必然分布在其它交換機(jī)的不同端口上,即一個(gè)端口(上行端口)的AFT含有其它交換機(jī)的地址并且至少存在一個(gè)端口(下行端口)含有的葉子節(jié)點(diǎn)地址分布在其它交換機(jī)的不同端口上.
定理得證.
定理4 如果葉交換機(jī)父親的葉端口AFT含有交換機(jī)的地址,那么它只含下級(jí)葉交換機(jī)的地址而不含任何其它交換機(jī)地址.
證明:根據(jù)葉端口的定義,葉端口只連接的交換機(jī)為處于樹型結(jié)構(gòu)中的最下層的葉交換機(jī),不連接任何中間交換機(jī),因此葉端口AFT中的地址只可能含有其直接連接的葉交換機(jī)地址或葉交換機(jī)所連接的終端地址,而不可能含有其它交換機(jī)的地址.
定理得證.
3.2 樹型剪裁算法
有以上的定義和定理作基礎(chǔ),這樣,對(duì)于滿足下行約束的AFT,我們提出的樹型剪裁算法基本思想如下:
(1)設(shè)置交換機(jī)(含交換機(jī)地址和端口AFT)集合H.
(2)確定葉交換機(jī)Sk:找出Si中只有一個(gè)Aij含有其它交換機(jī)的地址的Si為葉交換機(jī)(根據(jù)是否在H中確定)的備選(定理2),再根據(jù)定理3剔除備選葉交換機(jī)中存在的中間交換機(jī),把所有的葉交換機(jī)從H剪除,如果葉交換機(jī)某個(gè)下行端口出現(xiàn)多個(gè)葉子地址,表示有HUB等啞設(shè)備連接葉子.
(3)更新H中的AFT:把剩余Aij中地址為剪除掉的葉交換機(jī)下行端口含有的地址全部替換為葉交換機(jī)的地址Sk,并合并重復(fù)項(xiàng),相當(dāng)于把剪除的葉交換機(jī)變成了新的葉子節(jié)點(diǎn),轉(zhuǎn)入步驟(2),直到H只剩根節(jié)點(diǎn).
下面我們論證樹型剪裁算法的正確性.首先我們給定一個(gè)普適的真理,即:如果給定一顆樹,每次砍掉它的最下層分叉(此分叉向下連接的所有節(jié)點(diǎn)均為葉子)及其連接的所有葉子,而砍掉的分叉用新的葉子替代,則這棵樹最終會(huì)被砍剩下只剩一個(gè)根節(jié)點(diǎn).我們提出的樹型剪裁算法就基于這樣的一個(gè)真理.步驟(1)相當(dāng)于確定了樹的所有節(jié)點(diǎn)的集合,其中終端節(jié)點(diǎn)即葉子節(jié)點(diǎn)為樹的葉子,葉交換機(jī)為直接連接葉子的最下層分叉,中間交換機(jī)為其它分叉;步驟(2)剔除了所有的葉交換機(jī),相當(dāng)于砍掉了樹的所有最下層分叉,而確定葉交換機(jī)的過程是用證明過的定理2和定理3,確保了確定葉交換機(jī)的正確性;步驟(3)更新了剩余樹的新的節(jié)點(diǎn)結(jié)合,相當(dāng)于把砍掉的最低層分叉變成了新的葉子節(jié)點(diǎn).因此,我們提出的樹型剪裁算法是正確的.
而每次進(jìn)行樹型剪裁的過程,就是確定每一層拓?fù)溥B接關(guān)系的過程,砍掉的葉交換機(jī)的下行端口的AFT中的地址就是和它直接相連的葉子的地址,如果某個(gè)下行端口AFT記錄了多個(gè)地址,說明此端口通過啞設(shè)備連接了多個(gè)葉子節(jié)點(diǎn).
為了更加形象的說明算法的執(zhí)行過程和說明算法的正確性,我們通過一個(gè)具體的拓?fù)浒l(fā)現(xiàn)例子來說明樹型剪裁算法是如何發(fā)現(xiàn)具體的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的.如圖2的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),直接連接主機(jī)h8和h9的是一個(gè)集線器,圖2右側(cè)給出了網(wǎng)絡(luò)中所有交換機(jī)的AFT,比如根節(jié)點(diǎn)S1的端口1的AFT在完整時(shí)應(yīng)該是A11={S2,S4,S5,S6,h1,h2,h3,h4,h5},而圖2中S1的端口1的AFT只含有主機(jī)1,我們進(jìn)一步可以看到此網(wǎng)絡(luò)節(jié)點(diǎn)的AFT完整性很差,基于完整AFT的方法[8～10]和基于下行端口完整的方法[11,12]根據(jù)這樣的AFT是無法發(fā)現(xiàn)此網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的,其它基于AFT的方法[14～22]算法復(fù)雜度高,而且無法完整發(fā)現(xiàn)此網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).
下面基于我們的樹型剪裁算法來發(fā)現(xiàn)此網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),在根交換機(jī)確定為S1后(通常將路由器下連子網(wǎng)中直接和路由器端口相連的交換機(jī)定為根交換機(jī)),將交換機(jī)的AFT和交換機(jī)入集合H,然后確定葉交換機(jī),由于S1已經(jīng)被確定為根交換機(jī),我們首先從剩余的交換機(jī)中根據(jù)定理2選出備選的葉交換機(jī)集合,從圖2中我們看到剩余交換機(jī)除了S2的兩個(gè)端口(端口1和2)含有交換機(jī)的地址外,其它交換機(jī)都只有一個(gè)端口含有交換機(jī)的地址,因此,第一次算法求得的備用葉交換機(jī)為{S3,S4,S5,S6},再由定理3,對(duì)端口AFT含有多個(gè)葉子節(jié)點(diǎn)的項(xiàng)目作分析,只有S3的A16和S5的A53,但A16中的主機(jī)8和9并沒有分布在其他交換機(jī)的不同端口上,而A53的主機(jī)4和5分布在兩個(gè)端口A62和A63的AFT中,因此,S5被剔除掉,即算法求得的第一層葉交換機(jī)為{S3,S4,S6},而S5的端口3則被認(rèn)為是通過啞設(shè)備(集線器)連接葉子節(jié)點(diǎn)8和9.剪裁掉第一層葉交換機(jī)及其相連的葉子節(jié)點(diǎn),并將葉交換機(jī)變?yōu)樾碌娜~子,AFT更新后如圖3所示.
經(jīng)過第一次剪裁后,剩余交換機(jī)為:{S1,S2,S5},其它葉交換機(jī)變化了新的葉子節(jié)點(diǎn),圖3中用圓形節(jié)點(diǎn)表示葉子節(jié)點(diǎn),端口的AFT也進(jìn)行了相應(yīng)的更新,S1為根,剩余交換機(jī)S2和S5僅用定理2就可以確定S5為葉交換機(jī),繼續(xù)將S5及其下連的葉子節(jié)點(diǎn)h3和S6剪除,將S5更新為新的葉子節(jié)點(diǎn),如圖4(a)所示,繼續(xù)進(jìn)行剪裁直到剩余一個(gè)根節(jié)點(diǎn)S1為止,如圖4(a)～(c)所示.其中圖4中省略了相應(yīng)的AFT的變化.
從剪裁的過程我們可以看到,在通過樹型剪裁算法進(jìn)行拓?fù)浒l(fā)現(xiàn)時(shí),每次的剪裁過程記錄了葉交換機(jī)和葉子節(jié)點(diǎn)的直接連接關(guān)系,將每次剪裁掉的節(jié)點(diǎn)一層層組合在一起就可以形成完整的拓?fù)浣Y(jié)構(gòu).顯然,下行約束是相對(duì)于要求下行端口AFT完整的更寬松的約束,它也可以應(yīng)用在從連接根交換機(jī)的管理終端獲取所有子網(wǎng)交換機(jī)AFT的場(chǎng)景[8～16],這也是獲取AFT的必經(jīng)場(chǎng)景,它不要求每個(gè)下行端口完整,只要求通過下行端口AFT能確定唯一的拓?fù)浣Y(jié)構(gòu)即可,根據(jù)下行約束的定義可以看到,下行約束是僅通過下行端口AFT得出唯一正確拓?fù)涞淖钏杉s束,不符合下行約束的網(wǎng)絡(luò)的下行端口AFT,僅僅通過下行端口的AFT是得不出唯一正確的拓?fù)浣Y(jié)構(gòu)的.即符合下行約束的AFT僅由下行AFT就可以確定唯一的拓?fù)浣Y(jié)構(gòu),通過樹型剪裁算法可以得出相應(yīng)唯一正確的拓?fù)浣Y(jié)構(gòu).
我們提出的樹型剪裁算法是嚴(yán)格按照定理1～定理4執(zhí)行的,而定理1～定理4是根據(jù)下行約束AFT的定義嚴(yán)格證明得出的符合下行約束AFT網(wǎng)絡(luò)的特性,因此,符合下行約束AFT定義的網(wǎng)絡(luò)一定可以通過樹型剪裁算法推斷出唯一正確的拓?fù)浣Y(jié)構(gòu).而且算法也非常簡(jiǎn)單,算法復(fù)雜度低,為O(n2),其中n為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù).另外,我們提出的樹型剪裁算法只用到交換機(jī)的AFT,而不需要取得主機(jī)的AFT,現(xiàn)實(shí)網(wǎng)絡(luò)中的大部分主機(jī)不一定配置SNMP協(xié)議,因此,樹型剪裁算法對(duì)實(shí)際網(wǎng)絡(luò)的拓?fù)浒l(fā)現(xiàn)非常適用.
4 實(shí)驗(yàn)仿真
我們的實(shí)驗(yàn)仿真使用BRITE[20]和NS2,其中BRITE用于生成符合冪率分布的網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)溥B接關(guān)系,我們通過修改BRITE的拓?fù)渖纱a,可以將BRITE生成的拓?fù)溥B接關(guān)系直接導(dǎo)入到NS2中生成相應(yīng)的拓?fù)浣Y(jié)構(gòu),如圖5是一個(gè)BRITE生成的符合冪率分布的60個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的連接關(guān)系,經(jīng)過導(dǎo)入到NS2后生成的網(wǎng)絡(luò)拓?fù)鋱D.
由于我們?cè)谑褂肂RTIE生成拓?fù)溧徑雨P(guān)系時(shí),采用BA模型,即節(jié)點(diǎn)和拓?fù)溥B接是增量增長(zhǎng)和優(yōu)先連接,因此生成拓?fù)鋱D以第一個(gè)節(jié)點(diǎn)即節(jié)點(diǎn)0為根節(jié)點(diǎn),網(wǎng)絡(luò)流量產(chǎn)生方式是由從根節(jié)點(diǎn)0每隔1秒逐個(gè)向其它節(jié)點(diǎn)發(fā)送FTP報(bào)文,如第一秒向第一個(gè)節(jié)點(diǎn)發(fā)送,第二秒向第二個(gè)節(jié)點(diǎn),等等;另外,由于FTP報(bào)文在傳輸層使用的是TCP協(xié)議,會(huì)有相應(yīng)的回執(zhí)報(bào)文,因此,可以根據(jù)網(wǎng)絡(luò)中的流量信息采用反向地址學(xué)習(xí)機(jī)制構(gòu)造出各交換機(jī)的地址轉(zhuǎn)發(fā)表,可以通過AFT的老化機(jī)制和人為去除的方式使得AFT不完整且下行端口AFT符合下行約束,手工去除AFT表項(xiàng)時(shí),只要節(jié)點(diǎn)端口的AFT按滿足定理1的條件去除,就可以保證節(jié)點(diǎn)的AFT滿足下行最小約束.
由于樹型剪裁算法只用到交換機(jī)的AFT,而不需要取得主機(jī)的AFT,因此,BRITE生成的拓?fù)鋱D中的節(jié)點(diǎn)我們可以人工將其分為三種類型,第一種是交換機(jī),第二種是終端,第三種是啞設(shè)備.具體劃分方法是:將度數(shù)為1的節(jié)點(diǎn)即所有的葉子節(jié)點(diǎn)作為終端設(shè)備,如圖5中的節(jié)點(diǎn)50;將小部分度數(shù)大于2的下層節(jié)點(diǎn)作為啞設(shè)備,如圖5中的節(jié)點(diǎn)2和節(jié)點(diǎn)9;其余節(jié)點(diǎn)都作為交換機(jī),如圖5中的節(jié)點(diǎn)3和1.注意度數(shù)為2的節(jié)點(diǎn)不能劃分為啞設(shè)備,因?yàn)檫@樣的啞設(shè)備在基于AFT的拓?fù)浒l(fā)現(xiàn)方法中是不可能被發(fā)現(xiàn)的,如圖5中的節(jié)點(diǎn)6和18.
仿真數(shù)據(jù)在一臺(tái)Pentium IV 2.4GHz、內(nèi)存為2G,操作系統(tǒng)為WIN7的計(jì)算機(jī)進(jìn)行處理,對(duì)我們實(shí)驗(yàn)的所有由BRITE生成的拓?fù)浣Y(jié)構(gòu),只要在構(gòu)造AFT時(shí),只要下行端口的AFT符合下行約束,算法就可以準(zhǔn)確地發(fā)現(xiàn)正確的拓?fù)浣Y(jié)構(gòu),進(jìn)一步驗(yàn)證了文中的樹型剪裁算法的拓?fù)浒l(fā)現(xiàn)結(jié)論,即:符合下行約束AFT定義的網(wǎng)絡(luò)一定可以通過樹型剪裁算法推斷出唯一正確的拓?fù)浣Y(jié)構(gòu).
雖然拓?fù)浒l(fā)現(xiàn)算法的正確性是衡量拓?fù)浒l(fā)現(xiàn)算法的最重要指標(biāo),時(shí)間性能對(duì)于拓?fù)浒l(fā)現(xiàn)算法也是很重要的,圖6是生成的不同節(jié)點(diǎn)數(shù)的網(wǎng)絡(luò)對(duì)應(yīng)的樹型剪裁算法的運(yùn)行時(shí)間,圖中以雙縱坐標(biāo)的方式顯示,橫坐標(biāo)表示BRITE生成的拓?fù)浣Y(jié)構(gòu)中的節(jié)點(diǎn)數(shù),包含交換機(jī)、終端及啞設(shè)備,縱坐標(biāo)1表示算法對(duì)于不同節(jié)點(diǎn)數(shù)網(wǎng)絡(luò)的拓?fù)浒l(fā)現(xiàn)時(shí)間,圖例中用‘□’標(biāo)記,縱坐標(biāo)2表示相應(yīng)的節(jié)點(diǎn)數(shù)網(wǎng)絡(luò)中含有地交換機(jī)的個(gè)數(shù),圖例中用‘×’標(biāo)記.從圖6中我們發(fā)現(xiàn),節(jié)點(diǎn)端口的AFT生成后,算法執(zhí)行拓?fù)浒l(fā)現(xiàn)的時(shí)間是很快的,因此,實(shí)際網(wǎng)絡(luò)中的拓?fù)浒l(fā)現(xiàn)的時(shí)延主要來源于采集所有交換機(jī)的AFT的時(shí)間.
另外,從圖6中還可以看到,基本趨勢(shì)是隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的增加,拓?fù)浒l(fā)現(xiàn)算法的運(yùn)行時(shí)間是逐步遞增的,如500個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)時(shí)間和600個(gè)差不多,而800個(gè)節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)時(shí)間比700個(gè)節(jié)點(diǎn)的還要少,原因是500個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中含有的交換機(jī)數(shù)量和600個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)中的交換機(jī)數(shù)量差不多,而800個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中含有的交換機(jī)數(shù)量比700個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)中的交換機(jī)數(shù)量還要少,進(jìn)一步說明了我們提出的樹型剪裁算法僅依賴于交換機(jī)的AFT,而不需要主機(jī)的AFT,算法運(yùn)行時(shí)間取決于網(wǎng)絡(luò)中交換機(jī)的數(shù)量及其AFT的具體情況,仔細(xì)觀察圖6可以發(fā)現(xiàn),網(wǎng)絡(luò)中交換機(jī)的數(shù)量和算法運(yùn)行時(shí)間的趨勢(shì)是基本一致的.
由于目前拓?fù)浒l(fā)現(xiàn)僅基于下行端口的方法只有文[11,12]的工作,而且文[11,12]的方法要求下行端口的AFT完整,在下行端口AFT不完整時(shí),無法發(fā)現(xiàn)正確的網(wǎng)絡(luò)拓?fù)?因此,與我們提出的樹型剪裁算法不具有可比性.
大部分的基于AFT的拓?fù)浒l(fā)現(xiàn)算法需要用到終端設(shè)備的AFT,這樣需要網(wǎng)絡(luò)中的主機(jī)都要配置SNMP,但現(xiàn)實(shí)網(wǎng)絡(luò)中用戶為了保護(hù)隱私,大部分主機(jī)默認(rèn)是不配置SNMP的,這樣還需要通過ARP取得主機(jī)的可達(dá)地址,而我們提出的樹型剪裁算法只需要獲取交換機(jī)的AFT,這對(duì)實(shí)際網(wǎng)絡(luò)的拓?fù)浒l(fā)現(xiàn)非常有用,在實(shí)際網(wǎng)絡(luò)中獲取AFT時(shí),可能會(huì)獲取到部分支持SNMP的主機(jī)的AFT,因此,算法部署到實(shí)際網(wǎng)絡(luò)環(huán)境時(shí),需要根據(jù)sysServices MIB判斷設(shè)備類型(這也是所有拓?fù)浒l(fā)現(xiàn)必須做的工作),并去除所有非交換機(jī)的AFT后,再運(yùn)行樹型剪裁算法.
5 部署應(yīng)用
為了進(jìn)一步驗(yàn)證算法在實(shí)際網(wǎng)絡(luò)系統(tǒng)中的可行性和適用性,我們將算法部署應(yīng)用到我們開發(fā)的網(wǎng)絡(luò)資源主動(dòng)管理系統(tǒng)中,
實(shí)際部署時(shí)我們發(fā)現(xiàn),實(shí)際網(wǎng)絡(luò)AFT缺失量并不是很大,可能和我們的實(shí)際網(wǎng)絡(luò)環(huán)境規(guī)模相對(duì)較小有關(guān),不需要進(jìn)行整個(gè)子網(wǎng)的PING操作,子網(wǎng)的AFT完全滿足最小下行約束,但AFT表中有部分不可達(dá)的設(shè)備,這可能由部分設(shè)備配置改變和部分設(shè)備遷移或宕機(jī)引起,因此,仍然需要對(duì)AFT中的IP地址進(jìn)行PING操作,排除那些不可達(dá)的表項(xiàng),但相對(duì)于PING整個(gè)網(wǎng)段,大大減少了PING操作,縮短了拓?fù)浒l(fā)現(xiàn)的實(shí)際時(shí)間,由于實(shí)際網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)要下載AFT和進(jìn)行PING操作,拓?fù)浒l(fā)現(xiàn)時(shí)間要比仿真實(shí)驗(yàn)的拓?fù)浒l(fā)現(xiàn)時(shí)間長(zhǎng)很多,圖7是主動(dòng)網(wǎng)絡(luò)管理系統(tǒng)進(jìn)行實(shí)際拓?fù)浒l(fā)現(xiàn)的網(wǎng)絡(luò)拓?fù)鋱D.
6 未來工作
本文基于實(shí)際網(wǎng)絡(luò)AFT不完整的情況,定義了三種約束,本文的作者基于最小下行約束,提出了一種樹型剪裁算法,可以在AFT完整性較差的情況下發(fā)現(xiàn)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).本文的工作重點(diǎn)討論了下行約束算法,顯然研究有效的最小約束算法對(duì)物理拓?fù)浒l(fā)現(xiàn)是最有意義的,因?yàn)樗梢猿浞掷盟蠥FT提供的有效信息,而不是只限于單個(gè)方向的有效信息,因此,后續(xù)工作,我們會(huì)對(duì)上行約束和最小約束算法逐步展開研究,同時(shí)本文也為其他學(xué)者提出了一個(gè)開放的課題,也期望其他學(xué)者提出他們的解決上行約束和最小約束AFT的算法.對(duì)于整個(gè)交換域的拓?fù)浒l(fā)現(xiàn),我們可以在子網(wǎng)拓?fù)浒l(fā)現(xiàn)的基礎(chǔ)上用文[15,16]的方法再進(jìn)行子網(wǎng)間合并,當(dāng)然,在后續(xù)工作中,如何將樹型剪裁算法直接成功應(yīng)用于整個(gè)交換域是我們的重要研究方向.
[1]Siamwalla R,Sharma R,Keshav S.Discovering internet topology[R].Cornell Univ,Ithaca,NY,1999.
[2]Bierman A,Jones K.Internet RFC-114,2000,Physical topology MIB[S].
[3]Dawes N,Schenkel D,Slavitch M.Method of determining the topology of a network of objects[P].USA:6231997,2002-06-07.
[4]Schenkel D,Slavitch M,Dawes N.Method of determining topology of a network of objects which compares the similarity of the traffic sequences/volumes of a pair of devices[P].USA:598462,1999-07-02.
[5]邱林,張建忠,吳功宜.基于端口流量的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法研究[J].計(jì)算機(jī)工程與應(yīng)用,2002,22(4):171-172.
Lin Q,Jianzhong Z,Gongyi W.Physical topology discovery method study based on ports traffic[J].Computer Engineering and Application,2002,22(4):171-172.(in Chinese)
[6]Son MH,et al.Physical topology discovery for metro ethernet networks[J].ETRI Journal,2005,9(4):175-186.
[7]Black R,Donnelly A,Fournet C.Ethernet topology discovery without network assistance[A].Proc of the 12th IEEE Int’l Conf.on Network Protocols[C].Los Alamitos:IEEE,2004.130-159.
[8]Breitbart Y,Garofalakis M,Martin C,Rastogi R,Seshadri S,Silberschatz A.Topology discovery in heterogeneous IP networks[A].Proc of the INFOCOM[C].New York:IEEE,2000.85-94.
[9]Breitbart Y,Garofalakis M,Jai B,Martin C,Rastogi R,Silberschatz A.Topology discovery in heterogeneous IP networks:The NetInventory system[J].IEEE/ACM Trans on Networking,2014,12(3):221-234.
[10]Bejerano Y,Breitbart Y,Garofalakis M,Rastogi R.Physical topology discovery for large multi-subnet networks[A].Proc of the IEEE INFOCOM[C].New York:IEEE Press,2003.162-172.
[11]鄭海,張國(guó)清.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究[J].計(jì)算機(jī)研究與發(fā)展,2002,39(3):264-268.
Zheng H,Zhang GQ.An algorithm for physical network topology discovery[J].Journal of Computer Research and Development,2002,39(3):264-268.(in Chinese)
[12]陳福,楊家海,楊揚(yáng) 網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)新算法及其實(shí)現(xiàn)[J].電子學(xué)報(bào),2008,36(8):1620-1625.
Fu C,Jiahai Y,Yang Y.New algorithms on IP network topology discovery and Its implement[J].Acta Electronica Sinica,2008,36(8):1620-1625.(in Chinese)
[13]Lowekamp B,O’Hallaron DR,Gross TR.Topology discovery for largeethernet networks[A].Proc of the ACM SIGCOMM[C].New York:ACM,2001.57-68.
[14]孫延濤,吳志美,石志強(qiáng).基于地址轉(zhuǎn)發(fā)表的交換式以太網(wǎng)拓?fù)浒l(fā)現(xiàn)方法[J].軟件學(xué)報(bào),2006,17(12):2565-2576.
Yantao S,Zimei W,Ziqiang S.Amethod of topology discovery for switched ethernet based on address forwarding tables[J].Journal of Software,2006,17(12):2565-2576.(in Chinese)
[15]Bejerano Y.Taking the skeletons out of the closets:A simple and efficient topology discovery scheme for large multisubnet networks[A].Proc Of IEEE INFOCOM[C].IEEE Press,2006.1-13.
[16]Bejerano Y.Taking the skeletons out of the closets:A simple and efficient topology discovery scheme for large ethernet lans[J].IEEE/ACM Trans on Networking,2009,17(2):1205-1218.
[17]Breitbart Y,Gobjuka H.Characterization of layer-2 unique topologies[J].Information Processing Letters,2008,105(2):52-57.
[18]Gobjuka H,Breitbart Y.Characterization of layer-2 unique topologies in multisubnet local networks[A].Proc of IEEE LCN[C].IEEE Press,2006.522-524.
[19]Gobjuka H,Breitbart Y.Ethernet topology discovery for networks with incomplete information[A].Proc of IEEE ICCCN[C].IEEE Press,2007.613-620.
[20]Gobjuka H,Breitbart Y.Finding ethernet-type network topology is not easy[R].TR-KSU-CS-207-03,Kent State University,2007.
[21]Gobjuka H,Breitbart Y.Discovering network topology of large multisubnet ethernet networks[A].Proc IEEE LCN[C].IEEE Press,2007.230-237.
[22]Gobjuka H,Breitbart Y.Ethernet topology discovery for networks with incomplete information[J].IEEE/ACM Trans on Networking,2010,18(4):1220-1233.
張 賓 男,1976年生于河南新鄉(xiāng).總參第六十三所博士后.研究方向?yàn)榫W(wǎng)絡(luò)管理與測(cè)量、網(wǎng)絡(luò)異常檢測(cè).
E-mail:zhang-bin163@163.com
刁興春 男,1964年生于江蘇泰興.碩士研究生,研究方向?yàn)榫W(wǎng)絡(luò)管理與數(shù)據(jù)質(zhì)量.
A Physical Topology Discovery Method Based on AFT of Downstream Constraint
ZHANG Bin,DIAO Xing-chun,LIU Yi,YU Yun,YUAN Zhen,DING Chen-lu,JIANG Guo-quan
(The63rdResearchInstitute,Nanjing,Jiangshu210007,China)
Network physical topology discovery is very important for network management and application,the physical topology discovery based on AFT is a hot topic on current study.However,the incomplete AFT of network nodes in real network leads to the hardness of physical topology discovery.Based on decreasing the demand for the completeness of AFT in topology discovery,this paper defines three constraints of AFT,and proposes a tree-chopping algorithm based on AFT satisfying downstream constraint to discover the physical topology of a subnet.The proposed algorithm decreases the constraints for the completeness of AFT greatly,and demands the loosest constraint in physical topology discovery relying solely on downstream ports.The correctness and efficiency of the proposed algorithm is verified by the simulation experiment,and the algorithm applicability to real network is verified by deploying the algorithm in a real network management system.
physical topology discovery;address forwarding table;network management;
2014-10-10;
2015-03-11;責(zé)任編輯:藍(lán)紅杰
江蘇省博士后科研資助項(xiàng)目(No.1402138C);國(guó)家自然科學(xué)基金(No.61371196,No.1462009);中國(guó)博士后科學(xué)基金(No.2015M582832)
TP393
A
0372-2112 (2016)08-1864-09
