大数据中心网络环境的拓扑表示学习方法研究

潘姗姗 周亦敏

摘 要：在大数据中心网络（BDCN）环境下，应用预测和分析拓扑结构的机器学习（ML）算法受到越来越多的关注。利用ML算法对交通网络预测、异常交通監控和路线选择模型的研究取得重大进展，但是在处理网络数据时受到严重制约，探索隐藏在网络拓扑结构中的信息能力有限。因此提出一种新方法“Topology 2Vec”学习网络拓扑，聚焦于网络结构和性能，并使用低维向量表示节点，以确保表示可以适应不同要求。为评估方法有效性，将该方法应用于控制器放置问题的真实数据中心拓扑数据典型用例。实验表明，以“Topology 2Vec”作为前提可以在网络延迟方面产生更好结果。

关键词：拓扑表示学习;机器学习;NRL;BDCN

DOI：10. 11907/rjdk. 182104

中图分类号：TP301文献标识码：A文章编号：1672-7800（2019）003-0057-05

0 引言

网络是一种使用广泛的数据格式，如社交媒体中的社交网络，生物科学中蛋白质-蛋白质互动网络研究中的引用网络。为挖掘网络数据有用信息，通常依赖于摘要网络统计索引、内核函数或手工设计特征，但其中大多数方法都受到高计算和空间成本的困扰。

国内机器学习领域的拓扑研究主要通过数据分析拓扑结构，往往从某个空间采样，嵌入到高维空间，分析研究其低维结构，探测样本空间拓扑结构。例如通过PDSC算法[1]分析预测其拓扑结构，同时着眼于点阵图像转化拓扑结构、提取向量后构建三维立体拓扑结构，如TBR方法[2]实现拓扑结构向量化。郭薇、陈军[3]提出基于点集拓扑学描述三维拓扑空间关系形式化。近年来网络表示学习（NRL）也被作为一种新的学习范式而提出，通过保留网络拓扑结构、顶点内容和其它边信息，将网络顶点嵌入低维矢量空间，有助于在新的向量空间中轻松处理原始网络以供进一步分析。该方法为机器学习（ML）提供了一种更好的方式理解数据和图形结构。但是在BDCN环境下的研究，国内仍处于空白，急需设计出一种切实可行的方法研究拓扑结构。

目前应用于通信网络环境中比较全面的是Sayoud等[4]完成的SSGA，通过优化设计拓扑布局和分配相应的容量（TDCA问题）使通信网络总安装成本最小化。使用GA可以更好地解决高度约束的优化问题。与现有启发式方法相比，可以获得更好的结果，包括网络成本、性能和计算速度。但是针对大数据中心网络（BDCN）环境中的许多问题，如路径选择、流量工程和任务分配，NRL可以更有效解释网络拓扑。因此，本文设计一种名为Topology 2Vec的基于网络表示学习方法，学习BDCN拓扑结构的网络表示方法和拓扑信息比较全面的机器学习方法，在大数据网络环境下的拓扑分析表明，该方法在网络拓扑分析方面有更好的性能。

1 网络表示学习方法

网络表示学习（NRL）从网络挖掘有用信息以了解每个节点矢量表示，使在原始网络空间彼此接近的节点间也具有相似潜在表示。网络表示学习BDCN的方法拓扑分析如图1所示。拓扑表示学习旨在作为连接ML方法的桥梁以解决基于图形数据的BDCN问题，BDCN拓扑描述节点之间的联系[5]。因此，学习拓扑表示在所有网络节点中发现潜在联系并使用低维矢量表示特征。在信息网络中已经有可以使用的嵌入式解决方案，但是不能直接用于有更具体场景的BDCN环境。首先节点和链接可能由于设备故障而改变，因此应作为一个动态网络[6]，选择一个随机数对网络进行采样;其次，现有方法关注节点邻近度，描述节点之间的相似性或发现群体结构体。在通信网络中，本文更关注节点之间的传输能力并将其定义为工作可达性;第三，在信息网络中必须考虑网络性能，但表示学习结果并非总是如此。要满足该要求，必须给予一些具有更好链路性能的节点，使出现在样本结果集中的频率更高。因此需要一个局部可并行化和有效的表示学习方法适应BDCN环境。为解决该问题，本文提出一种名为Topology 2Vec的基于嵌入方法，生成一组向量概括拓扑和网络状态，旨在同时学习潜在的联系以正确表示网络状态信息向量。该表示针对BDCN环境进行了优化。拓扑分析有利于拓扑结构使用ML方法解决相关问题。

