大型異構(gòu)多子以太網(wǎng)物理拓?fù)浒l(fā)現(xiàn)算法研究*

馬曉波，楊國林

（內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院，呼和浩特010080）

大型異構(gòu)多子以太網(wǎng)物理拓?fù)浒l(fā)現(xiàn)算法研究*

馬曉波，楊國林

（內(nèi)蒙古工業(yè)大學(xué)信息工程學(xué)院，呼和浩特010080）

正確的網(wǎng)絡(luò)物理拓?fù)湫畔υS多網(wǎng)絡(luò)管理任務(wù)起著至關(guān)重要的作用，而實際網(wǎng)絡(luò)中可能存在不易被發(fā)現(xiàn)的“啞”設(shè)備，這給網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)帶來了很大難度，傳統(tǒng)的拓?fù)浒l(fā)現(xiàn)算法不能全面發(fā)現(xiàn)網(wǎng)絡(luò)設(shè)備。針對這種情況，提出一個大型的異構(gòu)多子以太網(wǎng)物理拓?fù)浒l(fā)現(xiàn)算法。算法首先利用通用的MIB信息，得到任意兩個節(jié)點間的直接連接，然后選擇具有最小可能連接數(shù)的節(jié)點，使用擴(kuò)展規(guī)則使所有的RSs完整。實驗結(jié)果表明，不需要修改任何硬件或軟件資源，能夠發(fā)現(xiàn)“啞”設(shè)備，保證拓?fù)浒l(fā)現(xiàn)與給定輸入庫兼容。該算法在地址轉(zhuǎn)發(fā)表不完整的情況下，能夠高效、全面、正確地發(fā)現(xiàn)網(wǎng)絡(luò)的物理拓?fù)浣Y(jié)構(gòu)。

異構(gòu)多子網(wǎng)；物理拓?fù)浒l(fā)現(xiàn)；啞設(shè)備；地址轉(zhuǎn)發(fā)表

1 引 言

很多網(wǎng)絡(luò)管理任務(wù)（如性能分析、故障識別等）取決于網(wǎng)絡(luò)連接知識。然而，目前網(wǎng)絡(luò)工具不能讓網(wǎng)絡(luò)管理員得到精確的網(wǎng)絡(luò)設(shè)備連接圖，沒有高性能的工具來定位網(wǎng)絡(luò)故障、調(diào)整網(wǎng)絡(luò)性能或識別網(wǎng)絡(luò)流量的瓶頸，獲取數(shù)據(jù)鏈路層（ISO體系的第二層）的網(wǎng)絡(luò)拓?fù)湫畔⑹掷щy，市場上的商業(yè)網(wǎng)絡(luò)管理平臺不能自動地發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。目前市場上的商業(yè)工具（例如：HP’s OpenView（opeview.hp.com），IBM’s Tivoli（tivoli.com），Cisco’s Discovery Protocol（www.cisco.com），and Nortel’s DiscoveryProtocol（www.nortelnetworks.com））大多數(shù)基于私有信息，而且在大型的多子以太網(wǎng)中往往無法全面捕捉第二層的連接關(guān)系，如果網(wǎng)絡(luò)中有啞設(shè)備（hubs或semihubs），拓?fù)浒l(fā)現(xiàn)會變得更加復(fù)雜。許多物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法使用本地節(jié)點的網(wǎng)橋和IP MIB信息。然而，網(wǎng)橋和交換機只參與有限的信息交換，在生成樹協(xié)議期間，它們只與它們的鄰居節(jié)點通信，相關(guān)的MIB信息被存儲在地址轉(zhuǎn)發(fā)表（Address Forwarding Table，AFT）中。

在研究了含啞設(shè)備（hubs或semihubs）的大型異構(gòu)多子以太網(wǎng)物理拓?fù)浒l(fā)現(xiàn)存在的問題后，提出了一個新的實用的物理拓?fù)浒l(fā)現(xiàn)算法，該算法只利用通用的MIB信息，不需要修改任何硬件或軟件資源，能夠全面發(fā)現(xiàn)網(wǎng)絡(luò)設(shè)備的連接情況，時間復(fù)雜度為O（n3），較以前算法有很大改進(jìn)。

