大容量星上交换网络的设计与实现

鲍民权，邱智亮，张茂森，刘焕峰

（西安电子科技大学综合业务网国家重点实验室，陕西西安710071）

0 引言

随着移动通信、多媒体广播业务的发展，人们对卫星数据通信的要求更加迫切，这需要在卫星上实现分组交换。星上交换除需要完成与地面交换相同的功能外，还受到芯片容量、功率及实现复杂度等多方面的限制[1]。多级交换网络允许使用小容量芯片构建大规模交换网络，交换网络的容量不再受到单芯片容量和引脚数目的限制。因此，当构建大容量星上交换网络时，多级交换网络结构更具有优势[2]。现有大多数高速交换网络内部都采用定长信元交换，由于变长分组在被切片成定长信元时，信元的利用率不可能达到100%，这就要求内部链路速率高于外部链路速率。

在分析定长信元长度与内部链路速率的关系的基础上，给出了通过选取信元长度来降低内部链路速率的方法。交换网络规模的扩大，使完成一次调度的时间相应增加，如果处理不当，会对交换网络性能造成影响[3]。介绍了交换网络中的多子调度器技术，通过多个子调度器并行计算，完成整个交换网络的路由调度，以有效消除交换网络规模增加对系统性能造成的影响。

1 Clos网络模型

Clos网络是一种常见的多级交换网络，其模块化结构和可扩展性很好地满足了星上交换的要求。Clos网络模块化的结构允许通过多个小容量的芯片构建大规模的交换网络，将中间级模块用一个完整的3级Clos网络替换，可以把3级Clos网络扩展为5级Clos网络，采用相同的方法继续扩展下去，这样可以使用相同的交换模块，构建任意规模的交换网络[4]。Clos网络的结构可归纳为以下3点:①交换网络中的交换模块被排列为3级;②每一个交换模块同相邻级中任一交换模块相连接;③每一个交换模块都是无阻塞的。

Clos网络的结构如图1所示。其中，IM表示输入级模块，CM表示中间级模块，OM表示输出级模块;VOQ表示输入级模块的虚拟输出队列，VIQ表示输出级模块中虚拟输入队列。

图1 Clos网络结构

通常，将Clos网络输入级模块输入端口数记为n，输出端口数记为m，输入级模块数记为k，并把这样的Clos网络记为C（m，n，k）。Clos网络被分为2种:中间级无缓存结构（MSM）和中间级有缓存结构（MMM）。中间级无缓存的Clos网络（MSM）可以保证分组在交换网络内部传输时的顺序，但是需要合适的调度算法解决中间级输出端口分组冲突问题[5]。目前，基于中间级无缓存的Clos网络的调度算法已经成为研究的重点，文中所讨论的也是这种网络。

2 队列管理技术

当交换网络的输入端口采用先进先出（FIFO）的排队规则时，可能会出现队头分组竞争输出端口失败，而后续分组的目的端口即使空闲，也无法发送的现象，这种现象被称为队头（HOL）阻塞，它严重制约了交换网络的吞吐率。为消除队头阻塞带来的影响，通常在IM模块中使用虚拟输出队列（VOQ）来代替简单的FIFO，每一个VOQ对应于交换网络的一个输出端口，因此每一个IM模块中有n×k个VOQ。由于同一VOQ中的分组发往同一输出端口，因此不会被发往其他端口的分组所阻塞。同时，VOQ按照分组到达的先后顺序发送，分组之间不会乱序。

在实际的工程中，可以使用共享缓存和队列管理实现VOQ技术[6]。采用共享缓存不需要为每一个VOQ队列单独分配缓存，节省了存储资源。当有分组到达时，输入端口向队列管理模块发出申请，队列管理模块将分组信息加入对应的VOQ中，同时在共享缓存中给当前分组分配一定的空间，这个过程被称作分组的入队;VOQ根据自己队列情况向交换网络的调度器发送请求，调度器根据所有VOQ的请求进行调度;当完成一次调度后，如果VOQ获得在交换网络内部发送数据的机会，分组内容会从共享缓存中被读出，以定长信元的形式在交换网络内部传输，同时VOQ修改队列信息，这个过程被称作分组的出队。

交换网络内部的定长信元需要在OM模块的输出端口处被组装成变长分组。因此，每个输出端口都要有相应的输出缓存来存储整个分组。对于OM模块的每一个输出端口，最多同时有k个IM模块同时向该端口发送信元，这要求每个输出端口至少要维护k个输出队列，被称为VIQ，而每一个输出级模块需要维护的输出队列数目为n×k个，VIQ也可以使用共享缓存和队列管理来实现。

3 信元长度和链路加速比的关系

