廖飛，龍永新，鐘海

（湖南工業(yè)大學計算機與通信學院，湖南株洲412007）

一種基于NetMagic的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法

廖飛，龍永新，鐘海

（湖南工業(yè)大學計算機與通信學院，湖南株洲412007）

對NetMagic網(wǎng)絡(luò)實驗平臺進行研究，提出了一種基于NetMagic的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法。介紹了網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法原理，定義探測和響應(yīng)報文在以太網(wǎng)幀中的封裝格式，在簡單拓撲和復雜拓撲情況下對本算法進行仿真實驗。仿真實驗驗證了算法的邏輯可行性和有效性。

網(wǎng)絡(luò)拓撲發(fā)現(xiàn)；互聯(lián)網(wǎng)技術(shù)；NetMagic

0 引言

隨著新型網(wǎng)絡(luò)技術(shù)研究的爆炸式發(fā)展，現(xiàn)有網(wǎng)絡(luò)實驗平臺的局限性越來越突出。一直以來，路由器和高性能交換機的生產(chǎn)技術(shù)是“思科”“華為”“中興”等國內(nèi)外大型通信企業(yè)的核心技術(shù)，其系統(tǒng)內(nèi)部結(jié)構(gòu)和處理流程一般不對外公開。商業(yè)網(wǎng)絡(luò)設(shè)備廠商因考慮自身利益而導致的封閉性，已成為網(wǎng)絡(luò)技術(shù)創(chuàng)新和發(fā)展的最大障礙。

互聯(lián)網(wǎng)科學作為一門以實驗為基礎(chǔ)的科學，是在真實的網(wǎng)絡(luò)環(huán)境中進行實驗并收集數(shù)據(jù)，是進行網(wǎng)絡(luò)技術(shù)研究和創(chuàng)新最有效和最具說服力的手段。實驗驗證是互聯(lián)網(wǎng)研究的基本方法，而現(xiàn)有網(wǎng)絡(luò)和實驗平臺缺乏靈活的實驗機制。因此，現(xiàn)有互聯(lián)網(wǎng)技術(shù)的演進和新一代互聯(lián)網(wǎng)技術(shù)的研究創(chuàng)新，都需要一個開放和靈活的實驗驗證平臺。

NetMagic[1-2]是近年來推出的面向網(wǎng)絡(luò)技術(shù)研究和教學的一種可編程創(chuàng)新實驗平臺。因其具有靈活性強、可重構(gòu)等特性，使得基于NetMagic的開發(fā)和研究日益受到廣泛關(guān)注。其可適用于很多領(lǐng)域，如網(wǎng)絡(luò)教學、專用網(wǎng)絡(luò)建設(shè)、網(wǎng)絡(luò)科研等。NetMagic實驗平臺采用的是新型部分可編程交換機體系結(jié)構(gòu)技術(shù)，將商用以太網(wǎng)交換芯片和大容量FPGA（fieldprogrammable gate array）有機結(jié)合，能提供高端口密度下報文線速交換轉(zhuǎn)發(fā)能力和豐富的工作模式配置，有效支持用戶自定義報文處理邏輯集成。而軟件定義網(wǎng)絡(luò)（software define networking，SDN）是Emulex一種新型網(wǎng)絡(luò)創(chuàng)新架構(gòu)。其核心技術(shù)是將網(wǎng)絡(luò)設(shè)備控制面與數(shù)據(jù)面分離，從而實現(xiàn)了網(wǎng)絡(luò)流量的靈活控制，為核心網(wǎng)絡(luò)及應(yīng)用的創(chuàng)新提供了良好的平臺。

網(wǎng)絡(luò)拓撲發(fā)現(xiàn)是互聯(lián)網(wǎng)技術(shù)研究的核心內(nèi)容之一。網(wǎng)絡(luò)拓撲發(fā)現(xiàn)是指通過網(wǎng)絡(luò)中各元素（路由器、交換機、網(wǎng)關(guān)和終端主機等）和通信線路確定網(wǎng)絡(luò)元素之間的互連關(guān)系。因此，針對小規(guī)模局域網(wǎng)，本文對NetMagic網(wǎng)絡(luò)實驗平臺進行研究，提出了一種基于NetMagic的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法。本文以軟件定義網(wǎng)絡(luò)思想的控制和轉(zhuǎn)發(fā)分離架構(gòu)的設(shè)計理念為基礎(chǔ)，設(shè)計算法。通過對兩種拓撲結(jié)構(gòu)的仿真實驗，驗證了本算法的邏輯可行性和有效性。