2 相關(guān)工作

文獻(xiàn)［1］提出了不含啞設(shè)備的多子網(wǎng)物理拓?fù)浒l(fā)現(xiàn)算法，但要求地址轉(zhuǎn)發(fā)表完整，而且多數(shù)情況下得到的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不唯一。文獻(xiàn)［2］中提出的多子網(wǎng)物理拓?fù)浒l(fā)現(xiàn)算法能夠發(fā)現(xiàn)“啞”設(shè)備，然而，在地址轉(zhuǎn)發(fā)表不精準(zhǔn)的情況下，不能發(fā)現(xiàn)正確的網(wǎng)絡(luò)拓?fù)?。文獻(xiàn)［3］中Lowekamp等人提出的算法可以在地址轉(zhuǎn)發(fā)表不完整的情況下發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)?，也能發(fā)現(xiàn)hubs，但是該算法適用于單子網(wǎng)，在多子網(wǎng)情況下非常容易出錯。為了在地址轉(zhuǎn)發(fā)表不完整的情況下發(fā)現(xiàn)多子網(wǎng)的物理拓?fù)?，文獻(xiàn)［4］中提出了一個“兩階段”方法：第一階段，他們試圖利用地址轉(zhuǎn)發(fā)表的擴(kuò)展規(guī)則使不完整的地址轉(zhuǎn)發(fā)表完整，如果能夠使地址轉(zhuǎn)發(fā)表完整，則進(jìn)入第二階段，即使用文獻(xiàn)［1］中提出的算法來發(fā)現(xiàn)網(wǎng)絡(luò)設(shè)備的連接情況，然而，要使不完整的地址轉(zhuǎn)發(fā)表完整非常困難，甚至有時實現(xiàn)不了。文獻(xiàn)［5］中給出了一種基于生成樹協(xié)議的物理拓?fù)浒l(fā)現(xiàn)算法，然而，不像網(wǎng)橋信息，大多數(shù)的網(wǎng)絡(luò)供應(yīng)商不會定期提供生成樹的根信息。

3 網(wǎng)絡(luò)模型

進(jìn)行拓?fù)浒l(fā)現(xiàn)的網(wǎng)絡(luò)區(qū)域稱為交換域，交換域中的節(jié)點使用生成樹協(xié)議確定節(jié)點之間唯一的轉(zhuǎn)發(fā)路徑?？梢詫⒕W(wǎng)絡(luò)中的節(jié)點分成三類：①在拓?fù)浒l(fā)現(xiàn)過程中訪問過該節(jié)點的MIB；②在拓?fù)浒l(fā)現(xiàn)過程中沒有訪問過該節(jié)點的MIB，但該節(jié)點出現(xiàn)在了第一類節(jié)點的MIB中；③在拓?fù)浒l(fā)現(xiàn)過程中沒有訪問過該節(jié)點的MIB，且該節(jié)點也沒出現(xiàn)在其它節(jié)點的MIB中。第二類和第三類節(jié)點稱為啞設(shè)備（hubs或semihubs），當(dāng)semihubs或hubs直接相連時，拓?fù)浒l(fā)現(xiàn)很難發(fā)現(xiàn)它們以及它們之間的連接情況。

網(wǎng)絡(luò)模型用無向樹N＝＜V，E＞來表示，其中V是網(wǎng)絡(luò)節(jié)點集合，E是節(jié)點之間的物理連接集合。對于網(wǎng)絡(luò)N中的節(jié)點a來說，如果它不是hub，則用p（a）表示節(jié)點a的端口數(shù)，用ai表示節(jié)點a的第i個端口，用subnet（a）表示節(jié)點a所屬的子網(wǎng)。如果節(jié)點a是終端節(jié)點當(dāng)且僅當(dāng)p（a）＝1。中間節(jié)點（即非葉子節(jié)點）代表第二層網(wǎng)絡(luò)元素（交換機和網(wǎng)橋）。同一交換區(qū)域中的數(shù)據(jù)包從一個節(jié)點轉(zhuǎn)發(fā)到另一個節(jié)點不需要經(jīng)過路由器，然而，對于不同子網(wǎng)的網(wǎng)絡(luò)設(shè)備之間要想通信必須經(jīng)過各自子網(wǎng)的路由器。因此，把路由器看作主機，路由器和主機表示為終端節(jié)點（即葉子節(jié)點）。