为展示在BDCN问题上的潜力，本文在典型情况下评估其有效性。例如控制器放置，在网络资源管理中这是一个通过ML算法解决的重要问题。控制器主要关注点为安置问题，即如何根据BDCN拓扑结构找到合适位置。已有学者使用改进的聚类获得放置策略算法。本文通过第一次探索BDCN拓扑结构获得潜在表示，然后使用现有基于ML的网络分区算法获得更好答案。

为证明方法有效性，选择控制器的放置问题作为典型场景。实验结果表明，该方法在不使用表示学习作为前提的情况下，比最先进的解决方案有更好的性能。

2 相关工作

2.1 基于网络结构的NRL

网络表示学习算法用学习网络中节点向量表示从网络数据中提取的信息。根据网络数据的不同输入，一般将NRL方法分为两类：基于网络结构的NRL（即只考虑拓扑信息）和结合辅助信息的NRL（即除保留结构关系外，对于节点，NRL方法还保留辅助信息以改进表示）。DeepWalk[7]是第一个用于网络表示学习的算法，灵感来自Skip-Gram模型[8]，该模型目的是为在句子中使用单词上下文学习单词表示，DeepWalk在网络中的每个节点上随机游走，然后通过将随机游动序列视为等价句子学习节点表示。DeepWalk假设随机游动序列中的节点具有相似性。因此，不同的随机游走策略会创建不同的节点序列，并保留不同类型的网络结构相似性[9-10]。Node2Vec[11]引入两个超参数控制随机游走过程，以保持BFS和DFS搜索策略之间的平衡。Struc2Vec[12]构造一个多层网络对结构相似性进行编码，如果两个节点以相同的顺序进行采样，则应具有相似结构特征。LINE[13]模拟用于学习节点表示的两种节点关系（即一阶邻近和二阶邻近）。GraRep[14]扩展了LINE，并以不同的k步邻近度学习全局表示。

2.2 无人监督机器学习

在机器学习领域，无监督学习[15]是一个在没有训练样本的大量数据中学习特征和隐藏结构的典型方法。随着分布式计算技术的发展，出现了许多计算平台用于培训更复杂的模型，各种应用程序被不断开发，数据比以前更具多样性。简而言之，大量计算资源以及更高的数据质量促进了无监督学习在学术领域的发展，如自然语言、知识图谱、计算机成像和异象[16]。

很多研究人员使用无监督学习模型解决网络表示学习问题，例如网络嵌入是一种特有吸引力的方法[17-18]。网络嵌入（NE）[19]的概念很简单：在原始高维学习潜在特征空间使用低维向量表示学习成果，其中难点是关于非网络线性特征及一对节点之间的多阶关系。已有许多典型研究方法，如Node2vec [20]，该方法基于深度学习并提供改进的随机性，通过为DFS和BFS设置不同的权重获取功能。与DeepWalk不同，Node2vec引入两个控制DFS和BFS的超参数，使用一个简单的目标函数保留一阶相似度和二阶相似度，所以该方法可应用于发现本地特定问题的结构，如社区结构识别，还可验证实验结果和可扩展性。

2.3 BDCN环境下的拓扑问题

