圖論在網(wǎng)絡拓撲發(fā)現(xiàn)算法中的應用

1、圖論在網(wǎng)絡拓撲發(fā)現(xiàn)算法中的應用路連兵1+，胡吉明2，姜 巖1，2 1，2(河海大學 計算機及信息工程學院,江蘇 南京 210098)E-mail ：摘要：網(wǎng)絡拓撲發(fā)現(xiàn)技術(shù)已經(jīng)廣泛地應用在各種項目軟件中。然而，隨著網(wǎng)絡結(jié)構(gòu)復雜度升級，這給拓撲發(fā)現(xiàn)帶來了挑戰(zhàn)。所以我們越來越需要一種高效，準確的網(wǎng)絡拓撲算法自動發(fā)現(xiàn)網(wǎng)絡拓撲結(jié)構(gòu)。目前的拓撲算法主要集中在：(1)路由層的發(fā)現(xiàn)。這個層面的發(fā)現(xiàn)算法在技術(shù)上比較簡單，只需要尋找路由與路由之間，或路由端口與子網(wǎng)之間的連接關(guān)系，利用路由器的自身特性，很容易實現(xiàn)。(2)鏈路層的發(fā)現(xiàn)。直到目前為止，已有的廠商工具很難準確發(fā)現(xiàn)網(wǎng)絡拓撲，已發(fā)表的理論文獻知識也只是理論上

2、闡述，實際應用難度比較大。本論文，提出一種基于圖論的骨架樹數(shù)據(jù)存儲結(jié)構(gòu)算法，可以高效推斷網(wǎng)絡的拓撲關(guān)系。關(guān)鍵詞：骨架樹;子網(wǎng);地址轉(zhuǎn)發(fā)表;圖論；信任節(jié)點Topology Discovery in Networks Based on Graph Theory*LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,21,2(School of Computer Science and Information, Hohai University, Nanjing Jiangsu 210098, China)Abstract: Topology discovery system

3、s are starting to be introduced in the form of easily and widely deployed software. However, Today's IP network is complex and dynamic. Keeping track of topology information efficiently is a difficult task. So, we need effective algorithms for automatically discovering physical network topology.

4、 Earlier work has typically focused on: (1) Layer-3 (network layer) topology, which can only router-to-router interconnections and router interface-to-subnet relationships. This work is relatively easy and has lots of systems can do it. (2)Layer-2(link layer), till now, no tools can discovery the ne

5、twork topology exactly because of bad algorithm. In this paper, Skeleton-tree based on Graph theory is proposed to infer the connections between network nodes. Key words:Skeleton-tree; subnets; Address Forwarding Table; Graph Theory；Trust Node1 網(wǎng)絡拓撲的現(xiàn)狀Ethernet Local Area Networks (LANs) 是指在一區(qū)域內(nèi)將不同的網(wǎng)

6、絡設備通過傳輸光纜，電纜連接起來，實現(xiàn)網(wǎng)絡資源共享的網(wǎng)絡。但是由于網(wǎng)絡設備種類眾多，而且同類產(chǎn)品產(chǎn)自不同廠家也會在原理上有所區(qū)別，所以管理員要能夠高效管理維護日益膨脹、復雜的網(wǎng)絡已經(jīng)十分困難。本課題網(wǎng)絡拓撲發(fā)現(xiàn)（Topology Discovery ，簡稱TD）就是從降低網(wǎng)絡維護人員工作的難度、準確高效反應網(wǎng)絡結(jié)構(gòu)的角度而研究的。TD主要功能是盡可能真實反應不同設備之間的物理連接關(guān)系。有效的TD算法不但能夠快速繪制出網(wǎng)絡實體互聯(lián)關(guān)系，而且能夠準確的體現(xiàn)不可管理設備如集線器HUB（但目前有的HUB是可管理的）等。這樣網(wǎng)絡管理員就可以直接在網(wǎng)絡拓撲圖上得到網(wǎng)絡故障，流量瓶頸等重要信息，對所發(fā)生的故

