在太位交换机设计中，对负载平衡算法和队列结构设计的要求是简单高效。采用队列架构，负载平衡算法几乎不增加系统的通信开销，且不降低通信容量，因此有助于实现无阻塞交换，本文介绍的分布式控制概念和提高负载平衡效率的方法，值得从事高容量交换架构设计的(中国)通信工程师关注。

随着太位(terabit)交换技术走出实验室并在中心局中获得应用，设计人员必须考虑既能平衡负载，又保证高效交换架构的算法。目前，许多交换机仍然使用带有分布式控制的并行交换元件(switch element)，这需要有效的负载平衡算法和队列结构设计。实现上述功能的一种可行方法是利用“只请求(request-only)”虚拟输出队列集成不带缓存的输入队列纵横制交换机。

理想的负载平衡算法工作在分布式模式下，可以通过在每个交换元件中使“只请求”虚拟输出队列的长度一致，以动态平衡并行交换元件之间的工作负荷。该算法额外增加的通信开销很少并且不会降低通信容量，因此无须增加内部线路速率就能实现无阻塞交换。该算法还能在10ns内完成一次负载平衡操作，因此适用于40Gbps的OC-768线路速率。此外，该架构的存储带宽还与系统的端口数目无关。

在新一代交换架构设计中，单级交换机架构因其结构简单和性能高效而得到广泛应用。单级交换机架构可以分为集中控制架构和分布控制架构。

在集中控制架构中，只有一个由多个交换片(switch slice)组成的交换域。集中调度器(scheduler)控制所有交换片入口端口和出口端口之间的连接配置。分布式控制架构由多个并行的交换域组成，每个域均带有独立的调度器。负载平衡算法为每个到达的交换单元(switch cell)分配特定的交换元件，而局部调度器决定何时将交换单元切换至出口端口。与集中控制相比，分布式控制更易于实现太位系统。

分布式交换架构必须具有简单、快速、高效的负载平衡算法和队列结构，这样通信开销就很小而且存储带宽与端口数目无关。下面将研究带有分布式控制的单级交换架构的队列结构和负载平衡算法。

集中式控制

首先考虑带有集中式控制的交换架构。通过采用目前最先进的串行I/O技术，单级交换芯片可工作于数百Gbps的低速率范围内，这意味着为了达到太位交换容量，需要多个交换芯片协同工作。在集中式交换架构中，交换单元通常分为多个在相同单元时间内由一组交换片完成交换操作的部分。所有的交换片均由单个调度器控制，这样就能同步切换交叉点。图1显示了集中式交换架构示例，图中IP表示入口处理器，EP表示出口处理器，SE表示交换元件，CS表示集中调度器。

集中调度方法可采用下述三种队列结构中的任意一种：基于共享内存的输出队列、基于纵横制的输入队列和输入输出混合队列。由于输出队列交换结构要求很高的存储带宽，因此很难进行调整，而输入队列和输入输出混合纵横队列则是集中控制式交换架构的最佳选择。

集中架构的优点在于调度机制简单高效，因为它只需要一个集中调度器。集中架构的不足之处在于其灵活性不高。由于集中调度器需要在每个单元时间内进行调度决策，因此当线路速率增加时，单元时间将相应缩短，这样调度器就难以在有限的时间内完成调度任务。例如，当链路速率达到40Gbps时，传输ATM单元的时间约为10ns。在400MHz时钟频率下，调度器需要每4个时钟周期产生一个调度结果，因此，即便能完成这项操作，其实现也极为困难。

另外，根据集中调度器的控制要求，所有的交换片均需要同步配置。当更高的线路速率导致单元时间缩短时，交换片之间的同步将很困难，而且集中调度器本身也可能成为瓶颈，因为其灵活性非常有限。最后，即便集中调度器隐含哪怕一个故障点，也可能破坏整个交换架构。

分布式交换架构示例参见图2，从N个入口端口到达的链路数据率为R的交换单元首先由N个入口处理器进行处理。架构中共有P个并行交换元件，每个元件都是带有N个入口端口和N个出口端口(N×N)的交换机。交换单元将根据特定的负载平衡机制分配交换元件，由出口处理器聚集并以链路数据率R发送至出口端口。需要说明的是图2中的每个模块均可由ASIC芯片实现。

分布式调度控制交换架构的优点

分布式调度控制交换架构的优点是具备能够单独决策的独立交换元件，这些交换元件不需要高速同步，从而简化了交换系统设计。此外，该架构提供了内置容错功能，因为负载平衡分配器可采取“不为故障分配交换单元”的措施来旁路不正常的交换操作，从而避免了单点故障。

如果负载平衡算法的系统开销很小并能有效抑制通信容量下降，那么交换元件及其I/O链路的速率只需为线路速率R的1/P，以实现无阻塞传输。由于当前的串行I/O技术可为单个交换元件芯片提供几百Gbps的交换容量，因而有利于太位交换架构降低每个交换元件的容量。