首先，信息网络是由来自不同应用场景的行为实体交互生成的。不同情景给予网络不同的财产，在社区网络中，节点和链接可能会经常变化。但是，BDCN环境是一个更具体的情况，需要考虑动态节点和链路状态在什么时候改变路由、链路性能和路径故障，从而动态性影响节点和链接，然后扩展到整个网络拓扑。因此，需要一个可以适应的样本方法改变网络拓扑。

其次，代表学习信息网络中的方法主要用来提取节点之间的接近度、描述节点的相似性。而在通信网络中，需要解释低维向量中的可达性。

第三，网络表现状态和结构是BDCN拓扑问题的核心。除了节点关系，还需要捕捉基于链接性能的BDCN具体要求。因此，连接节点是由网络性能决定节点之间的物理链接。网络状况和拓扑结构都应考虑获得拓扑节点之间的潜在关系和通信网络中的表征学习问题。

本文利用网络嵌入方法，使用BDCN的Topology 2Vec拓扑结构，选择控制器安置问题（CPP）[11]进行验证。BDCN中许多问题可以从学习结果中找到解决BDCN拓扑表示问题的方法，其中典型方法是CPP，其核心是如何能够根据BDCN拓扑结构找到合适位置以关注不断变化的网络状态。现有方法通过用改进的聚类方法解决该问题，以减少问题规模[17-18]。本文方法以学习拓扑结构作为前提，最大限度减少拓扑信息缺乏。

3 大数据环境下的拓扑表示

3.1 问题定义

在实践中，大数据环境下的网络拓扑在网络构建和传输中起主要作用，并且BDCN 的拓扑始终是无向的，链路权重可以是0/1或非负实数。根据具体问题，链路权重可能会随着链路性能或链路可用性分散。基于该前提定义大数据环境下的网络拓扑、节点可达性和拓扑表示。

在大数据环境下，基于一组随机游走的节点确定图形结构，使用节点可达性表示节点之间的成对关系。直接连接两个网络设备之间的物理链路间接表明两个节点之间存在很多路径，通过图形采样可估计节点系列之间的可能性，学习BDCN拓扑。

3.2 网络拓扑的表示学习

一个精心设计的BDCN环境下的表示学习方法应该满足有效性。首先，该方法必须能使用节点之间本地结构保留拓扑全局视图;其次，必须能适应不同应用的要求，因为关系节点可能存在不同方面的可达性;第三，该方法应是可扩展的，以增加BDCN大小。

许多图形表示方法是基于随机游走模式的，并且结果受下一跳节点影响。大数据环境下的局部搜索有两个影响因素：拓扑结构和可达性。本文Topology2Vec方法的基础是使用一组随机节点的游走对拓扑进行采样，通过学习节点之间的关系获取全局知识，并且节点可达性不仅可能与拓扑结构有关，还可能与路径性能有关。本文权重表示链接性能，由权重决定下一个节点。

3.3 低维度拓扑表示学习算法

在大数据环境下，应考虑局部结构和链路性能。为计算权重，通过使用链路性能评估权重，选择通过式（1）描述下一个节点，使链路性能更好地保留拓扑信息。

对于采样，通过固定长度或标准的随机游走探索整个拓扑结构。作为学习矢量表示的前提，所有节点可能性表示为：

然后，使用Skip Gram模型完成表示任务。同时，它可以被任何其它类似方法取代。Skip-Gram模型是与神经网络相比没有隐藏层的NLP模型。现有方案表明，通过使用适当的采样方法作为基础，可以获得良好的结果。通过Skip-Gram模型将优化问题转换为：

通常使用分层Softmax计算条件概率，并且每个节点将分配给二叉树的叶子，然后模拟节点概率[v]作为树节点可变长度序列。

对于最优化，随机梯度 （SGD）[21]用于更新参数：

按照上述过程，最终获得低维向量表示BDCN拓扑的每个节点。另外，每对矢量之间的距离相应指示节点之间可达性。

3.4 大数据环境下拓扑低纬度表示算法实现

