太比特交换开关拓扑结构研究

文章编号：1009－6868(2001)04－0010－05 文献标识码：A 中图分类号：TN915.05

　　交换开关是网络交换设备的重要组成部分，它直接决定路由器和交换机的性能。高性能交换开关的设计对网络核心交换设备的研制十分关键。本文对端口速率大于10Gbit/s，端口数目大于128的太比特(Terabit)交换开关的拓扑结构进行研究。

　　交换开关分为时分交换开关和空分交换开关两类。按照拓扑结构的不同，上述两类开关还可以进一步细分，如图1所示。设交换开关端口数为N，端口速率为V，则共享介质(总线)和共享存储器交换开关对存储器带宽的要求分别为(N＋1)V和2NV。若N=128，V=10Gbit/s，则上述带宽大于1Tbit/s。由于目前存储器根本无法提供如此大的带宽，因此时分交换难以满足Terabit交换的要求。当交换开关内部加速比等于1时，空分交换开关对存储器带宽的要求仅为2V，即20Gbit/s。所以用空分方式实现Terabit交换是可行的。

图1 交换开关分类

　　空分交换分为单级交换开关(Crossbar)和多级交换网络两类。本文第1节、第2节分别介绍这两类开关。第3节分析各种空分交换开关性能、扩展性以及提供多交换路径的能力，并指出K元n方网络是实现Terabit交换较好的拓扑结构。文章最后提出了在选定拓扑结构以后，对Terabit交换还需进一步研究的问题。以下讨论假设交换开关内部加速比等于1。

　　1 单级交换开关

　　Crossbar(交换开关)内部包含N2个交叉点，一个8端口Crossbar交换开关结构如图2所示。每个交叉点有连接和断开两个状态。若位于第i行第j列的交叉点处于连接状态，则输入端口i与输出端口j相连。

图2 8端口Crossbar交换网络

　　为提高内部带宽利用率和保证公平性，Crossbar采用定长信元交换方式。开关每交换一个信元的时间称为一个时间槽。根据信元缓冲的位置，Crossbar交换开关分为输入缓冲、输出缓冲和输入输出结合的缓冲3类。当交换开关内部加速比等于1时，信元在输入端口缓冲。输入缓冲Crossbar在每个输入端口采用虚拟输出队列以避免HOL(Head of Line)阻塞。一个集中的调度器根据各输入端口的请求决定每个时间槽内输入输出端口的连接关系，因此调度算法决定了Crossbar开关的性能。

　　Crossbar调度算法必须具有高带宽利用率、保证公平以及支持组播和优先级。常用的Crossbar调度算法有iSLIP、PIM、ISP、ESLIP等。Crossbar交换开关的优点是单级交换，无内部阻塞，可灵活支持组播。缺点是扩展性较差(N2个交叉点)。目前高性能Crossbar交换开关有Saturn(1Tbit/s)、ETT1(320Gbit/s)等。

　　2 多级交换网络

　　按照输入输出端口连接关系，多级交换网络可分为动态多级互联网络和静态多级互联网络，以下简称为动态网络和静态网络。两者的比较如表1所示。

　　2.1 动态网络

　　与Crossbar不同的是多级互联网络具有内部阻塞，根据交换网络是否用内部缓冲区解决内部阻塞的特性，动态网络可分为内部缓冲动态网络和无内部缓冲动态网络。

　　2.1.1 内部缓冲动态网络

　　内部缓冲动态网络采用内部缓冲区来解决网络内部阻塞，根据网络对每个微流[如在ATM和TCP/IP中分别使用VPI/VCI和5元组(源IP、源端口号、协议、目的IP、目的端口号)标识的用户流]路由方式不同，内部缓冲动态网络又可分为动态路由网络和静态路由网络。

　　动态路由网络针对单个信元进行路由，把从输入端口i到输出端口j的所有流量均匀地分布在i和j之间可能的多条交换路径上，这样有利于网络内部的负载平衡，但缺点是无法保证同一微流的信元在通过交换网络后不乱序。因此动态路由网络的输出端口需要对信元进行重新排序。

　　Benes网络是典型的动态路由网络。16端口的3级Benes网络如图3所示。每个交换单元由4端口Crossbar、输入缓冲区以及Crossbar调度逻辑组成。网络的第一级将信元均匀地分配到不同的第二级交换单元，而后两级交换单元按信元的目的端口号将信元交换到输出端口。

图3 16端口的3级Benes网络

　　Benes网络可能导致同一微流的信元乱序。如果要保证微流信元次序，必须在每个信元进入网络前为其加上时间戳，同时输出端口缓存到达的信元，并按时间戳的顺序对信元进行重排序。重排序增加了额外的延时。

