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

一种新型多级可扩展交换网络 陈一骄 汤庆新 （国防科学技术大学 计算机学院,湖南 长沙 410073） ：提出了一种新型多级可扩展交换网络。在建立该交换网络逻辑结构模型的基础上，对该交换网络进行了形式化描述，并了扩展方式。然后，通过分析该交换网络通信链路间的竞争，定量地描述了该交换网络的端口间可达性、无阻塞条件可靠性。最后通过与单级Crossbar网络、传统3级Clos网络的定量对比，证明在同等容量下该网络的结构复杂性最低。 ：交换网络；多级；可扩展；复杂度 A Novel Scalable Multiple-Stage Switching Fabric Chen 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 logical model of the switching fabric is built up. Based on the model, 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 connectivity，the no-blocking condition and the reliability of the fabric are described. 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; Complexity 1. 概述 随着网络业务的迅猛增长和光传输技术的成熟，路由器等网络节点的性能对整个网络性能的瓶颈限制日益凸显。高速交换网络是路由器的重要组成部分，其容量、可扩展性、可靠性等直接影响路由器的性能及使用灵活性[1][2]。单级Crossbar是目前路由器采用较多的一种交换网络，但其复杂度与端口数的平方成正比，工程实现上受限于芯片体积等因素，其容量不可能做到很大[3]。多级交换网络很自然地以构建大容量交换网络。直接连接交换网络[4]和间接连接交换网络[5]是空分多级交换网络的两种主要类型。由于存在重负载情况下性能难以保证、工程实现难度大等缺陷，以3D Torus交换网络和超立方体交换网络[6]为代表的直接相连交换网络仅在大容量交换网络研究的初期得到了一定的发展。相比直接连接交换网络，即使在重负载情况下，间接连接交换网络的性能也能得到较好的保证，在网络流量急剧增长的背景下，间接连接交换网络成为构建大容量交换网络的首选。但是以3级Clos交换网络[7]等为代表的间接连接交换网络也存在可扩展性差、调度机制复杂等缺陷需要改进。 在保证交换网络性能的前提下，为提高其以较小粒度进行扩展的能力，同时保证网络复杂度不因规模扩展而激增，本文提出一种新型多级可扩展交换网络。文在建立该交换网络逻辑结构模型的基础上，对可靠性、端口间可达性、无阻塞条件、复杂度等进行了分析证明。 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)%