DCell网络上的路径覆盖和限制连通性研究

摘要

随着社会信息化的发展，计算机应用深入到了各个行业，网络资源和数据规模不断扩大。在这样的背景下，云计算(Cloud Computing)迅速兴起。近年来，云计算的发展已经上升到包含美国在内的多个国家的国家战略层面。云计算本质上是一种资源按需分配的模式。它的一个核心理念就是通过不断提高“云”端的处理能力，进而减轻终端用户的处理负担，而将绝大部分计算放在“云”端，由大型数据中心网络来完成。作为云计算的基础设施和下一代网络技术的创新平台，数据中心网络的研究已经成为近年来学术界和工业界关注的热点。
　　数据中心网络可以表示为一个简单图G=(V(G)，E(G))，我们用V(G)和E(G)分别表示图G中的顶点集合和边集合，顶点和边分别表示数据中心网络中的服务器和连接服务器的链路，而交换机可被认为是透明的网络设备。数据中心网络拓扑结构的性质对于数据中心网络的性能至关重要。
　　网络中的哈密顿性质在信息通信中具有重要的应用。如果在数据中心网络的多播路由算法中使用哈密顿路径或哈密顿圈，则能够有效地减少或避免死锁和拥塞。哈密顿性质可以被看作是不交路径覆盖性质的一个特例，例如，一对一、一对多、多对多1-不交路径覆盖问题即哈密顿连通性问题，而一对一2-不交路径覆盖问题即哈密顿图问题。
　　网络的不交路径覆盖已经被广泛应用于数据库设计，VLSI设计，代码优化，无线传感器网络的拓扑控制，以及软件测试。在数据中心网络中，不交路径覆盖能够有效地提高数据收集或数据分发效率。例如，在数据中心网络中使用不交路径覆盖进行数据收集（从所有服务器中收集数据）或数据分发（分发数据到所有服务器上），我们仅需访问数据中心网络中每台服务器一次。
　　随着数据中心网络的规模不断扩大，服务器发生故障的情形是不可避免的，使用限制连通度能够更加精确地度量数据中心网络的容错性。因此研究数据中心网络的限制连通度是一个重要的课题。
　　DCell网络是一种重要的数据中心网络，它具有较好的路由性能和高扩展性，且能很好地支持一对多和多对多等网络通信服务，并能够支持超大规模的数据中心网络。
　　本文研究DCell网络（Dk，n，其中k≥0且n≥2）的哈密顿性质，不交路径覆盖问题，以及限制连通性，具体研究成果如下:
　　1.证明了DCell网络具有很好的哈密顿性质:
　　(1)证明了Dk,n是哈密顿连通的（D1,2除外）和哈密顿的（D0,2除外）。
　　(2)给出了构造Dk,n上任意两个不同顶点间一条哈密顿路径的O(tk，n)算法，其中tk，n为Dk,n的顶点数。
　　(3)证明了Dk,n是(n+k-4)-哈密顿连通的和(n+k-3)-哈密顿的。
　　2.研究了DCell网络的不交路径覆盖问题:
　　(1)对于任意的整数1≤r≤n+k-1，证明了Dk,n是一对一r-不交路径覆盖的（D1,2除外）。
　　(2)对于任意的整数1≤r≤n+k-1，给出了构造Dk,n上一个一对一r-不交路径覆盖的O(tk，n)算法，并分析了这些不交路径中最长路径长度的上界。
　　(3)证明了Dk,n是一对多(n+k-2)-不交路径覆盖的（D1,2除外）。
　　(4)对于任意的整数1≤r≤(「)(n+k-1）/2」，证明了Dk,n是多对多r-不交路径覆盖的（D1,2除外）。
　　3.研究了DCell网络的限制连通性:
　　若Dk,n上每个无故障顶点存在至少h个无故障邻居，则基于该条件下的Dk,n的连通度可定义为限制h-连通度(用kh(Dk,n)表示）。
　　(1)对于任意的整数k≥1以及0≤h≤n-1，证明了kh(Dk,n)=（h+1）（k-1）+n。
　　(2)对于任意的整数k≥2以及n≤h≤n+k-2，证明了kh(Dk,n)=(n+k-h-1)th-n+1，n。
　　本文的研究成果，可以为新型数据中心网络的设计提供理论依据。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 云计算

1．3 数据中心网络

1．4 研究意义

1．5 研究内容

1．6 文章组织结构

第二章 相关知识

2．1 基本概念和符号表示

2．2 DCell网络及其基本性质

2．3 本章小结

第三章 DCell网络上的哈密顿性质

3．1 DCell网络上的哈密顿性质

3．2 DCell网络上的容错哈密顿性质

3．3 本章小结

第四章 DCell网络上的不交路径覆盖

4．1 DCell网络上的一对一不交路径覆盖

4．2 DCell网络上的一对一不交路径覆盖算法

4．3 DCell网络上的一对多不交路径覆盖

4．4 DCell网络上的多对多不交路径覆盖

4．5 本章小结

第五章 DCell网络上的限制连通性

5．1 辅助引理

5．2 DCell网络上的限制连通性

5．3 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

攻读博士学位期间发表的论文和参与的科研项目

致谢