学位论文 > 优秀研究生学位论文题录展示

关于几种网络的可靠性研究

作　者: 武燕
导　师: 魏暹荪
学　校: 陕西师范大学
专　业: 应用数学
关键词: (l,k)控制数限制连通度限制容错直径金字塔网蝶形网
分类号: O157.5
类　型: 硕士论文
年　份: 2003年
下　载: 206次
引　用: 1次
阅　读: 论文下载

内容摘要

互连网络拓扑结构是计算机系统或者通信系统中元件之间的连接方式，它是决定该系统性能的重要因素之一。对网络拓扑结构进行系统的量化研究和分析是信息科学中近十几年才发展起来的新的研究领域，组合数学是研究和分析网络拓扑结构的公认的最有力的数学工具之一，特别是图论概念与方法在网络有效性与容错性的分析中发挥了重要作用。随着对网络拓扑结构的深入研究和分析，一批图论的新概念，新参数应运而生，用这些概念和参数可以更准确的度量网络有效性与容错性。在容错网络中，结点和(或)连线的失灵会导致数据传输延迟的增加，为了度量故障点带来的影响，即在故障网络中的最大传输延迟，提出一个新的度量参数——容错直径。在并行计算系统的网络中，信息是通过若干条内点不交的路径平行地进行传输。对于这样的网络，仅孤立的考虑连通度和直径是不够的，因为网络虽然有大连通度和小直径，但通过该网络中的若干条内点不交的路并行传输信息时，其中某些路径可能很长，因而传输延迟大，信息到达时间间隔很大，影响整个系统的有效性，因此需要将连通度与直径综合考虑，于是提出了宽直径的概念。另外在资源共享的并行系统网络中，提出了新的参数——(l，k)控制数。在利用上述参数分析网络时，我们假定系统组件中的任何子集都会同时发生故障，然而，在某些网络中可以安全的假定网络组件中的某些子集不会同时失灵，对于这样的网络，经典的连通度不能精确度量其容错性，因此提出了限制连通度，限制边连通度，限制容错直径等参数，可以更准确地分析各种互连网络的可靠性。因此本文就格网、金字塔网、蝶形网对上述几种参数进行了研究。这三种网络都被广泛用于并行计算系统，有很大的研究和应用价值。本文的主要工作为：第一章作为预备知识，首先给出在下面各章将要用到的一些图论概念，术语和基本定理，然后简单介绍了几个最基本的网络结构，最后着重介绍了度量互连网络的有效性与容错性的几个参数以及研究进展情况。第二章讨论格网的宽直径与(l，k)控制数。首先介绍了格网的定义。其次由笛卡尔乘积图的性质给出格网的直径与连通度。然后由任意两点间的多条内点不交路给出格网的宽直径与(l，k)控制数。第三章讨论金字塔网的有效性与容错性。金字塔网是并行计算，网络计算，图像处理的一种重要的网络拓扑结构．本文在这一章首先介绍了金字塔网的定义，并由其定义给出金字塔网的递归结构，在下面各节中，多次用到这一结构．其次讨论根到其他点的宽距离，并由此给出金字塔网的（l，k）控制数．然后给出了超K图的定义，并讨论了金字塔网的超K图性质，由此得到金字塔网的限制连通度．接着对于有故障点的金字塔网。文章通过构造性算法给出限制容错直径的证明．最后讨论了金字塔网的超入图性质，给出了其限制边连通度．第四章讨论蝶形网的有效性与容错性．介绍了蝶形网的定义，用构造性方法给出任意两点间的宽距离，由此得到队k）控制数，此外在限制故障集下，分情况讨论了任意两点间的容错距离，得出了限制容错直径的上界．

全文目录

前言  7-9
第一章互连网络与图论  9-14
  1.1 图的基本概念  9-10
  1.2 几个常用的网络拓扑结构  10
  1.3 网络有效性与容错性  10-14
第二章 n维格网的宽直径与(l，k)控制数  14-17
  2.1 引言  14
  2.2 n维格网的连通度，直径，宽直径与(l，k)控制数  14-17
第三章金字塔网  17-28
  3.1 引言  17-18
  3.2 金字塔网的(l，k)控制数  18-20
  3.3 金字塔网的限制连通度和限制容错直径  20-24
  3.4 金字塔网的限制边连通度  24-28
第四章蝶形网  28-45
  4.1 引言  28
  4.2 蝶形网的(l，k)控制数  28-32
  4.3 蝶形网的限制容错直径  32-45
总结  45-46
致谢  46-47
参考文献  47-49
攻读硕士学位期间的研究成果  49

关于几种网络的可靠性研究

内容摘要

全文目录

相似论文