軟件定義網絡中一種優化的拓撲發現機制

李蘭英　王敏　朱素霞

摘要： 針對軟件定義網絡中拓撲發現機制存在資源消耗過大，運行效率低等問題，提出一種優化的拓撲發現機制（S-OFDP）。首先基于圖的最小頂點覆蓋思想，采用貪心算法實現網絡拓撲的最少交換機覆蓋，再利用端口分類和哈希策略消除網絡中的冗余數據包。仿真實驗結果表明：與現有的拓撲發現機制相比，S-OFDP機制下，網絡中總LLDP數量的效率增益可達48.66%。因此，S-OFDP能夠有效地減少網絡中LLDP的數量，從而減少資源消耗，降低了控制器的負載。

關鍵詞：

軟件定義網絡;拓撲發現;頂點覆蓋;控制器

DOI：10.15938/j.jhust.2022.04.013

中圖分類號： TP393

文獻標志碼： A

文章編號： 1007-2683（2022）04-0098-09

An Optimized Topology Discovery Mechanism in Software

Defined Networks

LI Lan-ying，WANG Min，ZHU Su-xia

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract：Aiming at the problems of excessive resource consumption and low operating efficiency in the topology discovery mechanism in Software Defined Networks （SDN）， a stronger topology discovery mechanism （S-OFDP） is proposed. First， based on the idea of minimum vertex coverage of the graph， the greedy algorithm is used to achieve the minimum switch coverage of the network topology， and then the port classification and hash strategy are used to eliminate redundant data packets in the network. The simulation results show that compared with the existing topology discovery mechanism， the efficiency gain of the total LLDP in the network under S-OFDP can reach 48.66%. Therefore， S-OFDP can effectively reduce the number of LLDP in the network， so as to reduce resource consumption and reduce the load of the controller.

Keywords：SND（software defined networks）; topology discovery; vertex cover; controller

0引言

軟件定義網絡（software defined networks，SDN）是一種全新的基于軟件的網絡架構和技術，一個重要的特征就是控制平面與數據平面分離[1]。SDN將網絡劃分為三層，最上層是應用層;中間的控制層是整個網絡架構的核心，主要負責各種轉發規則的控制，維護網絡拓撲和狀態信息;最下層是基礎設施層即數據平面，它只根據控制器下發的規則對數據包進行處理和轉發。控制層與基礎設施層之間的接口通常稱為南向接口，OpenFlow是目前主流的南向接口標準之一[2]。SDN簡化了網絡的配置和管理，網絡服務可以簡單地通過運行在控制器上的應用程序來實現[3]，通過安裝適當的規則，控制器能夠管理交換機，實現路由、轉發、防火墻、網絡地址轉換、負載均衡等功能[4]。

與傳統網絡相比，SDN具有控制邏輯集中，開放可編程等優點，拓撲管理更是其不同于傳統網絡的一個重要特征。在SDN中，數據平面與控制平面的解耦使得SDN可以對網絡進行邏輯上的集中控制。為了實現集中控制，控制器應該具有整個網絡的全局視圖。此外，網絡的全局性視圖不僅方便了控制器的集中控制，也便于應用平面的服務使用網絡的可編程性來執行其操作。因而，網絡的拓撲發現對控制平面和應用平面都很重要，它提供了整個網絡設備的抽象可見性[5]。控制器作為核心，不僅要分擔傳統網絡底層設備的控制功能，還要為許多不同的應用提供服務[6]，因此，控制器的負載也成了一個新的問題，拓撲發現機制作為控制層的基礎服務之一，需要一直不斷地運行，因而，拓撲發現機制的優化對減輕控制器的負載有著重要的作用。

