集中与分布：协同虚拟网络映射

丰旻　廖建新　王敬宇

摘要：结合传统集中式和分布式两类算法各自的特性，提出了协同虚拟网络映射算法。该算法保留了集中式算法中拥有全局视野的中心控制实体，负责总体控制和关键决策，同时将具体映射方案的计算过程交给有限的底层网络子集实现；唯一的中心控制实体与多个底层节点相互配合协作，共同完成虚拟网络映射的整个过程。该算法继承了集中式和分布式算法各自的优势，有效弥补了二者的缺陷，初步的仿真试验也证明了其可行性和有效性。

关键词： 网络虚拟化；虚拟网络映射；集中；分布；协同虚拟网络映射

1 网络虚拟化

作为消除互联网僵化顽疾的强大工具，网络虚拟化被视为下一代网络架构的关键技术，获得了学术界和产业界的广泛关注[1-5]。网络虚拟化通过虚拟化技术将作为基础设施的底层网络抽象为相应的虚拟底层，通过虚拟资源切片的方式，将多个彼此隔离且异构的虚拟网络同时映射到其上。许多新的计算和网络技术都受益于网络虚拟化，如软件定义网络、云计算和数据中心网络。在网络虚拟化环境中，传统的网络服务提供商自然分化为负责部署、管理和维护底层网络资源的基础设施提供商和租用网络资源构建虚拟网络以向终端用户提供多样化服务的服务提供商。

2 集中式和分布式的虚拟

网络映射

基础设施提供商需要采用有效的算法来将虚拟网络请求映射到底层网络的特定节点和链路上，以更加有效且高效地使用底层网络资源。这就是虚拟网络映射问题。然而由于存在多维的资源限制和多个目标，使得无论问题空间是否受限，虚拟网络映射问题都是NP难的[6]。随着网络虚拟化技术的快速发展和应用，虚拟网络映射便成了其中亟待解决的核心问题之一。

难以驾驭的计算复杂性促使研究者们专注于设计各种启发式算法来寻找接近最优解的切实可行的映射解决方案[7-14]。现有虚拟网络映射算法可以按照不同的标准进行多种分类，如按照节点映射与链路映射是同时进行还是先后进行，分为一阶段算法和两阶段算法（如文献[8]、文献[9]、文献[11]）；按照涉及单个还是多个基础设施提供商，分为单域算法（如文献[9]、文献[10]、文献[11]）和多域算法（如文献[14]）；按照考虑可生存性分配备用冗余资源（如文献[7]、文献[8]）与否等标准进行分类。本文中我们考虑虚拟网络映射实现的控制方式，将现有虚拟网络映射算法分为集中式的虚拟网络映射算法和分布式的虚拟网络映射算法两大类。

2.1 集中式虚拟网络映射算法

在集中式算法中，只有一个唯一的中心控制实体负责映射的全部决策。集中式算法的优势在于这个唯一的中心控制实体通过收集、评估和管理底层网络中的所有资源信息而具有全局视野，清楚的了解整个网络的各种信息，因此更可能找出全局最优或者至少接近全局最优的映射方案，资源分配的过程中也不会发生冲突等情况。逻辑上集中的控制也使得根据具体业务需求进行的全局资源调配和优化成为可能，并使得整个虚拟网络的映射运营过程便于维护调整，提升了网络控制的便捷性。但是另一方面，这个唯一的控制实体也就成为了整个网络的“瓶颈”。随着底层网络的不断扩容，中心控制实体与众多节点间的通信数量将呈指数增长，及时获取底层资源的实时信息将越来越难以完成，因此对于网络拓扑不断变化的动态网络来说延迟较高。其面对大尺度网络则很容易出现扩展性问题和产生系统单点故障，而一旦中心控制实体出现问题，整个网络的映射、运行、管理和维护就会难以为继。

俞敏岚等[9]将虚拟网络映射分为节点映射和链路映射两个阶段，并假定底层物理网络支持灵活的路径分割和周期性的路径迁移。算法采用了贪婪的节点映射，链路映射阶段则使用多商品流算法或K最短路径算法求解。

Chowdhury等[10]通过在节点映射阶段考虑链路的带宽限制，来协调节点映射和链路映射。算法结合地理位置约束条件，由底层网络加上元节点和元链路构成增广的拓扑图，进而将虚拟网络映射问题建模成混合整数规划，并利用确定或随机取整求解可行的节点映射方案。其链路映射算法与文献[9]相同。