如果節(jié)點a和b通過端口ai和bj相連，當(dāng)且僅當(dāng)在節(jié)點a和b間有從端口ai到端口bj的路徑存在。路徑上邊的數(shù)目稱為路徑長度，如果路徑長度為1，那么端口ai和bj直接相連。

端口ai的地址轉(zhuǎn)發(fā)表記為AFT（ai），滿足下列性質(zhì)：①如果subnet（bj）＝subnet（ai）且從ai到bj有路徑存在，則bj∈AFT（ai）；②如果subnet（bj）≠subnet（ai），但是有端口ck滿足subnet（ck）＝subnet（ai）并且有路徑ck…bj…ai存在，則bj∈AFT（ai）。這就意味著，AFT（ai）中包含在端口ai上收到的所有數(shù)據(jù)包的目的地址。當(dāng)節(jié)點a收到數(shù)據(jù)包時，如果AFT（ai）中包含此數(shù)據(jù)包的目的地址，則節(jié)點a會通過端口ai轉(zhuǎn)發(fā)此數(shù)據(jù)包。如果AFT（ai）中包含端口ai上收到的所有數(shù)據(jù)包的目的地址，不包含從ai到達(dá)不了的節(jié)點，則稱AFT（ai）是完整的。除了端口ai外，在節(jié)點a的其它端口上看到的節(jié)點集合稱為AFT（ai）的補集，記為CAFT（ai）。因為網(wǎng)絡(luò)用樹來表示，且任何節(jié)點都不能在它自己的端口上看見它自己，所以a∈CAFT（ai）。

如果端口ai和bj之間有路徑存在，那么CAFT（ai）∩CAFT（bj）＝?。因為如若不然，則至少存在一個節(jié)點c，能通過兩條不同的路徑到達(dá)c：一條來自于端口ak（k≠i）；另一條來自于端口bl（l≠j）。因此，如果CAFT（ai）∩CAFT（bj）≠?，則端口ai和bj之間沒有路徑存在。如果端口ai和bj直接相連，則AFT（ai）∩AFT（bj）＝?。

從端口ai可到達(dá)的節(jié)點集合記為RS（ai）。通過定義可知，a不屬于RS（ai）。如果a是終端節(jié)點（也就是說a只有一個端口），那么RS（a1）包含除a外的所有網(wǎng)絡(luò)節(jié)點。RS（ai）的補集記為CRS（ai），即CRS（ai）＝V－RS（ai）。在單子網(wǎng)中，如果地址轉(zhuǎn)發(fā)表是完整的，則RS（ai）＝AFT（ai）。然而，在多子網(wǎng)中，節(jié)點a的MIB中不包含RS（ai）信息，但包含AFT（ai）信息。用圖1（a）進(jìn)一步說明AFT、CAFT、RS和CRS的概念，圖1中節(jié)點x是semihub，黑圈是hub，有兩個子網(wǎng)：s1＝｛1，2，x｝，s2＝｛3，4｝，表1列出了AFTs、CAFTs、RSs和CRSs的值。

圖1 含semihub和hub的網(wǎng)絡(luò)和PDCG

表1 圖1（a）中各端口的AFT、CAFT、RS和CRS值

為了推出端口ai和bj直接連接，下面介紹可能直接連接（Potential Direct Connection，PDC）的概念：

（1）AFT（ai）∩AFT（bj）＝?

（2）AFT（ai）∪AFT（bj）是一組子網(wǎng)

（3）CAFT（ai）∩CAFT（bj）＝?

（4）如果ai和bj屬于同一子網(wǎng)，那么沒有滿足下面條件的ck存在：ck與ai不在同一子網(wǎng)；AFT（ai）∪AFT（bj）＝AFT（ai）∪AFT（ck）；其中AFT（ai）和AFT（ck）滿足上面三個條件。

