基于ＩＰｖ４和ＩＰｖ６混合網(wǎng)絡(luò)環(huán)境下拓撲發(fā)現(xiàn)算法研究

摘要：對于網(wǎng)絡(luò)性能優(yōu)化，配置控制和故障監(jiān)控等來說有一個準(zhǔn)確的網(wǎng)絡(luò)拓撲結(jié)構(gòu)是至關(guān)重要的。文中提出兩個網(wǎng)絡(luò)層拓撲發(fā)現(xiàn)算法分別對應(yīng)于IPv6-only和 IPv4-only網(wǎng)絡(luò)，一個數(shù)據(jù)鏈路層拓撲發(fā)現(xiàn)算法以及一個在共存的網(wǎng)絡(luò)中的轉(zhuǎn)換探測算法來進行各方面的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)。

關(guān)鍵字：拓撲發(fā)現(xiàn)；IPv6；SNMP；轉(zhuǎn)換方式

中圖分類號：TP393文獻標(biāo)識碼：A文章編號：1009-3044(2008)34-1585-03

Topology Discovery for Coexisting IPv6 and IPv4 Networks

CHEN Wen-feng， LU Ji-guang， WANG Juan

(School of Computer Science， South-Central University for Nationalities， Wuhan 430074， China)

Abstract: Having an accurate network topology is vital for network performance optimization， configuration control， and fault monitoring … etc. In this paper， two network layer topology discovery algorithms for IPv6-only and IPv4-only networks， a data link layer topology discovery algorithm， and a transition detection algorithm of coexisting networks are presented to discover network topologies from various aspects.

Key words: topology discovery; IPv6; SNMP; transition mechanism

1 引言

在網(wǎng)絡(luò)管理功能中，擁有一個精確和完整的網(wǎng)絡(luò)拓撲結(jié)構(gòu)是非常重要的， 如性能優(yōu)化，配置控制和故障監(jiān)控等。拓撲圖可以描述TCP/IP協(xié)議的每一個層，同時能有效協(xié)助網(wǎng)絡(luò)管理員更好地管理網(wǎng)絡(luò)。

有許多IPv4網(wǎng)絡(luò)下拓撲發(fā)現(xiàn)方法，如報告[2-3]。此外，還有關(guān)于IPv6-only的一些建議，如報告[4-5]。大部分這些拓撲發(fā)現(xiàn)算法都是基于ICMP和SNMP。然而這些已經(jīng)眾所周知的方法還是不足以管理IPv6和IPv4共存的網(wǎng)絡(luò)。為展示兩個IP版本一起的拓撲結(jié)構(gòu)，要首先探測重合的部分，即下文中轉(zhuǎn)換方式部署的節(jié)點。

在本文中，提出IPv4與IPv6共存網(wǎng)絡(luò)的拓撲發(fā)現(xiàn)算法。在網(wǎng)絡(luò)層和數(shù)據(jù)鏈路層同時采取SNMP和ICMP技術(shù)。通過ip6routetable或iproutetable的SNMP獲得的動態(tài)管理信息用來構(gòu)建網(wǎng)絡(luò)層拓撲圖，通過attable和dot1dtpfdbtable獲取的信息用來構(gòu)建數(shù)據(jù)鏈路層拓撲圖。使用多播IPv6逆鄰居發(fā)現(xiàn)報文及廣播IPv4 RARP報文收集所有的IP地址。經(jīng)過分析所有IP地址的格式，IP地址重疊的主機就找了出來，同時可以得出所有MAC地址和其相對應(yīng)的全部IP地址。從而就徹底呈現(xiàn)一個完整的混合網(wǎng)絡(luò)拓撲結(jié)構(gòu)。

2 SNMP MIB和ICMP

SNMP MIBs和ICMP報文中的信息是拓撲發(fā)現(xiàn)兩個最常用的資源。SNMP的MIBs提供網(wǎng)絡(luò)管理信息，ICMP可有效地用于發(fā)現(xiàn)網(wǎng)絡(luò)中任意路徑的主機狀態(tài)。

2.1 MIB-II，IPv6 MIB，和Bridge MIB

SNMP的MIB的是一個存放管理對象信息的倉庫。MIB-II，IPv6 MIB，和Bridge MIB管理組在發(fā)現(xiàn)算法中都有使用到。用到MIB-II中三個重要的表：sysservices，attable，iproutetable。system組中的sysservices是用來通過管理節(jié)點確定服務(wù)支持。at組的attable包含當(dāng)前活動的IPv4節(jié)點和他們相應(yīng)的MAC地址。IP組的iproutetable是發(fā)現(xiàn)網(wǎng)絡(luò)層拓撲的關(guān)鍵所在。具體來說，iproutenexthop值是路徑上下一個路由器的目的地，可通過iproutedest和iproutemask來確定。

