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

可伸展多级分组交换网络结构的研究

作　者: 陈震
导　师: 刘增基
学　校: 西安电子科技大学
专　业: 通信与信息系统
关键词: 分组交换交换网络可扩展性可伸展性多级网络标记路由算法流量均衡
分类号: TN915.02
类　型: 博士论文
年　份: 2004年
下　载: 214次
引　用: 4次
阅　读: 论文下载

内容摘要

为了适应通信业务流量与日俱增的需要，当前的路由器和交换机工程实践强调交换网络具有可扩展性。解决可扩展性有两种基本途经：一种是提升单级交换单元的交换容量，但是由于工程实现的限制，单级交换单元的交换容量不可能很大；另一种途径是采用由多个交换单元构成连接网络的方法来实现一个更大规模的交换网络，这是目前可扩展交换网络最常用的解决方案。当前大型交换网络的连接网络拓扑主要采用多级网络，其中以三级Clos网络(C3)最为常用。本文首先研究三级Clos网络的广义无阻塞条件，三级Clos网络上的Evil-Twin随机路由算法，给出了h—关系流量条件下三级Clos网络上的简单随机路由算法的理论性能分析，然后研究分组交换的MSM结构(Memory-Space-Memory)实现的三级Clos网络的概率无阻塞条件和平均时延，以及SSS结构(Space-Space-Space，S3)实现的三级Clos网络的吞吐特性。但是工程实际需求的交换网络的端口数目可能是任意的，而采用基本交换单元构建的Clos网络拓扑是一种固定的拓扑，往往不能充分利用很多交换单元，这意味着更高的成本和复杂性。针对Clos网络拓扑缺乏足够的伸展性、不够灵活的问题，提出多级网络的可伸展性问题。研究表明，存在两类多级网络是可伸展的，其级间连接模式分别为模加减和混洗连接。首先研究以2×2交换单元为基本交换单元、级间连接模式为模加减的Banyan网络，称为P2I网络和PN2I网络，接着将其推广至PkI网络。最后研究级间连接模式为混洗连接的多级网络，即广义混洗网络(Generalized Shuffle-Exchange Networks，GSEN)和广义Delta网络(Generalized Delta Networks，GDN)。在可伸展的多级网络的研究中，遇到的主要问题是：可伸展的多级网络在其网络端口数目为整数的幂次时，其网络拓扑具有最好的对称性(简称为幂次网络或完全网络)，标记路由算法简单、易于实现，因而具有良好的性能。随着网络的伸展，网络端口数目不再是整数的幂次时，原来适用于完全网络的标记路由算法可能不再适用，需要采用新的标记路由算法。另外，此时网络结构的对称性要比完全网络差，在均匀到达、目的地址为均匀分布的注入业务流条件下，采用适用于完全网络的标记路由算法将导致非完全网络内部链路流量的不均衡，为此提出了新的流量均衡的平衡标记路由算法。通过理论分析和仿真实验表明，流量均衡的平衡标记路由算法可以有效的改善非完全网络的时延吞吐性能，使之具有完全网络的性能。概括的讲，本文的主要工作和贡献包括以下几个方面： 1．研究了三级Clos网络的广义无阻塞条件，采用启发式搜索算法得到其必要条件。研究了三级Clos网络上的Evil-Twin随机路由算法，证明了Evil-Twin置换和西女【匕子科技大学博士学位论文:可仲展多级分组交换网络结构的研究拉丁矩阵之间的密切关系，并相应给出了Evi卜Twin置换的构建方法。给出了在h一关系流量条件下，三级CloS网络上的随机路由算法的理论性能分析。分析了分组交换MSM结构实现的三级C10s网络的概率无阻塞条件和平均时延，以及555结构实现的三级Clos网络的吞吐率。针对Clos网络拓扑缺乏伸展性，不够灵活的缺点，提出了多级网络的可伸展性的概念。2.提出了级间连接模式基于模加减的一类可伸展多级网络:PZI网络、PNZI网络以及Pkl网络。提出了这类网络上的基于数的进制表示的标一记路由算法，并分析了这类网络的结构属性。发现这类网络在网络端口数目不是整数的幂次时，该标记路由算法将导致网络内部链路流量不均衡的问题。为此，提出了新的流量均衡的平衡标记路由算法，并证明了其正确性。仿真实验结果表明平衡标记路由算法有效地改善了网络性能。3.研究了另外一类基于混洗连接模式的可伸展多级网络:广义混洗网络和广义 Dclta网络。同样的，广义混洗网络和广义Delta网络在网络端口数目不是整数的幂次的情况下，原路由算法也将导致网络内部链路流量不均衡的问题。为此，提出了新的流量均衡的平衡标记路由算法，通过仿真实验表明平衡标记路由算法有效地改善了网络性能。研究了单向和双向广义混洗网络的标记路由算法，提出了双向广义混洗网络的后向网络的标一记路由算法。4.研究了三级广义Delta网络(D3)。三级广义Delta网络是三级CloS网络的一个直接推广。其网络端口数目可以按需构建，因而具有更好的灵活性。在均匀到达、目的地址为均匀分布的注入业务流条件下，仿真分析表明采用平衡标记路山算法的三级GDN网络与相同端口数目的三级CloS网络具有同等的性能。同时，研究了三级GDN网络的具体实现问题。研究表明，三级GDN网络是设计端口数目为任一整数的倍数的交换网络实际可行的候选方案。关键词:分组交换交换网络可扩展性可伸展性多级网络标记路由算法流量均衡