1 SDN原理介紹

軟件定義網(wǎng)絡(luò)由于能支持新型網(wǎng)絡(luò)協(xié)議和新型網(wǎng)絡(luò)體系結(jié)構(gòu)，而得到廣泛發(fā)展[3]。在學術(shù)界，美國GENI、Internet2[4]、歐洲OFELIA和日本的JGN2plus[5]先后開展了對SDN的研究和部署，IETF（internet engineering task force）, ITU（international telecommunication union）, ETSI（european telecommunications standards institute）等標準組織也開始關(guān)注SDN，討論SDN在各自領(lǐng)域可能的發(fā)展場景和架構(gòu)應(yīng)用。

圖1為軟件定義網(wǎng)絡(luò)原理圖。圖中，網(wǎng)絡(luò)控制平面與數(shù)據(jù)轉(zhuǎn)發(fā)平面相分離。網(wǎng)絡(luò)控制邏輯和狀態(tài)被轉(zhuǎn)移到一個集中控制器上，因此，網(wǎng)絡(luò)控制平面（SDN控制器）能以一個全局網(wǎng)絡(luò)的視野去管理和控制網(wǎng)絡(luò)。數(shù)據(jù)轉(zhuǎn)發(fā)平面（SDN交換機）只專注于報文的轉(zhuǎn)發(fā)。SDN控制器通過配置SDN交換機中的規(guī)則表來控制交換機的行為，和SDN交換機之間通過特定的通信協(xié)議傳遞消息。也就是說，SDN控制器相當于人的大腦，SDN交換機類似于人的手腳和肌肉，整個思想活動全由SDN控制器控制，SDN交換機根據(jù)SDN控制器下發(fā)的特定指令執(zhí)行相應(yīng)的動作行為，其行為完全是傻瓜式的狀態(tài)[6-7]。

本文所提算法就是采用上述思想。通過SDN控制器來定義SDN交換機的存儲和行為。在網(wǎng)絡(luò)拓撲發(fā)現(xiàn)過程中，只需對NetMagic平臺內(nèi)部的FPGA編程，將其配置成SDN交換機即可（如何通過FPGA編程將硬件配置成SDN交換機在此不詳細講述）。

2 網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法設(shè)計

網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法中的探測過程采用主動探測，發(fā)現(xiàn)過程工作在數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層之上。主動探測是指探測節(jié)點為獲取拓撲信息主動向網(wǎng)絡(luò)中發(fā)送路徑探測包，并通過收集到的返回信息，分析網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，最終形成網(wǎng)絡(luò)拓撲。對于小規(guī)模局域網(wǎng)來說，一般是數(shù)據(jù)鏈路層的拓撲發(fā)現(xiàn)。其主要利用ARP（address resolution protocol）協(xié)議。本課題組采用自主開發(fā)的一套NMAC（NetMagic access and control protocol）協(xié)議，將探測信息封裝在以太網(wǎng)幀中，而后在軟硬件之間進行通信。

本文以SDN思想的控制和轉(zhuǎn)發(fā)分離架構(gòu)的設(shè)計理念為基礎(chǔ)來設(shè)計算法。以圖2所示的實驗環(huán)境為例，對算法進行描述。本實驗共有3臺PC機和4臺NetMagic網(wǎng)絡(luò)實驗平臺。1臺PC機充當SDN控制器，主要功能為向NetMagic下發(fā)拓撲探測報文、處理生成的響應(yīng)報文和生成網(wǎng)絡(luò)拓撲結(jié)構(gòu)。另外2臺PC機作為連接在網(wǎng)絡(luò)中的終端設(shè)備，目的在于模擬網(wǎng)絡(luò)中的真實環(huán)境，其是否接入網(wǎng)絡(luò)環(huán)境，不影響整個實驗過程。通過硬件邏輯設(shè)計，將4臺NetMagic配置成SDN交換機，其對控制器下發(fā)的拓撲探測報文進行處理，每個交換機的功能和行為完全相同。

