论文部分内容阅读
随着社会信息化的发展,计算机应用深入到了各个行业,网络资源和数据规模不断扩大。在这样的背景下,云计算(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除外)和哈密顿的(Do,2除外)。(2)给出了构造Dk,n上任意两个不同顶点间一条哈密顿路径的O(tk,n)算法,其中tk,n为Dk,n的顶点数。(3)证明了Dk,n是(n+k-4)-哈密顿连通的和(n+k-3)-哈密顿的。2.研究了DCell网络的不交路径覆盖问题:(1)对于任意的整数1证明了Dk,n是一对一r-不交路径覆盖的(D1,2除外)。,(2)对于任意的整数1给出了构造Dk,。上一个一对一r-不交路径覆盖的O(tk,n)算法,并分析了这些不交路径中最长路径长度的上界。(3)证明了Dk,n是一对多(n+k-2)-不交路径覆盖的(D1,2除外)。(4)对于任意的整数1证明了Dk,n是多对多r-不交路径覆盖的(D1,2除外)。3.研究了DCell网络的限制连通性:若Dk,n上每个无故障顶点存在至少h个无故障邻居,则基于该条件下的Dk,n的连通度可定义为限制h-连通度(用kh(Dk,n)表示)。(1)对于任意的整数k≥1以及证明了(2)对于任意的整数k≥2以及n证明了本文的研究成果,可以为新型数据中心网络的设计提供理论依据。