李蘭英　王敏　朱素霞

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

關鍵詞：

軟件定義網絡;拓撲發(fā)現(xiàn);頂點覆蓋;控制器

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

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

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

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

1S-OFDP

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

1.1Packet-Out數(shù)量的優(yōu)化

1.2OpenFlow交換機之間LLDP pkt數(shù)量的優(yōu)化

1.3Packet-In數(shù)量的優(yōu)化

1.4S-OFDP機制的詳細步驟

3仿真實驗與結果分析

3.1實驗環(huán)境與參數(shù)設置

3.2網絡中LLDP的數(shù)量

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

對控制器負載的影響

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

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

4結論

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

參 考 文 獻：

[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]黃韜， 劉江， 汪碩，等.未來網絡技術與發(fā)展趨勢綜述[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]程銘鑫. 面向軟件定義移動自組織網絡的拓撲發(fā)現(xiàn)設計與實現(xiàn)[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.

（編輯：溫澤宇）