由于SDN技术已广泛应用于BDCN环境[20]，单一控制器的缺點逐渐显现。大型数据中心网络规模的不断扩大意味着单个集中控制器模式可能无法满足可扩展性需求，研发重点由此转向控制平面的多个控制器。因此，该计划的可用性取决于是否可找到优化的位置策略。在启用SDN的网络中，CPP严重影响控制器资源分配、容错和控制器之间的延迟。现有方法通常使用改进的机器学习算法找到网络分区以获得合理数量、实现控制器本地化。

因此本文运用Topology 2Vec表示学习方法探索BDCN拓扑，然后将其与一些网络分区算法相结合，以获得拓扑分区策略。拓扑表示学习可以充分利用隐藏于网络结构的可用信息，并表示低维空间节点。学习结果采用向量形式，因此对大多数ML方法更友好。此外，Topology2Vec中基于随机游走的采样方法可保证并行处理能力满足可扩展性要求。

4 实验结果与分析

结合DBCP、标准K均值和优化K均值的方法性能与端到端通信和控制器间通信的平均延迟进行比较。使用Python运行模拟，利用BDCN拓扑的真实数据集对不同网络环境进行建模，获取几种不同的CPP解决方案，以便在使用或不使用Topology2Vec时获得性能变化。

（1）数据集。实验数据集从Topological Zoo获得，Topological Zoo包含许多真实的数据中心网络拓扑[17]。

（2）比较方法。将本文方法Topology 2Vec与以下基线进行比较，基线使用相邻矩阵表示拓扑和一对节点之间关系的路径长度：①DBCP[22]。该方法使用基于密度的交换机群集算法分割网络，并使用网络分区获得最佳数量的控制器。对于每个子网，DBCP部署一个控制器以保证低时间消耗，传播延迟和容错。②标准K均值。K均值聚类算法使用标准过程通过使用随机采样分割网络以获得初始分区和中心;③Optimized K-means[23]：由于标准K-means初始阶段使用随机抽样方法，因此无法保证延迟可以很好地最小化，所以从网络延迟角度将CPP制定为网络分区问题。该方法使用优化的K-means获得网络分区和质心。通过文献[24]提出的初始化方法，优化的实现比标准K-means擁有更短的延迟和更好性能。

实验使用Topology 2Vec作为研究延迟指标变化的前提，包括端到端通信延迟和控制器间通信延迟。端到端延迟包括交换机到控制器的延迟，控制器到控制器的延迟以及控制器到交换机的延迟。图2实验结果表明，与原始方法相比，Topology 2Vec集成的3种网络分区方法在端到端延迟方面具有更好性能。在图3中，比较控制器间延迟性能实验结果反映了控制器转换效率。本文方法缩短了所有3种方法的控制器间的延迟，可使控制层实现更高的控制消息传递效率。此外，在3种原始方法中，DBCP比标准K-Means和Optimized K-means具有更好性能，与本文方法相结合，提高了DBCP性能，表明通过全面拓扑表示可以改善现有CPP解决方案。

5 结语

本文在机器算法和深度表示学习算法的前提下，关注BDCN环境下拓扑表示学习问题，并提出了Topology 2Vec模型。该模型可以同时保留拓扑结构和网络状态，深度了解节点之间的数据信息，结果更接近于真实的可达性。根据评估可知，Topology 2Vec可以更好地使用拓扑表示支持BDCN环境下的控制器放置问题。后续研究将采用更好的节点采样方法以降低研究成本，使机器学习算法与拓扑表示学习结合得更紧密，解决BDCN环境下节点预测问题。

参考文献：

[1] 谢子雨. 机器学习的拓扑结构研究[D]. 上海：复旦大学，2013.

[2] 唐龙，黄爽英，钟晓军，等. 基于拓扑结构表示的向量化方法[J]. 计算机工程，1994（S1）：542-548.

