图嵌入方法及其在网络虚拟化中应用研究

Network virtualization, an active area of research in computation, has a wide range of applications. One of key technologies of network virtualization is graph embedding methods which allow a virtual logical topological graph representing users' requirements is well embedded into a physical topological graph. In this program, two methods for graph embedding are investigated. This first method is based on Cayley graphs and Coset graphs, which will be used to solve such virtualization problems in P2P overlay networks as designing virtual topological structures with high symmetry and achieving an efficient routing in these networks, and will also be attempted to obtain an efficient routing in a real complex network. The second method is based on k-pairs disjoint paths in a graph, which will be used to solve some virtual topology design problems where physical topological graphs are from among swapped networks and Biswapped networks, two classes of combinatorial networks using a similar swapped connectivity rule to link their modules. Applications regarding to tolerant fault routing in these combinatorial networks are explored based on the obtained k-pairs disjoint paths constructions. These combinatorial networks enjoy many favorable properties and thus see many potential applications. These methods for graph embedding take advantage of structure properties of symmetric graphs to reduce some network virtualizaton problems, which is significant in developing new methods based on algebra and graph theory for addressing network problems, and in diverse applications of network virtualization technologies.

网络虚拟化是当前计算领域的研究热点,有广阔的应用前景，其关键技术之一是图嵌入方法，即将由实际需求抽象所得虚拟逻辑拓扑结构图如何有效嵌入到基础物理网络结构图中的方法。本项目研究两类图嵌入方法。一类是基于Cayley图和陪集图的图嵌入方法，研究其在对等网络中用于设计高对称性的虚拟拓扑结构图并获得高效路由方法等虚拟化问题；也探讨其如何有助于设计现实复杂网络有效路由方法。另一类是基于k-pairs不相交路径的图嵌入方法，研究其在基于Swapped互连规则的两类组合网络作为物理网络结构图时的虚拟拓扑设计以及容错路由方面的应用。这些组合网络有优良特性因而有较好应用前景。这些图嵌入方法充分利用图结构对称性来简化一些网络虚拟化问题，其研究对深化和发展网络中的代数和图论方法，对网络虚拟化技术深入广泛应用有深刻意义。

图嵌入方法是实现网络虚拟化的关键技术之一，它是将由实际需求抽象所得虚拟逻辑拓扑图嵌入到基础物理网络结构图中的一类方法。本项目主要研究利用图结构对称性简化某些网络虚拟化问题的图嵌入方法。研究内容包括三个方面。第一，研究了复杂网络的点度呈幂率分布的形成机制，得出了复杂网络的度序列长度（即不同点度的个数）的一般性结论，即网络度序列长度是网络点数的对数的量级；根据该结论，利用基于代数图论的图嵌入方法，探究了一般复杂网络中的路由策略。此外，利用代数图论Cayley图方法，提出了路由和容错性能良好的网络拓扑结构，并讨论其作为结构化数据中心的网络模型等方面的应用。第二，研究了环、不相交路、支配集、连通支配集等典型拓扑结构在基于Swapped互连规则的两类组合网络中的嵌入问题，较圆满解决了Biswapped网络中的泛圈性问题（网络泛圈性即为网络中包含各种长度的环的特性），得出了这两类组合网络中不相交路、支配集、连通支配集等问题的计算复杂性结论（均为NP难度问题），并给出近似求解算法。第三，研究了无线传感器网络、社交网络中的相关问题，包括非干扰不相交路径、最小干扰连通拓扑在无线网路中的嵌入问题，给出了有效的求解算法；为社交网路的正影响支配集问题得出了一个改进的贪心近似算法等。在本项目研究结论中，复杂网络度序列长度的结论揭示了复杂网络的一个较为普遍的规律，可以作为一般复杂网络的一个新特性；所提出的基于图嵌入的路由策略的研究方法、Biswapped网络中泛圈性等问题的研究方法具有一定通用性，适用于研究相关问题。. 本项目执行期间取得的主要成果为公开发表了21篇学术论文，包括在国际SCI刊物上发表7篇（《Physica A》上2篇，《Information Sciences》，《The Computer Journal》，《Chaos》，《Journal of Applied Analysis and Computation》和《Journal of Communications and Networks》上各1篇），国内一级刊物《计算机学报》和《软件学报》上各1篇，国际EI刊物《Journal of Interconnection Networks》上1篇。培养了硕士生10名，正在培养的硕士生5名；合作单位培养了博士生1名。