圖2 網(wǎng)絡(luò)拓撲發(fā)現(xiàn)實驗環(huán)境Fig.2The network topology discovery experiment environment

網(wǎng)絡(luò)運行時，SDN交換機以報文轉(zhuǎn)發(fā)為基礎(chǔ)，內(nèi)部并不含CPU，不運行任何操作系統(tǒng)。對于網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的應(yīng)用，還需要一臺外部主機對NetMagic的FPGA進行編程配置。外部主機利用自主開發(fā)的NMAC協(xié)議，通過以太網(wǎng)報文的形式傳到NetMagicFPGA的管理配置接口，然后由NetMagicFPGA對這些命令和配置報文進行解析，改變NetMagic的轉(zhuǎn)發(fā)行為。

網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法的具體流程如下：

1）網(wǎng)絡(luò)拓撲發(fā)現(xiàn)開始。SDN控制器首先向1號交換機發(fā)出跳數(shù)為0的拓撲探測報文，1號交換機收到跳數(shù)為0的探測報文后，生成響應(yīng)報文并返回至控制器。

2）根據(jù)返回報文，SDN控制器配置目的Mac地址表，并將其發(fā)送給1號交換機。

3）SDN控制器發(fā)送一個跳數(shù)為1的拓撲探測報文，1號交換機發(fā)現(xiàn)報文的跳數(shù)為1，將該報文跳數(shù)減1并附上自己本機ID號和輸出端口號后廣播。

4）交換機2號、3號收到跳數(shù)為0的報文，生成響應(yīng)報文并返回至控制器。SDN控制器收到2號、3號交換機的返回報文，將配置目的Mac地址表發(fā)送至2號、3號交換機。

5）SDN控制器發(fā)送一個跳數(shù)為2的拓撲探測報文，1號交換機判斷報文跳數(shù)為2，對報文跳數(shù)減1后直接進行廣播轉(zhuǎn)發(fā)；2號、3號交換機收到跳數(shù)為1的報文，其發(fā)現(xiàn)報文跳數(shù)為1，將報文跳數(shù)減1并附上自己本機ID號及輸出端口號后廣播。

6）交換機4號收到跳數(shù)為0的報文，將響應(yīng)報文返回至SDN控制器。SDN控制器收到4號交換機的返回報文后，將配置目的Mac地址表發(fā)送至4號交換機。

7）SDN控制器再發(fā)送一個跳數(shù)為3的拓撲探測報文。各交換機重復上述工作，最后控制器發(fā)現(xiàn)沒有返回的響應(yīng)報文，整個網(wǎng)絡(luò)拓撲發(fā)現(xiàn)過程結(jié)束。

下面對本算法作如下幾點說明：

1）廣播是指向連接交換機的所有活躍端口發(fā)送報文（接收到此報文的輸入端口除外，活躍端口指的是已經(jīng)連通且能夠通信的端口）。

2）根據(jù)算法設(shè)計，需要定義2類報文，并將NMAC命令進行以太網(wǎng)報文封裝。報文定義和封裝格式如下。

定義1拓撲探測報文是目的Mac地址全為1，Type類型為0x09，協(xié)議號為253的NMAC報文。

探測報文在以太網(wǎng)報文中的封裝格式見圖3。

圖3 探測報文封裝格式Fig.3The detecting packet message encapsulation format

定義2響應(yīng)報文是攜帶本機ID號，Type類型為0x10，port為收到跳數(shù)為0的輸入端口號，F(xiàn)lag為SDN交換機是否連接其它設(shè)備標識的NMAC報文。

響應(yīng)報文在以太網(wǎng)報文中的封裝格式見圖4。

圖4 響應(yīng)報文封裝格式Fig.4The response packet message encapsulation format

在圖3和圖4中，加顏色部分為NMAC報文，規(guī)定NMAC協(xié)議號為253，從圖中可以看出每個字段的位寬。

3 仿真分析

