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

发布时间：2017-04-28 15:14

  本文关键词：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除外)和哈密顿的(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证明了本文的研究成果,可以为新型数据中心网络的设计提供理论依据。
【关键词】：数据中心网络 DCell网络 哈密顿性质 不交路径覆盖 限制连通性
【学位授予单位】：苏州大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5;TP308
【目录】：

• 摘要4-6
• Abstract6-11
• 第一章 绪论11-23
• 1.1 研究背景11
• 1.2 云计算11-13
• 1.3 数据中心网络13-18
• 1.4 研究意义18-20
• 1.5 研究内容20-21
• 1.6 文章组织结构21-23
• 第二章 相关知识23-29
• 2.1 基本概念和符号表示23-26
• 2.2 DCell网络及其基本性质26-28
• 2.3 本章小结28-29
• 第三章 DCell网络上的哈密顿性质29-42
• 3.1 DCell网络上的哈密顿性质29-33
• 3.2 DCell网络上的容错哈密顿性质33-41
• 3.3 本章小结41-42
• 第四章 DCell网络上的不交路径覆盖42-79
• 4.1 DCell网络上的一对一不交路径覆盖42-54
• 4.2 DCell网络上的一对一不交路径覆盖算法54-59
• 4.3 DCell网络上的一对多不交路径覆盖59-69
• 4.4 DCell网络上的多对多不交路径覆盖69-78
• 4.5 本章小结78-79
• 第五章 DCell网络上的限制连通性79-98
• 5.1 辅助引理79-81
• 5.2 DCell网络上的限制连通性81-97
• 5.3 本章小结97-98
• 第六章 总结与展望98-101
• 6.1 总结98-99
• 6.2 展望99-101
• 参考文献101-115
• 攻读博士学位期间发表的论文和参与的科研项目115-117
• 致谢117-119

【相似文献】

中国期刊全文数据库 前10条

1 杨克昌;刘志辉;;马步哈密顿圈[J];电脑编程技巧与维护;2011年09期

2 殷超杰;郭大昌;郑健微;;条件点错误情况下交叉立方体中哈密顿圈的存在性讨论[J];广东工业大学学报;2012年03期

3 邓汉元,陈雪生;关于C_r懔C_n的Hamilton分解[J];湖南师范大学自然科学学报;2000年03期

4 ;范更华教授荣获2005年度国家自然科学奖二等奖──“哈密顿圈及圈覆盖理论”[J];福州大学学报(自然科学版);2006年01期

5 韩雪涛;;好玩的数学——哈密顿圈[J];科技导报;2008年13期

6 郭海宽;;故障3-元n-立方体的哈密顿圈嵌入[J];山西大学学报(自然科学版);2013年02期

7 陆生勋;产生一个任意图的所有哈密顿圈的一种方法[J];杭州大学学报(自然科学版);1980年01期

8 张福基,郭晓峰;哈密顿圈的H-变换[J];数学杂志;1983年04期

9 关亚东;杨文学;赵星寒;;由邻接L矩阵生成图的全部哈密顿圈[J];吉林化工学院学报;1987年03期

10 刘春峰,梁怀学;线图中的哈密顿圈[J];松辽学刊(自然科学版);1988年02期

中国重要会议论文全文数据库 前1条

1 敖丽敏;马昭彦;冯朝阳;;关于最少分叉树的一个定理及其证明[A];“电力大系统灾变防治和经济运行重大课题”部分专题暨第九届全国电工数学学术年会论文集[C];2003年

中国硕士学位论文全文数据库 前10条

1 潘瑞霞;图的哈密顿[a，，b]-因子的若干结果[D];山东大学;2009年

2 王超;图的哈密顿（g，f）-因子[D];山东大学;2010年

3 蔺厚元;（K_（1，4）；2）-图的哈密顿性[D];山东师范大学;2005年

4 张巧莲;关于“3.3.4.3.4”铺砌相关性质的研究[D];河北师范大学;2011年

5 鲍奇;一类网络图的容错哈密顿性和容错哈密顿连通性研究[D];清华大学;2009年

6 何东红;一类图的哈密顿染色[D];河北工业大学;2007年

7 李雪;一类毛毛虫图的哈密顿染色[D];河北工业大学;2007年

8 潘学军;关于图的哈密顿因子的若干结果[D];山东大学;2006年

9 何剑;度条件与过线性森林的圈[D];华中师范大学;2009年

10 郑振;折纸术链环的构筑与拓扑性质研究[D];兰州大学;2011年

  本文关键词：DCell网络上的路径覆盖和限制连通性研究，由笔耕文化传播整理发布。

本文编号：333066