由上面可得出直接連接是PDC的子集。端口ai和bj可能連接（Potential Connection，PC）當(dāng)且僅當(dāng)CRS（ai）∩CRS（bj）＝?。PDCG（Potential Direct Connection Graph）是可能直接連接圖，端口作為PDCG的節(jié)點，如果端口ai和bj可能直接連接則在PDCG中它們之間有邊存在。例如，在圖1（a）中，端口b2和2間有一個PDC，PCs為（a2，b1）和（a1，b2），圖1（a）的PDCG如圖1（b）所示。

4 拓?fù)浒l(fā)現(xiàn)算法

4.1 RS的擴(kuò)展過程

規(guī)則1：如果端口ai和bj相連，a≠b，那么RS（ai）＝RS（ai）∪CRS（bj）且RS（bj）＝RS（bj）∪CRS（ai）。

規(guī)則2：如果端口ai和bj相連，a≠b，子網(wǎng)su中有一節(jié)點c，c∈RS（ak）（k≠i），并且對任何端口bl，RS（bl）不包含子網(wǎng)su中的節(jié)點，那么RS（bj）＝RS（bj）∪C（C包含子網(wǎng)su中的所有節(jié)點以及從子網(wǎng)su中能看到的節(jié)點）

證明：用反證法證明。因為網(wǎng)絡(luò)拓?fù)涫且豢脴?，所以網(wǎng)絡(luò)中的任意兩個節(jié)點之間只有一條路徑。假設(shè)子網(wǎng)su中有兩個節(jié)點c和d（c≠d），c∈RS（ak），d∈RS（aq），且在子網(wǎng)su中沒有屬于RS（bl）的節(jié)點（l是節(jié)點b的任意端口）。假設(shè)把節(jié)點c和d分別加到RS（bj）和RS（bk）中，但是，因為端口ai和bj相連，所以節(jié)點d也一定出現(xiàn)在RS（bj）中，矛盾。定理得證。

見圖1（a），因為在PDCG中有邊＜b2，2＞，所以b2和終端節(jié)點2直接連接。因此，節(jié)點a和b間唯一的可能連接變成了連接。應(yīng)用規(guī)則2可得出RS（b1）包含節(jié)點1、3、4、x和a，RS（a2）包含節(jié)點2、4和b（見表1）。

4.2 算法描述

該算法分兩個階段：第一階段，發(fā)現(xiàn)MIB中任意兩個節(jié)點間的直接連接；第二階段，選擇兩個它們之間具有最小可能連接數(shù)的節(jié)點，這個連接數(shù)不可能大于2（證明見下4.3）。選擇了可能連接后，使用擴(kuò)展規(guī)則擴(kuò)展RSs，重復(fù)這個過程直到所有的RSs是完整的。每一階段都需驗證CRS的交集是否為空，該算法的時間復(fù)雜度為O（n3）。算法描述如下所示。

Input：A set of complete AFTs

Output：A set M?PDC ofmatchings

uniqueness＝unique；

Phase＃1

Generate Potential Direct Connection Graph PDCG（N）；

M＝?；CC＝（｛a｝，…，｛c｝）where CC is the set of connected components each of which at this stage is a single node；

Do while（PDCG（N）is not empty）

1.If there is a terminal node aiin PDCG（N）and U（ai，bj）is an edge in PDCG（N），

select U（ai，bj）；

（a）M＝M∪｛（AFT（ai），AFT（bj））｝；

（b）If a∈CCland b∈CCkand k≠l，thenCCl＝CCl∪CCk；delete CCkfrom CC；

（c）remove from PDC（N）Graph all edges，whose endpoints are in CCl；

2.If there are no terminal nodes in PDCG（N），uniqueness＝not unique；

（a）select an arbitrary PDC（ai，bj）；

（b）Goto 1a；

Phase＃2

Generate PCs as follows：

for any two ports aiand bjdo if CRS（ai）∩CRS（bj）＝Ф，then add＜ai，bj＞to PCs；

Do while（set of PCs is not empty）

1.find two nodes a and b such that the number of potential connections between a and b in the set of PC isminimal；