全文目录

第一章绪论  11-29
  1．1 交换网络概述  11-26
    1．1．1 交换网络的地位和作用  11-12
    1．1．2 分组交换网络的演进  12-17
      1．1．2．1 交换网络结构方面  12-13
      1．1．2．2 物理实现方面  13-14
      1．1．2．3 高速互连通信技术  14-17
    1．1．3 当前大容量分组交换网络  17-20
      1．1．3．1 多平面单级无缓存交换结构  17-18
      1．1．3．2 多平面单级缓存交换结构  18-19
      1．1．3．3 多平面多级交换结构  19-20
    1．1．4 交换网络的技术发展趋势  20-26
      1．1．4．1 交换网络结构的可扩展性  21-23
      1．1．4．2 交换网络接口的标准化  23-25
      1．1．4．3 交换网络的基准测试(Benchmark)  25-26
  1．2 本文的研究思路与安排  26-29
第二章三级Clos网络的研究  29-59
  2．1 引言  29
  2．2 三级Clos网络的广义无阻塞条件  29-38
    2．2．1 简介  29-32
    2．2．2 三级Clos网络的广义无阻塞条件的一些具体结论  32-33
    2．2．3 有限自动机理论基础  33-34
    2．2．4 广义无阻塞三级Clos网络的有限自动机模型  34-35
    2．2．5 广义无阻塞条件的启发式探索算法  35-38
      2．2．5．1 “力迫”算法实现  35-37
      2．2．5．2 数值结果  37-38
  2．3 分组交换Clos网络内部的路由算法  38-48
    2．3．1 三级Clos网络的Evil-Twin随机置换路由算法  38-43
      2．3．1．1 简介  38-39
      2．3．1．2 分析  39-42
      2．3．1．3 应用  42-43
    2．3．2 三级Clos网络的随机化路由算法  43-48
      2．3．2．1 简介  43-44
      2．3．2．2 性能分析  44-48
      2．3．2．3 结论  48
  2．4 分组交换三级Clos网络的性能分析  48-56
    2．4．1 假定  49
    2．4．2 MSM结构的三级Clos网络V(m，n，r)的性能分析  49-54
      2．4．2．1 概率无阻塞条件分析  49-50
      2．4．2．2 平均传送时延分析  50-54
    2．4．3 SSS结构的三级Clos网络V(m，n，r)的性能分析  54-56
  2．5 Clos网络的可伸展性问题  56-57
  2．6 本章内容小结  57-59