由于每个交换元件所需的速率为R/P，因此带有P个交换元件的分布式架构中，交换单元时间将比集中式架构的单元时间更大，这简化了调度器实现并能选取智能化程度更高的调度算法。例如，集中式控制架构中，40Gbps OC-768线路的ATM交换单元的单元时间约为10 ns；而在带有8个并行交换元件的分布式架构中，单元时间为80ns，这个时间有利于复杂调度算法的实现。

基于上述几点，可以得到如下结论：分布式控制交换架构比集中式控制架构更适合于太位交换设计。为了满足太位交换的速度要求，负载平衡算法和队列结构设计必须简单高效。

例如，如果负载平衡算法需要从其他器件中重新获取状态信息，必须添加额外的系统开销，即需要增加成百上千个工作频率达到几GHz的高速信号。而且，负载平衡算法需要在所有的交换元件中均匀分配，以平衡所有交换元件的工作负荷并抑制通信容量的下降。存储带宽与交换架构端口的数目无关，这一点相当重要；否则该架构将无法升级至更高的交换容量。

分布式交换架构仍然还有一些问题有待解决。例如，并行ATOM架构、门限负载平衡架构和叉形连接架构均在交换元件中采用输出队列。输出队列交换元件的一个重要问题是要求其带宽正比于端口数N，这意味着整个交换容量将受到每个交换元件存储带宽的限制。

另一方面，并行负载平衡调度算法采用不带缓存的纵横交换机制作为其交换单元。但由于在交换单元中不存在单元请求缓冲器，出口端口的冲突将导致某些单元请求被抛弃，为此在下一单元时间内入口处理器必须重发请求。由于整个通信容量的下降，该交换架构的处理速率必须增至原来的1.6倍，以提供无阻塞交换。

队列结构

队列结构和负载平衡算法对于交换架构的时序和性能至关重要。队列结构采用并行不带缓存的输入队列纵横架构并配备“只请求”虚拟输出队列。负载平衡算法工作于分布式模式下，可通过在每个交换单元中均衡“只请求”虚拟输出队列的长度，以动态平衡并行交换元件之间的工作负荷。负载平衡算法将几乎不增加系统的通信开销，也不会导致通信容量下降。该架构的存储带宽与系统的端口数目无关。

图3显示了带有P个交换元件的N×N系统的队列结构，这里N=2，P=2。令IP[i]表示入口处理器，EP[j]表示出口处理器，而SE[p]则表示第p个交换元件。

在每个入口处理器中，根据交换单元的出口端口，交换单元存储在单元虚拟输出队列(CVOQ)中。特别地，我们用CVOQ[i][j] 表示开始于第i个入口端口，终止于第j个出口端口的交换单元的FIFO队列。CVOQ[i][j]驻留在入口处理器IP[i]中，而负载平衡分配器(LBD)则在CVOQ中，根据所有交换单元的工作负荷为特定的交换元件分配交换单元。

在队列结构中，交换单元切换至出口端口共分两个阶段：请求确认阶段和交换单元转移阶段。在请求确认阶段，LBD向一个并行交换元件发送交换单元请求，单元请求存储在交换元件的请求虚拟输出对列(RVOQ)中。

我们用RVOQ[i][p][j][t]表示请求FIFO RVOQ[i][p][j]的第t个请求入口，请求FIFO RVOQ[i][p][j]驻留在第p个交换元件中，并存储从i个入口端口发送至第j个出口端口的请求。RVOQ[i][p][j]的宽度为1-b，并具有固定的长度T。每个SE[p]带有N2个RVOQ，这些RVOQ共产生N2条发送至局域纵横调度器的信号。

调度器将在一个单元时间内对N个请求进行鉴别和确认，以保证不会有两个确认请求来自相同的入口处理器或发送至相同的出口处理器。一旦每个交换元件的局域调度器安排好一组请求，这些请求的确认信号将发回至入口处理器。在单元传输阶段，确认单元通过相应的交换元件传输至出口处理器。

有效的负载平衡算法需要根据RVOQ的长度进行决策。在从交换元件中重新获取RVOQ长度的过程中，为了不增加通信开销，可在入口处理器中添加一组跟踪虚拟输出队列(TVOQ)，以反映交换元件中的RVOQ。TVOQ[i][p][j]所表示的FIFO跟踪从IP[i]发送至SE[p]，最终到达EP[j]的未确定单元请求。

当请求从IP[i]发送至SE[p]或者单元确认从SE[p]发送至IP[i]时，TVOQ[i][p][j]和RVOQ[i][p][j]都将刷新，并且刷新的同步延迟等于入口处理器和交换单元之间的传输时间。

一旦交换单元从交换元件传送至目标出口处理器，将由出口处理器的单元集合器(CA)采集并进入出口端口的输出队列(OQ)。由于CVOQ中的多个交换单元可在一个单元时间内通过分布式交换元件并行传送，因此单元集合器需要恢复交换单元的顺序。