2.if＜ai，bj＞is notunique potential connection，uniqueness＝not unique；

3.M＝M∪｛（RS（ai），RS（bj））｝；（break ties arbitrarily）

4.Delete＜ai，bj＞from further considerations；

5.oldRS（ai）＝RS（ai）；

6.oldRS（bj）＝RS（bj）；

7.Extend RS（ai）and RS（bj）；

8.oldRS（ai）＝RS（ai）；

9.oldRS（bj）＝RS（bj）；

10.Update the set of PCs；

Return M and uniqueness；

4.3 正確性證明

接下來證明利用該算法得到的拓?fù)渑c輸入的AFTs兼容。首先證明至少有兩個節(jié)點a和b，它們之間的可能連接數(shù)不大于2。接下來證明在節(jié)點a和b間有兩條可能連接或沒有可能連接的情況下，如何選擇節(jié)點a和b間的可能連接生成正確的拓?fù)洹?/p>

定理1：如果AFT（ai）∩AFT（bj）≠?，i、j分別是節(jié)點a、b的端口，那么節(jié)點a和b間至多有兩條可能連接。

證明：假設(shè)有一節(jié)點u，u∈AFT（ai）∩AFT（bj），且u屬于子網(wǎng)s，因為沒有AFT會包含同一子網(wǎng)中所有的節(jié)點，所以可設(shè)有一節(jié)點v，v屬于子網(wǎng)s，并且v∈AFT（ak），v∈AFT（bl），i≠k，j≠l?？紤]下面兩種情況：

（1）子網(wǎng)s中的所有節(jié)點至少出現(xiàn)在節(jié)點a或b的三個端口上。假設(shè)圖2（a）中的端口ai和bj間有路徑，并設(shè)子網(wǎng)s中的節(jié)點u、v和w，u∈AFT（ai），v∈AFT（ak），w∈AFT（am）。因為拓?fù)鋱D用樹表示，所以節(jié)點v和w一定屬于AFT（bj）。又因為節(jié)點u屬于子網(wǎng)s，所以它一定出現(xiàn)在節(jié)點a和b的AFTs中。假設(shè)u∈AFT（bl）和u∈AFT（ai），則｛v，w｝∈CAFT（ai）∩CAFT（bL），u∈CAFT（bj）∩CAFT（ap），p≠i，且｛u，v，w｝∈CAFT（ap）∩CAFT（bq），p≠i≠k≠m，j≠l≠q。因此，（ak，bj）是節(jié)點a和b間唯一的可能連接。

（2）子網(wǎng)s中的所有節(jié)點至多出現(xiàn)在節(jié)點u和v的兩個端口上。假設(shè)子網(wǎng)s中的所有節(jié)點出現(xiàn)在節(jié)點a和b的AFTs中，在圖2（b）中，對節(jié)點a的AFT（ai）和AFT（ak）、節(jié)點b的AFT（bj）和AFT（bl）有u∈AFT（ai）∩AFT（bj），v∈AFT（ak）∩AFT（bl）。因此，在節(jié)點a和b間只有兩條可能連接：（ak，bj）和（ai，bl），這是因為u∈CAFT（ak）∩CAFT（bp），p≠l，v∈CAFT（bj）∩CAFT（aq），q≠k。

圖2 為了定理1的證明

定理2：如果RS（ai）∩RS（bj）≠?，i、j分別是節(jié)點a、b的端口，AFT（ap）∩AFT（bq）＝?（p、q分別是節(jié)點a、b的任意端口），那么（ai，bj）是節(jié)點a和b間唯一的可能連接。

為了說明這種情況見圖3（a），節(jié)點u和v屬于子網(wǎng)s1，節(jié)點p和q屬于子網(wǎng)s2。