廖建新等[11]提出将多个拓扑特征值集成应用于设计拓扑感知的映射算法。文中提出了6个反映不同网络拓扑属性的拓扑特征值，进而利用其各自特点和优势设计了基于多拓扑特征值的拓扑感知算法。算法核心的节点排序策略也可用于改进其他映射算法。拓扑特征值还被用于拓扑分解，以解开大尺寸虚拟网络的层次结构，优化映射过程。

2.2 分布式虚拟网络映射算法

相比于依赖单一中心控制实体的集中式算法，分布式算法则依靠分布广泛且数量众多的底层节点。虚拟网络映射的整个决策由各底层节点共同实现完成，于是负载得以分散，可扩展性得以增强，整个映射过程和网络运行不会因为单点故障而完全失效。然而，分布式的设计思路也一把双刃剑，与更好可扩展性、鲁棒性相伴的是节点间更大的同步开销。底层网络的全局信息，如各个节点和链路的状态，实时资源占用情况等等，都需要有完善的消息传递机制在所有底层节点间随时进行更新和同步，以在各底层节点维护最新的统一的全局信息。因为只有每个底层节点对全局信息了解得越清楚越及时，才越可能做出当前真实网络条件下的最佳映射决策，并且避免可能出现的冲突和不一致。

Houidi等[12]提出使用多代理系统设计分布式算法。实现节点间协商与同步的消息传递采用了洪泛机制，即每个底层节点映射虚拟节点和链路后，都向所有其他节点发送消息，告知映射结果。因此消息的数量相对底层网络的尺寸成指数增长，算法受到过多同步消息和较大映射开销的困扰，在扩展性和映射性能方面还无法与集中式算法相比。

卿苏德等[13]提出了基于布隆过滤器的分布式映射算法。算法利用机器学习和推理技术，通过积累的历史信息在没有或缺乏底层网络信息的情况下对节点的能力进行评估，并依赖底层节点的自主映射完成整个虚拟网络映射。同步消息中捎带的布隆过滤器实现了有限范围的信息同步，既有效避免了映射冲突，又规避了传统洪泛算法的巨大通信开销。

Chowdhury等[14-15]针对多个基础设施提供商，提出了根据地域切分和映射的PolyViNE架构，以协调解决基础设施提供商与服务提供商间的利益冲突。服务提供商将虚拟网络请求发给多个基础设施提供商，由其各自提出涉及自己和其他基础设施提供商网络的跨域映射方案和报价，最终由服务提供商择优确定映射方案。另外基础设施提供商之间也存在竞争，争夺高利润的映射任务并尽力将难以牟利的部分留给其他基础设施提供商。

3 协同虚拟网络映射算法

集中式算法和分布式算法各自的优劣势启发我们在本文中尝试充分结合利用两者的特点与优势，设计一个介于集中与分布控制之间的虚拟网络映射算法，我们称之为协同虚拟网络映射（CVNE）。

集中式算法的优势源于中心控制实体拥有全局视野，因此我们保留全局唯一的中心控制实体，依然负责收集、评估和管理底层网络中的所有资源信息，并具有全局视野和关键决策的控制权。分布式算法的优势在于映射的整个决策由众多底层节点实现完成，分散负载，于是我们将具体细节的映射方案计算过程交给底层节点实现。中心控制实体与底层节点相互配合协作，共同完成虚拟网络映射。

3.1 协同算法总体流程

当一个虚拟网络请求达到后，首先进入中心控制实体维护的虚拟网络请求队列。中心控制实体采取自定义的排队机制依次进行虚拟网络映射。

对于当前进行映射的虚拟网络请求，如果其虚拟节点数量较少、拓扑结构简单且无需分区域映射，则中心控制实体首先采取特定算法选取一个或多个底层节点作为“中心节点”。选取中心节点的具体数量由整个系统（包括底层网络和中心控制实体）的负载情况决定：系统负载较轻时可以选择合理数量的多个中心节点，而负载较重时则将只选取唯一的中心节点。中心节点的选择算法可借鉴文献[11]中的拓扑感知的节点排序算法，即利用基于多拓扑特征值的节点排序策略对底层节点排序，然后选取初步满足映射要求的候选底层节点中排名较高且自身资源占用率较低的作为中心节点。中心控制实体将当前虚拟网络请求和全局网络信息一同发给各中心节点，由其为该虚拟网络计算映射方案。中心节点获得全局网络信息后，进一步从与相邻节点（一定跳数范围内）的通信中获取自己所处局部网络的实时信息，更新全局网络信息，以解决中心控制实体获取底层网络信息的延迟问题。节点和链路映射算法可根据中心节点所属网络的具体设置，灵活选用定制的算法。每个中心节点计算出映射方案后发回给中心控制实体，由中心控制实体比较选定最优方案（默认总开销最少为最优）进行资源分配，完成映射。如果中心节点计算映射方案失败，则将失败情况告知中心控制实体，由中心控制实体进行相应调整：重新选择其他中心节点计算映射方案，或在多次映射失败后推迟或放弃该虚拟网络请求。我们将上述过程称为“简单网络映射”。

