基于距離的IPv6校園網拓撲發現整合算法*

董守玲 李佳 張凌

(華南理工大學計算機科學與工程學院，廣東廣州510006)

拓撲發現是網絡管理的一項基本功能.由于下一代互聯網IPv6協議中地址結構等方面的變化以及IPv6網絡中龐大的節點數量，適用于IPv4網絡的拓撲發現方法已不再適用于IPv6網絡環境.由于Traceroute6探測方法是利用ICMPv6消息發現從源地址到目的地址之間通過的路由器來得到網絡拓撲，它獨立于IP的特性使得許多學者研究采用Traceroute6探測方法對IPv6的骨干網網絡層的拓撲進行拓撲發現.Astic等［1］提出了一種基于Traceroute6的分級結構的拓撲發現思想，該方法雖然對局域網的管理收到了良好的效果，但需要在每一個子網內安置探測點，系統較為復雜.Daniel等［2］提出了一種利用源路由選項進行改進的基于Traceroute6的拓撲發現思想，對6Bone網絡進行了大規模的探測，但是目前并不是所有路由器都支持IPv6的源路由選項，而且利用源路由機制進行拓撲發現會大幅增加探測時間.國內在IPv6網絡拓撲發現領域的研究起步較晚，同樣主要研究基于Traceroute6的拓撲發現方法［3-7］，這種方法通用性好，算法容易實現，但存在路由別名的問題(同一路由器的不同接口地址被誤認為是多個路由器)，致使準確性不高;此外，Traceroute6探測方法不能發現網段信息，而且如果給定的探測目的地址缺少部分邊界路由器，則這些邊界路由器及相連鏈路不能被發現，或發現的信息不完整.若增加探測節點來提升完整性，則會增加探測時間以及出現更多的路由別名問題.針對Traceroute6拓撲發現方法存在的不足，許多學者也在使用源路由提高完整性、減少路由別名、減少冗余探測提高性能方面進行了探討和研究［8-12］.

開放式最短路徑優先(OSPF)協議是一個內部網關協議，用于在單一自治系統內決策路由.OSPF域中的每臺路由器上都有一個鏈路狀態數據庫，存放關于整個路由域的鏈路狀態信息.當網絡結構發生變化時，路由器之間通過交換過程和泛洪過程實現鏈路狀態數據庫的動態同步，從而得到本區域的拓撲結構.如果能與網絡上的路由器交換信息，就可以得到網絡拓撲信息.曾有學者利用OSPF協議進行IPv4網絡環境下的拓撲發現［13］.這種發現方法的準確率令人滿意，而且包含豐富的子網信息，更重要的是，該方法不存在路由別名的問題.但是，該方法只能得到子網信息，不能得到接口信息，而且OSPF從第3版本(OSPFv3，用于IPv6網絡)開始不再用IPv6地址標識路由器，雖然OSPFv3協議在IPv6網絡的路由設計中得到了廣泛的應用，但該發現方法在IPv6環境中的使用受到了限制.

基于Traceroute6的拓撲發現方法和基于OSPF路由協議發現方法各有優缺點，如果將這兩種拓撲發現方法結合，就可以利用OSPFv3發現的拓撲信息來對Traceroute6發現的信息進行補充和修正，改善拓撲結果的覆蓋率以及解決路由別名的問題，而利用Traceroute6發現的信息又可以標識OSPFv3發現的路由器的IPv6地址及接口.

這兩種拓撲發現方法結合的難點在于，基于Traceroute6的拓撲發現方法是用IPv6地址來標識路由器的，而OSPFv3協議不包含地址信息，它是用RouterID來標識路由器的.

筆者曾提出一個名為ANTDBMP的算法［14］.該算法分別使用基于Traceroute6的拓撲發現方法和基于OSPF的拓撲發現方法進行拓撲發現，并基于跳數(hop)成功地將兩種方法發現的結果進行整合，得到了較好的效果.但這種基于跳數的整合方法也存在一些不足之處，而且系統效率不高.針對這個問題，文中提出一個新的IPv6網絡拓撲信息的整合算法DIAITD(Distance-Based Integrated Algorithm for IPv6 Topology Discovery)，并通過實際網絡對該算法進行了測試.

1 DIAITD算法