7、障一目了然。如果網(wǎng)絡拓撲上顯示一條鏈路總處于滿負荷傳輸狀態(tài)，那么擴大該條鏈路的容量對提高網(wǎng)絡性能將有很大幫助。1.1網(wǎng)絡拓撲中幾個難點至于難于拓撲第二層網(wǎng)絡這種狀況，其原因是多方面的，下面介紹在網(wǎng)絡拓撲發(fā)現(xiàn)算法設計的過程中，僅僅借助于2層的網(wǎng)絡設備的MIB信息所存在的困難。從國內(nèi)外研究得知，設計出好的網(wǎng)絡拓撲算法，主要是要解決一下幾方面的問題。（i）2層網(wǎng)絡設備的透明性。二層拓撲困難其原因是多方面的，主要是建立這些網(wǎng)絡十分容易。因為交換機可以透明地連接，甚至于插上線纜就可以建立一個局域網(wǎng)。而這種連接的簡便性使得局域網(wǎng)對網(wǎng)絡管理軟件都是透明的。但這并不意味著第二層發(fā)現(xiàn)功能將無所作為。關(guān)鍵基礎設施

8、的廠商們已經(jīng)開發(fā)出了自有的發(fā)現(xiàn)協(xié)議，可將數(shù)據(jù)存儲于SNMP企業(yè)版，例如Cisco公司的CDP 協(xié)議（Cisco Discovery Protocol）、Extreme Networks的EDP協(xié)議（Extreme Discovery Protocol）、Enterasys Networks的CDP協(xié)議（Cabletron Discovery Protocol）以及Nortel Networks的NDP協(xié)議（Nortel Discovery Protocol）等。這里的一個明顯問題是，這些協(xié)議都不能工作在混合廠商設備集成的網(wǎng)絡環(huán)境下。2層網(wǎng)絡設備交換機、網(wǎng)橋、集線器等與終端的主機或上層的路由設備

9、都是直接互聯(lián)，而且設備不記錄相鄰的設備信息，僅有二層交換機上維護著一張表,記錄著接收的數(shù)據(jù)包應該從哪個端口轉(zhuǎn)發(fā)出去,這張表就是AFTs。（ii）2層網(wǎng)絡中設備缺乏統(tǒng)一的標準。2層網(wǎng)絡中存在亞元設備，所謂亞元設備是指有些設備通過SNMP Bridge MIB很難實現(xiàn)獲取AFTs信息，甚至不支持SNMP服務；有些設備比如集線器（HUB）, 不具有類似于交換機的"智能記憶"能力和"學習"能力，它也不具備交換機所具有的MAC(Media Access Control)地址表。所以要準備發(fā)現(xiàn)網(wǎng)絡中這些設備，是網(wǎng)絡拓撲算法設計的一大挑戰(zhàn)。（iii）多子網(wǎng)網(wǎng)絡結(jié)構(gòu)。目

10、前的LANs都支持劃分多子網(wǎng)，在同一子網(wǎng)內(nèi)的設備可以直接通訊，不需要經(jīng)過路由器。而不同子網(wǎng)內(nèi)的設備之間通訊需要經(jīng)過路由器數(shù)據(jù)轉(zhuǎn)發(fā)（即使物理上是連接直接連接）。同一子網(wǎng)內(nèi)的設備構(gòu)成了連接樹。見圖1-1（a）。它表示的典型的網(wǎng)絡結(jié)構(gòu)被分成三個子網(wǎng)結(jié)構(gòu):其中表示主機節(jié)點，表示交換機節(jié)點，表示集線器等共享設備，相應的網(wǎng)絡無向樹模型見圖1-1（b）、圖1-1（c）、圖1-1（d）。圖1-1(a) 網(wǎng)絡模型圖1-1(b) 連接樹圖1-1(c) 連接樹圖1-1(d) 連接樹II 網(wǎng)絡模型目前日益復雜的LAN主要由交換機（也稱網(wǎng)橋），路由器，主機等組成，由于本課題研究的LAN是一個連接實體，在2層網(wǎng)絡中，任意

11、一對網(wǎng)絡節(jié)點之間總會存在僅包含2層網(wǎng)絡設備（交換機，HUB等）的路徑，且僅有一條。路徑中的交換的活動端口(也稱轉(zhuǎn)發(fā)端口)可以通過生成樹協(xié)議判斷。子網(wǎng)生成樹用無向樹表示。其中是網(wǎng)絡節(jié)點集，是任意兩網(wǎng)絡節(jié)點的活動端口的物理連接關(guān)系。把實際物理網(wǎng)絡拓撲結(jié)構(gòu)抽象表達成無向樹，是本課題網(wǎng)絡拓撲發(fā)現(xiàn)的目標。在無向樹中，交換機是無向樹內(nèi)部節(jié)點，路由器和主機用無向樹的葉節(jié)點表示。在2層網(wǎng)絡拓撲中，發(fā)現(xiàn)路由器比較困難，所以用一系列的主機表示一個路由器。由于子網(wǎng)生成樹是無向樹，任意兩節(jié)點之間的數(shù)據(jù)傳輸都遵循生成樹協(xié)議，而路徑選擇由交換機活動端口上的AFT信息決定。換個角度描述，AFT是端口接收的一系列Media