在实际应用中，变长分组在进入交换网络前被切片为定长信元，然后在交换网络中完成交换过程，在输出端口处重组为变长分组。相比变长分组交换，采用定长信元交换有以下优点:①不需要为变长分组维护中间级链路，简化调度算法;②避免长分组阻塞短分组的现象，有利于减少交换网络的时延抖动;③减少中间级模块的数目，如果在Clos网络中使用变长分组交换，按照严格无阻塞的条件，CM模块数m与IM模块输入端口数n之间的关系需要满足m≥2n-1，而如果采用定长信元交换，则只需要满足可重排无阻塞，即m≥n。

当交换网络内部采用定长信元交换时，实际传送的内容总是大于分组的实际长度，在设计交换网络时，内部链路速率要高于外部端口速率。内部链路速率越高，硬件实现的难度就越大。因此，在满足无阻塞交换的前提下，需要尽可能地降低内部链路速率。通过分析发现，当外部端口速率固定时，影响内部链路速率的关键因素是定长信元的长度，信元长度决定了传输同样长度分组时信元的利用率，也就决定了内部链路的加速。

为计算内部链路速率与信元长度的关系，首先定义如下变量:帧长度Lf，帧间隔LI，信元数据部分长度Ld，信元头部长度Ltag，信元长度Lc（=Ld+Ltag），端口数据速率Cf，内部链路数据速率Cc，加速比S（=Cc/Cf）。其中，LI表示物理链路上2分组间的最小帧间隔;Ltag包含信元在交换网络内部路由和分组重组时所需的信息。上述变量满足式（1），式中符号「⏋表示向上取整。

式（1）左边是交换网络内部传输一个分组所需最小时间，右边是端口处接收对应长度分组所需的时间。为保证无阻塞传输，内部传输时间应小于等于端口处传输所用时间。式（1）可转化为式（2）:

式中，S表示内部链路速率与端口速率的比值，也就是加速比，不等式右端是同样分组长度下交换网络内部传输数据总长度（即所有定长信元长度总和）和外部传输数据总长度（包括分组内容和帧间隔）的比值。根据式（2）确定的关系，可以选择当不等式右端值最小时的Ld作为交换网络内部信元数据部分的长度，此时所需加速比最小。

由于IM内部采用共享缓存来存储分组，因此Ld还受限于共享缓存的读取速率和位宽。用Cout_buffer表示共享缓存的读取速率，Cout_buffer应满足式（3）。

式中，Tslot=Lc/Cc表示一个时隙的长度，则共享缓存读取端口的位宽Bout_buffer满足式（4）:

式中，F表示共享缓存读取时钟的频率，现有数字系统数据位宽一般都是2的整数次幂，因此不等式右端的计算结果需要向上对2的整数次幂取整。

4 子调度器技术

当交换网络中只有一个调度器时，必须在一个时隙内完成一次调度，否则系统吞吐率会下降。如果交换网络端口数目非常大，则完成一次调度所需的时间也会很长，时隙长度也会随之增大，交换网络不得不使用较长的信元。为消除端口数目增加对时隙长度带来的影响，可以在交换网络中增加多个调度器，每一个调度器的结构与原调度器类似，称之为子调度器[7]。当多个子调度器并行工作时，允许每个子调度器用多个时隙完成一次调度。

当使用3个子调度器时，工作过程如图2所示，每个子调度器允许使用3个时隙完成一次调度。每个时隙开始时，请求被发往某一子调度器;该调度器可以使用3个时隙完成一次调度，在完成该次调度过程中产生的请求由其他子调度器进行处理;每个时隙结束后，都有相应的子调度器返回调度结果，指导下一时隙内交换网络中信元的传输，因此交换网络的吞吐率不会因为调度时间的增加而下降。

图2 有3个子调度器时的工作流程

当使用多子调度器时，IM模块和调度器需要有相应的改变。IM模块需要为每一个VOQ添加一个计数（VC），表示对应VOQ中未发送匹配请求的信元数目;当有新分组到达时，根据分组长度，VC增加相应数目。当发送一个匹配请求时，VC减1。同时在子调度器中添加VOQ标志位（VF）和调度结果寄存器（VR）。子调度器结构如图3所示。

图3 子调度器结构

图3中调度器模块实现预定的调度算法。VF和VR与IM模块中的VOQ相对应。VF的值为0或1，1表示该子调度器收到了对应VOQ发送的调度请求，0表示没有收到请求;VR表示对一个调度请求的结果，它包含2部分:①对应VOQ的请求是否获得匹配;②获得匹配后该信元所需的路由信息。当使用P个子调度器时，调度器工作流程如下:

