为了适应通信业务流量与日俱增的需要，当前的路由器和交换机工程实践强调交换网络具有可扩展性。解决可扩展性有两种基本途经：一种是提升单级交换单元的交换容量，但是由于工程实现的限制，单级交换单元的交换容量不可能很大；另一种途径是采用由多个交换单元构成连接网络的方法来实现一个更大规模的交换网络，这是目前可扩展交换网络最常用的解决方案。当前大型交换网络的连接网络拓扑主要采用多级网络，其中以三级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网 络是设计端口数目为任一整数的倍数的交换网络实际可行的候选方案。关键词:分组交换交换网络可扩展性可伸展性多级网络标记路由算法 流量均衡