12、Access Control (MAC)地址信息，形成MAC地址表并維護它。下面為了算法的描述方便，給出TD算法和描述中所用到字符的原始定義：1. :表示在圖中任意兩節(jié)點之間的路徑。2. :表示任意節(jié)點的所有活動端口集合。3. :表示節(jié)點的第個端口。4. :表示節(jié)點的第個端口的AFT地址轉(zhuǎn)發(fā)表。5. :表示節(jié)點的活動端口與節(jié)點具有連接關(guān)系且6. :表示子網(wǎng)subnet 的集合。7. :表示任意子網(wǎng)所確定的連接樹。:任意一對網(wǎng)絡節(jié)點,的路徑集合。所以，是中所有網(wǎng)絡節(jié)點與邊的集合。8. :任意一交換機，如果子網(wǎng)包含，則且。所以給定節(jié)點的AFTs信息是指在中所有可達的節(jié)點的集合。9. : 由可以這樣

13、定義：也是節(jié)點在第端口處的AFT信息集合(這個AFT信息集合忽略不屬于子網(wǎng)中節(jié)點的信息，即滿足AFT中的節(jié)點且).10. :節(jié)點的所有活動端口，即如果，則。11. :連接樹的根節(jié)點。12. :一系列節(jié)點，且在中以為根節(jié)點。 下列是本課題中用到的術(shù)語定義:1. True 節(jié)點: 表示有唯一MAC地址并且可以通過SNMP獲得AFT信息的網(wǎng)絡設備。所有主機都是True 節(jié)點。為了簡化本研究課題，課題中的True 節(jié)點用交換機（Switch）代表。2. False 節(jié)點: 表示與True 節(jié)點相反的網(wǎng)絡設備。也就是啞元設備或無法通過SNMP獲得AFT信息的設備。本研究課題簡化False 節(jié)點,用Hub

14、代表。3. Subnet: 表示最大IP網(wǎng)絡設備集合任意兩設備之間通信都不需要經(jīng)過路由器。4. 完備性: 端口的AFT信息中包含子網(wǎng)中所有節(jié)點。5. 完備性: 端口的AFT信息中包含子網(wǎng)集中所有節(jié)點。III 拓撲算法概述本課題中的網(wǎng)絡自拓撲算法(TD)在實際網(wǎng)絡中應用主要實現(xiàn)：1. 在給定的網(wǎng)絡中，能夠正確拓撲發(fā)現(xiàn)True節(jié)點活動端口之間的物理連接關(guān)系。2. 通過已知網(wǎng)絡設備的有限AFT信息，推導網(wǎng)絡中的False節(jié)點如Hub，以及與之相鄰的網(wǎng)絡節(jié)點之間的連接關(guān)系。下面我們闡述網(wǎng)絡自拓撲算法TD的詳細設計。TD算法設計主要分為三步驟：1. 充分獲得網(wǎng)絡設備的AFTs信息。2. 利用一定的推導算

15、法或稱為技術(shù)，為每個子網(wǎng)建立數(shù)學模型：無向連接樹。但是在算法設計過程中考慮到AFTs信息可能不完備，所以推導算法引入了一種輔助結(jié)構(gòu)樹Assistant Data Tree(簡稱ADT),以簡化算法實現(xiàn)過程。3. 約定合并規(guī)則，合并所有無向樹的ADT結(jié)構(gòu)。遞歸合并無向樹的ADT結(jié)構(gòu)，如果結(jié)果得到的是一獨立的輔助結(jié)構(gòu)樹，那么就認為這顆輔助結(jié)構(gòu)樹就是網(wǎng)絡的實際拓撲結(jié)構(gòu)。這一結(jié)論在后面將給出證明。A. 輔助結(jié)構(gòu)樹AT的數(shù)據(jù)結(jié)構(gòu)子網(wǎng)的連接樹為，交換機在中可以分為兩類節(jié)點：交叉節(jié)點和橫越節(jié)點。在給出定義之前，首先我先給出圖論中度的概念：無向圖的頂點的度是指中與關(guān)聯(lián)的邊的數(shù)目。用表示頂點的度。l 度大于等于

