大型異構多子以太網物理拓撲發現算法研究*

馬曉波，楊國林

（內蒙古工業大學信息工程學院，呼和浩特010080）

大型異構多子以太網物理拓撲發現算法研究*

馬曉波，楊國林

（內蒙古工業大學信息工程學院，呼和浩特010080）

正確的網絡物理拓撲信息對許多網絡管理任務起著至關重要的作用，而實際網絡中可能存在不易被發現的“啞”設備，這給網絡拓撲發現帶來了很大難度，傳統的拓撲發現算法不能全面發現網絡設備。針對這種情況，提出一個大型的異構多子以太網物理拓撲發現算法。算法首先利用通用的MIB信息，得到任意兩個節點間的直接連接，然后選擇具有最小可能連接數的節點，使用擴展規則使所有的RSs完整。實驗結果表明，不需要修改任何硬件或軟件資源，能夠發現“啞”設備，保證拓撲發現與給定輸入庫兼容。該算法在地址轉發表不完整的情況下，能夠高效、全面、正確地發現網絡的物理拓撲結構。

異構多子網；物理拓撲發現；啞設備；地址轉發表

1 引 言

很多網絡管理任務（如性能分析、故障識別等）取決于網絡連接知識。然而，目前網絡工具不能讓網絡管理員得到精確的網絡設備連接圖，沒有高性能的工具來定位網絡故障、調整網絡性能或識別網絡流量的瓶頸，獲取數據鏈路層（ISO體系的第二層）的網絡拓撲信息十分困難，市場上的商業網絡管理平臺不能自動地發現網絡拓撲結構。目前市場上的商業工具（例如：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））大多數基于私有信息，而且在大型的多子以太網中往往無法全面捕捉第二層的連接關系，如果網絡中有啞設備（hubs或semihubs），拓撲發現會變得更加復雜。許多物理網絡拓撲發現算法使用本地節點的網橋和IP MIB信息。然而，網橋和交換機只參與有限的信息交換，在生成樹協議期間，它們只與它們的鄰居節點通信，相關的MIB信息被存儲在地址轉發表（Address Forwarding Table，AFT）中。

在研究了含啞設備（hubs或semihubs）的大型異構多子以太網物理拓撲發現存在的問題后，提出了一個新的實用的物理拓撲發現算法，該算法只利用通用的MIB信息，不需要修改任何硬件或軟件資源，能夠全面發現網絡設備的連接情況，時間復雜度為O（n3），較以前算法有很大改進。

2 相關工作

文獻［1］提出了不含啞設備的多子網物理拓撲發現算法，但要求地址轉發表完整，而且多數情況下得到的網絡拓撲結構不唯一。文獻［2］中提出的多子網物理拓撲發現算法能夠發現“啞”設備，然而，在地址轉發表不精準的情況下，不能發現正確的網絡拓撲。文獻［3］中Lowekamp等人提出的算法可以在地址轉發表不完整的情況下發現網絡拓撲，也能發現hubs，但是該算法適用于單子網，在多子網情況下非常容易出錯。為了在地址轉發表不完整的情況下發現多子網的物理拓撲，文獻［4］中提出了一個“兩階段”方法：第一階段，他們試圖利用地址轉發表的擴展規則使不完整的地址轉發表完整，如果能夠使地址轉發表完整，則進入第二階段，即使用文獻［1］中提出的算法來發現網絡設備的連接情況，然而，要使不完整的地址轉發表完整非常困難，甚至有時實現不了。文獻［5］中給出了一種基于生成樹協議的物理拓撲發現算法，然而，不像網橋信息，大多數的網絡供應商不會定期提供生成樹的根信息。

3 網絡模型

進行拓撲發現的網絡區域稱為交換域，交換域中的節點使用生成樹協議確定節點之間唯一的轉發路徑。可以將網絡中的節點分成三類：①在拓撲發現過程中訪問過該節點的MIB；②在拓撲發現過程中沒有訪問過該節點的MIB，但該節點出現在了第一類節點的MIB中；③在拓撲發現過程中沒有訪問過該節點的MIB，且該節點也沒出現在其它節點的MIB中。第二類和第三類節點稱為啞設備（hubs或semihubs），當semihubs或hubs直接相連時，拓撲發現很難發現它們以及它們之間的連接情況。

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

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

端口ai的地址轉發表記為AFT（ai），滿足下列性質：①如果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上收到的所有數據包的目的地址。當節點a收到數據包時，如果AFT（ai）中包含此數據包的目的地址，則節點a會通過端口ai轉發此數據包。如果AFT（ai）中包含端口ai上收到的所有數據包的目的地址，不包含從ai到達不了的節點，則稱AFT（ai）是完整的。除了端口ai外，在節點a的其它端口上看到的節點集合稱為AFT（ai）的補集，記為CAFT（ai）。因為網絡用樹來表示，且任何節點都不能在它自己的端口上看見它自己，所以a∈CAFT（ai）。

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

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

圖1 含semihub和hub的網絡和PDCG

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

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

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

（2）AFT（ai）∪AFT（bj）是一組子網

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

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

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

4 拓撲發現算法

4.1 RS的擴展過程

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

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

證明：用反證法證明。因為網絡拓撲是一棵樹，所以網絡中的任意兩個節點之間只有一條路徑。假設子網su中有兩個節點c和d（c≠d），c∈RS（ak），d∈RS（aq），且在子網su中沒有屬于RS（bl）的節點（l是節點b的任意端口）。假設把節點c和d分別加到RS（bj）和RS（bk）中，但是，因為端口ai和bj相連，所以節點d也一定出現在RS（bj）中，矛盾。定理得證。

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

4.2 算法描述

