一种新型多级可扩展交换网络-revised-05-09.doc

一种新型多级可扩展交换网络陈一骄基金项目：本论文受国家高技术研究发展计划(863) No.2008AA01A323 和(863)No.2008AA01A325资助作者简介：陈一骄，1972年9月生，男，副研究员，主要研究方向为高性能路由器及网络安全；汤庆新其他作者职称/学位，硕士研究生。 E-mail： 汤庆新（国防科学技术大学 计算机学院,湖南 长沙 410073）摘 要：本文提出了一种新型多级可扩展交换网络。论文在建立该交换网络逻辑结构模型的基础上，首先对该交换网络进行了形式化描述，并说明了其扩展方式。然后，通过分析该交换网络通信链路间的竞争，说明定量地描述了该交换网络的端口间可达性、无阻塞条件，证明了其和可靠性。最后通过与单级Crossbar交换网络、传统3级Clos交换网络的定量对比，证明在同等容量下该交换网络的结构复杂性最低。关键词：交换网络；多级；可扩展；复杂度A Novel Scalable Multiple-Stage Switching FabricChen Yi-jiao Tang Qing-xin(School of Computer Science and Technology, National of Defense Technology, Changsha 410073, China)Abstract: A novel scalable multiple-stage switching fabric is proposed in this paper. Firstly, the architecture logical model of the switching fabric is built up. Based on the modelAnd then, the method of fabric upgrading is described while the formal description of the fabric is given. Secondly, by analyzing the competition of links, the neighbouring connectivityof the fabric，the no-blocking condition and the reliability of the fabric are describedexplained. Lastly, it is proved that the structure complexity of the fabric is lowest compared to the Crossbar fabric and the custom three-stage Clos network.Key words: Switching fabric; Multiple-stage; Scalable; Complexity1. 概述随着网络业务的迅猛增长和光传输技术的成熟，路由器等网络节点的性能对整个网络性能的瓶颈限制日益凸显。高速交换网络是路由器的重要组成部分，其容量、可扩展性、可靠性等因素直接影响路由器的性能及使用灵活性12。单级Crossbar交换网络是目前路由器采用较多的一种交换网络，但其复杂度与端口数的平方成正比，工程实现上受限于芯片体积等因素，其容量不可能做到很大3。于是多级交换结构网络很自然地被引入成为以构建大容量分组交换网络的常用结构。直接连接交换网络3和间接连接交换网络3是空分多级交换网络的两种主要结构类型。由于存在重负载情况下性能难以保证、工程实现难度大等缺陷，以3D Torus交换网络和超立方体交换网络3为代表的直接相连交换网络仅在大容量交换网络研究的初期得到了一定的发展。相比直接连接交换网络，即使在重负载情况下，间接连接交换网络的性能也能得到较好的保证，在网络流量急剧增长的背景下，间接连接交换网络成为构建大容量交换网络的首选。但是以3级Clos交换网络3等为代表的间接连接交换网络也存在可扩展性差(扩展粒度大)、调度机制复杂等缺陷需要改进。在保证交换网络性能的前提下，为提高其以较小粒度进行扩展的能力，同时保证网络复杂度不因规模扩展而激增，本文提出一种新型多级可扩展交换网络。论本文在建立该交换网络逻辑结构模型的基础上，对其该交换网络的可靠性、端口间可达性、无阻塞条件、结构复杂度等进行了分析证明。2. 多级可扩展交换网络的逻辑结构模型2.1 结构模型如图1所示，本文提出的多级可扩展交换网络由3级组成：输入级由P个带缓存的交换单元b-ISU(buffered Input Switch Unit)构成；中间级由4个非缓存的(Q=3P/4)核心交换单元u-CSU(unbuffered Core Switch Unit)构成；输出级由P个带缓存的交换单元b-OSU(buffered Output Switch Unit)构成。b-ISU分为4组，组编号依次为0,1,2,3，每组b-ISU的数目为P/4个；b-OSU分为4组，组编号依次为0,1,2,3，每组b-OSU的数目为P/4个；4个u-CSU依次编号为0,1,2,3。图1 交换网络逻辑结构图如图2所示，对于所在组编号为X的b-ISU-H，其3个输出端口与编号为X、(X+1)%4、(X+2)%4的u-CSU间各有一条链路；对于所在组编号为Y的b-OSU-I，其3个输入端口与编号为Y、(Y+1)%4、(Y+2)%4的u-CSU间各有一条链路。每个b-ISU将其输入端口流入的数据分组分流到其连接的3个u-CSU，u-CSU将数据分组交换至其目的端口所在的b-OSU，数据分组在b-OSU完成排序等操作后从输出端口离开交换网络。图2 链路连接示意图根据实际应用对网络流量等交换网络容量的要求，本文提出的交换网络可灵活配置自身的规模，。以只配置一半的容量为例：。在这种配置模式下，网络由P/2个b-ISU、P/2个b-OSU和2个u-CSU组成。每个(=3P/4)u-CSU视为2个 (=3P/8)的u-CSU，P/2个b-ISU和P/2个b-OSU同样分为四组，依据上文所述图2进行链路配置，保证交换网络扩展时可以利用现有资源。如需将一个配置了一半容量的交换网络扩展到全容量模式，只需增加相应的b-ISU和b-OSU数目并同比例增加u-CSU的交换端口的数量，对b-ISU等重新分组编号，然后配置相应链路，就可以实现交换网络容量的扩展调整，从而在保持整个交换网络体系结构稳定性的基础上适应应用新业务对交换网络容量吞吐率的要求，大大降低了扩展网络规模的难度。2.2 形式化描述为方便对该交换网络连通性、端口间可达性（交换线路数）和无阻塞条件等的分析，做如下定义：定义1 将第i个b-ISU的2个输入端口分别记为和(i=1,2,.,P)，3个输出端口分别记为、和；将第j个b-OSU的3个输入端口分别记为、和(j=1,2,.,P)，2个输出端口分别记为和；将第k个u-CSU的3P/4个输入端口和3P/4个输出端口分别定义为和 (a=1,2,3P/4;b=1,2，3P/4;k=1,2,3,4)。定义2 将端口V的左邻端口集记为L(V)，右邻端口集记为R(V)，根据图1，可得式 (1)、式(2)，其中式(1)为各端口的左邻端口集，式(2)为各端口的右邻端口集： (1) (2)计算式(1)和式(2)中集合包含元素的个数，即各端口左邻端口和右邻端口的数目，得式(3)、式(4)： (3) (4)定义3将端口到( i=1,2，P;j=1,2，P;a=1,2;f=1,2)的交换线路集记为LR(,)。对任意rRL，r=,。定义4 定义端口间可达性(交换线路数)如下：l 不通：一个b-ISU和一个b-OSU间没有交换线路；l 单链路：一个b-ISU和一个b-OSU间只有一条交换线路；l 双链路：一个b-ISU和一个b-OSU间有两条交换线路；l 冗余链路：一个b-ISU和一个b-OSU间有三条交换线路。3. 性能分析3.1 端口间可达性、无阻塞条件对于端口和端口，若#L(,)大于0，则两端口间具有可达性； L(,)包含的元素数目越多，即两端口间交换线路数目越多，则两端口间的可达性越强。为计算端口间交换线路数据，首先分析各端口的右邻节点，对式(2)做递推计算，得式(5):(5)根据式(3)、式(4)和式(5)，计算式(5)中各集合包含元素的数目，得式(6):(6)由式(6)中可知，数据分组可从任何一个b-ISU的输入端口到达任何一个b-OSU的输出端口。图32表示的是各级端口的左邻端口和右邻端口数目(以PP=取16为例)。显然明显，b-ISU的输入端口、u-CSU的输入端口和b-OSU的输入节点端口的右邻节点数目决定# LR(,)的大小，即决定整个网络的端口间可达性的强弱。图2 3端口扇入扇出数对任意 LR(,)，具体分析如下：l 若所在组编号相同，有：#LR(,)=3；l 若所在组编号不同，有：# LR(,)=2。由此和定义4得到整个网络的端口间可达性，如表1所示。表1不是阿拉伯数字编号吗？ 端口间可达性 b-OSUb-ISU组1组2组3组4组1冗余链路双链路双链路双链路组2双链路冗余链路双链路双链路组3双链路双链路冗余链路双链路组4双链路双链路双链路冗余链路对于所在组编号相同的和，有# LR(,)=3，根据定义3对元素rRL的描述，这两个顶点端口间存在3条没有链路竞争的交换线路，根据结合对传统3级Clos交换网络的研究7，这两个端口间的数据分组传送符合完全无阻塞的条件。对于所在组编号不同的和，有# LR(,)=2，根据定义3对元素rL的描述，这两个顶点端口间存在2条没有链路竞争的交换线路，根据结合对传统3级Clos交换网络的研究9，这两个端口间的数据分组传送符合可重配置无阻塞的条件。3.2、网络的可靠性根据表1可知，所在组编号不同的任意一个b-ISU到任意一个b-OSU之间具备两条交换线路，并且这两条交换线路通过两个不同的u-CSU，只有当两条交换线路所通过的u-CSU同时损坏，两个交换单元间的端口间可达性才会完全丧失。当只有一个u-CSU损坏时，虽然所在组编号不同的任意一个b-ISU和任意一个b-OSU之间的# LR(,)从2下降为1，但其端口间的通信能力没有完全丧失，从而提高了交换网络的可靠性。所在组编号相同的任意一个b-ISU到任意一个b-OSU之间具备三条交换线路，并且这两条交换线路通过三个不同的u-CSU，只有当三条交换线路所通过的u-CSU同时损坏，两个交换单元间的端口间可达性才会完全丧失，因此这种情况下网络的可靠性可得到进一步的加强。在进行配置时，可根据实际应用的需要将任意一组b-ISU和任意一组b-OSU编为同一编号，即可以在任意一个b-ISU和b-OSU间提供3条交换线路，以提高这一对交换单元之间数据分组传输的可靠性。同时，由于冗余链路的存在，通过对通信链路的重配置，在链路损坏数目小于P时，都可以保证整个网络的吞吐率容量保持不变。3.3结构复杂度使用交叉点的数目描述某个网络的复杂度性。具体考虑一个(N=1,2,3)的交换网络：l 使用单级Crossbar结构交换网络实现，包含的交叉点数目记为；l 使用符合严格无阻塞条件的3级Clos 交换网络结构C(3，2，N/2)7实现，包含的交叉点数目记为；l 在某种Packing策略下，使用符合可广义无阻塞条件的3级Clos 交换网络结构C(m，2，N/2)9实现，包含的交叉点数目记为，其中,为斐波那契数列8。l 使用本文提出的交换网络结构实现，包含的交叉点数目记为。具体计算可得式(7): (7)将取不同的数值，根据式(7)可得：l 当时，有；l 当取任意值时，有；l 当时，根据斐波纳契数列的定义，有；得时，有。对于一个大容量的交换网络，是一个普遍现象，由此我们可以得出：一般情况下，本文提出的交换网络相对于单级Crossbar交换网络、传统3级Clos交换网络结构复杂度要低。4. 结论该论文提出了一种新型多级可扩展交换网络，该交换网络具有可靠性高、配置灵活复杂程度低和复杂度低配置灵活等特点。论文首先建立了该交换网络的逻辑结构逻辑模型,并对它进行了形式化描述，然后在明确该交换网络逻辑结构的基础上，描述了网络的其使用和扩展方式。接着然后论文通过计算端口间交换线路数目，给出了该交换网络的端口间可达性和无阻塞条件，分析了该通过假设交换网络在不同程度损坏的方式程度下的可靠性。最后，通过与单级Crossbar交换网络、传统3级Clos交换网络进行比较，证明了在输入输出端口数目大于13的条件下，本交换网络的复杂度要低。参 考 文 献1 James Aweya, Michle Duellette, Delfin Y.Montuno, Zhnonghui Yao. Enhancing Network Performance With TCP Rate Contrpl. IEEE/ACM TRANSACTIONS ON NETWORKING, 2000.2 Huan-YunWei, Shih-chiang Tsao, Ying_Dar Lin. Assessing and Improving TCP Rate Shaping over Edge Gateways. IEEE TRANSACTIONS, Vol.53, NO.3, MARCH 2004.3 Dune Networks Inc. Next-generation Swith-fabricEB/OL. /products/papers/DN-Scalability-WP V1.2.pdf.4 Dally W J. Performance analysis of k-ary n-cube interconnect ion networks. IEEE Trans on Computers, 19