16、3的節(jié)點稱為交叉節(jié)點。l 度等于2的節(jié)點稱為橫越節(jié)點。在圖1-1（b）中交換機，都是橫越節(jié)點，是交叉節(jié)點。定義1。 的輔助結(jié)構(gòu)樹用描述：每個頂點是中節(jié)點的集合，弧是中邊的集合。每個交叉節(jié)點和葉節(jié)點可以用單獨定點表示，而橫越節(jié)點段(組)（若多于一個的連續(xù)橫越節(jié)點相連接，稱為橫越節(jié)點段或組）可用一個或多個頂點表示。 為了陳述方便，在無向連接樹中，中的元素稱為邊，中的元素稱為節(jié)點。而對應的輔助結(jié)構(gòu)樹中，中的元素稱為頂點，中的元素稱為弧。需要強調(diào)的是元素，可能包含多個中的節(jié)點，理由我們在后面章節(jié)給予闡述。無向連接樹與其對應的輔助結(jié)構(gòu)樹之間存在同構(gòu)的。定義2。 一般說來，兩個圖和是同構(gòu)的(記為)，如果存

17、在兩個一一映射： ： 使得當且僅當，這樣的映射對稱為和之間的一個同構(gòu)。所以，通過細分輔助結(jié)構(gòu)樹，使得每個交叉節(jié)點在中都用獨立的頂點代替，一旦達到這種狀態(tài)，那么就可以反向得到所對應的無向樹。相反，通過無向樹，也可以得到輔助結(jié)構(gòu)樹。很容易發(fā)現(xiàn)，由無向樹可以得到唯一的骨架樹，反向推導則不成立。定義3。如果輔助結(jié)構(gòu)樹中任意頂點映射到無向樹中的節(jié)點都是一一對應，即由到的映射，總存在唯一節(jié)點與頂點對應，那么稱他們是信任節(jié)點或信任頂點。所以給定網(wǎng)絡中,如果任意節(jié)點都是信任節(jié)點，那么這個網(wǎng)絡拓撲結(jié)構(gòu)可以被唯一確定。B. 輔助結(jié)構(gòu)樹生成ATC算法概述輔助結(jié)構(gòu)樹生成算法是拓撲算法的核心部分，在IV章節(jié)會詳細的介紹

18、。基于無向生成樹，選定任意節(jié)點為根節(jié)點，則為以為根節(jié)點的生成樹。定義4。是任意節(jié)點，以為根節(jié)點的子樹的所有節(jié)點,。而是包含節(jié)點的數(shù)量。特別要聲明的是與存在區(qū)別：在中包含子網(wǎng)內(nèi)所有的節(jié)點包括交換機以及根節(jié)點。而則只包含葉節(jié)點,在圖2(1)中,圖2(1)屬性1。 中任意一對節(jié)點i. 如果節(jié)點是的子孫節(jié)點，則。ii. 節(jié)點，或者是交叉節(jié)點，則。為了下面討論，現(xiàn)引入有序序列表。節(jié)點，按照值大小，生成序列表。如果節(jié)點具有相同值，則橫越節(jié)點排列在交叉節(jié)點前面。在圖2(1)中,是根節(jié)點,根據(jù)值的大小, 是序列的第一個元素，所有的葉節(jié)點的值最小，所以在列表的最后。是交叉節(jié)點，而其他的交換機都是橫越節(jié)點，由屬性

19、1可知,在序列表中,在其他交換機的前面,所以子網(wǎng)的序列是，其中具有相同的值,具有相同值。ATC算法依據(jù)元素在序列中的順序，首先取第一個序列元素，作為輔助結(jié)構(gòu)樹的第一個節(jié)點，并可以計算出的值。然后取出節(jié)點作為第二節(jié)點。由于都是橫越節(jié)點而且值都相同所以不需要區(qū)別順序，所以在輔助結(jié)構(gòu)樹中僅用同一個頂點代表。由與值的差異可以判斷出，在和之間存在一個False節(jié)點Hub。同理,與、之間也存在Hub節(jié)點，與之間存在Hub節(jié)點，見圖2(2) 。圖2(2)從列表中依據(jù)的值大小依次提取節(jié)點,最終可以得到的輔助結(jié)構(gòu)樹。IV 輔助結(jié)構(gòu)樹生成(ATC)算法本章節(jié)詳細介紹ATC算法。介紹之前先闡述幾個理論基本屬性。然后