①在时隙t的起始时刻，如果某VOQ的计数值VC＞0，且第p（=tmodP）个子调度器中对应VF位为0，则VF置1，VC减1，否则保持不变;

②在时隙t～t+P-1内，该子调度器按照预定的调度算法完成一次调度，并在时隙t+P-1结束前，将调度结果写入VR寄存器，如果某VOQ获得匹配，则将对应VF位清0，否则不变;

③调度器向IM模块返回VR寄存器的结果;

④在时隙t+P起始时刻，该子调度器接收新的匹配请求，并与上一次调度中未获得匹配的请求一起参与到新一轮的匹配过程;同时，在时隙t+P内，根据上一次匹配的结果，获得匹配的VOQ将队头信元发送到OM模块。

根据调度器的工作流程，可以得出完成一次调度的时间Tsch和子调度器数目P之间的关系:

从式（5）中可以看出，信元长度减少会增加子调度器数目，进而增加系统占用的资源。但是当端口数达到一定程度，采用长信元所需要的链路速率已经超出器件能承受的极限时，必须适当减少信元长度，以降低内部加速，这时，多子调度器技术是必须的。

5 实验结果与分析

搭建一个C（8，4，6）Clos网络为实验平台，端口速率为1Gbps，在不影响吞吐率的前提下，对所需的内部链路速率进行对比。这里采用了一种简单实用的集中式正交匹配调度算法[8]。参照Gbit以太网的参数，式（2）中各变量取值如下:Cf=1Gbps，Lf=64～1518B，LI=20B，Ltag=4B。

当Ld取不同值时，在Lf的取值范围内，对式（2）不等式右端求最大值，可以求出加速比和信元数据部分长度的关系如图4所示。将图4中所示曲线记为函数f（Ld），式（2）等价于S≥f（Ld）。

在实验中，取F=125MHz，Bout_buffer=128bit，根据实际测试，调度算法完成一次匹配需要约48个时钟周期。当使用单个调度器时，可以求得S=1.65，即内部链路速率为1.65Gbps。

图4 信元数据部分长度与所需加速比的关系

当使用多子调度器技术时，时隙的长度不受调度算法的限制，因此信元长度也是任意的，只要16B的整数倍即可。将式（5）展开，可以得到式（6）。

根据式（6）可以得到在上述参数下，信元数据部分长度与所需子调度器数目的关系如图5所示。

图5 信元数据部分长度与所需子调度器数目的关系

可以根据图4与图5，结合链路速率和资源等限制，选取合适的信元长度。在实际的测试中，使用了Ld=32B，这时子调度器数目为2，内部链路速率为1.27Gbps。所需链路速率降低了约23%，这为系统的实现带来好处，不但降低了系统功耗，而且扩大了芯片选型的范围。

6 结束语

Clos交换网络由于其模块化结构和良好的可扩展性获得了广泛的关注，被看作是未来构建大容量交换网络的基础。然而，由于Clos网络多路径的特性，调度算法往往比较复杂，尤其是在端口数目较大情况下，问题更为突出。为解决这个问题，可以在交换网络中增加多个子调度器，通过多个子调度器之间的并行计算，从而缩短时隙的长度。时隙长度直接影响到内部链路的加速，选择合适的时隙长度，有利于降低内部链路加速。

在工程应用中，可先按照文中提供的算法计算出交换网络所需的最低加速比，再根据系统参数来选择合适的信元长度，结合实际中交换算法所需的时钟周期数，计算出交换网络所需的子调度器数目。这样可以在端口数目增加的情况下，保证系统性能不受影响。

[1]史芳.一种新的星上交换连接控制实现方案[J].无线电通信技术，2007，33（1）:6-8.

[2]刘增基.交换原理与技术[M].北京:人民邮电出版社，2007:41-44.

[3]杨君刚，刘增基.混合交换机制三级Clos网络分布式调度算法[J]，西安电子科技大学学报，2008，35（4）:581-585.

[4]CLOS C.A Study of Nonblocking Switching Networks[J].Bell System Technical Journal，1953，32:406-424.

[5]杨君刚.高速多级分组交换网络若干关键技术的研究[D].西安:西安电子科技大学，2008.

[6]张树旗，贾树恒.一种支持变长分组的CIOQ交换结构[J].计算机应用，2005，25（7）:1491-1493.

[7]OKI E，Rojas-Cessa R，CHAO H J.A Pipeline-based Concurrent Round-robin Dispatching Scheme for Closnetwork Switches[C]//Communications，ICC 2002.IEEE International Conference on，2002，4:2121-2125.

[8]ENG K Y，KAROL M J，YEH Y S.A Growable Packet（ATM）SwitchArchitecture:DesignPrinciplesand Application[J].Communications，IEEE Transactions on，1992，40:423-430.