廖飛，龍永新，鐘海

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

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

廖飛，龍永新，鐘海

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

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

網絡拓撲發(fā)現(xiàn)；互聯(lián)網技術；NetMagic

0 引言

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

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

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

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

1 SDN原理介紹

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

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

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

2 網絡拓撲發(fā)現(xiàn)算法設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）根據算法設計，需要定義2類報文，并將NMAC命令進行以太網報文封裝。報文定義和封裝格式如下。

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

探測報文在以太網報文中的封裝格式見圖3。

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

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

響應報文在以太網報文中的封裝格式見圖4。

圖4 響應報文封裝格式Fig.4The response packet message encapsulation format

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

3 仿真分析

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

3.1 仿真方案設計

仿真方案如下。

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

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

3）響應機制。

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

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

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

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

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

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

3.2 仿真結果與分析

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

圖5 拓撲結構圖Fig.5The topology diagram

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

圖6 仿真結果過程圖Fig.6The simulation results

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

圖7 拓撲結構圖aFig.7The topological diagram a

圖8 拓撲結構圖bFig.8The topological diagram b

圖9 拓撲結構圖cFig.9The topological diagram c

4 結語

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

[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]張鈞，黃亞樓. 第二代因特網（Internet2）的技術與發(fā)展[J]. 計算機應用，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)網實驗平臺[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]王志剛，王汝傳，王紹棣，等. 網絡拓撲發(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]楊國正，陸余良，夏陽. 計算機網絡拓撲發(fā)現(xiàn)技術研究[J]. 計算機工程與設計，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è)大學碩士生，主要研究方向為網絡嵌入式系統(tǒng)，E-mail：loveuliaofei@126.com

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