根據OSPF協議，每臺運行OSPF路由協議的路由器必須用RouterID來唯一標識.RouterID通常為一個IPv4地址或者是一個有意義的字符串.若僅僅拿RouterID和基于Traceroute6探測發現的IPv6地址作對比，很難發現兩者的直接聯系.由于OSPF的鏈路狀態通知中有豐富的子網信息，可以利用子網信息來查找兩種拓撲發現方法的關聯之處.

1.1 相關工作

ANTDBMP算法［14］首先將利用 Traceroute6發現的IPv6地址和利用OSPFv3協議發現的子網信息進行比對，確定地址分布在哪些網段內;然后采用UDP數據包探測法計算IPv6地址以及屬于該子網的OSPF路由器的跳數，根據對比跳數來確定IPv6地址屬于哪一臺OSPF路由器;最后通過其它信息對特殊的情況進行分析和修正.

但是，ANTDBMP算法存在一些缺陷.首先，OSPF路由器的跳數計算是將該路由器的RouterID作為目標地址進行Traceroute6操作從而得出，如果RouterID不是IPv4地址而是一個有意義的字符串(例如路由器的位置)，則無法計算OSPF路由器的跳數;其次，即使所有RouterID都是IPv4地址，當Traceroute6的某IPv4地址出現目的地不可達時(路由器設置了不回應)，就得不到該地址的跳數;再者，即使所有地址都可達，跳數都能正確返回，同一路由器的不同地址也會因為路由表規定的路徑不同而返回不同的跳數.如圖1所示，路由器R1、R2、R3兩兩相連，以R1為探測源點，到達R3的路徑就有兩條:路徑1(跳數為2，R1-R3);路徑2(跳數為3，R1-R2-R3).當對 R3上的 RouterID進行 Traceroute6操作時，可能路由表選了路徑2，而對R3的一個IPv6地址進行Traceroute6操作時，路由表選了路徑1，那么返回的跳數就不一樣，這時根據跳數進行判斷就會判斷錯誤.

圖1 不同的傳輸路徑及其返回的跳數Fig.1 Different transmission paths and their hops

1.2 DIAITD 算法原理

由于基于跳數結合的方法在某些情況下變得不可靠，文中提出一種新的結合方式，不再用跳數進行判斷，而是利用連接關系表中的信息.

定義D(A)為連接關系表中節點A到網關的最短距離，N1、N2、N3為子網，IPA、IPB、IPC 為 IPv6地址.

根據網絡路由器之間的連接關系，有如下性質.

性質1 對于任何存根子網，有且只有一臺路由器屬于該存根子網.

根據性質1可以得到如下結論:?N1∈存根子網，?R1∈N1，?IPA∈N1，如果 D(IPA)=D(R1)，那么IPA∈R1.

性質2 對于任何路由器間子網，有且只有兩臺路由器屬于該子網，它們有共同的子網前綴.

根據性質2可以得到如下結論:?N1∈路由器間子網，?R1∈N1，?R2∈N1，?IPA∈N1，如果D(IPA)=D(R1)且 D(IPA)≠D(R2)，那么 IPA∈R1.

性質3 一個路由器的不同接口具有不同的子網地址.

根據上述性質和結論，分別定義基于OSPF路由協議的拓撲發現方法和基于Traceroute6的拓撲發現方法得到的節點間的連接關系為LinkList_OSPF和 LinkList_Traceroute6.以 LinkList_OSPF 為例，以網關作為根節點，通過最短路徑算法求出在連接關系表中其它所有節點到網關的最短距離.對LinkList_Traceroute6作同樣的分析，然后以這個距離作為度量值.

取出由Traceroute6拓撲發現方法得到的一個IPv6地址IPA，從子網集合Subnet_OSPF中進行查找，看是否存在與IPA地址前綴匹配的子網N1，若N1對應的OSPF路由器有且只有一臺路由器R1(即N1為存根子網)，則比較 D(IPA)和D(R1)，若相等，則IPA屬于R1;若存在另外一個路由器R2(即N1為路由器間子網)，則分別比較D(IPA)、D(R1)和D(R2)，從而得出IPA屬于哪一臺路由器.

但僅僅用距離來進行判斷時，在以下情況下會失效:當測試地址(記為IPA)為路由器間網絡的地址，且兩臺OSPF路由器(記為R1和R2)與網關的距離相等時，無法判斷IPA是屬于R1還是屬于R2，如圖2所示.

圖2 IPA、R1、R2與網關的最短距離Fig.2 Shortest distances between gateway and IPA，R1and R2

