递归型数据中心网络上的条件容错通信性能研究

Cloud computing is developing rapidly in the world, and playing an increasingly important role in education, scientific research and other related fields. The topology of data center network is critical to the performance of cloud computing. Traditional tree-based data center networks have issues of bandwidth bottleneck, failure of single switch, etc.. Recently proposed Fat-Tree and other tree-based data center networks cannot support well in the one to many and many to many routing communications. In order to overcome the above disadvantages of the tree-based data center networks, the researchers have proposed DCell, BCube, etc. recursive-type data center networks, these structures have better scalability, communication performance and fault-tolerant communication performance with respect to tree-based data center networks. The result of restricted connectivity, extra connectivity, and fault diameter of recursive-type data center network can improve the fault-tolerance of the network. And the methods used in the existing studies cannot be applied to general recursive-type data center networks; and there are loss of general method and related researches on experiments. In this project, we will first study the conditional fault-tolerance problems in several special recursive-type data center networks. And then we will give a general result and provide a general method on the restricted connectivity, extra connectivity, and fault diameter problems of recursive-type data center networks. Moreover, we will study fault-tolerant routing algorithms relate with the project. Finally, we will analyze the performance and time complexities of the proposed algorithms, conduct simulation and real experiments accordingly in recursive-type data center networks. Our research has strong theoretical value and practical significance.

云计算在全球迅速兴起，在教育、科研等相关领域发挥着日益重要的作用。数据中心网络拓扑结构的性质对于云计算的性能至关重要。传统的树型数据中心网络存在带宽瓶颈和单点失效等问题，且目前提出的胖树等树型数据中心网络不能很好的支持一对多和多对多的通信。为了克服树型结构的上述缺点，研究者们提出了DCell、BCube等多种递归型数据中心网络，这些结构具有较好的可扩展性、通信和容错通信性能。使用限制连通度、外连通度和故障直径能够很好的提高一个递归型数据中心网络的条件容错通信性能。然而，目前只有几种特殊的递归型数据中心网络上的这些问题的部分研究成果，且现有方法缺乏一般性及相关实验研究。本项目将研究递归型数据中心网络上的条件容错通信性能，给出在这些结构上求解限制连通度、外连通度和故障直径的通用方法和一般结果；设计相应的容错路由算法；分析算法的性能并进行相应的模拟和实际实验，具有较强的理论价值和实际意义。

数据中心网络的性能在很大程度上决定着云计算的性能，但随着云计算应用需求的不断提高，数据中心网络中的服务器数量变得越来越庞大。研究者们提出了DCell、BCube等多种递归型数据中心网络，这些网络克服了胖树等树型数据中心网络不能很好的支持一对多和多对多通信等缺点。使用限制连通度、外连通度和故障直径能够很好的提高一个递归型数据中心网络的条件容错通信性能，且在递归型数据中心网络上研究这些问题，缺乏一般性的研究结果及相关实验研究。本项目研究了递归型数据中心网络上的条件容错通信性能，并进行了模拟实验和应用研究，具体研究成果如下：1.研究了特殊的递归型数据中心网络BCube和BCDC上的限制连通度；提出了部署于n-口交换机上的k-维递归型数据中心网络RDCN的定义，证明了当k≥1且n≥3时，RDCN的限制连通度为2kδ+n-2，这一结果近于其连通度的2倍，δ∈{1,n-1}表示RDCN中任意顶点与同维度其它子网络相连接的边数。2.研究了特殊的递归型数据中心网络DCell和BCube上的外连通度；证明了当k≥3,n≥3且0≤g≤2时,递归型数据中心网络RDCN的g-外连通度为(g+1)(kδ-1)+n，这一结果近于其连通度的g+1倍。3.研究了特殊的递归型数据中心网络DCell上的故障直径的上界；研究了与递归性数据中心网络具备相似递归构造特征的交错立方体、WK-递归图、交换群图、局部扭立方体等网络结构上的容错性能问题。4.进行模拟实验和应用研究，研究了递归型数据中心网络RDCN上的容错单播路由算法，分析了算法的时间复杂度，证明了算法在最坏情况下构造出的最长路径长度的上界，完成了模拟程序的设计和验证。本项目的研究成果对新型数据中心网络拓扑结构的应用具有重要的理论和实践指导意义。