類似于MIB-II，生成IPv6網(wǎng)絡(luò)層拓撲需要IPv6 MIB。ip6routedest，ipv6routepfxlength，ip6nexthop在ip6routetable的作用類似于iproutedest，iproutemask，iproutenexthop在iproutetable中對應(yīng)的作用。此外，管理器可以從ipv6nettomediatable中得出IPv6地址和MAC地址之間的映射。

子網(wǎng)中的交換機和網(wǎng)橋其工作方式是基于設(shè)備的物理地址進行的，對于三層拓撲發(fā)現(xiàn)是透明的，所以處于數(shù)據(jù)鏈路層的網(wǎng)絡(luò)設(shè)備的發(fā)現(xiàn)原理是依據(jù)地址轉(zhuǎn)發(fā)表來收集拓撲信息的。Bridge MIB記錄鏈路層的管理信息。在dot1dtpfdbtable表中，Dot1dTpFdbAddress表示物理地址，dot1dTpFdbPort表示源數(shù)據(jù)幀主機通信的端口，dot1dTpFdbStatus表式端口狀態(tài)，這些都是數(shù)據(jù)鏈路拓撲發(fā)現(xiàn)的重要部分。

2.2 Internet控制消息協(xié)議（ICMP）

相對于SNMP MIB對管理信息的作用，ICMP則便于找出當(dāng)前網(wǎng)絡(luò)主機的狀態(tài)。icmpv4一般用來檢測IPv4的主機的活動與否。事實上，所有當(dāng)前活動的主機會在接到來自一個主機發(fā)出的icmpv4響應(yīng)請求后，都會發(fā)出對應(yīng)的icmpv4響應(yīng)應(yīng)答消息。在IPv6中，icmpv6響應(yīng)請求和響應(yīng)應(yīng)答報文類似于icmpv4中的。唯一不同的是，廣播在IPv6是不允許的。取而代之的是在整個管理域中使用多播icmpv6報文。具體來說，向被管理的主機發(fā)送逆鄰居發(fā)現(xiàn)報文，無論該地址是否屬于管理范圍，所有獲得這個報文的活動主機都會回應(yīng)IPv6地址。通過對icmpv4和icmpv6的使用，就可收集所有相關(guān)的IP地址。

3 網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的算法

在下文中，將設(shè)計包括Ipv6網(wǎng)絡(luò)層，Ipv4網(wǎng)絡(luò)層，鏈路層，以及混合網(wǎng)絡(luò)轉(zhuǎn)換方式在內(nèi)的4種算法來進行各個方面網(wǎng)絡(luò)拓撲發(fā)現(xiàn)。

3.1 Ipv6網(wǎng)絡(luò)層拓撲發(fā)現(xiàn)

IPv6網(wǎng)絡(luò) 層拓撲發(fā)現(xiàn)的方法類似于樹狀結(jié)構(gòu)的廣度優(yōu)先搜索，通過檢查所有路徑的路由表來發(fā)現(xiàn)所有能到達的路由器。首先，把算法執(zhí)行主機的第一個網(wǎng)關(guān)作為一個出發(fā)點，通過檢查ip6RouteTable來發(fā)現(xiàn)所有鄰近路由器，然后，在新發(fā)現(xiàn)的路由器重復(fù)上述過程，直到?jīng)]有發(fā)現(xiàn)新的路由器。執(zhí)行期間，該算法維持一個名為IP6_TOPO的鏈表，來存儲可到達的路由器信息以及其鄰近路由器的信息。圖1說明了IP6_TOPO的數(shù)據(jù)結(jié)構(gòu)，從一個已知的路由器開始，他全部的鄰接路由器通過adj指針連接，所有檢測到的路由器通過router指針一個接一個地添加。也就是說，IP6_TOPO每一行記錄頭部路由器相連接的所有鄰近路由器，并且每行的頭部存儲路由器的IP地址。INSERT-ROUTER和INSERT-ADJ，用于增加新發(fā)現(xiàn)路由器。該算法的主體如下所示：

1 IP6_TOPO = NULL

2 LIST_ROUTER = NULL

3 QUEUE_IP6_ADDR = NULL

4 ENQUEUE( QUEUE_IP6_ADDR ， IPv6 address of a local gateway )

5 while QUEUE_IP6_ADDR ≠ NULL

6 do IP6_ADDR = DEQUEUE( QUEUE_IP6_ADDR )

7 INSERT-ROUTER( IP6_TOPO ， IP6_ADDR)