如果当前虚拟网络请求的虚拟节点数量较多、拓扑结构复杂或者有地域限制需要分区域映射，则中心控制实体需要在中心节点选择之前首先对虚拟网络拓扑进行预处理：对于有地域限制或者跨多个运营商等情况的虚拟网络请求，优先根据具体限制情况将其自然分解为多个虚拟子网；对于虚拟节点数量较多或拓扑结构复杂的虚拟网络我们采用KS核分解算法[11]将其分解为一个核心网络和多个边缘网络。自然分解的多个虚拟子网将被相应分配给各底层网络自治域中处于相邻边界的一个或多个中心节点，分别进行多个简单网络映射，然后各中心节点将各自的虚拟子网映射方案发回给中心控制实体，由其选择其中的全局最优（默认总开销最少为最优）的方案组合进行映射，或进行相应调整。拓扑分解后的核心网络则首先进行简单网络映射。由于每个边缘网络通过KS核分解算法生成，核心网络中与之相连的衔接节点已确定映射方案，因此我们在边缘网络映射中将已映射的衔接节点作为下阶段的中心节点，其从上阶段核心网络映射的中心节点处得到全局网络信息和边缘网络信息后进行简单网络映射。如果边缘网络映射的中心节点计算映射方案失败，则将失败原因告知核心网络的中心节点，由其进行相应调整，重新映射对应的衔接节点，或在多次映射失败后推迟或放弃该虚拟网络请求。

协同虚拟网络映射算法相比传统集中式算法，由于将大量具体的映射任务交由底层中心节点完成，中心控制实体在映射中只负责虚拟网络请求的预处理、分配、重分配、方案确定和资源分配等，因此负载明显减轻。由中心控制实体在头尾阶段进行全局最优的决策，由分布的中心节点进行局部最优的方案计算，保证了最终的映射方案是接近最优解的，也不会出现映射冲突等情况。动态网络的延迟问题由于中心节点从中心控制实体处获取的全局网络信息与在所处局部网络中的实时信息更新相结合而得以有效解决；面对大尺度网络的扩展性问题和系统单点故障问题也将得到极大缓解。

相比传统分布式算法，协同虚拟网络映射算法中虽然每个底层节点都具备成为中心节点的能力，但是每一次映射只有少数更有能力的优质节点被选中，映射任务限定在有限的底层网络子集中。映射冲突由于中心控制实体的存在得以有效避免。这些都使得节点间的同步开销大大降低，无需采取洪泛等产生大量同步消息的消息传递机制。多个中心节点同时计算部分或整体映射方案也实现了虚拟网络映射的并行计算，可以明显降低映射耗时。

3.2 协同算法映射实例

图1显示了服务提供商的两个虚拟网络请求通过协同算法映射到基础设施提供商的底层网络的实例。图中实线代表链路连接，其粗细反映带宽大小；虚线代表映射成功的虚拟链路；底层网络节点用大写字母表示，虚拟网络节点用小写字母表示，在映射中被指定为中心节点的底层网络节点用绿色标明。虚拟网络请求1和2先后到达，进入虚拟网络请求队列中，但由于虚拟网络请求2预期收益较高，因此将优先映射。虚拟网络请求2节点较多，于是通过KS核分解算法被分解为红色的1个核心网络和蓝色的3个边缘网络。其核心网络被中心控制实体分配给底层网络的中心节点A计算映射方案。3个边缘网络在核心网络映射方案确定后被分别交给下阶段的中心节点B、C、F，同时计算各自边缘网络的映射方案。最后的总体映射方案由中心控制实体确定，并进行资源分配以完成映射。虚拟网络请求1由于节点数量少，拓扑简单，也没有地域限制，因此无需分解。其被中心控制实体交给底层节点I计算映射方案，最后得以映射。

4 仿真结果