SDN拓撲發現機制的優化研究已成為眾多學者研究的熱點。SDN的拓撲發現協議OFDP（openFlow discovery protocol）[7]主要利用傳統網絡中的鏈路層發現協議LLDP（link layer discovery protocol）來實現。在OFDP中，控制器需要對整個數據平面所有交換機的所有端口都發送Packet-Out消息，對于同一條鏈路，控制器需要對鏈路兩端交換機提交的Packet-In消息各解析一次，對于數據中心的一些網絡拓撲如FatTree等類型的網絡拓撲來說，其端口數量是交換機數量的n倍，這就需要控制器生成并發送大量的Packet-Out消息，導致消耗了很多資源，增加了控制器的負載;Azzouni A[8]等提出了 sOFTDP，對于拓撲發現的安全和優化問題進行了討論，并把一部分的控制權限轉移給交換機，以此來減少控制器的負載，但是這導致了控制平面和數據平面的再次耦合，失去了SDN網絡架構的優勢;OFDPv2[9]提供了一種對OFDP的改進機制，利用OpenFlow交換機重寫包頭的能力，修改LLDP pkt消息的源MAC地址，使控制器只需要對每個交換機發送一個Packet-Out消息，因而大大減少了控制器的負載，但對交換機發送給控制器的Packet-In消息沒有作出改進。OCHOA A L 等[10]提出了一種基于代理的簡單機制的分布式算法，以提高拓撲發現過程的效率為目標，設計了一種新的拓撲發現協議，稱為SD-TDP，此協議通過一個軟件代理在每個交換機中實現。由于拓撲發現過程是由支持網絡協議的節點來執行的，這就需要在交換機上安裝協議，不利于網絡的擴展性;程銘鑫[11]將SDN控制器部署在移動自組織網絡中，提出了一種面向無線環境的拓撲發現協議。通過IEEE802.11協議獲取鄰居節點的MAC地址，使用自定義OpenFlow報文將其上報至SDN控制器，再由 SDN控制器統一對發現的鄰居進行處理。該拓撲發現協議不再依靠LLDP，減少了數據層的鏈路負載，同時也減少了SDN控制器的負載。Dana Hasan和Mohamed Othman[12]重現了OFDPv2，考慮了重傳情況下的OFDPv2的性能，實驗結果表明，在重傳情況下，重傳的數據包是所需數據包數量的兩倍，OFDPv2的性能仍然優于OFDP;Suleman Khan[13]等的研究討論了SDN體系結構每一層可能的安全威脅，將傳統網絡和SDN中的拓撲發現協議進行了對比，提出了一個SDN拓撲發現的主題分類方法，并提供了檢測拓撲發現潛在威脅以及SDN最先進的解決方案，還提出了SDN拓撲發現領域的未來挑戰和研究方向;Im-OFDP[14]考慮了Packet-Out消息的更優化，減少了控制平面的Packet-Out消息和Packet-In消息，但在一些不規則拓撲中，該機制仍會重復提交Packet-In數據包，其次，數據平面冗余數據包仍然存在，頂點交換機收到Packet-Out仍需要泛洪到自己的所有活動端口。

綜上，現有的拓撲發現機制沒有充分考慮到數據冗余，仍然存在資源消耗過大、負載過重等問題。本文提出了一種優化的拓撲發現機制S-OFDP，將網絡拓撲抽象為圖，以減少拓撲發現機制運行時網絡中各類LLDP的數量作為優化目標，將拓撲發現機制的優化分為對Packet-Out、數據平面LLDP pkt和Packet-In三類LLDP數據包數量的優化。最后進行了模擬仿真實驗與分析，與已有的拓撲發現機制相比，S-OFDP能夠有效減少網絡中的LLDP的數量，降低控制器的負載。

1S-OFDP

SDN拓撲發現時，控制器和交換機的通信通常分為3個階段，一是控制器按指定時間（默認是5s）周期性地向交換機的端口發送含有LLDP pkt的Packet-Out消息;二是交換機按照安裝好的規則轉發接收到的LLDP pkt;三是交換機將接收到的LLDP pkt處理并封裝在Packet-In中發送給控制器。S-OFDP對通信過程中3種不同的LLDP數據包的數量做了優化處理。

1.1Packet-Out數量的優化

1.2OpenFlow交換機之間LLDP pkt數量的優化

1.3Packet-In數量的優化

1.4S-OFDP機制的詳細步驟

3仿真實驗與結果分析

3.1實驗環境與參數設置

3.2網絡中LLDP的數量

由圖8和表9可以看出，S-OFDP相比于SDN中傳統的OFDP機制和OFDPv2機制，在各個方面的效率增益都很大，相比于Im-OFDP，在Packet-In消息和數據平面LLDP pkt的數量上有明顯的減少，且結合式（2）～（10）可知，在不規則拓撲中，存在以下三種情況：①網絡中頂點交換機的數量遠低于總交換機數量;②網絡中頂點交換機之間存在大量鏈路;③交換機連接了大量主機，S-OFDP拓撲發現機制的效率增益更明顯。綜上，S-OFDP總體上優于現有的拓撲發現機制。

對控制器負載的影響

在SDN網絡中，為了實現可編程的集中式控制[20]，控制器的負載至關重要，它是影響網絡性能的關鍵[21]。本實驗中，獲取拓撲發現機制運行的CPU時間使用默認周期，每5s對拓撲發現服務進行一次更新，控制器不運行其他服務或應用程序，此時的Ryu控制器CPU的負載只由該拓撲發現機制所引起。圖9為運行不同拓撲發現機制下Ryu控制器所消耗的CPU時間。

由圖9可以看出，S-OFDP的累計CPU時間明顯低于其他拓撲發現機制，說明控制器需要處理和發送的信息少，因而所用時間明顯減少，使得控制器的負載有所下降。

4結論

本文在現有研究基礎上，采用了最小頂點覆蓋、端口分類和哈希策略等算法，提出一種新的拓撲發現機制S-OFDP。該拓撲發現機制通過應用最小頂點覆蓋思想減少了控制器需要下發的Packet-Out的數量;利用端口分類，減少了數據平面需要轉發的LLDP pkt的數量;采用哈希策略，消除了鏈路的重復發現，減少了控制器需要分析的Packet-In的數量。仿真實驗結果證明：S-OFDP與現有的拓撲發現機制相比，LLDP的數量明顯減少，控制器負載得到有效的降低。在上述研究基礎上，下一步工作將集中于當SDN中存在非OpenFlow域時，拓撲發現機制的優化研究。