　　静态路由网络保证属于同一微流的信元在网络中经过相同的交换路径，因此可保证同一微流的信元不乱序。属于同一微流的信元在进入交换网络时被赋予相同的路径号。静态路由网络根据信元的路径号对信元进行交换。静态路由方式较难实现交换网络内部的负载平衡。Clos网络是静态路由网络。16端口3级Clos网络如图4所示。Clos网络与Benes网络较为相似，只是在第1级和第3级使用非对称的交换单元。例如图4中3级交换单元分别是4×6、4×4和6×4，一旦有新的微流进入交换网络时，必须有集中控制逻辑为该流分配路径号。

图4 16端口3级Clos网络

　　设Clos网络第一级有d个输入，r个输出；第二级有r个输入，r个输出；第三级有r个输入，d个输出，则当满足以下条件时，Clos网络内部无阻塞：
　　
　　其中β为端口速率与网络内部链路速率的比值；B为微流最大速率与网络内部链路速率的比值。

　　2.1.2 无内部缓冲动态网络

　　无内部缓冲动态网络主要包括Tandem banyan和Batcher bitonic sorter网络。虽然无内部缓冲网络的实现需要较少的逻辑，但要取得像有缓冲网络一样的性能，需要大量的片内和片间高速互联。

　　Tandem banyan网络包含n级Banyan网络，如图5所示。若多个信元在第i级Banyan网络内部的某交换单元发生冲突，则选择一个通过，其余信元进入第i＋1级Banyan网络重新进行交换；第n级Banyan网络将无法交换的信元丢弃。如果n足够大，信元的丢失率可以小于用户指定的阈值。

图5 Tandem banyan网络

　　为了保证传输的可靠性，必须为网络增加确认机制。即交换到输出端口的信元向其输入端口发确认信号。只有接收到确认信号后，源输入端口才将该信元从缓冲区中删除。若输入端口没有接收到确认信号，则重发该信元。

　　Tandem banyan网络不保证同一微流内信元的次序。

　　Batcher bitonic sorter网络如图6所示，由左端的排序网络和右端的自路由Banyan网络组成。排序网络根据信元目的端口号的大小对其进行重新排序。包含向上箭头的排序单元表示目的端口较大的信元将被交换到靠上的输出端口，目的端口较小的信元将被交换到靠下的输出端口；包含向下箭头的排序单元的功能正好相反。若两个信元的目的端口号相等，排序单元在内部不对信元进行排序，直接输出。

图6 Batcher bitonic sorter网络

　　若进入交换网络的信元具有各自不同的目的端口号，那么排序后的信元在进入自路由网络后不会发生内部阻塞。若有目的端口冲突的信元进入交换网络，则必须在排序网络和自路由网络之间增加过滤逻辑。过滤逻辑在目的端口冲突的信元中选择一个信元进入自路由网络，丢弃其余信元，并通知相应的输入端口。输入端口将重新发送被丢弃的信元。

　　Batcher bitonic sorter网络在早期的ATM交换机中使用。如Starlite交换机、Sunshine交换机等均采用Batcher bitonic sorter网络。

　　2.2 静态网络

　　静态网络节点间的连接是固定的。采用不同的连接方法可组成不同的拓扑结构。由于任意两个节点不一定直接相连，也没有类似动态互联网络中临时建立的连接，因此静态网络中非直连节点的通信需要通信路径上其他节点的支持。

　　静态网络拓扑有线性阵列；环、树、胖树、星形网；K元n立方体网等。我们认为胖树形网和K元n立方体网可用来构建高性能的交换网络。

　　2.2.1 胖树形网

　　胖树解决了树结构根节点易成为通信瓶颈的问题。胖树结构中，越接近根节点，链路的带宽越大，如图7所示。对于理想的胖树结构，上层链路带宽应为下层链路带宽之和。在实际应用中，为了提高性能，只有低层节点(图中圆形节点)与交换网络的输入输出端口相连，高层节点(图中方形节点)均为路由器。

图7 胖树结构

　　K元n立方体网络的拓扑为n维结构，每维有K个节点相连。每维距离最长的节点可以环接，也可以不环接。环接的称为Torus网络，不环接的称为Mesh网络。图8所示为3元3方Mesh网络，节点是路由器。每个路由器分别连接交换网络的一对输入输出端口，以及X、Y、Z三维正负共6个方向。每个路由器内部包含接口控制、输入缓冲区、地址译码、Crossbar以及调度逻辑。

图8 3元3方Mesh网络

　　目前高性能并行计算机多采用K元n方网络进行内部互联，例如著名的T3D、T3E、银河III并行巨型机采用3维Torus网络互联，曙光采用2维Mesh网络互联。

　　3 太比特交换网络拓扑结构的选择