[3] 郭薇，陈军. 基于点集拓扑学的三维拓扑空间关系形式化描述[J]. 测绘学报，1997（26）：122-127.

[4] SAYOUD H，TAKAHASHI K，VAILLANT B. Designing communication network topologies using steady-state genetic algorithms[J].  IEEE Communications Letters，2011，5（3）：113-115.

[5] WANG T，SU Z，XIA Y. Rethinking the data center networking： architecture，network protocols， and resource sharing[J]. IEEE Access，2014，2：1481-1496.

[6] WANG T，SU Z，XIA Y. CLOT： a cost-effective low-latency overlaid torus-based network architecture for data centers[C]. IEEE International Conference on Communications，2015：5479-5484.

[7] PEROZZI B，AL-RFOU R，SKIENA S. Deepwalk： online learning of social representations[C]. ？Proceedings of the Twentieth ACM SIGKDD international conference on Knowledge discovery and data mining，2014： 701-710.

[8] MIKOLOV T，SUTSKEVER I，CHEN K， et al. Distributed representations of words and phrases and their compositionality[C]. ？Proceedings of the Twenty-Sixth International Conference on Neural Information Processing Systems， 2013：3111-3119.

[9] GROVER A，LESKOVEC J. Node2vec： scalable feature learning for networks[C]. ？Proceedings of the Twenty-Second ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2016： 855-864.

[10] RIBEIRO L F R，SAVERESE P H P，FIGUEIREDO D R. Struc2vec： learning node representations from structural identity[C]. ？Proceedings of the Twenty-Third ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2017：385-394.

[11] TANG J， QU M，WANG M， et al. Line： large-scale information network embedding[C]. Proceedings of the Twenty-Fourth International Conference on World Wide Web， 2015：1067-1077.

[12] CAO S，LU W，XU Q. Grarep： learning graph representations with global structural information[C]. Proceedings of the Twenty-Fourth ACM International on Conference on Information and Knowledge Management， 2155： 891-900.

[13] HOFMANN T. Unsupervised learning by probabilistic latent semantic analysis [J]. Machine Learning， 2001，？42？（1-2）：177-196.

[14] NG Y H，CHOI J，NEUMANN J，et al. ActionFlowNet： learning motion representation for action recognition[C]. 2018 IEEE Winter Conference on Applications of Computer Vision，2018：1-9.

[15] ZHANG D，YIN J，ZHU X，et al.  Network representation learning： a survey[J].  IEEE Transaction on Big Data，？2017，99：1.

[16] HAMILTON W L，YING R，LESKOVEC J. Representation learning on graphs： methods and applications[C]. IEEE Data Engineering Bulletin， 2017：1-24.

[17] WANG D. Structural deep network embedding[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2016： 1225-1234.

[18] PEROZZI B，AL-RFOU R，SKIENA S. DeepWalk： online learning of social representations[C]. 20th International Conference on Knowledge Discovery and Data Mining， 2014： 701-710.

[19] GROVER A，LESKOVEC J. Node2Vec[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2016：855-864.

[20] BOTTOU L. Stochastic gradient learning in neural networks[J]. Neuro-N？mes， 1991，91（8）：1-12.

[21] KNIGHT S，NGUYEN H X，FALKNER N，et al. The internet topology zoo[J]. IEEE Journal on Selected Areas in Communications，2011，29？（9）：1765-1775.

[22] LIAO J，SUN H，WANG J，et al. Density cluster based approach for controller placement problem in large-scale software defined networking [J]. Computer Networks，2017（112）： 24-35.

[23] WANG G，ZHAO Y，HUANG J，et al. A K-means-based network partition algorithm for controller placement in software defined network[C]. IEEE International Conference on Communications，2016？：1-6.

[24] KATSAVOUNIDIS I，KUO C C，ZHANG Z. A new initialization technique for generalized Lloyd iteration[J].  IEEE Signal Process Letter， 1994，1（10）： 144-146.

（責任编辑：江 艳）