数据产品中各类交换结构的实现

1、        摘   要：本文论述了在高低端路由器、交换机等数据产品中各类交换结构的实现，分析了相应的特点与其应用场合，为数据产品中交换结构的设计提供了借鉴。  交换结构是路由器、交换机等数据产品中的核心部件，直接决定了整个系统的主要性能。多年来，各相关厂商、科研院所提出了许多交换方案，以解决数据交换过程中的碰撞冲突与阻塞等问题。从实现机制上分，大体上可分为两类：时分交换结构、空分交换结构。 时分交换结构在时分交换结构中，交换单元不能同时交换一个以上的输入端口数据。从交换结

2、构的角度看，每个输入端口数据的处理是串行的。共享总线交换结构共享总线交换结构采用时分背板总线进行数据交换，总线容量为单个端口容量的N倍以提供足够带宽。每个输入端口以一定的优先级，如仲裁或菊花链结构，向总线发送数据。交换结构如图1所示。共享总线交换结构非常简单，并且各结点之间具有相对的独立性，但其可扩展性受背板总线速率所限，而当背板总线可*性不佳或一个端口进入超长传输时，可能导致整个交换体系的崩溃。分层总线交换结构在一定程度上改善了共享总线交换结构的性能。在分层总线下，局部交换通过局部总线，只有全局交换需要经过多条总线，如图2所示。共享内存交换结构共享内存结构被广泛应用于中小型甚至某些特定的大型

3、交换结构实现当中，如图3所示。复用器(MUX)对各输入端口数据进行调度，解复用器(DEMUX)对共享内存中各队列进行调度，共享内存存储转发数据，控制器协调读写操作并提供各队列状态信息。共享内存交换结构简单有效，交换可根据不同的设置被相应的优化。但其交换性能取决于共享内存的存取速率，共享内存的读写带宽与调度算法需要有2N倍端口速率，可扩展性较差，并且共享内存的可*性也直接影响了整个交换体系。 空分交换结构与时分交换结构相比，空分交换结构适用范围更广，可分为单级交换结构、多级交换结构、群集交换结构。单级交换结构Crossbar是一种典型的单级交换结构，其实现方式有：集中方式(输入比输出多

4、)、扩展方式(输入比输出少)、连接方式(输入和输出一样多)，一般采用连接方式，由N×N交*矩阵构成，如图4所示。Crossbar是一种严格非阻塞交换结构，可通过输入输出之间交*点的闭合，同时提供多条数据通路。交*点由调度器控制，调度器依据各输入数据队列的信息，经过调度算法得到输入端口和输出端口之间的一个匹配，并配置相应交*点。调度器的调度效率决定了Crossbar的交换速率。Crossbar交换结构优点在于所有输入输出之间都存在着独立的交换通道，因此该结构本质上是非阻塞的，并能够方便地实现组播。但Crossbar的可扩展性较差，增加一个端口就可导致交*点的指数增长，并且数据流通过交换

5、结构的传输延时不定，另外尽管输入端口是非阻塞的，但如果两个输入数据流具有相同输出端口，则输出端口阻塞，因此排队仲裁是必须的。多级交换结构时分交换结构与Crossbar交换结构都是单级交换结构，实现较为简单。当考虑大型交换系统时，单级交换结构有两个问题：为了解决以上问题，提出了多级交换结构。多级交换结构通过多个小的交换单元互连构造出一个大型的、容量可扩展的交换网络。多级结构能够容纳非常多的输入输出端口，其内部控制比较复杂，但各小交换单元的实现可以采用现有的成熟技术。多级交换结构之间的不同取决于各交换单元之间的互连形式，图5列出了其中的几种结构。在多级交换结构中，级数越少，交换延迟也就越小，但交换

6、通路也相应减少，这导致碰撞阻塞的更容易产生，因此多级交换结拓扑的确定有一个各项性能之间的折中。Banyan网络是得到广泛研究的一种多级交换结构，它的特点在于可伸缩性、固定交换时延、数据传输的自路由性与有序性。由于自路由性，其数据转发过程非常简单，数据信元能并行通过该结构，但如果超过一个信元在同一时刻到达一个交换单元的话，就会产生碰撞冲突，因此Banyan网络会由于内部的信元阻塞导致相关信元丢失，对此存在着两个解决方案，实际上两个方法可以同时应用：以Banyan网络为基础，为了实现更好的性能，又提出了许多Banyan网络的改进方案，如Batcher-Banyan网络、L-level Banyan