Jade（Java agent development framework）是一種人工智能，其agent可以用來模擬交換機之間的邏輯關(guān)系。為論證本拓撲發(fā)現(xiàn)算法的邏輯可行性和有效性，利用Java語言構(gòu)造了不同的拓撲關(guān)系進行仿真測試。

3.1 仿真方案設(shè)計

仿真方案如下。

1）交換機的功能有：記錄探測報文從“父節(jié)點”（上一個節(jié)點）進來的端口號（一般為1號端口）；當接收到跳數(shù)為0的探測報文時，發(fā)出響應(yīng)報文。

2）初始化。初始化交換機的的層數(shù)為一個充分大的值（如256）。若收到的探測報文中的Req_Seq/ Ack_Seq域的值小于自己當前的層數(shù)，則更新交換機的層數(shù)，并記錄報文進入的端口號， 該端口將作為自己通往“父節(jié)點”的端口。

3）響應(yīng)機制。

①當交換機收到的探測報文跳數(shù)大于1時，將跳數(shù)減1，然后向所有活躍端口（除了收到報文的端口）轉(zhuǎn)發(fā)報文。

②當交換機收到的探測報文跳數(shù)等于1時，構(gòu)造新的探測報文，將本交換機的ID號和Port端口號添加到新的探測報文當中，并將跳數(shù)減1，然后向所有活躍端口（除了收到報文的端口）轉(zhuǎn)發(fā)出報文。

③當交換機收到的探測報文跳數(shù)等于0時，分為3種情況：

情況一Req_Seq/Ack_Seq中的值大于自己當前層數(shù)，則層數(shù)加1，丟棄報文；否則跳轉(zhuǎn)到情況二。

情況二構(gòu)造響應(yīng)報文。將收到的報文添加Dest_ID號和Dest_Port端口號，并將自己的ID號和收到報文的端口號分別寫入Src_ID和Src_Port中，然后將響應(yīng)報文轉(zhuǎn)發(fā)給“父節(jié)點”。

情況三當收到的報文為響應(yīng)報文，直接向“父節(jié)點”轉(zhuǎn)發(fā)，直到返回給控制器。

3.2 仿真結(jié)果與分析

為了驗證了所提算法的邏輯可行性和有效性，本文進行了2組測試實驗，即算法在簡單拓撲結(jié)構(gòu)和復雜拓撲結(jié)構(gòu)下的運行情況。簡單的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖如圖5所示。通過Java語言編寫算法程序，從各個節(jié)點收集拓撲信息，歸類整理，再調(diào)用畫圖軟件繪出拓撲結(jié)構(gòu)圖。從圖5可以看出，算法仿真得到的拓撲結(jié)構(gòu)圖和本文真實的實驗環(huán)境完全相同。

圖5 拓撲結(jié)構(gòu)圖Fig.5The topology diagram

圖6是圖5的仿真結(jié)果過程圖。虛擬機軟件VMware平臺上有個sniffer可以進行全局抓包，能夠看到控制器與各個交換機之間的報文交換過程。從圖中可以看出，報文交換過程完全與本文算法預期的報文發(fā)送過程一樣。該仿真結(jié)果驗證了所提算法的邏輯可行性和有效性。

圖6 仿真結(jié)果過程圖Fig.6The simulation results

圖7～9是3種復雜情況下的拓撲結(jié)構(gòu)圖。從3個拓撲結(jié)構(gòu)中都可以得到本機ID號、本機連父的端口號、父ID號和父連本機的端口號這些關(guān)鍵的拓撲信息，通過這些信息可以獲得全網(wǎng)交換機和控制主機的拓撲圖。進一步驗證了所提算法的邏輯可行性和有效性。

圖7 拓撲結(jié)構(gòu)圖aFig.7The topological diagram a

圖8 拓撲結(jié)構(gòu)圖bFig.8The topological diagram b

圖9 拓撲結(jié)構(gòu)圖cFig.9The topological diagram c

4 結(jié)語