8 LIST_ROUTER← LIST_ROUTER ∪ IP6_ADDR

9 for each ROUTER _ADDR ∈ ip6RouteTable in router IP6_ADDR

10 do INSERT-ADJ(IP6_TOPO ， ROUTER _ADDR)

11 if ROUTER _IP6_ADDR !∈LIST_ROUTER

12 then ENQUEUE( QUEUE_IP6_ADDR ， ROUTER _ADDR )

在這個算法中，LIST_ROUTER保存所有探測到的路由器， QUEUE_IP6_ADDR是一個發(fā)現(xiàn)的路由器隊列。在第4行中，所有網(wǎng)關(guān)的IPv6地址都插入到QUEUE_IP6_ADDR ，它存儲所發(fā)現(xiàn)路由器的IPv6地址。5到12行循環(huán)處理從QUEUE_IP6_ADDR中提取的一個路由器所有鄰接的路由器。探測到所有可達路由器后循環(huán)將停止。6-8行是從QUEUE_IP6_ADDR提取路由器信息，并存儲這個路由器的IPv6地址到IP6_TOPO和LIST_ROUTER 。9-12行是處理所有鄰接路由器的一個循環(huán)。一旦算法完成后， IP6_TOPO包含IPv6網(wǎng)絡(luò)拓撲結(jié)構(gòu)必要的信息。

3.2 Ipv4網(wǎng)絡(luò)層拓撲發(fā)現(xiàn)

類似于IP6_TOPO，IP4_TOPO保存發(fā)現(xiàn)了的IPv4路由器所有必要的數(shù)據(jù)。兩個數(shù)據(jù)結(jié)構(gòu)也類似，IP4_TOPO和IP6_TOPO之間的差異在目標(biāo)MIB的使用方式不同。在算法中除了將IP6_ADDR更換為IP4_ADDR，唯一的變化在第9行中使用ipRouteTable ，而不是ip6RouteTable 。采用此算法，可以得到IP4_TOPO結(jié)構(gòu)，從而建造IPv4的網(wǎng)絡(luò)層拓撲。

3.3 鏈路層拓撲發(fā)現(xiàn)

鏈路層拓撲發(fā)現(xiàn)的算法可分為兩部分：每個交換機直接相連主機的探測，和交換機之間的連接結(jié)構(gòu)。為了發(fā)現(xiàn)所有鄰接的主機，我們首先計算dot1dTpFdbTable中dot1dTpFdbPort的每個獨特值得發(fā)生出現(xiàn)次數(shù)。dot1dTpFdbPort的每個值對應(yīng)設(shè)備的一個物理端口。如果一個值在dot1dTpFdbPort列中僅出現(xiàn)一次，那么僅有一臺主機連接到相應(yīng)的端口。否則，就有多重IP的主機通過一個或多個交換機連接到這個端口。算法的第一部分說明了每個交換機連接的所有交換機和所有主機。通常我們把一個以太網(wǎng)IP網(wǎng)絡(luò)視為一個有著根，節(jié)點和連接邊的樹，對應(yīng)于網(wǎng)關(guān)，主機以及對應(yīng)的內(nèi)部連接。我們采取了一個自上而下的方法來建立交換機之間的連接關(guān)系。從一個位于葉子節(jié)點的指定交換機開始，dot1dTpFdbTable表的dot1dTpFdbAddress列包含主機的MAC地址，而不是交換機的，我們向上查找它上層的交換機，或者稱為父交換機。直到根交換機被刪除才執(zhí)行結(jié)束，從而就發(fā)現(xiàn)了交換機間的連接。

在算法的執(zhí)行過程中，涉及到LINK_TOPO 和 SWITCH_TOPO兩個數(shù)據(jù)結(jié)構(gòu)，LINK_TOPO保存所有交換機直接連接的主機，SWITCH_TOPO則記錄所有交換機之間的連接狀態(tài)。圖2說明了LINK_TOPO 的數(shù)據(jù)結(jié)構(gòu)，SWITCH_TOPO的結(jié)構(gòu)類似于LINK_TOPO，除了將att替換為lnk，LINK_TOPO每一行的頭存儲一個已經(jīng)發(fā)現(xiàn)交換機的MAC地址。所有直接相連的主機通過att指針來連接，被檢測的交換機則由switch指針連接。在SWITCH_TOPO中，只記錄交換機的MAC地址。INSERT-SWITCH，INSERT-ATTACH， 和 INSERT-LEAF這三個函數(shù)分別用于插入一個新的交換機（在 LINK_TOPO 和SWITCH_TOPO中），一個直接相連的主機（在LINK_TOPO中），和一個孩子交換機（在SWITCH_TOPO中）。

