超立方体变形网络容错性研究

论文摘要

互连网络在并行计算与通信系统中起着重要作用。而互连网络可以用无向图G=（V,F）表示,其中图G中的每个节点对应于互连网络的处理器,并且图G中的每条边对应于互连网络的通信链路。随着多处理器系统中故障节点数量的增加,互连网络可能会崩溃。因此,通过区分故障节点和无故障节点来保持互连网络的可靠性是非常重要的。而网络的容错性是互连网络性能的一个重要指标,它主要是指在网络发生故障时系统某些特性的保持能力。其中点连通度,边连通度和诊断度是度量网络容错性能的几个重要参数。人们定义点连通度和边连通度的时候都是假定系统的任何部件都可能会同时失灵,这在实际应用中可能并不准确,因此他们不能准确评估网络的可靠性。为了克服这一缺点,引入了g-限制连通度和g-好邻诊断度的概念。S是系统G的点割,且G-S的任一点都至少有g个邻点,把S的最小点割数定义为G的g-限制连通度,这一参数比传统连通度更能准确地测量互连网络的容错性。而g-好邻诊断度是指在每个节点至少有g个好邻点的情况下,系统最多能诊断出的错误节点的个数。g-好邻诊断度相较于经典诊断度具有更好的连通性和诊断能力。本文用图论知识研究了系统发生故障时网络保持的三种能力:g-限制点连通度,g-限制边连通度和g-好邻诊断度。超立方体（Hypercube）是较早出现的一种网络,它的优点是高对称性,高容错性,优良的嵌入性,以及简单的路由算法,是目前研究最多的网络之一。但根据不同的网络设计要求,人们对超立方网络进行了变形,形成了一些变形的立方网络结构:分层立方网络,（n,k）-星图网络等。本文研究了这两种网络的容错参数,为网络设计者提供了更加详细的容错信息。为了确定分层立方网络,（n,k）-星图的g-好邻诊断度,本文采用Preparata,Metzem和Chien提出的PMC模型和Sengupta和Dahbura提出的MM*模型。本文第一章介绍了系统的容错概念以及文章用到的图论基础知识。本文第二章主要分析了分层立方网络n-HHC的容错能力。通过推导得到了n-HHC网络的g-限制（边）连通度的具体值Kg（n-HHC）-λg（n-HHC）=2g（m+1-g）,并确定了在PMC模型和MM*模型下分层立方网络n-HHC的g-好邻诊断度均为tg（n-HHC）=2g（m+ 2-g）-1,其中1≤g≤m-1,m≥2,n=2w+m。这为网络的设计提供了更详细的参考。本文第三章主要研究了（n,k）-星图网络Sn,k的容错参数-超（边）连通度。2≤k≤n-1,当0≤g≤n-k时,Li和Xu得到了Kg（Sn,k）=n+g（k-2）-1,以及当g≤min｛k-2,n/2-1｝时,λg（Sn,k）=（n-g-1）（g+1）;当g>min｛k-2,n/2-1｝时,λg（Sn,k）=（n-g+1）（g-1）在这一章我们将通过推导得到当n-k+1≤g≤n-2时,kg（Sn,k）=λs（g）（Sn,k）=（n+1）!（n-g-1）/（n-k）!。Wei和Xu等人以此为依据,推导出了在PMC模型和MM*模型下（n,k）-星图网络的g-好邻诊断度。为网络设计者们提供了参考。

论文目录

• 摘要
• abstract
• 主要符号对照表
• 第1章 绪论
•   1.1 互连网络与图
•   1.2 图论的预备知识
•   1.3 研究背景及现状
•     1.3.1 PMC模型
•     1.3.2 MM*模型
•     1.3.3 诊断度
• 第2章 分层立方网络的容错性分析
•   2.1 分层立方网络
•   2.2 PMC模型下分层立方网络的g好邻诊断度
•   2.3 MM*模型下分层立方网络的g好邻诊断度
•   2.4 本章小结
• 第3章 （n,k）-星图的容错性研究
•   3.1 背景介绍
•   3.2 几种网络的定义和引理
• n,k网络的超（边）连通度以及g好邻诊断度'>  3.3 S_n,k网络的超（边）连通度以及g好邻诊断度
•   3.4 本章小结
• 第4章 总结
• 致谢
• 参考文献
• 个人简介

文章来源

类型: 硕士论文

作者: 关咏妮

导师: 李向军

关键词: 互连网络,容错,限制连通度,好邻诊断度

来源: 长江大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 长江大学

分类号: O157.5

总页数: 50

文件大小: 1613K

下载量: 18