当交换单元直接从入口处理器传送至出口处理器而不在交换元件中缓存时，在任何给定的时间内到达单元集合器的无序交换单元的上限应为P。因此，重排序机制很简单，而单元集合器中缓存的空间也相当有限。此外，上限P意味着交换单元的报头只需要_log2(P)个位作为重排序标号。因此，这种重排序几乎不会增加额外的通信开销。

这种队列架构与并发调度算法的区别在于未获确认的请求不被抛弃，因此不需要重发单元请求。这种方法的优点相当明显：无须增加与重发请求相关的成本，而且由于RVOQ可存储未获确认的请求，交换元件中的纵横调度器可以更精确的反映CVOQ的状态，以提高调度效率。相反，并发调度算法中的调度器在每个单元时间内，只能认定每个入口处理器中的一个请求。

TVOQ和RVOQ之间的映射关系有利于实现不同端口、不同级别的无损耗背压协议(backpressure protocol)，而不会增加从SE传送至IP的通信开销。这与需要专有背压网络的架构形成了鲜明的对比，而且带有分布式负载平衡和纵横调度器的并行交换元件允许交换架构中存在内置容错。

平衡负载

入口处理器中分配了N个负载平衡分配器，每个入口处理器一个。这些负载平衡分配器并行独立工作，其工作线路速率将使得充分多的单元请求发送至并行交换元件。

用C语言描述的负载平衡算法伪代码参见代码表1。变量的第一个参数表示该变量从属的入口处理器，TVOQ_LEN[i][p][j]指定了TVOQ的长度。如上所述，TVOQ_LEN[i][p][j]的值将随单元确认以及单元请求的生成而增加。

方程： 中，

TVOQ_FULL[i][j]指示TVOQ中是否存在空记录项，并可根据TVOQ_LEN计算增量。类似地，在

方程： 中，

CVOQ_REQ[i][j]指示在下一个操作中，负载平衡分配器应考虑的CVOQ值，该值可随增量而刷新。同样地，在

方程： 中，

需要3个步骤完成负载平衡操作。首先负载平衡分配器利用循环调度器从非零的CVOQ_REQ值中选取一个CVOQ。第二步，对于所选的CVOQ，算法在P个交换元件中找到最小的TVOQ长度。最后算法随机选取具有最小TVOQ长度的交换元件，并向该元件发送单元请求。

对于特定的负载平衡分配器LBD[i]，算法所需的信息可根据{TVOQ[i][p][j] | 0≤p≤P - 1, 0≤j≤N-1}和 {CVOQ[i][j]|0≤j≤N-1}，在入口处理器IP[i]上生成。

负载平衡算法的硬件实现也很简单，目前已采用0.18μm CMOS工艺实现了320Gbps交换架构，该架构由8个交换元件组成并且每个入口处理器带有64个CVOQ。算法可在10ns以内完成负载平衡调度。

提升速率

图4显示了在16×16交换结构中含有4个交换元件的架构仿真性能。输入通信中平均分段存取的长度为16个单元，而传送目的地遍布所有的出口端口。通信将在接通时段和断开时段之间重复，每个时段的长度呈几何分布。

本架构可被视为P个服务器(P-server)的队列系统，其中每个服务器的工作线路速率为整个系统的1/P。为了便于比较，图4还显示了采用集中式控制的输入队列纵横架构的仿真结果，该架构可视为单服务器队列系统，其工作线路速率是分布式架构的P倍。

与预期一样，P-server系统可支持与单服务器相同的通信容量，只是单元延迟略大一点。但分布式控制和动态负载平衡允许P-server系统采用比集中式控制架构更为简捷的实现方法升级至更高的交换容量。仿真使用的纵横调度器类似于4次迭代iSLIP。

采用队列架构，负载平衡算法几乎不增加系统的通信开销，而且不会降低通信容量。因此算法有助于实现无阻塞交换，使其不受内部加速请求的阻碍。分布式控制、简捷的实现方法以及较高的负载平衡效率使得该架构更为引人注目，并适用于以通信为内核的高容量交换架构。

Walter Wang是Mindspeed Technologies公司的高级设计师，负责交换架构开发，他于普林斯顿大学获得计算机工程硕士学位，并将获得该大学的博士学位。Email: walter.wang@mindspeed.com。

Libin Dong是Mindspeed Technologies公司成员，她在匹兹堡大学获得计算机科学博士学位，研究方向为实时通信系统、QoS管理和交换交换架构的调度算法。Email: libin.dong@mindspeed.com。

Wayne Wolf是MediaWorks Technology公司首席SoC设计师和内核科学家，他是普林斯顿大学的电子工程教授，在斯坦福大学获得电子工程学士、硕士和博士学位，研究方向是嵌入式计算、VLSI CAD和多媒体系统。Email: wolf@ee.princeton.edu。

作者：Walter Wang

高级设计师

Mindspeed Technologies公司

Libin Dong

算法工程师

Mindspeed Technologies公司

Wayne Wolf

首席SoC设计师

MediaWorks Technology公司