软件定义网络中一种优化的拓扑发现机制

李兰英　王敏　朱素霞

摘要： 针对软件定义网络中拓扑发现机制存在资源消耗过大，运行效率低等问题，提出一种优化的拓扑发现机制（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.

（编辑：温泽宇）