LINK-TOPO在鏈路層拓撲結(jié)構(gòu)的應(yīng)用算法可以描述如下：

1 LINK_TOPO = NULL

2 SWITCH_TOPO = NULL

3 QUEUE1_SWITCH = NULL

4 QUEUE2_SWITCH = NULL

5 LIST_SWITCH = NULL

6 LIST_LEAF = NULL

7 ENQUEUE( QUEUE1_SWITCH ， MAC address of gateway)

8 ENQUEUE( QUEUE2_SWITCH ， MAC address of gateway)

9 while QUEUE1_SWITCH ≠ NULL

10 do MAC_ADDR = DEQUEUE( QUEUE1_SWITCH )

11 INSERT-SWITCH( LINK_TOPO ， MAC_ADDR )

12 INSERT-SWITCH( SWITCH_TOPO ， MAC_ADDR )

13 for each HOST_ ADDR∈ dot1dTpFdbTable in MAC_ADDR

14 do if HOST_ ADDR is switch and!∈ LIST_SWITCH

15 then ENQUEUE( QUEUE1_SWITCH ， HOST_ ADDR )

16 ENQUEUE( QUEUE2_SWITCH ， HOST_ ADDR )

17 LIST_SWITCH = LIST_ SWITCH ∪ HOST_ ADDR

18 else if the value of dot1dTpFdbPort in HOST_MAC_ADDR is unique

19 then INSERT-ATTACH( LINK_TOPO ， HOST_ ADDR )

20 while QUEUE2_SWITCH ≠ NULL

21 do MAC_ADDR = DEQUEUE( QUEUE2_SWITCH )

22 if all SWITCH_ ADDR in dot1dTpFdbTable in MAC_ADDR!∈ LIST_SWITCH

23 then LIST_SWITCH = LIST_SWITCH － MAC_ADDR

24 LIST_LEAT = LIST_LEAF ∪ MAC_ADDR

25 else if all SWITCH_ ADDR in dot1dTpFdbTable in MAC_ADDR ∈ LIST_LEAF

26 then INSERT-LEAF( SWITCH_TOPO ， all SWITCH_ ADDR )

27 LIST_LEAF = LIST_LEAF－ all SWITCH_ ADDR

28 else ENQUEUE( QUEUE2_SWITCH ， MAC_ADDR )

在此算法中，QUEUE1_SWITCH 和QUEUE2_SWITCH是進行處理的迭代交換機隊列，LIST_SWITCH包含所有已經(jīng)發(fā)現(xiàn)的交換機。網(wǎng)關(guān)的MAC地址一旦插入到QUEUE1_SWITCH 和 QUEUE2_SWITCH，則9到19行的while循環(huán)用來檢測每一個交換機所有的直接連接主機。dot1dTpFdbTable的dot1dTpFdbPort 同樣值的數(shù)量反應(yīng)了連接這一端口的主機數(shù)量，如果該值是獨一無二的，它表明只有一臺主機連接到端口。檢測完所有發(fā)現(xiàn)交換機后循環(huán)停止，主機和交換機的連接信息保存在LINK_TOPO。處于20到28行的while循環(huán)是用來建立所有交換機之間的連接。22到24行是如果交換機是樹上的葉子節(jié)點就刪除交換機。25到27行處理所有交換機葉節(jié)點。如果交換機的狀態(tài)仍然未知，它將被再次插入到QUEUE2_SWITCH。這個循環(huán)當(dāng)所有交換機被訪問時結(jié)束，從而連接狀態(tài)儲存在SWITCH_TOPO 中。結(jié)合LINK_TOPO和SWITCH_TOPO 兩個數(shù)據(jù)結(jié)構(gòu)，就可以提出一個鏈路層拓撲。

3.4 轉(zhuǎn)換方式發(fā)現(xiàn)

為了結(jié)合IPv6與IPv4網(wǎng)絡(luò)層拓撲圖，應(yīng)該首先發(fā)現(xiàn)雙重地址主機或路由器。因此，一個檢測IPv6轉(zhuǎn)換方式的算法是必要的。通過多播IPv6的逆鄰居發(fā)現(xiàn)報文和廣播IPv4的 RARP報文，分析應(yīng)答消息可以獲得所有與MAC地址對應(yīng)的IP地址。通過分析收集到的所有IP地址的格式，就可以建立MAC地址和其相關(guān)IP地址的對應(yīng)關(guān)系。執(zhí)行期間，該算法有個名為 MAC_IP的連接鏈表，用于儲存所有IP地址相應(yīng)的MAC地址。圖3說明了MAC_IP的數(shù)據(jù)結(jié)構(gòu)，每行的頭節(jié)點存儲了一個處理范圍內(nèi)的MAC地址。如圖3所示，所有與此MAC相關(guān)的IP地址都通過IP指針連接 ，而所有MAC地址通過每個節(jié)點的mac指針連接，INSERT-MAC 和 INSERT-IP函數(shù)是分別用來增加的一個新的MAC地址和IP地址。