　　Terabit交换网络拓扑结构的选择必须考虑性能、可扩展性和是否提供多路径通路等因素。本节根据这些因素，对上述各种空分交换开关进行比较。

　　3.1 多级网络优于Crossbar

　　由于没有内部阻塞，在相同工艺水平下，Crossbar交换开关的性能高于多级交换网络的性能。因此目前吉比特交换(端口数目16×32，端口速率2.5Gbit/s～10Gbit/s)普遍采用Crossbar结构。然而对于端口速率较高，端口数目较多的太比特交换来说，除了性能，还必须考虑可扩展性。

　　与多级互联网络相比，Crossbar的可扩展性较差。首先，随着端口数目和端口速率的增加，实现Crossbar的集中调度越来越困难。例如OC－768c接口要求一次调度时间小于50ns。对于目前的工艺水平，当端口数目N达到100时，在50ns内实现复杂度为O(NlogN)的调度算法(如iSLIP)，根本不可能。通过增加信元长度可以放宽对调度时间的限制，但信元过大会明显降低Crossbar带宽的利用率和公平性。此外，由于受芯片内部逻辑和引脚数量的限制，构建大规模的Crossbar交换阵列也比较困难。因此从可扩展性方面考虑，Terabit交换必须选择多级交换网络。

　　3.2 静态网络优于动态网络

　　由于动态多级互联网络是通过控制多个开关的合理接通和断开实现其互联功能的，因此在本质上，动态互联网络的功能不论在物理还是在逻辑上都是集中的。而静态互联网络最大的特点就是功能和物理实现的分布性。因此静态互联网络的扩展性比动态互联网络强。

　　如果Terabit交换网络能为每对源和目的节点之间提供多条交换路径，那么一方面可以提供负载平衡的机制，另一方面可以提高交换网络的可靠性，即一旦某条路径出现故障，数据可以转从其他路径交换。

　　内部无缓冲动态网络，如Tandem banyan网络、Batcher bitonic sorter网络等不提供多交换通路，为实现负载平衡和网络可靠性必须采用耗费硬件资源的多套交换网络并行工作方式。而Benes网络、Clos网络、胖树网络、K元n方网络直接提供多交换路径。

　　3.3 K元n方网络优于胖树

　　胖树和K元n方网络是典型的静态互联网络拓扑，而且这两种拓扑结构在MPP巨型机中都得到了验证。我们认为构造Terabit交换网络，K元n方网络比胖树更加合适。主要表现在以下两点：

　　(1) K元n方网络是全对称结构，系统内部不存在单一故障点，而对于胖树来说，虽然可以提供冗余的高速互联路径，但如果根路由器发生故障，整个交换网络就会瘫痪。

　　(2)在胖树结构中，上层链路带宽大于下层链路带宽。因此越接近根路由器，链路带宽越大。这实际等于网络内部交换加速比大于1，且端口越多，加速比越大。这对存储器带宽要求较高，往往难以实现。

　　综上所述，K元n方网络是Terabit交换首选的拓扑结构。与这一结论相符的是，目前推出的Terabit路由器如AVICI TSR和Pluris TERAPLEX20都采用K元n方交换网络，前者为立方体结构，后者为超立方体结构。

　　4 结束语

　　拓扑选择只是交换网络设计的第一步。如果采用K元n方交换网络实现Terabit交换，还有许多重要的问题有待研究，如：

• 选用何种数据切换方式，如虫孔路由、存储转发、虚旁路等；
• 选用何种流控方式，如虚通道，基于信用的流控等，以及如何在内部阻塞时合理地丢弃信元等；多路径路由算法，如何在多条等代价的路径中选路，以及如何保证微流内部信元的次序等；故障动态切换，如何动态发现故障，如何在故障条件下完成路由功能等。

　　本文初步研究了Terabit交换网络的拓扑结构，并指出K元n方网络是构建Terabit交换网络的一种可选拓扑。随着工艺水平的不断提高，全相连的适度规模的Crossbar结构是可行的。

[摘要] 文章首先详细分析了当前各种高性能交换开关拓扑结构，包括交换开关、动态多级互联网络和静态多级互联网络，然后结合太比特交换开关的特点，通过比较各种拓扑结构的性能、扩展性以及提供多交换路径的能力，得出K元n方网络是实现太比特交换较为可行的结构。

[关键词] 太比特 交换开关 拓扑 动态网络 静态网络

[Abstract] The topologies of high－performance switches are analyzed in－depth, including the single－stage Crossbar switch, dynamic and static multi－stage fabrics. Based on the analysis of characteristics of terabit switches and the comparison among different topologies with respect to reliability, scalability and path diversity, it is concluded that the n－dimension switching fabric with k nodes is feasible to realize the terabit switching.

[Keywords] Terabit Switch Topology Dynamic network Static network