20、介紹在ATC算法中是如何應用的。A. 基本屬性定義 現(xiàn)有節(jié)點集(一個或多個子網(wǎng)),且為無向連接樹。為根節(jié)點。假設任意節(jié)點的AFT相對于都是完備的,任意節(jié)點，根端口(rootport)是指與根節(jié)點相連接的端口，其他端口為葉端口(leafports)。所以表達式為：集合有以下屬性：屬性2：中任意節(jié)點,。 證明:由于是集合的連接樹，所以任意葉節(jié)點且。由的計算表達式可得，任意子樹都至少包含一個葉節(jié)點。屬性3：任意節(jié)點以及其任意子孫節(jié)點，存在且。 屬性4：任意節(jié)點，其子孫節(jié)點，存在且。證明:由屬性2可知。由于，且的計算表達式為 可推導包含，但不在中。得證。屬性5：任意交叉節(jié)點，其任意一子孫節(jié)點，存在且。

21、證明:節(jié)點是交叉節(jié)點，所以度，即葉節(jié)點數(shù)量。由屬性1可知任意子樹至少包含一個節(jié)點(應該是葉節(jié)點)。得證。利用以上屬性可以確定節(jié)點之間的順序?，F(xiàn)定義：等式2定義5：節(jié)點在序列中是完備的是指:節(jié)點出現(xiàn)在其所在序列的所有父節(jié)點之后，出現(xiàn)在所有子孫節(jié)點之前。 引理1: 任意節(jié)點以及交叉節(jié)點在序列中順序是完備的。 證明:由等式2可知根節(jié)點,故在序列中是第一個節(jié)點。假設節(jié)點以及交叉節(jié)點,是其子節(jié)點(),由屬性3,4可得,綜上可得即。得證。 但是引理1不適合交叉節(jié)點，因為橫越節(jié)點不包含在中。在輔助結(jié)構(gòu)樹中具有相同值的橫越節(jié)點用一個頂點表示。為了區(qū)別橫越節(jié)點順序，應用如下引理： 引理2：任意兩橫越節(jié)點,為兩節(jié)

22、點之間的路徑,假設路徑中存在節(jié)點，則也是橫越節(jié)點且。證明:由屬性3,4可得，如果節(jié)點是或交叉節(jié)點，則。由于題設中，所以w必橫越節(jié)點。推論1： 假定存在橫越節(jié)點,是所有橫越節(jié)點集合且,如果任意節(jié)點,則所有中節(jié)點是連續(xù)的。B. ATC算法 (Algorithm)STC算法目標就是把連接樹轉(zhuǎn)化為輔助結(jié)構(gòu)樹。轉(zhuǎn)化過程是迭代的過程，初始化狀態(tài)為空，每次迭代過程中加入TRUE節(jié)點到中，直到所有中的TRUE節(jié)點都在中。STC算法需要初始值集合、集合、根結(jié)點和所有節(jié)點的AFT信息即。在中每個頂點都代表集合 (中包含一個或多個節(jié)點),代表中節(jié)點值。如果中某節(jié)點包含了多個橫越節(jié)點，則節(jié)點具有相同的值。中弧代表中的

23、邊。在計算中弧的過程中，必然會出現(xiàn)弧的前端連接有節(jié)點,另一端末梢節(jié)點沒有連接節(jié)點或稱沒有發(fā)現(xiàn),這種弧稱為末梢弧(見圖3(a)中)，末梢弧集合記作。如果末梢弧的末梢節(jié)點被發(fā)現(xiàn)，則此末梢弧從集合中被刪除。每一弧都有相應的一個集合相對應。是指通過弧所能到達的節(jié)點集合即：節(jié)點的某個端口（連接弧的端口）的AFT值。為了詳細闡述ATC算法，仍以圖2(1)為例。ATC算法首先獲得每個節(jié)點的根端口，和的值。然后比較節(jié)點的值，構(gòu)造序列。然后初始化，選擇頂點代表根節(jié)點，并記， (依據(jù)等式2)，并把與根節(jié)點連接的個末梢弧添加到集合中。圖3(a)是STC算法初始狀態(tài)。圖3(a)初始化后，ATC算法反復從序列中抽取第一