證明：假設(shè)有一子網(wǎng)s1，u是子網(wǎng)s1的節(jié)點，u∈RS（ai）∩RS（bj），子網(wǎng)s1屬于節(jié)點a和b的某一端口，在擴(kuò)展過程中s1一定被加到RS（ai）和RS（bj）中。因此，有一節(jié)點c，使路徑（cp，ai）和（cq，bj）存在，節(jié)點c或者屬于子網(wǎng)s1或者節(jié)點c至少從兩個端口上能看見子網(wǎng)s1中的節(jié)點，而且，子網(wǎng)s2中的節(jié)點u和v、子網(wǎng)s3中的節(jié)點w和z和子網(wǎng)s2中的節(jié)點能被節(jié)點a和c的AFTs看到，子網(wǎng)s3中的節(jié)點能被節(jié)點b和c的AFTs看到。如果節(jié)點a在節(jié)點c和b間的路徑上，如圖3（b）所示，那么節(jié)點u和v能被節(jié)點a的兩個AFTs看見，因此，這與假設(shè)（節(jié)點a和b的AFTs交集為空）矛盾。如果節(jié)點c在節(jié)點a和b間的路徑上，那么有下列情況存在：

圖3 為了定理2的證明

（1）節(jié)點c通過端口cp和cq（p≠q）分別與節(jié)點a和b相連，如圖3（c）所示；

（2）節(jié)點c通過端口cp與節(jié)點a和b相連，如圖3（d）所示。

首先考慮第一種情況。當(dāng)選擇可能連接（ai，cp）進(jìn)行擴(kuò)展時，應(yīng)用規(guī)則2，子網(wǎng)s1和s2中的所有節(jié)點和從子網(wǎng)s1和s2中能看到的所有節(jié)點被加到RS（ai）中，因此子網(wǎng)s1中的所有節(jié)點和節(jié)點u、v、b被加到RS（ai）中。同樣，當(dāng)選擇連接（cq，bj）進(jìn)行擴(kuò)展時，子網(wǎng)s1中的所有節(jié)點和節(jié)點w、z、a被加到RS（bj）中。因為a∈RS（bj）且b∈RS（ai），所以節(jié)點a和b間存在唯一的可能連接。

使用同樣的方法，第二種情況的正確性也能被證明。

定理3：如果節(jié)點a和b間不存在唯一的可能連接，a≠b，那么沒有這樣的節(jié)點u和v使｛u，v｝∈AFT（ai），u∈AFT（bj），v∈AFT（bk），j≠k。

證明：假設(shè)網(wǎng)絡(luò)中有兩對不同的節(jié)點a、b和u、v，且｛u，v｝∈AFT（ai），u∈AFT（bj），v∈AFT（bk），j≠k，如圖4（a）所示。因為每個節(jié)點要么能看到同一子網(wǎng)中的所有節(jié)點要么一個也看不到，所以有一節(jié)點w，節(jié)點u、v和w屬于同一子網(wǎng)，且w∈AFT（bk）。因此，下面的關(guān)系成立：w∈CAFT（ai）∩CAFT（by），y≠k，u∈CAFT（ax）∩CAFT（bk），x≠i，v∈CAFT（ax）∩CAFT（by），x≠i，y≠k。所以，連接（ai，bk）是唯一的。

定理4：如果網(wǎng)絡(luò)中任兩個節(jié)點間沒有唯一的可能連接，并且節(jié)點a和b間至多有兩條可能連接，那么選擇其中的一條可能連接來生成的網(wǎng)絡(luò)拓?fù)渑c給定的AFTs集合兼容。

證明：假設(shè)端口b1與AFT（b1）中的節(jié)點不直接相連，如圖4（b）所示，下面證明將端口b1與AFT（b1）中的節(jié)點相連可得到有效的網(wǎng)絡(luò)拓?fù)洹?/p>

從定理3可知，或者AFT（bi）∩AFT（cj）＝?（i、j分別是節(jié)點b、c的任意端口），或者AFT（ak）∩AFT（cj）＝?（k、j分別是節(jié)點a、c的任意端口），因此，考慮下面情況：

（1）AFT（bi）∩AFT（cj）＝?（i、j分別是節(jié)點b、c的任意端口），在這種情況下，AFT（b1）?AFT（a1）。設(shè)F＝AFT（a1）∩AFT（b1）。因為在節(jié)點a和b間恰有兩條可能連接（根據(jù)定理1），所以將端口b1與F中的節(jié)點相連可在端口b2和a1間得到一條唯一的連接。通過擴(kuò)展節(jié)點a和b的AFTs，節(jié)點c、11、21和從這些節(jié)點能看到的節(jié)點會被加到AFT（b2）中。最后，如果將端口b2連到端口d1上，那么（a2，d1）是一個有效的可能連接（因為a2和d1間有路徑）。