本文以SDN思想的控制和轉(zhuǎn)發(fā)分離架構(gòu)的設(shè)計理念為基礎(chǔ)，提出了一種新型的基于NetMagic的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法。先對算法進行了描述，定義了探測和響應(yīng)報文在以太網(wǎng)幀中的封裝格式，并通過軟件對算法進行仿真實驗，驗證了所提算法的邏輯可行性和有效性。實驗結(jié)果表明：該算法通過本機ID號、本機連父的端口號、父ID號和父連本機的端口號關(guān)鍵四元組拓撲信息，可以主動探測獲得全網(wǎng)交換機和控制器主機之間的拓撲結(jié)構(gòu)視圖。

[1]Li Tao，Sun Zhigang，Jia Chunbo，et al. Using NetMagic to Observe Fine-Grained Per-Flow Latency Measurements [C]//Proceedings of the ACM SIGCOMM 2011. Toronto：ACM，2011：466-467.

[2]Naous J，Gibb G，Bolouki S，et al. NetFPGA：Reusable Router Architecture for Experimental Research[C]// Proceedings of the ACM Workshop on Programmable Routers for Extensible Services of Tomorrow (PRESTO’08). Seattle：ACM，2008：1-7.

[3]Nascimento M R，Rothenberg C E，Salvador M R，et al. Virtual Routers as a Service：The RouteFlow Approach Leveraging Software-Defined Networks[C]//Proceedings of the 6th International Conference on Future Internet Technologies(CFI). Seoul：ACM ，2011：34-37.

[4]張鈞，黃亞樓. 第二代因特網(wǎng)（Internet2）的技術(shù)與發(fā)展[J]. 計算機應(yīng)用，1999，19(12)：22-24. Zhang Jun，Huang Yalou. The Technique and Development of Internet2[J]. Computer Applications，1999，19(12)：22-24.

[5]梁學軍，林昭文，馬嚴. 未來互聯(lián)網(wǎng)實驗平臺[J]. 計算機學報，2013，36(7)：1365-1366. Liang Junxue，Lin Zhaowen，Ma Yan. Future Internet Experiment Platform[J]. Chinese Journal of Computers，2013，36(7)：1365-1366.

[6]王志剛，王汝傳，王紹棣，等. 網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法的研究[J]. 通信學報，2004，25(8)：36-43. Wang Zhigang，Wang Ruchuan，Wang Shaodi，et al. Research on Network Topology Discovery Algorithm[J]. Journal on Communications，2004，25(8)：36-43.

[7]楊國正，陸余良，夏陽. 計算機網(wǎng)絡(luò)拓撲發(fā)現(xiàn)技術(shù)研究[J]. 計算機工程與設(shè)計，2006，27(24)：4710-4712. Yang Guozheng，Lu Yuliang，Xia Yang. Research on Computer Network Topology Discovery Technology[J]. Computer Engineering and Design，2006，27(24)：4710-4712.

（責任編輯：鄧彬）

A Netmagic-Based Network Topology Discovery Algorithm

Liao Fei，Long Yongxin，Zhong Hai
（School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China）

Investigates the NetMagic network experiment platform, and proposes a network topology discovery algorithm based on NetMagic. Describes the principle of network topology discovery algorithm defines the encapsulation format ofdetection and response packets in an Ethernet frame, and simulates the algorithm in the cases of simple topology and complex topology. The simulated result verifies the logic feasibility and effectiveness of the algorithm.

network topology discovery；internet technology；NetMagic

TP393

A

1673-9833(2014)05-0084-05

10.3969/j.issn.1673-9833.2014.05.017

2014-07-20

國家自然科學基金資助項目（61170102，61350011），湖南省自然科學基金資助項目（11JJ3070），湖南省自然科學基金重點課題基金資助項目（12JJ2036），湖南省自然科學面上課題基金資助項目（14JJ2115），湖南省教育廳科研基金資助項目（12A039），湖南工業(yè)大學研究生創(chuàng)新基金資助項目（CX1404）

廖飛（1988-），男，湖南常德人，湖南工業(yè)大學碩士生，主要研究方向為網(wǎng)絡(luò)嵌入式系統(tǒng)，E-mail：loveuliaofei@126.com

龍永新（1966-），男，湖南益陽人，湖南工業(yè)大學副教授，碩士生導師，博士，主要從事智能信息處理和數(shù)字圖像處理方面的教學與研究，E-mail：1525127621@qq.com