參 考 文 獻：

[1]DIEGO K， FERNANDO M V R， PAULOE V， et al. Software-Defined Networking： A Comprehensive Survey [J]. Proceedings of the IEEE，2015，103（1）：14.

[2]LARA A，KOLASANI A， RAMAMURTHY B. Network Innovation Using OpenFlow： A Survey [J]. IEEE Communications Surveys & Tutorials，2014，16（1）：493.

[3]KIM H， FEAMSTER N. Improving Network Management with Software Defined Networking[J]. IEEE Communications Magazine，2013，51（2）：114.

[4]黃韜， 劉江， 汪碩，等.未來網絡技術與發展趨勢綜述[J]. 通信學報，2021，42（1）：130.HUANG Tao， LIU Jiang， WANGShuo， et al. Survey of the Future Network Technology and Trend[J]. Journal on Communications，2021，42（1）：130.

[5]PAKZAD F， PORTMANN M， TAN W L， et al. Efficient Topology Discovery in Software Defined Networks[C]//2014 8th International Conference on Signal Processing and Communication Systems （ICSPCS）. IEEE， 2014：1.

[6]HU Fei， HAO Qi， BAO Ke. A survey on Software-Defined Network and OpenFlow： From Concept to Implementation[J]. IEEE Communications Surveys & Tutorials，2014，16（4）：2181.

[7]AZZOUNI A， TRANG N T M， BOUTABA R， et al. Limitations of OpenFlow topology Discovery Protocol[C]//2017 16th Annual Mediterranean Ad hoc Networking Workshop （Med-Hoc-Net）. IEEE，2017：1.

[8]AZZOUNI A， BOUTABA R， TRANG N T M， et al. sOFTDP： Secure and Efficient OpenFlow Topology Discovery Protocol[C]//NOMS 2018-2018 IEEE/IFIP Network Operations and Management Symposium. IEEE，2018：1.

[9]PAKZAD F， PORTMANN M， TAN W L， et al. Efficient Topology Discovery in OpenFlow-based Software Defined Networks[J]. Computer Communications，2016，77：52.

[10]LEONARDO O A， CRISTINA C P， ADRIANA F F. Discovering the Network Topology： An Efficient Approach for SDN[J]. Advances in Distributed Computing and Artificial Intelligence Journal，2016，5（2）：101.

[11]程銘鑫. 面向軟件定義移動自組織網絡的拓撲發現設計與實現[C]∥中國通信學會.2020中國信息通信大會論文集（CICC 2020），2020：483.

[12]DANA H， MOHAMED O. Efficient Topology Discovery in Software Defined Networks： Revisited[J]. Proceeding Computer Science，2017，116：539.

[13]KHAN S， GANI A， WAHAB A W A， et al. Topology Discovery in Software Defined Networks： Threats， Taxonomy， and State-of-the-art[J]. IEEE Communications Surveys & Tutorials， 2016，19（1）：303.

[14]GU Yongpu， LI Dong， YU Junqing. Im-OFDP： An Improved OpenFlow-based Topology Discovery Protocol for Software Defined Network[C]//2020 IFIP Networking Conference （Networking）. IEEE，2020：628.

[15]LANTZ B， HELLER B， MCKEOWN N. A Network in A Laptop： Rapid Prototyping for Software-Defined Networks[C]//Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. 2010：1.

[16]PFAFFB，PETTIT J，KOPONEN T， et al. The Design and Implementation of Open Vswitch[C]//12th {USENIX} Symposium on Networked Systems Design and Implementation （{NSDI} 15）. 2015：117.

[17]SAHA A K， SAMBYO K， BHUNIA C T. Topology Discovery， Loop Finding and Alternative Path Solution in POX Controller[C]//Proceedings of the International MultiConference of Engineers and Computer Scientists. 2016，2：553.

[18]CHOI J S， LI X S. Hierarchical Distributed Topology Discovery Protocol for Multi-Domain SDN Networks[J]. IEEE Communications Letters，2017，21（4）：775.

[19]張朝昆， 崔勇， 唐翯祎， 等.軟件定義網絡（SDN）研究進展[J].軟件學報，2015，26（1）：72.

ZHANG Chaokun， CUI Yong， TANG Haoyi， et al. State-of-the-art Survey on Software-Defined Networking （SDN）[J]. Journal of Software，2015，26（1）：72.

[20]王健，李志新，趙國生，等.面向 SDN 的可生存性增強自配置技術[J].哈爾濱理工大學學報，2017，22（4）：51.

[23]WANG Jian， LI Zhixin， ZHAO Guosheng， et al. Self-Configuration Technology for Survivability Enhancement Oriented Software Defined Networking[J]. Journal of Harbin University of Science and Technology，2017，22（4）：51.

[21]左青云，陳鳴，趙廣松，等.基于OpenFlow的SDN技術研究[J].軟件學報，2013，24（5）：1085.ZUO Qingyun， CHEN Ming， ZHAO Guangsong， et al. Research on OpenFlow-based SDN Technologies[J]. Journal of Software，2013，24（5）：1085.

（編輯：溫澤宇）