解決方法1 對于距離相等的情況，取IPA的子網前綴prefixA，根據prefixA構造一個新的該子網下的任意地址IPB.例如，prefixA為2001:da8:250:3001::，可以構造一個 IPv6地址2001:da8:250:3001::45.通過網關對IPB發ICMP探測包，則該網段的路由器地址通常選擇發出回應包的接口(如圖2中的IPC)返回一個地址不可達的ICMP回應包，若D(IPC)=D(IPA)且IPC≠IPA，則IPC與IPA是同一路由器下的兩個接口地址，接下來只需分別查看R1與R2的子網表，通常有且只有一個路由器包含IPC所在子網的信息，從而認定IPA屬于那臺有IPC子網信息的路由器.

解決方法2 查看接口表，看IPA所在路由器是否存在其它接口地址.假設存在其它地址IPC是IPA所在路由器上的另一接口地址，如圖3所示.既然IPA和IPC是同一路由器的不同接口地址，而只有一個接口會遇到同一個網段距離相等的情況，因此IPC不會出現同一個網段距離相等的問題.對IPC采用上述提到的基于距離的整合方法，可以判斷IPC位于路由器R1上，因此作為同一路由器的接口地址，IPA也屬于路由器R1.

圖3 同一路由器上的接口與網關的最短距離Fig.3 Shortest distances between gateway and interfaces on the same router

解決方法3 查看子網表和接口表，查看是否存在前綴同樣為prefixA的其它接口地址.如圖3所示，存在與IPA前綴相同的IPD.由于同一路由器間網絡里有且只有兩個接口地址，因此，若利用解決方法1和2能確定出IPD屬于哪一臺路由器(見圖3，IPD屬于R2)，相應地就能確定IPA屬于該網段下的另一臺路由器(即R1).

通過上述3種解決方法，能有效解決基于距離的整合方法出現距離相同時無法判斷的問題.

這種基于距離的DIAITD算法無需發ICMP包進行探測，只需分析連接關系表，在減少網絡通信的同時縮短了分析時間;而且，最短路徑算法是一個被廣泛使用的成熟算法，其時間復雜度不高，只要連接關系表的數據正確，計算出來的距離就是正確的，這樣便保證了DIAITD算法的準確率;再者，由于無需借用RouterID進行判斷，整合方法與路由協議無關，因此該結合方法同樣適用于其它拓撲發現方法間的結合，具有很好的通用性.

1.3 DIAITD 算法描述

下面給出DIAITD算法描述，其中RouterList_Traceroute6代表基于Traceroute6獲取的路由器節點集合，RouterList_OSPF代表基于OSPFv3獲取的路由器節點集合，LinkList_Traceroute6代表基于Traceroute6獲取的連接關系，LinkList_OSPF代表基于OSPFv3獲取的連接關系，Subnet_OSPF代表基于OSPFv3獲取的子網集合，D(A)代表A與網關之間的距離，CurDistance表示與網關的最短距離計數，baseNodeList表示已處理的節點列表.

首先計算基于所有OSPF路由器到網關的最短距離，其算法描述如下:

其次計算Traceroute6獲得的IPv6地址到網關的最短距離，算法與上述算法類似，此處不再贅述.

根據上述計算的最短距離，對拓撲發現結果進行整合.其算法描述如下:

1.4 DIAITD算法的時間復雜度分析

計算所有路由器到網關的最短距離時，最壞的情況時要遍歷LinkList才能找到對應Ri的記錄，此時時間復雜度為O(ML)，其中M為RouterList的大小，L為LinkList的大小;在整合時，最壞的情況下要遍歷子網表才能找到對應Ri的子網記錄，測試算法的時間復雜度為O(MS)，S為Subnet_OSPF的大小.因此總的復雜度為O(ML)+O(MS).

2 測試與結果分析

基于文中所提出的拓撲發現整合算法，使用java語言在Linux環境中設計并實現了一個IPv6網絡層拓撲發現系統.該系統包含5個模塊:2個探測引擎、1個拓撲整合模塊、1個拓撲保存以及1個拓撲顯示模塊.