24、元素，用表示，并修改， 為了方便討論，約定末梢弧已知連接節(jié)點記作。首先驗證末梢弧是否與新抽取的元素相連接：引理1:如果存在關(guān)系，則與節(jié)點相連接，否則不與末梢弧連接。ATC算法在依據(jù)等式2計算節(jié)點值的時候，判斷橫越節(jié)點準則：如果且是整數(shù)，那么與節(jié)點都是橫越節(jié)點。如果是橫越節(jié)點則添加節(jié)點到集合中，在中都用表示。見圖3(b)。都是橫越節(jié)點，且，。圖3(b)如果，那么在中將用新的頂點表示。頂點對應集合，,的每個葉端口，都對應有末梢弧，并添加到中。如果，則與之間直接連接即不存在其它節(jié)點。圖3(c), , ,所以節(jié)點在中用新的頂點代替。由于，故與或直接連接。圖3(c)假設（a是末梢?。敲垂?jié)點的上級節(jié)點

25、是FALSE節(jié)點，存在兩種情況需要考慮：1. 如果是TRUE頂點，,那么在與頂點之間插入FALSE頂點，且，（依據(jù)等式2，頂點是交叉頂點類型）。由頂點引伸出的2個末梢弧，。算法首先用弧連接頂點，然后用頂點的其中一個末梢弧連接頂點即（是末梢弧線），（是頂點的另一個末梢弧，是頂點的末梢?。Ｗ詈髲募现袆h除末梢弧，添加末梢弧。圖3(d)在圖3(d)中，是新發(fā)現(xiàn)的節(jié)點在中用代表，是代表節(jié)點。由于，需要與的其中一個末梢弧（，）連接。添加頂點代表Hub, 與頂點（節(jié)點）連接，與頂點（節(jié)點）連接。故，頂點的另一個末梢弧具有，見圖3(e)。圖3(e)2. 如果頂點是FALSE節(jié)點（如，Hub），則頂點是節(jié)點

26、的父節(jié)點。此時創(chuàng)建新末梢弧且，然后添加末梢弧到中，末梢弧連接節(jié)點（即頂點），刪除末梢弧。見圖3(f) 。圖3(f)假設算法從序列中抽取節(jié)點元素。由于頂點有末梢弧且，也就是說通過這末梢弧可以到達節(jié)點。但是因為包含也節(jié)點，此時有兩種情況：1. 在頂點與之間存在另一個FALSE節(jié)點即Hub。2. 頂點（Hub）存在另一端口連接頂點。 從網(wǎng)絡布線的實際設計思路考慮，后者出現(xiàn)的幾率要高。所以ATC算法搜尋連接頂點與，然后添加新的末梢弧且，見圖3(g)。圖3(g)按同樣的方法最終把圖2(1)中的無向樹轉(zhuǎn)化為對應的輔助數(shù)據(jù)樹如圖3(h)。圖3(h)定理1：給定連接樹，并指定根節(jié)點，STC算法相應的創(chuàng)建輔助結(jié)

27、構(gòu)樹，在中每個節(jié)點，或交叉節(jié)點在中都可以被唯一的頂點表示。證明:序列中的元素加入到輔助結(jié)構(gòu)樹過程中都是按照在中的順序依次加入。由引理1可知，中每個節(jié)點，或交叉節(jié)點，在中表現(xiàn)都是出現(xiàn)在其所有子節(jié)點之前，所有父節(jié)點之后，即順序是固定的。從序列中選定節(jié)點元素，如果父節(jié)點的末梢弧，那么節(jié)點元素與末梢弧相連。所以在中的位置是唯一確定的。假如，那么在頂點與之間插入FALSE節(jié)點。利用引理2,在中具有相同的橫越節(jié)點，在中用同一頂點表示。綜上可知，是一顆有效的樹e。C. 降低難度系數(shù)：獲取完備的AFTs信息。由的定義，每個節(jié)點所包含的AFTs信息就是節(jié)點的所有葉端口AFT信息總和。所以只要這些葉端口完備即可。