初步的仿真实验参照文献[9]、文献[11]和文献[13]的网络环境和参数设置进行，将集中式算法的代表——文献[9]的算法（以BL表示），以及分布式算法的代表——文献[13]的基于布隆过滤器的分布式算法（以P2PVNE表示）作为对比算法，定量测试我们的协同虚拟网络算法（以CVNE表示）在长期平均收益、接受率和收益开销比3项性能指标上的表现。协同算法中虚拟网络请求队列采用了传统收益优先的排队机制，即按照预期收益由多到少的顺序先后进行映射；各中心节点处的映射算法采用了文献[11]中的NDC算法。

协同算法与集中式、分布式代表算法的长期平均收益比较如图2所示。协同算法与集中式、分布式代表算法的长期接受率比较如图3所示。协同算法与集中式、分布式代表算法的长期收益开销比比较如图4所示。从图2、图3和图4中我们可以看到，文献[13]中的分布式算法在长期平均收益、接受率和收益开销比3项性能指标上相比文献[9]中的集中式算法都有了明显提升，而我们的协同算法在长期接受率和收益开销比两项性能指标相比前两者又有了更大的提升，在长期平均收益上相比分布式算法也有一定的提升。总的来看，协同虚拟网络映射算法由于将集中式算法和分布式算法的相对优势充分结合，有效弥补了二者的缺陷，从而达到了更好的映射性能。

5 结束语

虚拟网络映射问题是网络虚拟化中的关键挑战，传统集中式和分布式的映射算法各有利弊。我们在本文中充分结合利用两大类算法的相对优势，设计了兼具集中与分布特点的协同虚拟网络映射算法。算法相比传统的集中式和分布式算法的综合优势明显，初步的仿真试验结果也证明了算法的可行性和有效性。

参考文献

[1] CHOWDHURY N， BOUTABA R. A survey of network virtualization [J]. Computer Networks， 2010，54（5）： 862-876.

[2] FEAMSTER N， GAO L， REXFORD J. How to lease the Internet in your spare time [J]. ACM SIGCOMM Computer Communication Review， 2007，37（1）： 61-64.

[3] BAVIER A， FEAMSTER N， HUANG M， et al. In VINI veritas： Realistic and controlled network experimentation [J]. ACM SIGCOMM Computer Communication Review， 2006，36（4）： 3-14.

[4] ANDERSON T， PETERSON L， SHENKER S， et al. Overcoming the Internet impasse through virtualization [J]. IEEE Computer Magazine， 2005，38（4）： 34-41.

[5] TURNER J， TAYLOR D. Diversifying the Internet [C]//Proceedings of the Global Telecommunications Conference， 2005. St. Louis， MO， 2005，2： 755-760. doi：10.1109/GLOCOM.2005.1577741.

[6] ANDERSEN D G. Theoretical approaches to node assignment [R]. Unpublished Manuscript， 2002.

[7] YU H， QIAO C， ANAND V， et al. Survivable Virtual Infrastructure Mapping in a Federated Computing and Networking System under Single Regional failures [C]//Proceedings of the IEEE GLOBECOM， 2010：1-6.

[8] YU H， ANAND V， QIAO C， et al. Cost Efficient Design of Survivable Virtual Infrastructure to Recover from Facility Node Failures [C]//Proceedings of the IEEE ICC， 2011：1-6.

[9] YU M， YI Y， REXFORD J， et al. Rethinking virtual network embedding： substrate support for path splitting and migration [J]. ACM SIGCOMM Computer Communication Review， 2008，38（2）： 17-29.

[10] CHOWDHURY N， RAHMAN M， BOUTABA R. Virtual network embedding with coordinated node and link mapping [C]//Proceedings of the IEEE INFOCOM， 2009： 783-791.

[11] LIAO J， FENG M， LI T， et al. Topology-aware Virtual Network Embedding Using Multiple Characteristics [J]. KSII Transactions on Internet and Information Systems， 2014，8（1）： 145-164.

[12] HOUIDI I， LOUATI W， ZEGHLACHE D. A distributed virtual network mapping algorithm [C]//Proceedings of the IEEE ICC， 2008：5634-5640.

[13] 卿苏德. 网络虚拟化映射算法研究 [R]. 北京邮电大学博士学位论文. 2013.

[14] CHOWDHURY M， SAMUEL F， BOUTABA R. Polyvine： policy-based virtual network embedding across multiple domains [C]//Proceedings of the 2nd ACM SIGCOMM workshop on Virtualized infrastructure systems and architectures， New York， USA， 2010：49-56.

[15] FENG M， ZHANG L， ZHU X， et al. Topology-aware virtual network embedding through the degree [C]//Proceedings of the IET National Doctoral Academic Forum on Information and Communications Technology， 2013：1-6.