2個探測引擎中的一個基于利用源路由改進的Traceroute6方法，另一個基于OSPFv3路由協議.系統利用這兩個探測引擎分別去收集網絡拓撲信息.其中，基于Traceroute6的探測引擎收集信息分為初步探測拓撲階段、源路由測試階段以及交叉路徑發現階段.基于OSPFv3路由協議的發現方法是將計算機模擬成路由器，與網絡上的路由器交換網絡拓撲信息，從而得到完整的網絡拓撲信息［15］.在整合模塊中，利用DIAITD算法把兩個拓撲發現引擎的拓撲發現結果進行整合.整合后的拓撲結果可以通過拓撲顯示模塊進行顯示，也可以通過拓撲保存模塊保存進數據庫.

實驗在華南理工大學校園網上進行，為測試系統的各項指標分別進行了多項測試，同時比較新舊算法的準確性、完整性以及效率.

測試1 比較改進的基于距離的拓撲信息整合算法(DIAITD算法)和舊的基于跳數的整合算法(ANTDBMP算法).

為保證測試的真實性，隨機采用每臺路由器上的一個接口地址作為探測節點，共22個.通過OSPF探測引擎發現OSPF路由器22臺，通過Traceroute6探測引擎發現31個IPv6地址，結合情況如表1所示，其中，準確率為成功結合的IPv6地址數與IPv6地址總數之比.

表1 新舊拓撲信息整合算法發現整合效果對比Table 1 Comparison of integration effect between original and new algorithms for topology information integration

表1的數據顯示，基于距離的DIAITD算法向網絡發送了10個ICMP探測包，這是由于測試時程序遇到了第1.2節中提到的距離相等的問題，而其采用解決方法1來解決問題，因此產生了網絡通信.通過對比發現，新的基于距離的拓撲發現整合算法比基于跳數的算法更加準確，分析整合時間和發包數也大為減少.

測試2 分別采用基于OSPF的拓撲發現方法、基于Traceroute6的拓撲發現方法和DIAITD整合算法對網絡進行測試，結果如表2所示.

表2 3種拓撲發現算法結果的比較Table 2 Comparison of results among three topology discovery algorithms

從表2中可以看出，OSPFv3發現方法只能發現子網信息，不能得到接口信息，Traceroute6發現方法可以發現接口信息，但是不能發現網段信息，并且存在別名問題，這導致發現的路由器和連接關系個數與真實情況有出入.另外Traceroute6發現的接口個數與探測節點集合的大小有關，由于本次探測的探測節點只有22個，因此只發現了31個接口，大量的接口信息不能被發現.DIAITD整合算法不僅可以發現路由器設備，還可以發現子網及接口，發現的信息比單獨的OSPFv3發現方法或Traceroute6發現方法更為完整，經驗證與真實拓撲圖更為吻合.由于整合算法的接口信息來源于Traceroute6發現方法，因此接口數目與Traceroute6發現方法發現的一樣.

測試3 校園網環境與加入公網環境拓撲結果的比較.

在原有地址集合里增加了3個公網地址:上海交通大學的地址(ipv6.sjtu.edu.cn，IP 為 2001:da8:8000:1::80)、華南農業大學的地址(ipv6.scau.edu.cn，IP 為 2001:da8:2004:1000:202:116:160:48)和谷歌的地址(ipv6.google.com，IP 為 2404:6800:8003::69).探測結果如表3所示.

表3 校園網環境與公網環境拓撲發現結果比較Table 3 Comparison of discovery results between campus network and public network

表3表明，在增加了3個公網地址后，除子網個數沒有變化外，路由器個數、連接關系個數和接口個數都有不同程度的增加.子網個數沒有變化的原因是子網信息是利用OSPF協議發現的，而公網和校園網不屬于同一個OSPF域，因此運用OSPF協議只能獲得華南理工大學校園網的信息，在校外的網絡只能用Traceroute來探測.在這種情況下，校外的子網就不能被發現了.

3 結語

文中設計和實現了一個基于距離的IPv6校園網拓撲發現整合算法，該算法將兩種不同的拓撲發現方法的拓撲結果進行整合.測試結果證明，該算法能更有效、準確、迅速地整合拓撲信息.拓撲信息的整合是一個相對新的研究領域，雖然文中方法目前只能對Traceroute6和OSPF協議的拓撲結構進行整合，但基于OSPF協議的廣泛應用以及Traceroute6的通用性，整合之后的結果無論從完整度和精確度來看都比單一拓撲發現方法更接近實際網絡情況，這種基于距離的整合方法定能對處于同一個OSPF域的IPv6校園網拓撲發現提供有效幫助.