7、网络、Banyan-Delta网络、扩展Banyan网络等，其中Benes网络是较为突出的一种。Benes网络是一个重排非阻塞的Banyan网络，交换级数为(log2N)-1级，采用方形交换单元(输入输出端口数相同)构造并进行多级互连，保证了在每个输入输出端口间都有N个可能的通路。Benes网络可以扩展至任意奇数级，如图6所示。Clos网络是Benes网络的推展。Benes网络采用方形交换单元，便于实现，而Clos网络用非方形交换单元构造。Clos网络是一个三级全互连网络，由5元组(M1, R1, R2, R3, N3)表示，如图7所示。如果R2>= M1+N3-1，它是一个严格非阻塞结

8、构；如果R2>= Max(M1，N3)，则是一个重排非阻塞结构。另外，还有一种非常重要的交换结构：多平面交换结构。线卡中的一个数据流可同时通过各个平面，数据在输出端进行重组。多平面交换结构可以与多种交换结构结合，如Crossbar、Clos等，在大容量交换结构的实现中，被许多交换芯片制造商与设备制造商所采用，以期达到相当高的交换速率。图8为四平面交换结构。群集交换结构从网络拓扑上看，群集交换结构与多级交换结构相类似，也是通过一些小的交换结构构建一个大的交换结构。不同的是，多级交换结构内部的交换单元不与输入输出端口相连，而群集交换结构通过各线卡上的交换单元堆叠成一个大的交换结构，如图9所示

9、。图中每个圆圈表示线卡上的交换单元。群集交换结构中某些交换网络结构可以归类为K-ary N-cube形网络(其中K为每条边的结点数，N为维数)，如图9中的环状网络(Ring)是6-ary 1-cube网络；网状网络(Mesh)是4-ary 2-cube网络，也称为2D-Torus；而三维超立方体网络(3D-Hypercube)是2-ary 3-cube形网络。衡量群集交换结构性能有以下一些因素：一个良好的群集交换结构，应该是一个小直径、无限可扩展性、高对分带宽、高性价比、多连通度、低延时、无阻塞、非死锁的交换结构。二维(网状)、三维或更高维的超立方体等格形网络结构是得到应用较多的群集交换结构，

10、许多问题也类似，以下以此类结构为例对群集交换结构的特点进行论述。一般说来，格形结构的可扩展性好、传输通量高，但由于各交换单元之间需要互连，多数交换端口用在互相连接当中，因此较为昂贵，并且交换结构分散控制拓扑复杂，因此会在技术上带来一些问题，如死锁问题。死锁一般发生在当一个发送数据信元期待一个不可能发生的事件的时候，如互为发送的双方都期待对方的缓冲区释放出空间以接收对方数据等情况。死锁可以由虚拟通道技术加以解决，或由传输等待超时发现并退出发生死锁的一个或几个数据传输来打破。另外，由于群集交换结构的信元传送需要经过多个交换单元，因此会有较单级结构更多的延时，这可以采用增加维数，减小直径的方法，也可

11、以通过加快各交换单元处理速度等方法。随着交换技术的进步，各交换单元的处理速率越来越快，直径所带来的延时在一定范围内不是主要考虑因素，因此虽然大于三维的超立方体结构具有更小的直径，但由于控制的复杂性、价格昂贵等原因，近年来逐渐转向三维网络，特别是对3D-Torus结构的研究与应用。3D-Torus网络用大小固定的交换单元互连而成为一个三维环绕的格形网，每个交换单元通过单向或双向链路与它的六个相邻节点相连，并具有一个双向数据通路的连接线卡，路由选择时要求在每个方向上分别经过若干转接点。图10是3D-Torus网络拓扑结构图。3D-Torus网络具有以下特点： 结语近年来，随着Internet流量的迅