28、判斷根端口則通過端口的AFT是否包含根節(jié)點。必要條件1:給定連接樹，且集合已知，是其根節(jié)點。每個節(jié)點，根端口的AFT必須包含根節(jié)點，所有葉端口在中必須完備的。在下一章中介紹必要條件1很容易滿足。D. (AFTs-Supplement) 信息在IV-C部分介紹在了AFTs不完整的情況下如何得到輔助結(jié)構(gòu)樹。但是我們在合并所有子網(wǎng)的輔助結(jié)構(gòu)樹時候，需要每個節(jié)點的AFTs信息包含前導端口所指向的節(jié)點信息。為了方便討論，把這部分信息記為。現(xiàn)假設是中信任節(jié)點集合。以輔助結(jié)構(gòu)樹為數(shù)據(jù)基礎，根節(jié)點為起點，后序遍歷方式，采用遞歸方法計算得到。在計算過程中，任意以頂點為根節(jié)點的子樹都對應存在信任節(jié)點集合。下面詳細

29、闡述程序?qū)崿F(xiàn)過程：給定頂點以及其子節(jié)點記為，在后序遍歷（post-order tour）過程中，每個的子節(jié)點都把其信任節(jié)點集合返回給，獲得所有子節(jié)點的信任集合后就可以得到頂點的信任節(jié)點集合即：。頂點的每個葉端口都對應著一個子節(jié)點，添加到頂點對應端口的AFT信息中，端口增加信息。E. 合并輔助結(jié)構(gòu)樹TD算法由兩個主要部分組成.首先,依據(jù)ATC輔助結(jié)構(gòu)樹生成算法計算每個子網(wǎng)的輔助結(jié)構(gòu)樹。需要獲得子網(wǎng)的信息包括：子網(wǎng)內(nèi)的所有節(jié)點列表，根節(jié)點，以及子網(wǎng)內(nèi)節(jié)點的AFTs信息，依據(jù)獲得的有效信息每個子網(wǎng)可以對應生成一個輔助結(jié)構(gòu)樹。然后我們可以根據(jù)一定的規(guī)則合并每個子網(wǎng)的輔助結(jié)構(gòu)樹?，F(xiàn)有兩輔助結(jié)構(gòu)樹，。分別

30、是其節(jié)點結(jié)合，是信任節(jié)點結(jié)合。假設兩輔助結(jié)構(gòu)樹具有共同的信任節(jié)點（至少一個），那么這兩輔助結(jié)構(gòu)樹可以合并，即且。合并以后，。再次選擇一輔助結(jié)構(gòu)樹與之合并，遞歸合并后，如果最終合并結(jié)果是一顆獨立的輔助結(jié)構(gòu)樹即計算所需要的該網(wǎng)絡拓撲物理結(jié)構(gòu)。VI 算法分析A. 正確性?，F(xiàn)證明算法的正確性與復雜度。本論文中TD算法的正確性完全依賴于ATC算法的正確性。定理2：TD算法為每個子網(wǎng)可以創(chuàng)建一個輔助結(jié)構(gòu)樹。證明:(由定理1可以得證)下面證明合并輔助結(jié)構(gòu)樹算法的正確性。假設存在兩輔助結(jié)構(gòu)樹和以及對應連接樹節(jié)點集合，。他們信任節(jié)點集合為和，且，。TD算法合并后，記，。經(jīng)證明節(jié)點的AFTs信息對于集合滿足必要條

31、件1。即合并后的連接樹是有效的。B. 復雜度。闡述本算法的復雜度。TD算法主要由STC算法和兩部分組成。先考慮時間復雜度。STC算法的運行時間復雜度是，算法的運行時間復雜度是，所以TD算法運行時間的復雜度是。VII 總結(jié)本文詳細討論了怎樣利用圖論的理論知識來實現(xiàn)網(wǎng)絡拓撲結(jié)構(gòu)的自動發(fā)現(xiàn)，介紹了拓撲發(fā)現(xiàn)算法中的主要兩步驟，同時對實現(xiàn)過程中的關(guān)鍵技術(shù)進行了詳細分析。但是本文在分析FALSE 節(jié)點的時候，還沒有給出很好的算法分析，所以下一步工作重點是重點研究FALSE節(jié)點，研究出發(fā)點是FALSE節(jié)點與TRUE節(jié)點對網(wǎng)絡數(shù)據(jù)流的影響，找出特征，進一步分析處理，旨在提高網(wǎng)絡拓撲算法的準確度，降低算法的復雜度。References:1 Y.Bejerano, Y.Breitbart, M.Garofalakis, and R.Rastogi,