該算法分兩個階段：第一階段，發現MIB中任意兩個節點間的直接連接；第二階段，選擇兩個它們之間具有最小可能連接數的節點，這個連接數不可能大于2（證明見下4.3）。選擇了可能連接后，使用擴展規則擴展RSs，重復這個過程直到所有的RSs是完整的。每一階段都需驗證CRS的交集是否為空，該算法的時間復雜度為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 正確性證明

接下來證明利用該算法得到的拓撲與輸入的AFTs兼容。首先證明至少有兩個節點a和b，它們之間的可能連接數不大于2。接下來證明在節點a和b間有兩條可能連接或沒有可能連接的情況下，如何選擇節點a和b間的可能連接生成正確的拓撲。

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

證明：假設有一節點u，u∈AFT（ai）∩AFT（bj），且u屬于子網s，因為沒有AFT會包含同一子網中所有的節點，所以可設有一節點v，v屬于子網s，并且v∈AFT（ak），v∈AFT（bl），i≠k，j≠l。考慮下面兩種情況：

（1）子網s中的所有節點至少出現在節點a或b的三個端口上。假設圖2（a）中的端口ai和bj間有路徑，并設子網s中的節點u、v和w，u∈AFT（ai），v∈AFT（ak），w∈AFT（am）。因為拓撲圖用樹表示，所以節點v和w一定屬于AFT（bj）。又因為節點u屬于子網s，所以它一定出現在節點a和b的AFTs中。假設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）是節點a和b間唯一的可能連接。

（2）子網s中的所有節點至多出現在節點u和v的兩個端口上。假設子網s中的所有節點出現在節點a和b的AFTs中，在圖2（b）中，對節點a的AFT（ai）和AFT（ak）、節點b的AFT（bj）和AFT（bl）有u∈AFT（ai）∩AFT（bj），v∈AFT（ak）∩AFT（bl）。因此，在節點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分別是節點a、b的端口，AFT（ap）∩AFT（bq）＝?（p、q分別是節點a、b的任意端口），那么（ai，bj）是節點a和b間唯一的可能連接。

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

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

圖3 為了定理2的證明

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

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

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

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

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

證明：假設網絡中有兩對不同的節點a、b和u、v，且｛u，v｝∈AFT（ai），u∈AFT（bj），v∈AFT（bk），j≠k，如圖4（a）所示。因為每個節點要么能看到同一子網中的所有節點要么一個也看不到，所以有一節點w，節點u、v和w屬于同一子網，且w∈AFT（bk）。因此，下面的關系成立：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：如果網絡中任兩個節點間沒有唯一的可能連接，并且節點a和b間至多有兩條可能連接，那么選擇其中的一條可能連接來生成的網絡拓撲與給定的AFTs集合兼容。

證明：假設端口b1與AFT（b1）中的節點不直接相連，如圖4（b）所示，下面證明將端口b1與AFT（b1）中的節點相連可得到有效的網絡拓撲。

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

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

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

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

5 綜合實例

這里介紹兩個實例。第一個實例證明算法利用AFTs可唯一的確定網絡拓撲結構；第二個實例證明算法利用AFTs雖不能唯一的確定網絡拓撲結構，但能發現網絡的所有拓撲結構。

圖5 含hub的網絡模型

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

表2 多子網圖5中各端口的AFT值

端口e2、x間和端口e3、u間有一個PDC，所以這些直接連接能被發現。應用算法的第一階段和第二階段可得到下列的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）。接下來擴展RS（b1）、RS（c1）、RS（d1）和RS（e1）。利用擴展規則1，節點e被加到RS（b1）中，節點b，q，t，v，y被加到RS（e1）中。因為從節點e的任何端口都看不到子網s4中的節點q和r，但在節點b的AFTs能看到節點q和r，利用擴展規則2，子網s4中的所有節點和從子網s4中能看到的節點都被加到RS（e1），因此節點q，r和a被加到RS（e1）。同理，擴展RS（e1）和RS（c1），節點e被加到RS（c1）中，節點c、s和t被加到RS（e1）中。最后，擴展RS（d1）和RS（e1）。各端口的RSs見表3。

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

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

在這一階段，每兩個節點間有一個唯一的PC，所以可獲得完整的RSs并能得到唯一的網絡拓撲。

表3 發現了PC（b1，e1），（c1，e1）和（d1，e1）后得到的RS值

表4 發現了PC（b2，d1）和（c2，d1）后得到的RS值

表5 發現了PC（a2，d1）后得到的RS值

6 結束語

精準的網絡拓撲發現對網絡各方面的管理起著非常重要的作用。對現有的物理拓撲發現算法進行分析后，提出了一種異構多子以太網物理拓撲發現算法，克服了網絡協議不一致，網絡設備異構等帶來的困難，在不完整的地址轉發表情況下能夠全面、準確、高效地發現大型網絡的設備，該算法具有廣泛的適用性。對于含VLAN的網絡，只有在極少數私家Bridge－MIB中提供了相關信息，因此含VLAN的拓撲發現算法將是下一步研究工作的重點。

［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］ 馬曉波.異構多子網的以太網物理拓撲發現算法研究［J］.計算機工程與科學，2008，30（9）：11－14.

［7］ 馬曉波，楊國林，馬志強，莊旭菲.異構IP網絡物理拓撲發現的改進算法［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

內蒙古自然科學基金項目（2013MS0906）；內蒙古自治區高等學校科學研究項目（NJZY13102）；國家自然基金（61363052）

馬曉波（1976－），女（蒙古族），內蒙古呼和浩特人，副教授，碩士，碩士生導師，主研方向：計算機網絡，網絡拓撲發現。

2014－09－11