第三章一类可伸展的Banyan网络  59-83
  3．1 一种可伸展的Banyan网络：P2I网络  59-67
    3．1．1 简介  59-60
    3．1．2 P2I网络  60-62
      3．1．2．1 P2I网络的定义  60-61
      3．1．2．2 P2I网络的简单标记路由算法  61-62
      3．1．2．3 结构特性  62
    3．1．3 P2I网络的性能分析  62-63
      3．1．3．1 内部链路使用概率  62-63
      3．1．3．2 数学建模  63
    3．1．4 P2I网络性能的仿真分析  63-65
    3．1．5 新的标记路由算法—平衡标记路由算法  65-67
  3．2 一种可伸展的Banyan网络：PN2I网络  67-74
    3．2．1 简介  67
    3．2．2 PN2I网络  67-70
      3．2．2．1 PN2I网络的定义  67-68
      3．2．2．2 PN2I网络的简单标记路由算法  68-70
    3．2．3 PN2I网络的理论性能分析  70
      3．2．3．1 PN2I网络的内部链路使用概率  70
      3．2．3．2 PN2I网络性能分析的数学模型  70
    3．2．4 平衡标记路由算法  70-72
    3．2．5 仿真性能分析  72-74
  3．3 一种新的多级连接网络-PkI网络及其路由算法的研究  74-82
    3．3．1 简介  75-76
    3．3．2 PkI网络  76-77
      3．3．2．1 PkI网络的定义  76
      3．3．2．2 简单标记路由算法  76
      3．3．2．3 PkI网络中流量不平衡现象  76-77
    3．3．3 解决方法  77-80
      3．3．3．1 数学描述  77-78
      3．3．3．2 矩阵分析的Moore-Penrose逆  78
      3．3．3．3 一个实例  78-80
    3．3．4 P3I网络的仿真性能分析  80-82
  3．4 本章内容小结  82-83
第四章广义混洗网络  83-97
  4．1 单向广义混洗网络的流量均衡路由算法  83-89
    4．1．1 简介  83
    4．1．2 单向广义混洗网络的定义和路由算法  83-84
    4．1．3 广义混洗网络中流量不平衡现象  84-85
    4．1．4 解决方法  85-87
      4．1．4．1 数学描述  85-86
      4．1．4．2 矩阵分析的Moore-Penrose逆  86
      4．1．4．3 一个实例  86-87
    4．1．5 GSEN(3，5，3)网络的仿真性能分析  87-89
  4．2 双向广义混洗网络以及标记路由算法  89-95
    4．2．1 简介  89-90
    4．2．2 背景  90-91
      4．2．2．1 数论基础知识  90
      4．2．2．2 双向广义混洗连接网络  90-91
    4．2．3 广义混洗网络中的标记路由算法  91-95
  4．3 本章内容小结  95-97
第五章三级广义Delta网络  97-115
  5．1 广义Delta网络(GDN)  97-100
    5．1．1 广义Delta网络的定义  97-98
    5．1．2 广义Delta网络的路由算法  98-99
    5．1．3 三级广义Delta网络的等效表示  99
    5．1．4 随机路由算法引起的内部链路拥塞问题  99-100
  5．2 随机均衡路由算法  100-105
  5．3 仿真分析  105-113
  5．4 三级广义Delta网络的可行性讨论  113
  5．5 三级广义Delta网络的可均衡性讨论  113-114
  5．6 本章内容小结  114-115
第六章总结  115-119
  6．1 本文的主要贡献  115-116
  6．2 有待进一步研究的工作  116-119
    6．2．1 可伸展多级网络框架的理论问题  116-117
      6．2．1．1 通信流量模式的问题  116-117
      6．2．1．2 多播问题  117
      6．2．1．3 多级网络的QoS保证的问题  117
      6．2．1．4 乱序问题  117
    6．2．2 可伸展多级网络的具体实现问题  117
    6．2．3 交换网络和整个数据网络的互动问题  117-119
致谢  119-121
参考文献  121-131
作者在攻读博士学位期间完成的论文和工作  131-132

可伸展多级分组交换网络结构的研究

内容摘要

全文目录

相似论文