TRANS_DET算法，使用MAC_IP結(jié)構(gòu)，以確定使用哪個轉(zhuǎn)換機制，如下:

1 MAC_IP=NIL

2 QUEUE_MAC = NULL

3 Broadcasting ICMPv4 echo request

4 for each MAC_ADDR in atTable of gateway

5 ENQUEUE( QUEUE_MAC ， MAC_ADDR )

6 while QUEUE_MAC ≠ NULL

7 do MAC_ADDR = DEQUEUE( QUEUE_MAC )

8 INSERT-MAC( MAC_IP ， MAC_ ADDR )

9 Multicasting IPv6 Inverse Neighbor Solicitation message

10 Broadcasting IPv4 RARP requests

11 for each replied message

12 do INSERT-IP( MAC_IP ， all IP addresses in replied message )

首先，MAC_IP數(shù)據(jù)結(jié)構(gòu)和QUEUE_MAC隊列中在TRANS-DET算法里初始化。QUEUE_MAC維持所有從最初網(wǎng)關(guān)中atTable獲得的MAC地址。唯一的while循環(huán)檢查所有存儲在QUEUE_MAC隊列的MAC地址。第7行將MAC插入到MAC_IP中，8到9行發(fā)送IPv6逆鄰居請求消息和IPv4的RARP請求消息。檢測應(yīng)答消息，獲得所有后來插入到MAC_IP的IP地址。通過分析主機的IP地址，來建立MAC地址和IP地址的轉(zhuǎn)換方式。因此，無論路由器或主機， IPv6與IPv4網(wǎng)絡(luò)的重疊部分都將被發(fā)現(xiàn)。從而，就可以得出IPv6與IPv4網(wǎng)絡(luò)的拓撲共存圖。

4 小結(jié)

本文主要論述了網(wǎng)管系統(tǒng)中一個重要部分：網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的算法研究。提出IPv6-only和 IPv4-only的網(wǎng)絡(luò)層拓撲發(fā)現(xiàn)算法，一個數(shù)據(jù)鏈路層拓撲發(fā)現(xiàn)算法以及一個在共存的網(wǎng)絡(luò)中的轉(zhuǎn)換探測算法。網(wǎng)絡(luò)層拓撲構(gòu)造使用ip6routetable和iproutetable中的路由信息，而數(shù)據(jù)鏈路層采用atTable和dot1dtpfdbtable中數(shù)據(jù)來創(chuàng)建。轉(zhuǎn)換探測通過收集和分析兩個IP版本整個IP地址來實施，在其中通過使用逆ipv6多播鄰居發(fā)現(xiàn)報文和ipv4 RARP的廣播報文。來找出在共存網(wǎng)絡(luò)部署哪種轉(zhuǎn)換方式。因此，路由器和主機的重疊可以判定來完成IP網(wǎng)絡(luò)拓撲發(fā)現(xiàn)。

參考文獻：

[1] 汪浩，張堯弼，馬月玲.以太網(wǎng)物理拓撲發(fā)現(xiàn)算法[J].微型電腦應(yīng)用，2007，23(5).

[2] Spring N，Mahajan R，Wetherall D，et al.Measuring ISP topologies Rocketfuel[J].IEEE/ACM Transactions on Networking，2004，12(1):2-16.

[3] Breitbart Y，Garofalakis M，Jai B，et al.Topology discovery in heterogeneous IP networks: the NetInventory system[J]. IEEE/ACM Transactions on Networking，2004，12(3):401-414.

[4] Astic I，F(xiàn)estorO.A hierarchical topology discovery service for IPv6 networks[J].Network Operations and Management Symposium，2002:497-510.

[5] IPv6 Network Topology Discovery System -Dolphin[EB/OL].http://www.nlsde.buaa.edu.cn/ipv6/210.25.133.26/default.php.

[6] 王志剛，王汝傳，王紹棣，等.網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法的研究[J].通信學(xué)報，2004，25(8):36-43.

[7] 熊坤，寇曉蕤，范元書，等.網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法定性分析[J].計算機工程與應(yīng)用，2004(14):136-137.

[8] 黃曉波，潘雪增.網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的算法和實現(xiàn)[J].計算機應(yīng)用與軟件，2007(7):159-161.