?圖4 為了定理3和定理4的證明

（2）AFT（ai）∩AFT（cj）＝?（i、j分別是節(jié)點a、c的任意端口），在這種情況下，AFT（a1）?AFT（b1）。設(shè)F＝AFT（a1）∩AFT（b1）。因為在節(jié)點a和b間恰有兩條可能連接，所以將端口b1與F中的節(jié)點相連可在端口b2和a1間得到一條唯一的連接。通過擴(kuò)展節(jié)點a和b的AFTs，將得到如圖4（c）所示的拓?fù)洹?/p>

5 綜合實例

這里介紹兩個實例。第一個實例證明算法利用AFTs可唯一的確定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；第二個實例證明算法利用AFTs雖不能唯一的確定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，但能發(fā)現(xiàn)網(wǎng)絡(luò)的所有拓?fù)浣Y(jié)構(gòu)。

圖5 含hub的網(wǎng)絡(luò)模型

見圖5所示的網(wǎng)絡(luò)：黑圈代表hubs，子網(wǎng)有：s1＝｛s，t｝，s2＝｛x，y｝，s3＝｛u，v｝，s4＝｛r，q｝，節(jié)點a，b，c，d和e的AFTs見表2。

表2 多子網(wǎng)圖5中各端口的AFT值

端口e2、x間和端口e3、u間有一個PDC，所以這些直接連接能被發(fā)現(xiàn)。應(yīng)用算法的第一階段和第二階段可得到下列的PC組：（a1，b2），（a2，b1），（a1，c2），（a2，c1），（a1，d2），（a2，d1），（a1，e1），（a2，e1），（b1，c2），（b2，c1），（b1，d2），（b2，d1），（b1，e1），（c1，d2），（c2，d1），（c1，e1），（d1，e1）。

唯一的可能連接如下：（b1，e1），（c1，e1）和（d1，e1）。接下來擴(kuò)展RS（b1）、RS（c1）、RS（d1）和RS（e1）。利用擴(kuò)展規(guī)則1，節(jié)點e被加到RS（b1）中，節(jié)點b，q，t，v，y被加到RS（e1）中。因為從節(jié)點e的任何端口都看不到子網(wǎng)s4中的節(jié)點q和r，但在節(jié)點b的AFTs能看到節(jié)點q和r，利用擴(kuò)展規(guī)則2，子網(wǎng)s4中的所有節(jié)點和從子網(wǎng)s4中能看到的節(jié)點都被加到RS（e1），因此節(jié)點q，r和a被加到RS（e1）。同理，擴(kuò)展RS（e1）和RS（c1），節(jié)點e被加到RS（c1）中，節(jié)點c、s和t被加到RS（e1）中。最后，擴(kuò)展RS（d1）和RS（e1）。各端口的RSs見表3。

之后得到的唯一可能連接是（b2，d1）和（c2，d1），擴(kuò)展后的結(jié)果如表4所示。

下一步得到的唯一可能連接是（a2，d1），擴(kuò)展后的結(jié)果如表5所示。

在這一階段，每兩個節(jié)點間有一個唯一的PC，所以可獲得完整的RSs并能得到唯一的網(wǎng)絡(luò)拓?fù)洹?/p>

表3 發(fā)現(xiàn)了PC（b1，e1），（c1，e1）和（d1，e1）后得到的RS值

表4 發(fā)現(xiàn)了PC（b2，d1）和（c2，d1）后得到的RS值

表5 發(fā)現(xiàn)了PC（a2，d1）后得到的RS值

6 結(jié)束語