［1］Astic I，Festor O.A hierarchical topology discovery service for IPv6 networks［C］∥Proceedings of 2002 IEEE/IFIP Network Operations and Management Symposium.Florence:Institute of Electrical and Electronics Engineers Incorporation，2002:497-510.

［2］Daniel G W，Fangzhe C，Ramesh V，et al.Topology discovery for public IPv6 networks［J］.Computer Communications Review，2003，33(3):59-68.

［3］Dong S L，Zhang L，Lan C F.Compatible IPv4 and IPv6 networks topology discovery schema based on general protocols［C］∥Proceedings of 2007 International Conference on Broadband Network ＆ Multimedia Technology.Beijing:IC-BNMT，2007:307-311.

［4］Liu Z S，Luo J Y，Wang Q X.Large scale topology discovery for public IPv6 networks［C］∥Proceedings of 7th International Conference on Networking.Cancun:IEEE Computer Society，2008:639-644.

［5］李元臣，劉維群，匡國防，等.基于 Traceroute6的 IPv6網絡拓撲發現技術［J］.計算機應用，2008，28(3):560-562.Li Yuan-chen，Liu Wei-qun，Kuang Guo-fang，et al.Topology discovery for IPv6 networks based on Traceroute6［J］.Computer Applications，2008，28(3):560-562.

［6］宮晨，郎昕培，陳英，等.IPv6骨干網絡的拓撲發現［J］.計算機科學，2006，33(4):29-31.Gong Chen，Lang Xin-pei，Chen Ying，et al.Topology discovery for backbone of IPv6 networks［J］.Computer Science，2006，33(4):29-31.

［7］叢林，陳陽，鄧北星，等.CERNET2 IPv6網絡層拓撲發現［J］.廈門大學學報:自然科學版，2007，46(增刊 2):6-8.Cong Lin，Chen Yang，Deng Bei-xing，et al.The IPv6 network layer topology discovery of CERNET2 ［J］.Journal of Xiamen University:Natural Science，2007，46(Suppl 2):6-8.

［8］周苗，楊家海，吳建平.基于滑動地址序列的IPv6網絡拓撲發現引擎［J］.清華大學學報:自然科學版，2009，49(8):1241-1244.Zhou Miao，Yang Jia-hai，Wu Jian-ping.IPv6 topology discovery engine based on a sequence of sliding addresses［J］.Journal of Tsinghua University:Science and Technology，2009，49(8):1241-1244.

［9］楊柳，李振宇，張大方，等.冗余最小化的IPv6拓撲發現方法 ［J］.計算機研究與發展，2007，44(6):939-946.Yang Liu，Li Zhen-yu，Zhang Da-fang，et al.Topology discovery with smallest redundancy in IPv6 ［J］.Journal of Computer Research and Development，2007，44(6):939-946.

［10］Zhu M M，Luo J Y.An improved solution for IPv6 network topology discovery based on source routing mechanism［C］∥Proceedings of the 2009 International Conference on Communication Softwareand Networks.Macau:IEEE Computer Society，2009:279-282.

［11］Qian S Y，Wang Y H，Xu K.Utilizing destination options header to resolve IPv6 alias resolution［C］∥2010 IEEE Global Telecommunications Conference.Miami:Institute of Electrical and Electronics Engineers Incorporation，2010:1-6.

［12］Qian S Y，Xu M，Qiao Z L，et al.Route positional method for IPv6 alias resolution［C］∥2010 Proceedings of 19th International Conference on Computer Communications and Networks.Zurich:Institute of Electrical and Electronics Engineers Incorporation，2010:1-6.

［13］徐建鋒，鄧永平，丁圣勇.基于OSPF服務器的網絡拓撲發現［J］.計算機應用，2004，24(8):98-100.Xu Jian-feng，Deng Yong-ping，Ding Sheng-yong.OSPF server based network topology discovery［J］.Computer Applications，2004，24(8):98-100.

［14］Dong S L，Li J，Zhang L，et al.A novel algorithm of IPv6 network topology discovery for campus network［C］∥2011 International Conference on Computer Science and Service System.Nanjing:IEEE Computer Society，2011:68-71.

［15］董守玲，張凌，董守斌，等.基于IPv6的下一代互聯網拓撲發現系統及實現方法:中國，ZL 201010275867.x［P］.2012-03-28.