精準(zhǔn)的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)對網(wǎng)絡(luò)各方面的管理起著非常重要的作用。對現(xiàn)有的物理拓?fù)浒l(fā)現(xiàn)算法進(jìn)行分析后，提出了一種異構(gòu)多子以太網(wǎng)物理拓?fù)浒l(fā)現(xiàn)算法，克服了網(wǎng)絡(luò)協(xié)議不一致，網(wǎng)絡(luò)設(shè)備異構(gòu)等帶來的困難，在不完整的地址轉(zhuǎn)發(fā)表情況下能夠全面、準(zhǔn)確、高效地發(fā)現(xiàn)大型網(wǎng)絡(luò)的設(shè)備，該算法具有廣泛的適用性。對于含VLAN的網(wǎng)絡(luò)，只有在極少數(shù)私家Bridge－MIB中提供了相關(guān)信息，因此含VLAN的拓?fù)浒l(fā)現(xiàn)算法將是下一步研究工作的重點。

［1］ Breitbart Y，Garofalakis M，Jai B.Topology Discovery in Heterogeneous IP Networks：The NetInventory System［J］.IEEE/ACM Trans.Networking，2004，12（3）：401－414.

［2］ Y Bejerano，Y Breitbart，M Garofalakis，R Rastogi，Physical Topology Discovery for Large Multi－Subnet Networks［C］.In：Proceedings of INFOCOM 2003：342－352.

［3］ Lowekamp，David R.O’Hallaron，Thomas R Gross.Topology discovery for large ethenet networks［C］.In：Proceeding of ACM SIGCOMM，California，Aug 2001：237－248.

［4］ Y Sun，ZWu，Z Shi.The Physical Topology Discovery for Switched Ethernet Base on Connection Reasoning［C］.In：Proceedings of ISCIT，2005：42－45.

［5］ Y Sun，Z Shi，ZWu，A Discovery Algorithm for Physical Topology in Switched Networks［C］.In：Proceedings of the IEEE Conference on Local Computer Networks，2005： 311－317.

［6］ 馬曉波.異構(gòu)多子網(wǎng)的以太網(wǎng)物理拓?fù)浒l(fā)現(xiàn)算法研究［J］.計算機工程與科學(xué)，2008，30（9）：11－14.

［7］ 馬曉波，楊國林，馬志強，莊旭菲.異構(gòu)IP網(wǎng)絡(luò)物理拓?fù)浒l(fā)現(xiàn)的改進(jìn)算法［J］.微處理機，2011，32（1）：18－20.

［8］ Xiaobo Ma，Guolin Yang，Xufei Zhuang.Research and Implementation on Algorithm of Automatic Physical Topology Discovery in Heterogeneous Multi－subnet［J］.Information Technology Journal，2013，12（20）：5736－5740.

Study on Algorithm of Discovering Physical Network Topology for Large Heterogeneous Multi－Subnet Ethernet Networks

Ma Xiaobo，Yang Guolin
（College of Information Engineering，Inner Mongolia University of Technology，Hohhot010080，China）

The exact network topology information is very important for many network management tasks，and some＂dumb＂devicesmay be not found in the network，so it is very difficult to conduct the network topology discovery because the classical topology discovery algorithm can not fully discover network devices.For this situation，a physical topology discovery algorithm of large heterogeneousmultisubnet ethernet networks is presented in this paper.Firstly，it discovers all direct connections between any two MIB－enabled nodes by the general information of MIB，and then selects two nodes with minimum number of potential connections to use the extension rules for complete RS.The experimental results show that this algorithm does not require any hardware or software modifications and can discover the＂dumb＂devices and guarantee discovering the topology which is compatible with the given input library.In the case of incomplete address forwarding table，it can discover physical layer topology in efficient，complete and accurate ways.

Heterogeneousmulti－subnet；Physical topology discovery；Dumb device；Address forward table

10.3969/j.issn.1002－2279.2015.01.010

TP393

A

1002－2279（2015）01－0029－06

內(nèi)蒙古自然科學(xué)基金項目（2013MS0906）；內(nèi)蒙古自治區(qū)高等學(xué)?？茖W(xué)研究項目（NJZY13102）；國家自然基金（61363052）

馬曉波（1976－），女（蒙古族），內(nèi)蒙古呼和浩特人，副教授，碩士，碩士生導(dǎo)師，主研方向：計算機網(wǎng)絡(luò)，網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)。

2014－09－11